scomporre un mesh 3D in un 2d rete

Question

Supponiamo di avere un oggetto tridimensionale 3, rappresentato come un mesh 3D in un formato di file comune. Come concepiresti un algoritmo per decomporre la mesh in una o più reti 2d, ovvero una rappresentazione bidimensionale che può essere ritagliata e piegata per creare l'oggetto 3d originale.

Tra le altre cose, l'algoritmo dovrebbe rappresentare:

• multiple scomposizioni possibili per un dato oggetto
• movimentazione sagomata una maglia in tele dimensione fissa (fogli di carta).
• Riconoscere quando due pannelli nella rete si sovrappongono (e quindi non sono validi).
• Rompere una rete in più reti se non possono essere rappresentate come una singola, a causa di sovrapposizioni o vincoli di dimensioni della pagina.
• Generazione di schede nelle posizioni appropriate, per il collegamento di facce adiacenti.

L'evidente caso degenerato è semplicemente quello di creare una rete per faccia, con linguette sulla metà dei bordi. Questo non è l'ideale, ovviamente: il caso ideale è una singola rete continua. La realtà per forme complesse è probabile che sia da qualche parte nel mezzo.

Mi rendo conto che trovare la rete ottimale (meno reti/meno pagine) è probabilmente computazionalmente costoso, ma una buona euristica per trovare reti "abbastanza buone" sarebbe sufficiente.

Answer 1

Quando ho letto la tua domanda, le parole "algoritmo papercraft automatico" è venuto da me. Così ho cercato su Google e ho trovato Papercraft Models using Generalized Cylinders (pdf) di Massarwi et al.

ci propone un nuovo metodo per produrre modelli papercraft unfolded arrotondati figure giocattolo animali da maglie triangolari mediante approssimazione strip-based. Sebbene in linea di principio un modello triangolare può essere dipana semplicemente mantenendo il più possibile della sua connettività mentre controllando intersecano triangoli piano dispiegata, creando un modello con decine di migliaia di triangoli è realistico. Il nostro approccio è quello approssimare la maglia modello da una serie di strisce di triangoli continue senza vertici interni. Inizialmente, abbiamo suddividendo la nostra mesh nelle parti corrispondenti alle caratteristiche del modello . Ci segmento ogni parte in zonali regioni, raggruppando triangoli che sono distanze topologici simili dal parte contorno. Generiamo triangolo strisce semplificando le maglie mentre mantenendo i confini delle zonali regioni ed altre cut-linee. Il motivo viene quindi creato semplicemente da spiegando il set di strisce. La caratteristica di distinzione del nostro metodo consiste nel fatto che approssimiamo un modello a maglie di un insieme di strisce continue, non da altre superfici rigate come parti di coni o cilindri . Pertanto, il modello approssimata può essere spiegato generato utilizzando solo maglie operazioni e un semplice algoritmo svolgimento. Inoltre, un set di strisce può essere creato semplicemente piegando la carta (senza bordi di separazione) e può rappresentare le caratteristiche uniformi dei modelli di mesh originali .

C'è anche un precedente documento correlato chiamato Paper craft models from meshes (9MB pdf) di Shatz et al.

Questo documento introduce un algoritmo per segmentare una maglia in sviluppabili approssimazioni. L'algoritmo può essere utilizzato in varie applicazioni in CAD e computer grafica. Questo documento è incentrato sulla creazione di carta e dimostra che l'algoritmo genera approssimazioni che sono sviluppabili, facili da tagliare e possono essere incollate insieme . Viene anche mostrato che l'errore tra il modello specificato e il modello di carta è piccolo.

Fonte: http://www.ee.technion.ac.il/~ayellet/images/sel-papers-pic-5.jpg

Answer 2

Gli algoritmi eed3si9n legati alla genererà bel papercraft ragionevole maglie dalla geometria complessa. Se desideri dispiegare la mesh esattamente come è modellata, ad esempio per i modelli di poliedri, ecco una tecnica relativamente semplice per dispiegare qualsiasi mesh così com'è

Costruire un grafico dalla mesh di origine in cui ogni faccia è una vertice nel grafico e due vertici sono connessi se condividono un bordo comune nella mesh. Uno di questi grafici rappresenta una mesh non divisibile se e solo se non ha loop, cioè è un albero.

Un albero buono rappresenta la minor numero di linee di piegatura per raggiungere la faccia più lontana dal punto di partenza, poiché ogni piega rappresenta l'errore che si accumula nel modello finito. L'algoritmo di Dijkstra è buono qui, ma lo spanning tree minimo non funziona. Con ogni spigolo equamente ponderato, tutti gli alberi sono alberi con spanning minimo, anche uno che dispiega la tua maglia in un'unica grande spirale. Quando hai incollato il modello, gli errori si sarebbero accumulati fino a quando le ultime facce non si sarebbero adattate affatto.

Una volta ottenuto l'albero, iniziare disegnando la faccia iniziale all'origine. Quindi cammina l'albero e aggiungi le nuove facce calcolando il nuovo vertice come l'intersezione di due cerchi con raggi corrispondenti alle lunghezze dei bordi nella mesh originale. Le posizioni per le schede corrispondono ai bordi che erano nella mesh originale, ma non si trovano nell'albero appiattito.

I tagli specificati dall'utente possono essere gestiti come delezioni di bordi prima della fase dell'albero.

Alcuni inconvenienti di questa tecnica sono che felicemente creare parti sovrapposte nel modello piatto, ed è dipendente da trovare un buon faccia partenza. Ho provato Floyd-Warshal a trovare una faccia dal diametro minimo da cui partire, ma il suo comportamento O (n^3) è stato concepito per pause caffè eccessivamente lunghe. Le parti sovrapposte potrebbero essere gestite contrassegnando quel ramo dell'albero come "incompleto", saltandolo e ripetendo di nuovo l'algoritmo su tutte le facce incomplete.

Answer 3

So che questa non è una risposta, ma è correlata. Il programma di grafica di Ex-SGI, il programma di Paul Haeberli Lamina, è una soluzione per questo problema.