I have a model rendered as a mesh. The mesh is read in from a file where each element (triangles for now) has 3 vertices listed in either counter-clockwise or clockwise order when traversing the triangle. This order is used to show which way the surface normals are pointing. If listed in the file in CCW order, the surface normal would be pointing outwards, if CW, then inwards. Either way, I would like to somehow show which way the surface normals are pointing from my mesh, but that's another issue. I will use this directon of each face in my mesh topology as I trace from one element to another in testing for connectivity and other things. So here's my problem. How do I know if the element has it's vertices listed in CCW or CW order so that I can do some checks on the surface normals from one element to the next? BTW - And since I'm new to the concept, any better explanation of a surface normal would be of help. Any help much appreciated.

It would be better if you would make it more clear what exactly you want.
There is at least two possible interpretations:

1: you want some normals to point inward and some outward depending to the winding order. That's what you get by computing normal using cross product. You do not need any extra work, normal you get is already pointing inside in one case and outside in other.

2: you want to determine winding order of the face, for some other additional reason, so that you do not just get desired result without determining winding order(i.e. it is not like case 1). For example you have bad mesh with mixed winding order and want to fix it up.

Any method will have a lot of problems with non-closed meshes, self-intersecting meshes or moebius strips or klein bottles, i.e. when "inside" and "outside" is not defined. I think it is very likely bad idea to make some faces be clockwise and some counterclockwise.
Beware that in 3D, face by itself is not "clockwise" or "counterclockwise". If you look from one side, it may be clockwise, and looking from other side, it could be counterclockwise. (not to mention handness of coordinate system you use) For non-closed meshes and especially meshes like Klein bottle or Moebius strip, "clockwise" or "counterclockwise" definately doesn't make any sense at all.

With closed non-selfintersecting mesh, you can for example define CW and CCW as seen from outside of the mesh.
There is two ways to find such clockwiseness:
a.) Geometrical method. trace ray from center of triangle pointing in direction of normal (as determined by cross product), check for intersection with all other triangles . If there is even number of intersections (or 0), normal points outside, else it points inside.
b.) Topological method. For every triangle DAB or DBA that shares edge with triangle ABC, if vertices of edge is in same order in both triangles, them has different winding, otherwise same winding. I.e. let ABC has CW winding. Then DAB has CCW winding (both has AB) and DBA has CW (one has AB and other BA).
This way you start with one known triangle and then determine winding of all neighbouring ones, and so-on. If you run into contradiction, then you are dealing with non-orientable surface (like Klein bottle)

Again, clockwise and counterclockwise makes sense only with closed meshes that do not intersect itself.

Sorry I wasn't clear enough.

The reason I'm trying to figure out which way the surface normals point (by the winding order) is so that I can create a true graph representation from the mesh (which I trace the topology of) and get the regions of interest. Regions (or volumes) for example, are what I gather from knowing the surface normals. I.e. I have a sphere, the inside of the sphere is region 1 because it's surface normals point inwards, and the outside of the sphere is region 2, it's surface normals point outwards. I use these surface normals to find regions or volumes.

Another example might be 100 1" thick cylinders that when all stacked on top of each other might resemble a broom stick, but in fact, they all have their own volume or region and I want to be able to select and show each individual region or cylinder volume.

So what I do is trace the topology from one starting triangle to a connecting triangle and if both elements have the same winding order, that means both surfaces point in the same direction and I can add this connecting surface to my region list. If it doesn't, then the new element is not part of this region/volume. So far, all the models I've been dealing with are closed meshes.

still not very clear. If you have 100 separate cylinders, there is no edges shared among the cylinders. It may even be 100 cylinders partly immersed into eachother, it doesn't matter. If it is separate cylinder meshes then you can just pick any mesh you want and display it, or display all.

(If you initially have triangle soup, then yes there will be problems and yes you probably will need some "heruistics" to split it into parts, but i'm assuming that's not the case ("mesh" implies that it is not triangle soup))
So: you have some sort of triangle soup and want to find "regions" of it?

By the way, as I told, if one triangle is ABC and other is DAB them have different winding order(both has AB), if other triangle is DBA them have same order.(one has AB and other has BA). You can make 2 paper triangles and test yourself.

edit:
Also, individual triangle has no winding order, and there must be externally defined direction. If you have triangle ABC and some direction, then you can compute normal of that triangle (using cross product) and use sign of dot product of normal and direction to determine winding order.
That is, use dot_product(direction, cross_product(B-A,C-A)) that is positive or negative depending to winding order you see looking along direction. Where cross_product(B-A,C-A) gives normal of the triangle (not unit length but doesn't matter there)
If you have "normal" explicitly storen in the file, you can use it as direction. I.e. essentially determine if normal of triangle is parallel to "normal" storen in file, or antiparallel.

[Edited by - Dmytry on October 6, 2005 4:41:49 PM]

Quote:Original post by Dmytry
still not very clear. If you have 100 separate cylinders, there is no edges shared among the cylinders. It may even be 100 cylinders partly immersed into eachother, it doesn't matter. If it is separate cylinder meshes then you can just pick any mesh you want and display it, or display all.

I should have stated that each cylinder is closed on both ends. But when you stack the cylinders on top of each other, the adjoining ends become a commen *shared* edge (since that's how the original model was created). So it's not like there will be triangles overlaying each other when they come together. Each cylinder when joined will share a common edge. So if a model has two cylinders, then I will have 3 regions. Region 1 showing the outside of both cylinders joined, Region 2 showing only the outside of the 1st cylinder (since it has a volume in itself), and Region 3 showing the outside of the 2nd cylinder (as it has it's own volume).

What makes it difficult is that I have to find the separate cylinders and separate them as if they were all stacked together, so w/o the cylinder ends, it would be very difficult to be able to separate them. If it's closed, then it has a volume/region. This is what my application does. If I can't separate them, I can't select them and display each or all. Originally when my app reads in the model from a file, it displays them all. I need to be able to break it down.

Quote:Original post by Dmytry
... ("mesh" implies that it is not triangle soup))
So: you have some sort of triangle soup and want to find "regions" of it?

Well, it's a mesh so I guess it's not triangle soup.

Quote:Original post by Dmytry
By the way, as I told, if one triangle is ABC and other is DAB them have different winding order(both has AB), if other triangle is DBA them have same order.(one has AB and other has BA)

Well, I don't decide the winding order. This order is how the model was created and is used to help decide where regions reside. I think I'm not making this clear as I can't seem to get the point across of what I'm doing.

if you have information like
triangle 1: 0,0,0 ; 0,1,0 ; 0,1,1
triangle 2: 0,0,0 ; 0,1,1 ; 0,0,1
it is triangle soup of the "quad"
If you have information like
vertice 1: 0,0,0
vertice 2: 0,1,0
vertice 3: 0,1,1
vertice 4: 0,0,1
triangle 1: 1,2,3
triangle 2: 1,3,4
it is more or less mesh.

It is not simple to convert "triangle soup" into collection of meshes, and any algorithm doing that is going to fail in many cases.

edit: also,

Quote:
By the way, as I told, if one triangle is ABC and other is DAB them have different winding order(both has AB), if other triangle is DBA them have same order.(one has AB and other has BA). You can make 2 paper triangles and test yourself.

explains how to implement "if both elements have the same winding order"

Quote:Original post by Dmytry
If you have information like
vertice 1: 0,0,0
vertice 2: 0,1,0
vertice 3: 0,1,1
vertice 4: 0,0,1
triangle 1: 1,2,3
triangle 2: 1,3,4
it is more or less mesh.

Ah, good, because I have information like this in my file. So I really think I'm ok here. And I think I have another way to explain my problem ...

I have direction. This is shown by the order that the vertices are listed in my file.

Example:

If listed as A, B, C in my file, then the direction of the triangle is CCW.
If listed as B, A, C (assuming all points are in same position as abc), then the direction is CW.

So with this information (which I have), I should know which way my surface normals point.

Here's my problem ... and this is going to sound really stupid, how does a computer know what order A from B from C is? How do I tell it that ABC is CCW and not CW, afterall, I'm just reading in a bunch of vertice id's that make up a triangle. I know these vertices are in the winding order of either CCW or CW by the way the file was formatted (domain knowledge as a developer). But to a computer, A, B, and C are just vertices, I might as well call them Tom, Ben, and Jerry ... where's the directional order in that?

Does that make my point anymore clear?

Given a list of 3 vertices in normal 3 dimensional space, the vertices are niether clockwise nor counterclockwise. They form a triangle, and if you look at the triangle from one side, the vertices go clockwise around it. If you look at the triangle from the other side, the vertices go counterclockwise around it. This provides a convenient way to assign a front and a back to a triangle. We can say the side that when viewed appears to have the points in counterclockwise order is the front, and the clockwise side is the back. We can also say the surface normal points outward from the front.