How to calculate the normals of a box?

Question

I am trying to create an algorithm that calculate the normals of a model/ mesh. People have been telling me to use the cross products between the two vectors which at first seem like a good idea until I discovered that it might not always work. For instance just imagine a box with its front face sitting at the origin and its back face down the Z axis. Here is an image:

I do apologize for bad hand writing but that shouldn't be of any significance. As you can see,I cross v and u to get the normal pointing toward the positive z axis. However, If I use that same calculation to calculate the normal for the back face then obviously the normal will then be a vector directing inside the shape. The result is that I have inaccurate normals to calculate the brightness of a light. I want the normal to be facing away from the model at all time.

I know there gotta be a better way to calculate the normal but I don't know what it is. Can anyone suggests to me another algorithm to calculate the normal that would get rid of this problem? If not then there has to be a way to check whether or not a normal is facing inside the object / model. If so then can you suggests it in the answer and where I would find an explanation about it because I would love to have an intuition on how these methodologies work.

Answer 1

Most software packages obey a configurable cyclic ordering for triangle indices - clockwise or anti-clockwise. Thus all meshes they export have self-consistent ordering, and as long as your program uses the same convention, you should have nothing to worry about.

---

Having said that, I imagine you want to know what to do in the hypothetical (?) situation where the index ordering is inconsistent.

One method we could use is ray-intersection. The important theorem is that a ray with its source outside the mesh will only intersect the mesh an even number of times, and if inside, odd.

To do this, we can do the following:

• Calculate the "normal" using the cross product as above (and normalize it) => N
• Take any point on the triangle (preferably the midpoint)
• Increment this point along the normal by some small epsilon value (depends on your floating point format and size of model - I'd say 1e-4 for single and 1e-8 for double precision) => P
• Intersect this ray [dir = N, src = P] with all triangles in the mesh (a good algorithm for this would be Möller–Trumbore)
• If the number of intersections is even, then the ray started from outside of the mesh; this means that the normal points outwards from the mesh (because you incremented its source from a point on the surface). - and of course, vice versa.

---

Minor (-ish ?) digression: a naive approach to the above, of looping through all triangles in the mesh, would be O(n) - and hence the whole procedure would have quadratic time complexity. This is perfectly fine for very small meshes of ~20 triangles (e.g. a box), but not ideal for any larger!

You can use spatial sub-division techniques to lower the cost of this intersection step:

• K-D trees / Octrees: These require O(n log n) (for the best algorithm, that is - see Ingo Wald's paper) to construct, but intersections are guaranteed to be O(log n) if done properly. The overall complexity would then be O(n log n), which is pretty much the best you can get
• Grid: This simply partitions the search space and triangles into smaller boxes. Construction is O(n) and much more memory-efficient. Intersection time is still O(n), but the constant factor is much smaller than that of the naive approach.