The MCTS: Microsoft Exchange Server 2010 certification validates your skills in supporting the maintenance and administration of the Exchange servers in an enterprise environment. Learn everything you need to know with this course.

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 ?

Thanks in advance,

Egsoc

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 ?

Thanks in advance,

Egsoc

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

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.

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.

About the fast car problem:

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

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

Experts Exchange Solution brought to you by

Your issues matter to us.

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

Start your 7-day free trialIf 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...

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

-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

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

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

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

.f

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

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

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

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

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

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

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.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

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