PDA

View Full Version : Convert a polygon into triangles


chamsy
06-25-2005, 08:07 PM
Hi,

Is there any algoritms to convert 3d polygons into triangles.


Thanks a lot,
Chamal.

pzurita
06-25-2005, 08:31 PM
Hi,

Is there any algoritms to convert 3d polygons into triangles.


Thanks a lot,
Chamal.
Yes, you can do Delaunay triangulation.
http://www.ics.uci.edu/~eppstein/gina/delaunay.html
http://mathworld.wolfram.com/DelaunayTriangulation.html

chamsy
06-26-2005, 05:05 AM
Hi pzurita,

It was really helpful thanks a lot.

Chamal.

playmesumch00ns
06-28-2005, 10:38 AM
If you're talking about convertinga polygon with say 6 sides into triangles, it's very easy:


vertex v1, v2, v3;
vector<triangle> newtris;

v1 = polygon.vertices[0];
for ( i=0; i < polygon.sides-2; ++i )
{
v2=polygon.vertices[ i+1 ];
v3=polygon.vertices[ i+2 ];

newtris.push_back( triangle( v0, v1, v2 ) );
}

gga
06-28-2005, 12:30 PM
Triangulation of 3d polygons is a rather unclear term, so you need to be a tad more precise what you are dealing with.

Basically the algorithms to triangulate polygons get more complex as you specify your requirements and the type of input data you may be facing. From simpler to more complex:

1) If you are dealing with a 2d polygon in 3d space that is convex, has no holes and you don't care about the shape of the resulting triangles, you are dealing with the easiest case and you can use playmesumch00ns algorithm.

2) If you are dealing with concave polygons (say a star-shaped polygon), you should be looking into some form of ear clipping algorithm, as playmesumch00ns algorithm will not work.
For a technical description of ear clipping, look at Dave Eberly's explanation at:
http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

3) If you are dealing with polygons with holes, an ear-clipping algorithm can easily be modified to support holes. The idea is that you basically draw a line between a vertex in the hole and a vertex in the polygon (repeat for other holes).

4) Ear clipping algorithms make no guarantees about the triangles. This can lead to triangles that are extremely thin and that do not interpolate normals very easily. Delaunay triangulation adds the property that for each triangle of the triangulation, the circumcircle of that triangle is empty of all the vertices of other triangles. This can arguably give you better shading to the resulting triangles. For a visual example:
http://www.cs.cornell.edu/Info/People/chew/Delaunay.html

5) Finally, a 3d polygon can mean a 2d polygon in 3d space (ie. a polygon where all its vertices lie on a plane) or it can mean a polygon where all its points lie anywhere in 3d space but from a particular view they result in a 2d shape (think: shape of constellations). You usually deal with 2d polygons, so the usual approach in case of a 3d polygon is to project it along an axis so that you end up with a 2d polygon. Once you have a 2d polygon, you deal with it as usual with an ear-clipping or delaunay triangulation.

CGTalk Moderation
06-28-2005, 12:30 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.