Possible Bounding Sphere problem

Dec 28, 2010 at 1:44 AM

I have a game I’m working on which requires me to detect what geometry the user clicks on. I’m able to use a pick ray and iterate over all my geometries and use the intersect method. I then find the one with the shortest distance and call it selected.

The issue I’m running into is sometimes I can very clearly see a mesh, but I can’t pick it. When I iterate over all the geometries and I get to the one I’m supposed to be intersecting with my pick ray, I get no intersections. 

I think I’ve tracked this down to the bounding sphere. In some cases the sphere is not completely surrounding my geometry. It’s leaving a bit chopped off at the bottom or a side. I think I have narrowed when this happens down to me having geometry with two distinct unconnected sections, contained in a single geometry instance. 

Does Balder support situations where a single mesh may have two or more sections that may be unconnected by any shared vertices. If so, are you aware of any bug that could cause the bounding sphere to calculate incorrectly in those situations? 

Please help me understand Balders position on this. If this is something that is supported, I’ll try to put together a demo. If this isn’t something Balder will do, I’ll get back to the drawing board on that part of my game.

Dec 28, 2010 at 3:45 AM

I think I found the problem. There is a method in the geometry class that prepares the bounding sphere (PrepareBoundingSphere) This method is tasked with creating the bounding volume sphere. It finds the two vectors that are farthest from each other based on the min/max x,y,z coordinates. Then it divides that by two to find a radius. It also finds something called a Centroid, which in this case is an average x,y,z coordinate. It actually finds the average of all the x’s and all the y’s and all the z’s and creates a vector from that. This is treated as the center of the bounding sphere. 

In my case (partially noted above) I have a single mesh that is separated into two parts. These parts are relatively far from each other and arranged in such a way as the top part has many more vertices than the bottom part. So when this average is found, the top cluster of vertices has more weight than the bottom. The end result being the center and radius chosen do not form a bounding sphere that holds all the vertices in the mesh. 

Another solution for finding the bounding sphere could be:
Welzl
http://www.gamedev.net/reference/programming/features/welzlminsphere/page2.asp 

I see the method for preparing the bounding sphere is virtual, so I can create my own in my mesh class. If it works, I’ll post the code.

Dec 28, 2010 at 4:00 AM

I understand there is an implementation here:

http://www.cgal.org/

I'm also checking that out, I'm not sure on license just yet though.

Coordinator
Dec 29, 2010 at 5:23 AM

Hi,

thanks for the links. The bounding spheres in Balder is something I've been going back and forth with trying to find a good solution - so really appreciate the links.

The two parts you have in your mesh, if you had them as two geometries belonging to the same mesh (two objects in the 3D modelling software) - they would get separate bounding spheres, but get a outer bounding sphere containing them. That might help - unless you already have this, of course.

Love to get feedback on this if you do try out creating your own bounding sphere.

Dec 29, 2010 at 3:30 PM

Hope MS don't mind me digging around in their code...  Anyway XNA studio has a method named CreateFromPoints as a static method of the Bounding Sphere class. It takes a list of vectors and ouputs a center and radius.  I'm going to study their code and give it a go.  I used Red Gate's free Reflector program to view the code details.

XNA studio seems to be free if you have VS2010 installed already.  Once that was installed I created a console app and added a refference to the XNA core framework. Then I created a BoundingSphere object and compiled.  I add that new exe to reflector by dragging it to the Reflector window and then doubled clicked on my main method to view the source.  Now I have a way to click 'into' the XNA core libs and poke around.

Great way to learn and there seems to be lots of gems in there to study.

Just hope I'm not breaking any rules set down by MS; Perhaps I'll need to read their EULA to understand what I can and cannot do with their XNA framework.

Dec 30, 2010 at 1:26 AM

seems to work... the sphere is a bit larger than it should be I think but it's not too small when there are clustered points. (Hope I don't see a lawsuit from MS!)

        public override void PrepareBoundingSphere()
        {
            if (BoundingSphere.IsSet())
                return;

            var Vertices = FullDetailLevel.GetVertices();
            var Vectors = from v in Vertices select v.ToVector();

            BoundingSphere = CreateFromPoints(Vectors);
            base.PrepareBoundingSphere();
        }
        private static BoundingSphere CreateFromPoints(IEnumerable<Balder.Math.Vector> Vectors)
        {
            float num, num2, num4, num5;
            Balder.Math.Vector vector2, vector5, vector6, vector7, vector8, vector9;
            BoundingSphere sphere;

            Balder.Math.Vector vector4 = vector5 = vector6 = vector7 = vector8 = vector9 = Vectors.First();
            foreach (Balder.Math.Vector vector in Vectors)
            {
                if (vector.X < vector4.X)
                {
                    vector4 = vector;
                }
                if (vector.X > vector5.X)
                {
                    vector5 = vector;
                }
                if (vector.Y < vector6.Y)
                {
                    vector6 = vector;
                }
                if (vector.Y > vector7.Y)
                {
                    vector7 = vector;
                }
                if (vector.Z < vector8.Z)
                {
                    vector8 = vector;
                }
                if (vector.Z > vector9.Z)
                {
                    vector9 = vector;
                }
            }

            num5 = Balder.Math.Vector.Distance(vector5, vector4);
            num4 = Balder.Math.Vector.Distance(vector7, vector6);
            num2 = Balder.Math.Vector.Distance(vector9, vector8);
            if (num5 > num4)
            {
                if (num5 > num2)
                {
                    vector2 = Balder.Math.Vector.Lerp(vector5, vector4, 0.5f);
                    num = num5 * 0.5f;
                }
                else
                {
                    vector2 = Balder.Math.Vector.Lerp(vector9, vector8, 0.5f);
                    num = num2 * 0.5f;
                }
            }
            else if (num4 > num2)
            {
                vector2 = Balder.Math.Vector.Lerp(vector7, vector6, 0.5f);
                num = num4 * 0.5f;
            }
            else
            {
                vector2 = Balder.Math.Vector.Lerp(vector9, vector8, 0.5f);
                num = num2 * 0.5f;
            }
            foreach (Balder.Math.Vector vector10 in Vectors)
            {
                Balder.Math.Vector vector3 = new Vector();
                vector3.X = vector10.X - vector2.X;
                vector3.Y = vector10.Y - vector2.Y;
                vector3.Z = vector10.Z - vector2.Z;
                float num3 = vector3.Length;
                if (num3 > num)
                {
                    num = (num + num3) * 0.5f;
                    vector2 += (Balder.Math.Vector)((1f - (num / num3)) * vector3);
                }
            }
            sphere.Center = vector2;
            sphere.Radius = num;
            return sphere;
        }
Coordinator
Dec 30, 2010 at 9:08 PM
Most excellent. Thanks. We'll just move a couple of lines and rename a few variables and whoops, lawsuit avoided - just kidding. I'll dig into the logic of it, saw a few optimizations thatbcould be done to it. Thanks again