# polygon triangulation

This topic is 5060 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am looking for some simple code that deals with triangulation of convex/concave/polygon with holes. I would like to simulate the stuff done by GLU's gluNewTess for my simulation environment. although, I find a lot for 2D, I am not able to find a neat one for 3D polygon triangulation. Also, I am not able to compare the existing ones. Could some one throw light onto my needs. Appreciate your help. ~ Matt

##### Share on other sites
You can very easily use the 2D methods for 3D as well. You just map the 3D polygon to a 2D polygon, by cubic mapping or so, and then you triangulate that 2D polygon. For each vertex, you also have to save the original 3D coordinates, or an index into the original polygon, and then you can create 3D triangles of the same vertices that the 2D triangles use.

##### Share on other sites

I found several methods from -

http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html#triangulation

but am not able to pick the right one!!, also some vote for delaunay triangulation.

Would appreciate a fitting reply that compares the above methods and the easy one that I could think off to implement simulating the gluNewTess function call.

also could someone give a link that explains the basic idea of how to convert 3D polygons to 2D so that I could use any 2D triangulation algorithm

~ Matt

##### Share on other sites
Update!! --

I tried the implementation of Seidel's algorithm by Atul & dinesh manocha. But the input to this algo. is specified as polygon contours and I've only a bunch of vertices for the polygon and would like to get the triangles of the same.

I am confused, whether to proceed with other algorithms that handle concave & polygons with holes or can I change their implementation to accept just a bunch of vertices.

Thanks,

Matt

##### Share on other sites
One note. If all you have is vertices, and you have not prescribed certain edges as being the boundary, then there is NO unique concave polygon that contains the points. There is, however, a unique minimal convex hull, which would be found by using a standard Delaunay triangulation of a 2D point cloud. The most efficient technique here would probably be the divide and conquer algorithm described in detail by Guibas and Stolfi, though efficient incremental and sweepline algorithms also exist. The incremental algorithm is easiest.

If you desire a concave boundary, then you will have to either specify the boundary edges explicitly (which would give you a polygon that can feed Siedel's algorithm), or come up with a set of rules for deciding which edges will become the boundary. I'm not aware of any specific rule set for reconstructing concave objects from point clouds, but you might look at Hughes Hoppe's web page at research.microsoft.com. He's done work on reconstruction of concave meshes (not polygons per say) in 3D.

##### Share on other sites

I looked at triangulation by EAR CLIPPING and finds it simple reading the paper on a first go!!....hope it would do triangulation for convex/concave polygons & polygons with holes. I would appreciate your thoughts on it. Since I don't worry about the time and just concerned about a simple implementation, I assume that I could start with this. Any specific limitations that I should concern about ?.

Also, I would appreciate your help in referring me to a site that teaches me the basic math in converting polygons having 3d vertices (x,y & z) to 2d vertices (x,y or y,z or z,x). Forgot my high-school math ?

Regarding delaunay, standard delaunay wouldn't meet my purpose and I guess I would need to look onto constrained delaunay triangulation.

Also, I am unclear why do I need to specify edges rather gluNewTess (OpenGL's tesselation) takes only vertices.

thanks,

Matt

##### Share on other sites
Hey Matt,

The ear-clipping method is a good way to map a concave polygon into so-called "monotone" pieces that can individually be triangulated using a convex triangulation method, then stitch them back together. This is certainly appropriate.

You are correct that a true Delaunay triangulation would not work. Unfortunately, constrained Delaunay is FAR from easy to implement. I would steer you away from trying to implement that; however, you may find Jonathan Shewchuk's code, Triangle, is available as source code for free and supports constrained Delaunay using the divide and conquer technique. You still need to *know* which edges are boundary here, as those edges become the constraints.

As for gluNewTess.. I think you're just not interpreting the input correctly. You specify a series of vertices, but those vertices are in a certain order that explicitly defines the boundary edges (each vertex in the list creates an edge back to the prevous vertex). Probably, gluNewTess expects the vertices to be listed in an order that defines the polygon counterclockwise.

Note that if gluNewTess can deal with 3D polygons, internally it actually does a 2D triangulation. It does this by computing the normal vector to the polygon, creating a coordinate system with 2 axes in that plane, then projects the points into the plane. Once the points are in the plane, it treats the vertices as 2D, and uses a 2D approach. My prior post (the one lost due to timeout---GRRRR, bad gamedev!) went into this process in detail. gluNewTess *may* be able to deal with nonplanar polygons (any "polygon" in 3D with more than 3 vertices might not actually be perfectly planar, and in fact might be far from planar). BUT, nonplanar polygons can cause difficulties depending on how the projection plane for the 2D mapping is chosen.

I am not going to have time to show you all the math for mapping a 3D polygon into 2D. It is unfortunate my prior post was lost, since I did give all the math you need. But, here is a summary:

1) Choose one vertex of the polygon to be the local origin, O = (O.x, O.y, O.z).

2) Create a unit vector from O to the next vertex along an edge connected to O. Call the unit vector X = (X.x, X.y, X.z). This will be the direction of the X axis in the 2D plane in which you will be doing the triangulation

3) Find a unit normal vector to the polygon by taking X and any other edge that is not parallel to X and doing a cross product. (See articles here at gamedev or do a forum search to learn how to do a cross product). Call the normal Z = (Z.x, Z.y, Z.z).

4) Do another cross product, Y = Z cross X, and normalize it for good measure. (We need to make sure it has length 1.0).

5) Now, X and Y are the two directions that define the plane in which you will do the triangulation.

6) Form a 3 x 3 rotation matrix:

    [X.x X.y X.z]R = |Y.x Y.y Y.z|    [Z.x Z.y Z.z]

This is the so-called "world to object" rotation matrix, which maps vectors in world space into the coordinate system of interest, e.g., it converts vectors in world space into the coordinate system given by X, Y, and Z. The transpose of R is the object to world rotation matrix, which takes vectors in the object's space and maps them to the world. (The tranpose rules is only true if R contains no scaling factors...this one does not, since we made sure X, Y, and Z all had length 1.0).

7) Now, map all your polygon vertices:

V_mapped = R * (V_world_space - O)

8) Now that all your vertices are mapped, your V_mapped vectors *are* the 2D vertices you need! Just drop the Z coordinate!

So, except for telling you how to do the matrix and vector math in the formula for V_mapped, that is all the math to do the 3D to 2D conversion! Articles here on gamedev should give you all the matrix & vector math you need to carry it out!

I think gluNewTess probably doesn't do generalized ear-clipping. I think it uses a plane sweep to divide the triangle into trapezoids, which are easily triangulated. Similar to ear-clipping, and easy enough to implement.

Posting now. Here goes nothing!

##### Share on other sites
I was looking @ Ear-clipping and unsure whether it handles polygons with holes; I was told that it would but donno how would I check the same. I also looked @ Triangle, as told by you, it takes edges and also would like me to specify holes too.

May be for my spec. to triangulate concave/convex/polygons, I assume I could go ahead with ear-clipping methods.

Is there any specific reason that I shouldn't use ear-clipping algorithm for my purpose than Triangle as proposed by jonathan.

~ Matt

##### Share on other sites
you could try using a 2D BSP idea.
Here is the algorithm I thought of:

1) Project polygon into 2D.
use it's normal vector and one point to define 2 mutually perpendicualar vectors. Take the cross procuct to form a basis or frame. These vectors are the rows of it's matrix - invert it and multiply each point to transform to the origin.

Rx Ry Rz 0^-1
Ux Uy Uz 0 =
Lx Ly Lz 0
Px Py Pz 1

Rx Ux Lx 0
Ry Uy Ly 0
Rz Uz Lz 0
-P.R -P.U -p.L 1

2) Take each line and form planes that are perpendiclar to the plane of the polygon.

3) Form a BSP tree using these planes partitioning the edges as required. Maintain the original edges too.

4) Now the polygon should be triangulated - reduce the number of excess edges by sliding the new verts to the original verts.
( this part is probably quite easy, but I am not sure about the implementation ).

There are some good links on Erich Haines' homepage
http://www.acm.org/tog/editors/erich/

spelling error
[/edit]

##### Share on other sites
What is wrong with ear clipping? If you just read the paper, you see that they are handling an example with wholes/convex polygon, and it's a relatively easy method. That bsp tree method is just overkill imho, and it will result in much more triangles than necessary. You can probaly reduce it after it though, but why would you do that if there's something as easy as the ear-clipping method.

• 12
• 40
• 15
• 10
• 23