Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Detecting collisions

Posted on 2005-05-06
41
Medium Priority
?
329 Views
Last Modified: 2012-05-05
Hey,

I have a load of models. But for the sake of this question, we'll just imagine that I have two models. These models are always cuboids, expressed in terms of top-left-front coord, and bottom-right-rear co-ordinate, i.e:

(x1,y1,z1)
        ___________
       |                  |\
       |                  | \
       |                  |  \
       |                  |   \
       |                  |    |
       |__________|     |
        \                  \    |
          \                  \  |
            \                  \|
              ---------------
                                (x1',y1',z1')


(x2,y2,z2)
        ___________
       |                  |\
       |                  | \
       |                  |  \
       |                  |   \
       |                  |    |
       |__________|     |
        \                  \    |
          \                  \  |
            \                  \|
              ---------------
                                (x2',y2',z2')


I need an algorithm to detect whether or not these two models come within a certain distance of eachother (in any of the dimensions).

What's the simplest way to do this? My attempts are incorrect.   :-(

Thank you in advance!
Rob.
0
Comment
Question by:InteractiveMind
  • 11
  • 9
  • 7
  • +4
41 Comments
 
LVL 27

Expert Comment

by:aburr
ID: 13948732
Create array of points inside cube 1 and an array inside cube 2.
Test to see if any are equal. If so – collision.
You can make it equal within any margin you want
This is a simple by not particularly efficient method.
0
 
LVL 27

Expert Comment

by:aburr
ID: 13948750
More efficient but less simple
Create array of points inside cube 2 (typically PC@(x,y,z)
Test all x components. If x less than x1 and greater than x’1     next test
                                     If not – collision
-
Then test y component
Then test z component
0
 
LVL 23

Expert Comment

by:Mysidia
ID: 13948765
How simple?

I guess there's a faster way, if you take better advantage of the arrangements
of the sides and how cubes are put together,
but for two cubes:

Check the positions of the corners, to see if they intersect  (then distance is <= 0).

If the models don't intersect, take each face of each model.

From here this reduces to a problem of computing the distance between
two pieces of planes...

Find the two nearest points on both pieces, compute the distance between
them in 3 dimensions store that minimum distance in a list.

Repeat with all pairs of boundary (plane pieces) of the cubes

for two cubes there will be 6*6 = 36 pairs  to check

the smallest number in the list is the distance.
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 27

Expert Comment

by:aburr
ID: 13948771
With appropriate scaling, this can all be done with integer arithmetic
0
 
LVL 27

Expert Comment

by:aburr
ID: 13948805
I think this will work without arrays

Test  if x2 less than x1 + x’2 and greater than x1 + x’1    next test
          If not – collision
Repeat for y and z    
(Note I have used 1, 2 and ‘ correctly)
0
 
LVL 27

Expert Comment

by:aburr
ID: 13948835
If you want a buffer zone, just test on a cube enlarged by the buffer zone
0
 
LVL 27

Expert Comment

by:aburr
ID: 13949135
My third way is incorrect correction coming
0
 
LVL 27

Expert Comment

by:aburr
ID: 13949163
Try this

Test
      if x2 less than x1 + x’2 and greater than x1 + x’1    no collision
            if not     test y
      if y passes test     no collision
            if not      test z
      if z passes test       no collision
            if not      collision
0
 
LVL 85

Expert Comment

by:ozo
ID: 13949653
Without loss of generality, let x1<x1', y1<y1', z1<z1',x2<x2', y2<y2', z2<z2'
then compare the point (x1-x1,y1-y1,z1-z1) = (0,0,0) with the box
from (x2-x1',y2-y1',z2-z1') to (x2'-x1,y2'-y1,z2'-z1)
0
 
LVL 85

Expert Comment

by:ozo
ID: 13949698
The distance between the cuboids would not change if you make one smaller by x1'-x1,y1'-y1,z1'-z1 and the other larger by x1'-x1,y1'-y1,z1'-z1, and shift the origin by -x1,-y1,-z1
This reduces the problem to determining the distance from a single cuboid to the origin
0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 13950988
If the cubes are defined by their centers cube1=(Cx,Cy,Cz) and cube2=(cx,cy,cz) and the lengths of the sides are cube1=S and cube2=s then cube2 intersects cube1 if its center lays within the cube defined by center=(Cx,Cy,Cz) and sides= S+s.

Hence for collision we require (where Abs() means absolute value)

    Abs(Cx-cx)<(S+s)/2  AND  Abs(Cy-cy)<(S+s)/2  AND  abs(Cz-cz)<(S+s)/2

    else no collision.



(
For your cube definition  

(Cx,Cy,Cz) = ((x1'+x1)/2 , (y1'+y1)/2, (z1'+z1)/2)
(cx,cy,cz)  =  ((x2'+x2)/2 , (y2'+y2)/2, (z2'+z2)/2)
 
S=x1-x1'
s=x2-x2'  
)
0
 
LVL 37

Expert Comment

by:Harisha M G
ID: 13952851
Hi InteractiveMind,
    The best method would be to check whether the centres of the cuboids are near enough for the collision...

    I mean, first consider the centres of both of them...
    (x1'+x1)/2, (y1'+y1)/2, (z1'+z1)/2 = (a,b,c) .. say
    and
    (x2'+x2)/2, (y2'+y2)/2, (z2'+z2)/2 = (p,q,r) .. say

    Now check whether sqrt( (p-a)² + (q-b)² + (r-c)² ) is less than some constant.

    If it is less, then they are going to collide.
    (This method best fits for spheres and you will have to check for further conditions if it is a cuboid)..

    If you are interested, I will tell more!!

Bye
---
Harish
0
 
LVL 25

Author Comment

by:InteractiveMind
ID: 13954660
Thanks everyone.

Harish,

yes, I'd like to know more.  :-)

I can't seem to figure out how to calculate the distance along each axis, from what you've done so far; please help.

Cheers,
Rob.
0
 
LVL 37

Expert Comment

by:Harisha M G
ID: 13954667
sqrt( (p-a)² + (q-b)² + (r-c)² )

Gives the distance....

Since you have cuboids, you will have to check the coordinates in case the objects are near enough in the above test
0
 
LVL 23

Expert Comment

by:Mysidia
ID: 13954808
That will get you the distance between the centers of the cubes.
A shortest distance between the two cubes will be on the same line, since your
cube can fit in a sphere.

Collision can be at a point (one of the cube's 8 vertices)  on a line (one of the 12 edges)
or on a surface (one of the 6 faces)

The shortest distance from the center of a cube to any of the vertices is the
same.   The distance from the center to any of the edges is the same.

That leaves say the collision of say a vertex of one cube and a place somewhere on the
interior surface (other than the middle or the sides)  of the second cube.

The length of the line to the center will be different than at the edges and the middle, and just
the coordinates of the point at the center won't include this information about how the two cubes
are oriented with respect to one another, and how their sizes compare to one another.

So you overestimate the distance, because the distance from this point on the middle of a face of
the cube's the center is a longer length, but this orientation detail has no bearing no the actual
least distance between the two objects...
0
 
LVL 85

Expert Comment

by:ozo
ID: 13954864
Distance along x = 0 if abs((x1+x1')/2 - (x2+x2')/2) - abs(x1-x1')+abs(x2-x2') < 0
                           else  abs((x1+x1')/2 - (x2+x2')/2) - abs(x1-x1')+abs(x2-x2')
Total distance =
sqrt((distance along x)² + (distance along y)² + (distance along z)²)
0
 
LVL 25

Author Comment

by:InteractiveMind
ID: 13954893
Ozo,

So, to calculate the distance between the models faces, along the x-axis, I would use the following?

if ( abs((x1+x1')/2 - (x2+x2')/2) - abs(x1-x1')+abs(x2-x2') < 0 )
   x = 0
else
   x = abs((x1+x1')/2 - (x2+x2')/2) - abs(x1-x1')+abs(x2-x2')


??

Cheers.
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 13954901
The simplest way to do it would be to ditch your cuboids and go with bounding spheres.

The distance between two spheres is trivial.  It's the distance between the centers of the spheres minus the sum of the radii of the spheres.  i.e. distance = sqrt((x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2) - r1 - r2.

To get the true distance between two cuboids, you have to consider the surface of constant distance from the cuboid.  This surface is the outer surface of the union of the following volumes:

1.  8 spheres of radius d/2 centered on each corner.
2.  12 cylinders of radius d/2 centered on each edge.
3.  6 additional cuboids expanding from each face of the original cuboid by a distance d/2.
4.  The original cuboid.

To precisely check if two cuboids are within distance d of each other, you need to determine if any of these 27 simple geometric objects for one cuboid intersect with any of the 27 volumes of the other cuboid.  
0
 
LVL 37

Expert Comment

by:Harisha M G
ID: 13954909
>  The simplest way to do it would be to ditch your cuboids and go with bounding spheres.

That is what I was telling
0
 
LVL 25

Author Comment

by:InteractiveMind
ID: 13954921
Okay, I can sort of see the logic to that ... I'm just a little confused, as to what the value of the spheres radius would be? Would it be the biggest length of the cuboid?
0
 
LVL 25

Author Comment

by:InteractiveMind
ID: 13954933
..Or, have I mis-interpreted your idea? :o\
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 13954935
That's not what you said.  
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 13954943
InteractiveMind:
I'm guessing that you're using the cuboids as a bounding surface for more complex geometric objects, maybe for some  kind of 3-d game.  I'm suggesting you use spheres for bounding surfaces instead of cuboids since the checks are so complex.  That, or tell us what kind of approximations you are willing to accept for the distance calculation.
0
 
LVL 37

Expert Comment

by:Harisha M G
ID: 13954963
Look at this figure

            A ____________________________  D
             /                                                /|
           /                                                /  |
     B  /                        O                 C   /    |
        |¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ |   /   H
        |                                                |  /
        |                                                |/
    F    ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯   G
 
Now clearly AG is the largest distance... do you agree ?

Now let O is the centre of one cuboid...

And let "d/2" be its distance from A, B, ... H (In other words, let d be the diagonal length)
So, If two cuboids have to touch, their centres can atmost be at a distance of "d"
0
 
LVL 25

Author Comment

by:InteractiveMind
ID: 13954969
You're correct that it's for a 3D game; The higher the accuracy the better, obviously, but I'm not really willing to sacrifice too much computational power/time for accuracy.. So, which ever solution you feel is better suited for this would be fine.

If I should go for the sphere-solution, then I need someone to quickly run over it with me quickly -- I'm a little confused about it.

Thank you,
Rob.
0
 
LVL 37

Expert Comment

by:Harisha M G
ID: 13954990
I think you are asking it for your "Ping" game...

If so.. I can provide you with a code in C++ which is similar to that...
0
 
LVL 25

Author Comment

by:InteractiveMind
ID: 13954992
Harish,

By looking at that, I can see the AG is the largest length, but how could I programmatically calculate the longest distance? Would I just need to use the sqrt( x^2 + y^2 + z^2 ) for it?

Also, once I've found 'd', would that represent the diameter of the sphere?
0
 
LVL 25

Author Comment

by:InteractiveMind
ID: 13954993
Harish,
No, I've finished that game  ^_^  I'm moving onto something a bit more advanced; which requires movement in 3 dimensions, as opposed to boring 2D  :-)
0
 
LVL 37

Expert Comment

by:Harisha M G
ID: 13955000
sqrt( (x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 )
0
 
LVL 37

Expert Comment

by:Harisha M G
ID: 13955005
Tell us what you are looking for... instead of just saying two cuboids are colliding...
0
 
LVL 37

Expert Comment

by:Harisha M G
ID: 13955008
sqrt( (x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 )

where x1 & x2 are the x coordinates of any two opposite corners... and so on..
0
 
LVL 25

Author Comment

by:InteractiveMind
ID: 13955021
Okay, I'm developing a 3D game, and for it, I've got to create my own Collision Detection System. In this 3D universe of mine, I have a load of cuboids.

I need to detect whether any of these cuboids come within a certain distance of eachother (in any of the 3 Dimensions). The distance between the cuboids, would be the face-to-face distance. The cuboids cannot rotate, just move along the 3 dimensions.

I figured that I'd need to calculate the x, y and z distances between each cuboid; if the distance is less than or equal to a constant, then I need to do something..

Any ideas?

Thanks,
Rob.

P.S.  I'll be back in about 30 minutes. Cheers.
0
 
LVL 37

Expert Comment

by:Harisha M G
ID: 13955023
Not only AG.. BH, CE and DF are also of largest length and are equal
0
 
LVL 37

Accepted Solution

by:
Harisha M G earned 2000 total points
ID: 13955070
OOP is better for this situation...

and as NovaDenizen has told, you better use spheres as they are to be handled...
 
Assuming you are creating in C++/Java...

Create a class of spheres with centre and radius as its members.

If c1 and c2 are circles

Then you can easily check whether they are colliding by checking for
sqrt( (c1.x-c2.x)^2 + (c1.y-c2.y)^2 + (c1.z-c2.z)^2 ) <= c1.r + c2.r

And when you have more objects, you can use arrays

sqrt( (c[1].x-c[2].x)^2 + (c[1].y-c[2].y)^2 + (c[1].z-c[2].z)^2 ) <= c[1].r + c[2].r

Since they are the function of indices, you can easily create function like this...
(I am using C++ syntax)

bool touch(mysphere c1, mysphere c2)
{
    if( sqrt( (c1.x-c2.x)*(c1.x-c2.x) + (c1.y-c2.y)*(c1.y-c2.y) + (c1.z-c2.z)*(c1.z-c2.z) ) <= c[1].r + c[2].r)
        return true;
    else
        return false;
}

And then you can call the function using loops...

mysphere c[10];
....

for(i=0;i<10;i++)
    for(j=0;j<10;j++)
         if(i==j) continue;
         else
             if(touch(c[i],c[j])
             {
                    .....
             }

0
 
LVL 25

Author Comment

by:InteractiveMind
ID: 13955120
Fab! :-)

Thank you everyone.
0
 
LVL 37

Expert Comment

by:Harisha M G
ID: 13955158
Thank you
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 13956218
I know points are already awarded and everything, and I argued against the use of cuboids in favor of spheres, but I thought of a fairly simple way to measure the distance between cuboids.  

double find_1d_dist(double min1, double max1, double min2, double max2) {
    if (max1 < min2) {   // no intersection
        return min2 - max1;
    } else if (max2 < min1) { // no intersection
        return min1 - max2;
    } else {
        return 0; // they intersect in this dimension
    }
}
// it is assumed that x1 <= x2, y1 <= y2, and z1 <= z2
struct cuboid { double x1,x2,y1,y2,z1,z2;};

// returns 0 when cuboids overlap or are in contact, distance otherwise.
// as an optimization, you might want to leave out the sqrt and just test against the squared distance.
double find_cuboid_distance(const struct cuboid *c1, const struct cuboid *c2) {
    double xdist, ydist, zdist;
    xdist = find_1d_dist(c1->x1, c1->x2, c2->x1, c2->x2);
    ydist = find_1d_dist(c1->y1, c1->y2, c2->y1, c2->y2);
    xdist = find_1d_dist(c1->z1, c1->z2, c2->z1, c2->z2);
    return sqrt(xdist*xdist + ydist*ydist + zdist*zdist);
}
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 13956229
er, that last "xdist = " should be "zdist = ".
0
 
LVL 85

Expert Comment

by:ozo
ID: 13956435
Sorry,
abs((x1+x1')/2 - (x2+x2')/2) - (abs(x1-x1')+abs(x2-x2'))
should have been
abs((x1+x1')/2 - (x2+x2')/2) - (abs(x1-x1')+abs(x2-x2'))/2
which, when x1<x1' and x2<x2', would be equivalent to
(abs((x1+x1') - (x2+x2')) - ((x1'-x1)+(x2'-x2')))/2
so
max( (abs((x1+x1') - (x2+x2')) - ((x1'-x1)+(x2'-x2)))/2, 0 )
is the same as
max( ((x1+x1')-(x2+x2')-((x1'-x1)+(x2'-x2)))/2, ((x2+x2')-(x1+x1')-((x1'-x1)+(x2'-x2)))/2, 0 )
=
max( ( x1+x1'  -x2-x2'   -x1'+x1  -x2'+x2  )/2, ( x2+x2'  -x1-x1'  -x1'+x1   -x2'+x2  )/2, 0 )
=
max( ( x1         -x2'       +x1  -x2'     )/2, ( x2         -x1'  -x1'          +x2  )/2, 0 )
=
max( x1-x2', x2-x1', 0 )
which can also be evaluated as
    if (x1' < x2) {   // no intersection
        return x2 - x1';
    } else if (x2' < x1) { // no intersection
        return x1 - x2';
    } else {
        return 0; // they intersect in this dimension
    }
0
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 13957139
..I am at loss as to why you have accepted an answer for collidng spheres when a variety of solutions for cuboids were given.  Cuboid collision is not difficult and does not involve any floating point mutliplication unlike sphere collsion. I feel you have been badly advised.
0
 
LVL 23

Expert Comment

by:Mysidia
ID: 13957360
re: GwynforWeb
I have to agree, and in retrospect, I like your solution best.. although you didn't mention
how to get it for a specified distance apart (that's trivial): use of cuboid collision
over sphere-bounding for detection has the advantages you mention, and the
advantages are important and significant in a real time application like a 3D game,
where speed matters:  integer math is usually preferable to floating point math,
because it is much faster.

Since (x,y,z)  coordinates are used, IMO: the author had right idea of using cubes
for bounding in the beginning.

[Spheres for bounding might have offered a better choice if he had an application
where he had chosen to use (radius,angle-degrees,height) coordinates or similar to
represent position, but he was not]

The sphere solution, although it was less efficient and a poor choice taking that
realistic technical consideration into account, I guess, was probably more
tempting: it's a little easier for people to recognize from an elementary
math/geometry perspective,  in my estimation.

Maybe that meant it was simpler: I don't know
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: Nicole
This is a research brief on the potential colonization of humans on Mars.
When we purchase storage, we typically are advertised storage of 500GB, 1TB, 2TB and so on. However, when you actually install it into your computer, your 500GB HDD will actually show up as 465GB. Why? It has to do with the way people and computers…
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

572 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question