F(lang): Kollisions Kontrolle Kreis-Kreis, Kreis-Rechteck

11/11/2007 - 17:20 von Reinhard Pagitsch | Report spam
Hallo NG,

Mal vorweg: Meine Schulzeit da ich Mathematik gelernt habe ist schon
über 22 Jahre her.

Ich hab hier einen Text der die oben beschriebene Kollision Kontrolle
erklàrt. Nur ich komm einfach nicht mehr mit mit dem was da geschrieben
wird.
Kann mir das Ganze bitte mal jemand erklàren?

(Ab wann ich aussteige ist mit ReinhardP: gekennzeichnet.)

Danke,
Reinhard

Hier der Auszug was mir nicht klar ist:
(die ganze Erklàrung mit Bildern gibts auf
http://www.programmersheaven.com/d/...tilde;3268)


2) Calculate accurate positions at time of collision.

The central trick for this step is the Quadratic equation.

Let's take a moment to define our terms. (See figure 2a)

Stuff we know:
x1,y1 and x2,y2 - The initial positions of the centers of the two objects
dx1,dy1 and dx2,dy2 - The distances the objects moved this frame
r1, r2 - radii of the two objects

Stuff we calculate:
t - Time of collision
cx1,cy1 and cx2,cy2 - The centers at time of impact

What we're trying to find is when the centers of the two objects are
the same distance apart as the sum of their radii. The distance
formula is sqrt([cx1-cx2]^2 + [cy1-cy2]^2). Therefore, we're looking
for the time (t) when
(r1+r2)=sqrt([cx1-cx2]^2 + [cy1-cy2]^2).

How do we know where will a ball be at any given time (t)? Here are
functions which describe the paths of the centers of the balls over
time:

cx1 = x1 + tdx1 cx2 = x2 + tdx2
cy1 = y1 + tdy1 cy2 = y2 + tdy2

The t's relate all the forumlas to each other. Replacing the cx's and
cy's in the distance forumla with these equations and we end up with:

r1+r2 = sqrt(((x2 + tdx2)-(x1 + tdx1))^2 + ((y2 + tdy2)-(y1 + tdy1))^2)

ReinhardP: ab hier steig ich aus:

Multiply everything out then rearrange and simplify and you end up
with:

0 = [(dx2-dx1)^2 + (dy2-dy1)^2] t^2
+ [2(x2-x1)(dx2-dx1) + 2(y2-y1)(dy2-dy1)] t
+ [(x2-x1)^2 + (y2-y1)^2 - (r1+r2)^2]

This is a polynomial in the form 0=ax^2+bx+c. We can use the Quadratic
equation (-b(+|-)sqrt(b^2-4ac))/2a to solve for the variable. The a, b
and c are all spelled out above. You could plug a, b and c into that
monster equation, but it turns out you want to calculate it in pieces.

The Quadratic equation will give two answers, call them t1 and t2. One
for each the plus and minus of the square root portion. There are some
special cases to check before solving the equation, and some special
cases that result from the equation. (See figure 2, cases 1-6)

1) If a=0 the equation goes infinite. Notice that "a" consists of the
square of the difference between the direction vectors.
Therefore, a=0 if and only if the balls are moving the same
direction and the same speed.

2) If 4ac > b^2 then you end up trying to take the square root of a
negative number. In other words, there's no solution. It turns
out that this happens if and only if the balls never pass within
r1+r2 of each other. Even though the paths may cross, the balls
are far enough apart in time that they don't approach close
enough to each other to ever actually touch.

3) If both t's are negative then the balls are receding from each
other.

4) If one t is negative and the other t is positive then the balls
began the frame already overlapped.

5) If both t's are positive then the smaller of the two is when they
first reach r1+r2 from each other.

6) If both t's are greater than 1.0 then the balls do not collide
this frame.

Condition 5 is the only valid collision and you continue with the rest
of the calculations.

Conditions 1, 2, 3 and 6 indicate that there is not a valid collision
this frame and you therefore can abort before performing the rest of
the calculations. In effect, you discard this pair of objects since a
collision didn't take place.

Ideally, condition 4 should not occur. Whether or not it does occur
depends on whether or not you handle multiple collisions in one frame.
If you don't test for condition 4 then the rest of the math works out
that the balls will remain locked together "arm-in-arm" so to speak.




 

Lesen sie die antworten

#1 Ulrich Lange
11/11/2007 - 20:06 | Warnen spam
Hallo Reinhard,

Reinhard Pagitsch schrieb:

Ich hab hier einen Text der die oben beschriebene Kollision Kontrolle
erklàrt. Nur ich komm einfach nicht mehr mit mit dem was da geschrieben
wird.
Kann mir das Ganze bitte mal jemand erklàren?

(Ab wann ich aussteige ist mit ReinhardP: gekennzeichnet.)

[...]

r1+r2 = sqrt(((x2 + tdx2)-(x1 + tdx1))^2 + ((y2 + tdy2)-(y1 + tdy1))^2)

ReinhardP: ab hier steig ich aus:

Multiply everything out then rearrange and simplify and you end up
with:



Vor dem Ausmultiplizieren muß man noch beide Seiten quadrieren, damit
die Wurzel (sqrt) rechts verschwindet:

(r1+r2)^2 = ((x2 + tdx2)-(x1 + tdx1))^2 + ((y2 + tdy2)-(y1 + tdy1))^2

Jetzt mußt Du die beiden Quadrate rechts ausmultiplizieren und alle
Terme mit gleicher Potenz in t zusammenfassen. Ich machs mal für das
erste Quadrat rechts:

((x2 + tdx2)-(x1 + tdx1))^2
= (x2 + tdx2)^2 - 2*(x2+tdx2)*(x1+tdx1) + (x1 +tdx1)^2

= x2^2 + 2*x2*dx2*t + dx2^2 *t^2
- 2*x2*x1 * 2*(x1*dx2+x2*dx1)*t + 2*dx1*dx2*t^2
- x1^2 + 2*x1*dx1*t + dx1^2*t^2

= x1^2 + 2*x1*x2 + x2^2
+ 2*(x1+x2)*(dx1+dx2)*t
+ (dx1+dx2)^2*t^2

Wenn Du das für das zweite Quadrat auch noch machst, und dann alle
Terme mit t^2, t^1 bzw. t^0 zusammenfaßt (nicht vergessen, den t^0-Term
(r1+r2)^2 von links noch rüberzubringen), sollte insgesamt die u.g.
Formel herauskommen:


0 = [(dx2-dx1)^2 + (dy2-dy1)^2] t^2
+ [2(x2-x1)(dx2-dx1) + 2(y2-y1)(dy2-dy1)] t
+ [(x2-x1)^2 + (y2-y1)^2 - (r1+r2)^2]

This is a polynomial in the form 0=ax^2+bx+c.



Hier ist ein kleiner Fehler im Text, der evtl. auch das Verstàndnis
erschwert. Richtigerweise sollte es heissen "This is a polynomial on the
form 0=at^2+bt+c".

Ich hoffe, damit kommst Du erstmal weiter. Solltest Du weiter unten in
dem Text wieder aussteigen, frag' einfach nochmal nach.

Gruß, Ulrich Lange

(ulrich punkt lange bindestrich mainz at t-online punkt de)

Ähnliche fragen