operações booleanas em malhas

dado um conjunto de vértices e triângulos para cada malha. Alguém sabe de um algoritmo ou de um lugar para começar a procurar (tentei o Google primeiro, mas não encontrei um bom lugar para começar) para executar operações booleanas nas malhas mencionadas e obter um conjunto de vértices e triângulo para a malha resultante? De particular interesse são subtração e união.

Imagens de exemplo: http://www.rhino3d.com/4/help/Commands/Booleans.htm

Penso nisso como Geometria Sólida Construtiva (CSG). Espero que você possa encontrar alguma ajuda aqui.

http://www.alsprogrammingresource.com/csg.html

http://createuniverses.blogspot.com/2009/09/qtcsg-constructive-solid-geometry.html

http://www.nigels.com/research/

Também procure no google por Geometria Sólida Construtiva como um começo.

HTH

Eu acho que podemos resolver isso se pensarmos sobre isso.

Obviamente, você desejaria criar faces (triângulos) onde as duas geometrias se cruzam. Então você tem três malhas: a interseção que você acabou de isolar, geometria 1 e geometria 2.

Em seguida, basta excluir o que você não precisa!

• BooleanDifference: exclua a peça isolada e a geometria 2.
• BooleanIntersection: exclua as geometrias 1 e 2, deixando a parte isolada
• BooleanUnion: mesclar as geometrias 1 e 2 e excluir a peça isolada (certifique-se de unir as geometrias 1 e 2 em uma geometria sólida)
• BooleanSplit: Separe a geometria 1, geometria 2 e duplique a parte isolada (anexe uma à geometria 1 e a outra à geometria 2)

Eu acho que isso cobre, né? A parte mais difícil seria obviamente criar as faces da interseção. Para isso, percorra cada face de uma e verifique se essa face faz parte da outra; se estiver totalmente dentro, copie a face como parte da malha de interseção. Se estiver parcialmente dentro, será necessário dividir o triângulo ao longo da linha de interseção; Eu acho que o DirectX e o OpenGL teriam funções auxiliares para isso, ou é apenas uma matemática de avião 3D (vetores). Aprendi esse tipo de coisa no Cálculo 3 (ou foi 2?), Mas se você não tem idéia, talvez pergunte em math.stackexchange.com . E então, claro, se o rosto estiver do lado de fora, não faça nada. Depois de percorrer todas as faces das duas malhas, você ficará com a malha de interseção.

Se você está lidando com modelos poligonais, pode ser necessário lidar com geometria não-múltipla, o que significa que a questão do que é "dentro" e do que é "fora" não está definida. É complicado executar uma operação booleana se você não souber se possui 0 ou 1.

Você também precisa lidar com casos marginais, como polígonos co-planares, polígonos que cruzam arestas, vértices que ficam nas arestas e / ou faces e coisas dessa natureza. Nada disso é impossível, você só precisa de uma maneira muito robusta de representar seus dados de malha e uma definição precisa do que você espera que aconteça nesses casos.

Vale a pena notar que a maioria de suas operações pode ser representada por negação e união, onde a negação de alguma geometria é exatamente essa geometria com suas normais invertidas. Portanto, se você conseguir acertar a união, as outras operações deverão apenas seguir:

• intersecção (A, B): =! união (! A,! B)
• subtrair (A e B): =! união (! A, B)

Sander tem algumas postagens de blog bastante boas que discutem as implementações de CSG: http://sandervanrossen.blogspot.com/search/label/CSG

Esse é um assunto bastante complicado, pelo menos se você quiser fazer isso de forma robusta (o ponto flutuante causa algumas sérias dificuldades).

Eu gostaria de apontar a literatura sobre geometria computacional / computação gráfica sobre o assunto, particularmente esses artigos recentes:

http://homes.cs.washington.edu/~gilbo/repofiles/booleans2009.pdf

http://openflipper.org/uploads/media/campen_2010_eg_02.pdf