# polygon triangulation

## Recommended Posts

taurean    122
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
quasar3d    814
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
taurean    122

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
taurean    122
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
grhodes_at_work    1385
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
taurean    122

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
grhodes_at_work    1385
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
taurean    122
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
quasar3d    814
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.

##### Share on other sites
taurean    122

www.magic-software.com/Documentation/ TriangulationByEarClipping.pdf

i don't see it discussing about handling holes. Could u send me the link of the paper that shows info. about handling holes with examples.

Also, I don't see in the code about how it handles holes.

~ Matt

##### Share on other sites
grhodes_at_work    1385
Here's a post by David Eberly (Magic Software guy) that discusses triangulation with holes:

Triangulation of Polygon with Holes

##### Share on other sites
Quote:
 Original post by quasar3dThat bsp tree method is just overkill imho, and it will result in much more triangles than necessary.

but the Delaunay triangulation usually creates extra triangles
too. The BSP method is the fastest method since you no longer need to think about the algorithms + you don't need to worry about ear clipping.

Anyway, I've thought of another possible procedure:
1. take each point of each hole and connect an edge to
the nearest point not on the hole.
2. create polygons from the remaining 2D subspaces and ear
clip them.

Please let me know if there is a flaw in this algorithm somewhere.

##### Share on other sites
Guest Anonymous Poster
I think I am probably mistaking what you mean with a polygon with holes. I thought you just ment a concave polygon, as the C example you gave is a concave polygon. But in the link ghrodes posted, they mention both concave polygons and polygons with holes, so I guess they are something different then. So what's exactly the difference between a concave polygon and a polygon with wholes? Probably an O shape or so?

##### Share on other sites
taurean    122
Could you help me out understanding the below piece of code from ear-clipping algo.::

What does this line check?

if ( EPSILON > (((Bx-Ax)*(Cy-Ay)) - ((By-Ay)*(Cx-Ax))) ) return (0);

Ax,Ay,Bx,By,Cx,Cy being the three vertices of a triangle that is formed out of the polygon.

thanks,

Matt

##### Share on other sites
Premandrake    175
That line looks as though it is checking if the point C is on the "right" of the infinite line formed by AB. So essentially if the angle formed by ABC is < 180 degrees (within tolerance).

Check out this page for an explanation of the 2d vector cross product (which is what is being used here).

##### Share on other sites
taurean    122
thank you for your reply. Thatz an awesome site!! but where do I find a similar explanation for 3D especially

a) find the area of a polygon in 3D;
b) clockwise test for polygons in 3D;
c) convex/concave test ......

~ Matt

##### Share on other sites
taurean    122
if ( EPSILON > (((Bx-Ax)*(Cy-Ay)) - ((By-Ay)*(Cx-Ax))) ) return (0);

Ax,Ay,Bx,By,Cx,Cy being the three vertices of a triangle that is formed out of the polygon.

"That line looks as though it is checking if the point C is on the "right" of the infinite line formed by AB. So essentially if the angle formed by ABC is < 180 degrees (within tolerance)."

Inorder to continue this explanation to 3D, I guess I could check for EPSILON > |cross-product of vectors formed by adjacent sides of the polygon in 3D|.

Because, if the vectors are parallel, their length of cross-product would be 0 as it would be a zero vector.

clarify this!!

~ Matt

##### Share on other sites
grhodes_at_work    1385
Quote:
 Original post by taureanthank you for your reply. Thatz an awesome site!! but where do I find a similar explanation for 3D especially a) find the area of a polygon in 3D;b) clockwise test for polygons in 3D;c) convex/concave test ......Appreciate your input on this.~ Matt

a) See response to your other post on this subject.

b) You just project into a 2D plane and do the 3D->2D projection thing, since in 3D you might be looking at the polygon from either side----in 3D it is both clockwise *and* counterclockwise!

c) Did the ear-clipping articles not discuss this? Well any, a polygon is concave (in the 2D sense) if any interior angle is > 180 degrees.

##### Share on other sites
taurean    122
Quote:
 Original post by grhodes_at_work1) 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 triangulation3) 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!

Well, I understood the above concept of shifting each 3D vertices to 2D vertices. How does this differ from finding the normal of the polygon by taking cross - product of 2 vectors of adjacent sides of polygon; and then with the absolute coefficients of N.x, N.y, N.z; strip the one coefficient from 3d vertices that is greater than the other two to make the 2d set of vertices. (This doesn't involve any rotation or matrix either !! )

??

~ Matt

##### Share on other sites
grhodes_at_work    1385
Quote:
 Original post by taureanWell, I understood the above concept of shifting each 3D vertices to 2D vertices. How does this differ from finding the normal of the polygon by taking cross - product of 2 vectors of adjacent sides of polygon; and then with the absolute coefficients of N.x, N.y, N.z; strip the one coefficient from 3d vertices that is greater than the other two to make the 2d set of vertices. (This doesn't involve any rotation or matrix either !! )~ Matt

What you describe is exactly the same thing. And, actually, you ARE effectively using a rotation matrix, :). You are just doing the steps without formally putting the numbers into a data structure that you call a matrix. But the math is the same and the matrix is hidden in there.

##### Share on other sites
FugueInCPP    184
Hi Taurean -

I just briefly skimmed the replies, so I apologize if this is already been covered, but holes or "islands" as they're usually referred to are very easy to implement in a 2D ear clipping routine. I do not have any experience with true 3D triangulation, but have had a lot of luck using 2D ear clipping.

To carve islands into your shape is really quite straightforward:

1) Determine what order your polygon verts are in (clockwise, anti-clockwise).

2) Reverse the order of your island verts such that they the opposite order of your polygon verts.

3) Find the closest vert on your polygon to the left-most vert on your island shape.

4) Now insert the island verts into your polygon verts "after" the point you found in step 3. Now add the point from step 3 after the island verts (so this point now occurs both before and after the island verts in your polygon shape).

You're done! The ear clipping routine will correctly triangulate around this island shape. You can also chain islands together in this same manner.

Also, for my 2D ear clipper, the only real math I needed was the following two functions:

- Get_Side_Of_Line (): given a point and a line.
- Are_Any_Verts_Inside_Tri (): implemented with barycentric coordinates to decrease numerical roundoff error.

Good luck!

## Create an account

Register a new account