This terrain tutorial will cover how to implement quad trees using OpenGL 4.0 and C++.
The code in this tutorial is based on the previous tutorial.
In the previous tutorial we partitioned our terrain into 65x65 vertex cells.
The reason we did so is primarily so we can cull out the sections of the terrain we don't want to render, and focus on just rendering what is visible to the user.
So instead of rendering all two million terrain polygons we can just render the subset that is actually viewable.
And we will do this using quad trees.
There are many different space partitioning algorithms that exist which can help us reduce the number of polygons that we are drawing each frame.
Quad trees are a form of space partitioning that work very well with terrain data.
How quad trees work is that they divide the terrain into four even squares (quads).
Then each quad is further divided into four more evenly sized quads.
This division keeps going until we meet a certain criteria that we put in place.
In this tutorial the criteria will be the maximum number of triangles allowed inside a quad.
The maximum value will be set to 65x65 vertices making up 4096 triangles per quad.
To illustrate how the quad tree algorithm works we first start with a quad that encompasses the entire terrain:
Then we divide it into four quads and check if each of those quads has more than 4096 triangles in it or not:
If the quad has more than 4096 triangles in it then we divide that quad into four evenly sized quads and check again if each of the new four quads has less than 4096 triangles in it or not:
Once each of the quads in the entire quad tree has less than 4096 triangles in it we are done dividing the terrain up into sections.
And because each quad is a cube with a known location and size we can use the FrustumClass to cull any of the cubes we are not viewing.
This is where we start to gain major speed in rendering our terrain.
On average you will be culling roughly 75 percent of the terrain.
The next aspect of the quad tree algorithm is that we maintain a tree structure so that the quads are linked to each other in a parent child relationship such as the following:
So just like the three terrain pictures above the diagram uses the top node of the tree to represent the entire terrain.
The second tier of child nodes represents the first four quads that the parent terrain was split into.
The third tier represents the four child quads that each of the four parent quads got split into.
And from there the tree will continue to grow in the same fashion until it has met the criteria of when to or when not to split each quad (in this example it is by 4096 triangles maximum per quad).
Now because it is a tree structure with a parent child relationship we can use this to our advantage and gain even more speed when culling the terrain.
For example we start at the first node and check if it can be seen or not.
If we can't see the first node then the terrain can't be seen and we don't render anything.
This is a very fast check which has enabled us to exclude rendering the entire terrain to the video card.
However if we can see the first node then we go down the tree.
Next we check to see if we can view any of the four child nodes which represent the first four quads the terrain was split into.
For each quad we can't see we can then exclude checking any of its child nodes, this is where the node tree nets us incredible speed through this quick method of elimination.
The quads that can be viewed we then check their child nodes and continue down the viewable part of the tree until we have a final list of child nodes at the bottom of the tree that can be viewed.
We pass that final list of child node IDs to our node rendering function in the TerrainClass, and we render just that reduced final list of child nodes.
Finally note that most quad tree implementations do store the rendering data directly in the quad tree nodes, and we are only storing an index to the terrain node array.
You can do it both ways, but decoupling the implementation of the rendering node and the quad tree implementation helps reduce software complexity and debugging problems.
Framework
The frame work for this tutorial is the same as the previous tutorial except that we add a QuadTreeClass and FrustumClass object to it.
The FrustumClass is the same one as the OpenGL frustum culling tutorial with an additional function for rectangles.
We will start by first looking at the new QuadTreeClass.
Quadtreeclass.h
////////////////////////////////////////////////////////////////////////////////
// Filename: quadtreeclass.h
////////////////////////////////////////////////////////////////////////////////
#ifndef _QUADTREECLASS_H_
#define _QUADTREECLASS_H_
The QuadTreeClass will need to interface with the FrustumClass for culling, so the header is included here.
///////////////////////
// MY CLASS INCLUDES //
///////////////////////
#include "frustumclass.h"
////////////////////////////////////////////////////////////////////////////////
// Class name: QuadTreeClass
////////////////////////////////////////////////////////////////////////////////
class QuadTreeClass
{
private:
Each node in the quad tree will be defined as follows with position, size (width), node ID, and four child nodes:
struct NodeType
{
float positionX, positionZ, width;
int nodeID;
NodeType* nodes[4];
};
public:
QuadTreeClass();
QuadTreeClass(const QuadTreeClass&);
~QuadTreeClass();
void Initialize(float, float, float, float);
void Shutdown();
void Render(FrustumClass*, float, float);
void GetNodesDrawn(int&, int&);
void GetRenderList(int*, int&);
private:
void CreateTreeNode(NodeType*, float, float, float);
void ReleaseNode(NodeType*);
void RenderNode(NodeType*, FrustumClass*, float, float);
private:
The parent node is the root of the quad tree.
This single node will be expanded recursively to build the entire tree.
NodeType* m_parentNode;
The m_renderList will be populated each frame with the list of node IDs that can be viewed based on the combination of the frustum and the quad tree culling.
int* m_renderList;
float m_terrainWidth, m_nodeWidth, m_upperLeftX, m_upperLeftZ;
int m_nodeCount, m_visibleNodes;
};
#endif
Quadtreeclass.cpp
///////////////////////////////////////////////////////////////////////////////
// Filename: quadtreeclass.cpp
///////////////////////////////////////////////////////////////////////////////
#include "quadtreeclass.h"
The class constructor initializes the render list and quad tree parent node to null.
QuadTreeClass::QuadTreeClass()
{
m_parentNode = 0;
m_renderList = 0;
}
QuadTreeClass::QuadTreeClass(const QuadTreeClass& other)
{
}
QuadTreeClass::~QuadTreeClass()
{
}
void QuadTreeClass::Initialize(float terrainWidth, float nodeSize, float centerX, float centerZ)
{
The first thing the QuadTreeClass has to do is store all the information it will need from the TerrainClass about its dimensions.
This will be used to build the quad tree and also set the node IDs.
// Calculate upper left corner of the terrain mesh based on the center location and the size of the terrain.
m_upperLeftX = centerX - terrainWidth / 2.0f;
m_upperLeftZ = centerZ + terrainWidth / 2.0f;
// Set the width of the terrain.
m_terrainWidth = terrainWidth;
m_nodeWidth = nodeSize;
We now start the recursive method of building the quad tree by sending in the parent node first into the recursive CreateTreeNode function.
// Create the parent node for the quad tree.
m_parentNode = new NodeType;
m_nodeCount = 0;
// Recursively build the quad tree based on the mesh dimensions.
CreateTreeNode(m_parentNode, centerX, centerZ, m_terrainWidth);
The render list that is used each frame to render is created here.
// Create the render list after the nodes have been created and the node count is populated.
m_renderList = new int[m_nodeCount];
return;
}
The Shutdown function calls the ReleaseNode function which recursively traces down the tree and removes all the nodes.
The render list is also released here.
void QuadTreeClass::Shutdown()
{
// Release the render list.
if(m_renderList)
{
delete [] m_renderList;
m_renderList = 0;
}
// Recursively release the quad tree data.
if(m_parentNode)
{
ReleaseNode(m_parentNode);
delete m_parentNode;
m_parentNode = 0;
}
return;
}
The Render function calls RenderNode which goes through the tree nodes using the frustum object and determines the node visibility.
The m_visibleNodes variable must be initialized to zero before the rendering is done as it will be incremented for each node that should be drawn.
void QuadTreeClass::Render(FrustumClass* Frustum, float minHeight, float maxHeight)
{
// Reset the number of triangles that are drawn for this frame.
m_visibleNodes = 0;
// Render each node that is visible starting at the parent node and moving down the tree.
// Note we send in the min and max height from the overall terrain, as the height accuracy doesn't affect culling as much as the width and depth do in a quad tree.
RenderNode(m_parentNode, Frustum, minHeight, maxHeight);
return;
}
CreateTreeNode is the function that builds the quad tree.
Note that it is recursive and will call itself numerous times.
It starts with the parent node and then calls itself for each child node, and for each child node it calls itself for their children nodes and so forth.
It builds the entire node tree and at the same time it populates the node ID in each bottom child node.
void QuadTreeClass::CreateTreeNode(NodeType* node, float positionX, float positionZ, float width)
{
float offsetX, offsetZ, posX, posZ;
int i, j;
// Initialize the children nodes of this node to null.
node->nodes[0] = 0;
node->nodes[1] = 0;
node->nodes[2] = 0;
node->nodes[3] = 0;
// Store the node position and size.
node->positionX = positionX;
node->positionZ = positionZ;
node->width = width;
// If there are too many triangles in this node then split it into four equal sized smaller tree nodes.
if(width > m_nodeWidth)
{
for(i=0; i<4; i++)
{
// Calculate the position offsets for the new child node.
offsetX = (((i % 2) < 1) ? -1.0f : 1.0f) * (width / 4.0f);
offsetZ = (((i % 4) < 2) ? -1.0f : 1.0f) * (width / 4.0f);
// Create the child nodes.
node->nodes[i] = new NodeType;
// Extend the tree starting from this newly created child node using the calculated offsets for the new node's size and location.
CreateTreeNode(node->nodes[i], (positionX + offsetX), (positionZ + offsetZ), (width / 2.0f));
}
return;
}
// If there are the right number of triangles then we have determined that this must be a bottom child node. Therefore we set its parameters and stop traversing downward.
m_nodeCount++;
// Calculate the node ID by figuring out what ID would match up to the index of the terrain node array.
// The quad tree is built non-linear, and the terrain node array was built in a linear fashion.
// Therefore we need to use this node's position to figure out what terrain node index it would result in.
posX = positionX - (node->width / 2.0f);
posZ = positionZ + (node->width / 2.0f);
posX = posX - m_upperLeftX;
posZ = posZ - m_upperLeftZ;
i = (int)(posX / node->width);
j = (int)(posZ / node->width) * -1;
node->nodeID = j * (m_terrainWidth / m_nodeWidth) + i;
return;
}
The ReleaseNode function is used for releasing all the nodes in the quad tree.
The function is recursive and will call itself to traverse the entire node tree.
void QuadTreeClass::ReleaseNode(NodeType* node)
{
int i;
// Recursively go down the tree and release the bottom nodes first and move back upwards releasing as we go.
for(i=0; i<4; i++)
{
if(node->nodes[i] != 0)
{
ReleaseNode(node->nodes[i]);
}
}
// Delete the four child nodes for this current node.
for(i=0; i<4; i++)
{
if(node->nodes[i])
{
delete node->nodes[i];
node->nodes[i] = 0;
}
}
return;
}
RenderNode is responsible for determining all the visible nodes that should be drawn in the quad tree each frame.
It takes as input the frustum object which it uses to check if the user can view each quad or not.
It populates the render list with the visible node IDs.
Just like the other functions this is also recursive and calls itself for all the child nodes it can see.
void QuadTreeClass::RenderNode(NodeType* node, FrustumClass* Frustum, float minHeight, float maxHeight)
{
float maxWidth, maxDepth, minWidth, minDepth;
int count, i;
bool result;
// Get the dimensions of the node for the frustum to use.
maxWidth = node->positionX + (node->width / 2.0f);
minWidth = node->positionX - (node->width / 2.0f);
maxDepth = node->positionZ + (node->width / 2.0f);
minDepth = node->positionZ - (node->width / 2.0f);
// Check to see if the node can be viewed.
result = Frustum->CheckRectangle2(maxWidth, maxHeight, maxDepth, minWidth, minHeight, minDepth);
// If it can't be seen then none of its children can either so don't continue down the tree, this is where the speed is gained.
if(!result)
{
return;
}
// If it can be seen then check all four child nodes to see if they can also be seen.
count = 0;
for(i=0; i<4; i++)
{
if(node->nodes[i] != 0)
{
count++;
RenderNode(node->nodes[i], Frustum, minHeight, maxHeight);
}
}
// If there weren't any children nodes then there is no need to continue as parent nodes won't contain any triangles to render.
if(count != 0)
{
return;
}
// Otherwise if this node can be seen and has triangles in it then render these triangles. Populate the render list with this node ID so the terrain class object knows to render it.
m_renderList[m_visibleNodes] = node->nodeID;
m_visibleNodes++;
return;
}
The GetNodesDrawn function returns how many nodes were drawn this frame, as well as how many nodes were culled.
void QuadTreeClass::GetNodesDrawn(int& nodesDrawn, int& nodesCulled)
{
nodesDrawn = m_visibleNodes;
nodesCulled = m_nodeCount - m_visibleNodes;
return;
}
The GetRenderList function will be called by the TerrainClass each frame after rendering the quad tree so it can get the list of terrain nodes it needs to draw.
void QuadTreeClass::GetRenderList(int* outputRenderList, int& count)
{
count = m_visibleNodes;
memcpy(outputRenderList, m_renderList, sizeof(int) * count);
return;
}
Frustumclass.h
The FrustumClass has been updated to include a second rectangle checking function which uses the maximum boundaries instead of using the center point and distances from the center.
////////////////////////////////////////////////////////////////////////////////
// Filename: frustumclass.h
////////////////////////////////////////////////////////////////////////////////
#ifndef _FRUSTUMCLASS_H_
#define _FRUSTUMCLASS_H_
///////////////////////
// MY CLASS INCLUDES //
///////////////////////
#include "openglclass.h"
////////////////////////////////////////////////////////////////////////////////
// Class name: FrustumClass
////////////////////////////////////////////////////////////////////////////////
class FrustumClass
{
public:
FrustumClass();
FrustumClass(const FrustumClass&);
~FrustumClass();
void ConstructFrustum(OpenGLClass*, float*, float*);
bool CheckPoint(float, float, float);
bool CheckCube(float, float, float, float);
bool CheckSphere(float, float, float, float);
bool CheckRectangle(float, float, float, float, float, float);
bool CheckRectangle2(float, float, float, float, float, float);
private:
float m_planes[6][4];
};
#endif
Frustumclass.cpp
////////////////////////////////////////////////////////////////////////////////
// Filename: frustumclass.cpp
////////////////////////////////////////////////////////////////////////////////
#include "frustumclass.h"
FrustumClass::FrustumClass()
{
}
FrustumClass::FrustumClass(const FrustumClass& other)
{
}
FrustumClass::~FrustumClass()
{
}
void FrustumClass::ConstructFrustum(OpenGLClass* OpenGL, float* viewMatrix, float* projectionMatrix)
{
float matrix[16];
float t;
// Create the frustum matrix from the view matrix and updated projection matrix.
OpenGL->MatrixMultiply(matrix, viewMatrix, projectionMatrix);
// Get the near plane of the frustum.
m_planes[0][0] = matrix[3] + matrix[2];
m_planes[0][1] = matrix[7] + matrix[6];
m_planes[0][2] = matrix[11] + matrix[10];
m_planes[0][3] = matrix[15] + matrix[14];
// Normalize it.
t = (float)sqrt((m_planes[0][0] * m_planes[0][0]) + (m_planes[0][1] * m_planes[0][1]) + (m_planes[0][2] * m_planes[0][2]));
m_planes[0][0] /= t;
m_planes[0][1] /= t;
m_planes[0][2] /= t;
m_planes[0][3] /= t;
// Calculate the far plane of the frustum.
m_planes[1][0] = matrix[3] - matrix[2];
m_planes[1][1] = matrix[7] - matrix[6];
m_planes[1][2] = matrix[11] - matrix[10];
m_planes[1][3] = matrix[15] - matrix[14];
// Normalize it.
t = (float)sqrt((m_planes[1][0] * m_planes[1][0]) + (m_planes[1][1] * m_planes[1][1]) + (m_planes[1][2] * m_planes[1][2]));
m_planes[1][0] /= t;
m_planes[1][1] /= t;
m_planes[1][2] /= t;
m_planes[1][3] /= t;
// Calculate the left plane of the frustum.
m_planes[2][0] = matrix[3] + matrix[0];
m_planes[2][1] = matrix[7] + matrix[4];
m_planes[2][2] = matrix[11] + matrix[8];
m_planes[2][3] = matrix[15] + matrix[12];
// Normalize it.
t = (float)sqrt((m_planes[2][0] * m_planes[2][0]) + (m_planes[2][1] * m_planes[2][1]) + (m_planes[2][2] * m_planes[2][2]));
m_planes[2][0] /= t;
m_planes[2][1] /= t;
m_planes[2][2] /= t;
m_planes[2][3] /= t;
// Calculate the right plane of the frustum.
m_planes[3][0] = matrix[3] - matrix[0];
m_planes[3][1] = matrix[7] - matrix[4];
m_planes[3][2] = matrix[11] - matrix[8];
m_planes[3][3] = matrix[15] - matrix[12];
// Normalize it.
t = (float)sqrt((m_planes[3][0] * m_planes[3][0]) + (m_planes[3][1] * m_planes[3][1]) + (m_planes[3][2] * m_planes[3][2]));
m_planes[3][0] /= t;
m_planes[3][1] /= t;
m_planes[3][2] /= t;
m_planes[3][3] /= t;
// Calculate the top plane of the frustum.
m_planes[4][0] = matrix[3] - matrix[1];
m_planes[4][1] = matrix[7] - matrix[5];
m_planes[4][2] = matrix[11] - matrix[9];
m_planes[4][3] = matrix[15] - matrix[13];
// Normalize it.
t = (float)sqrt((m_planes[4][0] * m_planes[4][0]) + (m_planes[4][1] * m_planes[4][1]) + (m_planes[4][2] * m_planes[4][2]));
m_planes[4][0] /= t;
m_planes[4][1] /= t;
m_planes[4][2] /= t;
m_planes[4][3] /= t;
// Calculate the bottom plane of the frustum.
m_planes[5][0] = matrix[3] + matrix[1];
m_planes[5][1] = matrix[7] + matrix[5];
m_planes[5][2] = matrix[11] + matrix[9];
m_planes[5][3] = matrix[15] + matrix[13];
// Normalize it.
t = (float)sqrt((m_planes[5][0] * m_planes[5][0]) + (m_planes[5][1] * m_planes[5][1]) + (m_planes[5][2] * m_planes[5][2]));
m_planes[5][0] /= t;
m_planes[5][1] /= t;
m_planes[5][2] /= t;
m_planes[5][3] /= t;
return;
}
bool FrustumClass::CheckPoint(float x, float y, float z)
{
int i;
// Check if the point is inside all six planes of the view frustum.
for(i=0; i<6; i++)
{
if(((m_planes[i][0] * x) + (m_planes[i][1] * y) + (m_planes[i][2] * z) + m_planes[i][3]) < 0.0f)
{
return false;
}
}
return true;
}
bool FrustumClass::CheckCube(float xCenter, float yCenter, float zCenter, float radius)
{
int i;
// Check if any one point of the cube is in the view frustum.
for(i=0; i<6; i++)
{
if(m_planes[i][0] * (xCenter - radius) +
m_planes[i][1] * (yCenter - radius) +
m_planes[i][2] * (zCenter - radius) + m_planes[i][3] > 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter + radius) +
m_planes[i][1] * (yCenter - radius) +
m_planes[i][2] * (zCenter - radius) + m_planes[i][3] > 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter - radius) +
m_planes[i][1] * (yCenter + radius) +
m_planes[i][2] * (zCenter - radius) + m_planes[i][3] > 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter + radius) +
m_planes[i][1] * (yCenter + radius) +
m_planes[i][2] * (zCenter - radius) + m_planes[i][3] > 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter - radius) +
m_planes[i][1] * (yCenter - radius) +
m_planes[i][2] * (zCenter + radius) + m_planes[i][3] > 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter + radius) +
m_planes[i][1] * (yCenter - radius) +
m_planes[i][2] * (zCenter + radius) + m_planes[i][3] > 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter - radius) +
m_planes[i][1] * (yCenter + radius) +
m_planes[i][2] * (zCenter + radius) + m_planes[i][3] > 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter + radius) +
m_planes[i][1] * (yCenter + radius) +
m_planes[i][2] * (zCenter + radius) + m_planes[i][3] > 0.0f)
{
continue;
}
return false;
}
return true;
}
bool FrustumClass::CheckSphere(float xCenter, float yCenter, float zCenter, float radius)
{
int i;
// Check if the radius of the sphere is inside the view frustum.
for(i=0; i<6; i++)
{
if(((m_planes[i][0] * xCenter) + (m_planes[i][1] * yCenter) + (m_planes[i][2] * zCenter) + m_planes[i][3]) < -radius)
{
return false;
}
}
return true;
}
bool FrustumClass::CheckRectangle(float xCenter, float yCenter, float zCenter, float xSize, float ySize, float zSize)
{
int i;
// Check if any of the 6 planes of the rectangle are inside the view frustum.
for(i=0; i<6; i++)
{
if(m_planes[i][0] * (xCenter - xSize) +
m_planes[i][1] * (yCenter - ySize) +
m_planes[i][2] * (zCenter - zSize) + m_planes[i][3] >= 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter + xSize) +
m_planes[i][1] * (yCenter - ySize) +
m_planes[i][2] * (zCenter - zSize) + m_planes[i][3] >= 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter - xSize) +
m_planes[i][1] * (yCenter + ySize) +
m_planes[i][2] * (zCenter - zSize) + m_planes[i][3] >= 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter - xSize) +
m_planes[i][1] * (yCenter - ySize) +
m_planes[i][2] * (zCenter + zSize) + m_planes[i][3] >= 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter + xSize) +
m_planes[i][1] * (yCenter + ySize) +
m_planes[i][2] * (zCenter - zSize) + m_planes[i][3] >= 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter + xSize) +
m_planes[i][1] * (yCenter - ySize) +
m_planes[i][2] * (zCenter + zSize) + m_planes[i][3] >= 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter - xSize) +
m_planes[i][1] * (yCenter + ySize) +
m_planes[i][2] * (zCenter + zSize) + m_planes[i][3] >= 0.0f)
{
continue;
}
if(m_planes[i][0] * (xCenter + xSize) +
m_planes[i][1] * (yCenter + ySize) +
m_planes[i][2] * (zCenter + zSize) + m_planes[i][3] >= 0.0f)
{
continue;
}
return false;
}
return true;
}
bool FrustumClass::CheckRectangle2(float maxWidth, float maxHeight, float maxDepth, float minWidth, float minHeight, float minDepth)
{
int i;
float dotProduct;
// Check if any of the 6 planes of the rectangle are inside the view frustum.
for(i=0; i<6; i++)
{
dotProduct = ((m_planes[i][0] * minWidth) + (m_planes[i][1] * minHeight) + (m_planes[i][2] * minDepth) + (m_planes[i][3] * 1.0f));
if(dotProduct >= 0.0f)
{
continue;
}
dotProduct = ((m_planes[i][0] * maxWidth) + (m_planes[i][1] * minHeight) + (m_planes[i][2] * minDepth) + (m_planes[i][3] * 1.0f));
if(dotProduct >= 0.0f)
{
continue;
}
dotProduct = ((m_planes[i][0] * minWidth) + (m_planes[i][1] * maxHeight) + (m_planes[i][2] * minDepth) + (m_planes[i][3] * 1.0f));
if(dotProduct >= 0.0f)
{
continue;
}
dotProduct = ((m_planes[i][0] * maxWidth) + (m_planes[i][1] * maxHeight) + (m_planes[i][2] * minDepth) + (m_planes[i][3] * 1.0f));
if(dotProduct >= 0.0f)
{
continue;
}
dotProduct = ((m_planes[i][0] * minWidth) + (m_planes[i][1] * minHeight) + (m_planes[i][2] * maxDepth) + (m_planes[i][3] * 1.0f));
if(dotProduct >= 0.0f)
{
continue;
}
dotProduct = ((m_planes[i][0] * maxWidth) + (m_planes[i][1] * minHeight) + (m_planes[i][2] * maxDepth) + (m_planes[i][3] * 1.0f));
if(dotProduct >= 0.0f)
{
continue;
}
dotProduct = ((m_planes[i][0] * minWidth) + (m_planes[i][1] * maxHeight) + (m_planes[i][2] * maxDepth) + (m_planes[i][3] * 1.0f));
if(dotProduct >= 0.0f)
{
continue;
}
dotProduct = ((m_planes[i][0] * maxWidth) + (m_planes[i][1] * maxHeight) + (m_planes[i][2] * maxDepth) + (m_planes[i][3] * 1.0f));
if(dotProduct >= 0.0f)
{
continue;
}
return false;
}
return true;
}
Terrainclass.h
We have now added the QuadTreeClass to the TerrainClass.
The are also new functions like GetNodesDrawn for getting how many nodes were drawn and culled, and also CalculateMeshDimensions which is used to help build the quad tree using the terrain's dimensions.
You will also see that the FrustumClass is now passed into the Render function for the TerrainClass.
////////////////////////////////////////////////////////////////////////////////
// Filename: terrainclass.h
////////////////////////////////////////////////////////////////////////////////
#ifndef _TERRAINCLASS_H_
#define _TERRAINCLASS_H_
//////////////
// INCLUDES //
//////////////
#include <fstream>
using namespace std;
///////////////////////
// MY CLASS INCLUDES //
///////////////////////
#include "shadermanagerclass.h"
#include "textureclass.h"
#include "lightclass.h"
#include "terrainnodeclass.h"
#include "quadtreeclass.h"
////////////////////////////////////////////////////////////////////////////////
// Class name: TerrainClass
////////////////////////////////////////////////////////////////////////////////
class TerrainClass
{
private:
struct VertexType
{
float x, y, z;
float tu, tv;
float nx, ny, nz;
float tx, ty, tz;
float bx, by, bz;
float r, g, b;
};
struct HeightMapType
{
float x, y, z;
float nx, ny, nz;
float r, g, b;
};
struct ModelType
{
float x, y, z;
float tu, tv;
float nx, ny, nz;
float tx, ty, tz;
float bx, by, bz;
float r, g, b;
};
struct VectorType
{
float x, y, z;
};
struct TargaHeader
{
unsigned char data1[12];
unsigned short width;
unsigned short height;
unsigned char bpp;
unsigned char data2;
};
struct TempVertexType
{
float x, y, z;
float tu, tv;
float nx, ny, nz;
};
public:
TerrainClass();
TerrainClass(const TerrainClass&);
~TerrainClass();
bool Initialize(OpenGLClass*, char*);
void Shutdown(OpenGLClass*);
bool Render(OpenGLClass*, ShaderManagerClass*, LightClass*, FrustumClass*, float*, float*, float*);
void GetNodesDrawn(int&, int&);
private:
bool LoadSetupFile(char*, char*, float&, char*, char*, char*);
bool LoadRawHeightMap(char*);
void SetTerrainCoordinates(float);
void CalculateNormals();
bool LoadColorMap(char*);
void BuildTerrainModel();
void ReleaseHeightMap();
void ReleaseTerrainModel();
void CalculateTerrainVectors();
void CalculateTangentBinormal(TempVertexType, TempVertexType, TempVertexType, VectorType&, VectorType&);
bool LoadTerrainNodes(OpenGLClass*);
void ReleaseTerrainNodes(OpenGLClass*);
void CalculateMeshDimensions();
private:
int m_vertexCount;
int m_terrainHeight, m_terrainWidth;
HeightMapType* m_heightMap;
ModelType* m_terrainModel;
TerrainNodeClass* m_Nodes;
int m_nodeCount;
TextureClass *m_Texture, *m_NormalMap;
QuadTreeClass* m_QuadTree;
int* m_renderList;
float m_minHeight, m_maxHeight;
};
#endif
Terrainclass.cpp
///////////////////////////////////////////////////////////////////////////////
// Filename: terrainclass.cpp
///////////////////////////////////////////////////////////////////////////////
#include "terrainclass.h"
TerrainClass::TerrainClass()
{
m_heightMap = 0;
m_terrainModel = 0;
m_Nodes = 0;
m_Texture = 0;
m_NormalMap = 0;
m_QuadTree = 0;
m_renderList = 0;
}
TerrainClass::TerrainClass(const TerrainClass& other)
{
}
TerrainClass::~TerrainClass()
{
}
bool TerrainClass::Initialize(OpenGLClass* OpenGL, char* setupFilename)
{
char terrainFilename[256], textureFilename[256], colorMapFilename[256], normalFilename[256];
float heightScale;
bool result;
// Get the terrain filename, dimensions, and so forth from the setup file.
result = LoadSetupFile(setupFilename, terrainFilename, heightScale, textureFilename, colorMapFilename, normalFilename);
if(!result)
{
return false;
}
// Initialize the terrain height map with the data from the raw file.
result = LoadRawHeightMap(terrainFilename);
if(!result)
{
return false;
}
// Setup the X and Z coordinates for the height map as well as scale the terrain height by the height scale value.
SetTerrainCoordinates(heightScale);
// Calculate the normals for the terrain data.
CalculateNormals();
// Load in the color map for the terrain.
result = LoadColorMap(colorMapFilename);
if(!result)
{
return false;
}
// Now build the 3D model of the terrain.
BuildTerrainModel();
// We can now release the height map since it is no longer needed in memory once the 3D terrain model has been built.
ReleaseHeightMap();
// Calculate the tangent and binormal for the terrain model.
CalculateTerrainVectors();
The new CalculateMeshDimensions function get called here the store the min and max height of the terrain model before it gets released.
These values will be used each frame for culling nodes in the quad tree.
// Calculate the dimensions of the mesh for the quad tree's usage.
CalculateMeshDimensions();
// Copy the terrain model data into the individual terrain nodes.
result = LoadTerrainNodes(OpenGL);
if(!result)
{
return false;
}
// Release the terrain model now that the nodes have been loaded.
ReleaseTerrainModel();
// Create and initialize the diffuse texture object.
m_Texture = new TextureClass;
result = m_Texture->Initialize(OpenGL, textureFilename, false);
if(!result)
{
return false;
}
// Create and initialize the normal map texture object.
m_NormalMap = new TextureClass;
result = m_NormalMap->Initialize(OpenGL, normalFilename, false);
if(!result)
{
return false;
}
return true;
}
void TerrainClass::Shutdown(OpenGLClass* OpenGL)
{
// Release the normal map texture object.
if(m_NormalMap)
{
m_NormalMap->Shutdown();
delete m_NormalMap;
m_NormalMap = 0;
}
// Release the diffuse texture object.
if(m_Texture)
{
m_Texture->Shutdown();
delete m_Texture;
m_Texture = 0;
}
// Release the terrain nodes.
ReleaseTerrainNodes(OpenGL);
return;
}
bool TerrainClass::Render(OpenGLClass* OpenGL, ShaderManagerClass* ShaderManager, LightClass* Light, FrustumClass* Frustum, float* worldMatrix, float* viewMatrix, float* projectionMatrix)
{
float diffuseLightColor[4], lightDirection[3];
int i, j, renderCount;
bool result, wireFrame, renderNodeLines;
// Get the light properties.
Light->GetDirection(lightDirection);
Light->GetDiffuseColor(diffuseLightColor);
// Set wireframe mode off.
wireFrame = false;
// Set node bounding box line rendering on.
renderNodeLines = true;
// Enable wireframe mode to see triangles composing the terrain clearly.
if(wireFrame)
{
OpenGL->EnableWireframe();
}
Now use the quad tree Render function to determine all the visible nodes in the quad tree using the frustum object for culling.
After it is done get the render list and render count from the quad tree so we can render just the visible nodes in this function.
// Get the list of nodes to render.
m_QuadTree->Render(Frustum, m_minHeight, m_maxHeight);
m_QuadTree->GetRenderList(m_renderList, renderCount);
// Set the terrain shader as the current shader program and set the matrices that it will use for rendering.
result = ShaderManager->RenderTerrainShader(worldMatrix, viewMatrix, projectionMatrix, lightDirection, diffuseLightColor);
if(!result)
{
return false;
}
// Set the diffuse texture for the terrain in the pixel shader texture unit 0.
m_Texture->SetTexture(OpenGL, 0);
// Set the normal map texture for the terrain in the pixel shader texture unit 1.
m_NormalMap->SetTexture(OpenGL, 1);
Render only the visible nodes using the render list provided by the quad tree this frame.
// Put the node vertex and index buffers on the graphics pipeline to prepare them for drawing.
for(i=0; i<renderCount; i++)
{
// Only render the list of nodes that the quad tree determined are visible.
j = m_renderList[i];
m_Nodes[j].Render(OpenGL);
}
// Disable wireframe mode after rendering terrain.
if(wireFrame)
{
OpenGL->DisableWireframe();
}
// Render the node bounding box lines.
if(renderNodeLines)
{
result = ShaderManager->RenderColorShader(worldMatrix, viewMatrix, projectionMatrix);
if(!result)
{
return false;
}
Likewise, we only render the visible bounding boxes using the same render list of node IDs provided by the quad tree.
for(i=0; i<renderCount; i++)
{
// Only render the node bounding boxes that the quad tree determined are visible.
j = m_renderList[i];
m_Nodes[j].RenderLines(OpenGL);
}
}
return true;
}
bool TerrainClass::LoadSetupFile(char* filename, char* terrainFilename, float& heightScale, char* textureFilename, char* colorMapFilename, char* normalFilename)
{
ifstream fin;
char input;
// Open the setup file. If it could not open the file then exit.
fin.open(filename);
if(fin.fail())
{
return false;
}
// Read up to the terrain file name.
fin.get(input);
while(input != ':')
{
fin.get(input);
}
// Read in the terrain file name.
fin >> terrainFilename;
// Read up to the color map file name.
fin.get(input);
while(input != ':')
{
fin.get(input);
}
// Read in the color map file name.
fin >> colorMapFilename;
// Read up to the value of terrain height.
fin.get(input);
while(input != ':')
{
fin.get(input);
}
// Read in the terrain height.
fin >> m_terrainHeight;
// Read up to the value of terrain width.
fin.get(input);
while(input != ':')
{
fin.get(input);
}
// Read in the terrain width.
fin >> m_terrainWidth;
// Read up to the value of terrain height scaling.
fin.get(input);
while(input != ':')
{
fin.get(input);
}
// Read in the terrain height scaling.
fin >> heightScale;
// Read up to the texture file name.
fin.get(input);
while(input != ':')
{
fin.get(input);
}
// Read in the texture file name.
fin >> textureFilename;
// Read up to the normal map texture file name.
fin.get(input);
while(input != ':')
{
fin.get(input);
}
// Read in the normal map file name.
fin >> normalFilename;
// Close the setup file.
fin.close();
return true;
}
bool TerrainClass::LoadRawHeightMap(char* terrainFilename)
{
FILE* filePtr;
unsigned short* rawImage;
unsigned int imageSize, count;
int error, i, j, index;
// Create the float array to hold the height map data.
m_heightMap = new HeightMapType[m_terrainWidth * m_terrainHeight];
// Open the 16 bit raw height map file for reading in binary.
filePtr = fopen(terrainFilename, "rb");
if(filePtr == NULL)
{
return false;
}
// Calculate the size of the raw image data.
imageSize = m_terrainHeight * m_terrainWidth;
// Allocate memory for the raw image data.
rawImage = new unsigned short[imageSize];
// Read in the raw image data.
count = fread(rawImage, sizeof(unsigned short), imageSize, filePtr);
if(count != imageSize)
{
return false;
}
// Close the file.
error = fclose(filePtr);
if(error != 0)
{
return false;
}
// Copy the image data into the height map array.
for(j=0; j<m_terrainHeight; j++)
{
for(i=0; i<m_terrainWidth; i++)
{
index = (m_terrainWidth * j) + i;
// Store the height at this point in the height map array.
m_heightMap[index].y = (float)rawImage[index];
}
}
// Release the bitmap image data.
delete [] rawImage;
rawImage = 0;
return true;
}
void TerrainClass::SetTerrainCoordinates(float heightScale)
{
int i, j, index;
// Loop through all the elements in the height map array and adjust their coordinates correctly.
for(j=0; j<m_terrainHeight; j++)
{
for(i=0; i<m_terrainWidth; i++)
{
index = (m_terrainWidth * j) + i;
// Set the X and Z coordinates.
m_heightMap[index].x = (float)i;
m_heightMap[index].z = -(float)j;
// Move the terrain depth into the positive range. For example from (0, -256) to (256, 0).
m_heightMap[index].z += (float)(m_terrainHeight - 1);
// Scale the height.
m_heightMap[index].y /= heightScale;
}
}
return;
}
void TerrainClass::CalculateNormals()
{
int i, j, index1, index2, index3, index;
float vertex1[3], vertex2[3], vertex3[3], vector1[3], vector2[3], sum[3], length;
VectorType* normals;
// Create a temporary array to hold the face normal vectors.
normals = new VectorType[(m_terrainHeight-1) * (m_terrainWidth-1)];
// Go through all the faces in the mesh and calculate their normals.
for(j=0; j<(m_terrainHeight-1); j++)
{
for(i=0; i<(m_terrainWidth-1); i++)
{
index1 = ((j+1) * m_terrainWidth) + i; // Bottom left vertex.
index2 = ((j+1) * m_terrainWidth) + (i+1); // Bottom right vertex.
index3 = (j * m_terrainWidth) + i; // Upper left vertex.
// Get three vertices from the face.
vertex1[0] = m_heightMap[index1].x;
vertex1[1] = m_heightMap[index1].y;
vertex1[2] = m_heightMap[index1].z;
vertex2[0] = m_heightMap[index2].x;
vertex2[1] = m_heightMap[index2].y;
vertex2[2] = m_heightMap[index2].z;
vertex3[0] = m_heightMap[index3].x;
vertex3[1] = m_heightMap[index3].y;
vertex3[2] = m_heightMap[index3].z;
// Calculate the two vectors for this face.
vector1[0] = vertex1[0] - vertex3[0];
vector1[1] = vertex1[1] - vertex3[1];
vector1[2] = vertex1[2] - vertex3[2];
vector2[0] = vertex3[0] - vertex2[0];
vector2[1] = vertex3[1] - vertex2[1];
vector2[2] = vertex3[2] - vertex2[2];
index = (j * (m_terrainWidth - 1)) + i;
// Calculate the cross product of those two vectors to get the un-normalized value for this face normal.
normals[index].x = (vector1[1] * vector2[2]) - (vector1[2] * vector2[1]);
normals[index].y = (vector1[2] * vector2[0]) - (vector1[0] * vector2[2]);
normals[index].z = (vector1[0] * vector2[1]) - (vector1[1] * vector2[0]);
// Calculate the length.
length = (float)sqrt((normals[index].x * normals[index].x) + (normals[index].y * normals[index].y) +
(normals[index].z * normals[index].z));
// Normalize the final value for this face using the length.
normals[index].x = (normals[index].x / length);
normals[index].y = (normals[index].y / length);
normals[index].z = (normals[index].z / length);
}
}
// Now go through all the vertices and take a sum of the face normals that touch this vertex.
for(j=0; j<m_terrainHeight; j++)
{
for(i=0; i<m_terrainWidth; i++)
{
// Initialize the sum.
sum[0] = 0.0f;
sum[1] = 0.0f;
sum[2] = 0.0f;
// Bottom left face.
if(((i-1) >= 0) && ((j-1) >= 0))
{
index = ((j-1) * (m_terrainWidth-1)) + (i-1);
sum[0] += normals[index].x;
sum[1] += normals[index].y;
sum[2] += normals[index].z;
}
// Bottom right face.
if((i<(m_terrainWidth-1)) && ((j-1) >= 0))
{
index = ((j - 1) * (m_terrainWidth - 1)) + i;
sum[0] += normals[index].x;
sum[1] += normals[index].y;
sum[2] += normals[index].z;
}
// Upper left face.
if(((i-1) >= 0) && (j<(m_terrainHeight-1)))
{
index = (j * (m_terrainWidth-1)) + (i-1);
sum[0] += normals[index].x;
sum[1] += normals[index].y;
sum[2] += normals[index].z;
}
// Upper right face.
if((i < (m_terrainWidth-1)) && (j < (m_terrainHeight-1)))
{
index = (j * (m_terrainWidth-1)) + i;
sum[0] += normals[index].x;
sum[1] += normals[index].y;
sum[2] += normals[index].z;
}
// Calculate the length of this normal.
length = (float)sqrt((sum[0] * sum[0]) + (sum[1] * sum[1]) + (sum[2] * sum[2]));
// Get an index to the vertex location in the height map array.
index = (j * m_terrainWidth) + i;
// Normalize the final shared normal for this vertex and store it in the height map array.
m_heightMap[index].nx = (sum[0] / length);
m_heightMap[index].ny = (sum[1] / length);
m_heightMap[index].nz = (sum[2] / length);
}
}
// Release the temporary normals.
delete [] normals;
normals = 0;
return;
}
bool TerrainClass::LoadColorMap(char* colorMapFilename)
{
FILE* filePtr;
TargaHeader targaFileHeader;
unsigned char* targaImage;
unsigned long count, imageSize;
int height, width, bpp, error, i, j, k, index;
// Open the color map file in binary.
filePtr = fopen(colorMapFilename, "rb");
if(filePtr == NULL)
{
return false;
}
// Read in the file header.
count = fread(&targaFileHeader, sizeof(TargaHeader), 1, filePtr);
if(count != 1)
{
return false;
}
// Get the important information from the header.
width = (int)targaFileHeader.width;
height = (int)targaFileHeader.height;
bpp = (int)targaFileHeader.bpp;
// Make sure the color map dimensions are the same as the terrain dimensions for easy 1 to 1 mapping.
if((height != m_terrainHeight) || (width != m_terrainWidth))
{
return false;
}
// Make sure we are dealing with 24 bit color maps.
if(bpp != 24)
{
return false;
}
// Calculate the size of the 24 bit targa image data.
imageSize = width * height * 3;
// Allocate memory for the targa image data.
targaImage = new unsigned char[imageSize];
// Read in the targa image data.
count = fread(targaImage, 1, imageSize, filePtr);
if(count != imageSize)
{
return false;
}
// Close the file.
error = fclose(filePtr);
if(error != 0)
{
return false;
}
// Initialize the position in the targa image data buffer.
k=0;
// Read the image data into the color map portion of the height map structure.
for(j=0; j<m_terrainHeight; j++)
{
for(i=0; i<m_terrainWidth; i++)
{
// Targa are saved upside down by default in most image editors, so load bottom to top into the array.
index = (m_terrainWidth * (m_terrainHeight - 1 - j)) + i;
m_heightMap[index].r = (float)targaImage[k+2] / 255.0f;
m_heightMap[index].g = (float)targaImage[k+1] / 255.0f;
m_heightMap[index].b = (float)targaImage[k+0] / 255.0f;
k+=3;
}
}
// Release the targa image data.
delete [] targaImage;
targaImage = 0;
return true;
}
void TerrainClass::BuildTerrainModel()
{
int i, j, index, index1, index2, index3, index4;
// Calculate the number of vertices in the 3D terrain model.
m_vertexCount = (m_terrainHeight - 1) * (m_terrainWidth - 1) * 6;
// Create the 3D terrain model array.
m_terrainModel = new ModelType[m_vertexCount];
// Initialize the index into the height map array.
index = 0;
// Load the 3D terrain model with the height map terrain data.
// We will be creating 2 triangles for each of the four points in a quad.
for(j=0; j<(m_terrainHeight-1); j++)
{
for(i=0; i<(m_terrainWidth-1); i++)
{
// Get the indexes to the four points of the quad.
index1 = (m_terrainWidth * j) + i; // Upper left.
index2 = (m_terrainWidth * j) + (i+1); // Upper right.
index3 = (m_terrainWidth * (j+1)) + i; // Bottom left.
index4 = (m_terrainWidth * (j+1)) + (i+1); // Bottom right.
// Now create two triangles for that quad.
// Triangle 1 - Upper left.
m_terrainModel[index].x = m_heightMap[index1].x;
m_terrainModel[index].y = m_heightMap[index1].y;
m_terrainModel[index].z = m_heightMap[index1].z;
m_terrainModel[index].tu = 0.0f;
m_terrainModel[index].tv = 1.0f;
m_terrainModel[index].nx = m_heightMap[index1].nx;
m_terrainModel[index].ny = m_heightMap[index1].ny;
m_terrainModel[index].nz = m_heightMap[index1].nz;
m_terrainModel[index].r = m_heightMap[index1].r;
m_terrainModel[index].g = m_heightMap[index1].g;
m_terrainModel[index].b = m_heightMap[index1].b;
index++;
// Triangle 1 - Upper right.
m_terrainModel[index].x = m_heightMap[index2].x;
m_terrainModel[index].y = m_heightMap[index2].y;
m_terrainModel[index].z = m_heightMap[index2].z;
m_terrainModel[index].tu = 1.0f;
m_terrainModel[index].tv = 1.0f;
m_terrainModel[index].nx = m_heightMap[index2].nx;
m_terrainModel[index].ny = m_heightMap[index2].ny;
m_terrainModel[index].nz = m_heightMap[index2].nz;
m_terrainModel[index].r = m_heightMap[index2].r;
m_terrainModel[index].g = m_heightMap[index2].g;
m_terrainModel[index].b = m_heightMap[index2].b;
index++;
// Triangle 1 - Bottom left.
m_terrainModel[index].x = m_heightMap[index3].x;
m_terrainModel[index].y = m_heightMap[index3].y;
m_terrainModel[index].z = m_heightMap[index3].z;
m_terrainModel[index].tu = 0.0f;
m_terrainModel[index].tv = 0.0f;
m_terrainModel[index].nx = m_heightMap[index3].nx;
m_terrainModel[index].ny = m_heightMap[index3].ny;
m_terrainModel[index].nz = m_heightMap[index3].nz;
m_terrainModel[index].r = m_heightMap[index3].r;
m_terrainModel[index].g = m_heightMap[index3].g;
m_terrainModel[index].b = m_heightMap[index3].b;
index++;
// Triangle 2 - Bottom left.
m_terrainModel[index].x = m_heightMap[index3].x;
m_terrainModel[index].y = m_heightMap[index3].y;
m_terrainModel[index].z = m_heightMap[index3].z;
m_terrainModel[index].tu = 0.0f;
m_terrainModel[index].tv = 0.0f;
m_terrainModel[index].nx = m_heightMap[index3].nx;
m_terrainModel[index].ny = m_heightMap[index3].ny;
m_terrainModel[index].nz = m_heightMap[index3].nz;
m_terrainModel[index].r = m_heightMap[index3].r;
m_terrainModel[index].g = m_heightMap[index3].g;
m_terrainModel[index].b = m_heightMap[index3].b;
index++;
// Triangle 2 - Upper right.
m_terrainModel[index].x = m_heightMap[index2].x;
m_terrainModel[index].y = m_heightMap[index2].y;
m_terrainModel[index].z = m_heightMap[index2].z;
m_terrainModel[index].tu = 1.0f;
m_terrainModel[index].tv = 1.0f;
m_terrainModel[index].nx = m_heightMap[index2].nx;
m_terrainModel[index].ny = m_heightMap[index2].ny;
m_terrainModel[index].nz = m_heightMap[index2].nz;
m_terrainModel[index].r = m_heightMap[index2].r;
m_terrainModel[index].g = m_heightMap[index2].g;
m_terrainModel[index].b = m_heightMap[index2].b;
index++;
// Triangle 2 - Bottom right.
m_terrainModel[index].x = m_heightMap[index4].x;
m_terrainModel[index].y = m_heightMap[index4].y;
m_terrainModel[index].z = m_heightMap[index4].z;
m_terrainModel[index].tu = 1.0f;
m_terrainModel[index].tv = 0.0f;
m_terrainModel[index].nx = m_heightMap[index4].nx;
m_terrainModel[index].ny = m_heightMap[index4].ny;
m_terrainModel[index].nz = m_heightMap[index4].nz;
m_terrainModel[index].r = m_heightMap[index4].r;
m_terrainModel[index].g = m_heightMap[index4].g;
m_terrainModel[index].b = m_heightMap[index4].b;
index++;
}
}
return;
}
void TerrainClass::ReleaseHeightMap()
{
// Release the height map array.
if(m_heightMap)
{
delete [] m_heightMap;
m_heightMap = 0;
}
return;
}
void TerrainClass::ReleaseTerrainModel()
{
// Release the terrain model data.
if(m_terrainModel)
{
delete [] m_terrainModel;
m_terrainModel = 0;
}
return;
}
void TerrainClass::CalculateTerrainVectors()
{
int vertexCount, faceCount, i, index;
TempVertexType vertex1, vertex2, vertex3;
VectorType tangent, binormal;
// Calculate the number of vertices in the terrain.
vertexCount = (m_terrainHeight - 1) * (m_terrainWidth - 1) * 6;
// Calculate the number of faces in the terrain model.
faceCount = vertexCount / 3;
// Initialize the index to the model data.
index = 0;
// Go through all the faces and calculate the the tangent, binormal, and normal vectors.
for(i=0; i<faceCount; i++)
{
// Get the three vertices for this face from the terrain model.
vertex1.x = m_terrainModel[index].x;
vertex1.y = m_terrainModel[index].y;
vertex1.z = m_terrainModel[index].z;
vertex1.tu = m_terrainModel[index].tu;
vertex1.tv = m_terrainModel[index].tv;
vertex1.nx = m_terrainModel[index].nx;
vertex1.ny = m_terrainModel[index].ny;
vertex1.nz = m_terrainModel[index].nz;
index++;
vertex2.x = m_terrainModel[index].x;
vertex2.y = m_terrainModel[index].y;
vertex2.z = m_terrainModel[index].z;
vertex2.tu = m_terrainModel[index].tu;
vertex2.tv = m_terrainModel[index].tv;
vertex2.nx = m_terrainModel[index].nx;
vertex2.ny = m_terrainModel[index].ny;
vertex2.nz = m_terrainModel[index].nz;
index++;
vertex3.x = m_terrainModel[index].x;
vertex3.y = m_terrainModel[index].y;
vertex3.z = m_terrainModel[index].z;
vertex3.tu = m_terrainModel[index].tu;
vertex3.tv = m_terrainModel[index].tv;
vertex3.nx = m_terrainModel[index].nx;
vertex3.ny = m_terrainModel[index].ny;
vertex3.nz = m_terrainModel[index].nz;
index++;
// Calculate the tangent and binormal of that face.
CalculateTangentBinormal(vertex1, vertex2, vertex3, tangent, binormal);
// Store the tangent and binormal for this face back in the model structure.
m_terrainModel[index-1].tx = tangent.x;
m_terrainModel[index-1].ty = tangent.y;
m_terrainModel[index-1].tz = tangent.z;
m_terrainModel[index-1].bx = binormal.x;
m_terrainModel[index-1].by = binormal.y;
m_terrainModel[index-1].bz = binormal.z;
m_terrainModel[index-2].tx = tangent.x;
m_terrainModel[index-2].ty = tangent.y;
m_terrainModel[index-2].tz = tangent.z;
m_terrainModel[index-2].bx = binormal.x;
m_terrainModel[index-2].by = binormal.y;
m_terrainModel[index-2].bz = binormal.z;
m_terrainModel[index-3].tx = tangent.x;
m_terrainModel[index-3].ty = tangent.y;
m_terrainModel[index-3].tz = tangent.z;
m_terrainModel[index-3].bx = binormal.x;
m_terrainModel[index-3].by = binormal.y;
m_terrainModel[index-3].bz = binormal.z;
}
return;
}
void TerrainClass::CalculateTangentBinormal(TempVertexType vertex1, TempVertexType vertex2, TempVertexType vertex3, VectorType& tangent, VectorType& binormal)
{
float vector1[3], vector2[3];
float tuVector[2], tvVector[2];
float den;
float length;
// Calculate the two vectors for this face.
vector1[0] = vertex2.x - vertex1.x;
vector1[1] = vertex2.y - vertex1.y;
vector1[2] = vertex2.z - vertex1.z;
vector2[0] = vertex3.x - vertex1.x;
vector2[1] = vertex3.y - vertex1.y;
vector2[2] = vertex3.z - vertex1.z;
// Calculate the tu and tv texture space vectors.
tuVector[0] = vertex2.tu - vertex1.tu;
tvVector[0] = vertex2.tv - vertex1.tv;
tuVector[1] = vertex3.tu - vertex1.tu;
tvVector[1] = vertex3.tv - vertex1.tv;
// Calculate the denominator of the tangent/binormal equation.
den = 1.0f / (tuVector[0] * tvVector[1] - tuVector[1] * tvVector[0]);
// Calculate the cross products and multiply by the coefficient to get the tangent and binormal.
tangent.x = (tvVector[1] * vector1[0] - tvVector[0] * vector2[0]) * den;
tangent.y = (tvVector[1] * vector1[1] - tvVector[0] * vector2[1]) * den;
tangent.z = (tvVector[1] * vector1[2] - tvVector[0] * vector2[2]) * den;
binormal.x = (tuVector[0] * vector2[0] - tuVector[1] * vector1[0]) * den;
binormal.y = (tuVector[0] * vector2[1] - tuVector[1] * vector1[1]) * den;
binormal.z = (tuVector[0] * vector2[2] - tuVector[1] * vector1[2]) * den;
// Calculate the length of the tangent.
length = (float)sqrt((tangent.x * tangent.x) + (tangent.y * tangent.y) + (tangent.z * tangent.z));
// Normalize the tangent and then store it.
tangent.x = tangent.x / length;
tangent.y = tangent.y / length;
tangent.z = tangent.z / length;
// Calculate the length of the binormal.
length = (float)sqrt((binormal.x * binormal.x) + (binormal.y * binormal.y) + (binormal.z * binormal.z));
// Normalize the binormal and then store it.
binormal.x = binormal.x / length;
binormal.y = binormal.y / length;
binormal.z = binormal.z / length;
return;
}
bool TerrainClass::LoadTerrainNodes(OpenGLClass* OpenGL)
{
int nodeWidth, arrayHeight, arrayWidth, i, j, index;
// Set the width of the node. 64 +1 (0-64) since dealing with 1025 sized terrain and need even division.
nodeWidth = 65;
// Set size of the node array that we are breaking the terrain up into. Must alight with the terrain size and the node width.
arrayHeight = 16;
arrayWidth = 16;
// Set the number of nodes in the 2D array.
m_nodeCount = arrayHeight * arrayWidth;
// Create the terrain node array.
m_Nodes = new TerrainNodeClass[m_nodeCount];
// Loop through and initialize all the terrain nodes.
for(j=0; j<arrayHeight; j++)
{
for(i=0; i<arrayWidth; i++)
{
index = (arrayWidth * j) + i;
m_Nodes[index].Initialize(OpenGL, m_terrainModel, m_terrainWidth, nodeWidth, nodeWidth, i, j);
}
}
We create the quad tree and the render list in the LoadTerrainNodes function.
// Create and initialize the quad tree object.
m_QuadTree = new QuadTreeClass;
m_QuadTree->Initialize((m_terrainWidth-1), (nodeWidth - 1), 512.0f, 512.0f);
// Create the render list for the quad tree.
m_renderList = new int[m_nodeCount];
return true;
}
void TerrainClass::ReleaseTerrainNodes(OpenGLClass* OpenGL)
{
int i;
The quad tree and the render list are released in the ReleaseTerrainNodes function.
// Release the render list.
if(m_renderList)
{
delete [] m_renderList;
m_renderList = 0;
}
// Release the quad tree object.
if(m_QuadTree)
{
m_QuadTree->Shutdown();
delete m_QuadTree;
m_QuadTree = 0;
}
// Release the terrain node array.
if(m_Nodes)
{
for(i=0; i<m_nodeCount; i++)
{
m_Nodes[i].Shutdown(OpenGL);
}
delete [] m_Nodes;
m_Nodes = 0;
}
return;
}
CalculateMeshDimensions is a new function that calculates the minimum and maximum height of the terrain.
We will use this for culling each frame.
We could determine the exact min/max height for each cell, but for a quad tree this single height should be sufficient as most culling occurs instead on depth and width.
void TerrainClass::CalculateMeshDimensions()
{
int i;
// Determine the minimum and maximum height of the terrain for the quad tree object.
m_minHeight = m_terrainModel[0].y;
m_maxHeight = m_terrainModel[0].y;
for(i=1; i<m_vertexCount; i++)
{
if(m_terrainModel[i].y < m_minHeight)
{
m_minHeight = m_terrainModel[i].y;
}
if(m_terrainModel[i].y > m_maxHeight)
{
m_maxHeight = m_terrainModel[i].y;
}
}
return;
}
The new GetNodesDrawn function returns the nodes culled and drawn by the quad tree for the current frame.
void TerrainClass::GetNodesDrawn(int& nodesDrawn, int& nodesCulled)
{
m_QuadTree->GetNodesDrawn(nodesDrawn, nodesCulled);
return;
}
Zoneclass.h
The ZoneClass now has a FrustumClass object as a member.
///////////////////////////////////////////////////////////////////////////////
// Filename: zoneclass.h
///////////////////////////////////////////////////////////////////////////////
#ifndef _ZONECLASS_H_
#define _ZONECLASS_H_
///////////////////////
// MY CLASS INCLUDES //
///////////////////////
#include "openglclass.h"
#include "inputclass.h"
#include "userinterfaceclass.h"
#include "cameraclass.h"
#include "positionclass.h"
#include "terrainclass.h"
////////////////////////////////////////////////////////////////////////////////
// Class name: ZoneClass
////////////////////////////////////////////////////////////////////////////////
class ZoneClass
{
public:
ZoneClass();
ZoneClass(const ZoneClass&);
~ZoneClass();
bool Initialize(OpenGLClass*);
void Shutdown(OpenGLClass*);
bool Frame(OpenGLClass*, ShaderManagerClass*, FontClass*, UserInterfaceClass*, InputClass*, float);
private:
bool Render(OpenGLClass*, ShaderManagerClass*, FontClass*, UserInterfaceClass*);
void HandleMovementInput(InputClass*, float);
private:
CameraClass* m_Camera;
PositionClass* m_Position;
TerrainClass* m_Terrain;
LightClass* m_Light;
FrustumClass* m_Frustum;
};
#endif
Zoneclass.cpp
////////////////////////////////////////////////////////////////////////////////
// Filename: zoneclass.cpp
////////////////////////////////////////////////////////////////////////////////
#include "zoneclass.h"
ZoneClass::ZoneClass()
{
m_Camera = 0;
m_Position = 0;
m_Terrain = 0;
m_Light = 0;
m_Frustum = 0;
}
ZoneClass::ZoneClass(const ZoneClass& other)
{
}
ZoneClass::~ZoneClass()
{
}
bool ZoneClass::Initialize(OpenGLClass* OpenGL)
{
char configFilename[256];
bool result;
// Create and initialize the camera object.
m_Camera = new CameraClass;
m_Camera->SetPosition(0.0f, 0.0f, -10.0f);
m_Camera->Render();
m_Camera->RenderBaseViewMatrix();
// Create and initialize the position object.
m_Position = new PositionClass;
m_Position->SetPosition(500.0f, 50.0f, -10.0f);
m_Position->SetRotation(0.0f, 0.0f, 0.0f);
// Create and initialize the terrain object.
m_Terrain = new TerrainClass;
strcpy(configFilename, "../Engine/data/setup.txt");
result = m_Terrain->Initialize(OpenGL, configFilename);
if(!result)
{
cout << "Error: Could not initialize the terrain object." << endl;
return false;
}
// Create and initialize the light object.
m_Light = new LightClass;
m_Light->SetDiffuseColor(1.0f, 1.0f, 1.0f, 1.0f);
m_Light->SetDirection(-0.5f, -1.0f, -0.5f);
The frustum object is created here.
// Create the frustum object.
m_Frustum = new FrustumClass;
return true;
}
void ZoneClass::Shutdown(OpenGLClass* OpenGL)
{
The frustum object is released here.
// Release the frustum object.
if(m_Frustum)
{
delete m_Frustum;
m_Frustum = 0;
}
// Release the light object.
if(m_Light)
{
delete m_Light;
m_Light = 0;
}
// Release the terrain object.
if(m_Terrain)
{
m_Terrain->Shutdown(OpenGL);
delete m_Terrain;
m_Terrain = 0;
}
// Release the position object.
if(m_Position)
{
delete m_Position;
m_Position = 0;
}
// Release the camera object.
if(m_Camera)
{
delete m_Camera;
m_Camera = 0;
}
return;
}
bool ZoneClass::Frame(OpenGLClass* OpenGL, ShaderManagerClass* ShaderManager, FontClass* Font, UserInterfaceClass* UserInterface, InputClass* Input, float frameTime)
{
float posX, posY, posZ, rotX, rotY, rotZ;
bool result;
// Do the frame input processing for the movement.
HandleMovementInput(Input, frameTime);
// Get the view point position/rotation.
m_Position->GetPosition(posX, posY, posZ);
m_Position->GetRotation(rotX, rotY, rotZ);
// Update the UI with the position.
UserInterface->UpdatePositonStrings(Font, posX, posY, posZ, rotX, rotY, rotZ);
// Render the zone.
result = Render(OpenGL, ShaderManager, Font, UserInterface);
if(!result)
{
return false;
}
return true;
}
bool ZoneClass::Render(OpenGLClass* OpenGL, ShaderManagerClass* ShaderManager, FontClass* Font, UserInterfaceClass* UserInterface)
{
float worldMatrix[16], viewMatrix[16], projectionMatrix[16], baseViewMatrix[16], orthoMatrix[16];
int nodesDrawn, nodesCulled;
bool result;
// Get the world, view, and ortho matrices from the opengl and camera objects.
OpenGL->GetWorldMatrix(worldMatrix);
m_Camera->GetViewMatrix(viewMatrix);
OpenGL->GetProjectionMatrix(projectionMatrix);
m_Camera->GetBaseViewMatrix(baseViewMatrix);
OpenGL->GetOrthoMatrix(orthoMatrix);
Each frame we construct the frustum based on the viewing and projection matrices.
// Construct the frustum.
m_Frustum->ConstructFrustum(OpenGL, viewMatrix, projectionMatrix);
// Clear the scene.
OpenGL->BeginScene(0.0f, 0.0f, 0.0f, 1.0f);
We send the frustum into the terrain rendering each frame so the quad tree can use it for culling non-viewable terrain nodes.
// Render the terrain using the terrain shader.
result = m_Terrain->Render(OpenGL, ShaderManager, m_Light, m_Frustum, worldMatrix, viewMatrix, projectionMatrix);
if(!result)
{
return false;
}
We now update the user interface with how many nodes were drawn and how many nodes we culled.
// Update with nodes drawn/culled.
m_Terrain->GetNodesDrawn(nodesDrawn, nodesCulled);
result = UserInterface->UpdateNodeStrings(Font, nodesDrawn, nodesCulled);
if(!result)
{
return false;
}
// Render the user interface.
result = UserInterface->Render(OpenGL, ShaderManager, Font, worldMatrix, baseViewMatrix, orthoMatrix);
if(!result)
{
return false;
}
// Present the rendered scene to the screen.
OpenGL->EndScene();
return true;
}
void ZoneClass::HandleMovementInput(InputClass* Input, float frameTime)
{
float posX, posY, posZ, rotX, rotY, rotZ;
bool keyDown;
// Set the frame time for calculating the updated position.
m_Position->SetFrameTime(frameTime);
// Check if the input keys have been pressed. If so, then update the position accordingly.
keyDown = Input->IsLeftPressed();
m_Position->TurnLeft(keyDown);
keyDown = Input->IsRightPressed();
m_Position->TurnRight(keyDown);
keyDown = Input->IsUpPressed();
m_Position->MoveForward(keyDown);
keyDown = Input->IsDownPressed();
m_Position->MoveBackward(keyDown);
keyDown = Input->IsAPressed();
m_Position->MoveUpward(keyDown);
keyDown = Input->IsZPressed();
m_Position->MoveDownward(keyDown);
keyDown = Input->IsPgUpPressed();
m_Position->LookUpward(keyDown);
keyDown = Input->IsPgDownPressed();
m_Position->LookDownward(keyDown);
keyDown = Input->IsQPressed();
m_Position->StrafeLeft(keyDown);
keyDown = Input->IsEPressed();
m_Position->StrafeRight(keyDown);
// Get the view point position/rotation.
m_Position->GetPosition(posX, posY, posZ);
m_Position->GetRotation(rotX, rotY, rotZ);
// Set the position of the camera.
m_Camera->SetPosition(posX, posY, posZ);
m_Camera->SetRotation(rotX, rotY, rotZ);
// Update the camera view matrix for rendering.
m_Camera->Render();
return;
}
Summary
Now only visible portions of the terrain are rendered and the rest is culled through use of the quad tree.
The count of triangles that are rendered is also now displayed.
To Do Exercises
1. Recompile the code and run the program. You should
2. Unlock the FPS in this tutorial and the previous tutorial. Move around the terrain in both and see how that affects the fps.
3. Add a user interface element for rendering how many polygons are being drawn each frame.
4. Research other methods of space partitioning such as oct trees, BSP trees, and portals.
Source Code
Source Code and Data Files: gl4terlinux09.tar.gz
