On Fri, 12 Mar 1999 21:54:32 +0100, ingo <ing### [at] ingodemonnl> wrote:
>I can imagine using planes instead of prisms to represent the triangles (in
>a closed mesh). First use Ron's method to check if the mesh is closed. Then
>for every triangle calculate the normal. 

>Follow each normal in both
>directions and count the intersections, to determine the inside (odd
>number). 

This has all the same drawbacks as the original proposal, of course.  
There are better ways to find the outside normal.  In fact, the one I'm
thinking of is the same kind of algorithm you've proposed: 

1. start with a random triangle and pick a direction to be called "outside."  
2. Propagate this decision to its neighbors, and their neighbors, and so on 
   until there are no more neighbors.  Now you have a connected, closed piece 
   of the mesh with consistent normals.  
3. Pick a point outside the bounding box of the mesh.
4. If the point is "inside" the piece using the test below, flip all the 
   normals.  
5. If there are any triangles left that are not in the "mesh so far," pick one 
   and build a closed, connected surface for it using steps 1-4.  
6. If one of the points on the new piece is inside the "mesh so far", flip its 
   normals again before adding it to the "mesh so far."  
7. If any piece of the "mesh so far" is inside the new piece, flip that piece's 
   normals before adding the new piece.  Do this for every piece that's inside
   the new piece.
8. Repeat from step 5 until you run out of unused triangles.

>Then replace the triangle by a plane with the "outside normal".

If you know the outside normal for every triangle, your work is done.  For
any given point, just fire a ray at a random triangle in the mesh.  At the
first intersection (possibly not the triangle you fired at) check the normal.
If it points away from you, you're inside.  If it points toward you, you're
not.  If it's perpendicular, ignore it and try firing at a different triangle.

[plausible solution snipped for space]
>Does this make sense?

It makes sense.  I think it would even work.  But I think it'd be even slower
than intersection-counting.  It would almost certainly be slower than the 
method I've proposed.

Post a reply to this message