operaciones booleanas en mallas

15

dado un conjunto de vértices y triángulos para cada malla. ¿Alguien sabe de un algoritmo o un lugar para comenzar a buscar (primero probé en google pero no he encontrado un buen lugar para comenzar) para realizar operaciones booleanas en dichas mallas y obtener un conjunto de vértices y triángulos para la malla resultante? De particular interés son la resta y la unión.

Imágenes de ejemplo: http://www.rhino3d.com/4/help/Commands/Booleans.htm

graphics algorithm graphics-programming procedural lathomas64
fuente

Respuestas:

10

Pienso en esto como Constructive-Solid-Geometry (CSG). Espero que puedas encontrar ayuda aquí.

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

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

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

También busque en google para Geometría sólida constructiva como un comienzo.

HTH

JustBoo
fuente
+1: iba a publicar los mismos enlaces, JustBoo, ​​¡hasta que me di cuenta de que me ganaste! :)
jacmoe
¡Gracias! ¡La terminología Constructive-Solid-Geometry es exactamente lo que necesitaba!
lathomas64
@jacmoe - La ironía es increíble y completa ahora :-) Te mereces crédito por algunos de esos. Gracias.
JustBoo
algunos de esos? : PI creo que los anoté todos allá atrás. : D Aún así, son solo cosas básicas de CSG. A partir de ahí, se vuelve bastante difícil: ni siquiera los principales paquetes de modelos comerciales lo hicieron bien.
jacmoe
3

Creo que podemos resolverlo si solo pensamos en ello.

Obviamente, querrás crear caras (triángulos) donde las dos geometrías se crucen. Luego te quedan tres mallas: la intersección que acabas de aislar, la geometría 1 y la geometría 2.

Luego, simplemente borre lo que no necesita.

  • BooleanDifference: elimina la parte aislada y la geometría 2.
  • Intersección booleana: elimina la geometría 1 y 2, dejando la parte aislada
  • BooleanUnion: combina las geometrías 1 y 2 y elimina la parte aislada (asegúrate de unir las geometrías 1 y 2 en una geometría sólida)
  • BooleanSplit: separe la geometría 1, la geometría 2 y duplique la parte aislada (adjunte una a la geometría 1 y la otra a la geometría 2)

Creo que eso lo cubre, ¿eh? La parte difícil obviamente sería crear las caras de intersección. Para eso, recorra cada cara de una y verifique si esa cara es parte de la otra; si está totalmente adentro, copie la cara como parte de la malla de intersección. Si está parcialmente adentro, debe dividir el triángulo a lo largo de la línea de intersección; Creo que DirectX y OpenGL tendrían funciones auxiliares para esto, o son solo algunas matemáticas de planos 3D (vectores). Aprendí ese tipo de cosas en Calculus 3 (¿o fue 2?) Pero si no tienes idea, quizás preguntes en math.stackexchange.com . Y luego, por supuesto, si la cara está afuera, no hagas nada. Una vez que itera sobre todas las caras de ambas mallas, quedará con la malla de intersección.

Ricket
fuente
2

Si se trata de modelos poligonales, es posible que deba tratar con geometría no múltiple, lo que significa que la cuestión de qué está "adentro" y qué está "afuera" no está definida. Es complicado realizar una operación booleana si no sabe si tiene un 0 o un 1.

También debe lidiar con casos marginales, como polígonos coplanares, polígonos que intersecan bordes, vértices que se encuentran en bordes y / o caras, y cosas de esa naturaleza. Nada de lo cual es imposible, solo necesita una forma muy sólida de representar sus datos de malla y una definición precisa de lo que espera que suceda en esos casos.

JasonD
fuente
1

Vale la pena señalar que la mayoría de sus operaciones se pueden representar mediante negación y unión, donde la negación de cierta geometría es solo esa geometría con sus normales invertidos. Entonces, si puede lograr la unión correcta, entonces las otras operaciones deberían seguir:

  • intersección (A, B): =! unión (! A,! B)
  • restar (A y B): =! unión (! A, B)

Sander tiene algunas publicaciones de blog bastante buenas que discuten las implementaciones de CSG: http://sandervanrossen.blogspot.com/search/label/CSG

jpaver
fuente
1
Iba a mencionar mis propias cosas de CSG, pero aparentemente alguien más ya lo hizo: O)
Sander van Rossen