titles pro premiere essential cinematic graphics language-agnostic collision-detection physics
Completa fuente para colisionador bola a bola.

graphics - essential - titles pack premiere pro templates



Colisión bola a bola-Detección y manejo (12)

Bueno, hace años hice el programa como tú lo presentaste aquí.
Hay un problema oculto (o muchos, depende del punto de vista):

  • Si la velocidad de la bola es demasiado alta, puedes perderte la colisión.

Y también, casi en el 100% de los casos, tus nuevas velocidades serán incorrectas. Bueno, no las velocidades , sino las posiciones . Tienes que calcular nuevas velocidades precisamente en el lugar correcto. De lo contrario, simplemente cambia las bolas en una pequeña cantidad de "error", que está disponible en el paso discreto anterior.

La solución es obvia: tienes que dividir el paso del tiempo para que, primero, cambies al lugar correcto, luego colisiones, luego cambies por el resto del tiempo que tengas.

Con la ayuda de la comunidad Stack Overflow, he escrito un simulador de física bastante básico pero divertido.

Haz clic y arrastra el ratón para lanzar una bola. Rebotará y eventualmente se detendrá en el "piso".

Mi próxima gran característica que quiero agregar es la colisión bola a bola. El movimiento de la bola se divide en el vector de velocidad de hacha e y. Tengo gravedad (pequeña reducción del vector y en cada paso), tengo fricción (pequeña reducción de ambos vectores en cada colisión con una pared). Las bolas se mueven honestamente de una manera sorprendentemente realista.

Supongo que mi pregunta tiene dos partes:

  1. ¿Cuál es el mejor método para detectar la colisión bola a bola?
    ¿Acabo de tener un bucle O (n ^ 2) que itera sobre cada bola y verifica cada otra bola para ver si el radio se superpone?
  2. ¿Qué ecuaciones utilizo para manejar las colisiones bola a bola? Fisica 101
    ¿Cómo afecta a las dos bolas los vectores x / y de velocidad? ¿Cuál es la dirección resultante hacia la que se dirigen las dos bolas? ¿Cómo aplico esto a cada bola?

El manejo de la detección de colisiones de las "paredes" y los cambios resultantes del vector fueron fáciles, pero veo más complicaciones con las colisiones bola-bola. Con las paredes simplemente tuve que tomar el negativo del vector x o y apropiado y apagarlo iría en la dirección correcta. Con las bolas no creo que sea así.

Algunas aclaraciones rápidas: por simplicidad, estoy bien con una colisión perfectamente elástica por ahora, también todas mis bolas tienen la misma masa ahora, pero podría cambiar eso en el futuro.

Editar: Recursos que he encontrado útiles

Física de la pelota 2d con vectores: colisiones bidimensionales sin trigonometría.pdf
Ejemplo de detección de colisión de bola 2d: adición de detección de colisión

¡Éxito!

¡Tengo la detección y respuesta de colisión de pelota funcionando muy bien!

Código relevante:

Detección de colisiones:

for (int i = 0; i < ballCount; i++) { for (int j = i + 1; j < ballCount; j++) { if (balls[i].colliding(balls[j])) { balls[i].resolveCollision(balls[j]); } } }

Esto verificará las colisiones entre cada bola, pero omitirá las verificaciones redundantes (si tiene que verificar si la bola 1 choca con la bola 2, entonces no necesita verificar si la bola 2 choca con la bola 1. Además, se salta la verificación de colisiones entre sí). ).

Luego, en mi clase de pelota tengo mis métodos de colisión () y resoluciónColección ():

public boolean colliding(Ball ball) { float xd = position.getX() - ball.position.getX(); float yd = position.getY() - ball.position.getY(); float sumRadius = getRadius() + ball.getRadius(); float sqrRadius = sumRadius * sumRadius; float distSqr = (xd * xd) + (yd * yd); if (distSqr <= sqrRadius) { return true; } return false; } public void resolveCollision(Ball ball) { // get the mtd Vector2d delta = (position.subtract(ball.position)); float d = delta.getLength(); // minimum translation distance to push balls apart after intersecting Vector2d mtd = delta.multiply(((getRadius() + ball.getRadius())-d)/d); // resolve intersection -- // inverse mass quantities float im1 = 1 / getMass(); float im2 = 1 / ball.getMass(); // push-pull them apart based off their mass position = position.add(mtd.multiply(im1 / (im1 + im2))); ball.position = ball.position.subtract(mtd.multiply(im2 / (im1 + im2))); // impact speed Vector2d v = (this.velocity.subtract(ball.velocity)); float vn = v.dot(mtd.normalize()); // sphere intersecting but moving away from each other already if (vn > 0.0f) return; // collision impulse float i = (-(1.0f + Constants.restitution) * vn) / (im1 + im2); Vector2d impulse = mtd.multiply(i); // change in momentum this.velocity = this.velocity.add(impulse.multiply(im1)); ball.velocity = ball.velocity.subtract(impulse.multiply(im2)); }

Código fuente: Completa fuente para colisionador bola a bola.

Si alguien tiene algunas sugerencias sobre cómo mejorar este simulador de física básica, hágamelo saber. Una cosa que todavía tengo que agregar es el momento angular para que las bolas rueden de manera más realista. ¿Cualquier otra sugerencia? ¡Deja un comentario!

Como una aclaración a la sugerencia de Ryan Fox de dividir la pantalla en regiones, y solo verificar las colisiones dentro de las regiones ...

por ejemplo, divida el área de juego en una cuadrícula de cuadrados (que arbitrariamente dirá que son de 1 unidad de longitud por lado), y verifique las colisiones dentro de cada cuadrícula.

Esa es absolutamente la solución correcta. El único problema con él (como lo señaló otro póster) es que las colisiones entre fronteras son un problema.

La solución a esto es superponer una segunda cuadrícula con un desplazamiento vertical y horizontal de 0,5 unidades a la primera.

Luego, cualquier colisión que se produzca a través de los límites de la primera cuadrícula (y, por lo tanto, no se detecte) estará dentro de los cuadrados de cuadrícula en la segunda cuadrícula. Siempre que realice un seguimiento de las colisiones que ya ha manejado (ya que es probable que haya alguna superposición), no tiene que preocuparse por el manejo de casos de vanguardia. Todas las colisiones se llevarán a cabo dentro de una cuadrícula en una de las cuadrículas.

Como veo aquí, no se menciona una mejor manera de implementarlo. Lo referiré a "Cómo simular billares y sistemas similares" por Boris D. Lubachevsky, disponible en arxiv: http://arxiv.org/abs/cond-mat/0503627 En la imagen adjunta hay una captura de pantalla de un programa. Tengo la intención de hacer código abierto cuando lo termine. Incluso en una etapa temprana se está ejecutando con 5000 esferas bastante bien. Ojalá lo haga aún mejor, aunque no quiero implementar la segmentación, quiero mantener el código fácil de entender. La descripción estará disponible en http://compphys.go.ro

Edición posterior: el código ya está disponible en GitHub: https://github.com/aromanro/EventMolecularDynamics descripción está en el blog: http://compphys.go.ro/event-driven-molecular-dynamics/

Encontré una página excelente con información sobre detección de colisiones y respuesta en 2D.

http://www.metanetsoftware.com/technique.html

Intentan explicar cómo se hace desde un punto de vista académico. Comienzan con la simple detección de colisión de objeto a objeto, y pasan a la respuesta de colisión y cómo escalarla.

Editar: Enlace actualizado

Implementé este código en JavaScript utilizando el elemento HTML Canvas, y produjo simulaciones maravillosas a 60 cuadros por segundo. Comencé la simulación con una colección de una docena de bolas en posiciones y velocidades aleatorias. Descubrí que a velocidades más altas, una colisión brusca entre una bola pequeña y una mucho más grande hizo que la bola pequeña pareciera COLGARSE hacia el borde de la bola más grande, y se movió hasta alrededor de 90 grados alrededor de la bola más grande antes de separarse. (Me pregunto si alguien más observó este comportamiento.)

Algunos registros de los cálculos mostraron que la Distancia de conversión mínima en estos casos no era lo suficientemente grande como para evitar que las mismas bolas colisionen en el siguiente paso de tiempo. Hice algunos experimentos y descubrí que podía resolver este problema escalando el MTD en función de las velocidades relativas:

dot_velocity = ball_1.velocity.dot(ball_2.velocity); mtd_factor = 1. + 0.5 * Math.abs(dot_velocity * Math.sin(collision_angle)); mtd.multplyScalar(mtd_factor);

Verifiqué que antes y después de este arreglo, la energía cinética total se conservaba para cada colisión. El valor de 0.5 en el mtd_factor fue el valor mínimo aproximadamente encontrado que siempre hace que las bolas se separen después de una colisión.

Aunque esta corrección introduce una pequeña cantidad de error en la física exacta del sistema, la desventaja es que ahora las bolas muy rápidas se pueden simular en un navegador sin disminuir el tamaño del intervalo de tiempo.

Lo veo insinuado aquí y allá, pero también podría hacer primero un cálculo más rápido, como, comparar los cuadros delimitadores para la superposición, y luego hacer una superposición basada en el radio si la primera prueba pasa.

La suma / diferencia matemática es mucho más rápida para un cuadro delimitador que para todos los disparos del radio, y la mayoría de las veces, la prueba del cuadro delimitador descartará la posibilidad de una colisión. Pero si luego vuelve a realizar la prueba con trigonometría, está obteniendo los resultados precisos que está buscando.

Sí, son dos pruebas, pero en general será más rápido.

Para detectar si dos bolas chocan, simplemente verifique si la distancia entre sus centros es menos de dos veces el radio. Para hacer una colisión perfectamente elástica entre las bolas, solo debes preocuparte por el componente de la velocidad que está en la dirección de la colisión. El otro componente (tangente a la colisión) se mantendrá igual para ambas bolas. Puede obtener los componentes de colisión creando un vector unitario que apunte en la dirección de una bola a la otra, y luego tome el producto puntual con los vectores de velocidad de las bolas. A continuación, puede conectar estos componentes en una ecuación de colisión perfectamente elástica 1D.

Wikipedia tiene un buen resumen de todo el proceso . Para bolas de cualquier masa, las nuevas velocidades se pueden calcular utilizando las ecuaciones (donde v1 y v2 son las velocidades después de la colisión, y u1, u2 son anteriores):

Si las bolas tienen la misma masa, las velocidades simplemente se cambian. Aquí hay un código que escribí que hace algo similar:

void Simulation::collide(Storage::Iterator a, Storage::Iterator b) { // Check whether there actually was a collision if (a == b) return; Vector collision = a.position() - b.position(); double distance = collision.length(); if (distance == 0.0) { // hack to avoid div by zero collision = Vector(1.0, 0.0); distance = 1.0; } if (distance > 1.0) return; // Get the components of the velocity vectors which are parallel to the collision. // The perpendicular component remains the same for both fish collision = collision / distance; double aci = a.velocity().dot(collision); double bci = b.velocity().dot(collision); // Solve for the new velocities using the 1-dimensional elastic collision equations. // Turns out it''s really simple when the masses are the same. double acf = bci; double bcf = aci; // Replace the collision velocity components with the new ones a.velocity() += (acf - aci) * collision; b.velocity() += (bcf - bci) * collision; }

En cuanto a la eficiencia, Ryan Fox tiene razón, debería considerar dividir la región en secciones y luego hacer la detección de colisiones dentro de cada sección. Tenga en cuenta que las bolas pueden chocar con otras bolas en los límites de una sección, por lo que esto puede hacer que su código sea mucho más complicado. La eficiencia probablemente no importará hasta que tengas varios cientos de pelotas. Para obtener puntos de bonificación, puede ejecutar cada sección en un núcleo diferente, o dividir el procesamiento de colisiones dentro de cada sección.

Tienes dos formas fáciles de hacer esto. Jay ha cubierto la forma precisa de verificar desde el centro de la pelota.

La forma más fácil es usar un cuadro delimitador de rectángulo, establecer el tamaño de la caja en un 80% del tamaño de la bola y simulará la colisión bastante bien.

Agrega un método a tu clase de pelota:

public Rectangle getBoundingRect() { int ballHeight = (int)Ball.Height * 0.80f; int ballWidth = (int)Ball.Width * 0.80f; int x = Ball.X - ballWidth / 2; int y = Ball.Y - ballHeight / 2; return new Rectangle(x,y,ballHeight,ballWidth); }

Luego, en tu bucle:

// Checks every ball against every other ball. // For best results, split it into quadrants like Ryan suggested. // I didn''t do that for simplicity here. for (int i = 0; i < balls.count; i++) { Rectangle r1 = balls[i].getBoundingRect(); for (int k = 0; k < balls.count; k++) { if (balls[i] != balls[k]) { Rectangle r2 = balls[k].getBoundingRect(); if (r1.Intersects(r2)) { // balls[i] collided with balls[k] } } } }

Una buena manera de reducir el número de controles de colisión es dividir la pantalla en diferentes secciones. Luego solo comparas cada bola con las bolas en la misma sección.

Una cosa que veo aquí para optimizar.

¡Aunque estoy de acuerdo en que las bolas golpean cuando la distancia es la suma de sus radios, uno nunca debe calcular esta distancia! Más bien, calcula el cuadrado y trabaja con él de esa manera. No hay razón para esa costosa operación de raíz cuadrada.

Además, una vez que haya encontrado una colisión, debe continuar evaluando las colisiones hasta que no quede más. El problema es que la primera causa que otras personas deban resolverse antes de obtener una imagen precisa. ¿Considerar qué sucede si la bola golpea una bola en el borde? La segunda bola golpea el borde e inmediatamente rebota en la primera bola. Si golpeas un montón de bolas en la esquina, puedes tener bastantes colisiones que deben resolverse antes de poder repetir el siguiente ciclo.

En cuanto a la O (n ^ 2), todo lo que puede hacer es minimizar el costo de rechazar los que faltan:

1) Una bola que no se mueve no puede golpear nada. Si hay un número razonable de pelotas en el piso, esto podría ahorrar muchas pruebas. (Tenga en cuenta que todavía debe verificar si algo golpeó la bola estacionaria).

2) Algo que podría valer la pena hacer: divida la pantalla en varias zonas, pero las líneas deben ser borrosas: las bolas en el borde de una zona se enumeran como si estuvieran en todas las zonas relevantes (podrían ser 4). Yo usaría una cuadrícula 4x4, almacenaría las zonas como bits. Si un AND de las zonas de dos bolas devuelve cero, final de la prueba.

3) Como mencioné, no hagas la raíz cuadrada.