# Calculating bounding sphere.

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

## 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 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 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 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)/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 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 on other sites
Quote:
 Original post by alvaroOf 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 &lt; box2.min.x ||                box1.max.y &lt; box2.min.y ||                box1.max.z &lt; box2.min.z ||                box1.min.x &gt; box2.max.x ||                box1.min.y &gt; box2.max.y ||                box1.min.z &gt; 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 &lt; num_xyz; ++i) // loop for the # of verticies in the object    {        if ( vertlist.x &lt; box.min.x ) box.min.x = vertlist.x;        if ( vertlist.y &lt; box.min.y ) box.min.y = vertlist.y;        if ( vertlist.z &lt; box.min.z ) box.min.z = vertlist.z;        if ( vertlist.x &gt; box.max.x ) box.max.x = vertlist.x;        if ( vertlist.y &gt; box.max.y ) box.max.y = vertlist.y;        if ( vertlist.z &gt; box.max.z ) box.max.z = vertlist.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]

1. 1
2. 2
Rutin
25
3. 3
4. 4
5. 5

• 10
• 10
• 13
• 20
• 14
• ### Forum Statistics

• Total Topics
632948
• Total Posts
3009365
• ### Who's Online (See full list)

There are no registered users currently online

×