How does one test to see if a triangle's vertices are arranged in a
clockwise or counter clockwise direction?


Jim

Post a reply to this message

Jim Kress <kre### [at] kressworkscom> wrote:
> How does one test to see if a triangle's vertices are arranged in a
> clockwise or counter clockwise direction?

  Looking from which side?

-- 
#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

>   Looking from which side?

I am presented with a list of vertices (and their Cartesian coordinates) and
a set of triples that specify the vertex numbers for each triangle.  That is
all the information I have

How would I find out which side I am looking and then the direction?

Jim

Post a reply to this message

Jim Kress <kre### [at] kressworkscom> wrote:
> I am presented with a list of vertices (and their Cartesian coordinates) and
> a set of triples that specify the vertex numbers for each triangle.  That is
> all the information I have

> How would I find out which side I am looking and then the direction?

  You are looking at the side which is visible? A triengle mesh has two
sides. Which side would you want to know? What direction are you talking
about?

  I have to make guesses here since you are not giving me enough information.
  Is your situation so that you *know* that the triangle vertices are listed
with a certain winding (eg. clockwise) and you want to know if you are
looking at the triangle from the "outside" or the "inside"?
  Or is it so that the triangle vertices are given in a random order and
you need to know for each triangle, which side is facing the same direction
as the adjacent triangles?
  Or something else?

-- 
#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

I have a closed, 3D surface that is represented by a set of triangles.  I
have a list of the vertices of every triangle (i.e. the Cartesian
coordinates of each vertex) and I have a list of integers (grouped in
threes) where each group of integers gives me the number of each vertex in a
triangle.

For example:

vertex 1 is 1.0,2.0,3.0
vertex 2 is 2.0,3.0,4.0
vertex 3 is 4.0,5.0,6.0
vertex 4 is 5.0,6.0,7.0

Triangle 1 is made up of vertices 1,2,3
Triangle 2 is made up of vertices 1,2,4

The data I am given is:

1.0,2.0,3.0
2.0,3.0,4.0
4.0,5.0,6.0
5.0,6.0,7.0
1,2,3
1,2,4

This is all the data I am given.  I am not given any data about which side
of the triangle I am looking at.  I am not given any data about the winding
of the vertices.

What I want to do is make sure all triangle normals are pointing out of the
surface and all triangles are wound counter-clockwise.

Is that a better statement of my problem?  Any help you can provide would be
appreciated.

Jim

Post a reply to this message

Jim Kress wrote:
> 
> >   Looking from which side?
> 
> I am presented with a list of vertices (and their Cartesian coordinates) and
> a set of triples that specify the vertex numbers for each triangle.  That is
> all the information I have
> 
> How would I find out which side I am looking and then the direction?
> 
> Jim

First, you need your location (let's it be O).
Then compute the normal at one vertex (using vector product of
the edge of the triangle),
and lastly use the sign of the scalar product of the normal with
the vector O-vertex.
Clockwise will have one sign, and anti the other one.

Another use/convention of clockwise/anticlockwise orientation is
to indicate hole in mesh, but then they provide the normal of the
triangle too (because hole do not depent on view point). This
is obviously not the case here.

At best, all you could have in your case is a fast scanline engine,
removing the triangle which are facing the wrong direction
(assuming the mesh is closed and without holes). Or a dual texturing of
the triangles.
-- 
Non Sine Numine
http://grimbert.cjb.net/
Etiquette is for those with no breeding;
fashion for those with no taste.

Post a reply to this message

Jim Kress wrote:
> 
> I have a closed, 3D surface that is represented by a set of triangles.  
[SNIP]

> This is all the data I am given.  I am not given any data about which side
> of the triangle I am looking at.  I am not given any data about the winding
> of the vertices.
> 
> What I want to do is make sure all triangle normals are pointing out of the
> surface and all triangles are wound counter-clockwise.

See my other answer for the details.
Just choose any arbitrary location (possibly not right on the mesh, but even inside
is fine).
If the sign does not please you, just invert two vertices of the triangle.

Please note that you are not provided with the normal, so your first part looks
caduc (unless you exactly know how the normal is going to be computed).
The calculation of a normal always gives the same line, but the orientation
of the vector depends on the implementation. Your second part seems to imply
that you have such (implicit) knowledge about the internal computation.

> Is that a better statement of my problem?  Any help you can provide would be
> appreciated.

Just for curiosity, why do you need to do that ?


-- 
Non Sine Numine
http://grimbert.cjb.net/
Etiquette is for those with no breeding;
fashion for those with no taste.

Post a reply to this message

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

Thanks.  I'll try your suggestions and perhaps ask more questions later.

Jim

Post a reply to this message

Thanks for your help.  I'll try what you (and Warp) suggested.

Jim

Post a reply to this message