Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Prozak

Is my Per-Vertex Normal Calculation Algo correct?

This topic is 5192 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, before digging into the internet for some Vertex Normal calculation algorithms I decided to give it some thought on my white board, and I reached a basic algorithm: Pre-requisites: - All Faces must have their normals calculated. - Eliminate duplicate vertices to reduce algorithm time. Now, to calculate the normal of our vertex V: - Add all faces that use V to a list; - Remove from that List all faces that have the same normal, so that there aren''t any duplicate face normals in the list; - Average all the face normals still on the list, and thats our vertex normal. This is a slow algo intended for pre-processing scenarios, not real time. Is this the correct way to do it? (havent checked out other tuts on this yet), what other algorithms are there? Thanks for any tips/ thoughts on this... Salsa cooked it, your eyes eat it!
[Hugo Ferreira][Positronic Dreams][Colibri 3D Engine][Entropy HL2 MOD][My DevDiary]
[Yann L.][Enginuity] [Penny Arcade] [MSDN][VS RoadMap][Humus][BSPs][UGP][NeHe]
                          Prozak - The GameDever formally known as pentium3id

Share this post


Link to post
Share on other sites
Advertisement
Well, your algorithm gives the "correct" result (vertex normal == the average of the normals of the faces attached to it).

If you don''t have shading groups, you can go for an even more simple algo by changing the order of instructions a bit:

1.) Set all vertex normals to zero
2.) Loop through all faces
2.1) Compute the face normal for this face
2.2) Add this face normal to the vertices forming this face
2.3) Go back to 2
3.) Normalize vertex normals (if normalization required)

Most mesh structures store the vertices forming a face, so 2.2 is trivial. Also you don''t need any additional memory: even the face normal computed in 2.1 can be thrown away after 2.2 (or it can be saved for later usage, if you need it).

You might be confused by the fact that we don''t "average" normals anywhere in the algo. Well, this is not needed: averaging, ie. dividing by a positive constant (the number of faces connected to the vertex) doesn''t change the direction of the vertex normal, only the length of it - and we don''t really give a damn about temporary lengths because we''re about to normalize in the end anyway.

- Mikko Kauppila

Share this post


Link to post
Share on other sites
Great algo uutee, much faster in design, but there is an underlying reason for some of the steps i take in my algorithm.

I might be wrong but I think that to correctly calculate the vertex''s normal you can''t add the same face normal twice, because that screws up the end result.

An example. We have a Cube, from that Cube we have 3 faces from a corner. Each one of those 3 faces has a normal pointing in a diferent axis, one points to the left, the other down, and the other towards us:

_______X-Y-Z
Face1: 1-0-0
Face2: 0-1-0
Face3: 0-0-1

If I add those vectors up I get (1;1;1) which after being normalized becomes (0,5773;0,5773;0,5773).

BUT what happens when there is a repeated face normal? The vertex''s normal will then "deviate" towards that face.
Lets add a repeated face normal to our previous example:

_______X-Y-Z
Face1: 1-0-0
Face2: 0-1-0
Face3: 0-0-1
Face4: 1-0-0

The sum is now (2;1;1) which after normalization equals (0,8165;0,4082;0,4082), a totally diferent result...

I dont know, I might be wrong here, but I''ve given some good thought about this and this seems the correct way to do things... to eliminate result deviations...

Salsa cooked it, your eyes eat it!
[Hugo Ferreira][Positronic Dreams][Colibri 3D Engine][Entropy HL2 MOD][My DevDiary]
[Yann L.][Enginuity] [Penny Arcade] [MSDN][VS RoadMap][Humus][BSPs][UGP][NeHe]
                          Prozak - The GameDever formally known as pentium3id

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Prozak
- Remove from that List all faces that have the same normal, so that there aren''t any duplicate face normals in the list;
Why are you removing duplicate face normals? The usual approach is to add up all the face normals and normalize the result.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Prozak BUT what happens when there is a repeated face normal? The vertex''s normal will then "deviate" towards that face.
I see. So that''s why you''re removing duplicate normals? It might seem correct at first, but consider what happens when you have a pair of nearly identical but non-duplicate normals: the nearly identical normals are added together and the result is almost identical to what you''d get by adding up duplicate normals.

If you want to account for relative polygon influences perhaps you should multiply the face normal by the angle formed by the edges at the vertex whose normal you''re calculating?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Prozak
AP, next time read the replies before rushing to the post button.... geeeez!
What makes you think that your post existed at the time I clicked on the reply button?

Share this post


Link to post
Share on other sites
@utee:
>>vertices forming a face, so 2.2 is trivial.
no; most realtime engines don''t store the normal in it''s face structure, but either in it''s vertice structure or an extra array.

>>and we don''t really give a damn about temporary lengths
>>because we''re
no; the length of the normal _does_ matter; especially in cases where you are using "graphic API specific" lighting (scaling your normals results in buggy lighting, e.g.)

@Prozak:
>>If I add those vectors up I get (1;1;1) which after being
>>normalized becomes (0,5773;0,5773;0,5773).
no; (again*g*) you are averaging the whole stuff, _after_ you have added all face-normals to the according vertex-normals.

@AP:
>>have a pair of nearly identical but non-duplicate normals:
>>the nearly identical normals are added together and the
>>result is almost identical to what you''d get by adding up
>>duplicate normals.
then you have to duplicate the vertex, too; this will result in a "sharp/distinct edge" (depending on the direction of the normals) this is not un-usual !?!

DJSnow
---
this post is manually created and therefore legally valid without a signature

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by DJSnow
then you have to duplicate the vertex, too; this will result in a "sharp/distinct edge" (depending on the direction of the normals) this is not un-usual !?!
I don''t really understand what you mean by duplicating the vertex, but try to imagine a cube that''s had one of its 6 quads divided into a pair of triangles. In that case you have a cube with 6 sides but 7 polygons and 7 face normals. If the triangles corresponding to the subdivided face are coplanar then Prozak''s method disregards the second triangle''s face normal (because it''s identical to the first triangle''s face normal), but if the triangles are modified so that they''re not coplanar then what happens is that both triangles'' normals are included in the computation of the vertex normal. A small difference between the triangle''s normals would yield results very similar to what you''d get if you didn''t exclude identical face normals, and in that regard the method is problematic.

Share this post


Link to post
Share on other sites
>>no; most realtime engines don''t store the normal in
>>it''s face structure, but either in it''s vertice structure
>>or an extra array.

There''s no need to store face normals. They can be computed on the fly. IMHO a "basic" data structure for triangle rendering is (feel free to post other kinds of ideas)

class Vertex {
public:
Vector3D x,y,z;
};

class Triangle
{
public:
int n[3]; // triangle indices
};

This makes the procedure described above completely possible: face normals can be computed on the fly and the vertices forming a face are explicitly stated.

>>no; the length of the normal _does_ matter; especially
>>in cases where you are using "graphic API specific"
>>lighting (scaling your normals results in buggy lighting,
>>e.g.)

I don''t know of such APIs. I just assumed that we want the Final Vertex Normals (the ones we''re trying to compute in the end, as opposing to Temporary Vertex Normals ie. the ones that are still under computation in the algorithm) to be of unit length OR that we don''t care about the lengths of the Final Vertex Normals.

- Mikko Kauppila

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!