algorithm - many - instagram hashtags

Malla de geometría sólida constructiva

Question

Si construyo una forma usando técnicas constructivas de geometría sólida , ¿cómo puedo construir una malla de alambre para renderizar? Soy consciente de los algoritmos para representar directamente formas CSG, pero quiero convertirlo en una malla de alámbricas solo una vez para poder representarlo "normalmente"

Para agregar un poco más de detalle. Dada una descripción de una forma como "Un cubo aquí, una intersección con una esfera aquí, resta un cilindro aquí" Quiero poder calcular una malla poligonal.

Answer 1

Consulte también "Geometría sólida constructiva para poliedros triangulares" (1990) Philip M. Hubbard doi:10.1.1.34.9374

Answer 2

Estas bibliotecas parecen hacer lo que quieras:

www.solidgraphics.com/SolidKit/ carve-csg.com/ gts.sourceforge.net/

Answer 3

Hay dos enfoques principales. Si tiene un conjunto de formas poligonales, es posible crear un árbol BSP para cada forma, luego los árboles BSP se pueden fusionar. De Wikipedia,

1990 Naylor, Amanatides y Thibault proporcionan un algoritmo para fusionar dos árboles bsp para formar un nuevo árbol bsp a partir de los dos árboles originales. Esto proporciona muchos beneficios, entre ellos: la combinación de objetos móviles representados por árboles BSP con un entorno estático (también representado por un árbol BSP), operaciones CSG muy eficientes en poliedros, detección de colisiones exactas en O (log n * log n) y orden apropiado de Superficies transparentes contenidas en dos objetos interpenetrantes (se ha utilizado para un efecto de visión de rayos X).

El documento se encuentra aquí La fusión de árboles BSP produce operaciones de conjuntos poliédricos .

Alternativamente, cada forma se puede representar como una función en el espacio (por ejemplo, la distancia firmada a la superficie). Siempre que la superficie se defina como donde la función es igual a cero, las funciones se pueden combinar usando los operadores (MIN == intersección), (MAX == unión) y (NEGACIÓN = no) para imitar las operaciones establecidas. La superficie resultante se puede extraer como las posiciones donde la función combinada es igual a cero usando una técnica como Marching Cubes. También se pueden usar mejores métodos de extracción de superficie como Dual Marching Cubes o Dual Contouring. Esto, por supuesto, dará como resultado una aproximación discreta de la verdadera superficie CSG. Sugiero usar el Contorno dual , porque puede reconstruir características nítidas como las esquinas de los cubos.

Answer 4

He tenido un poco de suerte con la aplicación de BRL-CAD MGED donde puedo construir un poliedro convexo mediante la intersección de planos usando CSG y luego extraer la representación de límites usando el comando de línea de comandos g-stl. Compruebe http://brlcad.org/ Malcolm

Answer 5

Puede intentar triangular (tetraédrica) cada primitiva, luego realizar las operaciones booleanas en la malla tetraédrica, que es "más fácil" ya que solo necesita preocuparse por las operaciones de tetraedro-tetraedro. Luego puedes realizar la extracción de límites para obtener la B-rep. Como conoce las formas de sus primitivos de forma analítica, puede construir tetrahedralizations personalizadas de sus primitivos para satisfacer sus necesidades en lugar de confiar en una biblioteca de generación de malla.

Por ejemplo, supongamos que su objeto era la unión de un cubo y un cilindro, y suponga que tiene una tetraédrica de ambos objetos. Para calcular la representación de límites del objeto resultante, primero debe etiquetar todas las facetas de límites de los tetraedros de cada objeto primitivo. Luego, realiza la operación de unión: si dos tetraedros están separados, entonces no hay que hacer nada; ambos tetraedros deben existir en el poliedro resultante. Si se intersecan, entonces hay una serie de casos (probablemente del orden de una docena o menos) que deben ser manejados. En cada uno de estos casos, el volumen de los dos tetraedros debe volver a triangularse de manera que respete las restricciones de la superficie. Esto se hace más fácil por el hecho de que solo necesita preocuparse por los tetraedros, en lugar de formas más complicadas. Las etiquetas de facetas de límite deben mantenerse en el proceso de modo que en la colección final de tetraedros, las facetas de límite se puedan extraer para formar una malla triangular de la superficie.

Answer 6

Si puede convertir sus primitivas de entrada en mallas poliédricas, entonces podría usar las rutinas booleanas de malla C ++ de libigl. Lo siguiente calcula la unión de una malla (VA, FA) y otra malla (VB, FB):

igl::mesh_boolean(VA,FA,VB,FB,"union",VC,FC);

donde VA es un #VA por 3 matrices de posiciones de vértice y FA es un #FA por 3 matrices de índices de triángulos en VA, y así sucesivamente. La técnica utilizada en libigl es diferente de las dos mencionadas en la respuesta de Joe. Todos los pares de triángulos se intersecan entre sí (utilizando la aceleración espacial) y luego los sub-triángulos resultantes se clasifican como pertenecientes a la superficie de salida o no.

Answer 7

Here hay algunos enlaces de Google Scholar que pueden ser de utilidad.

Por lo que puedo decir de los resúmenes, la idea básica es generar una nube de puntos a partir de los datos volumétricos disponibles en el modelo CSG, y luego usar algunos algoritmos más comunes para generar una malla de caras en 3D para ajustar esa nube de puntos.

Editar: Investigando un poco más, este tipo de operación se llama "conversión de CSG a B-Rep (representación de límites)". Las búsquedas en esa cadena conducen a un PDF útil:

http://www.scielo.br/pdf/jbsmse/v29n4/a01v29n4.pdf

Y, para más información, el algoritmo clave se llama " Algoritmo de cubos que marcha ". Esencialmente, el modelo CSG se usa para crear un modelo volumétrico del objeto con voxels, y luego el algoritmo Marching Cubes se usa para crear una malla 3D a partir de los datos de voxel.