7
$\begingroup$

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: earth cartesian

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...):

polar earth

(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:

enter image description here

And this is how triangles would be formed:

enter image description here

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.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Nathan Reed Nov 5 '16 at 15:29
  • $\begingroup$ It sounds a little bit like ROAM, but hard to tell... youtube.com/watch?v=PPjWW8uPp3o $\endgroup$ – Alan Wolfe Nov 9 '16 at 23:21
  • $\begingroup$ @NathanReed Added further explanations and pictures. $\endgroup$ – Andreas Nov 12 '16 at 10:55
  • $\begingroup$ @AlanWolfe I´d say the algorithm is in the same ball park with a few differences. Good find :-) $\endgroup$ – Andreas Nov 12 '16 at 11:02
4
$\begingroup$

Instead of subdividing until reaching certain edge length on screen, you should look into GPU Gems 2 article "Adaptive Tessellation of Subdivision Surfaces with Displacement Mapping" by Michael Bunnell. It uses edge flatness test to adaptively tessellate the geometry which results in better quality with the same number of triangles.

With your current adaptive tessellation strategy you'll end up splitting flat surfaces, which unnecessarily increases your triangle count. This is particularly bad on GPU's as it increases quad overdraw for the resulting microtriangles.

About your question for the name of your subdivision scheme, I don't think there is specific name for it but it just falls under more generic "adaptive tessellation".

$\endgroup$
  • $\begingroup$ Yeah, it was a bit hasty answer, added some edits $\endgroup$ – JarkkoL Nov 7 '16 at 4:42
  • $\begingroup$ You've given so many detailed answers recently that I guessed you had more you could say on this one. +1 $\endgroup$ – trichoplax Nov 7 '16 at 11:16
  • $\begingroup$ "With your current adaptive tessellation strategy you'll end up splitting flat surfaces, which unnecessarily increases your triangle count." - It´s exactly the opposite. I guess you (and many others) don´t know what a polar coordinate system is and how it warps cartesian 3D-models depending on its projected location. I do agree with you that the threshold can be more elaborate than length on display but deriving it becomes difficult. And besides my target GPU does not have tesselation capability. I´ll update my answer with more info on later occation. $\endgroup$ – Andreas Nov 12 '16 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.