Troublesome Triangle

I ran into a problem computing a polygon normal using Newell’s method as described in Christer Ericson’s excellent book Real-Time Collision Detection. In this case the polygon happens to a be a triangle that is close to the origin. So I would guess that Newell’s method would yield a great result. However, this is not true. I only get 2 digits of accuracy in single precision.

Here is the triangle:
p1 = (0.331916571f, 0.382771939f, -0.465963870f)
p2 = (0.378853887f, -0.246981591f, -0.440359056f)
p3 = (0.331879079f, 0.382861078f, -0.465974003f)

I knew I was getting a bad normal because some of my convex hull code was failing. So I decided to analyze the problem. First of all, this triangle has edge lengths of around 0.6320, 0.6321, and 1e-4. So this is a sliver and it is well known that slivers can be numerically challenging.

I computed a baseline normal using doubles. Doubles yielded the following normal vector (truncated to 6 digits):
normal_doubles = (0.206384 -0.0243884 -0.978167).
I got the same result computing the normal in many different ways. So I am confident that this is accurate.

Then I computed the normal many several different ways using single precision:
– 1 way using Newell’s method as stated in Christer’s book
– 3 ways using edge cross products
– 3 ways using Newell’s method on the triangle shifted to each vertex (suggested by Christer)
– 1 way using Newell’s method on the triangle shifted to the centroid

Here is the code:

And here are the results:
0.205007 -0.0244907 -0.978454
0.206384 -0.0243884 -0.978167
0.206417 -0.0243837 -0.97816
0.206384 -0.0243884 -0.978167
0.206377 -0.0243887 -0.978168
0.206453 -0.024386 -0.978153
0.206315 -0.0243899 -0.978182
0.206375 -0.0243882 -0.978169

Exact:
0.206384 -0.0243884 -0.978167

As you can see, Newell’s method is only giving 2 digits of accuracy. Every other method is giving close to 4 digits of accuracy or more. The best result is from n1 and n2. Both of these are cross products that include the shortest edge. This agrees with Gino van den Bergen’s comments on Twitter.

Shifting the triangle origin to one of the vertices or the centroid all improve Newell’s method substantially. I’m a little disappointed that Newell’s method is still not as good as _any_ of the cross products. The price of generality?

Bottom line:
1. Shift a vertex to the origin before applying Newell’s method.
2. Cross products can produce triangle normals that are superior to the results of Newell’s method.
3. Switching to doubles can solve numerical problems, but it is better to first understand the underlying issue.