Jump to content
  • Advertisement
Sign in to follow this  
theagentd

Computing an optimized mesh from a number of spheres?

This topic is 822 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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...

Edited by theagentd

Share this post


Link to post
Share on other sites
Advertisement

In blender this is called a Boolean operation. That may lead you to something.

 

Your algorithm however doesn't sound useful. I'm assuming you want to connect a bunch of mountain or hills that are all spheres? Better to use a heightmap or some other scheme.

Share this post


Link to post
Share on other sites

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 :).

Edited by irreversible

Share this post


Link to post
Share on other sites

Incidentally - if what you're looking for is a blob-like approximation of your spheres, not an exact union, and you're only dealing with spheres, then it might not hurt to look into metaballs.

Share this post


Link to post
Share on other sites

Thanks for all the awesome responses! I'm not entirely sure I can implement this though... I will try to check out some Java libraries for accomplishing all this for me, hopefully. And here I thought I had a new idea... >___>

 

The only thing I had really heard about before was meta-balls.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!