# Collision Detection

I'm having some problems with collision detection here:

I have 2 cars viewed from above, so I want 2d collision detection on them while there actualy 3d, and those cars can rotate in any degree.

From those cars, I have following data:
* Their centerpoint(x,z; y is height) around which they rotate,
* Their rotation angle,
* Their lenght and width

There is of course the simple collision detection between to rectangles (=lenghts and widths), but you already see this would be a bad detection method cause when rotating, the rectangle is not straight anymore.

Therefore I'm looking for a (mathematical, but functional would be much better for me) collision detection between rotatable rectangles that is perfect.

Can anyone help me with that ?

Egsoc
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
Not sure what you mean by 'not straight anymore', probably that they are no longer aligned at x- and y-axis, but that is not that much of a problem.

I would suggest a 2-stage approach. Step one determines, if there is a possible collision and step two then determines the whether there actually is a collision.

Step 1: calculate the distance between both center points and compare it to the sum of diagonals of both cars divided by 2. if( distance <= ( d1 + d2 ) / 2 ) a possible collision has occured. To speed up the process you can use the square of both sides of the inequation to avoid the computationally rather expensive square roots.

Step 2: only necessary, if the test in Step 1 was successful. Check all 4 corners of car 1 if it is inside car 2.

There are however potential problems. The biggest one being that one of the cars could be so fast, that it goes right through the other car, without noticing it, i.e. the collision occurs between two calls to your detection function. This is rather hard to solve. One way to go would be to make your physics engine run at a constant rate independant of the rendering.

.f
0
Author Commented:
Well, with -Not straight anymore- I meant that the car (and so also the rectangle) can be rotated any degree.

So if there are 2 cars, one could be rotated like 20° and the other one 96° for example.

It's here where the problem begins.

I have a function to get the distance between the 2 centers but I don't know how to first calculate 4 points of a car when it's rotated and then what to test them with on the other car.

I was thinking about it and came up with the idea to pretend the car was driving only halve as fast and calculate collisions based on that. That would make the detection twice as refined.

Egsoc
0
Commented:
Ok, about the rotation. Let's assume that a rotation angle of 0 refers to a car going into positive x-direction and positive rotation angles are counter-clockwise. Calculating the four corners (left-front, right-front, left-rear, right-rear) will then be:

float s = sin( rot_angle );
float c = cos( rot_angle );

float l = length / 2;
float w = width / 2;

float lfx = x + l * c - w * s;
float lfy = y + l * s + w * c;
float rfx = x + l * c + w * s;
float rfy = y + l * s - w * c;
float lrx = x - l * c - w * s;
float lry = y - l * s + w * c;
float rrx = x - l * c + w * s;
float rry = y - l * s - w * c;

With those 4 corners you can set up equations for for all 4 sides of the car, according to y - mx - c = 0, with m being dy/dx [be sure to include special handling for dx == 0]. The next step would be to feed the corners of car1 into the equations for all 4 sides of car2 and if they have the same sign, this corner is _insides_ car2, else it is not. Do this for all 4 corners or until one corner is inside the other car.

A note on the fast-car-problem: Make sure to time your calculations in such a manner, that between 2 consecutive executions the maximum distance travelled is less than the smaller value of width and length.

Hope this helps. It certainly isn't the fastest possible solution, but the second [computationally expensive] step will rarely have to be executed when using the [rather cheap] distance calculation described above, befor devling into the trig-jungle.

.f
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Author Commented:
That is very clear.

If I understood well; the equation for each side of car2 would be YPos MINUS (?) MULTIPLY XPos MINUS Cosinus.
I didn't realy see what -dy- and -dx- are...

Also, What is the sign of a point of car1 ? And how do you get the sign of an equation ?

I'm getting there...Finally...:)

Egsoc

NB: I think anyone can see I'm not exactly a mathematical genius...
0
Commented:
Ooops, I assumed you were using c/c++, without even checking back. What language are you using? Looks like some sort of BASIC, would that be correct? I hope you can still understand the equations above and transform them to your programming language.

About dx and dy, they are distances in x- and y-direction. Let's say we have two points (x1, y1) and (x2, y2) then dx and dy would be (x2 - x1) and (y2 - y1) respectively. So if you want the equation for the right side of the car, choose the points (rfx, rfy) and (rrx, rry), calculate dx and dy, make sure that dx isn't equal to 0 and you will get m, the slope. If dx or dy is equal to 0, this indicates that your car is aligned at x and y axis', i.e. the rotation angle is 0, 90, 180, or 270 degrees. Calculations will be simpler and you don't have to use sin/cos then, just draw an image of the car on a piece of paper and you will see where to put plus and minus signs to check the corners of car1. If dx is not equal to 0, you still need to calculate c for your line equation. To do so, just feed your second point into the line equation and solve for c, i.e. c = y - mx. Now, you are all set to test the four corners of car1 against all four sides of car2, resulting in 4 (sides) * 4 (corners) * 2 (x and y coordinates) = 32 calculations.

To get the sign (positive/negative) of a number there is a function sgn( some_number ) in c/c++, and there most likely is one in your language, too. If I'm wrong here, you can always use

if( some_number < 0 )
// some_number is negative
else
// some_number is 0 or positive

Hope that gets you a step closer to your goal. A few hints: A piece of paper and a pen do wonders when dealing with 2d geometry. Also, check out some geometry tutorials on the web. You will need to get a basic understanding of the concepts throughout the development of the game.

.f
0
Author Commented:
I use Visual Basic,
-YPos MINUS (?) MULTIPLY XPos MINUS Cosinus- I wrote so there would be no confusion between the mathematics and the coordinates.

I'm currently studying your answers and I'm working on a procedure based on it, that will arrange my Collision Detection.

Egsoc
0
Author Commented:
if( distance <= ( d1 + d2 ) / 2 )
how you calculate those diagonals?
Can I just calculate the points as if the car wasn't rotated.

I'm now thinking diagonals are static but you never now on computers.

Egsoc
0
Commented:
Unless you allow deformations your car diagonals are static, so you can just calculate them once when initializing the car object. Use the easiest form for calculation, i.e. when the car isn't rotated. d1 would then be calculated like this:

d1 = square_root( length1 * length1 + width1 * width1 );

or

d1 = square_root( length1 ^ 2 + width1 ^ 2 );

Since the square root is computationally expensive I suggested that you compare the squared distances to the squared diagonal, although you don't have to. If you are not using it thousands of time each second you would most likely not notice anyway.

.f
0
Author Commented:
A now I also hava following question:

You said ...if they have the same sign...;
I assumed you meant c (=result of feeding a point to the equation) but where does the second sign comes from?

Egsoc
0
Commented:
There seems to be a misunderstanding. c is part of the line equation and you have to calculate it by solving the equation, using either the first or the second point of the line. Then you will be able to feed in the points of the second car and the equation (y - mx - c) will return 0, if the point lies on the line, or a positive/negative number. Those numbers on the right hand side is what you are interested in.

.f
0
Author Commented:
Well, once I had 17% on a maths exam, so I'm letting the number speak...

This is what I wrote to feed 1 point to 1 equation (in VB):
If Sgn(h.LF_Z - ((g.LF_Z - g.LB_Z) / IIf(g.LF_X - g.LB_X = 0, 1, g.LF_X - g.LB_X)) * h.LF_X) Then CollisionDetection = True
G and H stand for the cars here, then there are L-eft, R-ight, F-ront & B-ack.

Because above you once wrote: c = y - mx.

What I understand now is:
Y-mX-c is the equation.
c is the missing x you get when solving the equation.
Solving the equation again with c included results into a number which sign will be compared with the sign of the equation (=the sign of m as I recall from when I was in my 5th year of highschool).

I realy hope I have it right this time

Eric
0
Author Commented:
Now I wrote some illustration of the above comment:
(in VB)

d = (g.LF_Z - g.LB_Z) / IIf(g.LF_X - g.LB_X = 0, 1, g.LF_X - g.LB_X)
e = h.LF_Z - d * h.LF_X
If Sgn(h.LF_Z - d * h.LF_X - e) = Sgn(d) Then CollisionDetection = True

Where d is the DY/DX (above called m),
e = Result of the equation with missing e or what above is called c,
Then I compared the sign of the solved equation with the sign of d.

Egsoc (=Eric indeed, was more thinking about the code)
0
Commented:
I have an important comment to make that could speed up some things, or perhaps make things more complicated.

Have you ever considered using ray-point intersection (its sort of like ray-plane intersection)? Although  you may not have heard of it, it seems likely to work. Also you can calculate distances WITHOUT using a square root function. The distances end up in points on the ray.

Here are some equasions to calculate points on a ray or convert raypoints to real points:

PointOnRay=RayStart+(t * RayDirection)

Where PointOnRay is an X,Y value;
RayStart is the start of your ray in X, Y values;
t is an integer from 0 to infinity that represents a distance in ray-points from the start (0).(it can be negative, though, but you won't be dealing with that for distances)
Finally, RayDirection is an X,Y value indicating the direction of the ray. Try using something like values between 0.0 and 1.0. You can easily calculate this by getting the (for X: ) cosine of (Angle Of Rotation) and the (for Y: ) sine of (Angle of Rotation), where Angle of Rotation is the angle of rotation that the point has moved for that side of the box. (note that is only ONE corner's rotation. for the others, you can get the inverse of cosine,sine of the x,y dist (must be positive) that is normalized so that it is not greater than 1 or less than -1. You do this by subtracting the integer form (no decimals) of the distance from the floating point form (with decimal values) of the distance.)

I'll have to get back to this later, as I am out of time, but there are some very good articles on this at
www.gamedev.net

RageDBL
0
Author Commented:
Well, I'm currently constructing an algoritm based on the comments above, and I also did a lot of research on the internet.
There I found information about a line that starts at a point and runs perpendicular on the X-axis.
I'm not sure if thats what is meant by ray-collision-detection, but it could be.

Egsoc
0
Commented:
If you want it really explained well, then go to www.gamedev.net and find the article under collision detection called 'Collision Detection using Epsilloids' it goes over the ray-collision detection and also advanced 3D detection. It'll take you from the basics to epsilloidal bouding box collisions (that is a sphere with 3 radii). After looking at that, you might conclude that you could include 3D collisions as well (unless it's entirely unnecesssary). Also the articles there on collision detection may help you with 2D collisions, as about half of them are about that.
What I said last time is a logical method, but I'm not sure that you can measure ray-point distances accurately by the method I use, so it ends up using alot of square root functions, which is bad. This is something I need to work around as well.

RageDBL
0
Commented:
egsoc,
Use cicles. Define a circle for each car that fully encloses it. Use this for initial testing for if the distance apart of the 2 centres is greater than the sum of the radii then no collision has occured. You should in general always use a circle for initial tesing as it only requires 1 floating point multiplication

If the above does not elimiate collision then there may or may not be a collision. You should also define 2 or 3 smaller cirlces for each car that in total fully enclose the car. Now test (if the initial test has not eliminated collision) to see if the distances between each of the smaller circles is greater than the the sum of their radii. (you might want to experiment with ellipses as well, although these enclose the car better there are extra floating point operation in the distance checking)

You can go even further by defining another 4 or 5 circles for each car and check these if the 2nd test above does not eliminate collision

0
Commented:
shpuld read "initial tesing as it only requires 2 floating point multiplication",  assuming your cars are all the same or similar
0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Game Programming

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.