Jump to content
  • Advertisement
Sign in to follow this  
Daniel Protopopov

Segment subtraction

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

Hi there, What I am trying to do is a cut-down version of polygon outline CSG. For the polygon below (square) I have its vertices laid out in counter-clockwise direction. When I want to "carve" a certain section out of it (designated as red area), I need to re-generate polygon vertices taking into the account newly created carve-in segments (designated by curve Start->End). Original polygon vertices have their index in the array specified next to them. What do you think is the most optimal solution for "embedding" new curve vertices into polygon vertices list? I have tried standard List<T> Insert, but in case where Start > End (from end of polygon vertices list onto the beginning) this doesn't work. I also thought of implementing circular list so that vertices overbound will be clamped. Red region signifies vertices on polygon list that must not end up in modified list, start and end are points where incision occurs and ends up. The 1-4 numbers inside polygon indicate possible case scenarios, and this is where I am unsure what to do - do each case (8 total) separately, or try to figure out an algorithm for them all. This is possible since all cases share the same information, but I just cannot nail it down yet.

Share this post


Link to post
Share on other sites
Advertisement
What's your algorithm for deciding whether to retain the inside or the outside of the area? That is, what tells you that case 3 is not different than case 4? Is it always the case that one and only one vertex is "cut out?"

Assuming it's always that case that one/only-one vertex is to be removed, reverse the order of the Start-End array if End is on a line-segment that is not the "next" CCW line-segment starting from segment list[1]-list[0]; that is, after locating the insertion point for Start in the list, End must be on the next segment or the test fails. This test includes case 4 where the line-segments "wrap" to the beginning of the list. Then you can use a single algorithm to erase old and insert new.

Before the above test, list.push_back(list[0]) and push_back(list[1]) before that test, making the list "circular" and case 4 is not "special." When testing is done, pop the last 2 elements before you insert the new array.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!