• Advertisement

Archived

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

Is my Per-Vertex Normal Calculation Algo correct?

This topic is 5101 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
AP, next time read the replies before rushing to the post button.... geeeez!

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 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
Since you are averaging the face normals and not the normalized face normals, I think both the 7 polygon cube and 6 polygon cube will have the same vertex normals if the duplicate face normals are not removed.

Edit: Mis-read one of the posts.


[edited by - jake_speed on March 7, 2004 4:11:38 AM]

Share this post


Link to post
Share on other sites
Why do you remove duplicate normals ?
If you have a normal twice, this means that two faces have the same normal - meaning that the average of the normals, needs to point a bit more to the 2 faces with the same face normal.
Everything else is not a correct algorithm of averaging the face normals.

Hope this is correct, too. ^_^'

cu BlackHC

Edit:
Thinking about it, I came up with a accurater way to weight the normals:
Weight them by the angles the faces have in common with the vertex.
This will solve the quad vs triangle problem, too.
Since once the normal will be weighted with 90 (quad) or two times with 45 (2 triangles), the average will remain the same.


[edited by - BlackHC on March 7, 2004 1:23:30 PM]

Share this post


Link to post
Share on other sites
Removing the duplicate normals is unusual. I can see why you''re trying to do it, but your logic of removal is wrong. What you should be doing if you want a truly accurate distrubution of normals is to scale each normal by the area of the triangle the normal came from. This can be argued as "more correct". It''s also least likely to produce results that anyone actually wants.

If you follow the standard, even though you feel it''s wrong, more art will work as expected. You won''t need to retrain artists to think about your new way of handling normals. You won''t have to tweak art to work with your "unique but correct" solution.

Feel free to use your algorithm, but also do the standard one, and use the standard one unless art is specifically made for your new system... If the normals get biased, the art will be designed with that normal-biasing in mind.

Share this post


Link to post
Share on other sites
quote:

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?


i concur, that would make by far the most sense. size shouldnt matter, number shouldnt, but adjecentness to the vertex should.

Share this post


Link to post
Share on other sites

  • Advertisement