Decomposição de uma malha côncava em um conjunto de malhas convexas

Gostaria de decompor uma malha côncava em um conjunto de malhas convexas por 2 razões:

1. Renderização transparente
2. Formas físicas

Existe um algoritmo que aceita um conjunto de triângulos (côncavo) como entrada e gera vários conjuntos de triângulos (convexos)? Eu gostaria que não preenchesse os buracos entre as partes da malha original.

Eu já me deparei com uma pequena idéia: encontre todas as arestas côncavas e divida as malhas ao longo dos aros. Estou no caminho certo? Como eu poderia implementar isso?

Eu diria que você está no caminho certo, mas criar um algoritmo ideal e / ou eficiente é outra questão: é um problema difícil. No entanto, a menos que seu interesse seja acadêmico, uma solução suficientemente boa pode ser suficiente.

Primeiro, se você não está interessado em criar sua própria solução, o CGAL já contém um algoritmo para decomposição convexa de poliedros: http://doc.cgal.org/latest/Convex_decomposition_3/index.html

Agora para o método; Como muitos problemas em 3D, geralmente é útil considerar o problema em 2D que é mais fácil de entender. Para 2D, a tarefa é identificar vértices de reflexo e dividir o polígono em dois criando uma nova aresta (e possivelmente novos vértices) a partir desse vértice de reflexo, e continuando até que você não tenha vértices de reflexo (e, portanto, polígonos totalmente convexos) )

Decomposição de polígonos por J. Mark Keil contém o seguinte algoritmo (de forma não otimizada):

diags = decomp(poly)
    min, tmp : EdgeList
    ndiags : Integer
    for each reflex vertex i
        for every other vertex j
            if i can see j
                left = the polygon given by vertices i to j
                right = the polygon given by vertices j to i
                tmp = decomp(left) + decomp(right)
                if(tmp.size < ndiags)
                    min = tmp
                    ndiags = tmp.size
                    min += the diagonal i to j
    return min

Basicamente, compara exaustivamente todas as partições possíveis e retorna a que possui as menos diagonais produzidas. Nesse sentido, é um pouco de força bruta e ideal também.

Se você deseja decomposições de "aparência mais agradável", ou seja, que produzem formas mais compactas do que alongadas, você também pode considerar esta produzida por Mark Bayazit , que é ganancioso (portanto, muito mais rápido) e parece mais agradável, mas tem algumas falhas. Basicamente, funciona tentando conectar os vértices reflexos ao melhor oposto a ele, normalmente a outro vértice reflexo:

Uma das deficiências é que ele ignora decomposições "melhores" criando pontos Steiner (pontos que não existem em uma aresta existente):

O problema em 3D pode ser semelhante; em vez de vértices reflexos, você identifica "arestas de entalhe". Uma implementação ingênua seria identificar bordas de entalhe e executar cortes planos no poliedro repetidamente até que todos os poliedros sejam convexos. Confira "Partições convexas de poliedros: um algoritmo ideal de limite inferior e pior caso", de Bernard Chazelle, para obter mais detalhes.

Observe que essa abordagem pode produzir, no pior caso, um número exponencial de sub-poliedros. Isso ocorre porque você pode ter casos degenerados como este:

Mas se você tiver uma malha não trivial (pense em uma superfície irregular), obterá resultados ruins de qualquer maneira. É muito provável que você queira fazer muita simplificação antecipadamente, se precisar usá-lo para malhas complexas.

O cálculo de uma decomposição convexa exata de uma superfície S é um problema difícil de NP e geralmente produz um grande número de clusters. Para superar essas limitações, a restrição exata de convexidade pode ser relaxada e uma decomposição convexa aproximada de S é computada. Aqui, o objetivo é determinar uma partição dos triângulos de malha com um número mínimo de clusters, garantindo que cada cluster tenha uma concavidade menor que um limite definido pelo usuário.

Confira as seguintes bibliotecas de decomposição convexa aproximadas: https://code.google.com/p/v-hacd/ http://sourceforge.net/projects/hacd/

Aqui está um código que pode ajudá-lo. É em java, então você terá que convertê-lo em c ++.

Aqui também está outro artigo que pode ajudá-lo