Sign in to follow this  
rXpSwiss

Difference between distance based collision and bounding box collision

Recommended Posts

Hi,

What is the big difference between the distance based collision detection way and the bounding box way ? I know the distance based use the right triangle to calculate the distance between the two objects therefore is it more slow but what is the plus ?
The bounding box way takes two rect and look if they are overlapping and the distance way look the distance between the two but in the end it is the same thing ?
I see it that way :
Bounding Box :
[img]http://img35.imageshack.us/img35/5384/unledkb.jpg[/img]


Distance based collision :
[img]http://img194.imageshack.us/img194/2963/unled2cm.jpg[/img]



What didn't I get ?

Best regards,

rXp>!<

Share this post


Link to post
Share on other sites
The difference is that one is a spherical detection whilst the other is rectangular.
It comes down to what is best suited for the object.

Share this post


Link to post
Share on other sites
[quote name='Molle85' timestamp='1311345615' post='4838923']
The difference is that one is a spherical detection whilst the other is rectangular.
It comes down to what is best suited for the object.
[/quote]

Yes but the size of the sprite is still height x width size... so square... so no difference ?

Share this post


Link to post
Share on other sites
In the 2-dimensional case there isn't any difference.

Edit: For clarification, there isn't any difference when testing for collision as in your example. Actual differences, however, depend upon context. Are you just testing rectangles, or do your entities represent characters? A typical humanoid shape character can be approximated in 3D space using either a cylinder (based on the distance-based collision metric) or a box (the bounding box metric), in which case the response of the system will be slightly different. However, since a cylinder projected from the side into 2D space is just a box, then there is really no difference between the two methods as long as you are only dealing in 2D.

Share this post


Link to post
Share on other sites
I think with distance based collision detection you can get more accurate collisions where as with using just bounding box collision detection you can get a collision but visually you shouldn't have.

I may be wrong about this though as this is just a theory I haven't experimented too much with collision detection.

Share this post


Link to post
Share on other sites
That is not always true, you can have a sprite that is 10 wide and 100 high, if you draw a circle around that you'll see that it's not very precise.
You usually test the distance to see if you should use more advanced detection.

Share this post


Link to post
Share on other sites
The big benefit I can see right away (having never done this before) is the distance method should be adaptable to space simulations where you are already using distance everywhere for gravitational calculations. I assume you could also use the same method for a collision style that causes rapid deceleration rather than abrupt collision (think bubbles). Also, a brief glance around on the subject seems to indicate that distance based is very useful for soft-body objects.

Share this post


Link to post
Share on other sites
The difference is that distance is circular in 2D and spherical in 3D, not square or rectangular like a bounding box.

So on your bottom example, those would be two circles. One with a radius of 2, and the other with a radius of 1. The pythagorean theorem determines the distance between the two as a linear value, instead of a vector of XYZ values, and that distance is used by checking if it's less than the sum of the radii of the two objects in question.

Bounding boxes check the XYZ independently, whereas distance combines XYZ using pythagorean resulting in the circular or spherical check.

[img]http://www.van-noland.com/img/distance.jpg[/img]

Share this post


Link to post
Share on other sites
You usually select the type of bounding primitive based on the object you want to represent. Spheres, Cylinders, Boxes, etc, all have specific cases where they work better. There is usually no one-solution-for-all approach.

As Molle85 said, distance is usually used for elimination of candidates for collision detection.

Share this post


Link to post
Share on other sites
[img]http://img683.imageshack.us/img683/6730/unledqrg.png[/img]


Here's an example where it's pretty clear when to use what.
Hope you appreciate my awesome cloud painting skills :P

Share this post


Link to post
Share on other sites
[quote name='Molle85' timestamp='1311347517' post='4838958']
[img]http://img683.imageshack.us/img683/6730/unledqrg.png[/img]


Here's an example where it's pretty clear when to use what.
Hope you appreciate my awesome cloud painting skills :P
[/quote]




Microsoft should have hired you for their bootscreen graphic. just throw a RGBY microsoft windows swazi on there.


In my 3D projects I typically use spherical (distance) and cylindrical volumes for everything. In Molle's example the bounding circle/sphere is set on the outer-most point of whatever object it represents the collision volume of, in my experience I try to find a happy medium because there are no simple shapes that accurately depict the collision area of any of the objects I typically use in my projects. So instead I will use a bounding sphere that is actually smaller than the model so there aren't large areas where collision will be occuring without the model actually touching anything, or sometimes combinations of bounding volumes for different collision checks. This also can result in the farther portions of the model going through stuff to a degree, but like I said it's a happy medium.

Most especially I use distance checking because you can avoid its slowness by NOT doing the square root and simply squaring the other side of the equation..


As for bounding boxes, do you really think they are really any more accurate ? They are actually slower than a distance check because the CPU is making two variable comparisons, provided that you optimize your distance check to not use the squareroot.

So for example:

[code]

//here's your typical pythagorean distance check

objectA.position = [1, 2];
objectA.radius = 5;
objectB.position = [12, 4];
objectB.radius = 6;

radiisum = objectA.radius + objectB.radius;
delta = | objectA.position - objectB.position |;

//pythag
distance = sqrt(delta.x * delta.x + delta.y * delta.y);


if(distance < radiisum)
colliding();

[/code]

but to eliminate the slowness of square root calls (in projects where I have many objects that I am comparing for collisions with) I would do this:

[code]

//square-rootless distance check

objectA.position = [1, 2];
objectA.radius = 5;
objectB.position = [12, 4];
objectB.radius = 6;

radiisum = objectA.radius + objectB.radius;
delta = | objectA.position - objectB.position |;

//pythag without the sqrt
distancesqr = delta.x * delta.x + delta.y * delta.y;

radiisumsqr = radiisum * radiisum ;

if(distancesqr < radiisumsqr)
colliding();

[/code]

The end result is the same and I did it without a square root call!

If you wanted to get fancy, use a distance check like this between your sprites to see if they could potentially be colliding, then do a per-pixel collision check ;) then you'd be uberleet gamedev guy.

Share this post


Link to post
Share on other sites
Thank you for all your answers but a little followup question : What if you have to check a 2D collision between the arrow and the cloud... what do you use ?

Share this post


Link to post
Share on other sites
Hi again,

I put a little method together to be able to check the collision between a rectangle and a round object...
Sure it needs resources but could be useful right ?

[img]http://img32.imageshack.us/img32/5363/unledtzt.png[/img]

<div>[code]</div><div>bool Physics::IsCollidingRectRound(MySprite *rect, MySprite *round)</div><div>{</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//exp</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>float exp = 2;</div><div><br></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//rectangle&nbsp;</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>STRUCT_Location location = rect-&gt;getLocation();</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>STRUCT_Size size = rect-&gt;getSize();</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>float scaling = rect-&gt;getScaling();</div><div><br></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//round</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>float radius2 = 0;</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>STRUCT_Location location2 = round-&gt;getLocation();</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>float scaling2 = round-&gt;getScaling();</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>STRUCT_Size size2 = round-&gt;getSize();</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//get the radius</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>if(size2.height &gt; size2.width)</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>radius2 = (size2.height * scaling2) / 2;</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>else</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>radius2 = (size2.width * scaling2) / 2;</div><div><br></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//get the x distance between the 2 center points</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>float x = (location.x + size.width/2) - (location2.x + size2.width/2);</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>if (x &lt; 0)</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>x = x * -1;</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//get the y distance between the 2 center points</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>float y = (location.y + size.height/2) - (location2.y + size2.height/2);</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>if(y&lt;0)</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>y = y * -1;</div><div><br></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//get the angle</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>float angle = atan(y/x) * 180 / PI;</div><div><br></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//get the radius of the rect object</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>float rectRadius = (size.width/2)/cos(angle*PI/180);</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//get the biggest radius possible</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>float biggestRadiusPossible = pow(size.width/2,exp) + pow(size.height/2,exp);</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//if the wrong angle is used</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>if(rectRadius &lt; 0 || pow(rectRadius,exp) &gt; biggestRadiusPossible)</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>{</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//get the radius of the rect object</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>rectRadius = (size.height/2)/sin(angle*PI/180);</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>}</div><div><br></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//get the hypotenus^2</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>float hyp = pow(y,exp) + pow(x,exp);</div><div><br></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//add the 2 radius</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>float radiusAdd = pow(rectRadius, exp) + pow(radius2, exp);</div><div><br></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>if(radiusAdd &lt; hyp)</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>return false;</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>else return true;</div><div>}[/code]<br></div>

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this