Triangulation between polygons on different planes

Question

I would like to triangulate between two sets of polygons. One set is always inside another; in fact, external polygons are created as offsets from the original set. Triangulation would be easy if they were in the same plane, but I would like to add depth by moving the outer polygon to a parallel but different plane. The usual triangulation method that I use (glu tesselator) does not work. Is there an alternative that will be?

Answer 1

You say that you have a triangulation method that works in 2D. Good. Place both of your contours on the same plane z = 0 , perform two-dimensional triangulation, then set the z coordinate of the vertices of the outer contour to the desired value. As you said, move the outer contour into a parallel plane.

Why is this approach not suitable for you?

Yes, you may encounter some horizontal triangles that have all three vertices with the same z coordinate. If you used "true" three-dimensional triangulation, you can also end up in the same horizontal triangle. It all depends on the shape of the circuit and the algorithm.

If it is unacceptable to have such horizontal triangles, you can add a second pass to try to eliminate them:

Find the horizontal triangle. Its two edges will belong to either the original inner or the original outer contour. The third edge "shorted" the vertices of the original contour. Find another triangle that has the same edge as the "third" edge described above. A pair of these triangles forms a rhombus. There are only two ways to triangulate a rhombus. The one you have is unacceptable, so just reorient the rhombus differently.

It is hard to explain this without pictures.

Answer 2

IMO, when you move the outer polygon, you can try delaunay triangulation in 3d, for example with circumspheres. Cgal can perform 3d triangulation.

Answer 3

If I understand what you are asking correctly, it looks like you are trying to do what is sometimes called extrusion, for example, this .
There are many font libraries that can do what you would like to use for OpenGL. Although the information on this page is somewhat outdated, I heard good things about GLTT .

If you want to do it yourself, you may just have a simple triangular strip connecting two contours (assuming that they are connected [in the sense of a mathematical graph]), and you may not need a tessellator (except for creating the first contour).

Let's say that the “inner” contour is the one that is emitted from the tessellator, and you record its perimeter vertices. Then, as you say, create an “outer” path (the one you want to compensate for) by moving each inner vertex to some offset (possibly using a regular [orthogonal tangent line] at the vertex or whatever) in the same plane, and then add extrusion depth. If you keep the same general topology (i.e., the same number of vertices and one relationship information for each vertex), you can simply “stitch” this set of contours into one strip of the triangle. Depending on the effect you are looking for, you may need to add extra vertices to the outer contour to make it more aesthetic. This is not a real problem, except that the triangular strip connecting the contours is a little more complicated.