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

10

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?

jmegaffin
fonte
O que é malha "côncava / convexa"? Se malha significa rede triangular, então é apenas um conjunto de triângulos, que são convexos. Ou você está falando sobre o volume de objetos 3D? Talvez poliedros?
precisa saber é o seguinte
@IvanKuckir Malhas, ou poliedros, também podem ser côncavos / convexos, e a definição é praticamente a mesma. Por exemplo, nenhuma linha reta cruzará o interior do poliedro mais de uma vez.
congusbongus

Respostas:

11

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) )

vértices reflexos

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:

bayazit new vértice bayazit conectar 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):

decomposição de trevo usando dois pontos de direção

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.

poliedro com entalhe

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:

muitos poliedros entalhados

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.

congusbongus
fonte
6

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.

Decomposição convexa exata vs. decomposição convexa aproximada

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

khaled
fonte
0

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


fonte
1
Olá Rebelde Mascarado, as respostas somente para links são desencorajadas aqui. Se a URL for alterada ou o recurso ficar indisponível, ele poderá deixar respostas que dependem totalmente do link completamente vazias de soluções para usuários futuros. É ótimo fornecer links para crédito e outras leituras, desde que sua resposta ainda possa ser autônoma e fornecer um guia para resolver o problema mesmo antes de o leitor clicar mais. Considere editar esta resposta para incluir pelo menos uma descrição geral de como a solução à qual você está vinculando funciona.
DMGregory
@DMGregory Exclua a resposta que não consigo.
A resposta não precisa necessariamente ser excluída. Apenas editá-lo para incluir mais informações pode torná-lo uma ótima resposta.
DMGregory
@DMGregory, mas será uma duplicata de outra resposta nesta postagem. Vou apenas editar a outra resposta e colocar minhas informações lá.
Suponho que você sentiu que tinha algo a acrescentar quando compartilhou esta resposta em primeiro lugar. Não duvido que você possa explicar o código vinculado de uma maneira que não seja uma cópia oculta de uma resposta existente. Se você preferir excluí-lo, o link para isso está disponível na versão para desktop do site.
DMGregory