ReturnNULL 100 Report post Posted February 21, 2010 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 0 Share this post Link to post Share on other sites
Sirisian 2263 Report post Posted February 21, 2010 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. 0 Share this post Link to post Share on other sites
alvaro 21273 Report post Posted February 22, 2010 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... 0 Share this post Link to post Share on other sites
szecs 2990 Report post Posted February 22, 2010 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.0EDIT: Sorry: IT'S WRONG.This is not my day...EDIT2: or maybe it IS right.I shouldn't make replies today.EDIT3: definitely wrong 0 Share this post Link to post Share on other sites
Adam_42 3630 Report post Posted February 22, 2010 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. 0 Share this post Link to post Share on other sites
ReturnNULL 100 Report post Posted February 22, 2010 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 < 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] 0 Share this post Link to post Share on other sites