chamsy

06-25-2005, 08:07 PM

Hi,

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

Thanks a lot,

Chamal.

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

Thanks a lot,

Chamal.

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

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.

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 ) );

}

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.

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.