Triangulation between polygons on different planes

Question

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

Sergiosergipe

I don't understand what you want to achieve. Can you explain more clearly? With illustrations? What is your source data? What do you want to end up with? Can you add examples? Thanks :) – Eggshell

I have a series of contours (or polygons) created from a font. I also have another series of contours created from the first set as its outline at a specified offset. I want to create 3d models from these and use the outline as a beveled edge. However, the glu tesselator I usually use fails if all the contours are not on the same plane. – Sergiosergipe

In fact, I would have a solution if I could triangulate my polygons by forcing the tesselator not to create any triangle that has all of its three vertices on the same polygon. – Sergiosergipe

If you're interested in the mesh rather than the method, you can use tools such as Blender. Have you looked at openmesh.org, meshlab.sourceforge.net and github.com/vladimir-ch/umeshu? – Paling

Answer 1

You are saying that you have a triangulation method that works in 2D. Fine. Put both of your contours on the same plane z = 0, do the 2D triangulation, then set z coordinate of the vertices of the outer contour to the value you need. As you said, move the outer contour to the parallel plane.

Why this approach doesn't suit you?

Yes, you may end up with some horizontal triangles, which have all three vertices with the same z coordinate. If you used a "true" 3D triangulation you also may end up with same horizontal triangles. It all depends on the shape of the contour and algorithm.

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

Find a horizontal triangle. Two of its edges would belong to either original inner or original outer contour. The third edge would "short-circuit" the vertices of the original contour. Find another triangle that has the same edge as the "third" edge described above. The pair of these triangles form a rhombus. There are only two ways to triangulate the rhombus. The one that you've got is not acceptable, so just re-triangulate the rhombus in a different way.

It is hard to explain this without drawings.

Britanybritches

I think I understand you perfectly. I thought about correcting the 'wrong' triangles but I did not come up with what you just suggested. I will definitely think about it because this looks to be a very good solution! – Sergiosergipe

It looks to be a little bit more complicated than this. I get more than a single 'false' triangles, so cleaning up requires more than creating alternative triangles from a rhombus. Still I think this is the way to go, so unless someone has an even better idea, I think the bounty should be yours. – Sergiosergipe

Well, yes, after initial triangulation you may end up with many false/flat/horizontal triangles that are adjacent to each other. It just means that your second pass should run several times. Each time you run the "fixing" process it would fix one flat triangle. If it can't find any triangle to fix, stop the loop. Also, you need to look for not just a flat triangle, but such flat triangle that has at least one vertex belonging to outer contour and at least one vertex belonging to inner contour. If all vertices of a flat triangle belong to the same contour, you can't fix it (yet, at this pass). – Britanybritches

I did what you suggested and all of my triangles are correct. The only problem is that since the glu tesselator makes no effort to avoid triangles with long sides and narrow angles, I end up with a few hard edges instead of a smooth looking surface. These edges are usually created when quite a few triangles (>3) share the same vertex. Do you maybe have a method to get rid of these? – Sergiosergipe

I don't know if there is a method to make surface look smooth. If your original contour has sharp angle, you are likely to have there a sharp edge in 3D. You can try various heuristics, but it is trial and error. For example, you can have a preprocessing stage. After initial triangulation, still while in 2D, look through the generated triangles. Find the longest and narrowest (e.g. compare perimeter vs area, or min angle of triangle), try to change it using same rhombus approach and check if the result is "better". Repeat until nothing can be improved. – Britanybritches

Totally different heuristic approach is to smooth original 2D contours before making any triangulation. If there is a "sharp" corner on the contour, replace it with smooth approximation with several vertices. – Britanybritches

Thanks Vladimir, it looks quite good now. I make eight passes of going through the pair of faces with two common vertices to find those that could be made better by using the other, shorter diagonal. – Sergiosergipe

@aronsatie, I'm glad my idea was useful for you. – Britanybritches

Answer 2

IMO when you have moved the outer polygon you can try a delaunay triangulation in 3d for example with circumspheres. Cgal can do 3d triangulation.

Rockyrococo

Do you know of any smaller and simpler ones? I would prefer to avoid big libraries for a single task. – Sergiosergipe

@aronsatie:No,but you can try an algorithm, for example a bowyer-watson with circumspheres. In fact its the cgal algorithm. – Rockyrococo

Thanks, I will take a look. I was hoping for a simpler solution, since my contours are not random series of points. I want to triangulate between the original polygons and their modified versions calculated as offsets. The problem is only 3D because I move the offset to another plane that is parallel to the original. – Sergiosergipe

Answer 3

If I understand what you're asking correctly, it sounds like you're trying to do what's sometimes called an extrusion, like this
.
There are a number of font libraries that can do what you'd like for OpenGL. While the information on this page is somewhat dated, I've heard good things about GLTT.

If you want to do it yourself, you might get away with just a simple triangle strip connecting the two contours (assuming they're connected [in the mathematical graph sense]), and may not need the tessellator (aside from creating the first contour).

Let's say the "inner" contour is the one emitted from the tessellator, and you record its perimeter vertices. Then as you say, create the "outer" contour (the one that you want to offset) by translating each inner vertex by some offset (perhaps using normal [orthogonal to the tangent line] at the vertex, or whatever) in the same plane, and then add the extrusion depth. If you keep the same general topology (i.e., same number of vertices and same connectivity information for each vertex), then you can just "stitch" that set of contours into a single triangle strip. Depending on the effect you're looking for, you may need to add additional vertices to the outer contour to make it more aesthetically pleasing. That's no real problem, other than it makes the triangle strip connecting the contours a bit more complicated.

Brotherinlaw

I already have the vertices of both the original and the offset. The offset is a little more complicated than that, so the number of points are different. Stitching them together is also not trivial although at the moment that is what I am trying to do. I still have problems at sharp turns. – Sergiosergipe