Jim Kress <kre### [at] kressworkscom> wrote:
> What I want to do is make sure all triangle normals are pointing out of the
> surface and all triangles are wound counter-clockwise.

  Why didn't you say so from the very beginning?

  The problem is not trivial nor necessarily fast to compute, specially
if you can't trust that the triangles are given all with the same winding.

  The problem makes sense only on closed triangle meshes (if the mesh is
open, it can't have a well-defined interior). Also each triangle should be
adjacent (ie. share two vertices) to exactly three other triangles, no more,
no less. If these conditions are not met, the problem is not unambiguous
and thus doesn't necessarily have one unique correct answer (and specially
if a triangle is not adjacent to exactly three other triangles, but less
or, heaven forbid, more, all kinds of funny problems will arise when trying
to decide which side is which). Another sanity prerequisite: no coincident
surfaces, thanks.

  If the conditions are met, then the problem is solvable and has a
unique solution (as your intuition probably tells you).

  First you have to take a triangle and solve which side is facing
outside the closed mesh and which side is facing inwards.
  There are probably several algorithms for resolving this, but the one
that comes to mind is: Shoot a ray from the surface of the triangle to one
side of it (it doesn't really matter which direction), and if hits an even
amount of other triangles (also 0 is even), that side is is outside, else
it's inside.
  This has to be implemented with extreme care. There's a patological case
which has to be handled carefully or else the result will be erroneous:
If the ray hits a triangle exactly in its edge or even in its vertex.
The problem with this is whether you have to count the other triangle sharing
that edge or not: In some cases you should not count it while in other
cases you must count it! (The two different cases happen when the ray
goes "through" the surface formed by the two triangles, or when it just
"touches" the edge formed by the two triangles, but without going through
it. If the ray goes through a vertex point, the situation is even more
complicated.)
  I would say that the easiest way is that if a ray-hits-edge or
ray-hits-vertex case is detected, then just forget that ray and shoot
another ray to another direction. (In theory this could lead to an
infinite loop in an extremely pathological case, but I think that the
odds for this happening are laughably small.)

  Once you have made sure for this triangle which side is the outside,
you can change the order of its vertices if necessary.
  Now the next task is to fix the order of the vertices of all the other
triangles as well.
  There are basically two approaches for this: You could repeat the
raytracing process described above for each triangle, or you could fix
the other triangles with the help of this one, which you already know for
sure.
  The latter method works like this: Since you know the right ordering of
this triangle, you can know the right order for the three triangles adjacent
to it (the two shared vertices in the adjacent triangle should be listed in
reverse order than in this triangle; if they aren't, just swap them and
there you are: it's fixed). Now you can do this process recursively to
each of the two other triangles adjacent to the three triangles you just
fixed (you have to ne able to mark triangles as "fixed" so that you know
where to continue and where to stop).
  Which one of these two methods is better depends. It's quite clear that
the raytracing method is much slower than the adjacent-triangle-checking
method. On the other hand, the latter needs more memory (in pathological
cases *huge* amounts of memory) because you need to do it recursively.
(It might be possible to develop a non-recursive, ie. iterative version
of this algorithm which doesn't take as much memory, but I'm too tired
to think about that now.)

  All in all, it's not trivial and requires some complicated algorithms.
You'd be better good at coding. :)

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message