On Thu, 4 Mar 1999 16:59:57 +0100, Daniele Varrazzo <pir### [at] officineit> wrote:
>Hi, everybody.
>A triangle hasn't a well defined solid inside and an outside, that's
>obvious. And so even a triangle mesh.
>But if I know that my mesh represents a closed surface (or a set of closed
>surfaces), there is an easy way to know if a point is inside or outside.
>It is the Jordan's closed curve theorem, the same used with polygons:

There are some gotchas with that algorithm.  If you intersect an edge or a 
vertex, you have to do some extra work to determine whether the intersection 
should be counted or not.  Nathan Kopp has added this sort of thing to his 
UV-mapping patch, available at http://nathan.kopp.com . It's a bit more complex 
than just a "closed" keyword, though, IIRC.  

There's another way, though: 

First, when someone says a triangle mesh is closed, it's relatively easy to 
verify that that's likely the case: simply verify that each edge has exactly 
two adjacent faces.  This won't catch certain degenerate self-intersecting 
surfaces, but it'll be a good start.  From there, it's a (relatively) simple 
matter to reorient all of the triangles so that the insideness test doesn't 
require intersection counting, but only requires finding the closest triangle 
along a random ray and checking the orientation of that triangle relative to 
the ray.  Meshes already have an internal structure that optimizes this search.

A side note, and hopefully Nathan will see this too and make sure he's dealing 
with it correctly: CSG requires more than just an insideness test.  It also 
requires that the All_Intersections method really return all intersections, 
because if the closest one fails it wants to find the next-closest.  Internally 
bounded meshes DO NOT do this by default, because of the optimization I noted
above.

Post a reply to this message