Sign in to follow this  
ReturnNULL

Calculating bounding sphere.

Recommended Posts

What is the best way to find the bounding sphere(radius) of an object? I have a variable representing the number of verts, and an array of all the vertices's with their positions(xyz). p.s: I am using Opengl and 3D

Share this post


Link to post
Share on other sites
Find the distance squared between the vertices and the center of mass of the object and take the largest one? That would be my first guess. Then just sqrt that for the radius when you have the largest distance.

Share this post


Link to post
Share on other sites
Of course, Sirisian's answer is just an approximation (a useful one), and there will be cases where it won't do the right thing (e.g., if your vertices are much more dense on one side of the object than on the other side).

Once you have an approximation, you can refine it by figuring out a way to move the center of the sphere that would result in a reduction in radius. I haven't thought about this before, but I think you can use this method:

1. Find an approximated sphere (e.g., Sirisian's).
2. Get the set S of points that are on the surface of the current sphere (remember that comparing floating-point values for equality is tricky).
3. If the center of the sphere is inside the convex polyhedron formed by the points in S, you are done.
4. Compute the center of mass B of the points in S.
5. Move the center of the sphere a little bit towards B and recompute the required radius.
6. Goto 2.

Is this a known algorithm? Perhaps there's something better? This sounds like something that Dave Eberly would know...

Share this post


Link to post
Share on other sites
I may be wrong, but you can find the sphere, by finding the pair of vertices, that are the furthest from each other, the radius is the half of the distance, and the center is c=(v[k]+v[i])/2.0

EDIT: Sorry: IT'S WRONG.
This is not my day...

EDIT2: or maybe it IS right.
I shouldn't make replies today.

EDIT3: definitely wrong

Share this post


Link to post
Share on other sites
For a better approximation, I'd start with the centre of the axis aligned bounding box of the object as the sphere origin, instead of the centre of mass.

You can also compute the optimal sphere more slowly with Welzl's Algorithm.

Some other options and performance measurements can be found here.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Of course, Sirisian's answer is just an approximation (a useful one), and there will be cases where it won't do the right thing (e.g., if your vertices are much more dense on one side of the object than on the other side).

Once you have an approximation, you can refine it by figuring out a way to move the center of the sphere that would result in a reduction in radius. I haven't thought about this before, but I think you can use this method:

1. Find an approximated sphere (e.g., Sirisian's).
2. Get the set S of points that are on the surface of the current sphere (remember that comparing floating-point values for equality is tricky).
3. If the center of the sphere is inside the convex polyhedron formed by the points in S, you are done.
4. Compute the center of mass B of the points in S.
5. Move the center of the sphere a little bit towards B and recompute the required radius.
6. Goto 2.

Is this a known algorithm? Perhaps there's something better? This sounds like something that Dave Eberly would know...


I'll try and do what you said, but my game(tower defense) wouldn't need exact precision for collision detection.

I tried doing AABB collision also, but It didn't work right, I'll find my algorithm and post it here.

I declare my struct like this:

struct BoundingBox
{
Vector3f min;
Vector3f max;
};



I check for collisions here:

if (box1.max.x < box2.min.x ||
box1.max.y < box2.min.y ||
box1.max.z < box2.min.z ||
box1.min.x > box2.max.x ||
box1.min.y > box2.max.y ||
box1.min.z > box2.max.z)
{
return false;
}

return true;



And I calculate the AABB's here:

// initialize the aabb structs.
box.min.x = vertlist[0].x;
box.min.y = vertlist[0].y;
box.min.z = vertlist[0].z;

box.max.x = vertlist[0].x;
box.max.y = vertlist[0].y;
box.max.z = vertlist[0].z;


for (int i = 0; i < num_xyz; ++i) // loop for the # of verticies in the object
{
if ( vertlist[i].x < box.min.x ) box.min.x = vertlist[i].x;
if ( vertlist[i].y < box.min.y ) box.min.y = vertlist[i].y;
if ( vertlist[i].z < box.min.z ) box.min.z = vertlist[i].z;

if ( vertlist[i].x > box.max.x ) box.max.x = vertlist[i].x;
if ( vertlist[i].y > box.max.y ) box.max.y = vertlist[i].y;
if ( vertlist[i].z > box.max.z ) box.max.z = vertlist[i].z;
}



My problem is that the object is always colliding, no matter how far apart...

[Edited by - ReturnNULL on February 23, 2010 9:54:47 AM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this