PDA

View Full Version : Convert Convex Polygon to Triangle Strips



amb0027
01-20-2014, 05:57 PM
Hey guys, I want to start off saying I've googled and searched but I'm not sure I've found the best ways to do what I want to do. I currently have a project to model the floor plan of a building. I have drawn the floor plan using a line loop (the long tedious way of plotting each corner vertex). However, I know there has to be a better way to do this. There is also a pretty good arc on one side of the building and I'm unsure of the best way to do this. Currently, as I said, I'm using a line loop, and someone suggested using triangles instead (so that I could fill the polygon with color), but I'm unsure of the best way to do this? I'll try to include a link to a picture. Thanks in advance for the help.

I tried to include a picture, but was denied due to my post count. Sorry! If anyone knows a way to post a picture for you guys just let me know!

chbaker0
01-20-2014, 06:45 PM
I'd think the easiest way to do this would be to use a triangle fan, instead of a triangle strip. Then, you could just calculate the center of the polygon by "averaging" all of the vertices and create the fan starting at the center and going around through all of the corner vertices.

Of course, this relies on the polygon being convex; this won't always work with a concave polygon as the "center" may end up being outside of the polygon. If you need a more general solution, you should do some Google searches on triangulating polygons.

Here is the Wikipedia page on polygon triangulation (http://en.wikipedia.org/wiki/Polygon_triangulation) if you need some general methods.

CarstenT
01-21-2014, 09:40 AM
Are you working in 2D ? .. The general solution in 3D is probably intollerably messy to deal with.
Doing the general solution in 2D is a fun geometry-problem ;o) but usually pops up when your bussy doing something else.
If you'r in a hurry then draw triangles between the concave points to spot all the convex polygons that should be no problem.
chbaker0's link probably shows you a way to find out if a point is concave. I considered to eliminate those points by building the convex triangles that lies on each/or one side, load an array with the coherent points that is still left to be drawn and iterate forward that way. I never implemented it and don't really know if it works.

there are quite a few geometry libraries
http://www.personal.kent.edu/~rmuhamma/Compgeometry/compgeom.html
maybe the problem has a solution somewhere in those?

mhagain
01-21-2014, 12:46 PM
I'd think the easiest way to do this would be to use a triangle fan, instead of a triangle strip. Then, you could just calculate the center of the polygon by "averaging" all of the vertices and create the fan starting at the center and going around through all of the corner vertices.

Of course, this relies on the polygon being convex; this won't always work with a concave polygon as the "center" may end up being outside of the polygon. If you need a more general solution, you should do some Google searches on triangulating polygons.

Here is the Wikipedia page on polygon triangulation (http://en.wikipedia.org/wiki/Polygon_triangulation) if you need some general methods.

For an arbitrary convex polygon your don't even need to take the midpoint; just start at one of the points and go around it in order to create a triangle fan.

For multiple convex polygons the best way is to use indexed triangles rather than strips or fans, unless you're specifically targetting hardware where you know that indexing gives lower performance.

CarstenT
01-23-2014, 09:13 AM
oh ..
forgot all about the GLU library. It's got a tesselator ..
It doesn't look like something for newbees (like me)

http://www.songho.ca/opengl/gl_tessellation.html

chbaker0
01-23-2014, 10:10 AM
It's probably not a good idea to use it though, as GLU is pretty outdated. It depends on the fixed function pipeline; it's not the same as the tesselation we hear about nowadays, which occurs on the GPU.

tonyo_au
01-27-2014, 05:55 PM
The source code for tesselation in GLU is available at mesa (http://www.mesa3d.org/) if you want to remove the fixed function code