I need an algorithm for triangulating polygons, but there's a catch:

I want to draw arbitrarily shaped polygons, but they don't need to be texture mapped or anything - just paint-filled. The API doesn't matter. The point is, I have a polygon that could be any shape, convex or concave, and it lies flat on a plane, but that plane can be anywhere in 3D space.

The problem is that I also need the vertices of the polygon to be able to move freely, while staying on that plane. If they're moving gradually in real time and I want to draw every frame, what happens if a point changes from being convex to concave or vice versa?

Do I have to reconstruct the whole thing from scratch every time a vertex moves? I know how to do that, but wouldn't it be inefficient and stupid, or is there any possible way around that?

A combination of this and this should probably get the job done.

Or if you want to have a go at writing something yourself you could implement http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

From reviewing the links, I get the impression that neither of you actually read the third and fourth paragraph of my previous post. My question was not how to divide the polygon into triangles, but how to do it in such a way that I don't have to keep doing it over again every time a point moves.

I would start with triangulation every frame.

When in doubt, cobstant framerate techniques are better than variable framerate techniques.

If you might need to triangulate during a frame then you better be able to.

If you can't triangulate every frame, then you can't fully triangulate ANY frame. So you'll need to develop some optimization..

One possibility is local topology validation to re-triangulate only small parts of the polygon during a frame. Which may be harder than just making full triangulation really fast.

Another possibility is breaking up the triangulation work into two phases, and incrementally updating the base info as the shape moves. You would repeat only the 2nd phase every frame.

If you have multiple polygons, you can multithread and process each as a separate task, making effective use of multicore cpus.

As far as the polygon being on a plane in 3d, just calculate the polygon as a 2d shape and use a standard object-to-world space matrix to place it in any location and orientation in 3d space. This part is trivial.

>Another possibility is breaking up the triangulation work into two phases, and incrementally updating the base info as the shape moves. You would repeat only the 2nd phase every frame.

I'm not sure what the 2 phases represent.

>As far as the polygon being on a plane in 3d, just calculate the polygon as a 2d shape and use a standard object-to-world space matrix to place it in any location and orientation in 3d space. This part is trivial.

Actually, it's not that trivial, because for some reason, using matrices always seems to trip me up, and everything ends up in the wrong place, the wrong size and facing the wrong direction, but that's an entirely different issue.

You only have to re-triangulate when any part of it transitions from convex to concave or vice-versa.


L. Spiro

From reviewing the links, I get the impression that neither of you actually read the third and fourth paragraph of my previous post. My question was not how to divide the polygon into triangles, but how to do it in such a way that I don't have to keep doing it over again every time a point moves.

I don't see how you reach that conclusion. You have a problem which is neatly divided into two components: triangulating an arbitrary polygon and and re-triangulating as a response to moving points. I can help with the triangulating part since I looked for something similar a while back (hence the links).
The other component of the problem does not really interest me but it's clear solving the first component is already helpful. At worst you could just triangulate the polygon every frame. Depending on what exactly you want to do that might end up being very sufficient. A good solution would still be to trigger a new triangulation when you detect you need to (Spiro probably gave the right suggestion there). A perfect solution would be to use the already existing triangulation and only modify those bits which need to change. Personally I doubt there is something like that prepared, at least in the free and non-GPL part of the available sources (since those were my constraints when I looked for it).

You dont have to do the 3d work yourself if you dont want to. You can use unity/ue4 or a simple scene manager like my c# simplescene.

http://www.codeproject.com/Articles/798054/SimpleScene-d-scene-manager-in-Csharp-and-OpenTK


If you need some mentoring getting your 2d triangulation into 3d space, hit me up (davidj at gmail)

As for the 2 phases, the idea is to cache some of the triangulation work to avoid redoing it every frame. Just like spiro mentioned only retriangulating when a point changes from concave to convex (though i'm not sure this is sufficient).

However, if there is a case where the whole shape might need to be retriangulated in a frame, it pays to make it fast enough to run every frame.

Any movement of vertices may cause connected triangles to flip around, so you'll have to check for that. Also it may no longer be the most optimal triangulation (slivers etc.).