Finding which faces a vertex belongs to for vertex normals.

[DeeperShade]

Ok, i'm trying to create vertex normals for each vertex.
I'm fairly sure i've got the math right, I'm just having trouble finding out to which faces a point belongs...

The points are store in:
vector <texTri> texvert

texTri contains, x, y, z, nx, ny, nz, u, v;

I identify vertices by their location in the array. I.e texvert[1] is point 1.

the faces are store in:
vector <texface> facelist

texface contains, p1, p2, p3;

I've got my face normals store in a seperate array:
vector <D3DXVECTOR3> normal

and i know how many faces and verts there are, i've got two ints (numFaces, numVerts).

I can't for the life of me figure this out.
How do I easily go through each vert, and find out which facenumber it belongs to, and then use all of those face's normals to get the vertex normal...

It's the searching i'm stuck with. The vert normal maths i've got.

Any ideas?

[mike_2000_17]

To clarify, if I understand the process, you have normals for all faces and then you need to generate a normal for each vertex, presumably as the average of the normals of the faces to which the vertex belongs (one vertex connects multiple faces).

I don't think there is any good way to do it by iterating through the vertices and finding the faces they belong to. You must do it the opposite way, iterate through the faces and accumulate vertex normal vectors for each of their vertices. Something like this (pseudo-code):

// initialize all vertex normals to 0.
for(std::size_t i = 0; i < texvert.size(); ++i) {
  texvert[i].nx = 0.0;
  texvert[i].ny = 0.0;
  texvert[i].nz = 0.0;
};

// accumulate the face normals in the vertices
for(std::size_t i = 0; i < facelist.size(); ++i) {
  texvert[ facelist[i].p1 ].nx += normal[i].x;
  texvert[ facelist[i].p1 ].ny += normal[i].y;
  ...
  texvert[ facelist[i].p3 ].nz += normal[i].z;
};

// re-normalize the accumulated vertex normals: 
for(std::size_t i = 0; i < texvert.size(); ++i) {
  double n_mag = std::sqrt( texvert[i].nx * texvert[i].nx
                          + texvert[i].ny * texvert[i].ny
                          + texvert[i].nz * texvert[i].nz );
  texvert[i].nx /= n_mag;
  texvert[i].ny /= n_mag;
  texvert[i].nz /= n_mag;
};

That should do the trick nicely.

[DeeperShade]

Thank you. I can't tell you how much help that was because I haven't finished implementing my version of your suggestion yet, instead i've run into an error I had before, and although I could throw in another cheap hack to get around it again, i'd really like to know why this is happening.

The problem comes when my function tries to subtract two vectors from each other, that contain the same Z value. it doesn't matter if I use my own code to do it or if I use d3dxvec3subtract. It still gives an erroronus value.

Code:

        vec1 = D3DXVECTOR3 (texvert[a].x, texvert[a].y, texvert[a].z);
        vec2 = D3DXVECTOR3 (texvert[b].x, texvert[b].y, texvert[b].z);
        vec3 = D3DXVECTOR3 (texvert[c].x, texvert[c].y, texvert[c].z);

        D3DXVec3Subtract  ( &v1, &vec2, &vec1 );
        D3DXVec3Subtract  ( &v2, &vec3, &vec2 );

Values:

texvert[a].x = 0.8086
texvert[a].y = 0.0000
texvert[a].z = -37.8033

texvert[b].x = 20.5252
texvert[b].y = 0.0000
texvert[b].z = -31.9022

texvert[c].x = 6.9014
texvert[c].y = -18.7516
texvert[c].z = -31.9022

results of subtraction:

v1.x = 19.7166
v1.y = 0.0000
v1.z = 5.6010

v2.x = -13.0238
v2.y = -18.7516
v2.z = -1.9073486e-006

And there we have my problem.
Subtracting -31.9022 from itself responds with an error. Now it only occurs when the answer should be (if my shaky maths is right ;) 0.0000, so i could just scan it for the letter e and the - symbol and if found replace with 0.0000 but thats a cheap hack and I'd prefer to solve this properly.

So why is this happening?

[mike_2000_17]

This is completely normal behavior. Floating-point numbers on a computer have limited precision. You're using float types which are also called single-precision floating point numbers, and the precision they have is usually about 7-8 significant digits. Your original number is around 30 and your error value is about 2e-6 which makes the relative error at about 0.67e-7 which is almost exactly the kind of error you should expect from using single-precision floating-point numbers (7-8 digits of precision). Get used to it, do not expect any floating-point calculations to be exact (they are only exact in a few rare cases). Doing numerical calculations on a computer is all about trying to limit the round-off errors (there is an entire field of computer science dedicated to this issue).

This also means that you should never to equal-comparison with floating-point numbers. That is, you should never do if(my_var == 0.0) but rather use this kind of test instead: if( fabs(my_var) < some_tolerance ) where you use some small tolerance value (e.g., 1e-5 to 1e-8 or so, depending if you use float or double).

The reason why 3D rendering code and libraries typically just use float as opposed to the more precise double is because precision is rarely a concern for rendering (it only needs to be as precise as the eye can distinguish, which is not precise at all) and speed is more critical.

[DeeperShade]

Thank you once again. My understanding grows with every chat we have. I can get back to trying to solve the original problem now :p