[FP3] BooleanTools

Topics: Developer Forum
May 12, 2010 at 10:05 AM

I'm trying to use the BooleanTools module to automatically determine the hitbox for a 3D model by projecting the triangles from the model onto the XY plane and then merging them using BooleanTools.Union. Unfortunately, it doesn't seem to work... is the code up-to-date?

May 12, 2010 at 1:03 PM

The boolean tools aren't very stable at the moment, I think there is still a bit of work to be done on them.

If I understand correctly though, I don't think you need boolean tools for what you're doing. Boolean operations can be quite expensive and I think you can do what you're proposing in a much simpler way.

May 12, 2010 at 2:01 PM

How so?

The models I'm using are composed of several parts, and the parts overlap. The parts, projected onto the XY plane, make a jumble of overlapping triangles. For each triangle, I need to add it to an existing polygon (if it intersects with one) or create a new one (if it doesn't), and if it intersects with many polygons, combine them all.

Pretty sure I need a general union operation for this one, but glad to be proved wrong.

May 12, 2010 at 2:58 PM

Hmm, I was wrong, I cant seem to find a way that's simple and good!

The BooleanTools only accept outlines of a shape, not a triangulated shape. Adding each triangle seperately should work in theory, but most likely will probably throw errors when the triangles overlap by a very small distance (floats are only so accurate). This is even more likely to happen because you're not sure where the triangles will end up after projection.

Your next best bet is probably to project all the triangles into a list of points, then trace the outline of these points using a Hull Algorithm.

The Vertices class in Farseer 2 has a Convex Hull algorithm, but you probably want a Concave Hull. This is normally very complicated, but because everything is in triangles it might be doable in your case. (read http://stackoverflow.com/questions/83593/is-there-an-efficient-algorithm-to-generate-a-2d-concave-hull and http://stackoverflow.com/questions/1014293/2d-outline-algorithm-for-projected-3d-mesh)

Anyway, my way will *definitely* be difficult and a lot of work, but your way only *might* not work, so give it a go! :D

If you want a good library for boolean operations in the meantime, try GPC, it's very solid, but won't work on the 360.

Also, I'd be interested in hearing how this go's, so please post back with what you find!

May 12, 2010 at 3:30 PM

Hm, that 2d outline algorithm listed in the second link might be enough for my purposes. I'll have a shot at implementing it tomorrow & I'll report back.

I already tried implementing it using BooleanTools.Union, which was a complete disaster (even after removing the braindead coordinate rounding code and fixing it up so it would recognise shared edges). The union code appears to be flat-out wrong.