?
Solved

Collision Detection

Posted on 2003-03-26
17
Medium Priority
?
571 Views
Last Modified: 2013-12-26
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
0
Comment
Question by:egsoc
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 8
  • 5
  • 2
  • +1
17 Comments
 
LVL 8

Expert Comment

by:fl0yd
ID: 8212145
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 Comment

by:egsoc
ID: 8215985
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.

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
0
 
LVL 8

Accepted Solution

by:
fl0yd earned 400 total points
ID: 8216511
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
Get MongoDB database support online, now!

At Percona’s web store you can order your MongoDB database support needs in minutes. No hassles, no fuss, just pick and click. Pay online with a credit card. Handle your MongoDB database support now!

 

Author Comment

by:egsoc
ID: 8223034
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
 
LVL 8

Expert Comment

by:fl0yd
ID: 8223596
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 Comment

by:egsoc
ID: 8225335
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 Comment

by:egsoc
ID: 8251194
I was wondering about this statement:
  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
 
LVL 8

Expert Comment

by:fl0yd
ID: 8251976
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 Comment

by:egsoc
ID: 8252107
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
 
LVL 8

Expert Comment

by:fl0yd
ID: 8252719
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 Comment

by:egsoc
ID: 8254686
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 Comment

by:egsoc
ID: 8254791
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
 
LVL 1

Expert Comment

by:RageDBL
ID: 8299908
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 Comment

by:egsoc
ID: 8311642
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
 
LVL 1

Expert Comment

by:RageDBL
ID: 8335388
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
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 8490905
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
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 8490933
shpuld read "initial tesing as it only requires 2 floating point multiplication",  assuming your cars are all the same or similar
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
As game developers, we quickly learn that Artificial Intelligence (AI) doesn’t need to be so tough.  To reference Space Ghost: “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer. (http://www.youtu…
Add bar graphs to Access queries using Unicode block characters. Graphs appear on every record in the color you want. Give life to numbers. Hopes this gives you ideas on visualizing your data in new ways ~ Create a calculated field in a query: …
In this video you will find out how to export Office 365 mailboxes using the built in eDiscovery tool. Bear in mind that although this method might be useful in some cases, using PST files as Office 365 backup is troublesome in a long run (more on t…
Suggested Courses
Course of the Month12 days, 5 hours left to enroll

752 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