Detecção de colisão: um monte de casos especiais?

Estou escrevendo um mecanismo de física simples em 2D. Meu primeiro objetivo é fazer com que a detecção de colisão funcione. Eu sei que meus objetos acabarão sendo compostos de formas primitivas, mas eu queria saber - uma biblioteca de detecção de colisões seria composta de várias funções de caso especiais, como "rayAndLine", "rectangleRectangle", "rectangleCircle" etc. existe uma estrutura comum subjacente para a detecção de colisão que funciona independentemente de quais primitivas são usadas para fazer a forma?

Colocar o funcionamento da detecção de colisão é o primeiro grande objetivo do seu mecanismo de física 2D. É bom que você tenha decidido que, por enquanto, está trabalhando especificamente em 2D, pois nem todas as regras em 2D funcionam em 3D, apesar da quantidade de algoritmos relacionados à dimensão n, em algum momento você precisa especializá-los (faça mais variante específica, como como o produto cruzado satisfaz apenas a identidade Jacobi em 3D).

Sua pergunta é inerentemente sobre arquitetura e design de estrutura, e não sobre física 2D, portanto, a preocupação com o que seu edifício deve ser separado em sua mente sobre como essas peças são usadas. Essencialmente, você precisa separar a mentalidade de construir o mecanismo / biblioteca / estrutura do uso em outro projeto.

Arquitetando mecanismos de solução: com qualquer mecanismo de matemática, queremos essencialmente colocar valores em alguma função e esperamos que os valores que sejam úteis sejam úteis para fazer uma simulação interessante.

Os elementos principais desse processo devem ser o mais abstratos possíveis, enquanto os elementos atômicos (menores dados / métodos úteis) devem ser específicos para fins individuais e úteis para compor juntos. No nosso caso, quase o único atômico útil é um vetor 2D, que deve ser uma única classe de objeto que permite a expressão de uma estrutura (x, y) e possui métodos para todas as operações matemáticas básicas que são úteis para cálculos vetoriais em 2D. Adição, subtração, normalização, normal (perpendicular), produto cruzado, produto escalar, magnitude / comprimento e qualquer outra coisa que você encontrar que seja especificamente inerente a operações vetoriais -> operações vetoriais ou operações vetoriais -> números reais. Se você estiver usando uma linguagem baseada em classe, um simples class Vectorcom cada uma delas como uma função membro ou sobrecarga de operador seria muito bem.

Depois que todos os tipos atômicos são construídos, você compõe seus algoritmos em outra camada, sobre o nosso tipo atômico Vector. Meu ir para seria um Linee um Curve. Decidiremos aqui que a Curveestá fora do escopo para isso e requer muita especialização (o conceito a que você se refere acima como criando muitas funções de caso especiais). De VectorI também comporia um Rectanglecomo um 4 Vectorprimitivo, de composição Circlede vetor usando um Vectore uma radius, e, em seguida, que comporia um Polygondo Vectorbem. Polygondeve ser feito a partir Vectore não Lineaqui, porque cada linha compartilharia um ponto duplicado com a última linha no polígono.

Agora você tem formas, mas não sabemos o que fazer com elas.

Detecção de colisão A detecção de colisão não é uma ciência exata e não existe um único algoritmo perfeito (ou nenhum). Existem muitos métodos que podem ser usados ​​para obter uma variedade de qualidade de efeitos ou até ter mais precisão do que outros. Basicamente, porém, ele pode ser separado em alguns níveis diferentes de preocupação e, portanto, em alguns processos diferentes.

A detecção de colisão de fase ampla é o ato de seccionar áreas em que nos preocupamos com o que pode / poderia / faz colidir e separá-las para o processo de fase estreita. Em 2D, eu normalmente recomendaria o uso de uma árvore quádrupla para isso. Para isso, precisaremos do que Rectanglecriamos anteriormente e forneceremos uma detecção de colisão AABB. Isso significa Caixa delimitadora alinhada pelo eixo e nós a usaremos para determinar que, para uma caixa não rotativa, Anão Bexista nenhuma parte da caixa A. Segue-se da suposição de que nenhuma parte Bpode existir dentro da Aqual uma colisão existe se eles se cruzarem.

Uma árvore quádrupla é um processo recursivo em que você determina uma profundidade máxima ou permite que a quantidade de objetos impeça uma profundidade de recursão infinita. Ele agrupa os corpos físicos em 4 regiões (daí o nome) e deve permitir que você acesse cada quad separadamente. Você entraria em cada um desses quatro quadríceps e executaria o mesmo processo que não descreverei aqui por questões de brevidade, mas está disponível aqui: https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees- para detectar-prováveis-colisões-no-2D-espaço - gamedev-374

Colisão de fase estreitaé o processo de passar por seus grupos de formas que já determinamos que irá / poderá / colidir e executar uma verificação de colisão mais discreta; neste momento, começamos a nos preocupar se os objetos estão girando ou não (eu venci ' Para cobrir isso, quando você passar nessas fases de colisão, procure detectar a colisão com momento angular) e qual é a forma do corpo da colisão. Para executar esta parte da colisão, você especializaria seus métodos conforme descrito acima (criando funções específicas para AABBvsCircle, OBBvsCircle, CirclevsCircle, PolygonvsPoint, PolygonvsCircle, PointvsCircle etc.) No entanto, esses métodos também podem ser feitos de maneira em camadas como acima.

Seus cheques de separação primitivas são as discretas, métodos de detecção de colisão especializados ou os gerais, como SAT dependendo do caso de uso e todos devem simplesmente retornar um valor true / false, ou retornar um objeto relacional, tais como Manifold, Joint, CollisionObjectetc., que teria uma conexão com as duas formas encontradas em colisão e todas as informações necessárias para resolver a colisão, como a profundidade em que estão colidindo ou a que velocidade (quais dados você precisa em seu coletor depende de qual método de resolução você usa). O objeto que você passa para um Solverque deve abstrair as diferenças entre todas as formas diferentes que podem colidir, aceitando apenas um Manifolde não informações específicas sobre as formas.

Resumo O que Solverserá Manifoldproduzido colidindo um primitivo Acom outro primitivo B, usando o primeiro agrupamento de fase ampla (todos vs mundo) e, em seguida, a detecção de fase estreita (A vs B) e se as formas forem não-polígono devem ser especializadas, Solverentão produz novos Vectors para as posições e velocidades das formas colididas, ou um objeto que o PhysicsEnvironmentou Worldpossa usar para resolver a colisão em seus filhos, finalmente atualize QuadTreee repita esse processo no próximo quadro. Se as duas formas de colisão forem polígonos, a especialização deve ser feita apenas com relação ao aumento do desempenho, caso contrário, basta usar o Teorema do Eixo Separador