looking for a csg engine

[rouncer]

ive tried to code csg (constructive solid geometry) or boolean objects
for ages now with a little success, but not enough to be happy with.
i would really like to do modelling with it.

im having trouble coding it, at the moment, i can do it, but it leaves holes
and loose vertices around the place, and its not very nice to use - every
time you use it, youd have to weld 10 or so vertices and watch out for
model degeneracy. (the bad bit) if it screws up, other algorythms that act
on the model afterwards can crash, and it makes the whole editor really
touchy to use, it could crash at any second.

it seems to be my falling, trying to code this, ive coded alot of other things
but i just dont seem quite smart enough to debug this one.

i could use it myself, but its hardly professional enough to release as a product,
even as a free product, noone would want to use it.

is there any professional library out there for it?

[Nicholas Christopher]

http://opencsg.org/

http://www.cgal.org/

http://gts.sourceforge.net/

enjoy.

[Sol_HSA]

http://opencsg.org/ - GPL
http://www.cgal.org/ - LGPL/QPL or commercial license
http://gts.sourceforge.net/ - LGPL

.. to save time if license matters.

[anubis]

Recently I thought about dynamically evaluating CSG sets with something like marching cubes. That wouldn't be able to deal with sharp edges in a lot of situations but might still produce interesting results often enough to be useful

[rouncer]

that sounds interesting, could you elaborate a little more?

[anubis]

Well... finding out if a point is inside or outside of a csg set is easy and efficent. It's simply a matter of traversing the csg operator tree plus a point in object test for every primitive object used in the csg set. In marching cubes that is exactly the basic operation you perform. Of course that would only get you an aproximation of the real object and I'm not even sure that the algorithm can deal with all kinds of geometry but it would definetly be interesting to experiment with it

[Kenneth Gorking]

I recently found this when researching the marching cubes algo, might be useful: http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/

[mikola]

Have you tried using BSPs for constructive solid geometry? They have the advantage that they are unconditionally stable, if you get a bad result all that happens is part you waste some memory. They are also extremely fast, often beating standard algorithms like Laidlaw & Hubbard. Finally, they give you some nice bonuses like cheap collision detection and visibility culling.

Here is the original publication on the subject:
http://portal.acm.org/citation.cfm?id=97892&coll=portal&dl=ACM

And here is a 1 page sketch that I recently wrote detailing some improvements to the basic algorithm:
http://www.assertfalse.com/articles/SIGGRAPH_csg_sketch_2007.pdf

Right now I am working on an extended paper for publication in a journal which should go into greater detail on the algorithm. The sketch covers the basics of the approach, and with some patience and Naylor's article it should be enough to work out a correct implementation.

The down side to this approach is that updating the geometry can be very expensive on a GPU. I believe these issues can be addressed, and so far have some promising preliminary results. With any I luck, I will have a complete paper out some time around September along with a demo + source online.

Regards,
Mikola Lysenko