Em desenvolvimento de jogos, simulações físicas e navegação de robôs, a detecção de colisão é uma tecnologia central para garantir interações realistas antre objetos. O C++, com sua alta performance e controle de baixo nível, é a escolha principal para implementar sistemas eficientes de detecção de colisão. O objetivo principal é determinar se dois ou mais corpos geométricos se sobrepõem no espaço e, com base nisso, acionar lógicas correspondentes, como ricochete, parada ou cálculo de dano.

A detecção de colisão é geralmente dividida em duas fases: uma fase ampla (broad phase) e uma fase estreita (narrow phase). A fase ampla serve para excluir rapidamente pares de objetos claramente não intersectantes. Os métodos comuns incluem divisão espacial (como quadtree e octree) e algoritmos de varredura. A fase estreita realiza julgamentos geométricos precisos em pares de objetos potencialmente em colisão, frequentemente envolvendo cálculos relacionais entre pontos, linhas e faces.

Um exemplo simples de detecção de colisão entre caixas delimitadoras alinhadas aos eixos (AABB) é apresentado abaixo. A estrutura define os limites mínimos e máximos, e a função verifica a sobreposição em cada eixo.

struct CaixaLimitadora {
    float minX, maxX;
    float minY, maxY;
};

bool VerificaSobreposicao(const CaixaLimitadora& caixaA, const CaixaLimitadora& caixaB) {
    bool colisaoX = (caixaA.minX <= caixaB.maxX) && (caixaA.maxX >= caixaB.minX);
    bool colisaoY = (caixaA.minY <= caixaB.maxY) && (caixaA.maxY >= caixaB.minY);
    return colisaoX && colisaoY;
}

A detecção de colisão entre esferas (ou círculos em 2D) baseia-se no critério de distância. Se a distância entre os centros for menor que a soma dos raios, ocorre uma colisão. Otimizações importantes incluem o uso do quadrado da distância para evitar operações de raiz quadrada dispendiosas.

struct Vetor3D {
    float x, y, z;
};

bool ColisaoEntreEsferas(const Vetor3D& centro1, float raio1, const Vetor3D& centro2, float raio2) {
    float diffX = centro1.x - centro2.x;
    float diffY = centro1.y - centro2.y;
    float diffZ = centro1.z - centro2.z;
    float distanciaAoQuadrado = diffX * diffX + diffY * diffY + diffZ * diffZ;
    float somaRaios = raio1 + raio2;
    return distanciaAoQuadrado <= somaRaios * somaRaios;
}

O Teorema do Eixo Separador (SAT) é um algoritmo fundamental para determinar se dois polígonos convexos colidem. A ideia central é que, se existir um eixo no qual as projeções dos polígonos não se sobreponham, eles não estão em colisão. Os eixos a serem testados são as normais das arestas dos polígonos.

Para corpos convexos de dimensionalidade arbitrária, o algoritmo GJK é altamente eficiente. Ele determina a interseção construindo iterativamente um simplex dentro da diferença de Minkowski das formas e verificando se ele contém a origem.

struct Ponto {
    float coordenadas[3];
    Ponto operator-(const Ponto& outro) const {
        return {coordenadas[0] - outro.coordenadas[0],
                coordenadas[1] - outro.coordenadas[1],
                coordenadas[2] - outro.coordenadas[2]};
    }
};

float ProdutoEscalar(const Ponto& a, const Ponto& b) {
    return a.coordenadas[0]*b.coordenadas[0] + a.coordenadas[1]*b.coordenadas[1] + a.coordenadas[2]*b.coordenadas[2];
}

Ponto FuncaoSuporte(const std::vector<Ponto>& formaA, const std::vector<Ponto>& formaB, const Ponto& direcao) {
    auto pontoMaisDistante = [&direcao](const std::vector<Ponto>& conjunto) {
        Ponto melhor = conjunto[0];
        float maximo = ProdutoEscalar(conjunto[0], direcao);
        for (size_t i = 1; i < conjunto.size(); ++i) {
            float valor = ProdutoEscalar(conjunto[i], direcao);
            if (valor > maximo) {
                maximo = valor;
                melhor = conjunto[i];
            }
        }
        return melhor;
    };
    Ponto pontoA = pontoMaisDistante(formaA);
    Ponto pontoB = pontoMaisDistante(formaB); // Encontra o ponto mais distante na direção oposta
    pontoB.coordenadas[0] = -pontoB.coordenadas[0]; pontoB.coordenadas[1] = -pontoB.coordenadas[1]; pontoB.coordenadas[2] = -pontoB.coordenadas[2];
    return pontoA - pontoB;
}

Quando a detecção de colisão por GJK confirma uma interseção, o algoritmo EPA pode ser empregado para calcular a profundidade de penetração mínima e o vetor de separação correspondente, crucial para a resposta física. O EPA expande iterativamente um politopo a partir do simplex final do GJK até encontrar a face mais próxima da origem.

Para cenários com objetos em movimento rápido, a detecção de colisão discreta pode resultar em objetos que "pulam" uns sobre os outros. A detecção de colisão contínua (CCD) resolve isso analisando a trajetória do objeto ao longo do passo temporal. Uma abordagem comum é varrer um volume (como uma caixa AABB) ao longo do vetor de velocidade e calcular o primeiro instante de contato (TOI).

struct ResultadoCCD {
    bool houveColisao;
    float instanteDoImpacto;
};

ResultadoCCD VerificaAABBEmMovimento(const CaixaLimitadora& caixaEstacionaria, const CaixaLimitadora& caixaMovel, const Vetor3D& velocidadeMovel, float tempoMaximo) {
    float tEntrada = 0.0f;
    float tSaida = tempoMaximo;
    for (int eixo = 0; eixo < 2; ++eixo) { // Simplificado para 2D
        float velocidadeEixo = (eixo == 0) ? velocidadeMovel.x : velocidadeMovel.y;
        if (velocidadeEixo == 0.0f) continue;
        float t1, t2;
        if (velocidadeEixo > 0) {
            t1 = (caixaEstacionaria.minX - caixaMovel.maxX) / velocidadeEixo;
            t2 = (caixaEstacionaria.maxX - caixaMovel.minX) / velocidadeEixo;
        } else {
            t1 = (caixaEstacionaria.maxX - caixaMovel.minX) / velocidadeEixo;
            t2 = (caixaEstacionaria.minX - caixaMovel.maxX) / velocidadeEixo;
        }
        tEntrada = std::max(tEntrada, t1);
        tSaida = std::min(tSaida, t2);
        if (tEntrada > tSaida) return {false, 0.0f};
    }
    return {true, tEntrada};
}

Para otimizar o desempenho em cenas complexas, estruturas de dados espaciais como grid hashing, quadtree (para 2D) e octree (para 3D) são indispensáveis. Elas particionam o espaço e organizam os objetos, reduzindo drasticamente o número de testes de colisão de pares potenciais na fase ampla.

Em motores de físicca modernos, a arquitetura de detecção de colisão é frequentemente em múltiplas camadas. A primeira camada usa estruturas espaciais para identificação rápida de pares de sobreposição. Uma segunda camada aplica testes mais precisos (AABB, esferas) nos candidatos. Finalmente, uma terceira camada utiliza algoritmos exatos (SAT, GJK) para geometrias complexas. O uso de memória contígua e técnicas de processamento em lote (batch processing) com instruções SIMD pode melhorar a eficiência significativamente.

A integração com outros sistemas, como o módulo de resposta física, requer uma comunicação eficiente do vetor de penetração mínima (MTV) calculado. Para simulações que envolvem aprendizado por reforço ou treinamento de IA, a latência baixa na troca de dados entre o ambiente de simulação física e o framework de ML (como PyTorch ou TensorFlow) é crítica, muitas vezes alcançada através de memória compartilhada ou interfaces de alto desempenho.