splitting a concave polygon into convex ones

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

Recommended Posts

I'm trying to get the "vector method" working for 3D polygons. For now, instead of projection I'm calculating the edge's plane to do the intersections, but I'm not getting correct results. Since it seems to be surprisingly difficult to find a decent resource on this for 3D cases I'm having some trouble understanding the theory behind it. I'll start with a piece of code I mocked up:

 //points is a linked list of vertices. the only bit of importance is that TVecList::point stores the vertex position TVecList* points; TVecList* p0 = points; TVecList* p1 = p0->next; TVecList* p2 = p1->next; IVector3D vPolyNormal = VecNormalize(VecCrossProduct(p1->point - p0->point, p2->point - p1->point)); iNumSplittingEdges = 0; //for all edge pairs while(p0) [indent=1]{
 [indent=1]//wrap around for the last edge - need to include the first edge with the last one
 [indent=1]if(!p1) p1 = points;
 [indent=1]if(!p2) p2 = points;
 [indent=1]IVector3D vEdge0 = p1->point - p0->point;
 [indent=1]IVector3D vEdge1 = p2->point - p1->point;
 [indent=1]IVector3D vCross = VecCrossProduct(vEdge1, vEdge0);
 [indent=1]//create a ray from edge 0 (p1 is the point where the edges meet)
 [indent=1]IVector3D vRayOrigin = p1->point;
 [indent=1]IVector3D vRayDirection = VecNormalize(vEdge0); [indent=1]//literature says I should test for vCross.z as negative. I'm assuming that's because every single explanation I've seen uses 2D polygons that lie on the XY plane. [indent=1]//I'm getting around this temporarily by using a polygon that lies on the XZ plane and as such modified the test to vCross.y [indent=1]if(vCross.y < 0) // <- UHOH? [indent=2]{ [indent=2]TVecList* vs0 = points; [indent=2]TVecList* vs1 = vs0->next; [indent=2]//intersect the offending edge with every other edge in the polygon [indent=2]while(vs0) [indent=3]{ [indent=3]if(!vs1) vs1 = points; [indent=3]//skip the edges being tested [indent=3]if(vs0 == p0 || vs0 == p1 || vs0 == p2) { vs0 = vs0->next; vs1 = vs1->next; continue; } [indent=3]if(vs1 == p0 || vs1 == p1 || vs1 == p2) { vs0 = vs0->next; vs1 = vs1->next; continue; } [indent=3]//calculate this edge's plane from the edge itself an the polygon's normal [indent=3]IVector3D vEdge = VecNormalize(vs1->point - vs0->point); [indent=3]IVector3D vEdgePlaneNormal = VecCrossProduct(vPolyNormal, vEdge); [indent=3]IMath::IPlane3D edgePlane; [indent=3]edgePlane.CalcPlane(vs0->point, vEdgePlaneNormal); [indent=3]//calculate the distance of the ray origin to the plane [indent=3]TReal t = -(VecDotProduct(vRayOrigin, edgePlane.GetNormal()) + edgePlane.GetD()) / VecDotProduct(vRayDirection, edgePlane.GetNormal()); [indent=3]//and the intersection point on the plane [indent=3]IVector3D vIntersection = vRayOrigin + vRayDirection * t; [indent=3]//test if the intersection point lies on the line segment (its distance from the center of the segment is less than half the length of the segment)... [indent=3]IVector3D vEdgeHalf = (vs1->point - vs0->point) * TReal(.5); [indent=3]IVector3D vEdgeCenter = vEdgeHalf + vs0->point; [indent=3]TReal fEdgeHalfLength = vEdgeHalf.Magnitude() * 0.5f; [indent=3]//... then the edge should be split [indent=3]if(VecDistance(vEdgeCenter, vIntersection) < fEdgeHalfLength) [indent=4]{ [indent=4]//simply mark out the edges for now. When I get this working, vIntersection will be inserted in the vertex list between vs0 and vs1 [indent=4]vSplitEdge0[iNumSplittingEdges] = vRayOrigin - vRayDirection * 20; [indent=4]vSplitEdge1[iNumSplittingEdges] = vRayOrigin + vRayDirection * 20; [indent=4]vSplitPoints[iNumSplittingEdges] = vIntersection; [indent=4]iNumSplittingEdges++; [indent=4]//this would look somewhat different if an insertion took place here [indent=4]vs0 = vs0->next; [indent=4]vs1 = vs1->next; [indent=4]} [indent=3]else [indent=4]{ [indent=4]//take next edge if there's no inersection [indent=4]vs0 = vs0->next; [indent=4]vs1 = vs1->next; [indent=4]} [indent=3]} [indent=2]} [indent=1]//take the next edge pair [indent=1]p0 = p0->next; [indent=1]p1 = p1->next; [indent=1]p2 = p2->next; [indent=1]} 

Theory question: why is the Y component of the cross product negative? As in why does it work like that? Is there any other way I can replace this test for 3D cases or am I stuck with projection (which implies data duplication)?
Practice question: why doesn't the above code work some of the time?
Approach question: what would be the best way to split up truly nasty non-complex (but concave) polygons (see attached example)? Let's say I have a polygon shaped like a snail, winding towards the center. Using the approach I'm aiming for, with just 22 edges the polygon would be split into roughly 20 convex areas. Would I be better off storing these separately and then merging the triangulation (which is what I'm going for here) results or would it be easier to devise a method that would take the vertices added by the above code (if it were working) and run some form of an iterative scheme on the enhanced polygon?

I've attached a sample case and how I THINK the result should look like: edges in black, split planes in red and resulting convex polygons in random pastels. Since I'm not even sure whether that's the expected result, I'm finding it that much harder to debug my code.

Share on other sites

Approach question: what would be the best way to split up truly nasty non-complex (but concave) polygons (see attached example)?
I'd be really lazy: drop it in triangle. Bonus feature: holes are supported.

Why your approach does not work? I cannot say but what I remember is my triangolator was like 500 lines if memory serves. I could only speculate on the problem.
Consider your example image. See the break near the center, the one involving {white, blue, yellow} areas. My triangolator would wrongly consider the top pink area "outside" te polygon because of a failed "outside check" against the center oblique edge.
I later added more logic to handle that. It was an interesting and very formative experience on the intricacies of polygonal processing... having been there, I suggest to use a proper triangulation library.

Not only triangle can produce triangulations at various quality levels but it's also quite fast. I think it's about 100X faster than mine!

Share on other sites

[quote name='irreversible' timestamp='1328207294' post='4908806']
Approach question: what would be the best way to split up truly nasty non-complex (but concave) polygons (see attached example)?
I'd be really lazy: drop it in triangle. Bonus feature: holes are supported.

Why your approach does not work? I cannot say but what I remember is my triangolator was like 500 lines if memory serves. I could only speculate on the problem.
Consider your example image. See the break near the center, the one involving {white, blue, yellow} areas. My triangolator would wrongly consider the top pink area "outside" te polygon because of a failed "outside check" against the center oblique edge.
I later added more logic to handle that. It was an interesting and very formative experience on the intricacies of polygonal processing... having been there, I suggest to use a proper triangulation library.

Not only triangle can produce triangulations at various quality levels but it's also quite fast. I think it's about 100X faster than mine!
[/quote]

Thanks for the suggestion! I'll have a look at Triangle (I like the fact that it's free), however I was basing my original research on some apparently not too well guided googling (as I wasn't aware of the terms involved). Since then I've been reading up on ear clipping and plane sweeping and at the end of the day I've been finding myself strongly in favor of a simple implementation of ear clipping. The reasons are quite simple - I have at most a few tens of corners for the faces I need to triangulate so fancy solutions give little benehit; even though I won't be needing polygons with holes, ear clipping supports them; it's very easy to implement (at O(n^2) speed) and even though free alternatives are out there, there won't be any sort of license issues now or in the future; in addition, ear clipping actually generates a pretty minimal (and predictable) set of triangles without adding new vertices, which is precisely what I want.

Krohm - would you mind talking a bit about the project you're working on? You've been replying to my queries with pretty relevant personal insight and it's sparked some curiosity

1. 1
2. 2
3. 3
4. 4
Rutin
13
5. 5

• 13
• 10
• 9
• 9
• 11
• Forum Statistics

• Total Topics
633692
• Total Posts
3013355
×