Archived

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

imDivineLight

Bounding Spheres, Need A little Info

Recommended Posts

Hi! for the last couple of days i have been working on Bounding spheres to get frustum culling & collision detection. BUt i am getting much larger sphere than i need, so objects collide even far away. i am using D3DX functions to calculate the bounding sphere for my meshes. is there any other way or it''s the perfect one. & is the center of sphere is the pivot point we used in modeling package. if i scale the object how to scale the radius along it? i use Jim''s method. but i dont think it''s fine: check it out:
// Returns Objects bounding sphere scaled radius

inline float GetBSphereRadius()
{ 
	float XScale = mWorldPos.GetScaling()->x;
	float YScale = mWorldPos.GetScaling()->y;
	float ZScale = mWorldPos.GetScaling()->z;
		
	float Length = (float)sqrt( ( XScale * XScale ) + 
		( YScale * YScale ) + ( ZScale * ZScale ) );
    
        // Mesh''s orignal unscaled radius

	float fRadius = mpXMesh->GetBSphereRadius();

	fRadius += Length;
		
	return fRadius;
}

Share this post


Link to post
Share on other sites
All the times I have used D3DXComputeBoundingSphere(), it has worked OK for me. The thing is, the bounding sphere may seem huge because it has to encompass the entire object, while still maintaing it''s sphere shape. In other words, boundings spheres are just not good fits for some objects. I recommend that you check out this awesome article if you need help with bounding-sphere stuff.


Dustin Franklin
Mircrosoft DirectX MVP

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Most people use bounding spheres (and boxes) as a quick test, not the final test. If the bounding spheres collide, you do the slow test to determine if the meshes actually collide. If the bounding sphere don''t collide then there is no need to do the slow test.

You can test for collision using a tree of bounding spheres. For each bounding sphere, the mesh inside it is divided into smaller pieces which are each enclosed in bounding sphere. This continues until sphere contain a maximum number of triangles (or some other meaningful limit). To test for collision, first you check root spheres (the ones that enclose the entire mesh). If those collide then you check the spheres enclosed by those spheres. If any of those collide, you check the spheres enclosed by those spheres. ... Eventually, you get to the point where you check if triangles collide. Sphere collision is pretty fast so you spend a very small amount of time eliminating a large number of triangles to test.

Share this post


Link to post
Share on other sites
But i think my bounding spheres are way to bigger or not too accurate, here see a screenshot for a bounding sphere for building. isn't it way too big or i'm wrong?

[img]
http://www.geocities.com/darkengine2d/screenshot.jpg
[/img]

[edited by - imDivineLight on May 18, 2004 9:45:24 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by imDivineLight
But i think my bounding spheres are way to bigger or not too accurate, here see a screenshot for a bounding sphere for building. isn''t it way too big or i''m wrong?



It could be smaller if the center of the sphere was closer to the center of the building.

There is a problem because part of the building sticks out of the sphere.

My guess is that "fRadius += Length;" should be "fRadius *= Length;" since it is a scale factor.

Share this post


Link to post
Share on other sites
Bounding spheres will never give you a tight fit since they have to cover the whole object, and if your obejct is of an elnogated shape, you will get a very bad bounding sphere. Also I believe that doing heirarchical test with bounding spheres is not vey ideal for the same reason.

Instead, just use BoundingBoxes. You can write a generic enough code to compute a bounding box given n points. For intersection testing, just iterate thru its 8 corner points and check waether they are above or below the intersection plane. All eight points must be on the outside for the box to be rejected completely. Otherwise it is inside or intersects. If it is inside (all eigh points inside), then you can stop right there and select this box as well as all its children as being inside. Otherwise you wil lrecursively test each child.

Although it seems a lot more points to check vs a sphere, but as you will find out that intersection testing with spehre almost always passes (since it is just always so big). Hence you end up drawing lot of geometry that will later be culled away by the hardware.

Share this post


Link to post
Share on other sites
Yes spheres are very lame things, so tell me is there any other use of them or not? i think the only one is the initial dirty collision test, i have seen the AABBs they stick very tightly to meshes, such as walls & boxes, i find them more use full.

One info i want here is that if i move my mesh to another place in world how to translate the Max & Min Vectors of AABB according to the new position, i have tried adding the translation vector of mesh to these min max vectors but all is screwed up, please any help or another nice note on using AABBs for checking collisions, against spheres, points & other AABBS?

Share this post


Link to post
Share on other sites
Quick reply ... Rememebr vectors can not be translated. Only 'points' can be translated.

not sure what you are storing for the bounding boxes, but I work as follows

Given n points, I iterate thru them and find the max and min for each x y and z.

After iteration I have the min and max 'points' of the bounding box. In oyur mesh example, you can use all the vertices of the mesh if you want. This is a load time operation and speed is not of immediate concern (although does not hurt if you can speed this up though).

After this, just treat these as two extra vertices associated withthe mesh. Now if you transsform your mesh (translate, rotate, simply apply the same operation to these points as well).

If your mesh vertices are in model space, keep your bounding box's min max points in object space. If they are in world space, keep BB end points in works sapce as well. Just keepthem same and remember to keep track of the distinction between points vs vectors, and apply the same transformations!

good luck




[edited by - AQ on May 21, 2004 2:00:14 PM]

Share this post


Link to post
Share on other sites
First of all that:
fradius *= length; gives a way too big BSphere, so i think scaling you''r geometry is a bad or worst idea isn''t it?

& i successfully moved my AABB & BSphere to another point, for AABB add that point to MIN & MAx points & for sphere add it to sphere''s centre right?

Please i want some easy article on collision response also, when i collide where to go then ???

Share this post


Link to post
Share on other sites