# What is this triangle sub-division scheme called?

I have thought of a triangle sub-division for the purpose of smooth triangulation (no popping) over time on the fly. I think it is very likely the scheme is already invented and has a name but I can´t seem to find it.

Sub-division is made on triangle edge basis. For each edge longer than a certain threshold, say 1cm on display (i.e. projected space), the edge get two new points a threshold distance (1cm) away from each other. The edge in between the new points are then complete and need no further sub-division. Up to six new points are thus created from the sub-division, but it could be just one edge making two new points. From the points triangles are formed and the sub-division is performed recursively until all edges are shorter than the threshold.

Creating two points along the edge a threshold apart is significant for the subdivision to be smooth over time. I don´t see Loop or Catmull Clark doing this.

I should probably mention I use this successfully for cartesian meshes in polar projections. Strictly speaking the two points created along an edge may or may not be on the originally projected line.

So what is it called?

## Explanation

So I guess I have to explain a few things about cartesian coordinate systems in polar projections.

A good example of a polar coordinate system is a flat earth. Earth may look like this in a cartesian system with a huge table on top of it:

A polar coordinate system could have the x-axis defined as the angle from earth center to a cartesian coordinate given a plane used to project the earth. The y-axis is then the altitude, either from earth surface or bluntly the distance from earth center. A polar projected version of above image given my description would look like this (with the assumption the earth is spherical, which it is not...):

(please have patience with me not being a great artist.)

As you can see the table is now bent because in the middle it is closer to the earth center than in the edges (exaggerated, I know).

Without sub-division the table would still be flat in the polar view its altitude would be misleading. A point object on top of the table in cartesian coordinates may be below it in the polar view. The triangle sub-division aim to lessens the error until it is "small enough". I measure this by projected length on display because it is cheap and has good correspondence to my quality requirements but other schemes would do just as fine or better depending on the polar properties, e.g. likeliness you are interested in accurate altitude far below the earth surface.

As you may realize the error becomes greater the bigger the object and the closer it is to the polar origin.

Know to some details of the algorithm.

This is a triangle (in cartesian coordinates) with red and green edge being to long in the polar view, i.e. the red is very close the polar origin, the green not so close and the black quite far away:

And this is how triangles would be formed:

Once new points are created their cartesian coordinate is a coordinate along the original edge. The new triangles are fed to the algorithm once more and repeated until the error is small enough. In above image one might suspect the red edge should be partitioned at least one more time.

The point in making two control points is to get edge matching behavior without extra edge information. Splitting two adjacent triangles (or lines for that matter) is guaranteed to have the new points on the exact same location with the exact same information.

Key feature here is that new triangles does not cross the middle of the original triangle as this would otherwise cause too much error correction from one frame to another as the greatest error is in the middle between control points. Points close to the control point will be least corrected and thus give the least amount of correction to make the error small enough. This is crucial for smooth zooming in any of the axes or even movement of the projected objects.

Triangulation layout is stable no matter what edges are too long.

Breadth-first recursion is the better way to go if the sub-division is limited by time or memory as edge matching is guaranteed even for interrupted/partial sub-division.

• Some diagrams or screenshots of what you mean might be helpful. When you say the two new points are a threshold apart, does that mean they aren't evenly spaced along the edge? I don't quite get how that helps with temporal stability. Commented Nov 5, 2016 at 15:29
• It sounds a little bit like ROAM, but hard to tell... youtube.com/watch?v=PPjWW8uPp3o Commented Nov 9, 2016 at 23:21
• @NathanReed Added further explanations and pictures. Commented Nov 12, 2016 at 10:55
• @AlanWolfe I´d say the algorithm is in the same ball park with a few differences. Good find :-) Commented Nov 12, 2016 at 11:02