Recently in a Shockwave3D project, I had some problems with the modelsUnderRay command. More precisely, modelsUnderRay seemed to have some problems of its own. Occasionally it just didn't give the correct result, it would miss a model somehow. In the particular application I was building (a landscape that let the user's drive a car around on the surface), this was dramatic because the when modelsUnderRay failed, the car fell through the world. At first I started to develop little stop-gap bits of code that ensured that the built-in functions would work. And then it occurred to me, why not just write my own?

So in my application, I was firing a ray 'down' from the position of the car, and intersecting the land, and then moving the car 'up' so that it would ride on the surface. I was also orienting the car to the normal of the triangle that it was on top of. This is shown in Figure 1.

So as you can see from the diagram, missing the landscape would have rather drastic consequences. Additionally, in doing it myself, I was able to get not only the normal from the original triangle, but the blended normal that weights the three disparate normal at the vertices of the triangle, which allows for a much smoother motion across the surface. The desired "smooth normal" is shown in Figure 2.

So I needed a way to fire a ray at the landscape, see where it hit, and get the resulting normal vector. The code for my collision detection routine is generalized to the code in Listing 1 (which unlike my terrain example uses ALL of the objects in the world, in the same way that modelsUnderRay does). Note also that to debug this I used my 'Visual Debug Lines' that I presented in a previous MXDJ column (http://mxdj.sys-con.com/read/47857.htm).

The true "workhorse" of this routine is the ghTriangleRayCollision routine, that performs the magic of ray/triangle collision detection. This routine is based on an algorithm that I found at the SoftSurfer graphics site [see References, item1#], and that has been published several times in various places. A competing algorithm that could also be used would be the Akenine-Moller algorithm, which is presented in [see References, item #2]. The code for ghTriangleRayCollision is presented in Listing 2.

Finally, I wanted a way to average the normals of the triangle I hit, and get the normal of the exact point, or texel, within the triangle, weighted from the three triangle vertices. So I modified the code in Listing 1 to return not only the texture coordinates, but the three normals for the triangle that I hit. This is simply a matter of reading them out of the mesh in the same way the texture coordinates are read. Once I had the normals, then I knew the following information: the position of the points of the triangle (aTriangleHit in the returned array), the point of collision (vHitPosition in the returned array), and the normals at the vertices of the triangle (aTriangleNormals). With these three pieces of information I used a technique called Barycentric Coordinates to average the normals across the triangle. The Barycentric Coordinates are computed and returned as a vector of weights in the ghGetBarycentricCoords3D function in Code Listing 3.

The final application of the weights to the original vectors occurs in the ghGetTexelValues handler, that takes an array of values (the normals) and a vector that represents the BaryCentric weights of the point. The code for GetTexelValues is shown in Listing 4.

Using these methods, I rolled my own collision detection that was far more accurate than the modelsUnderRay command that exists in the 3D Xtra. It will detect backfacing collisions, will not return a collision when the ray intersects a model's bounding sphere but not the model, and is generally more precise around the edges of individual faces. Additionally, by adding some averaging methods, I was able to more smoothly interpolate across the surface of the triangle, rather than have sharp transitions between the normals of two adjoining triangles. This made for a much smoother terrain-following algorithm, without the overhead of constantly interpolating between the last and current face. Hopefully you too will find these functions a helpful addition to your toolbox in developing your own 3D worlds.

References: