Hey all,

So for my terrain system I have a quadtree with leaf node block sizes of 33 X 33. In order to have terrain collision I first find the block of terrain in the quadtree that the player is standing on. Once I have this 33 X 33 block I cast a ray downward from the players position and perform a ray/triangle intersection test to find the triangle the player is standing on, as well as the distance from that triangle.

It all works properly but for a block size of 33 X 33 I have 1089 cells, with 2 triangles per cell, so each game loop I'm doing 2178 ray/triangle tests in the worst case (it can early out once it finds an intersection).

Even with this small block size it is destroying my fps when I move (the test is only performed on movement). I go from 60fps to 25-30fps on movement.

I thought this was a pretty standard method for staying above the terrain. Am I missing some type of optimization that can make this faster? I could of course use smaller block sizes, but that increases the depth of the quadtree, increases the number of draw calls, increases the number of shared vertices (as edge vertices are shared between blocks) and increases the number of frustum/box tests for terrain node culling.

Any tips or resources on how to speed this up is appreciated.

Edit:
When looking more closely at the number of intersection tests done, if I am standing at the top left corner of the block I'm only performing a few tests, but when I am standing on the bottom right corner I am performed the maximum number of tests (~2000). This is due to the fact that my loop starts at the top left triangle and ends at the bottom right triangle. Since I have a uniform terrain there must be some clever way of taking advantage of the spatial locality of the player inside of the block to only have to perform a small number of intersection tests, right?

Thanks,
Dark

Why keep searching until you hit terrain? You only need to keep searching until you are past the bottom of your player's feet.

Also, does your quad tree actually store all leaf nodes, even if they are empty? You describe them as being 33x33, but you'll find you can inject nitro into your graph by only dividing the tree up as far as you need to. One of the real strengths of quad trees is that the moment you have a cell with nothing in it, you stop dividing it up. This drastically reduces the number of nodes you need to traverse, as most of your world will be empty space. For purposes of collision you can consider areas beneath terrain and inside of world objects as "empty space" as well, since you only care about intersections with the surface of collision objects and terrain.

The wikipedia article has a good image to describe what I'm talking about. http://en.wikipedia.org/wiki/Quadtree. See all that empty space? They have an incredibly small cell size where there are objects, and yet throwing a ray straight from top to bottom only results in a few dozen tests at worst.

Thanks for the reply Kuro. I think I should explain better. The quadtree is simply for terrain only, not the entire world. The terrain is 257X257 and gets split 3 times. Thus each of my leaf nodes contains a 33 X 33 block with no children and there is no empty space and no empty leaf nodes.

I got the idea of casting a downward ray from a terrain tutorial, but the more I think about it, this design my be flawed (at least for uniform spaced terrain).

I think with some clever mathmatics it is possible to get the exact cell of the terrain that the player is standing in. Then one would only have to check two triangles instead of an entire block.

If the terrain is uniform then I assume it is based of a height field which already is a grid... selecting the players position from a grid is trivial and about as fast as it gets. Doing this via a quadtree seems to overcomplicate a trivial problem.

Agreed. The tutorial I was following has lead me down a bad design path, but I am fixing it. I'm currently just working out the math to get the height from the grid, I won't even need to do a single ray/triangle test and it will be so fast that its essentially free.

I believe the quadtree is still useful for view frustum culling and as a part of GeoMipMap LoD, which is the next thing I'm implementing once I can walk across the terrain. If I only have a copy of the terrain vertices in the leaf nodes of the quadtree then I still have to parse the quadtree which is unfortunate. The other option would be to have a duplicate array of vertex (or just the height) data for the entire terrain and then to access that directly for the height calculations.

I found a solution for this on a forum. The code is here

float GetTerrainHeight( float fTerX, float fTerY )
{
// we first get the height of 4 points of the quad underneath the point
int x = (int)fTerX;
int y = (int)fTerY;
float fTriY0 = (heightData[x , y]);
float fTriY1 = (heightData[x + 1, y]);
float fTriY2 = (heightData[x , y + 1]);
float fTriY3 = (heightData[x + 1 , y + 1]);
// find which of the 2 triangles the point is over (depends on how you render)
// then take the height at a triangle point
// and adjust by the slope down right-angle edges * distance along that edge.

float fHeight;
float fSqX = fTerX - x;
float fSqY = fTerY - y;
if ( (fSqX + fSqY) < 1 )
{
fHeight = fTriY0;
fHeight += ( fTriY1 - fTriY0 ) * fSqX;
fHeight += ( fTriY2 - fTriY0 ) * fSqY;
} else {
fHeight = fTriY3;
fHeight += ( fTriY1 - fTriY3 ) * ( 1.0f - fSqY);
fHeight += ( fTriY2 - fTriY3 ) * ( 1.0f - fSqX);
}
return fHeight;
}


My javascript implementation is here (and my up axis is Y not Z)


this.getHeightAtPosition = function(x, z)
{
// we first get the height of the 4 vertices of the cell underneath the point
var unitX = Math.floor(x*mSpacingInv);
var unitZ = Math.floor(z*mSpacingInv);
var vertHeight0 = vertices[(unitX + (unitZ*mSize))*3 + 1];
var vertHeight1 = vertices[((unitX+1) + (unitZ*mSize))*3 + 1];
var vertHeight2 = vertices[(unitX + ((unitZ+1)*mSize))*3 + 1];
var vertHeight3 = vertices[((unitX+1) + ((unitZ+1)*mSize))*3 + 1];


var height;
var SqX = x - Math.floor(x);
var SqZ = z - Math.floor(z);

if ((SqX + SqZ) < 1)
{
height = vertHeight0;
height += (vertHeight1 - vertHeight0) * SqX;
height += (vertHeight2 - vertHeight0) * SqZ;
}
else
{
height = vertHeight3;
height += (vertHeight1 - vertHeight3) * ( 1.0 - SqZ);
height += (vertHeight2 - vertHeight3) * ( 1.0 - SqX);
}
return height;
}


However I am getting a jumping effect as I move across the terrain. The first section is just getting the height of the 4 vertices for the current cell. The second part looks like if sqX + sqZ <1 then we are in the upper left triangle and if its between 1 and 2 its in the bottom right triangle and then we get two edges and interpolate.

Figured it out. The following two values should be changed to

var SqX = (x*mSpacingInv) - Math.floor(x*mSpacingInv)

and the equivalent for SqZ.

This is for a terrain that doesnt have unit length spacing.