How to do fast & smooth shading?


Does anybody know how you can quickly calculate vertex normals of a triangle strip
(average of all connected triangles to that vertex), without searching through all nodes to verify which triangles are conected?

This is a very slow process. So I was wondering if there was an easier way to do this.



Easy. Use a vertex structure that includes for each vertex, a list of faces it is a part of. That way you only have to do the initial search one time at most (as long as the mesh topology remains constant).

The problem is if I have for example 100.000 vertexes with aprox. 100.000 triangles. This means 100.000 x 100.000 calculations, which is too much.

If it is a triangle strip I know that each vertex is connected to at least the previous and the next triangle. However, this vertex can be also connected to a triangle at the end of the list.

I was hoping there was a quicker way to organize data.

If it is just a simple triangle strip (with no degenerate triangles or edges) then it is possible to figure out which face(s) a vertex is adjacent to, with a simple formula.

Remember that the first vertex is only a member of the first face, the last vertex is only a member of the last triangle. The second vertex is a member of the first two faces, the second to the last vertex is a member of the last two faces and every other vertex is a member of three faces, such that for vertex n, faces (n-2), (n-1), and n are adjacent. (I think at least, I haven’t fully awoken yet. So double check my math.)

[This message has been edited by DFrey (edited 02-11-2001).]

Thanks for the explanation. Sorry for asking stupid questions, I just need badly to optimise the code. It is too slow.

Does the geometry for your strips change? If it doesn’t, you should just have to calculate the normals one time when you load the vertices.

The geometry can have more than one triangle strip and I have in the file the normal of each triangle. As DFrey said it is easy to calculate vertex normals for one strip and calculation is fast since it is a simple algorithm. However, for more than one strip that share vertexes the calculation might have to be like:

for each node,
for each trangle strip,
search all triangles with same node,
calculate vertex normal by average of all connected normals.

I don’t really know. This process is to slow when you have about 500.000 nodes.

[This message has been edited by billy (edited 02-13-2001).]

Perhpaps you’d be interested in the algorithm I gave there:

It has its limitations, but as far as I understand, that is what you are looking for… It works with or without strips…