## The impossibility of a good triangulation of a cone

Tuesday, March 18th, 2014 at 1:54 pm

I hadn’t worked on triangulating surfaces since the first version of machining strategist in 1994, but always thought I could do it better by distributing the triangles in a nice enough manners. It is true that the people who write surface triangulators in engineering CAD packages don’t in general try very hard, but I don’t think many folks realize that there is no right answer.

Suppose we have a smooth surface S, defined by a function from a subset of the plane to real space

```  f: D ------> R3, where D is a subset of R2
representing the set of points within a boundary B defined by:
b: [0,1] ------> R2 where b(0) = b(1)
```

… roughly speaking.

We want to approximate this surface to the tolerance e with a set of connected triangles defined by triplets of points in R3-space:
T = { (p0, p1, p2) }

It would be nice if it had the following properties:

1. For every point p in every triangle, there is a point q in S where |p-q| < e.

2. For every point q S, there is a point p in one of the triangles where |p-q| < e.

3. For every point p on a 1-sided triangle boundary, there is a point q in B where |p-q| < e.

4. For every point q B, there is a point p on a 1-sided triangle boundary where |p-q| < e.

5. There is a smooth continuous homeomorphism from S to the surface set of points in R3 that inside all the triangles that doesn’t move any point by more than e.

6. The orientation of the fold at each 2-sided edge triangle boundary is consistent with the curvature of S in that region.

7. The triangle approximation should depend only on the embedding of S in R3, and not have any relation to the 2D parameter map f.

8. The triangles should be as close to equilateral as possible; there should be no shards.

9. There should be as few triangles as possible to satisfy the tolerance value e.

Admittedly, these conditions aren’t very well specified, and line 5 implies the previous four, but I’m just being a lazy amateur. A professional whose job it was to produce high-quality triangle approximations of engineering surfaces would do it properly, I’m sure.

Who cares about the speed? I wrote a program that flipped and cracked triangles under the following three triangular manifold transforms to gradually change an initial triangulation into something that satisfied the requirements above.

The first snag I hit was that I wanted to that the second transform that moved a vertex into the centre of its surrounding polygon wasn’t going to change the standard rectangular triangulation into the more even hexagonal form.

No matter. The smallest perturbation would shake it away from this initial form so things would quickly spread and crystallize out.

But, here’s the real problem. What’s going to happen with a developable surface, like a cone, which is made up of straight lines?

Clearly, the majority of the triangle boundaries must run along these lines. But at the thin end we need n-sides to approximate the surface to tolerance, but at the fat end we need 2n-sides. At some point there is a transition. And at this transition you will need to make edges that go around the cone. And there is no way to do this without edges that fold outwards and produces a manifold that bounds a non-convex volume.

So, although the cone bounds a purely convex volume, we cannot respect its convexity with a triangulated model without over-triangulating at the thin end.

Usually a CAD model is made up of different surface patches that join together. By default, because no one tries to make the triangulations within the patches interesting, the nasty wrong-folding transitions tend to happen at the joins, and so are mis-characterized as a multi-surface problem, rather than an issue that runs deeper and within the impossibility of defining the perfect answer.