Wie zu beheben Kreis und Rechteck sich überlappen in Kollision Antwort?

Nach Jahren starrt auf dieses problem, und nie kommen mit eine perfekte Lösung, ich habe es endlich geschafft!

Es ist ziemlich straight-forward-Algorithmus, keine Notwendigkeit für Schleifen und Annäherungen.

Dies ist, wie es funktioniert, auf einer höheren Ebene:

1. Berechnen Kreuzung mal mit jeder Seite, die Ebene, WENN der Pfad vom aktuellen Punkt zu zukünftigen Stelle kreuzen, die dem Flugzeug.
2. Überprüfen Sie jede Seite der quadrant for single-side-Kreuzung, wieder die Kreuzung.
3. Bestimmen der Ecke, dass der Kreis kollidiert mit.
4. Lösen, das Dreieck zwischen dem aktuellen Punkt, der Ecke, und die sich schneidenden center (radius Weg von der Ecke).
5. Zeit berechnen, normal-und verschneidungs-center.

Und nun zu den schmutzigen details!

Die Eingabe für die Funktion ist begrenzt (die eine Links, oben, rechts, unten) und einem aktuellen Punkt (start) und einen zukünftigen Zeitpunkt (Ende).

Die Ausgabe ist eine Klasse namens Schnittpunkt hat die x -, y -, Zeit -, nx und ny.

• {x, y} ist die Mitte des Kreises, im Schnittpunkt der Zeit.
• Zeit ist ein Wert von 0 bis 1, wobei 0 am Anfang und 1 am Ende
• {nx, ny} ist das normal, verwendet für die Reflexion der Geschwindigkeit zu bestimmen, die neue Geschwindigkeit des Kreises

Beginnen wir mit caching-Variablen benutzen wir oft:

float L = bounds.left;
float T = bounds.top;
float R = bounds.right;
float B = bounds.bottom;
float dx = end.x - start.x;
float dy = end.y - start.y;

Und Berechnung von Schnittpunkt-mal mit jeder Seite, die Ebene (wenn der Vektor zwischen start-und end-Durchlauf über das Flugzeug):

float ltime = Float.MAX_VALUE;
float rtime = Float.MAX_VALUE;
float ttime = Float.MAX_VALUE;
float btime = Float.MAX_VALUE;

if (start.x - radius < L && end.x + radius > L) {
   ltime = ((L - radius) - start.x) / dx;
}
if (start.x + radius > R && end.x - radius < R) {
   rtime = (start.x - (R + radius)) / -dx;
}
if (start.y - radius < T && end.y + radius > T) {
   ttime = ((T - radius) - start.y) / dy;
}
if (start.y + radius > B && end.y - radius < B) {
   btime = (start.y - (B + radius)) / -dy;
}

Nun versuchen wir zu erkennen, wenn es unbedingt ein side-Kreuzung (und nicht in der Ecke). Wenn der kollisionspunkt liegt auf der Seite dann wieder die Kreuzung:

if (ltime >= 0.0f && ltime <= 1.0f) {
   float ly = dy * ltime + start.y;
   if (ly >= T && ly <= B) {
      return new Intersection( dx * ltime + start.x, ly, ltime, -1, 0 );
   }
}
else if (rtime >= 0.0f && rtime <= 1.0f) {
   float ry = dy * rtime + start.y;
   if (ry >= T && ry <= B) {
      return new Intersection( dx * rtime + start.x, ry, rtime, 1, 0 );
   }
}

if (ttime >= 0.0f && ttime <= 1.0f) {
   float tx = dx * ttime + start.x;
   if (tx >= L && tx <= R) {
      return new Intersection( tx, dy * ttime + start.y, ttime, 0, -1 );
   }
}
else if (btime >= 0.0f && btime <= 1.0f) {
   float bx = dx * btime + start.x;
   if (bx >= L && bx <= R) {
      return new Intersection( bx, dy * btime + start.y, btime, 0, 1 );
   }
}

Wir so weit gekommen sind, so wissen wir, entweder es gibt keinen Schnittpunkt, oder er kollidierte mit einer Ecke. Müssen wir bestimmen die Ecke:

float cornerX = Float.MAX_VALUE;
float cornerY = Float.MAX_VALUE;

if (ltime != Float.MAX_VALUE) {
   cornerX = L;
} else if (rtime != Float.MAX_VALUE) {
   cornerX = R;
}

if (ttime != Float.MAX_VALUE) {
   cornerY = T;
} else if (btime != Float.MAX_VALUE) {
   cornerY = B;
}

//Account for the times where we don't pass over a side but we do hit it's corner
if (cornerX != Float.MAX_VALUE && cornerY == Float.MAX_VALUE) {
   cornerY = (dy > 0.0f ? B : T);
}

if (cornerY != Float.MAX_VALUE && cornerX == Float.MAX_VALUE) {
   cornerX = (dx > 0.0f ? R : L);
}

Nun haben wir genug Informationen zur Lösung für das Dreieck. Dabei wird der Abstand Formel, finden Sie den Winkel zwischen zwei Vektoren, und das Gesetz von sines (zweimal):

double inverseRadius = 1.0 / radius;
double lineLength = Math.sqrt( dx * dx + dy * dy );
double cornerdx = cornerX - start.x;
double cornerdy = cornerY - start.y;
double cornerdist = Math.sqrt( cornerdx * cornerdx + cornerdy * cornerdy );
double innerAngle = Math.acos( (cornerdx * dx + cornerdy * dy) / (lineLength * cornerdist) );
double innerAngleSin = Math.sin( innerAngle );
double angle1Sin = innerAngleSin * cornerdist * inverseRadius;

//The angle is too large, there cannot be an intersection
if (Math.abs( angle1Sin ) > 1.0f) {
   return null;
}

double angle1 = Math.PI - Math.asin( angle1Sin );
double angle2 = Math.PI - innerAngle - angle1;
double intersectionDistance = radius * Math.sin( angle2 ) / innerAngleSin;

Dass wir jetzt gelöst, für alle Seiten und Winkel, wir können bestimmen, Zeit und alles andere:

//Solve for time
float time = (float)(intersectionDistance / lineLength);

//If time is outside the boundaries, return null. This algorithm can 
//return a negative time which indicates the previous intersection. 
if (time > 1.0f || time < 0.0f) {
   return null;
}

//Solve the intersection and normal
float ix = time * dx + start.x;
float iy = time * dy + start.y;
float nx = (float)((ix - cornerX) * inverseRadius);
float ny = (float)((iy - cornerY) * inverseRadius);

return new Intersection( ix, iy, time, nx, ny );

Woo! Das war ein spass... das hat viel Raum für Verbesserungen so weit wie Effizienz geht. Man könnte die Reihenfolge der Seite Kreuzung die Kontrolle zu entkommen, so früh wie möglich während der Herstellung möglichst wenig Berechnungen wie möglich.

Ich hatte gehofft, es gäbe einen Weg, es zu tun, ohne trigonometrische Funktionen, aber ich musste zu geben!

Hier ein Beispiel von mir nennen es und es verwenden, um die Berechnung der neuen position des Kreises mit der normalen zu reflektieren und den Schnittpunkt Zeit zu berechnen, die Größenordnung der Reflexion:

Intersection inter = handleIntersection( bounds, start, end, radius );

if (inter != null) 
{
   //Project Future Position
   float remainingTime = 1.0f - inter.time;
   float dx = end.x - start.x;
   float dy = end.y - start.y;
   float dot = dx * inter.nx + dy * inter.ny;
   float ndx = dx - 2 * dot * inter.nx;
   float ndy = dy - 2 * dot * inter.ny;
   float newx = inter.x + ndx * remainingTime;
   float newy = inter.y + ndy * remainingTime;
   //new circle position = {newx, newy}
 }

Und ich habe den vollständigen code auf pastebin mit einem vollständig interaktive Beispiel, wo können Sie zeichnen das Start-und End-Punkte, und es zeigt Ihnen die Zeit und die daraus resultierenden abprallen des Rechtecks.

Wenn Sie möchten, zu bekommen, dann läuft es sofort, haben Sie, um download-code von mein blog, sonst kleben Sie es in Ihren eigenen Java2D-Anwendung.

BEARBEITEN:
Ich geändert habe Sie den code in pastebin auch den kollisionspunkt, und auch einige Verbesserungen in der Geschwindigkeit.

BEARBEITEN:
Sie können ändern, diese für ein rotierendes Rechteck, mit diesem Rechteck Winkel un-drehen Sie das Rechteck mit dem Kreis von start-und Endpunkt. Sie führen die Kreuzung überprüfen und drehen Sie dann die daraus resultierenden Punkte und normalenvektoren.

BEARBEITEN:
Ich veränderte den code auf pastebin vorzeitig beendet, wenn die bounding Volumes der Pfad der den Kreis nicht schneidet das Rechteck aus.

InformationsquelleAutor

Es ist ein nicht-lineares problem, oder?

Nehmen Sie eine Zeit, Schritt und bewegen Sie den ball von der Verschiebung berechnet mit Geschwindigkeit zu Beginn des Schrittes. Wenn Sie finden, sich überlappen, reduzieren Sie die Schrittweite und eine Neuberechnung bis Konvergenz.

Sind Sie unter der Annahme, dass die Kugeln und Rechtecke sind beide starr, keine Verformung? Reibungsfreie Kontakt? Wie werden Sie behandeln die Bewegung des Balles nach dem Kontakt? Sind Sie auf der Umwandlung in ein Koordinatensystem der Kontakt (normal + tangential), berechnen, dann die Umwandlung zurück?

Es ist kein triviales problem.

Vielleicht sollten Sie in eine Physik-engine, wie Box2D, eher als mit der Programmierung selbst.

InformationsquelleAutor