Cutting polygons

While writing a CSG operations system, I had to write a function which cut one polygon with another. If the polygons are not co-planar this is quite easy, cutting the polygon with the other polygon’s plane.

But if the polygons ARE co-planar the case is much more complicated (Remmember I have to actually cut the polygon into smaller polygon).

Right now I do it that way:
A. Projecting the polygons into the y = 0 plane.
B. Calculating the 2D line equation for every side of the polygons.
C. Calculate the distance of every vertex from the other polygon’s lines.
D. Test the distances in order to know which one of ten possible cases I encountered.
E. Go back to 3D. Now that I know which case I have, I can do a simple Vector-Vector Intersection to find the intersection points. Then I can create the new polygons, because I know which case I have.

Can anyone show me a better way to do this?

I see that no one know how to do it better way…

thanks for helping me.

Doing robust boolean operations (even in 2D) is very nasty. There are so many special cases and degenerate cases that need to be accounted for. If at all possible I would recommend using an existing boolean library rather than trying to write one yourself.

I have a 2D polygon library that does a good job with 2D boolean operations. I don’t have the web address handy, but I can probably dig it up if you want it.

we dealing with 3d here, and most of the work is allready done. what do you mean with degenerating?

I amcurrently doing boolean intersections on 3D bodies - I resolve degeneracies using: http://www.geom.umn.edu/~mucke/GeomDir/sos90.html

Degeneracies are when, for example, a vertex of one triangle falls in the same plane as the other triangle. Basically, they’re just a bunch of special cases that you have to deal with. The Simulation of Simplicity algorithm in the above paper resolves them all before you do any checking… it’s pretty slick.

Chris

Sorry, but that is not my problem. I already handle (it’s quite easy…) the cases when one vertex is on the other polygon’s plane…

I am talking here on the MOST ELEGANT WAY to do the cutting…

[This message has been edited by Quaternion (edited 03-05-2001).]

[This message has been edited by Quaternion (edited 03-05-2001).]

You might consider projecting edge vectors of one polygon onto vectors that are perpendicular to the plane that both polygons are in and the edges of the other polygon.

It might be messy but you could use it to derive intersection points (or non-intersection). It would be a modified separating axis algorithm.
http://www.cs.unc.edu/~geom/OBB/OBBT.html
and also pg. 325 of “Real-Time Rendering”

His paper describes a method of collision detection for bounding boxes that I have used to determine the minimum distance of line segments.

The ideas in his paper would require a lot of modification to be applied to your problem but it may get you thinking about another way of solving it.

ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/obb.ps.gz

[This message has been edited by PeterK (edited 03-05-2001).]

okapota - In his post, he specifically asked about coplanar polygons, that’s why I brought it up.

The really hard part about degeneracies occurs when they are caused by round off error. In these situations a case may appear degenerate when evaluated one way, but non-degenerate when evaluated another way. You have to be very careful and consistent with your calculations. This is where most of the work in practical computational geometry is done (in my opinion). You read a lot of papers where they talk about an algorithm and the first thing they say is something like “asuuming general position…” Which is fine for discussing an algorithm, but won’t go very far for implementing it.

Chennes - yeah, I’ve read that paper and Simulation of Simplicity is a pretty cool approach for a lot of problems, though I’ve never implemented it. The only problem I see with Simulation of Simplicity is that it might remove some degeneracies that you actually want to see. Like I said though, I’ve never implemented it, so I can’t really say much about it.

Quaternion - Have you done a literature search on boolean operations? I’d be surprised if you couldn’t find plenty of detailed descriptions of the algorithm out there, which would explain exactly how they do the cutting. This seems to me like one of those things that has been done enough times that the chances of coming up with the most efficient solution without standing on the shoulders of others are pretty slim.

You said in your first post that it’s quite easy to cut two polygons which are not coplanar by cutting one with the other’s plane. But what do you do if the polygons only partially intersect? What about cases where only one egdge of a polygon lies in the plane of the other polygon. It’s these kinds of degeneracies that make this a really hard problem.

I’m not trying to be discouraging here, I’m just trying to point out potential issues.