Jump to content
• Advertisement

# Computing an optimized mesh from a number of spheres?

This topic is 976 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

##### Share on other sites
Advertisement
Take a look at constructive solid geometry, it may be what you’re looking for.

#### Share this post

##### Share on other sites

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

##### Share on other sites
The easiest way should be to 'render' the spheres into a density volume, and use marching cubes or a similar algorithm to triangulate it.
That's a voxelization step in between but it also enambles you to use any other shape than just spheres.

Look up this paper for alternatives (and also a proof the idea is useful):
http://media.lolrus.mediamolecule.com/AlexEvans_SIGGRAPH-2015-sml.pdf

#### Share this 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

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

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

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
Rutin
19
3. 3
khawk
18
4. 4
A4L
14
5. 5
• Advertisement

• 12
• 16
• 26
• 10
• 44
• ### Forum Statistics

• Total Topics
633766
• Total Posts
3013732
×

## Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!