Jump to content
  • Advertisement
Sign in to follow this  
ruysch

Polygon list to triangle list

This topic is 3627 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

Say I have a list vertices making out a list of polygons.
// vertices in mesh
vector <vec3> vertices;
// size (i.e vertices) making out current polygon.
vector <unsigned int> sizes;

Is there a algorithm which can convert the polygons into triangles ?

Share this post


Link to post
Share on other sites
Advertisement
I'm not entirely clear on how your sizes vector is working, but this is a general approach to turn an n-sided convex polygon into a set of triangles:

i) Pick a vertex, let's call that the apex.
ii) From the apex, advance to the next vertex on the polygon (this is the 'current vertex').

1) Add the apex as the first of 3 vertices for a new triangle.
2) Add the current vertex as the second vertex for the triangle.
3) Advance the current vertex and add it as the third vertex for the triangle.
4) While there are still vertices between the current vertex and the apex, goto 1.

Share this post


Link to post
Share on other sites
If the polygons are convex, pretty much anything will work. For instance, you can pick any two non-contiguous vertices and use them to divide the polygon into two smaller polygons, which you then recursively decompose into triangles.

If they are not convex, it gets much, much harder. I recommend using the algorithm above, but now you have to check that the segment between the two vertices actually doesn't intersect any other sides. In tricky polygons, this might take some searching.

The other alternative is to use an algorithm similar to scan-line rasterization to decompose the polygon into trapezoids, which you can then make out of two triangles each. I think this is what you get when you ask the GPC library for output as a list of triangles.

Share this post


Link to post
Share on other sites
Okay, the first guy confused me the second guy left something out.

I just posted something about this today, but it was in a different part of the forum. You can find it at

http://www.gamedev.net/community/forums/topic.asp?topic_id=501359

Take the time to read it.

Share this post


Link to post
Share on other sites
The algorithm posted by dmatter actually produces a fan of triangles (EDIT: not sharing vertices!) from a polygon, and works (as he has stated) for convex polygons. For both convex and concave polygons algorithms like ear-clipping and Seidel's algorithm are used often. If holes play a role, then the extended ear-clipping or modified Seidel algorithm are to be used. Other (but normally even more complex) algorithms exist as well. I don't know which of those algorithms will work well on non-planar and even self-intersecting polygons, but such things are normally too extraordinary to play a role. AFAIK such polygons are first divided into planar, non-intersecting polygons before one of the named algorithms is applied. However, Google knows sources where ear-clipping and/or Seidel's are described, e.g. Dave's geometrictools.com.

[Edited by - haegarr on July 16, 2008 8:25:46 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by dmatter
i) Pick a vertex, let's call that the apex.


If apex isnt updated then wont you end up with a a triangle fan ?
Sorry if I am picking on details - just want to be certain on how the algorithm works.

Share this post


Link to post
Share on other sites
Quote:
Original post by ruysch
Quote:
Original post by dmatter
i) Pick a vertex, let's call that the apex.


If apex isnt updated then wont you end up with a a triangle fan ?
Sorry if I am picking on details - just want to be certain on how the algorithm works.

It produces a triangle list that, when seen as a composited surface, looks like a triangle fan. This is because step 1) is applied for each single triangle, because step 4) branches back to step 1).

Share this post


Link to post
Share on other sites
Quote:
Original post by ruysch
So we agree upon it will give a triangle fan ...

I'm not sure if we understand us, so let me clarify. A real triangle fan has a vertex index list for the first 3 triangles like
1 2 3 4 5 6 ...
while the algorithm presented generates indices like
1 2 3 1 3 4 1 4 5 1 5 6 ...
and hence really produces single triangles, but each of them has the same geometry as the corresponding triangle in the real fan. In this example, the "apex" has the index 1, so you can see the 1 being repeated, once for each triangle.

Share this post


Link to post
Share on other sites
A triangle fan is a list of triangles where each triangle starts a the 'apex',
OpenGL version 1.1 has a very nice definition :

a href="http://www.opengl.org/documentation/specs/version1.1/glspec1.1/img25.gif">OpenGL triangle fan is figure at the outmost right


The algorithm outlined above is only able to produce triangle fans, which is nice (I aint complaining) we just have to be very certain we are speaking in the same terms else its difficult to answer/ask questions.

I really dont like that the algorithm isnt able to produce anything else than fans, Triangle strip would be nicer... or individual triangles, i.e no sharing-reuse of apex all over the triangle mesh.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!