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