asked on

Detecting collisions

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.

aburr

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.

aburr

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

Mysidia

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.

aburr

With appropriate scaling, this can all be done with integer arithmetic

aburr

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)

aburr

If you want a buffer zone, just test on a cube enlarged by the buffer zone

aburr

My third way is incorrect correction coming

aburr

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

ozo

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)

ozo

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

GwynforWeb

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'
)

Harisha M G

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

InteractiveMind

ASKER

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.

Harisha M G

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

Mysidia

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...

ozo

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)²)

InteractiveMind

ASKER

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.

NovaDenizen

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.

Harisha M G

> The simplest way to do it would be to ditch your cuboids and go with bounding spheres.

That is what I was telling

InteractiveMind

ASKER

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?

InteractiveMind

ASKER

..Or, have I mis-interpreted your idea? :o\

NovaDenizen

That's not what you said.

NovaDenizen

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.

Harisha M G

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"

InteractiveMind

ASKER

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.

Harisha M G

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...

InteractiveMind

ASKER

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?

InteractiveMind

ASKER

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 :-)

Harisha M G

sqrt( (x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 )

Harisha M G

Tell us what you are looking for... instead of just saying two cuboids are colliding...

Harisha M G

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..

InteractiveMind

ASKER

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.

Harisha M G

Not only AG.. BH, CE and DF are also of largest length and are equal

ASKER CERTIFIED SOLUTION

Harisha M G

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

InteractiveMind

ASKER

Fab! :-)

Thank you everyone.

Harisha M G

Thank you

NovaDenizen

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);
}

NovaDenizen

er, that last "xdist = " should be "zdist = ".

ozo

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
}

GwynforWeb

..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.

Mysidia

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