Dove immagazzino le forme in un ottetto?

Question

Un piccolo background sulle decisioni di design fino ad ora ... Ho sviluppato una struttura ad otto che può memorizzare punti. Ho scelto di limitare la ricorsione di "generazioni" in base a una determinata dimensione voxel di base. I nodi figli vengono creati solo quando i punti vengono aggiunti a quel nodo. Questo è non un'applicazione grafica dinamica: questo otto e gli oggetti in esso contenuti sono statici, quindi la pre-elaborazione per migliorare le prestazioni non è un problema.

Ora, vorrei aggiungere "forme" al mio otto - in particolare, una mesh di superficie composta da triangoli. I vertici di questi triangoli non corrispondono ai punti memorizzati nell'occhiello. Come si memorizzano queste forme nell'occhiello? Vedo due opzioni ...

nodi grigio sono "vuoto", nel senso che non hanno forme. Nell'alternativa 1, le forme vengono memorizzate in ogni nodo che intersecano, ovvero il nodo 1a contiene shape1 e 4c & 4d share shape2. Nell'alternativa 2, le forme sono memorizzate solo nel nodo più piccolo che intersecano, cioè il nodo 1a contiene shape1 e il nodo 4 contiene shape2.

La maggior parte dei post su octree che ho visto presuppongono Alt1, ma non spiegano mai perché. Alt2 ha più senso per me e creerà solo un lavoro extra per quelle forme che risiedono sui confini dei nodi. Perché è preferibile Alt1?

Modifica: per chiarire, il mio linguaggio di implementazione è C++, quindi preferirei implementazioni di esempio in quella lingua, ma la domanda è indipendente dalla lingua. Scusa se l'uso dei tag è errato.

Edit2: Sebbene non sia direttamente correlato alla questione dell'archiviazione delle forme, this link ha una buona discussione sull'ottava traversal dietro la domanda. Ho pensato che potesse aiutare chiunque fosse interessato a lavorare su questa domanda.

Answer 1

ALT1 è corretto. Dato che si desidera limitare il numero massimo di oggetti (triangoli) in un nodo, è necessario suddividere i nodi che conterranno molti triangoli. Ciò porta inevitabilmente ad avere un singolo triangolo in più nodi, a meno che non vogliate suddividere i triangoli in modo che si adattino perfettamente ai nodi octree (che dipende dalla vostra applicazione, in genere non lo consiglio e ad es. Per raytracing di solito non è fatto) .

Come controesempio, immagina ALT2 contenente un modello dettagliato del coniglio di Stanford, in piedi su un grande triangolo. Il grande triangolo impedirebbe la suddivisione del nodo radice in sottonodi e quindi il tuo albero sarebbe buono come se tu non avessi nessun ottetto.

In alternativa, è necessario mantenere il triangolo grande nel nodo radice e suddividerlo in sottonodi che conterranno il resto dei triangoli coniglietto più piccoli. Avere triangoli non solo nei nodi foglia, ma anche negli altri nodi probabilmente complicherà l'attraversamento di otto (ma dipende anche dalla tua applicazione). Se ci atteniamo allo scenario del raytracing, per trovare l'intersezione più vicina di un raggio e un triangolo, dovresti controllare un nodo e tutti i sottonodi per trovare l'intersezione più vicina e dovresti tenere traccia del movimento del raggio al nodo successivo, su tutti i livelli dell'albero contemporaneamente. D'altra parte, se la tua geometria è solo nelle foglie, prova i triangoli nelle foglie nell'ordine in cui il raggio li visita (tenendo traccia dei triangoli che sono stati già testati per evitare di testare lo stesso triangolo due volte).

Answer 2

Questo è più in riferimento a quadtrees che sono più familiare ma sono l'equivalente 2D di un ottetto; quindi potrebbe essere applicabile.

Gli approcci generali per l'inserimento: Ogni nodo interno di un quadrilatero ha una capacità che è il numero massimo di "oggetti" che un quadrangolo può contenere. Se si raggiunge la capacità, si suddividono e quindi si inseriscono tutti gli "oggetti" nel quadrante figlio appropriato. Avrai anche un punto in cui ti dividi e uno o più dei tuoi "oggetti" si trovano a cavallo di più quadranti figli; stai attento a quel caso quando inserisci/chiedi. Generalmente, la capacità del nodo viene scelta per favorire l'inserimento o l'interrogazione più veloce.

Quindi, tenendo conto di ciò, non vedo nulla di sbagliato con l'immagine di ALT2 che stai presentando. Ma la mia ipotesi sul perché si vede sempre l'immagine di ALT1 è l'approccio predefinito quando si inserisce in una cella non occupata è di suddividere e quindi inserire.