On 29 Aug 2000 12:24:28 -0400, Warp wrote:
>  I have done this kind of triangle mesh "fixing" myself (in my triangle
>mesh smoother program).
>  The idea is quite simple:
>
>  1. Take the first triangle and mark it as 'handled'.
>
>  2. Search all the triangles which are adjacent to this one and are
>     not marked as 'handled'. An adjacent triangle is one that shares two
>     vertices with this one.
>
>  3. Check if the adjacent triangle is ordered correctly. That is, if the
>     shared vertices are listed in inverse order in the adjacent triangle than
>     in the current triangle, then it's ok. If they are listed in the same
>     order, then you have to swap the other triangle.
>
>  4. Now mark these adjacent triangles as 'handled' and for each one of them
>     make recursively steps 2, 3 and 4 until no more triangles are found.
>
>  5. After that, search for some unhandled triangle. If the mesh consisted of
>     one contiguous surface, you'll not find any, but you have to do this
>     because the mesh may consist of several separate parts. If you find
>     an unhandled triangle, make all steps 1, 2, 3, 4 and 5 for it.
>
>
>  This works pretty well, but it's very slow, specially with big meshes.
>The slowest step is the second one (ie. the searching). There's probably some
>way of speeding it up using some tree structure or hash table.

You missed a step.  After you finish all the surfaces, you have to make sure 
they're correctly oriented.  Even if it's just one surface, you have to 
make sure you haven't inverted it.

The searching would be faster if each edge were a structure containing 
pointers to the two triangles that share it.  Building such a structure 
would be O(n log n).


-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message