Boolean operations for 2d areas

I have used a library called gpc to do thisin the past: http://www.cs.man.ac.uk/~toby/alan/software/gpc.html

Doing Booleans robustly is a challenge... There is a technique called snap-rounding (look up a paper on this subject by John Hobby) that can enable extremely robust 2D Boolean operations on polygonal shapes. The snap-rounding approach doesn't make the code cleaner and in fact probably makes it less so (more ugly), but it can make it more robust.

Another approach, which can be very robust and also very clean/intuitive is using an implicit surface approach. The idea is to rasterize the geometry into an image. For a simple union of shapes, it would look like:

1) Clear image to black
2) Render all 2D shapes as pure white into the image (ideally with edge or full image antialiasing)
3) Render all holes as pure black, again with antialiasing
4) Run a marching cubes algorithm (rather, the 2D equivalent) on the image to extract isosurfaces/contours between black and white. The resulting isosurfaces/contours are the boundary of your Boolean result.

That approach is elegant and intuitive and the code can be pretty clean...especially if you use a GPU and render-to-texture to build the image. One issue is that it won't exactly capture your original shape, e.g., your original shapes can become larger or smaller by approximately one pixel....higher resolution images result in a better capture of the exact input shapes.

There is a link of interest, which is a bit advanced and focused on 3D:

Implicit Surface Polygonization

Hope this helps!

What about merging BSP trees? It's what I tried when I had to do CSG and worked out fairly cleanly and with enough robustness for my purposes.
But then I'm in no way an expert on this kind of thing..

I don't like the BSP tree approach because (depending on inputs) it introduces edge splits that aren't strictly needed. If you had a need to perform a series of operations, e.g., working with more than 2 objects, you tend to get a bloat of unneeded edges/vertices. Now, you could add a pass in between to combine colinear split edges that were not marked by another edge, but that is a bit of messiness.

alvaro:

ok, seems great.

How good is its performance? Im planning a vector based worms like game, and this would be used to erase chunks of dirt from the ground when hit by projectiles etc.

Is it fast enough? (I didnt see any performance benchmarks on the site)

grhodes_at_work:

yeah, ive been thinking about that... especially since im already rendering the geometry on the gpu it might be a good idee. But a more mathematical approch would be nicer.

I will however need the extracted new shape back on the cpu, so calculating it on the gpu and transferring it back to the cpu would cause terrible performance, right?

implicit:

yeah, i should look into thoose bsp trees, but i havent found a good resource on this method.

//Emil

As far as GPU<->CPU performance is concerned...depends on what you need. Of course you do want to minimize communication between GPU and CPU if you want to do stuff interactively. I don't know if that is your case.

In terms of 2D Booleans with BSP trees, Dave Eberly has an implementation of 2D set operations/Booleans based on BSP trees that you can download (Boolean2D Sample @ GeometricTools.com).

[Edited by - grhodes_at_work on June 5, 2008 1:43:09 PM]

Quote:

Original post by cannonicus alvaro: ok, seems great. How good is its performance? Im planning a vector based worms like game, and this would be used to erase chunks of dirt from the ground when hit by projectiles etc. Is it fast enough? (I didnt see any performance benchmarks on the site)

It was fast enough for me. I wasn't using it very heavily, and my profiler didn't show it as a bottleneck, so I didn't spend any time measuring its performance.

The Wikipedia page on GPC links to this page, which contains a comparison of several polygon clippers, including GPC. Notice however that page belongs to the website for one of the non-free competitors, so take the results with a grain of salt.