*null

Terrain following is a pretty important part of almost any 3D application. It’s the process of figuring out what the geometry of the ground looks like, and how to go about interacting with it. For most applications, this can be a pretty search intensive process, but for a psuedo-randomly generated terrain, it’s just a brief regeneration of the ground.

The standard process of finding the triangle you’re resting on starts with narrowing down the number of triangles you might want to even think about checking with.  I’ll assume that a solid BVH (Bounding Volume Hierarchy) is in place, by which we can do Line to AABB (Axis-Aligned Bounding Box) collision.  This is a pretty trivial collision check, and will most likely be done less than 30 times to find the AABB(s) containing our line.

Next we have to find the triangle we’re colliding with inside of this AABB.  Let’s say we have a threshold of 10 triangles; this means 10 line to triangle checks.  This check is a bit uglier, and the early outs are probably going to fail for this sort of case.  The math is:

Given the triangle vertices,
and the line
we can calculate the triangle normal:
and a point on the triangle’s plane:

With the triangle’s plane defined, we can check if our line passes through it. If either of these checks passes, there is no collision:

Now that we know the line intersects the plane, we find the point of collision: 

Finally, we need to see if is actually contained in the triangle by performing a series of half space tests. If any pass, we do not collide with this triangle:

If we fail all of these tests, then collides with our ground, and we can move to the next piece of our object.  If not, we have 9+ more times to go through this formula to find out which triangle it actually collides with.  That’s pretty ugly, but it’s how we’re able to figure out where our tires, feet, treads, etc should be resting on the ground.  It’s also how you do triangle picking, allowing bullets to collide with walls, or for you to click where you want your troops to move to, so it’s not an uncommon forumla.

This formula really starts to expensive as you begin to realize that it’s not a game with just one player.  In fact, all the other players (objects, AI, or whatever else) have to go through this same formula… and this is the optimized version.

So what benefit does procedural terrain have over a normal situation?  Well, since a real-time generation of terrain has to be fast, generating a single triangle is going to be relatively cheap.  This means that re-generating that single triangle over the object’s position is faster than the 30 AABB to line checks we did before.  It’s also going to allow us to cut off those final three checks to see if is inside our triangle or not, and because we have only one triangle we only have to do the formula once.  In fact, we could probably even cut off the first two checks, being as we’ll already know our min and max height of the terrain and would be able to build our line with this in mind, meaning we won’t need to calculate anymore either.  This is looking much faster already.

Although, in practice, I was actually forced to find the quad underneath each tire, and do a simplified half-space check to figure out which of the two triangles a given tire was in, the principle is the same.  The end result is a very fast terrain following formula, and, in my case, a buggy to drive around the eternal space that is my terrain generator.

One final note, my OpenGL is still not ATI friendly it seems, so no new release yet.  Sorry.

Zilchius Programming Math, Picking, Procedural Generation, Terrain, Terrain Following, Vector Math