Stockage efficace pour un octree rare?

Question

Quelqu'un peut-il suggérer un , une méthode efficace pour stocker et accéder à un octree rare?

De préférence quelque chose qui peut être facilement implémenté dans HLSL.(Je travaille une application Raycasting / Voxel)

Dans ce cas, l'arborescence peut être préalculée, donc je suis surtout préoccupé par la taille et la durée de recherche.

mise à jour

Pour que quiconque cherche à le faire, une solution plus efficace peut être de stocker les nœuds comme un octree linéaire généré avec une courbe / morton de commande z.Cela élimine le stockage des nœuds internes, mais peut nécessiter une référence croisée de la matrice arborescente linéaire avec une seconde "texture de données", contenant des informations sur le voxel individuel.

Answer 1

Je ne suis pas très expérimenté chez HLSL, je ne suis donc pas sûr que cela réponde à vos besoins, voici mes pensées. Faites-moi savoir si quelque chose ici n'est pas sain d'esprit pour vos besoins - j'aimerais discuter alors peut-être que je peux apprendre quelque chose moi-même.

1. Chaque nœud de l'octree peut exister comme un vecteur3, où le composant (x, y, z) représente le point central du nœud. Le composant W peut être utilisé comme champ de drapeaux. une. Le champ W-Flags peut indiquer quels nœuds d'enfant d'octant suivent le nœud actuel. Cela nécessiterait 8 bits de la valeur.
2. Chaque entité stockée dans votre octree peut être stockée sous forme de boîte de sélection, où R, G, B peut être les dimensions de la boîte de sélection, et W peut être utilisé pour tout.
3. Définissez un vecteur spécial indiquant qu'une liste d'objets suit. Par exemple, si la (W + Z) est une valeur magique. Certains func (x, y) peuvent, disent, être le nombre d'objets qui suivent. Ou quel que soit le travail. une. Chaque nœud est potentiellement suivi de ce vecteur spécial, indiquant qu'il existe des objets stockés dans le nœud. Les vecteurs x suivants sont tous des identificateurs d'objet ou quelque chose comme ça. b. Sinon, vous pouvez avoir un nœud qui spécifie simplement une liste d'objets dans la mémoire. Encore une fois, je ne sais pas ce dont vous avez besoin ici ou des contraintes sur la manière d'accéder aux objets.

Alors, d'abord, construisez l'octree et tapez-le avec vos objets. Ensuite, marchez simplement l'octree, émettant les vecteurs sur un tampon de mémoire.

Je pense que une texture 512x512 peut contenir des niveaux d'Octree 5 entièrement emballés de profondeur (32 768 nœuds), chacun contenant 8 objets. Ou un octree à 4 niveaux entièrement emballé avec 64 objets chacun.

Answer 2

Il y a un excellent article sur des octrees clairsemés sur GPU: voxel précis efficaceOctrees - Analyse, extensions et mise en œuvre