Problems caused by floating point imprecision.

[lgc_ustc]

Greetings,

I am developing an outdoor terrain project, in which the terrain is constructed using a height map. Now I am using some ray-triangle algorithm to determine whether the bullets hit the terrain or not. The algorithm works fine, however, since the floating point numbers have finite precision, so when the bullet hits the border of two triangles, the bullet leaks out of the terrain since it does not intersect either triangle!!! Using double type numbers instead might improve this, but I guess that can not solve the problem from the root.

This is a case which I realized before I implemented the algorithm, and I also propose a solution: for each triangle to be tested against the ray for intersection, we "expand" it a liitle bit, i.e., we test another similar-shaped but a little bigger triangle instead. Thus there won't be any gaps in the terrain since all the triangles overlap! However, I do not know how to get such a substitution triangle yet. Can anybody tell me how? Or any better solutions?

Thanks

[plasmonster]

Try biasing the point distance to plane in your intersection calculations with a small floating point number. 1.0/32.0 works great for single precision:

#define FLOAT_BIAS (1.0/32.0)
int linePlane( Vector start, Vector end, Plane plane, Vector& hit, float& frac ){
	hit  = end;
	frac = 1;
 
	float dist0 = plane.distance( start );
	float dist1 = plane.distance( end );
	if( dist0 >= 0.0 && dist1 >= 0.0 )	return 0; // seg in front of plane
	if( dist0 < 0.0  &amp;&amp; dist1 < 0.0  )	return 1; // seg in back of plane
 
	int side = dist0 < 0;
	if( side ) frac	= (dist0 + FLOAT_BIAS) / (dist0 - dist1);
	else	   frac	= (dist0 - FLOAT_BIAS) / (dist0 - dist1);
	frac = clamp( frac, 0, 1 );
	hit  = start + (end - start) * frac;
 
	return 2; // seg was split
}

[lgc_ustc]

Thanks again, Portal I'll try this out soon.

[lgc_ustc]

Well, I think I misunderstood your suggestion, Portal . My problem is caused by the imprecise determination of which triangle the ray will intersect when it passes through the border of the two triangle. If it determines that the ray does not intersect with either triangle, then the ray will passes through the terrain.

I think I know what your solution means, but I do not think that the problem is caused by the very short ray you talked about, because all the problems happened when the ray was trying to travel betweeen the borders of triangles.

Thanks for your reply and any further suggestions very welcome!

[plasmonster]

lgc_ustc,

it might help to better understand how you're doing the tracing, and what kind of tracing you're doing, e.g., line tracing, collision detection, etc.

[SmutMonkey]

If you have the original heightmap data handy at runtime, then you may be better off querying that directly, rather than doing triangle intersection tests. You might get slightly differing results from your mesh (depending on whether you use or take into account turned edges), but you'll never get the problem of the ray leaking out of the world.

[lgc_ustc]

Well, I believe that querying the height map can solve this problem. Thanks for your suggestion. But I am still wondering how the problem is solved when we are dealing with indoor scenes organized in BSPs like Quake?

[plasmonster]

If you have a bsp tree, then you're almost home.
For collision detection, Quake uses beveled expanded convex brush hulls, which sounds complicated, but is actually one of the easiest and most intuitive methods around. The idea is this: First, I assume your world is composed of convex brushes (boxes, cylinders, spheres - any object such that every poly has every other poly behind it). When you create your bsp tree, you want to remember which brushes touch the empty leaves of your tree - just keep a list in your node structure:

struct bsp_node {
...
brush* brushList; // only for empty leaves
...
};

Now, when you perform a line trace, make a bounding box for the line, then expand the bounds by the size of you trace object. Take this expanded bounding box and filter it down the tree: if it's in front of a node, then go down the front side; if it's in back, then go down the back side; if it's split, then go down the front and back sides. If you reach an empty leaf, you now have a list of convex brushes to test the line against.

Tracing a line through a convex brush is quite simple, due to the nice properties of convex brushes. I won't go into the details here, but I would be happy to if you need them. Having done the brush trace, keep the intersection (if any) closest to the start point of the line. Once you've traversed the entire tree you should have the hit point.

Beveling a brush requires adding planes at the sharp edges and corners of the brush so that when you expand it, you won't get extreme wedgies in your world. Imagine expanding the planes of a tall pointy cone; the difference between the expanded planes and the original planes becomes excessive. By capping the cone with a bevel plane on top you can prevent this from happening.

Expansion simply means pushing the plane out along the normal in some fashion. There are several ways to do this, depending on the geometry of the moving object ( i.e., sphere, box, or cylinder ).

A nice thing about this method is that it's trivial to get surface information, such as textures and normals. Additionally, this method handles moving and rotating brushes.

Another method involves shifting the node planes, and requires beveling of the tree itself. Needless to say, this method is much more complicated, but worthy of mention.

edit:
worded some stuff differently