> I have a mesh of triangular facets, closed (all edges are shared by two
> 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.