Surface Normals

[sinanmut]

Hi,

I am have a mesh structure, and I computed the face normals. But some of the normals are correct and some of them are in opposite side. I know that same 3D programs like Maya, 3d Max and Blender are correcting the normals, but I have not understood the algorithm. Can anybody help me to solve the problem or can anybody tell the algorithm.

Thank you for your time and consideration.

Best Regards.

Sinan Mutlu

[hovermonkey]

It's pretty simple, you just find one known correct normal (start from the highest point in the mesh and you know the normal points upwards for example) and then go round the mesh making sure all the normals in each triangle face the same way. ie if triangle 1 has normals N1, N2, N3 and N1 is known to be correct then make sure that N2 and N3 are facing in the same direction (ie if the dot product between N1 and N2 is <0 then invert N2, etc.)

This will fail on some odd meshes (klein bottle or moebius strip type meshes) but generally works fine for most sensible ones.

[anubis]

Using the algorithm from this thread you can also ensure winding order of triangles without a reference normal.

http://www.devmaster.net/forums/showthread.php?t=12232

[rouncer]

dot product test.

[sinanmut]

Thank you for your helps,

I tried to understand the algorithm, and implemented it. But still there is a problem about the normals. This time the adjacent triangles have correct normals but there are areas in the mesh like that in first area normals are directed correctly and in the next area normals are directed oppositely.
I am missing something but I have not find it.
My code is like this:


typedef struct _3DMedXVertex{
double x;
double y;
double z;
}_3DMedXVertex;


typedef struct _3DMedXEdge;

typedef struct _3DMedXTriangle_ID{
int firstID;
int secondID;
int thirdID;
bool normalCorrected;
bool normalEvulated;
_3DMedXVertex * triangleNormal;
_3DMedXEdge * e1;
_3DMedXEdge * e2;
_3DMedXEdge * e3;
}_3DMedXTriangle_ID;

typedef struct _3DMedXEdge{
int edgeID;
_3DMedXVertex * startVertex;
_3DMedXVertex * endVertex;
int numberTri;
vector<_3DMedXTriangle_ID *> triList;
}_3DMedXEdge;

and the functions are:






void correctNormals()
{
bool first = false;
_3DMedXTriangle_ID * lastTriangle;

for(int i=0; i<_trilist.size(); i++)
{
if(_trilist[i]->normalEvulated)
continue;
if(!first)
{
first = true;
lastTriangle = _trilist[0];
lastTriangle->normalEvulated = true;
}
else if(!_trilist[i]->normalEvulated && !_trilist[i]->normalCorrected)
{
lastTriangle = _trilist[i];
lastTriangle->normalEvulated = true;
}

correctNormalsHelper(_trilist[i]);
}
}



void correctNormalsHelper(_3DMedXTriangle_ID *triangleTemp)
{
int count=0;
double lenght_Triangle = powl(triangleTemp->triangleNormal->x, 2) + powl(triangleTemp->triangleNormal->y, 2)
+ powl(triangleTemp->triangleNormal->z, 2);
lenght_Triangle = powl(lenght_Triangle, 1.0/2.0);

_3DMedXEdge * e1 = triangleTemp->e1;
_3DMedXEdge * e2 = triangleTemp->e2;
_3DMedXEdge * e3 = triangleTemp->e3;
_3DMedXTriangle_ID * triangleCorrect1 = NULL;
_3DMedXTriangle_ID * triangleCorrect2 = NULL;
_3DMedXTriangle_ID * triangleCorrect3 = NULL;
bool firstTriangle_Controlled = false;
bool secondTriangle_Controlled = false;
bool thirdTriangle_Controlled = false;
int neight_tri_count = 0;
if(e1->triList.size()>1)
neight_tri_count++;
if(e2->triList.size()>1)
neight_tri_count++;
if(e3->triList.size())
neight_tri_count++;

if(e1->numberTri>1 && e1->triList[0]!=triangleTemp && e1->triList[0]->normalEvulated)
count++;
else if(e1->numberTri>1 && e1->triList[1]!=triangleTemp && e1->triList[1]->normalEvulated)
count++;
if(e2->numberTri>1 && e2->triList[0]!=triangleTemp && e2->triList[0]->normalEvulated)
count++;
else if(e2->numberTri>1 && e2->triList[1]!=triangleTemp && e2->triList[1]->normalEvulated)
count++;
if(e3->numberTri>1 && e3->triList[0]!=triangleTemp && e3->triList[0]->normalEvulated)
count++;
else if(e3->numberTri>1 && e3->triList[1]!=triangleTemp && e3->triList[1]->normalEvulated)
count++;

if(neight_tri_count==3 && count==3)
return;
else if(neight_tri_count==2 && count==2)
return;
else if(neight_tri_count==1 && count==1)
return;
else
{
if(e1->numberTri>1)
{
//_3DMedXTriangle_ID * triangleCorrect;
if(e1->triList[0]!=triangleTemp)
triangleCorrect1 = e1->triList[0];
else
triangleCorrect1 = e1->triList[1];

double normal_X = triangleCorrect1->triangleNormal->x;
double normal_Y = triangleCorrect1->triangleNormal->y;
double normal_Z = triangleCorrect1->triangleNormal->z;
double lenght_nor = normal_X*normal_X + normal_Y*normal_Y + normal_Z*normal_Z;
lenght_nor = powl(lenght_nor,1.0/2.0);


double dot_product = triangleTemp->triangleNormal->x*normal_X
+ triangleTemp->triangleNormal->y*normal_Y
+ triangleTemp->triangleNormal->z*normal_Z;
double angle = acos(dot_product/(lenght_Triangle*lenght_nor));
angle = angle*(180.0/3.1415926535);
if((angle<=-90 || angle>=90))
{
flippingNormals(triangleCorrect1->triangleNormal);
triangleCorrect1->normalCorrected = true;
}
if(!triangleCorrect1->normalEvulated)
{
triangleCorrect1->normalEvulated = true;
firstTriangle_Controlled = true;
//correctNormalsHelper(triangleCorrect1);
}
}
if(e2->numberTri>1)
{
if(e2->triList[0]!=triangleTemp)
triangleCorrect2 = e2->triList[0];
else
triangleCorrect2 = e2->triList[1];

double normal_X = triangleCorrect2->triangleNormal->x;
double normal_Y = triangleCorrect2->triangleNormal->y;
double normal_Z = triangleCorrect2->triangleNormal->z;
double dot_product = triangleTemp->triangleNormal->x*normal_X
+ triangleTemp->triangleNormal->y*normal_Y
+ triangleTemp->triangleNormal->z*normal_Z;
double lenght_nor = normal_X*normal_X + normal_Y*normal_Y + normal_Z*normal_Z;
lenght_nor = powl(lenght_nor,1.0/2.0);
double angle = acos(dot_product/(lenght_Triangle*lenght_nor));
angle = angle*(180.0/3.1415926535);
if((angle<=-90 || angle>=90))
{
flippingNormals(triangleCorrect2->triangleNormal);
triangleCorrect2->normalCorrected = true;
}
if(!triangleCorrect2->normalEvulated)
{
triangleCorrect2->normalEvulated = true;
secondTriangle_Controlled = true;
//correctNormalsHelper(triangleCorrect2);
}
}
if(e3->numberTri>1)
{
if(e3->triList[0]!=triangleTemp)
triangleCorrect3 = e3->triList[0];
else
triangleCorrect3 = e3->triList[1];

double normal_X = triangleCorrect3->triangleNormal->x;
double normal_Y = triangleCorrect3->triangleNormal->y;
double normal_Z = triangleCorrect3->triangleNormal->z;
double dot_product = triangleTemp->triangleNormal->x*normal_X
+ triangleTemp->triangleNormal->y*normal_Y
+ triangleTemp->triangleNormal->z*normal_Z;
double lenght_nor = normal_X*normal_X + normal_Y*normal_Y + normal_Z*normal_Z;
lenght_nor = powl(lenght_nor,1.0/2.0);
double angle = acos(dot_product/(lenght_Triangle*lenght_nor));
angle = angle*(180.0/3.1415926535);
if((angle<=-90 || angle>=90))
{
flippingNormals(triangleCorrect3->triangleNormal);
triangleCorrect3->normalCorrected = true;
}
if(!triangleCorrect3->normalEvulated)
{
triangleCorrect3->normalEvulated = true;
thirdTriangle_Controlled = true;
//correctNormalsHelper(triangleCorrect3);
}
}
if(triangleCorrect1!=NULL && firstTriangle_Controlled)
correctNormalsHelper(triangleCorrect1);
if(triangleCorrect2!=NULL && secondTriangle_Controlled)
correctNormalsHelper(triangleCorrect2);
if(triangleCorrect3!=NULL && thirdTriangle_Controlled)
correctNormalsHelper(triangleCorrect3);
return;
}
}


correctNormalsHelper is a recursive function.

[sinanmut]

can anybody send me documents, papers or links about this subject.
Thank you.

[Reedbeta]

Please use the ... tags to post code.

[sinanmut]

I have downloaded the source code of blender, and in blender it is already done.
The code is:

void righthandfaces(int select) /* makes faces righthand turning */
{
EditMesh *em = G.editMesh;
EditEdge *eed, *ed1, *ed2, *ed3, *ed4;
EditFace *efa, *startvl;
float maxx, nor[3], cent[3];
int totsel, found, foundone, direct, turn, tria_nr;

/* based at a select-connected to witness loose objects */

/* count per edge the amount of faces */

/* find the ultimate left, front, upper face (not manhattan dist!!) */
/* also evaluate both triangle cases in quad, since these can be non-flat */

/* put normal to the outside, and set the first direction flags in edges */

/* then check the object, and set directions / direction-flags: but only for edges with 1 or 2 faces */
/* this is in fact the 'select connected' */

/* in case (selected) faces were not done: start over with 'find the ultimate ...' */

waitcursor(1);

eed= em->edges.first;
while(eed) {
eed->f2= 0; /* edge direction */
eed->f1= 0; /* counter */
eed= eed->next;
}

/* count faces and edges */
totsel= 0;
efa= em->faces.first;
while(efa) {
if(select==0 || (efa->f & SELECT) ) {
efa->f1= 1;
totsel++;
efa->e1->f1++;
efa->e2->f1++;
efa->e3->f1++;
if(efa->v4) efa->e4->f1++;
}
else efa->f1= 0;

efa= efa->next;
}

while(totsel>0) {
/* from the outside to the inside */

efa= em->faces.first;
startvl= NULL;
maxx= -1.0e10;
tria_nr= 0;

while(efa) {
if(efa->f1) {
CalcCent3f(cent, efa->v1->co, efa->v2->co, efa->v3->co);
cent[0]= cent[0]*cent[0] + cent[1]*cent[1] + cent[2]*cent[2];

if(cent[0]>maxx) {
maxx= cent[0];
startvl= efa;
tria_nr= 0;
}
if(efa->v4) {
CalcCent3f(cent, efa->v1->co, efa->v3->co, efa->v4->co);
cent[0]= cent[0]*cent[0] + cent[1]*cent[1] + cent[2]*cent[2];

if(cent[0]>maxx) {
maxx= cent[0];
startvl= efa;
tria_nr= 1;
}
}
}
efa= efa->next;
}

if (startvl==NULL)
startvl= em->faces.first;

/* set first face correct: calc normal */

if(tria_nr==1) {
CalcNormFloat(startvl->v1->co, startvl->v3->co, startvl->v4->co, nor);
CalcCent3f(cent, startvl->v1->co, startvl->v3->co, startvl->v4->co);
} else {
CalcNormFloat(startvl->v1->co, startvl->v2->co, startvl->v3->co, nor);
CalcCent3f(cent, startvl->v1->co, startvl->v2->co, startvl->v3->co);
}
/* first normal is oriented this way or the other */
if(select) {
if(select==2) {
if(cent[0]*nor[0]+cent[1]*nor[1]+cent[2]*nor[2] > 0.0) flipface(startvl);
}
else {
if(cent[0]*nor[0]+cent[1]*nor[1]+cent[2]*nor[2] < 0.0) flipface(startvl);
}
}
else if(cent[0]*nor[0]+cent[1]*nor[1]+cent[2]*nor[2] < 0.0) flipface(startvl);


eed= startvl->e1;
if(eed->v1==startvl->v1) eed->f2= 1;
else eed->f2= 2;

eed= startvl->e2;
if(eed->v1==startvl->v2) eed->f2= 1;
else eed->f2= 2;

eed= startvl->e3;
if(eed->v1==startvl->v3) eed->f2= 1;
else eed->f2= 2;

eed= startvl->e4;
if(eed) {
if(eed->v1==startvl->v4) eed->f2= 1;
else eed->f2= 2;
}

startvl->f1= 0;
totsel--;

/* test normals */
found= 1;
direct= 1;
while(found) {
found= 0;
if(direct) efa= em->faces.first;
else efa= em->faces.last;
while(efa) {
if(efa->f1) {
turn= 0;
foundone= 0;

ed1= efa->e1;
ed2= efa->e2;
ed3= efa->e3;
ed4= efa->e4;

if(ed1->f2) {
if(ed1->v1==efa->v1 && ed1->f2==1) turn= 1;
if(ed1->v2==efa->v1 && ed1->f2==2) turn= 1;
foundone= 1;
}
else if(ed2->f2) {
if(ed2->v1==efa->v2 && ed2->f2==1) turn= 1;
if(ed2->v2==efa->v2 && ed2->f2==2) turn= 1;
foundone= 1;
}
else if(ed3->f2) {
if(ed3->v1==efa->v3 && ed3->f2==1) turn= 1;
if(ed3->v2==efa->v3 && ed3->f2==2) turn= 1;
foundone= 1;
}
else if(ed4 && ed4->f2) {
if(ed4->v1==efa->v4 && ed4->f2==1) turn= 1;
if(ed4->v2==efa->v4 && ed4->f2==2) turn= 1;
foundone= 1;
}

if(foundone) {
found= 1;
totsel--;
efa->f1= 0;

if(turn) {
if(ed1->v1==efa->v1) ed1->f2= 2;
else ed1->f2= 1;
if(ed2->v1==efa->v2) ed2->f2= 2;
else ed2->f2= 1;
if(ed3->v1==efa->v3) ed3->f2= 2;
else ed3->f2= 1;
if(ed4) {
if(ed4->v1==efa->v4) ed4->f2= 2;
else ed4->f2= 1;
}

flipface(efa);

}
else {
if(ed1->v1== efa->v1) ed1->f2= 1;
else ed1->f2= 2;
if(ed2->v1==efa->v2) ed2->f2= 1;
else ed2->f2= 2;
if(ed3->v1==efa->v3) ed3->f2= 1;
else ed3->f2= 2;
if(ed4) {
if(ed4->v1==efa->v4) ed4->f2= 1;
else ed4->f2= 2;
}
}
}
}
if(direct) efa= efa->next;
else efa= efa->prev;
}
direct= 1-direct;
}
}

recalc_editnormals();

DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);

#ifdef WITH_VERSE
if(G.editMesh->vnode)
sync_all_versefaces_with_editfaces((VNode*)G.editM esh->vnode);
#endif

waitcursor(0);
}


in file editmesh_mods.c in the project blendercompactNG

but I could not understand the source code. Because I while I am compiling the project I get some errors. Can anybody tell me how can I implement this one.

Thank you for your time and consideration.