Hi Jim -

Another way to accomplish the same task is to run recursively through all of
your adjacent triangles and ensure that the "vertex ordering" of their two
adjacent vertices is the same.  That is, if triangle A is adjacent to
triangle B, and they share vertices v1 and v2, then if v1 comes "before" v2
in the vertex ordering of A, it should be the same for B.  I'd recommend
starting with any triangle in your surface, tweaking the order of the
adjacent triangles so that it matches your start triangle - then continuing
recursively with each of the child triangles.

Note that triangle A being (v1, v2, v3) and triangle B being (v4, v1, v2) is
valid - but triangle B being (v2, v1, v4) wouldn't be, so you'd want to
switch it to (v4, v1, v2).

Once you've oriented all of your triangles the same way, pick any normal
from any triangle in the surface and fire a ray from that triangle out into
the model.  If it intersects with an even number of triangles, it is facing
"out" - if it intersects with an odd number of triangles, it is facing "in".
You only need to do this for one triangle.  I'm assuming your surface has an
"inside" and an "outside", though.

That should solve your problem - not too hard to implement, either.

JP

"Warp" <war### [at] tagpovrayorg> wrote in message
news:3d1cecc2@news.povray.org...
> 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

On Thu, 25 Jul 2002 12:11:36 -0700, John Pallett wrote:
> Another way to accomplish the same task is to run recursively through all of
> your adjacent triangles and ensure that the "vertex ordering" of their two
> adjacent vertices is the same.  

Are you sure you don't have this backwards?

  A--B
  |\ |
  | \|
  C--D

Notice that A-D-C and B-D-A are both clockwise, but the D-A edge is not
represented the same in both triangles.

-- 
#macro R(P)z+_(P)_(P)_(P+1)_(P+1)+z#end#macro Q(C,T)bicubic_patch{type 1u_steps
6v_steps 6R(1)R(3)R(5)R(7)pigment{rgb z}}#end#macro _(Y)#local X=asc(substr(C,Y
,1))-65;<T+mod(X,4)div(X,4)9>-2#end#macro O(T)Q("ABEFUQWS",T)Q("WSXTLOJN",T)#
end O(0)O(3)Q("JNKLCGCD",0)light_source{x 1}// ron### [at] povrayorg

Post a reply to this message

You're right.  Adjust to make sure that all of your orderings are OPPOSITE,
not the same.  Sorry, that was a napkin-scratched solution.

Thanks, Ron.  Jim, hope this helps.

JP

"Ron Parker" <ron### [at] povrayorg> wrote in message
news:slr### [at] fwicom...
> On Thu, 25 Jul 2002 12:11:36 -0700, John Pallett wrote:
> > Another way to accomplish the same task is to run recursively through
all of
> > your adjacent triangles and ensure that the "vertex ordering" of their
two
> > adjacent vertices is the same.
>
> Are you sure you don't have this backwards?
>
>   A--B
>   |\ |
>   | \|
>   C--D
>
> Notice that A-D-C and B-D-A are both clockwise, but the D-A edge is not
> represented the same in both triangles.
>
> --
> #macro R(P)z+_(P)_(P)_(P+1)_(P+1)+z#end#macro Q(C,T)bicubic_patch{type
1u_steps
> 6v_steps 6R(1)R(3)R(5)R(7)pigment{rgb z}}#end#macro _(Y)#local
X=asc(substr(C,Y
> ,1))-65;<T+mod(X,4)div(X,4)9>-2#end#macro
O(T)Q("ABEFUQWS",T)Q("WSXTLOJN",T)#
> end O(0)O(3)Q("JNKLCGCD",0)light_source{x 1}// ron### [at] povrayorg

Post a reply to this message

Exactly how does this solution differ from the one I suggested?

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

<laughing VERY hard> My apologies, Warp - not enough coffee yesterday.  I
re-read your solution and it is exactly the same as the one I proposed.

Well, not exactly.  In your solution, the ray gets fired first - in mine it
gets fired at the end.

Boy, am I embarrased.  :)

JP


"Warp" <war### [at] tagpovrayorg> wrote in message
news:3d4097dc@news.povray.org...
>   Exactly how does this solution differ from the one I suggested?
>
> --
> #macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb
x]
> [1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
> -1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// -
Warp -

Post a reply to this message