StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is an inevitable problem when shooting a single ray against some geometry with edges and vertices. It's amazing how physical simulations seem to seek out the smallest of numerical inaccuracies!</p> <p>Some of the explanations and solutions proposed by other respondents will not work. In particular:</p> <ul> <li><p>Numerical inaccuracy really can cause a ray to "fall through the gap". The problem is that we intersect the ray with the plane ABC (getting the point P, say) before testing against line BC. Then we intersect the ray with plane BCD (getting the point Q, say) before testing against line BC. P and Q are both represented by the closest floating-point approximation; there's no reason to expect that these exactly lie on the planes that they are supposed to lie on, and so every possibility that you can have both P to the left of BC and Q to the right of BC.</p></li> <li><p>Using less-than-or-equal test won't help; it's inaccuracy in the intersection of the ray and the plane that's the trouble. </p></li> <li><p>Square roots are not the issue; you can do all of the necessary computations using dot products and floating-point division.</p></li> </ul> <p>Here are some genuine solutions:</p> <ul> <li><p>For convex meshes, you can just test against all the planes and ignore the edges and vertices, as you say (thus avoiding the issue entirely).</p></li> <li><p>Don't intersect the ray with each triangle in turn. Instead, use the <a href="http://realtimecollisiondetection.net/blog/?p=69" rel="noreferrer">scalar triple product</a>. (This method makes the exact same sequence of computations for the ray and the edge BC when considering each triangle, ensuring that any numerical inaccuracy is at least consistent between the two triangles.)</p></li> <li><p>For non-convex meshes, give the edges and vertices some width. That is, place a small sphere at each vertex in the mesh, and place a thin cylinder along each edge of the mesh. Intersect the ray with these spheres and cylinders as well as with the triangles. These additional geometric figures stop the ray passing through edges and vertices of the mesh.</p></li> </ul> <p>Let me strongly recommend the book <a href="http://realtimecollisiondetection.net/" rel="noreferrer">Real-Time Collision Detection</a> by Christer Ericson. There's a discussion of this exact problem on pages 446–448, and an explanation of the scalar triple product approach to intersecting a ray with a triangle on pages 184–188.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload