Descomposición de una malla 3D en una red 2d

Question

Suponga que tiene un objeto en 3 dimensiones, representada como una malla 3D en algún formato de archivo común. ¿Cómo te diseñar un algoritmo para descomponer la malla en una o más redes '' - 2d., Es decir, una representación de 2 dimensiones que se puede cortar y plegar para crear el objeto original 3d

Entre otras cosas, el algoritmo se necesitaría para tener en cuenta:

• posibles descomposiciones múltiples para cualquier objeto dado
• Manejo de ajuste de una malla en lienzos de tamaño fijo (hojas de papel).
• Al reconocer cuando dos paneles en la red se superponen (y por lo tanto no válido).
• Rompiendo una malla en múltiples redes, si no pueden ser representadas como una sola, debido al solapamiento o las limitaciones de tamaño de página.
• Generación de pestañas en los lugares apropiados, para la fijación de las caras adyacentes.

El caso degenerado obvia es simplemente para crear un mosquitero por cara, con pestañas de la mitad de los bordes. Esto no es lo ideal, obviamente: El caso ideal es una sola red continua. La realidad de formas complejas es probable que sea en algún lugar en el medio.

Me doy cuenta de que la búsqueda de la red óptima (menor número de redes / menos páginas) es probablemente computacionalmente caro, pero una buena heurística para encontrar 'suficientemente bueno' redes sería suficiente.

Answer 1

Cuando leí su pregunta, las palabras "algoritmo papercraft automática" vinieron a mí. Así que busqué en Google y encontré utilizando Generalizado Cilindros (pdf) por Massarwi et al.

  

Se propone un nuevo método para la producción de   patrones papercraft desplegadas de   figuras de animales de juguete redondeadas de   mallas trianguladas por medio de   aproximación de banda base. Aunque en   principio un modelo triangulado puede ser   desplegado simplemente reteniendo tanto   como sea posible de su conectividad, mientras   la comprobación de intersección de triángulos en   el plano desplegada, creando un patrón   con decenas de miles de triángulos es   poco realista. Nuestro enfoque consiste en   aproximar el modelo de malla por un conjunto de   tiras de triángulos continua sin   vértices internos. Inicialmente, se   subdividir nuestra malla en partes   correspondiente a las características de la   modelo. Nos segmento de cada parte en zonal   regiones, triángulos de agrupación que son   distancias topológicas similares de la   parte límite. Generamos triángulo   tiras por la simplificación de la malla mientras   retención de las fronteras de la zonal   regiones y líneas de corte adicionales. los   patrón se creó entonces simplemente   desplegar el conjunto de tiras. los   característica distintiva de nuestro método   es que nos aproximamos un modelo de malla por   un conjunto de tiras continuas, no por   otras superficies regladas, tales como partes de   conos o cilindros. Por lo tanto, la   patrón desplegada aproximada puede ser   generado usando operaciones de malla sólo   y un simple algoritmo de despliegue.   Además, un conjunto de tiras puede ser   elaborado con sólo doblar el papel   (Sin romper bordes) y puede   representar características lisas de la   modelos de malla original.

También hay un artículo relacionado anterior llamado engrana (pdf 9MB) por Shatz et al.

  

Este documento presenta un algoritmo para   la segmentación de una malla en desarrollable   aproximaciones. El algoritmo puede ser   utilizado en diversas aplicaciones de CAD   y gráficos por ordenador. Este papel   se centra en la elaboración de papel y   demuestra que el algoritmo   genera aproximaciones que son   desarrollable, fácil de cortar, y puede haber   pegados juntos. También se muestra que   el error entre el modelo y dado   el modelo de papel es pequeño.

Fuente: http://www.ee .technion.ac.il / ~ ayellet / imágenes / sel-documentos-pic-5.jpg

Answer 2

Los algoritmos eed3si9n vinculados a generará agradable papercraft razonable mallas de geometría complicada. Si desea desplegar la malla tal y como se modela, como para los modelos de poliedros, entonces aquí es una técnica relativamente sencilla para desplegar cualquier malla, ya que se destacan

Construir una gráfica de su malla de origen donde cada cara es un vértice en el gráfico, y dos vértices se conectan si comparten un borde común en la malla. Uno de estos gráficos representa una malla desplegable si y sólo si no tiene bucles, es decir, se trata de un árbol.

Un buen árbol representa las líneas de plegado menor cantidad para llegar a la cara más alejada del punto de partida, ya que cada pliegue representa error que se acumulan en el modelo terminado. el algoritmo de Dijkstra es bueno aquí, pero el árbol de expansión mínimo no funciona. Con cada borde ponderada por igual todos los árboles son árboles de expansión mínima, incluso uno que se desarrollaría la malla en una gran espiral. Como pegado el modelo en conjunto, los errores se acumularían hasta los últimos caras no encajaba en absoluto.

Una vez que tenga el árbol, empezar por dibujar la cara de partida en el origen. Luego caminar el árbol y añadir las nuevas caras mediante el cálculo del nuevo vértice como la intersección de dos círculos con radios correspondientes a las longitudes de los bordes de la malla original. Ubicaciones para las fichas corresponden a los bordes que estaban en la malla original, pero no están en el árbol flattenable.

cortes especificado por el usuario pueden ser manipulados como deleciones de borde antes de la etapa de árbol.

Algunas desventajas de esta técnica son que va a crear felizmente partes superpuestas en el patrón plano, y es dependiente de la búsqueda de una buena cara de partida. Traté de Floyd-Warshal para encontrar una cara de diámetro mínimo para comenzar a partir, pero su O (n ^ 3) el comportamiento hice para tomar un café excesivamente largos. Las partes superpuestas podrían tratarse mediante el marcado de esa rama del árbol como "incompleta", saltando, y volver a ejecutar el algoritmo en todos los rostros incompletos de nuevo.

Answer 3

Sé que esto no es una respuesta, sino que se relaciona. Lamina programa ex SGI gráficos chico Paul Haeberli es una solución para este problema.