Hey.
I have this idea of making a cool terrain system. I haven't been able to formulate a good Google search for it... The idea is to define a number of intersecting spheres that together form a solid mesh. However, I'm having trouble figuring out how to convert such a group of spheres to a solid mesh. So, my question is:
Given two or more intersecting spheres, how would I compute a solid triangle mesh from them without producing any triangles that end up inside the mesh?
Bonus question: The same question as above, but this time it also needs to support "anti-spheres" which instead of forming terrain cut holes in existing meshes.
I would like to avoid a voxel-based solution due to performance and memory reasons...
Boolean operations are indeed what you're looking for. However, my advice is to offload CSG ops to either an external library (which you'll have to google yourself) or a CAD program as a preprocessing step, which will both have far more robust implementations than what you can whip up on your own in a reasonable amount of time. CSG has a lot of edge cases and care must be taken to avoid degeneracies and precision issues. I know this, because I've gone down the other road and actually implemented my own CSG routine :ph34r: .
Now, if you do find yourself itching to do this on your own, then prepare for A LOT of testing and squinting your nose as your edge cases do not work :P . Of the three primary approaches (the stencil buffer approach, which gives you no resulting geometry; the BSP-tree based approach, which blows up quickly in terms of speed and memory footprint as you give it more complex objects) you'll want to look into the one that is the most stable and can handle large meshes, as painstakingly outlined in this paper by Laidlaw back in 1986. I do believe I encountered one mistake in the paper, though. However, I can't recall what it was and I don't have access to my code right now.
The one thing I love about Laidlaw's polygon-based approach is that operations on each mesh are atomic and can thus be batched off to different threads. That is, for all operation types you're essentially looking at the following scheme: 1) calculate intersection of AUB; 2) calculate intersection of BUA; 3) perform a simple discard on the data that you do not need (depending on what operation you're performing) and merge as needed. Steps 1 and 2 are completely separable and can be performed in parallel based only on the input meshes. Step 3 requires synchronization, but is a cheap one. The bad thing is that you probably won't be able to use your existing mesh data structures for it. Good luck :).
