OpenGL calculating correct normals given list of points

Question

For the problem I have: a) An ordered list of points b) A list of points that make up each polygon

For example

point1 = (1, 2, 2)
point2 = (1, 2, 3)
point3 = (1, 3, 3)

polygon1 = [ point1, point2, point3 ]

=> polygon1 is a triangle which could be part of the outside of the model.

I need to calculate the correct normals for lighting in OpenGL.

I know that I can calculate vectors on the plane from the points given, and cross-product to get A normal to the plane, but OpenGL requires the normals to be pointing in the correct direction (ie outward).

The process needs to be automated because I have LOTS of polygons.

If I pick two vectors on the plane I can't tell how I can be sure the normal I have calculated points in the correct direction for lighting (ie is on the outside of the model.)

I figured I could add the calculated normal to a point on the plane and see if its further from the origin to see if its correct, but the model is quite complex and some normals may need to point towards the origin(ish)

If it helps, it turns out all the polygons are triangles (dont see how it helps though, should be able to abstract for any polygon)

If there's a triangle floating in space by itself, what's the "correct" side? Seems to me the only right answer is two sided lighting. — Ani
Can't you simply use the front face ordering (clockwise or counterclockwise) to define the order you make the cross product? — user1118321
@ananthonline - its not a triangle floating in space, i've got lots of polygons which all connect to form a nice closed object — Blue42
@user1118 not quite sure what you mean - are you thinking the order the points are given correspond to which face is on the outside? Its in VTK format so I guess i'll consult their documentation — Blue42
Ah, I misunderstood. @datenwolf's answer seems like the correct one to me then. — Ani

datenwolf datenwolf · Accepted Answer · 2012-02-15T21:44:21

Your problem is usually called "manifold surface orientation". In the case of closed manifolds it can solved unambigously, in the case of open, but orientable manifolds you must manually decide which side of the patch is "outside".

However there are some manifolds, like Klein bottles or Moebius strips for which the problem cannot be solved (note that if you cycle two times over the Moebius strip you actually can orient the surface, if you assume that you can see only one side).

Okay, regarding your triangle soup problem: This is usually solved using so called half edges. I.e. for every triangle you build the list of vertices that make them up. This gives you 3 directed half-edges for each triangle. Now for each pair of vertices v1, v2 you make a list of edges connecting them (you should use the vertex ID pair as key into a hash map, where key((v1, v2)) == key((v2, v1)), most simply done by sorting them). For each such pair of vertices you should find either only one half edge, or two antiparallel half-edges. If there are more than 2 half-edges then the surface is not orientable. If the half-edges are parallel, the orientation of the triangle that belongs to one of the half-edges must be flipped. Choose one starting triangle, and build a tree of connected triangles, then of those triangles to the next and so on. In the tree store for each triangle a flip counter. If the counter is odd all triangles further down the tree are to be considered flipped as well. No triangle must have it's explicit flip counter being incremented beyond 1. Cumulative flipcounts of merging branches must be even at the merge point.

OpenGL calculating correct normals given list of points

2 Answers