Poliedros Convexos E Não Convexos

O problema que ninguém conta sobre poliedros não convexos

Você tem uma malha complexa com recortes, aberturas ou formatos em L. Quer calcular volume, gerar colisão ou fazer uma malha simplificada. A primeira coisa que tenta é decompor o objeto em partes convexas. O resultado sai errado na maioria das vezes na primeira tentativa. Isso acontece porque a decomposição não é intuitiva como parece. Um poliedro qualquer pode ter dezenas de faces côncavas aninhadas umas nas outras. Tentar resolver à mão é inviável para malhas com mais de 200 vértices.

Poliedros convexos e não convexos: o básico técnico

Um poliedro é convexo quando o segmento de reta entre quaisquer dois pontos do seu interior permanece inteiramente contido no poliedro. Em termos práticos, não existe reentrância. Se você traçar uma linha de qualquer vértice a qualquer outro vértice, a linha não atravessa o exterior. Um poliedro não convexo tem pelo menos uma reentrância. Pode ser um recuo, um buraco interno, ou uma seção em formato de L. A definição matemática exige que exista pelo menos um par de pontos internos cuja conexão reta saia do poliedro em algum trecho.

A convicidade é propriedade importante porque muitos algoritmos só funcionam corretamente com geometria convexa. Ray tracing, detecção de colisão por separação de eixos, decomposição para física, cálculo de volume por triangulação — tudo isso assume convexidade ou precisa de um passo extra para lidar com não convexidade. Poliedros convexos e não convexos aparecem juntos em praticamente qualquer modelo 3D real. Um parafuso não é convexo. Um cubo furado não é convexo. A maioria dos objetos do cotidiano não é convexa.

Como decompor na prática

O método padrão é usar uma biblioteca de decomposição convexa. A mais estável que uso é o HACD — Hierarchical Approximate Convex Decomposition. Ele funciona em três fases: primeiro identifica as faces côncavas da malha original, depois agrupa os vértices em clusters que satisfazem o critério de convexidade com tolerância configurável, e por fim reconstrói as superfícies de cada cluster separadamente. O parâmetro chave é a tolerância. Valor zero exige convexidade perfeita, o que gera centenas de peças para uma forma simples. Valor alto (0.1 a 0.5 dependendo da escala) permite aproximação e reduz drasticamente o número de poliedros resultantes. Para simulação física, tolerância em torno de 0.02 costuma dar boa relação entre precisão e performance.

O HACD tem uma limitação séria: ele não lida bem com buracos topológicos internos. Se o seu modelo tem um túnel atravessando, a saída geralmente contém malhas sobrepostas ou mal formadas dentro do túnel. Nesses casos, o workaround que eu uso é pré-processar o modelo com uma malha de fechamento temporária antes da decomposição, rodar o HACD, e depois remover os triângulos de fechamento da geometria final manualmente onde necessário. Outra ferramenta viável é a libgdx ConvexDecomposition, que usa abordagem diferente baseada em cortes por planos. Ela costuma produzir menos peças, mas com formas mais grosseiras. Para modelagem de precisão artística, o HACD dá melhor resultado. Para colisão em jogo mobile, a libgdx às vezes é suficiente e mais rápida.

Pegadinhas que eu descobri no campo

A principal pegadinha é a orientação das faces. A decomposição convexa assume winding order consistente em toda a malha. Se metade das faces está invertida, o algoritmo interpreta mal a topologia e gera clusters conflitados. Eu resolvi isso criando um script de auto-winding antes de rodar qualquer decomposição. O script percorre arestas vizinhas, compara normais, e inverte triângulos onde a orientação não é coerente. A segunda pegadinha é a sensibilidade numérica em vértices muito próximos. Quando dois vértices estão separados por menos de 1e-6 na escala do objeto, o HACD pode tratá-los como duplicados e colapsar arestas, gerando furos na malha resultante. A solução é fazer um merge de vértices com threshold adequado antes da decomposição. Threshold de 1e-4 funciona para a maioria dos modelos em escala Unity.

Um problema específico que eu encontrei foi com uma escultura em formato de estrela cinzelada com 47 faces côncavas entrelaçadas. A decomposição direta gerou 112 peças, muitas delas degeneradas com volume zero. O workaround foi rodar duas passadas: primeira com tolerância alta para agrupamento grosseiro, segunda com tolerância baixa apenas nos clusters que ainda apresentavam concavidade acima do limiar. Isso reduziu para 23 peças úteis em vez de 112.

Cálculo de volume e propriedades em poliedros não convexos

Para volume, a abordagem mais confiável é decompor em tetraedros a partir de um vértice fixo e somar os volumes assinados. O sinal positivo ou negativo indica orientação do tetraedro, eliminando ambiguidade em formas complexas. O método funciona para qualquer poliedro simples, convexo ou não, desde que a malha seja fechada e sem auto-interseções. Para Centro de Massa, o processo é similar: converte-se em tetraedros, calcula-se o CM de cada um, e faz-se média ponderada pelo volume de cada tetraedro. A precisão depende diretamente da qualidade da triangulação da malha original. Malhas com triângulos muito distorcidos geram CM impreciso.

Para Momento de Inércia, a fórmula para um tetraedro homogêneo é conhecida e tabelada. Somando os momentos de cada tetraedro transferidos para o referencial desejado usando o teorema dos eixos paralelos, obtém-se o tensor completo do poliedro. Isso é implementável em poucas linhas de código se você já tem a lista de tetraedros. Se o poliedro tem cavidades internas seladas, o cálculo de volume inclui automaticamente o espaço vazio como negativo desde que a orientação das faces internas esteja invertida em relação às faces externas. Isso é padrão em boa parte das bibliotecas modernas, mas não em todas. Sempre verifique com um modelo de teste simples antes de confiar no resultado.

Quando a decomposição convexa não funciona

Existem cenários em que a abordagem padrão simplesmente falha. Malhas auto-intersectantes geram resultados sem sentido porque a noção de interior e exterior deixa de ser bem definida. Você precisa reparar a malha antes — ferramentas como o Blender Boolean modifier com operação de unificação, ou bibliotecas como CGAL para boolean operations em malhas trianguladas. Poliedros com topologia de superfície não trivial — esferas com múltiplos furos, toros, superfícies de genus maior que zero — produzem decomposições fragmentadas. A convexidade é propriedade local da superfície, e furos criam ambiguidade em como delimitar o interior. Nesse caso, o recomendado é tratar cada component conectada separadamente e depois recombinar os resultados.

Um problema frequente é a perda de resolução durante a decomposição. Cada cluster convexo recebe sua própria malha, e as superfícies de corte internas frequentemente têm triangulação grosseira. Se você precisa manter o visual original, use a decomposição apenas para cálculos geométricos e mantenha a malha original separada para renderização.

Alternativas quando o HACD não basta

Quando a tolerância baixa gera muitas peças e a tolerância alta perde detalhes importantes, existe a opção de decomposição hierárquica recortada. O conceito é: primeiro obter clusters grossos com HACD, depois subdividir apenas os clusters que ainda possuem concavidade mensurável acima do limiar desejado. Isso evita processar toda a malha com tolerância baixa desnecessariamente. Para simulações onde performance é crítica e forma aproximada basta, existe a técnica de convex hull approximation por camadas. Você gera o envelope convexo da malha inteira e subtrai progressivamente fatias planares. Não preserva a forma original, mas dá uma representação convexa hierárquica útil para LOD em colisões.

Se o seu fluxo envolve geração procedural de poliedros não convexos — por exemplo, noise displacement aplicado a um cubo — o problema de concavidade surge naturalmente. Nesse cenário, vale a pena implementar um pré-filtro de suavização antes da decomposição. Reduzir a amplitude das variações em 20% elimina a maioria das concavidades finas que seriam impossíveis de decompor com qualidade.

Referências e ferramentas

O artigo original do HACD está disponível em https://mgallagher.github.io/hacd/. A implementação em C++ é portável para Unity, Unreal, e projetos standalone. A versão para Unity é amplamente usada na comunidade de desenvolvimento de jogos. Para decomposição alternativa, a libgdx convex decomposition está em repositório oficial do libgdx. Funciona bem como segundo fallback quando o HACD produz resultados insatisfatórios.

Para reparo de malha prévia, o CGAL oferece operações booleanas robustas, mas exige mais configuração. Para uso rápido em Blender, o addon Instant Meshes ou a funcionalidade de Remesh do software resolvem a maioria dos problemas de winding e bordas abertas. A documentação oficial de cada ferramenta deve ser consultada para detalhes de API. Os conceitos descritos aqui cobrem o fluxo essencial sem entrar em especificidades de implementação de cada biblioteca.