Archived

This topic is now archived and is closed to further replies.

Polygon tessellation for the braindead =)

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

ok I''ve been looking around for a while now for an artical on polygon tessellation.... I''ve found a fair amount on the subject but heh it seems to be beyond me =), but I know the subject can''t be that far out there... I''m not trying to down polys with holes or concaved or some other strange shape... I just want to be able to break down quads/pentagons/octagons/ect down in to triangle... doesn''t need to be fast... I''m just looking for something simple to implemnt for now...

Share this post


Link to post
Share on other sites
If you want to tesselate convex polygons, it really is pretty simple: the tesselated structure is a triangle fan. You start at a vertex, and then walk through the polygon contour by creating triangles in the way of a fan.

Concave tesselation is substancially more involved though.

Share this post


Link to post
Share on other sites
The triangle fan approach works well for convex polygons. However, there is an alternate approach that creates the same number of triangles (but in a strip instead of a fan) and tends to texture/vertex-shade better. This is the approach used in Quake III.

This code may be busted, but you should get the idea:

    
// Assumes that Polygon.verteces[numVerts] is an ordered

// (clockwise or counterclockwise, whatever you use)

// array of verteces.


int i1 = 0,
i2 = numVerts-1;

while(i1 < i2)
{
TriangleStrip.AddVertex(Polygon.verteces[i1];
TriangleStrip.AddVertex(Polygon.verteces[i2];

++i1;
--i2;
}


[edited by - TerranFury on June 3, 2002 5:09:29 PM]

Share this post


Link to post
Share on other sites
Now on to the topic of concave polygons. Assuming your verteces are in the correct order AND the polygon is not self-intersecting, there's a relatively simple algorithm you can use.

Again, assume that the polygon is represented as an ordered array of verteces.

Choose a vertex A. For each other vertex B, test to see if line AB remains inside the polygon at all times (eg: it doesn't intersect any edges). If the line does remain inside, split the polygon into two polygons. Recurse on each one until only triangles remain.

[edited by - TerranFury on June 3, 2002 5:44:00 PM]

Share this post


Link to post
Share on other sites