Algoritmo o software para cortar una malla

Question

¿Cuál es el enfoque correcto para cortar una malla 3D? Las mallas son todas superficies cerradas y las rebanadas deben ser imágenes binarias de lo que hay dentro de la malla. Entonces, por ejemplo, una malla que representa una esfera y las imágenes de corte son las de círculos rellenos.

Estoy buscando una biblioteca de software o un algoritmo que pueda integrar en mi proyecto actual de C++.

Answer 1

Mi biblioteca de juegos de código abierto contiene una implementación de malla de corte. Funciona con la API de Irrlicht, pero podría reescribirse para usar una API diferente con un esfuerzo modesto. Puede usar el código bajo los términos de la licencia BSD, o aprender de ello un implemento propio.

Ver MeshTools :: splitMeshZ en this file for an implementation of mesh slicing.

Si lo que desea es conocer el algoritmo, he aquí una descripción de alto nivel de lo que hice:

inicialmente pensé en el uso de un cuadro delimitador eje alineado para especificar dónde cortar la malla. Esto fue problemático porque introdujo muchos casos especiales. Por ejemplo, un borde que cruza la esquina de la caja se puede dividir en tres partes en lugar de solo dos.

El uso de un plano para cortar la malla en una malla izquierda y una malla derecha reduce el número de casos especiales, porque un borde está en un lado del plano o del otro, o cruza el plano y también lo está cortado en exactamente dos pedazos.

Cualquier configuración de cortes deseada se puede hacer simplemente cortando una vez, tomando una de las mallas resultantes y cortándola nuevamente en otra ubicación, y así sucesivamente. Específicamente en el caso que describa en la sección, se puede cortar un círculo de una esfera cortando la mitad de la esfera, moviendo el plano una pequeña cantidad y cortando la otra mitad dejando solo una banda delgada. (No se puede cortar una malla hasta literalmente sin profundidad con el código que escribí, pero se puede cortar una malla hasta lo que haya establecido como el umbral de igualdad de coma flotante. Creo que elegí arbitrariamente 0,001 en mi código).

Usando una lógica similar, cualquier ángulo deseado del plano de corte se puede lograr usando un plano fijo; solo necesita transformar la malla para rotarla en relación con el plano de corte fijo, y luego transformar el resultado. (Para mi juego, solo necesitaba cortes perpendiculares al plano XY, así que para simplificar solo permito que se establezca el valor Z del corte, y supongo que el corte está en esa ubicación Z.)

OK, ahora que hemos simplificado el problema, el algoritmo no es tan malo:

condición de inicio: Usted tiene un plano de corte. Tienes un conjunto de triángulos fuente. Tiene dos conjuntos de destino de polígonos (no triángulos; los cuatriciclos se pueden generar cortando el triángulo). Los dos conjuntos de destinos se llaman Izquierda y Derecha.

Proceso: Iterar más de tres puntos de un triángulo. Cuente el número de puntos que son menores que el plano de corte. Llamaré a esos menos que el plano de corte a la izquierda y los que son mayores que el plano de corte a la derecha. Hay sólo un puñado de casos:

• Todos los puntos del triángulo están a la izquierda: poner el triángulo en el conjunto izquierdo
• Todos los puntos están a la derecha: poner el triángulo de la derecha conjunto
• Uno el punto está a la izquierda, otros están a la derecha: si cortas un triángulo a través de dos bordes y sostienes uno de los puntos, terminas sosteniendo un triángulo más pequeño. Ponga un triángulo en el conjunto izquierdo formado por el punto izquierdo, y los dos puntos donde los bordes cruzan el plano. Coloque un quad en el conjunto de la derecha (vea el siguiente caso).

• Dos puntos quedan, un punto es el correcto. Si está sosteniendo un borde de un triángulo y lo corta a través de los otros dos bordes, se queda sosteniendo un trapezoide. Coloque un quad en el conjunto izquierdo compuesto por los dos puntos en su mano, más los dos puntos que cruzan el corte. Coloque un triángulo en el conjunto de la derecha (imagen de espejo del caso anterior).

• Cuando termine, convierta los quads en triángulos agregando un enlace en la parte más corta.

Eso es todo. Ese es el algoritmo básico. El código real maneja algunos casos más, como qué pasa si un borde es exactamente igual al corte, qué pasa si un triángulo está exactamente en el borde, no agrega polígonos degenerados (por ejemplo, un punto sin cuerpo), etc.

Misc. temas (todos los cubiertos en el código relacionado):

• No complicar los cálculos por LERP'ing el punto donde cruza el borde del plano de corte. No necesita una interpolación lineal completa, en realidad es High School secundaria Álgebra II: aumentar sobre la carrera, multiplicada por

• Es ventajoso guardar en caché los puntos generados (LERP) para que los triángulos que comparten vértices en la malla sin cortar compartirá los nuevos vértices correspondientes en la malla de corte.

• Si va a conservar el uso compartido de vértices, y está utilizando los búferes de índice triangular, desafortunadamente aún no conoce el índice cuando genera las formas para colocarlas en los conjuntos izquierdo y derecho. Utilizo una clase llamada "PossibleVertex" para representar un número de índice triangular futuro.

• Si va a mostrar la malla, el orden de la bobina es importante. Una cuidadosa reflexión sobre cómo codificarlo puede garantizar que los polígonos resultantes usen el mismo orden de devanado que los triángulos de los que provienen. Esto se vuelve especialmente complicado cuando se triangulan los cuádriceps. No puedo recordar los detalles, pero todo se maneja en el código vinculado.

• Para mi juego, quería hacer una cinta plana que conectara dos mallas cortadas. Es por eso que splitMeshZ resulta en 3 mallas, en lugar de solo dos.Puedes usar la malla del medio o simplemente ignorarla.

Answer 2

Supongo que usted está hablando de mallas triangulares?

¿Cuál es el enfoque "correcto" depende en gran medida de las características específicas de su caso de uso.

El enfoque OpenGL sugerido por Jerry podría funcionar para usted.

Otro enfoque sería calcular explícitamente los cortes. Puede hacer esto con CGAL. Más específicamente con su kernel 3D. Tiene un function que puede calcular intersecciones entre todo tipo de primitivas, incluyendo un plano y un triángulo. Al usar esta función, puede calcular con precisión el contorno de su intersección y convertirlo en una imagen. - De esta forma, no dependería de OpenGL, sino de CGAL.

Answer 3

He descrito el algoritmo para calcular las intersecciones de plano-volumen en this answer. Se proporciona una implementación en Java.

Answer 4

Sería más rápido (por sí mismo, no se está ejecutando en tiempo) si se implementa por sí mismo: Estos son los pasos que hay que hacer:

1-Extraer todos los triángulos de la malla

2-para cada triángulo,

2-1- comprobar si alguno de los puntos del triángulo están en la rebanada de plano,

2-2- si no, entonces para cada uno de sus tres bordes, encontrar la intersección ion con su plano de corte (si hay alguno). Debe tener 2 de ellos cruzados con el avión o ninguno.

2-2-1 Si se intersectan 2 bordes con el plano, se agrega una línea entre estos 2 puntos en el plano.

Answer 5

Un proyecto en el corte en lonchas malla 3D (con un código fuente en C++):

http://www.dainf.ct.utfpr.edu.br/~rminetto/projects/slicing/