Hi! I'm currently working on my 3d engine, and I'm in need of a fast polygon triangulation algorithm. What's the fastest one if I'm mainly (but not exclusively) working with convex polygons? And do you have any links to an explanation of the given algorithm? Edit: Ok.. I seem to have been a bit unclear, so I'll try to be as clear as possible. What I'm wondering about is the following; [A] Which general purpose algorithms are there for triangulating a simple (convex or concave) polygon and what are their complexity? I've found Ear Cutting, Delaunay and Seidel's Algorithm. I'd prefer that it doesn't generate any new vertices but it's not critical (for instance if it increases visual quality). Which of the given algorithms are fastest when working on primarily (but not exclusively) convex polygons with few vertices? [C] Do you know of which triangulation algorithms different games use? Thanks! [Edited by - pim on July 29, 2005 7:00:23 AM]

A nieve approach would be to, assuming convex polygons, and ordered in some way (CW or CCW) create a triangle fan. Pivot off of the first point.

If you want to hand simple, concave polygons, perhaps it would suffice to choose the most central vertex (closest to the average of the vertex's points) as the pivotal point. It seems in theory (and visually) this would work under most circumstances (w/o complex polygons, anyway)

Let me know if that's good enough for what you're doing (I'm curious) or if you wanted some long, complex formula.

-Michael g.

For convex just do a triangle fan, e.g.:

 1|-------------------|6  |                   |  |                   |  |                   | 2\                   /5   \                 /    \               /     \             /    3 \-----------/4

Choose any vertex (labed with numbers) as your pivot point, then shoot out rays to all the other, non-adjacent vertices.

For example, if you chose vertex 3, shoot rays to vertices 5, 6, and 1, each ray creating a triangle. Do not shoot rays to the adjacent vertices, in this case being 2 and 4.

HTH,
nilkn

EDIT: Sorry, I wrote 'concave' instead of 'convex'.

Another way to make sure it does the best it can with concave polygons is (assuming there's only one point really making it concave, it'll always work well, otherwise, well, you can do some more complex logic, anyway)
Keep track of the slope (or angle, but slope's quicker to calculate) from vertex(n) to vertex(n+1) if the "angle" or "slope" shows the next point makes the polygon concave, then the current point is the culprit. Choose that as the inital point for the triangle fan.

If you want to make it more robust, you could break it up into multiple triangle fans (one for each offending point) but then you'd have to figure out how you want to arrange the tris so they join.

Once it gets that tricky though, I personally would start looking at some 3rd party library/solution.

-Michael g.

ps. I think nilkn and I were saying the same thing: he's got ascii art though ;-)

Well.. there are some different ways to triangulate a convex polygon (zigzag, fan, subdivide++) but I need a way that works with concave polys as well!

As I understand it the method for concave polygons is similar in a way. Basically what you have to do is clip off triangles one at a time but make sure the inside of the triangle is entirely within the polygons, e.g.:

A ______________ B  \     C      /   \    /\    /    \  /  \  /     \/    \/     D      E

In this example you could clip off ACB, BCE or ADC, but not ADE or BED which is why you have to check your set of points does not create a triangle which includes parts outside the original polygon. The same rule for no. of triangles required applies for concave as convex polygons (i.e. no. of points minus 2).

As for fastest algorithm: I did some digging on this a while ago. I think the simplest/fastest algorithm involves projecting the polygon onto a plane (that is since it's already planar transform onto XY, XZ or YZ), sorting the points along one of the axes and walking along the edges from one end to the other. It involves something like tracking the spans inside the polygon in the Y direction when scanning in the X direction, if you see what I mean.

That algorithm is O(n lg n) because of the sort stage. However if you're only working with small numbers of points (I'm not sure exactly how small but 10 or so I'd think would be small enough), the O(n^2) method is probably best. That simply involves picking an edge and looping through all other vertices until you find one that can complete an acceptable triangle (i.e. the triangle contains no other points).

Apparently O(n lg lg n) and even O(n) are possible but these are probably much more complicated and never going to be worth it for almost any conceivable situation.

Quote:Original post by pim
I'm currently working on my 3d engine, and I'm in need of a fast polygon triangulation algorithm. What's the fastest one if I'm mainly (but not exclusively) working with convex polygons? And do you have any links to an explanation of the given algorithm?

Does it need to be general-purpose? Otherwise EOR-filling is pretty neat.

Basically only the horizontal outlines of the polygons are drawn by XORing the polygon's color onto the framebuffer. When all polygons has been "drawn" the filled scene is generated by walking through the framebuffer line-by-line and XORing the pixels in each successive scanline with the ones in the previously generated one.

Obviously you can only have solid polygons and overddraw is tricky. But it's blazingly fast =)

The above post was mine. Damn firefox won't stay logged in..

edit: Bah.. Scratch that, the original request was for triangulation and not rasterization.
It's past 3 around here so maybe I should just get some sleep?

Hmm... noone has really answered the question, so I'll try to be a bit more clear (edited the original post with the new info!)

Well, the O(n^2) algorithm I described above is ear clipping as far as I know. I can only find one page on Seidel's algorithm and it's not particularly clear to me. As for Delaunay triangulation I've never found anything on how it can be used to triagulate polygons.

Anyway my thoughts on the other questions are as follows: if almost all your polygons are convex the fastest way to do this it going to be to check if a polygon is convex first because that can be done easily in O(n) time. If it is convex then use either the fan or strip decomposition. Otherwise revert to either of the other algorithms. Which one is best depends as I said before on the number of vertices you're looking at - for small numbers (~10 or so I'd think although this is a total guess) ear clipping is simpler to implement and I expect just as fast as any other method.

As for generating new vertices: if my understanding of the floating point error issues involved is correct it makes no difference which triangulation you use as long as the points on the edges are exactly the same. This was the reason behind GLQuake's GL_KEEPTJUNCTIONS console variable because if two parallel edges are merged into one this can cause numerical precision errors which can lead to small cracks. But as I said as long as the vertices along two connected edges are exactly the same, no crack should appear. Therefore I don't see any reason for generating new vertices, although some triangulations may be better than others for culling purposes.