I came up with an algorithm to do this a while ago. First off, I''ll assume you have all your verteces arranged in either clockwise or counterclockwise order.

Now, this is how my idea worked. At the first vertex (A), iterate through the other verteces (B). Test segment AB to see if it will ever exit the polygon by testing it against each of the edges. If it doesn''t exit, then split the polygon into two polygons along this segment. Recurse on each of these two polygons (which may be concave). Stop recursion when the current polygon has three verteces.

Basically, you stop at the first possible split, and recurse on the two halves.

Now, there''s a limited number of possible splits, and just making a nested loop for all verteces A with all verteces B is inefficient. After all, if there are n verteces, there aren''t n² possible splits. There are _nC₂-(n-1) possibilities (since AB is the same as BA, and you don''t want existing edges of the polygon). So keep that in mind.

The only trouble with that algo is that you could split along an edge that is outside the polygon. For example:




In this case AB is external to the polygon and you must exclude it from consideration.

By the way, is there a better way to preserve spacing than the source tags?

[edited by - bob_the_third on September 29, 2002 6:33:05 PM]

quote:

---

Original post by eldee
the inside angle of segments v4-v5 and v5-v6 is appx 185ish degrees,
the inside angle of segments v5-v6 and v6-v7 is around 120ish degrees.

---

That's your mistake. You should not compare v5-v6 to v6-v7, but rather v1-v2 to v2-v6. This angle would be negative (counter-clockwise).

bob_the_third, your example does not work (BTW, what you're looking for is the tags):<br><pre><br>v1---v2 v5------|<br>| | | |<br>| v3-----v4 |<br>| |<br>| |<br>|-------------------|<br> </pre> <br>1. Start at v1.<br>2. Go to v2.<br>3. Try v3. Angle between v1-v2 and v2-v3 > 0, so go to v3<br>4. Try v4. Angle between v2-v3 and v3-v4 < 0.<br>5. Try v5. Same problem. The angle between v2-v3 and <b>v3 </b> -v5 is -135, so it is rejected. v6 and v7 are also rejected.<br>6. Go to v8, then v1.<br><br>I just realized that I have been using 180 degrees in my example, but it makes more sense to speak of a negative angle between the two vectors (they are counter-clockwise). Again, this can be determined by<br>v1.x * v2.y - v1.y * v2.x < 0 if clockwise<br>v1.x * v2.y - v1.y * v2.x > 0 if counter-clockwise<br><br>The > and < may be reversed. I'm not sure.<br><br>I'm getting tired of re-explaining this over and over. I <i>may </i> be wrong, but until someone points it out in a clear manner, I'm not going to repeat the same things ad nauseum.<br><br>Cédric<br><br><SPAN CLASS=editedby>[edited by - cedricl &#111;n September 29, 2002 9:47:15 PM]</SPAN><br><br><SPAN CLASS=editedby>[edited by - cedricl &#111;n September 29, 2002 9:49:04 PM]</SPAN>

cedricl: Actually I was referring to TerranFury's algorithm; sorry, should have made that more clear...

BWT thanks for the code tags.

[edited by - bob_the_third on September 29, 2002 9:54:10 PM]

quote:

---

Original post by bob_the_third
cedricl: Actually I was referring to TerranFury''s algorithm; sorry, should have made that more clear...

---

Your complaint was so similar to eldee''s, that I didn''t give it a second thought.

quote:

---

Now, this is how my idea worked. At the first vertex (A), iterate through the other verteces (B). Test segment AB to see if it will ever exit the polygon by testing it against each of the edges. If it doesn''t exit, then split the polygon into two polygons along this segment. Recurse on each of these two polygons (which may be concave). Stop recursion when the current polygon has three verteces.

---

That''s BSP in a nutshell!

Your only mistake is the determination of the split-plane. Like bob pointed out, there could be segements that don''t intersect any other edges but are still external. What you have to do assign a normal to your segment. If any of your points between the endpoints of the segment are on the wrong side of the line, then the segment either passes outside the polygon or cuts an edge. Determining which side of the normal is "wrong" depends on how you create your normal, and which points you intend to see - the "points between the endpoints of the segment" can go either way.

If you need a picture, I''ll provide you one. I use the exact same algorithm for my polygon subdivider, so I know it works (at least for the dozen or so cases I''ve checked )

Found this at Gamasutra. Haven''t read it yet, but it looks like what you''re looking for.

Crispy

The process of breaking a complex polygon into a collection of convex polygons is a form of "tesselation," which basically means to subdivide a geometry into a collection of simpler geometries of the same type.

The OpenGL utility library (GLU, not glut) has built-in functions for tesselating concave polygons, the gluTess* functions. You could use this code without having to write your own.

But, there is a simple algorithm, based on a plane sweep, that subdivides the polygon into triangles and trapezoids (quadrilaterals with the top and bottom edge parallel). When a trapezoid is encountered, it is just split into two triangles. I think this is what GLU implements. I did a quick web search and didn''t find a good link, but I''ve seen it somewhere.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

yeah, i ran accross the sweep plane theory in my
research... i even found a library that will do it
for you and spit it out into tri-strips, but they
dont come out right for some reason...

i''ve been messing with gluTesselation lately in fact,
but i''ve had some problems with the callbacks and
adding vertices dynamically... im going to play with it
a bit more, then i''ll post my results.

-eldee
;another space monkey;
[ Forced Evolution Studios ]

''In C we had to code our own bugs. In C++ we can inherit them.''