reordering inconsitently oriended triangles in a mesh

reordering inconsitently oriended triangles in a mesh

Post by Frédéric Delhoum » Fri, 06 Jun 2003 18:04:57



Hi,

I have a mesh of triangular facets, closed (all edges are shared by two
facets).
However, some of the triangles seem to be clockwise oriented.
What would be a simple algorithm (I do not need state of the art)
and good data structure to check/fix theses facets ?

The mesh can be a very large mesh, containing up to 10 000 000 facets.
The mesh is indexed (each triangle is described by 3 indices to the
vertices array).

I have access to the ivnorm source code but it is tied to OpenInventor
and I would like to implement
the algorithm myself.

Thank you.

Frederic.

 
 
 

reordering inconsitently oriended triangles in a mesh

Post by Hans-Bernhard Broeke » Fri, 06 Jun 2003 21:22:19



> I have a mesh of triangular facets, closed (all edges are shared by
> two facets).  However, some of the triangles seem to be clockwise
> oriented.  What would be a simple algorithm (I do not need state of
> the art) and good data structure to check/fix theses facets ?

The plan would be this:

1) select a triangle and determine whether it's ordered correctly by
shooting a ray off it's supposed outer side and counting intersections
with others.  If odd, the ray went to the wrong side, and you should
re-orient that triangle.

2) Now, you'll have to run the equivalent of a flood-fill across the
mesh.  You'll be extending a borderline starting at the initial
triangle, pushing it outward all the time until it closes back on
itself again in the end.  The extension process works by checking
triangles just outside the border for vertex ordering consistent with
those just inside.  I.e. the shared edges should always be listed in
opposite order on both sides of the border.  If they're not, reverse them.

You'll have to keep track of where the border currently is.  If your
10 million triangles come as triangle soup, i.e. with no neighborhood
information at all, finding another triangle sitting just on the
outside of the border line could take *ages*, though.  

What you're doing is roughly a breadth-first traversal of the triangle
connectivity graph, with each triangle a node, and each geometric edge
represented by a graph edge connecting the two incident triangles.

If you lack this graph's information content, you'll have to organize
the search in some other way.  E.g. you could sort them by minimal
vertex z and use a triangle at one end of the sorted list to initiate
the traversal, and keeping an "active z range" that gives you the
advancing border line's projection onto the z axis.

--

Even if all the snow were burnt, ashes would remain.

 
 
 

reordering inconsitently oriended triangles in a mesh

Post by Dave Eberl » Fri, 06 Jun 2003 21:27:03



Quote:> I have a mesh of triangular facets, closed (all edges are shared by two
> facets).
> However, some of the triangles seem to be clockwise oriented.
> What would be a simple algorithm (I do not need state of the art)
> and good data structure to check/fix theses facets ?

> The mesh can be a very large mesh, containing up to 10 000 000 facets.
> The mesh is indexed (each triangle is described by 3 indices to the
> vertices array).

> I have access to the ivnorm source code but it is tied to OpenInventor
> and I would like to implement
> the algorithm myself.

From a June 2 post in this news group to a thread entitled
"Vertex winding and edge decimation":
-----
You can traverse the mesh using a breadth-first search and adjust
the triangles, if necessary, to be consistently ordered with the
first triangle visited by the search.  For example, if the first
triangle is <V0,V1,V2> and the triangle adjacent to edge
<V0,V1> is <V3,V1,V0>, then the adjacent triangle has a
consistent ordering with the original.  However, if the adjacent
triangle is <V3,V0,V1>, the ordering is inconsistent, so you
have to swap the last two indices to obtain <V3,V1,V0>.
-----

A depth-first search also works.  In either case the search
requires a data structure that stores triangle adjacency
information.  The one I use for establishing consistent triangle
ordering is at http://www.magic-software.com/Core.html ,
the section "Edge-triangle manifold meshes" (with files
MgcETManifoldMesh.*).  A depth-first-search-based
algorithm for generating consistent triangles is in code at
that same web page, but in file MgcTriangleMesh.cpp,
function GetConsistentComponent.  This code is easily
modified to use the MgcETManifoldMesh data structure.
A breadth-first-search-based algorithm is about the same
effort (and size) to write as the depth-first one.

--
Dave Eberly

http://www.magic-software.com
http://www.wild-magic.com

 
 
 

reordering inconsitently oriended triangles in a mesh

Post by Frédéric Delhoum » Fri, 06 Jun 2003 22:22:35


Thank you for your information, I will try those methods.

Frdric

 
 
 

1. Algorithm to combine triangle meshes into triangle strips

I am looking for an algorithm to convert a triangle mesh into
triangle strips (to be used for more efficient display on SGI
graphics hardware.)  The triangle mesh, by my definition, is a
set of triangles that share between 1 and 3 edges with another
triangle(s).  A triangle strip, as per the GL/OpenGL format, is
an ordered set of triangles (usually more than two) that share
two edges with neighboring triangles, except for the first and
last triangle in the set who only share edges with one triangle.

Any help would be greatly appreciated.  Thanks in advance.

Keith Fry
University of Michigan

2. Text/Fonts Showing as Solid Blocks on v3.0.4

3. Triangle List/Mesh to Triangle Strip

4. FREE TEXTURES !!

5. triangle mesh => triangle strip

6. feature request for POV 3 also

7. Triangle mesh with different texture per triangle

8. Where can I find stereograms on the net?

9. triangle mesh => triangle strip

10. Cutting Triangle Mesh Surfaces

11. Intersecting triangle meshes

12. triangles and meshes

13. POV: Image maps onto individual triangles of a mesh