Hey all, I want to approximate a closed (Non-convex) mesh-volume with spheres, look at it as filling the shape with marbles of arbitrary size. The sphere''s may not overlap. The original shape has to be filled up/approximated in a fairly good manner, which means it doesn''t have to be perfect, as long as it is filled so that I don''t have many big holes in the volume. The spheres can have any radius, but with a given minimum. The result of the routine should be an array of positions and radii. Any ideas on how to approach this problem? Cheers! Nick

One naive approach is to simply voxelize the object into spheres of a fixed size (using the marching cubes algorithm for example). Really, you could just use a standard voxelization routing and replace the cubes with spheres.

To generate spheres of multiple sizes, you could generate a sphere tree using the basic algorithm of OBB of AABB trees, but replacing the boxes with spheres, and just keep the most detailed level of the tree. But this won''t necessarily give you a set of spheres that are packed tightly or non-overlapping.

The Visualization Toolkit (VTK) is open source and has code to voxelize things (I think).

public.kitware.com/VTK/

Also, this powerpoint presentation may help:

www.cs.utk.edu/~huangj/CS594S02/voxdist.ppt

As might this PDF file:

www.sdsc.edu/~nadeau/PhD/VolumeSceneGraphs.pdf

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Thanks!

That was exaclty the angle I needed. It looks very promissing!

Cheers,
Nick

quote:

---

Original post by NickWaanders
Thanks!

That was exaclty the angle I needed. It looks very promissing!

Cheers,
Nick

---

I''m happy to hear it!

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

quote:

---

Original post by grhodes_at_work
To generate spheres of multiple sizes, you could generate a sphere tree using the basic algorithm of OBB of AABB trees, but replacing the boxes with spheres, and just keep the most detailed level of the tree. But this won''t necessarily give you a set of spheres that are packed tightly or non-overlapping.

---

This problem has a 1-1 mapping with "optimal packing problems". There are well established methods for solving simple instances of such problems, so check out the literature, either online or at your local university/college library.

What you''ll find though is that the problem is NP-hard for arbitrary shapes and volumes. Some of the better methods for dealing with it involve simulated annealing or genetic search applied to a constraint satisfaction formulation of the problem domain.

It''s not an easy thing you seek to do, but it has been done... so the answers are out there.

Good luck,

Timkin

This problem gave me something good to think about in my spare time

I was thinking about a method to find the area of a 2D polygon, convex or not (non-overlapping of course). We basically divide it into triangles, and sum the area of each triangle. This would give us an exact area. If we expand this into three dimensions, trying to form simplier volumes such as pyramids, would it work as a good way to find the exact volume of an object? Or are the implications of such a process as the the volume splitting such that we wouldn''t benefit from the exact area due to the lack of good performance, etc.?

Once again, this is something that''s been broiling on the back burner this past week

This article describes a method for building a sphere list from a polyhedral object (actually they build a hierarchy). It sounds pretty complicated, but the results looked good:

http://citeseer.nj.nec.com/hubbard96approximating.html

[edited by - Eric on July 18, 2002 4:21:03 AM]

I think I shall move forward with my idea then, just for the heck of it!