Memoria efficiente per un octree sparso?

Question

Qualcuno può suggerire un veloce , metodo efficiente per la memorizzazione e l'accesso a un octretto sparso?

Preferibilmente qualcosa che può essere facilmente implementato in HLSL.(Sto lavorando a un'app Raycasting / Voxel)

In questo caso, l'albero può essere precalcolato, quindi sono per lo più preoccupato per le dimensioni e il tempo di ricerca.

Aggiornamento

Per chiunque cerchi di farlo, una soluzione più efficiente potrebbe essere quella di memorizzare i nodi come octree lineare generato con una curva / curva di z-ordine / albero di Morton.Fare quindi elimina la memorizzazione dei nodi interni, ma potrebbe richiedere il referenziamento cross-referenziamento dell'array dell'albero lineare con una seconda "texture di dati", contenente informazioni sul singolo voxel.

Answer 1

Non sono molto esperto a Hlsl, quindi non sono sicuro che questo soddisferà le tue esigenze, ecco i miei pensieri. Fammi sapere se qualcosa qui non è sano per le tue esigenze - mi piacerebbe discutere quindi forse posso imparare qualcosa da solo.

.
1. Ogni nodo nell'OCtree può esistere come vettore3, dove il componente (x, y, z) rappresenta il punto centrale del nodo. Il componente W può essere utilizzato come campo flags. un. Il campo W-Flags può denotare quali nodi figlio ottante seguono il nodo corrente. Ciò richiederebbe 8 bit del valore.
2. Ogni entità memorizzata nel tuo octree può essere memorizzata come box di delimitazione, dove R, G, B può essere la dimensione della scatola di delimitazione, e W può essere utilizzato per qualsiasi cosa.
3. Definisci un vettore speciale che denota che segue un elenco di oggetti. Ad esempio, se il (W + Z) è un valore magico. Alcune func (x, y) possono dire, essere il numero di oggetti che seguono. O, qualunque cosa funzioni. un. Ogni nodo è potenzialmente seguito da questo vettore speciale, indicando che ci sono oggetti memorizzati nel nodo. I prossimi X vettori sono tutti solo identificatori oggetto o qualcosa del genere. b. In alternativa, è possibile avere un nodo che specifica solo un elenco di oggetti in memoria. Ancora una volta, non sono sicuro di cosa ti serve qui o i vincoli su come accedere agli oggetti.

Allora, prima, costruisci l'octree e riempire con i tuoi oggetti. Quindi, basta camminare l'octree, emettendo i vettori a un buffer di memoria.

Sto pensando che una trama da 512x512 possa contenere un octretto completamente pieno di 5 livelli profondi (32.768 nodi), ciascuno contenente 8 oggetti. O, un octree a 4 livelli completamente imballato con 64 oggetti ciascuno.

Answer 2

C'è un ottimo articolo sullo octrees sparse focalizzato su GPU: Efficiente Voxel sparse VoxelOctrees - analisi, estensioni e implementazione