 # Unify triangles orientation.

Hi there !

I was almost sad not to have anything to ask and, as you already guessed, I have a new problem !

I am still working on my post-processor for CFD results. DON’T GO AWAY : the question is not linked to CFD !

Well, I have used the Marching Cubes algorithm to build an iso-surface from one of our models. The thing is, some faces are correctly orientated, others aren’t. It is not a problem for displaying as I do not cull faces (for some obscure reasons !). But it is a problem for normal smoothing !

So my question is: is there a way of unifying my triangles orientation ? The linked question is: when OpenGL culls a face, how does it compute the value that tells it if the face is front or back facing ???
I thought it was a combination of cross and dot products but I can’t get it right (stupid me !).

Thanks to anyone who can help (and the others as well ! )

Best regards.

Eric

P.S. : I have just subscribed to fortunecity for 100Mb free web site. I might use it to log the most common questions I receive from this discussion forum (I won’t publish sources that are sent to me: I would rewrite a sample app). Is anyone interested ? First topics would cover selection, rotation, MFC/Glut…

Ccan at least tell you how OpenGL does the face culling. It’s usually performed by determin the vertex order as projected on the screen. For example, if the projected triangle’s vertices is in clockwise order, and you have told OpenGL to cull backfaces, and a frontface is GL_CW, the then the triangle is visible. (Uh, hope that was correct )

And the other problem… well, maybe I can say something. But first I have to ask you: Do you ALWAYS get the normal correct but the vertex order is wrong sometimes, or is the normal wrong (inverted?) for all wrong oriented triangles? If it’s the first case, you can calculate the normal from the vertices you got, and see if the angle between the actual normal is greater than 90 degrees, if so, the triangle is oriented wrong, and just swap two veritces to get them in correct order. If it’s the other case, don’t ask me .

Hi Bob !

Thanks for the hint on OpenGL culling ! I hoped it was done at 3D level but suspected it was actually done after projection…

Concerning the normals, I actually calculate them from the vertices i.e. when I have a problem, it is because of the vertices orientation… What I am looking for is a method to unify such a mesh (3DS Max has got a function for it… But even this one does not always work !).

I have solved my problem in another way. I’ll try to explain it !

Basically, what I want to do is smooth my mesh.

Here is the routine I use:

/****** AWFUL ROUTINE START ******/

int i,i1,i2,j;

for (i1=0;i1<m_iNObjects;i1++)
{
C_SurfaceFace pFace1=(C_SurfaceFace) m_pObjects[i1];
for (i2=i1+1;i2<m_iNObjects;i2++)
{
C_SurfaceFace pFace2=(C_SurfaceFace) m_pObjects[i2];
if (pFace1->m_vNormal.CalculateAngle(pFace2->m_vNormal)<SmoothAngle)
{
for (j=0;j<3;j++)
{
HGL_Vector3Df vVector;
vVector=pFace1->m_ptVertices[j]-pFace2->m_ptVertices;
if (vVector.Norm()<DistanceTolerance)
{
if (pFace1->m_vNormals[j].DotProduct(pFace2->m_vNormal)>0)
pFace1->m_vNormals[j]=pFace1->m_vNormals[j]+pFace2->m_vNormalpFace2->m_fArea;
else
pFace1->m_vNormals[j]=pFace1->m_vNormals[j]+pFace2->m_vNormal
pFace2->m_fArea*(-1);
if (pFace2->m_vNormals.DotProduct(pFace1->m_vNormal)>0)
pFace2->m_vNormals=pFace2->m_vNormals+pFace1->m_vNormalpFace1->m_fArea;
else
pFace2->m_vNormals=pFace2->m_vNormals+pFace1->m_vNormal
pFace1->m_fArea*(-1);
}
vVector=pFace1->m_ptVertices[j]-pFace2->m_ptVertices;
if (vVector.Norm()<DistanceTolerance)
{
if (pFace1->m_vNormals[j].DotProduct(pFace2->m_vNormal)>0)
pFace1->m_vNormals[j]=pFace1->m_vNormals[j]+pFace2->m_vNormalpFace2->m_fArea;
else
pFace1->m_vNormals[j]=pFace1->m_vNormals[j]+pFace2->m_vNormal
pFace2->m_fArea*(-1);
if (pFace2->m_vNormals.DotProduct(pFace1->m_vNormal)>0)
pFace2->m_vNormals=pFace2->m_vNormals+pFace1->m_vNormalpFace1->m_fArea;
else
pFace2->m_vNormals=pFace2->m_vNormals+pFace1->m_vNormal
pFace1->m_fArea*(-1);
}
vVector=pFace1->m_ptVertices[j]-pFace2->m_ptVertices;
if (vVector.Norm()<DistanceTolerance)
{
if (pFace1->m_vNormals[j].DotProduct(pFace2->m_vNormal)>0)
pFace1->m_vNormals[j]=pFace1->m_vNormals[j]+pFace2->m_vNormalpFace2->m_fArea;
else
pFace1->m_vNormals[j]=pFace1->m_vNormals[j]+pFace2->m_vNormal
pFace2->m_fArea*(-1);
if (pFace2->m_vNormals.DotProduct(pFace1->m_vNormal)>0)
pFace2->m_vNormals=pFace2->m_vNormals+pFace1->m_vNormalpFace1->m_fArea;
else
pFace2->m_vNormals=pFace2->m_vNormals+pFace1->m_vNormal
pFace1->m_fArea*(-1);
}
}
}
}
}
for (i=0;i<m_iNObjects;i++)
{
C_SurfaceFace pFace=(C_SurfaceFace) m_pObjects[i];
if (pFace->m_vNormals.DotProduct(pFace->m_vNormal)>0)
pFace->m_vNormals=pFace->m_vNormals+pFace->m_vNormalpFace->m_fArea;
else
pFace->m_vNormals=pFace->m_vNormals+pFace->m_vNormal
pFace->m_fArea*(-1);
if (pFace->m_vNormals.DotProduct(pFace->m_vNormal)>0)
pFace->m_vNormals=pFace->m_vNormals+pFace->m_vNormalpFace->m_fArea;
else
pFace->m_vNormals=pFace->m_vNormals+pFace->m_vNormal
pFace->m_fArea*(-1);
if (pFace->m_vNormals.DotProduct(pFace->m_vNormal)>0)
pFace->m_vNormals=pFace->m_vNormals+pFace->m_vNormalpFace->m_fArea;
else
pFace->m_vNormals=pFace->m_vNormals+pFace->m_vNormal
pFace->m_fArea*(-1);
pFace->m_vNormals.Normalize();
pFace->m_vNormals.Normalize();
pFace->m_vNormals.Normalize();
}

/****** AWFUL ROUTINE END ******/

As you can see, before I add any face normal to a vertex normal, I check if they are orientated the same way (DotProduct). If they aren’t I add the opposite of the face normal (or I substract the normal, as you prefer !).

With this algorithm, all problems are gone ! But I still can not cull the faces…

A funny thing is that these tests would enable me to reorientate the faces correctly ! (which means I was trying to do A to achieve B and I finally managed to do B which would enable me to achieve A !).

If it sounds a bit obscure, I could gibe some more explanations !

What are you using as your rendering primitives? If you are using GL_TRIANGLE_STRIPS you should be aware of how those are used to calculate the front/back face. I’m going from memory here, but I think it’s close. Say you have 10 vertices, which we’ll just number 1-10. If you were to pass those 10 vertices in a strip like so…

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

The actual triangles that are created from that are in an order something like this…

(1,2,3) (3,2,4) (3,4,5) (5,4,6) (5,6,7) (7,6,8) (7,8,9) (9,8,10)

Notice that the orders of the vertices alternate. It does this so that the winding order (CW vs CCW) stays the same for some the most common useage of strips.

The other problem is “unify the winding order
TO WHAT?”

How is the computer to know which direction
you want the normal to point in? There has
to be something in your algorithm that
determines this when you create the triangles
and you have to get the algorithm right.

You could define an arbitrary “middle” of
the mesh and face all triangles “out” from
this “middle” but that may not yield correct
results for very convex meshes (or for even
mildly convex meshes in some cases). Thus,
only YOU can know for sure which way each
triangle is MEANT to go – so express that
knowledge already! Yes bgl, I know that and I guess this is my main problem !

I have tried to do it from the center of the mesh but it does not always work: the iso-surface I have is not always convex (or is not always a fraction of a convex one if you prefer !). The only solution here is to surface-tesselate (???) my big one. I mean find the sub-surfaces that are a fraction of a convex one… Could be done with the curving radius of the surface (well, in french it is called “rayon de courbure” and I do not know the english translation…).

I guess I will stick to the algorithm described above for the moment (i.e. check if the normals point in the same direction adn add/subtract according to that !). I do not really need to re-orientate the faces as I do not want to cull anyway !

Thanks to all of you for your help !

To Deiussum: in the current algorithm, I do not use strips but I have a stripper object that I made for importing ASE files. I will probably use it to optimize the mesh !

Best regards.

Eric