O Que É Um Polígono Não Convexo

Quando você desenha uma forma e o motor de colisão dela começa a falhar aleatoriamente, geralmente é porque você esqueceu de verificar se o polígono era convexo ou não

Isso aconteceu comigo há algum tempo num projeto de simulação 2D para um jogo de física simples. A cena inteira estava funcionando, até que objetos com formas irregulares começavam a atravessar paredes como se não existissem. A causa raiz era um polígono não convexo sendo processado como se fosse convexo pelo algoritmo de separação de eixos (SAT) que eu havia implementado. O SAT só funciona corretamente com polígonos convexos. Quando você aplica ele a uma forma côncava, as interseções simplesmente desaparecem do cálculo em certos ângulos e o resultado fica completamente imprevisível. Um polígono não convexo, também chamado de côncavo, é aquele em que pelo menos um dos seus ângulos internos mede mais de 180 graus. Isso significa que, se você traçar uma linha entre dois pontos qualquer dentro da forma, essa linha pode sair da área delimitada pelo polígono. No caso dos polígonos convexos, qualquer segmento que ligue dois pontos internos nunca sai da figura. A definição técnica é direta, mas a consequência prática é o que causa dor de cabeça em implementações reais. Na prática, a diferença se manifesta visualmente como uma "reentrância" ou "recorte" na borda da forma. Um star shape é um exemplo clássico. Um L também. Já um quadrado ou triângulo são sempre convexos, não importa como você os oriente. A propriedade de convexidade não depende do tamanho ou da posição, apenas da geometria interna dos ângulos.

Decomposição de polígonos côncavos em partes convexas

A solução mais comum para trabalhar com polígonos não convexos em sistemas de física ou renderização é decompor a forma em múltiplos polígonos convexos menores. Existem algoritmos específicos para isso. O método de triangulação de Ear Clipping é um dos mais usados quando você precisa converter tudo em triângulos, que são sempre convexos. Para uma decomposição mais eficiente em termos de número de peças, o algoritmo de Hertel-Mehlhorn costuma ser uma melhor escolha porque produz um número menor de polígonos convexos a partir de uma cadeia de pontos. Na minha experiência com a simulação mencionada, eu simplesmente parti o polígono problema em três triângulos usando uma triangulação e tratei cada triângulo como um corpo rígido separado dentro do mesmo framework de colisão. Isso resolveu o problema de atravessamento. O custo foi um leve aumento no overhead de processamento das colisões, mas nada que afetasse a performance no alvo que eu precisava. Para formas muito complexas com muitas reentrâncias, o número de partes convexas cresce e o ganho inicial de correção pode ser comprometido pelo custo computacional extra.

Pitfalls comuns que ninguém menciona em tutoriais básicos

O primeiro erro que vejo repetidamente é assumir que a ordem dos vértices não importa. Para um polígono não convexo, a sequência em que você passa os pontos define completamente a geometria. Se você invertê-la ou reordená-la arbitrariamente, o resultado pode ser um polígono auto-intersectante, o que quebra tanto a triangulação quanto qualquer teste de ponto interior. Sempre verifique se o polígono é simples — sem auto-interseções — antes de tentar decompor ou processar ele. O segundo erro crasso é confiar em bounding boxes únicas para polígonos côncavos em testes de colisão grossa. Uma bounding box apertada em torno de um polígono não convexo deixa muita área morta ao redor das reentrâncias. O resultado é que objetos passam perto o suficiente para uma colisão real mas não disparam o teste porque suas caixas delimitadoras não se sobrepõem. A workaround padrão é usar uma bounding volume hierárquica (BVH) ou, no mínimo, múltiplas bounding boxes sobrepostas que cubram as diferentes regiões da forma. Em cenários onde o desempenho é crítico e os polígonos não mudam de forma, pré-calculá-los e cacheá-los economiza muito mais tempo do que recalculá-los a cada frame.

Quando você deve simplesmente evitar polígonos não convexos

Se o seu sistema permite, a solução mais pragmática é nem chegar perto deles. Na minha linha de trabalho, a recomendação padrão é modelar formas complexas diretamente como conjuntos de primitivas convexas desde o início. Isso elimina a necessidade de decomposição em tempo de execução e remove uma classe inteira de bugs sutis. Ferramentas como o Box2D, por exemplo, não oferecem suporte nativo a polígonos côncavos justamente porque a decomposição pode introduzir instabilidade numérica em casos de borda, especialmente quando vértices ficam quase colineares ou quando as reentrâncias são extremamente agudas. Polígonos com ângulos internos menores que 5 graus tendem a causar problemas de precisão float em praticamente qualquer implementação de decomposição. Se você precisa desses detalhes finos, considere usar uma malha triangular diretamente ao invés de passar por uma cadeia de vértices e depois decompor. O caminho mais direto costuma ser o menos problemático.