The quad tree technique that we covered in the previous tutorial also offers another advantage that I wanted to cover in a separate tutorial.
With the ability to quickly eliminate polygons through culling non-visible nodes we can also determine what node we are currently inside and cull everything else.
What that then allows us to do is a line-triangle intersection check with just a small number of triangles in the current node instead of the entire terrain.
That information can then be used to determine the height of the triangle that is currently beneath the camera.
Knowing the height allows us to place the camera just above the terrain by a fixed amount that is modified then as you move around the terrain.
This height determination technique can also be applied to other objects on the terrain so that everything is placed on top of the terrain according to the height of the triangles that the object is currently sitting on top of.
And with the quad tree being able to cull everything so we only do line-triangle intersections in the current node the processing is incredibly reduced in comparison with checking the entire terrain for an intersection.
We will start the tutorial by looking at the modifications to the TerrainNodeClass and QuadTreeClass from the previous tutorial.
Terrainnodeclass.h
////////////////////////////////////////////////////////////////////////////////
// Filename: terrainnodeclass.h
////////////////////////////////////////////////////////////////////////////////
#ifndef _TERRAINNODECLASS_H_
#define _TERRAINNODECLASS_H_
///////////////////////
// MY CLASS INCLUDES //
///////////////////////
#include "openglclass.h"
////////////////////////////////////////////////////////////////////////////////
// Class name: TerrainNodeClass
////////////////////////////////////////////////////////////////////////////////
class TerrainNodeClass
{
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 LineVertexType
{
float x, y, z;
float r, g, b;
};
We have a new struct for the format of the vertex position data that we need to maintain for the triangle height calculations.
struct VectorType
{
float x, y, z;
};
public:
TerrainNodeClass();
TerrainNodeClass(const TerrainNodeClass&);
~TerrainNodeClass();
void Initialize(OpenGLClass*, void*, int, int, int, int, int);
void Shutdown(OpenGLClass*);
void Render(OpenGLClass*);
void RenderLines(OpenGLClass*);
We also add a new function to return the height given a specific X,Z position on the terrain.
void GetHeightAtPosition(float, float, float&);
private:
void InitializeBuffers(OpenGLClass*, VertexType*, int, int, int, int, int);
void ShutdownBuffers(OpenGLClass*);
void RenderBuffers(OpenGLClass*);
void BuildLines(OpenGLClass*);
void ReleaseLines(OpenGLClass*);
The CheckHeightOfTriangle function will do a line-triangle intersection test to determine the height of the input point on the triangle.
It will also return false if the point we specified is not on the triangle at all.
bool CheckHeightOfTriangle(float, float, float&, float[3], float[3], float[3]);
private:
int m_vertexCount, m_indexCount;
unsigned int m_vertexArrayId, m_vertexBufferId, m_indexBufferId;
int m_indexCount2;
unsigned int m_vertexArrayId2, m_vertexBufferId2, m_indexBufferId2;
float m_maxX, m_maxY, m_maxZ, m_minX, m_minY, m_minZ;
The new m_vertexArray variable is a pointer to an array of all the vertices in this node with just their position information.
We will use this list of triangles for our height calculations.
VectorType* m_vertexArray;
};
#endif
Terrainnodeclass.cpp
///////////////////////////////////////////////////////////////////////////////
// Filename: terrainnodeclass.cpp
///////////////////////////////////////////////////////////////////////////////
#include "terrainnodeclass.h"
TerrainNodeClass::TerrainNodeClass()
{
m_vertexArray = 0;
}
TerrainNodeClass::TerrainNodeClass(const TerrainNodeClass& other)
{
}
TerrainNodeClass::~TerrainNodeClass()
{
}
void TerrainNodeClass::Initialize(OpenGLClass* OpenGL, void* terrainModelPtr, int terrainWidth, int nodeWidth, int nodeHeight, int nodeIndexX, int nodeIndexY)
{
VertexType* terrainModel;
// Coerce the pointer to the terrain model data into the vertex type of the model.
terrainModel = (VertexType*)terrainModelPtr;
// Copy just the node subset from the terrain model data.
InitializeBuffers(OpenGL, terrainModel, terrainWidth, nodeWidth, nodeHeight, nodeIndexX, nodeIndexY);
// Release the pointer to the terrain model.
terrainModel = 0;
// Build the debug lines for the node's bounding box.
BuildLines(OpenGL);
return;
}
void TerrainNodeClass::Shutdown(OpenGLClass* OpenGL)
{
The new vertex array for each node is released in this Shutdown function.
// Release the vertex array.
if(m_vertexArray)
{
delete [] m_vertexArray;
m_vertexArray = 0;
}
// Release the debug bounding box lines rendering buffers.
ReleaseLines(OpenGL);
// Release the buffers used to render the terrain node.
ShutdownBuffers(OpenGL);
return;
}
void TerrainNodeClass::Render(OpenGLClass* OpenGL)
{
// Render the terrain node's buffers.
RenderBuffers(OpenGL);
return;
}
void TerrainNodeClass::InitializeBuffers(OpenGLClass* OpenGL, VertexType* terrainModel, int terrainWidth, int nodeHeight, int nodeWidth, int nodeIndexX, int nodeIndexY)
{
VertexType* vertices;
unsigned int* indices;
int modelIndex, index, i, j;
// Calculate the number of vertices in this terrain node.
m_vertexCount = (nodeHeight - 1) * (nodeWidth - 1) * 6;
// Set the index count to the same as the vertex count.
m_indexCount = m_vertexCount;
// Create the vertex array.
vertices = new VertexType[m_vertexCount];
// Create the index array.
indices = new unsigned int[m_indexCount];
The new vertex array in each node is created here.
// Create the position only vertex array used for height based movement.
m_vertexArray = new VectorType[m_vertexCount];
// Setup the indexes into the terrain model data we are using to build this smaller node subset.
modelIndex = ((nodeIndexX * (nodeWidth - 1)) + (nodeIndexY * (nodeHeight - 1) * (terrainWidth - 1))) * 6;
// Load the vertex array and index array with data.
index = 0;
for(j=0; j<(nodeHeight - 1); j++)
{
for(i=0; i<((nodeWidth - 1) * 6); i++)
{
vertices[index].x = terrainModel[modelIndex].x;
vertices[index].y = terrainModel[modelIndex].y;
vertices[index].z = terrainModel[modelIndex].z;
vertices[index].tu = terrainModel[modelIndex].tu;
vertices[index].tv = terrainModel[modelIndex].tv;
vertices[index].nx = terrainModel[modelIndex].nx;
vertices[index].ny = terrainModel[modelIndex].ny;
vertices[index].nz = terrainModel[modelIndex].nz;
vertices[index].r = terrainModel[modelIndex].r;
vertices[index].g = terrainModel[modelIndex].g;
vertices[index].b = terrainModel[modelIndex].b;
vertices[index].tx = terrainModel[modelIndex].tx;
vertices[index].ty = terrainModel[modelIndex].ty;
vertices[index].tz = terrainModel[modelIndex].tz;
vertices[index].bx = terrainModel[modelIndex].bx;
vertices[index].by = terrainModel[modelIndex].by;
vertices[index].bz = terrainModel[modelIndex].bz;
The position of each vertex is stored in the vertex array.
This information will be used in the line-triangle intersection tests.
// Store a copy for the triangle height lookup function.
m_vertexArray[index].x = terrainModel[modelIndex].x;
m_vertexArray[index].y = terrainModel[modelIndex].y;
m_vertexArray[index].z = terrainModel[modelIndex].z;
indices[index] = index;
modelIndex++;
index++;
}
modelIndex += (terrainWidth * 6) - (nodeWidth * 6);
}
// Allocate an OpenGL vertex array object.
OpenGL->glGenVertexArrays(1, &m_vertexArrayId);
// Bind the vertex array object to store all the buffers and vertex attributes we create here.
OpenGL->glBindVertexArray(m_vertexArrayId);
// Generate an ID for the vertex buffer.
OpenGL->glGenBuffers(1, &m_vertexBufferId);
// Bind the vertex buffer and load the vertex data into the vertex buffer.
OpenGL->glBindBuffer(GL_ARRAY_BUFFER, m_vertexBufferId);
OpenGL->glBufferData(GL_ARRAY_BUFFER, m_vertexCount * sizeof(VertexType), vertices, GL_STATIC_DRAW);
// Enable the vertex array attributes.
OpenGL->glEnableVertexAttribArray(0); // Vertex position.
OpenGL->glEnableVertexAttribArray(1); // Texture coordinates.
OpenGL->glEnableVertexAttribArray(2); // Normals.
OpenGL->glEnableVertexAttribArray(3); // Tangent
OpenGL->glEnableVertexAttribArray(4); // Binormal
OpenGL->glEnableVertexAttribArray(5); // Color.
// Specify the location and format of the position portion of the vertex buffer.
OpenGL->glVertexAttribPointer(0, 3, GL_FLOAT, false, sizeof(VertexType), 0);
// Specify the location and format of the texture portion of the vertex buffer.
OpenGL->glVertexAttribPointer(1, 2, GL_FLOAT, false, sizeof(VertexType), (unsigned char*)NULL + (3 * sizeof(float)));
// Specify the location and format of the normal vector portion of the vertex buffer.
OpenGL->glVertexAttribPointer(2, 3, GL_FLOAT, false, sizeof(VertexType), (unsigned char*)NULL + (5 * sizeof(float)));
// Specify the location and format of the tangent vector portion of the vertex buffer.
OpenGL->glVertexAttribPointer(3, 3, GL_FLOAT, false, sizeof(VertexType), (unsigned char*)NULL + (8 * sizeof(float)));
// Specify the location and format of the binormal vector portion of the vertex buffer.
OpenGL->glVertexAttribPointer(4, 3, GL_FLOAT, false, sizeof(VertexType), (unsigned char*)NULL + (11 * sizeof(float)));
// Specify the location and format of the color vector portion of the vertex buffer.
OpenGL->glVertexAttribPointer(5, 3, GL_FLOAT, false, sizeof(VertexType), (unsigned char*)NULL + (14 * sizeof(float)));
// Generate an ID for the index buffer.
OpenGL->glGenBuffers(1, &m_indexBufferId);
// Bind the index buffer and load the index data into it.
OpenGL->glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, m_indexBufferId);
OpenGL->glBufferData(GL_ELEMENT_ARRAY_BUFFER, m_indexCount* sizeof(unsigned int), indices, GL_STATIC_DRAW);
// Calculate the node dimensions so we can build bounding box lines.
m_maxX = vertices[0].x;
m_minX = vertices[0].x;
m_maxY = vertices[0].y;
m_minY = vertices[0].y;
m_maxZ = vertices[0].z;
m_minZ = vertices[0].z;
for(i=1; i<m_vertexCount; i++)
{
if(vertices[i].x > m_maxX) { m_maxX = vertices[i].x; }
if(vertices[i].x < m_minX) { m_minX = vertices[i].x; }
if(vertices[i].y > m_maxY) { m_maxY = vertices[i].y; }
if(vertices[i].y < m_minY) { m_minY = vertices[i].y; }
if(vertices[i].z > m_maxZ) { m_maxZ = vertices[i].z; }
if(vertices[i].z < m_minZ) { m_minZ = vertices[i].z; }
}
// Now that the buffers have been loaded we can release the array data.
delete [] vertices;
vertices = 0;
delete [] indices;
indices = 0;
return;
}
void TerrainNodeClass::ShutdownBuffers(OpenGLClass* OpenGL)
{
// Release the vertex array object.
OpenGL->glBindVertexArray(0);
OpenGL->glDeleteVertexArrays(1, &m_vertexArrayId);
// Release the vertex buffer.
OpenGL->glBindBuffer(GL_ARRAY_BUFFER, 0);
OpenGL->glDeleteBuffers(1, &m_vertexBufferId);
// Release the index buffer.
OpenGL->glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
OpenGL->glDeleteBuffers(1, &m_indexBufferId);
return;
}
void TerrainNodeClass::RenderBuffers(OpenGLClass* OpenGL)
{
// Bind the vertex array object that stored all the information about the vertex and index buffers.
OpenGL->glBindVertexArray(m_vertexArrayId);
// Render the vertex buffer as triangles using the index buffer.
glDrawElements(GL_TRIANGLES, m_indexCount, GL_UNSIGNED_INT, 0);
return;
}
void TerrainNodeClass::BuildLines(OpenGLClass* OpenGL)
{
LineVertexType* vertices;
unsigned int* indices;
float red, green, blue;
int vertexCount2, index;
// Set the color of the bound box lines to yellow.
red = 1.0f;
green = 1.0f;
blue = 0.0f;
// Set the number of vertices for the 12 lines in the box.
vertexCount2 = 24;
// Set the index count to the same as the vertex count.
m_indexCount2 = vertexCount2;
// Create the vertex array.
vertices = new LineVertexType[vertexCount2];
// Create the index array.
indices = new unsigned int[m_indexCount2];
// Initialize the index into the vertices.
index = 0;
// Base 4 lines.
vertices[index].x = m_minX;
vertices[index].y = m_minY;
vertices[index].z = m_minZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_maxX;
vertices[index].y = m_minY;
vertices[index].z = m_minZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_minX;
vertices[index].y = m_minY;
vertices[index].z = m_maxZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_maxX;
vertices[index].y = m_minY;
vertices[index].z = m_maxZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_minX;
vertices[index].y = m_minY;
vertices[index].z = m_minZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_minX;
vertices[index].y = m_minY;
vertices[index].z = m_maxZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_maxX;
vertices[index].y = m_minY;
vertices[index].z = m_minZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_maxX;
vertices[index].y = m_minY;
vertices[index].z = m_maxZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
// Top 4 lines.
vertices[index].x = m_minX;
vertices[index].y = m_maxY;
vertices[index].z = m_minZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_maxX;
vertices[index].y = m_maxY;
vertices[index].z = m_minZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_minX;
vertices[index].y = m_maxY;
vertices[index].z = m_maxZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_maxX;
vertices[index].y = m_maxY;
vertices[index].z = m_maxZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_minX;
vertices[index].y = m_maxY;
vertices[index].z = m_minZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_minX;
vertices[index].y = m_maxY;
vertices[index].z = m_maxZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_maxX;
vertices[index].y = m_maxY;
vertices[index].z = m_minZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_maxX;
vertices[index].y = m_maxY;
vertices[index].z = m_maxZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
// Vertical 4 lines.
vertices[index].x = m_minX;
vertices[index].y = m_minY;
vertices[index].z = m_minZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_minX;
vertices[index].y = m_maxY;
vertices[index].z = m_minZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_maxX;
vertices[index].y = m_minY;
vertices[index].z = m_minZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_maxX;
vertices[index].y = m_maxY;
vertices[index].z = m_minZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_minX;
vertices[index].y = m_minY;
vertices[index].z = m_maxZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_minX;
vertices[index].y = m_maxY;
vertices[index].z = m_maxZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_maxX;
vertices[index].y = m_minY;
vertices[index].z = m_maxZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
vertices[index].x = m_maxX;
vertices[index].y = m_maxY;
vertices[index].z = m_maxZ;
vertices[index].r = red;
vertices[index].g = green;
vertices[index].b = blue;
indices[index] = index;
index++;
// Allocate an OpenGL vertex array object.
OpenGL->glGenVertexArrays(1, &m_vertexArrayId2);
// Bind the vertex array object to store all the buffers and vertex attributes we create here.
OpenGL->glBindVertexArray(m_vertexArrayId2);
// Generate an ID for the vertex buffer.
OpenGL->glGenBuffers(1, &m_vertexBufferId2);
// Bind the vertex buffer and load the vertex data into the vertex buffer.
OpenGL->glBindBuffer(GL_ARRAY_BUFFER, m_vertexBufferId2);
OpenGL->glBufferData(GL_ARRAY_BUFFER, vertexCount2 * sizeof(LineVertexType), vertices, GL_STATIC_DRAW);
// Enable the two vertex array attributes.
OpenGL->glEnableVertexAttribArray(0); // Vertex position.
OpenGL->glEnableVertexAttribArray(1); // Vertex color.
// Specify the location and format of the position portion of the vertex buffer.
OpenGL->glVertexAttribPointer(0, 3, GL_FLOAT, false, sizeof(LineVertexType), 0);
// Specify the location and format of the color portion of the vertex buffer.
OpenGL->glVertexAttribPointer(1, 3, GL_FLOAT, false, sizeof(LineVertexType), (unsigned char*)NULL + (3 * sizeof(float)));
// Generate an ID for the index buffer.
OpenGL->glGenBuffers(1, &m_indexBufferId2);
// Bind the index buffer and load the index data into it.
OpenGL->glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, m_indexBufferId2);
OpenGL->glBufferData(GL_ELEMENT_ARRAY_BUFFER, m_indexCount2 * sizeof(unsigned int), indices, GL_STATIC_DRAW);
// Now that the buffers have been loaded we can release the array data.
delete [] vertices;
vertices = 0;
delete [] indices;
indices = 0;
return;
}
void TerrainNodeClass::ReleaseLines(OpenGLClass* OpenGL)
{
// Release the vertex array object.
OpenGL->glBindVertexArray(0);
OpenGL->glDeleteVertexArrays(1, &m_vertexArrayId2);
// Release the vertex buffer.
OpenGL->glBindBuffer(GL_ARRAY_BUFFER, 0);
OpenGL->glDeleteBuffers(1, &m_vertexBufferId2);
// Release the index buffer.
OpenGL->glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
OpenGL->glDeleteBuffers(1, &m_indexBufferId2);
return;
}
void TerrainNodeClass::RenderLines(OpenGLClass* OpenGL)
{
// Bind the vertex array object that stored all the information about the vertex and index buffers.
OpenGL->glBindVertexArray(m_vertexArrayId2);
// Render the vertex buffer as lines using the index buffer.
glDrawElements(GL_LINES, m_indexCount2, GL_UNSIGNED_INT, 0);
return;
}
The GetHeightAtPosition function returns the height at a given X and Z position on the terrain.
It loops through all of the triangles in this node and calls FindNode which will perform a line-triangle intersection test at the position defined by positionX and positionZ.
void TerrainNodeClass::GetHeightAtPosition(float positionX, float positionZ, float& height)
{
float vertex1[3], vertex2[3], vertex3[3];
int i, index;
bool foundHeight;
// Check all the polygons in this node to find the height of which one the polygon we are looking for.
for(i=0; i<(m_vertexCount/3); i++)
{
index = i * 3;
vertex1[0] = m_vertexArray[index].x;
vertex1[1] = m_vertexArray[index].y;
vertex1[2] = m_vertexArray[index].z;
index++;
vertex2[0] = m_vertexArray[index].x;
vertex2[1] = m_vertexArray[index].y;
vertex2[2] = m_vertexArray[index].z;
index++;
vertex3[0] = m_vertexArray[index].x;
vertex3[1] = m_vertexArray[index].y;
vertex3[2] = m_vertexArray[index].z;
// Check to see if this is the polygon we are looking for.
foundHeight = CheckHeightOfTriangle(positionX, positionZ, height, vertex1, vertex2, vertex3);
// If this was the triangle then quit the function and the height will be returned to the calling function.
if(foundHeight)
{
return;
}
}
return;
}
The CheckHeightOfTriangle function is responsible for determining if a line intersects the given input triangle.
It takes the three points of the triangle and constructs three lines from those three points.
Then it tests to see if the position is on the inside of all three lines.
If it is inside all three lines then an intersection is found and the height is calculated and returned.
If the point is outside any of the three lines then false is returned as there is no intersection of the line with the triangle.
If you have ever fallen through the terrain in any software that has you running over terrain, it is usually to do with this type of function and floating point precision issues.
bool TerrainNodeClass::CheckHeightOfTriangle(float x, float z, float& height, float v0[3], float v1[3], float v2[3])
{
float startVector[3], directionVector[3], edge1[3], edge2[3], normal[3];
float Q[3], e1[3], e2[3], e3[3], edgeNormal[3], temp[3];
float magnitude, D, denominator, numerator, t, determinant;
// Starting position of the ray that is being cast.
startVector[0] = x;
startVector[1] = 0.0f;
startVector[2] = z;
// The direction the ray is being cast.
directionVector[0] = 0.0f;
directionVector[1] = -1.0f;
directionVector[2] = 0.0f;
// Calculate the two edges from the three points given.
edge1[0] = v1[0] - v0[0];
edge1[1] = v1[1] - v0[1];
edge1[2] = v1[2] - v0[2];
edge2[0] = v2[0] - v0[0];
edge2[1] = v2[1] - v0[1];
edge2[2] = v2[2] - v0[2];
// Calculate the normal of the triangle from the two edges.
normal[0] = (edge1[1] * edge2[2]) - (edge1[2] * edge2[1]);
normal[1] = (edge1[2] * edge2[0]) - (edge1[0] * edge2[2]);
normal[2] = (edge1[0] * edge2[1]) - (edge1[1] * edge2[0]);
magnitude = (float)sqrt((normal[0] * normal[0]) + (normal[1] * normal[1]) + (normal[2] * normal[2]));
normal[0] = normal[0] / magnitude;
normal[1] = normal[1] / magnitude;
normal[2] = normal[2] / magnitude;
// Find the distance from the origin to the plane.
D = ((-normal[0] * v0[0]) + (-normal[1] * v0[1]) + (-normal[2] * v0[2]));
// Get the denominator of the equation.
denominator = ((normal[0] * directionVector[0]) + (normal[1] * directionVector[1]) + (normal[2] * directionVector[2]));
// Make sure the result doesn't get too close to zero to prevent divide by zero.
if(fabs(denominator) < 0.0001f)
{
return false;
}
// Get the numerator of the equation.
numerator = -1.0f * (((normal[0] * startVector[0]) + (normal[1] * startVector[1]) + (normal[2] * startVector[2])) + D);
// Calculate where we intersect the triangle.
t = numerator / denominator;
// Find the intersection vector.
Q[0] = startVector[0] + (directionVector[0] * t);
Q[1] = startVector[1] + (directionVector[1] * t);
Q[2] = startVector[2] + (directionVector[2] * t);
// Find the three edges of the triangle.
e1[0] = v1[0] - v0[0];
e1[1] = v1[1] - v0[1];
e1[2] = v1[2] - v0[2];
e2[0] = v2[0] - v1[0];
e2[1] = v2[1] - v1[1];
e2[2] = v2[2] - v1[2];
e3[0] = v0[0] - v2[0];
e3[1] = v0[1] - v2[1];
e3[2] = v0[2] - v2[2];
// Calculate the normal for the first edge.
edgeNormal[0] = (e1[1] * normal[2]) - (e1[2] * normal[1]);
edgeNormal[1] = (e1[2] * normal[0]) - (e1[0] * normal[2]);
edgeNormal[2] = (e1[0] * normal[1]) - (e1[1] * normal[0]);
// Calculate the determinant to see if it is on the inside, outside, or directly on the edge.
temp[0] = Q[0] - v0[0];
temp[1] = Q[1] - v0[1];
temp[2] = Q[2] - v0[2];
determinant = ((edgeNormal[0] * temp[0]) + (edgeNormal[1] * temp[1]) + (edgeNormal[2] * temp[2]));
// Check if it is outside.
if(determinant > 0.001f)
{
return false;
}
// Calculate the normal for the second edge.
edgeNormal[0] = (e2[1] * normal[2]) - (e2[2] * normal[1]);
edgeNormal[1] = (e2[2] * normal[0]) - (e2[0] * normal[2]);
edgeNormal[2] = (e2[0] * normal[1]) - (e2[1] * normal[0]);
// Calculate the determinant to see if it is on the inside, outside, or directly on the edge.
temp[0] = Q[0] - v1[0];
temp[1] = Q[1] - v1[1];
temp[2] = Q[2] - v1[2];
determinant = ((edgeNormal[0] * temp[0]) + (edgeNormal[1] * temp[1]) + (edgeNormal[2] * temp[2]));
// Check if it is outside.
if(determinant > 0.001f)
{
return false;
}
// Calculate the normal for the third edge.
edgeNormal[0] = (e3[1] * normal[2]) - (e3[2] * normal[1]);
edgeNormal[1] = (e3[2] * normal[0]) - (e3[0] * normal[2]);
edgeNormal[2] = (e3[0] * normal[1]) - (e3[1] * normal[0]);
// Calculate the determinant to see if it is on the inside, outside, or directly on the edge.
temp[0] = Q[0] - v2[0];
temp[1] = Q[1] - v2[1];
temp[2] = Q[2] - v2[2];
determinant = ((edgeNormal[0] * temp[0]) + (edgeNormal[1] * temp[1]) + (edgeNormal[2] * temp[2]));
// Check if it is outside.
if(determinant > 0.001f)
{
return false;
}
// Now we have our height.
height = Q[1];
return true;
}
Quadtreeclass.h
We have two new functions in QuadTreeClass that will assist with finding which node we need to do our triangle height calculation in.
////////////////////////////////////////////////////////////////////////////////
// Filename: quadtreeclass.h
////////////////////////////////////////////////////////////////////////////////
#ifndef _QUADTREECLASS_H_
#define _QUADTREECLASS_H_
///////////////////////
// MY CLASS INCLUDES //
///////////////////////
#include "frustumclass.h"
////////////////////////////////////////////////////////////////////////////////
// Class name: QuadTreeClass
////////////////////////////////////////////////////////////////////////////////
class QuadTreeClass
{
private:
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&);
bool GetHeightAtPosition(float, float, int&);
private:
void CreateTreeNode(NodeType*, float, float, float);
void ReleaseNode(NodeType*);
void RenderNode(NodeType*, FrustumClass*, float, float);
void FindNode(NodeType*, float, float, int&);
private:
NodeType* m_parentNode;
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"
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)
{
// 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;
// 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);
// Create the render list after the nodes have been created and the node count is populated.
m_renderList = new int[m_nodeCount];
return;
}
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;
}
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;
}
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;
}
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;
}
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;
}
void QuadTreeClass::GetNodesDrawn(int& nodesDrawn, int& nodesCulled)
{
nodesDrawn = m_visibleNodes;
nodesCulled = m_nodeCount - m_visibleNodes;
return;
}
void QuadTreeClass::GetRenderList(int* outputRenderList, int& count)
{
count = m_visibleNodes;
memcpy(outputRenderList, m_renderList, sizeof(int) * count);
return;
}
This is the first new function which gets the height at a given X and Z position on the terrain.
It first makes sure the position is actually on the terrain mesh before proceeding.
After that it calls FindNode which will return the ID of the node which contains the triangle at the given position.
bool QuadTreeClass::GetHeightAtPosition(float positionX, float positionZ, int& nodeID)
{
float meshMinX, meshMaxX, meshMinZ, meshMaxZ;
meshMinX = m_parentNode->positionX - (m_parentNode->width / 2.0f);
meshMaxX = m_parentNode->positionX + (m_parentNode->width / 2.0f);
meshMinZ = m_parentNode->positionZ - (m_parentNode->width / 2.0f);
meshMaxZ = m_parentNode->positionZ + (m_parentNode->width / 2.0f);
// Make sure the coordinates are actually over a polygon.
if((positionX < meshMinX) || (positionX > meshMaxX) || (positionZ < meshMinZ) || (positionZ > meshMaxZ))
{
return false;
}
// Find the node which contains the polygon for this position.
FindNode(m_parentNode, positionX, positionZ, nodeID);
return true;
}
FindNode is the next new function which recursively finds the node that the input position is located inside of.
It then returns the nodeID of the node that contains the triangle.
void QuadTreeClass::FindNode(NodeType* node, float x, float z, int& nodeID)
{
float xMin, xMax, zMin, zMax;
int count, i;
// Calculate the dimensions of this node.
xMin = node->positionX - (node->width / 2.0f);
xMax = node->positionX + (node->width / 2.0f);
zMin = node->positionZ - (node->width / 2.0f);
zMax = node->positionZ + (node->width / 2.0f);
// See if the x and z coordinate are in this node, if not then stop traversing this part of the tree.
if((x < xMin) || (x > xMax) || (z < zMin) || (z > zMax))
{
return;
}
// If the coordinates are in this node then check first to see if children nodes exist.
count = 0;
for(i=0; i<4; i++)
{
if(node->nodes[i] != 0)
{
count++;
FindNode(node->nodes[i], x, z, nodeID);
}
}
// If there were children nodes then return since the polygon will be in one of the children.
if(count > 0)
{
return;
}
// If there were no children then the polygon must be in this node. Check all the polygons in this node to find
// the height of which one the polygon we are looking for.
nodeID = node->nodeID;
return;
}
Terrainclass.h
////////////////////////////////////////////////////////////////////////////////
// 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&);
We have added one new function to the TerrainClass called GetHeightAtPosition.
The ZoneClass will call this function and TerainClass will query the quad tree for the information.
bool GetHeightAtPosition(float, float, float&);
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
There is only one new function in TerrainClass so we will just cover that.
The new GetHeightAtPosition function first queries the quad tree to get the node ID which contains the provided input position.
Once it has the node ID it then queries that specific node for the height of the triangle.
bool TerrainClass::GetHeightAtPosition(float positionX, float positionZ, float& height)
{
int nodeID;
bool result;
result = m_QuadTree->GetHeightAtPosition(positionX, positionZ, nodeID);
if(!result)
{
return false;
}
m_Nodes[nodeID].GetHeightAtPosition(positionX, positionZ, height);
return true;
}
Zoneclass.cpp
There are no changes to the header of ZoneClass, so we will just cover the source file changes.
////////////////////////////////////////////////////////////////////////////////
// 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);
// Create the frustum object.
m_Frustum = new FrustumClass;
return true;
}
void ZoneClass::Shutdown(OpenGLClass* OpenGL)
{
// 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, height;
bool result, foundHeight, heightLocked;
We have a new boolean variable to indicate whether we want to lock our height to the terrain or not.
// Set whether we lock to the terrain height or not.
heightLocked = true;
// 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);
Each frame we will query the terrain for the height of the triangle underneath our current position.
If it is found then we will lock our height to it and add 2.0 to move slightly just above.
// Get the height of the triangle that is directly underneath the given camera position.
foundHeight = m_Terrain->GetHeightAtPosition(posX, posZ, height);
if(foundHeight)
{
// If there was a triangle under the camera then position the camera just above it by two units.
if(heightLocked)
{
posY = height + 2.0f;
}
}
Note we had to move setting the camera position out of the HandleMovementInput function and place it here so we could update it with our height locked position each frame.
// Set the position of the camera and update the camera view matrix for rendering.
m_Camera->SetPosition(posX, posY, posZ);
m_Camera->SetRotation(rotX, rotY, rotZ);
m_Camera->Render();
// 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);
// Construct the frustum.
m_Frustum->ConstructFrustum(OpenGL, viewMatrix, projectionMatrix);
// Clear the scene.
OpenGL->BeginScene(0.0f, 0.0f, 0.0f, 1.0f);
// Render the terrain using the terrain shader.
result = m_Terrain->Render(OpenGL, ShaderManager, m_Light, m_Frustum, worldMatrix, viewMatrix, projectionMatrix);
if(!result)
{
return false;
}
// 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)
{
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);
Note that setting the camera position has been moved out of here and placed in the Frame function instead to support height locking.
return;
}
Summary
With the ability to determine the exact height of any point of the terrain we can now use that to position the camera always just above the terrain.
To Do Exercises
1. Recompile the code and run the program. Move around the terrain and you will find your height automatically adjusts to the changing height. Press escape to quit.
2. Change the amount of fixed height that the camera is over the terrain.
3. Place an object that randomly moves around the terrain adjusting its height based on information from the quad tree.
Source Code
Source Code and Data Files: gl4terlinux10.tar.gz
