Detección de colisión: ¿un montón de casos especiales?

Estoy escribiendo un motor de física simple en 2D. Mi primer objetivo es conseguir que funcione la detección de colisiones. Sé que mis objetos eventualmente estarán formados por formas primitivas, pero me preguntaba si una biblioteca de detección de colisión estaría compuesta por un conjunto de funciones de casos especiales, como "rayAndLine", "rectangleRectangle", "rectangleCircle", etc., o es ¿Existe un marco común subyacente para la detección de colisiones que funcione independientemente de qué primitivas se usen para hacer la forma?

Hacer que la detección de colisiones funcione es un gran primer objetivo para su motor de física 2D. Es bueno que hayas decidido que por ahora estás trabajando específicamente en 2D, ya que no todas las reglas en 2D funcionan en 3D, a pesar de la cantidad de algoritmos relacionados con n-dimensiones, en algún momento tienes que especializarlos (haz más variante específica como cómo el producto cruzado solo satisface la identidad de Jacobi en 3D).

Su pregunta es intrínsecamente sobre la arquitectura y el diseño del marco, no sobre la física 2D, por lo que la preocupación de lo que su edificio debe estar separado en su mente sobre cómo se usan esas piezas. Esencialmente, debe separar la mentalidad de construir el motor / biblioteca / marco de su uso en otro proyecto.

Arquitectura de motores de resolución: con cualquier motor matemático, esencialmente queremos poner valores en alguna función, y esperamos que los valores que resulten útiles para hacer una simulación interesante.

Los elementos centrales de este proceso deben ser lo más abstractos posible, mientras que los elementos atómicos (los datos / métodos más pequeños y útiles) deben ser específicos para propósitos individuales y ser útiles para componer juntos. En nuestro caso, casi el único atómico útil es un vector 2D, que debería ser una sola clase de objeto que permita la expresión de una estructura (x, y), y que tenga métodos para todas las operaciones matemáticas básicas que sean útiles para los cálculos vectoriales en 2D. Suma, resta, normalización, normal (perpendicular), producto cruzado, producto puntual, magnitud / longitud, y cualquier otra cosa que encuentre que sea específicamente inherente a vector -> operaciones de vector o vector -> operaciones de número real. Si está utilizando un lenguaje basado en clases, un simple class Vectorcon cada uno de estos como una función miembro o una sobrecarga del operador funcionaría muy bien.

Después de que se construyan todos los tipos atómicos, entonces compondría sus algoritmos en otra capa encima de nuestro tipo atómico Vector. Mi ir a sería una Liney una Curve. Decidiremos aquí que a Curveestá fuera de alcance para esto y requiere mucha especialización (el concepto al que hace referencia anteriormente como la creación de muchas funciones de casos especiales). Desde Vectortambién compondría a Rectanglecomo un Vectorprimitivo 4 , compongo a Circlepartir de un vector usando a Vectory a radius, y luego compondría un a Polygonpartir de Vectortambién. Polygondebe hacerse desde Vectory no Lineaquí porque cada línea compartiría un punto duplicado con la última línea en el polígono.

Ahora tienes formas, pero no sabemos qué hacer con ellas.

Detección de colisión La detección de colisión no es una ciencia exacta y no hay un solo algoritmo perfecto (o ninguno). Hay muchos métodos que se pueden usar para lograr una variedad de efectos de calidad o incluso tener más precisión que otros. Básicamente, sin embargo, se puede separar en algunos niveles diferentes de preocupación y, por lo tanto, en algunos procesos diferentes.

La detección de colisión de fase amplia es el acto de seccionar áreas donde nos preocupamos por lo que podría / podría / colisionar, y separarlos para el proceso de fase estrecha. En 2D, normalmente recomendaría usar un árbol cuádruple para esto. Para eso necesitaremos nuestro Rectangleque construimos antes y para proporcionarle una detección de colisión AABB. Esto significa Axis Aligned Bounding Box y lo usaremos para determinar que para una caja no giratoria Ano Bexiste ninguna parte de la caja A. Se deduce de la suposición de que no Bpuede existir ninguna parte de que existe Auna colisión si se cruzan.

Un árbol cuádruple es un proceso recursivo en el que determina una profundidad máxima, o permite que la cantidad de su objeto evite una profundidad de recursión infinita. Agrupa los cuerpos de física en 4 regiones (de ahí el nombre) y debería permitirle acceder a cada quad por separado. Luego entraría en cada uno de esos cuatro quads y realizaría el mismo proceso que no describiré aquí por brevedad, pero está disponible aquí: https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees- detectar-probables-colisiones-en-2d-espacio - gamedev-374

Colisión de fase estrechaes el proceso de revisar sus grupos de formas que ya hemos determinado que colisionarán / podrían / ​​harán y realizar una verificación de colisión más discreta, en este momento, comenzamos a preocuparnos si los objetos están girando o no (gané ' t cubra esto, cuando pase estas fases de colisión, busque la detección de colisión con momento angular) y qué forma tiene realmente su cuerpo de colisión. Para realizar esta parte de la colisión, debe especializar sus métodos como se describió anteriormente (realizar funciones específicas para AABBvsCircle, OBBvsCircle, CirclevsCircle, PolygonvsPoint, PolygonvsCircle, PointvsCircle, etc.) Sin embargo, estos métodos también se pueden hacer en capas. como anteriormente.

Sus cheques de separación primitivos son los, métodos de detección discretos especializados colisión o las generales como SAT dependiendo de caso de uso y todos deben volver simplemente ya sea un valor verdadero / falso, o devolver un objeto relacional tal como una Manifold, Joint, CollisionObjectetc. que tendría una conexión con las dos formas que se encuentran colisionando, y cualquier información sobre ellas necesaria para resolver la colisión, como qué tan profundas están colisionando o a qué velocidad (los datos que necesita en su múltiple dependen del método de resolución que use). Ese objeto que luego pasa a uno Solverque debería abstraer las diferencias entre todas las diferentes formas que podrían colisionar, al aceptar solo ay Manifoldno aceptar ninguna información particular sobre las formas.

Resumen El Solvertomará la Manifoldproducida por chocar algunos primitivo Acon un poco primitivo B, utilizando primero amplia fase de agrupación (todo vs mundo) y de detección de fase entonces estrecho (A vs B) y si las formas no son polígono debe ser especializado, la Solverproduce entonces ya sea nuevo Vectorcomo las posiciones chocaron formas y velocidades, o un objeto que el PhysicsEnvironmento Worldpuede utilizar para resolver la colisión de los niños en ella, y finalmente actualizar el QuadTreey repetir este proceso en el siguiente fotograma. Si ambas formas en colisión son polígonos, entonces la especialización solo debe hacerse con respecto a un mayor rendimiento, de lo contrario, simplemente usando el Teorema del eje de separación