Archived

This topic is now archived and is closed to further replies.

revearz

Adding up bounding spheres

Recommended Posts

Hi, Is there a quick way to add up many spheres into 1 big bounding sphere? Right now, I find create the bounding sphere encompassing all the points ( position of each sphere ). Then I add to the big bounding sphere radius the maximum radius of those little spheres. This doesn''t give me the optimal (near optimal) solution though. Any thoughts?

Share this post


Link to post
Share on other sites

Set min.x, min.y, min.z to very large value (1e8)
Set max.x, max.y, max.z to very small negative value (-1e8)
For each bounding sphere
pmin.x = sphere center.x - sphere radius
(repeat for y and z)
pmax.x = sphere center.x + sphere radius
(repeat for y and z)
if(pmin.x < min.x)
min.x = pmin.x
(repeat for y and z)
if(pmax.x > max.x)
max.x = pmax.x
(repeat for y and z)

min and max now represent 2 corners of a cube
Find the center of the cube: (max + min) / 2
Uber-sphere radius: distance from center to either min or max


That should work for you.

Share this post


Link to post
Share on other sites
I would use the same center C for the sphere that ApochPiQ proposed, but for the radius, consider using the maximum over all spheres S of (distance(C,S.center)+S.radius).

If you need an optimum solution, I can think of a method to find it, but it''s O(number_of_spheres^4) and not too easy to code.

Share this post


Link to post
Share on other sites
Thanks for the help guys. I didn''t think of converting the problem to bounding box first ...

ApochPiQ: is there a way to remove the computation of the sqrt when calculating (distance(C,S.center)+S.radius).


Share this post


Link to post
Share on other sites
I remember the article about dynamic sphere tree in the games programming gems ||, by ratcliff, and they had this function to recompute a tight bounding sphere around a cluster of points.


/*
An Efficient Bounding Sphere
by Jack Ritter
from "Graphics Gems", Academic Press, 1990
*/


/* Routine to calculate tight bounding sphere over */
/* a set of points in 3D */
/* This contains the routine find_bounding_sphere(), */
/* the struct definition, and the globals used for parameters. */
/* The abs() of all coordinates must be < BIGNUMBER */
/* Code written by Jack Ritter and Lyle Rains. */

#define BIGNUMBER 100000000.0 /* hundred million */

void Sphere::Compute(const SphereInterface &source)
{

Vector3f xmin( BIGNUMBER, BIGNUMBER, BIGNUMBER);
Vector3f xmax(-BIGNUMBER,-BIGNUMBER,-BIGNUMBER);
Vector3f ymin( BIGNUMBER, BIGNUMBER, BIGNUMBER);
Vector3f ymax(-BIGNUMBER,-BIGNUMBER,-BIGNUMBER);
Vector3f zmin( BIGNUMBER, BIGNUMBER, BIGNUMBER);
Vector3f zmax(-BIGNUMBER,-BIGNUMBER,-BIGNUMBER);
Vector3f dia1;
Vector3f dia2;

int count = source.GetVertexCount();

int i;
for (i=0; i<count; i++)
{
Vector3f caller_p;
source.GetVertex(i,caller_p);

if (caller_p.x<xmin.x) xmin = caller_p; /* New xminimum point */
if (caller_p.x>xmax.x) xmax = caller_p;
if (caller_p.y<ymin.y) ymin = caller_p;
if (caller_p.y>ymax.y) ymax = caller_p;
if (caller_p.z<zmin.z) zmin = caller_p;
if (caller_p.z>zmax.z) zmax = caller_p;
}

/* Set xspan = distance between the 2 points xmin & xmax (squared) */
float dx = xmax.x - xmin.x;
float dy = xmax.y - xmin.y;
float dz = xmax.z - xmin.z;
float xspan = dx*dx + dy*dy + dz*dz;

/* Same for y & z spans */
dx = ymax.x - ymin.x;
dy = ymax.y - ymin.y;
dz = ymax.z - ymin.z;
float yspan = dx*dx + dy*dy + dz*dz;

dx = zmax.x - zmin.x;
dy = zmax.y - zmin.y;
dz = zmax.z - zmin.z;
float zspan = dx*dx + dy*dy + dz*dz;

/* Set points dia1 & dia2 to the maximally separated pair */
dia1 = xmin;
dia2 = xmax; /* assume xspan biggest */
float maxspan = xspan;

if (yspan>maxspan)
{
maxspan = yspan;
dia1 = ymin;
dia2 = ymax;
}

if (zspan>maxspan)
{
dia1 = zmin;
dia2 = zmax;
}


/* dia1,dia2 is a diameter of initial sphere */
/* calc initial center */
mCenter.x = (dia1.x+dia2.x)*0.5f;
mCenter.y = (dia1.y+dia2.y)*0.5f;
mCenter.z = (dia1.z+dia2.z)*0.5f;
/* calculate initial radius**2 and radius */
dx = dia2.x-mCenter.x; /* x component of radius vector */
dy = dia2.y-mCenter.y; /* y component of radius vector */
dz = dia2.z-mCenter.z; /* z component of radius vector */
mRadius2 = dx*dx + dy*dy + dz*dz;
mRadius = float(Asura_Maths::Sqrt(mRadius2));

/* SECOND PASS: increment current sphere */

for (i=0; i<count; i++)
{
Vector3f caller_p;
source.GetVertex(i,caller_p);
dx = caller_p.x-mCenter.x;
dy = caller_p.y-mCenter.y;
dz = caller_p.z-mCenter.z;
float old_to_p_sq = dx*dx + dy*dy + dz*dz;

if (old_to_p_sq > mRadius2) /* do r**2 test first */
{ /* this point is outside of current sphere */
float old_to_p = float(Asura_Maths::Sqrt(old_to_p_sq));
/* calc radius of new sphere */
mRadius = (mRadius + old_to_p) * 0.5f;
mRadius2 = mRadius*mRadius; /* for next r**2 compare */
float old_to_new = old_to_p - mRadius;
/* calc center of new sphere */
float recip = 1.0f /old_to_p;

float cx = (mRadius*mCenter.x + old_to_new*caller_p.x) * recip;
float cy = (mRadius*mCenter.y + old_to_new*caller_p.y) * recip;
float cz = (mRadius*mCenter.z + old_to_new*caller_p.z) * recip;

mCenter.x = cx;
mCenter.y = cy;
mCenter.z = cz;
}
}
}



dunno if I am actually allowed to post that code, and how useful it is for you, but there you go. I'd guess, all you have to do after, is expand the big sphere with the radius of the child spheres, if a child spheres pierces through the bounding sphere, or if all your spheres have a similar radius, just add the radius of the child spheres to the bounding sphere.

[edited by - oliii on October 7, 2003 8:43:26 AM]

Share this post


Link to post
Share on other sites