• Advertisement
Sign in to follow this  

Avro's algorithm to check sphere against bounding box.need explination of code

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

i found this algorithm called "Arvo's algorithm", for testing if a sphere has overlapped with a bounding box. can anyone tell me exactly whats going on in this algorithm as im not sure of c++ at all. i only use c# and i never used c++.i dont understand symbols like "&" in c++ . thanks:
//Check to see if the sphere overlaps the AABB
const bool AABBOverlapsSphere ( const AABB& B, const SCALAR r, VECTOR& C ) 
{ 

float s, d = 0; 
//find the square of the distance
//from the sphere to the box
for( long i=0 ; i<3 ; i++ ) 
{ 

if( C < B.min(i) )
{

s = C - B.min(i);
d += s*s; 

}

else if( C > B.max(i) )
{ 

s = C - B.max(i);
d += s*s; 
}


}
return d <= r*r;


}

i mainly need to know what the parameter "const AABB& B" is. [Edited by - fguihen on January 3, 2005 4:34:34 PM]

Share this post


Link to post
Share on other sites
Advertisement
Do a search for 'c++ references' on google or the archives here for detailed info on what the '&' means. Short answer: it's similar to a pointer, except it cannot be null and is resolved with the . operator rather than ->. I don't know anything about C#, but I assume it has pointers as well. If not, then 'AABB& B' means that 'B' is an alias of sorts for an object of type AABB. 'const' just means that the object cannot be modified within the function.

(Code gurus, I know the above is very terse and incomplete! But a complete explanation would take several paragraphs, and the info is already out there...)

Now to the algorithm (if you already understand the algorithm and were just wondering about &, you can stop reading).

A convex object has a number of Voronoi regions associated with it. Each Voronoi region is associated with a feature of the object, where a feature is a face, vertex or edge. The defining characteristic of the Voronoi region associated with a feature is that all points in that region are as close or closer to that feature than to any other feature. The Voronoi regions for a convex polyhedron in 3D are partitioned by the planes of the faces, and planes perpendicular to the faces and passing through the edges. An AABB has 27 such regions (including the interior), and the partitioning planes are axis-aligned.

Given a sphere and an AABB, you can classify the center of the sphere with respect to the AABB's Voronoi regions. From that we know which feature the center of the sphere is closest to - it may be a corner, an edge, or a face. If then the (squared) distance from the sphere center to that feature is less than or equal to the (squared) radius of the sphere, the sphere intersects the AABB.

If arbitrary sphere-edge and sphere-face distance tests were required, the code would be quite a bit more complex. However, the axis-aligned nature of the AABB simplifies things considerably.

Looking at the code you posted, it may not be immediately clear how it relates to what I just described. But if you were to write the function out in 'longhand' - that is, find the squared distance for each Voronoi region separately - you would begin to see how it can be reduced to your example. In brief, various of the AABB's Voronoi regions share certain terms of the squared distance calculation, and so the squared distance can be found cumulatively at little cost.

Wow, well that was long-winded. Sorry. But I hope it was clear. Ask if you need any clarification.

Share this post


Link to post
Share on other sites
this explination is real heavy and would take me a long time to understand but what i want to know is this, if i have an object surrounded by a bounding sphere translated into world space, and an aabb which is translated into world space, can i use this algorithm to check for colisions? thats the way i see it, but i have been known to be wrong (with most things!)in c# , i think the AABB would be represented as an array of vertices. is this correct?

you can use pointers in c#, but they are rarely used ( and i never use them) as with managed code there are always safer ways to do things.us baby dot net programmers dont like doing our own garbage collection or dealing with memory leaks. thanks

Share this post


Link to post
Share on other sites
Quote:
this explination is real heavy and would take me a long time to understand but what i want to know is this, if i have an object surrounded by a bounding sphere translated into world space, and an aabb which is translated into world space, can i use this algorithm to check for colisions? thats the way i see it, but i have been known to be wrong (with most things!)in c# , i think the AABB would be represented as an array of vertices. is this correct?


Yeah, sorry, let me try and give you something a little more useful. Yes, this algorithm will determine whether there is an intersection between a sphere and an AABB in world space. The sphere is represented simply by its center (the vector 'C' in the function) and its radius (the scalar 'r' in the function). An AABB could be represented by an array of 8 corners as you suggest, but usually we just use two vectors typically called 'min' and 'max'. The 'min' vector holds the minimum x, y and z values for the AABB, and the 'max' vector holds the maximum x, y and z values.

So all you need to know is the center and radius of the sphere, and the min and max vectors for the AABB. Plug them into the function and you're good to go.

Share this post


Link to post
Share on other sites
An AABB is represented by just a minimum and a maximum vertex that hold the minimum and maximum components of the object in world-space.

The C++ code just uses an array of floats for the vectors (hence the loop). In C# this can easily be translated to:



// BoundingSphere class mainly hold Vector3 position (and getter/setter property)
// as well as float radius (plus getter/setter property)

// AxisAlignedBoundingBox class holds Vector3 min and Vector3 max and the following static member function for example:

// also a little more verbose for clarity
public static bool Overlap ( AxisAlignedBoundingBox aabb, BoundingSphere sphere) {

float squaredDistance = 0;

// process X
if (sphere.Position.X < aabb.Min.X) {
float diff = sphere.Position.X - aabb.Min.X;
squaredDistance += diff * diff;
}

else if (sphere.Position.X > aabb.Max.X) {
float diff = sphere.Position.X - aabb.Max.X;
squaredDistance += diff * diff;
}

// process Y
if (sphere.Position.Y < aabb.Min.Y) {
float diff = sphere.Position.Y - aabb.Min.Y;
squaredDistance += diff * diff;
}

else if (sphere.Position.Y > aabb.Max.Y) {
float diff = sphere.Position.Y - aabb.Max.Y;
squaredDistance += diff * diff;
}

// process Z
if (sphere.Position.Z < aabb.Min.Z) {
float diff = sphere.Position.Z - aabb.Min.Z;
squaredDistance += diff * diff;
}

else if (sphere.Position.Z > aabb.Max.Z) {
float diff = sphere.Position.Z - aabb.Max.Z;
squaredDistance += diff * diff;
}

return squaredDistance <= sphere.Radius;
}



HTH,
Pat.

Share this post


Link to post
Share on other sites
what this algorithm basicall does is this

you do a C AABB distance check

if for example C.x is inside the boundingbox's x range you can ignore it and imagine it as a 2d test for the y z axis only

so now if the y lies within the y range of your aabb you only need to take care of the z axis

in this case if C.z 's distance to the aabb is b.max.z+r or b.min.z-r it touches the top or the bottom plane

this gives you a exact collision since you can take care of sphere-aabbedge collisions

other approches simply create a sphere around the aabb which is a pretty unprecise collision

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement