En un motor de física 2D, ¿cómo evito resoluciones de colisión inútiles cuando los objetos se detienen?

9

En un motor de física que estoy desarrollando (para aprender) usando love-2d , implementé resoluciones de colisión de esta manera:

FixedUpdate(dt)  // I use fixed timestep
 foreach collide c1 in allNotStaticColliders
   c1.integartePhysic // i.e. apply gravitational force..
   foreach collider c2 "near" c1 // "near"= I use spatial hashing 
      if collide(c1,c2)
        resolve collision (c1,c2)  // the heavy operation
        collison callbacks c1
        collison callbacks c2
        ...

Animación de objetos que caen y se detienen

Como puede ver al final de la animación gif, hay una disminución de FPS cuando todos los colisionadores están casi conectados a tierra sobre un objeto estático.

El estado estático final, con 2 FPS

Esto se debe a que el número de resoluciones de colisión aumenta a medida que los objetos pasan más tiempo tocándose a medida que se asientan. Sin embargo, muchos de los cálculos son "inútiles" porque los objetos ya se han asentado en posiciones estables entre sí.

¿Cuál es la mejor práctica (es de esperar que no requiera un título en física) para evitar estas detecciones de colisión "inútiles"?

Editar: sugerencias DMGregory aceptadas y llegar a este resultado (aún no es óptimo)

ingrese la descripción de la imagen aquí

(Rojo = estático, Azul = activo, Verde = durmiendo)

2d collision-detection physics optimization love2d dnk drone.vs.drones
fuente
1
El enfoque habitual es "dormir" los objetos que se detienen, y no considerar las interacciones entre los objetos durmientes / estáticos (pero un objeto durmiente aún puede despertarse por una interacción de un objeto dinámico que todavía está despierto y en movimiento). Desafortunadamente, esto solo ayuda una vez que un objeto está completamente en reposo. Si estoy leyendo su ejemplo correctamente, parece que sus problemas de rendimiento comienzan cuando los objetos todavía se están asentando y moviendo ligeramente. Todo lo que se me ocurre hacer aquí es agregar más fricción / amortiguación al sistema (posiblemente con un umbral de velocidad) para que los movimientos pequeños decaigan y descansen más rápido.
DMGregory
@DMGregory Eso suena como una buena respuesta. Añadirlo?
Anko

Respuestas:

9

Sospeché que OP ya conocía este enfoque, así que lo mencioné en un comentario como solo un punto de partida, pero intentaré desarrollarlo un poco más ...

La mayoría de los motores de física dividen los objetos dinámicos en dos grupos, " despierto " y " dormido ".

Los objetos duermen cuando se sientan en reposo y se despiertan cuando son movidos o acelerados por alguna influencia externa.

Un objeto dormido se comporta como un objeto estático en la mayoría de los aspectos: su movimiento no está integrado con el tiempo (porque está en reposo, por lo que no tiene movimiento) y el motor ignora las colisiones entre objetos que están dormidos o estáticos.

Un objeto dormido que se sienta en un piso estático no lo atraviesa, a pesar de la falta de una respuesta de colisión, porque se omite toda integración de movimiento para los objetos dormidos, incluida la gravedad.

Por lo tanto, solo se deben verificar las colisiones que involucran al menos un objeto dinámico despierto:

Collisions    Static          Sleeping           Awake
          ------------------------------------------------
Awake     |    Check        Check & Wake         Check
Sleeping  |     No               No
Static    |     No

Esto puede reducir drásticamente la cantidad de objetos que necesitan una simulación activa, especialmente en pilas que, como se ilustra en la pregunta, tienen muchas colisiones mutuas para verificar si hay poco o ningún movimiento neto.

Dormir sólo ayuda una vez que los objetos realmente llegan a descansar, sin embargo, que podría tomar un tiempo.

Algunas cosas que puede hacer para descansar antes:

  • Tenga una velocidad o impulso mínimo distinto de cero y sujete a cero todo lo que caiga por debajo de él. (Esto es básicamente un épsilon, comúnmente usado para comparar carrozas)

  • Utilice la fricción, la amortiguación y las colisiones inelásticas para agotar la energía del sistema y ayudarlo a descansar más rápido en general.

  • Aumente la fricción / amortiguación / inelasticidad de forma selectiva para los objetos que se mueven lentamente para darles ese empujón final para que descansen, sin afectar el comportamiento de los cuerpos más enérgicos.

DMGregory
fuente
Buena respuesta. Señala un montón de buenas ideas. Para las comprobaciones de sueño / vigilia veo 2 puntos débiles: 1) si el objeto dormido o1 debajo del objeto dormido o2 despierta alejándose de o2, no despierta o2; 2) si elimino una plataforma estática debajo de un objeto dormido, ese objeto no se despierta (bajo la fuerza de gravedad)
dnk drone.vs.drones
1
@ dnkdrone.vs.drones Buenas observaciones. Como nunca he escrito un motor de física, no estoy seguro de cómo se maneja esto normalmente. Una posibilidad es que, cuando configuramos un objeto para dormir, almacenamos una lista de objetos que está tocando (o la agregamos a un grupo local de objetos). Cuando despertamos un objeto dormido, también despertamos todo en su lista / clúster. Puede haber opciones más elegantes, como buscar contactos cercanos al momento de despertarse (antes de que se aleje).
DMGregory