Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

hi i'm a complete newbie in computergraphics so sorry if it's a stupid answer. i'm trying to make a simple 3d engine from scratch, more for educational purpose than for real use.

for now i compute only face normals. in this way:

i have a Surface object with inside a Triangle's list. i compute normals inside Triangle class, in this way:

triangle.computeFaceNormals() {
    Vec3D u = v1.sub(v3)
    Vec3D v = v1.sub(v2)
    Vec3D normal = Vec3D.cross(u,v)
    normal.normalized()
    this.n1 = this.n2 = this.n3 = normal
}

and when building surface:

t = new Triangle(v1,v2,v3)
t.computeFaceNormals()
surface.addTriangle(t)

and i think this is the best way to do that.. isn't it?

now.. this works, ok. but light it's not smoothed. i'm trying to compute also vertex normals. (i'm testing my engine with tubolar surfaces so i have almost all vertex shared with more then one triangles)

i've found this simple algorithm: flipcode vertex normal but.. hei this algorithm has.. exponential complexity? (if my memory doesn't fail my computer science background..) (bytheway.. it has 3 nested loops.. i don't think it's the best way to do it..)

any suggestion?

share|improve this question
    
What language is this? It looks to me like t is the result of computeFaceNormals (which returns nothing), not a triangle. –  Josh Petrie Feb 10 '11 at 23:19
    
it is pseudocode : ) you're right in real code i have also "return this", sorry i've edited! –  nkint Feb 10 '11 at 23:42
add comment

3 Answers

up vote 4 down vote accepted

"Best" is pretty subjective -- it's going to involve weighing what you need out of the algorithm versus it's inputs, runtime complexity and other properties.

That said, both your approach and the linked FlipCode approach are reasonable in terms of producing usable results (you could quite simply copy your 'face normals' to each vertex, if you are not sharing actual vertex instances between triangles, which I'm unclear on from your code). Other techniques include weighting the contribution of each face normal by the size of the angle made with each face shared by the vertex.

You are correct in that the FlipCode approach appears suboptimal as written, but it could just be poorly specified: it's a little unclear whether or not it intends to suggest the second loop traverse all faces in the model, versus the handful of faces that share the vertex in question. If you have the adjacency information to reduce the search space of the second loop, it becomes less of a concern. Of course you may not have that adjacency information -- this is sort of what I mean by considering what inputs you have available to your algorithm.

If you don't just want to copy the face normal into the vertices, or you are sharing vertices and don't want to split them, you could:

foreach vertex:
   set vertex normal to (0,0,0)

foreach triangle:
   foreach vertex on that triangle:
      set vertex normal = normalize( vertex normal + face normal )

This assumes that each triangle is actually referencing each vertex rather than storing a copy of it -- I don't know what language you're using so I don't know if that's the case or not.

share|improve this answer
    
sorry english is not my first lang so mayebe i've explained ina bad way what i want.. i don't have yet vertex normals! i've edited my answer a bit, hope now i more clear –  nkint Feb 10 '11 at 23:51
    
It's okay, I understood you didn't have vertex normals. The pseudocode I provided will compute them for you by first setting each vertex's normal to (0,0,0) and then summing up the face normals for each face the vertex touches (and re-normalizing, of course). –  Josh Petrie Feb 11 '11 at 0:15
4  
You shouldn't normalize normals in this way. You should normalize after all summations in another foreach. If there is for example 10 triangles with the same normal, but last is with different (result normal should be almost equal to normal from 10 triangles), then you will have this, when summing the last one: set vertex nromal = normalize((1,0,0)+(0,0,1)) and that is (0.5,0,0.5), which is wrong. I hope that I haven't confused you. –  zacharmarz Feb 11 '11 at 8:22
add comment

Josh Petrie has right. If you want to compute vertex normals, you should weight triangle contribution by angle. But you can use naive solution and just sum all normals from all faces around vertex.

So you just compute all face normals and normalize them. Then set all vertex normals to zero. Then for each face (triangle) add its normal to all of its vertices. Then normalize all vertex normals. And it's done.

It's not too correct but it could be enough.

And your face normal calculation above - it's correct but you should aware, which side normal heads. It could head up or down. It depends on cross product - AxB is not the same as BxA - it gives you opposite vector.

share|improve this answer
    
Good point regarding the cross product. –  Josh Petrie Feb 11 '11 at 0:42
add comment

Let us assume that we have a cube made from 6 rectangles. We already know that the vertex normal for a cube is not the normalized sum of the connection faces because of the sharp edge. If you build a map of vertex value and it's different vertex normals for a cube you end up with 3 normals for each vertex.

Keeping the above point in mind this is how I calculate vertex normals(I have tested it and am using it).

class Face{
    uint vert_indices[3];
    vec3 surface_normal;
    vec3 vertex_normal[3];
}

Each face keep track of the vertex normals to use since two faces may share a vertex does not mean the vertex normal will be the same for each face.

Let us assume we are trying to calculate the vertex normal for vert when rendering face2.

vert is shared by face0,face1,face2,face3 and face4. All the above face are neighbours in order and face0 and face4 connect to form a loop.

The vertex normal for vert is the sum of all the connected neighbour chain to face2 normalized. The chain stops if the angle between two neighboured faces is more that 0.8 radians(angle == arccos(crossProduct(faceA.surface_normal, faceB.surface_normal))).

if the angle between face0 and face1 is more than 0.8 radian and the angle between face3 and face4 is more than 0.8 radian than the vertex normal for vert when rendering face2 is normalize(surfnormal1+surfnormal2+surfnormal3).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.