Comment fixer le cercle et le rectangle de chevauchement dans la collision de réponse?

Après des années de regarder ce problème, et de ne jamais venir avec une solution parfaite, je l'ai enfin fait!

C'est à peu près un simple algorithme, pas besoin de boucle et d'approximations.

C'est la façon dont il fonctionne à un niveau supérieur:

1. Calculer l'intersection avec chaque côté de l'avion SI le chemin à partir du point courant à l'avenir de point de croix de l'avion.
2. Vérifier chaque côté du quadrant pour un seul côté de l'intersection, de retour de l'intersection.
3. Déterminer l'angle que le cercle est la collision avec.
4. Résoudre le triangle entre le point courant, le coin, et de l'intersection du centre (rayon à l'écart du coin).
5. Calculer en temps, normal, et l'intersection du centre.

Et maintenant, pour les détails sanglants!

L'entrée à la fonction est de limite (qui est à gauche, haut, droite, bas) et d'un point courant (start) et un moment de l'avenir (à la fin).

La sortie est une classe appelée croisement a x, y, temps, nx et ny.

• {x, y} est le centre du cercle à l'intersection du temps.
• le temps est une valeur de 0 à 1, où 0 est au début et 1 en fin
• {nx, ny} est normal, utilisé pour refléter la vitesse pour déterminer la nouvelle vélocité du cercle

Nous avons commencer avec la mise en cache des variables que nous utilisons souvent:

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;

Et de calcul de l'intersection avec chaque côté de l'avion (si le vecteur entre le début et la fin passer au-dessus de l'avion):

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;
}

Maintenant, nous essayons de voir si c'est strictement un côté intersection (et pas un coin). Si le point de collision se trouve sur le côté puis retourner l'intersection:

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 );
}
}

Nous avons obtenu jusqu'ici nous savons donc il n'y a pas d'intersection, ou il est entré en collision avec un coin. Nous avons besoin de déterminer le coin:

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);
}

Nous avons maintenant suffisamment d'informations pour résoudre le triangle. Il utilise la formule de la distance, de trouver l'angle entre deux vecteurs, et la loi des sinus (deux fois):

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;

Maintenant que nous avons résolu de tous les côtés et les angles, nous pouvons déterminer le temps et tout le reste:

//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! C'était amusant... ce qui a beaucoup de place pour des améliorations de l'efficacité va. Vous pourriez les réorganiser le côté de l'intersection de la vérification pour échapper dès que possible, tout en apportant quelques calculs que possible.

J'espérais qu'il y aurait un moyen de le faire sans les fonctions trigonométriques, mais j'ai dû céder!

Voici un exemple de m'appeler et l'utiliser pour calculer la nouvelle position du cercle à l'aide de la normale à refléter et à l'intersection de temps pour calculer l'ampleur de la réflexion:

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}
}

Et j'ai posté le code complet sur pastebin complètement interactif, vous pouvez par exemple tracer les points de début et de fin et il vous montre le temps et résultant rebondir hors du rectangle.

Si vous voulez le remettre en marche tout de suite, vous aurez à télécharger code de mon blog, sinon le coller dans votre propre Java2D application.

EDIT:
J'ai modifié le code en pastebin pour inclure également le point de collision, et a également fait quelques améliorations de la vitesse.

EDIT:
Vous pouvez modifier ce pour une rotation d'un rectangle à l'aide du rectangle de l'angle de l'onu-faire pivoter le rectangle avec le cercle de points de début et fin. Vous devrez effectuer l'intersection de vérifier puis de tourner la résultante des points et les normales.

EDIT:
J'ai modifié le code sur pastebin pour quitter plus tôt si la délimitation du volume de la trajectoire du cercle ne se croisent pas avec le rectangle.

OriginalL'auteur ClickerMonkey

C'est un problème non linéaire, droite?

Vous prenez une étape de temps et de déplacer la balle à son déplacement calculé à l'aide de la vitesse au début de l'étape. Si vous trouver les chevauchements, de réduire la taille du pas de calcul jusqu'à la convergence.

Êtes-vous en supposant que les balles et les rectangles sont à la fois rigides, pas de déformation? Frottement de contact? Comment allez-vous gérer le mouvement de la balle après que le contact est établi? Êtes-vous transformer sur un système de coordonnées du contact (normal + tangentielle), le calcul, puis la transformation de retour?

Ce n'est pas un problème trivial.

Peut-être que vous devriez regarder dans un moteur physique, comme Box2D, plutôt que de coder vous-même.

OriginalL'auteur duffymo