I needed a bit of a diversion from the planet rendering itself, into something that would give some purpose behind it. Why is the planet there? Well, what better use is there for a planet than driving a tank on it?

The tank model from the XNA Heightmap Collision with Normals sample is the perfect tank to drive on a lonely, empty, and possibly dangerous new world. I grabbed the model and texture resources, and the Tank class, added them to my project, and added some “spawn tank” functionality to get it drawing, resulting in a beautiful flying tank that seemed to defy gravity. Since nobody should be able to defy gravity, it was time to bring the tank down to earth.

The basic concept is to find the triangle underneath the tank and the exact position within that triangle. This will give us the exact height at that location, and the normal so we can orient the tank correctly. When using a single height map that’s not too bad, but when there are potentially hundreds of height maps, organized in a quad tree, there’s some more work involved.

The first thing I do is find the quad tree node that’s under the tank. There isn’t a regular grid like with a height map, so I had to come up with a different way to find it. The first thing that came to mind was to do traverse the quadtree with a simple point-in-bounding-box check, but that would only work if the tank is already very close to the ground. I want to be able to have a position 6,000 km above the surface and be able to find the proper node.

The next idea was to create a view frustum from the planet center looking outward at each node. To create the frustum I’d have to calculate the proper field of view so the frustum planes would go through the edges of the quad tree nodes. I actually tried this method but had trouble getting the field of view calculations to work so things were aligned properly. I still think this method would work if I spent enough time on it, but there’s actually quite a bit of code that has to be executed for each check, so it’s not the best method anyway.

The final idea, and the one I have working, is to do a simple ray-bounding-box intersection test. I was initially going to create the ray at the planet center, pointing out towards the position we’re looking at, but that would very likely run into floating point precision issues, so instead the ray starts 1 km below the planet surface, which gives plenty of precision to work with.

So, I traverse the quad tree, doing the ray-bounding-box intersection test. If I find a hit, I perform the check against the children, and so on, until I reach a leaf node. Once I have a leaf node I need to find the triangle within the leaf, using ray-triangle intersection tests.  Now, I understand the concept, but coding one with my current knowledge is beyond me, so I downloaded the XNA triangle picking example, which has a nice ray-triangle intersection method.

Now, the original ray-bounding-box intersection can give false hits since we’re working with a spherical surface because the bounding boxes can overlap a bit. So the ray-triangle intersection tests might fail to find a triangle. If that happens I just continue on traversing the tree with the bounding box checks until I eventually find the proper node, as well as the proper triangle. This works, 99% of the time. There is still a bug where the code fails to find a node at all. It’s very rare, but something I’ll need to figure out someday.

So, in order to get the proper height value I need to get the exact point within the triangle. When using a height map it’s common to use bi-linear interpolation to find this height, and I spent some time trying to get that to work with partial success. I finally stepped back and realized that the ray-triangle intersect was returning the distance along the ray of the intersect, so it was a simple matter of multiplying the normalized ray-direction by the intersect distance to give me the exact position I needed. Treating that position as a vector from the planet center,  the magnitude is the height value that’s needed for the tank position.

That leaves the normal so the tank can be oriented properly. When using a height map the normal is also found using bi-linear interpolation. This presented a problem since I couldn’t ever get that to work completely for the height. Instead of mucking with it too much I chose to average the normals of the triangle, which seems to fit well within my “good enough” expectations at this time.

So, my planet has gained a purpose, and in so doing I now have some code that’s going to be very useful for things like placing trees and walking and crashing and shooting. I’ll try to put up a video in the next day or so.