topic pretty much says it all... OpenGL wont let me render complex/concave polys, so i need to figure out how to split it up into multiple convex ones. anybody know how to go about doing this? i''ve done some test cases on paper, and the only thing i can come up with is this: if the inside angle of 2 lines is greater than 180 degrees, then the intersecting vertice is ''concave'' and i need to subdivide at this point. my problem now is, where do i subdivide it to ? -eldee ;another space monkey; [ Forced Evolution Studios ]

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

You''re on the right track, but I''m not sure that it''s the best method.

Anyway, you simply try the subsequent vertices until you find one whose angle will be less than 180 degrees. Is that clear?

Cédric

well, that doesnt exactly work either...
because say i have 5 concave vertices in a row

*--*v1             *v6-*|    *           *     ||       *    *         ||______________________| 

using that method, you can tell that the first vert
to have an angle less than 180 here is vert6, and
if i tried to subdivide there i''d cut across the
top of my ''hole''


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

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

You could always solve this recursively using a BSP building method. You start at v1, and using nested loops, iterate each of the points in the polygon list using the big loop, and iterate each point in between in a subloop. If any of the points are "cut off" by any of the lines created in your main loop, then there''s a concavity. You go back to the last line that worked (should be the one before the line that didn''t work), split the polygon along that line, and perform the whole thing again on both remaining polygons. Keep splitting it into smaller and smaller polygons until you are left with a bunch of atomic (convex) polygons.

You can perform a few mock operations on scratch paper to get the feel of it. It''s actually quite nice.

well the thing with bsp''s is that they''re compiled..
this would have to be done in real time, and a nested loop
isnt going to be fast enough.

gluTesselation seems to be a winner though.

quote:

---

Original post by eldee
well, that doesnt exactly work either...
because say i have 5 concave vertices in a row

*--*v1             *v6-*|    *           *     ||       *    *         ||______________________|  

using that method, you can tell that the first vert
to have an angle less than 180 here is vert6, and
if i tried to subdivide there i''d cut across the
top of my ''hole''

---

No. v1-v2 is still convex, so the next vertex should be v9. To make sure that I make myself clear: first polygon = v1, v2, v9, v10, v1. I don''t think that its'' possible to "cut through a hole" when using this method.

Then, you would start at v2, and build polygon v2-v3-v9-v2

v3-v4-v8-v9-v3

v4-v5-v8-v4

v5-v6-v7-v8-v5

Cédric

quote:

---

Original post by cedricl
No. v1-v2 is still convex, so the next vertex should be v9. To make sure that I make myself clear: first polygon = v1, v2, v9, v10, v1. I don''t think that its'' possible to "cut through a hole" when using this method.

Then, you would start at v2, and build polygon v2-v3-v9-v2

v3-v4-v8-v9-v3

v4-v5-v8-v4

v5-v6-v7-v8-v5

Cédric

---

well, yes optimally thats where i would want to subdivide.
but the problem is that i dont know what my polygons are going
to be, or where the vertices will be located. i''m trying to
find an algorithmic way to determine which vertex to subdivide
to.

quote:

---

Anyway, you simply try the subsequent vertices until you find one whose angle will be less than 180 degrees.

---

when doing that, starting at the first concave vertex (v2),
the next sequential vertex that is convex is v6. if you subdivide
at that point, the line of subdivision runs over the top of the
''hole'' that is in the box.

*--*v1       .,==> *v6-*|    *v2 <==''    *v5   ||       *v3  *v4       ||______________________|   

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

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

I've been working on algorithms for this lately. Here are two approaches I've come up with for concave polygon tesselation:

METHOD 1
================================================================
1) Arrange all polygon vertices in descending order on the Y coordinate.
2) Extend infinite horizontal lines through each point.
3) The region formed by the intersection between adjacent horizonatl lines with the polygon edges will always be either a triangle or a quadrilateral.
4) If the region is a quadrilateral, split it arbitrarily into a triangle.

Note that I have left a lot of details out; this is because I haven't worked them out yet myself. Hopefully this will get you started.



METHOD 2
================================================================
Here's the pseudo-code for this algorithm.




An example of insidepoly(p) would be to project a ray horizontally (or in any direction) from p, and count the number of polygon edges it crosses. If the number is even, the point is inside the polygon. Otherwise it's outside the polygon.

The result of this algorithm is an edge list that subdivides the concave polygon into triangles. Some extra work is required to use this edge list and the vertex list to arrive at the triangle lists, but I haven't attempted this part of the problem yet; however I expect it should be fairly simple to do, or at least possible.


NOTE: I used the source tags because without them it killed my indentation.

[edited by - bob_the_third on September 29, 2002 4:22:11 PM]

[edited by - bob_the_third on September 29, 2002 4:46:02 PM]

quote:

---

Original post by eldee
when doing that, starting at the first concave vertex (v2),
the next sequential vertex that is convex is v6. if you subdivide
at that point, the line of subdivision runs over the top of the
''hole'' that is in the box.

*--*v1       .,==> *v6-*|    *v2 <==''    *v5   ||       *v3  *v4       ||______________________|    

---

No. The next vertex should be v9.

All you need is a way to determine if vertices are following are clockwise order or not. You can use the cross product for that. If all the vertices are on the XY plane, you can check the z coordinate. For example, the vectors v1_v2 and v2_v3 are not clockwise, because the sign of the z component of
v1_v2 X v2_v3 is negative. So you try the next vertex. v1_v2 X v2-v4 will also be negative, as will be v2_v5, v2_v6, v2_v7 and v2_v8.

Frankly, I don''t understand why you would think that this method will return v6. What makes v6 different from v5?

Since your polygon is in 3D, you can use the sign of the dot product with the normal (i.e.: (v1_v2 X v2_v3) . N). I don''t if a convex polygon will return positive or negative values, but it should be consistent, so try it to find out.

Cédric

quote:

---

Original post by cedricl
Frankly, I don''t understand why you would think that this method will return v6. What makes v6 different from v5?

---

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.

quote:

---

Since your polygon is in 3D, you can use the sign of the dot product with the normal (i.e.: (v1_v2 X v2_v3) . N). I don''t if a convex polygon will return positive or negative values, but it should be consistent, so try it to find out.
Cédric

---

actually, my polygon isn''t in 3D.


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

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