operações booleanas em malhas

15

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

lathomas64
fonte

Respostas:

10

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

JustBoo
fonte
+1 - eu ia postar os mesmos links, JustBoo - até que percebi que você me venceu! :)
jacmoe
obrigado! A terminologia Geometria Sólida Construtiva é exatamente o que eu precisava!
lathomas64
@jacmoe - A ironia é incrível e completa agora :-) Você merece crédito por alguns deles. Valeu.
JustBoo
alguns desses? : PI acredito que anotei todos lá atrás. : D Ainda assim, eles são apenas coisas básicas de CSG. A partir daí, fica muito peludo - nem mesmo os principais pacotes de modelagem comercial acertaram.
jacmoe
3

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.

Ricket
fonte
2

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.

JasonD
fonte
1

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

jpaver
fonte
11
Eu ia mencionar meu próprio material CSG, mas, aparentemente, alguém já fez: O)
Sander van Rossen