Construire un Octree pour la génération de terrain

9

J'ai déjà implémenté des cubes de marche / tétraèdres pour rendre une IsoSurface. Cela a fonctionné ( YouTube ), mais les performances ont été désastreuses car je n'ai jamais réussi à implémenter un niveau de détail variable en fonction de la distance de vue (ou même à supprimer d'anciens morceaux distants).

J'ai décidé de recommencer et de le faire correctement cette fois. J'ai commencé par créer un OctreeNode qui fonctionne comme suit quand Build()est appelé.

  • Si le bloc est trop petit pour être construit, revenez immédiatement.
  • Déterminez si la surface traverse le volume de ce morceau.
  • Si oui, alors décidez si nous voulons augmenter la LOD (car la caméra est proche)
  • Si oui, générez 8 enfants et appelez le même processus sur eux
  • Sinon, créez le maillage en utilisant les dimensions du nœud actuel

Quelques PseudoCode:

OctNode Build() {
    if(this.ChunkSize < minChunkSize) {
        return null;
    }
    densityRange = densitySource¹.GetDensityRange(this.bounds);
    if(densityRange.min < surface < densityRange.max) {
        if(loDProvider.DesiredLod(bounds > currentLoD) {
            for(i 1 to 8) {
                if(children[i] == null) {
                    children[i] = new OctNode(...)
                }
                children[i] = children[i].Build();
            }
        } else {
            BuildMesh();
        }
        return this;
    }
}

¹ En plus de renvoyer la densité en un point, la source de densité peut déterminer la plage de densité possible pour un volume donné.

² Le fournisseur LoD prend une boîte englobante et renvoie la LoD maximale souhaitée en fonction de la position / tronc de la caméra, des paramètres utilisateur, etc.

Alors ... Tout cela fonctionne assez bien. En utilisant une sphère simple comme source de densité et en montrant tous les nœuds:

Octree complet

Et juste les feuilles:

Octree ne montrant que les feuilles

Cependant, il y a quelques problèmes:

  • Je dois définir le volume englobant initial (et plus il est grand, plus je dois faire de traitement)
  • À la racine de l'arbre, je n'ai aucune idée de la profondeur des feuilles, donc ma numérotation LoD commence à la qualité la plus basse (racine) et augmente à mesure que les morceaux deviennent plus petits. Parce que LoD est maintenant relatif au volume initial, ce n'est pas très utile lorsque je veux faire des choses à des tailles / qualités spécifiques.

J'ai pensé à quelques options, mais les deux semblent défectueuses:

  • Maintenir une collection d'octrees et ajouter / supprimer en fonction de la distance. Je ne vois pas comment je maillerais bien¹, et j'aurais besoin d'une liste de nœuds vides connus, surtout si je veux des surfaces 3D arbitraires (pour éviter de recalculer les volumes vides à plusieurs reprises)
  • Ajoutez un nœud parent à la racine actuelle, puis ajoutez sept frères et sœurs pour le nœud d'origine. Cela fonctionnerait et serait à la demande, mais il semble complexe de reculer sensiblement lorsque le joueur se déplace dans le paysage. Cela rendrait également les numéros LoD encore moins significatifs.

¹ [Pour clarifier Q ci-dessous] À l'heure actuelle, si 2 nœuds physiquement adjacents dans l'arbre sont à des niveaux de détail différents, j'ai du code pour forcer les verts de sorte qu'il n'y ait pas de couture lorsque les mailles sont générées. Je peux le faire en connaissant la densité de plusieurs nœuds environnants. Dans un scénario où j'ai deux octets indépendants côte à côte, je n'aurais aucun moyen facile de récupérer ces informations, ce qui entraînerait des coutures.

Quelle est la meilleure façon d'aborder cela?

De base
la source

Réponses:

1

Je ne suis pas sûr de répondre à la question exacte, donc je vais répondre par segments, et n'hésitez pas à répondre dans les commentaires s'il y a un malentendu sur les détails d'une question spécifique.

Je dois définir le volume englobant initial (et plus il est grand, plus je dois faire de traitement)

Cela ne semble pas être le cas. Étant donné que l'octree augmente de manière exponentielle dans la granularité, l'ajout de quelques niveaux au sommet devrait être une très petite augmentation nette des performances.

À la racine de l'arbre, je n'ai aucune idée de la profondeur des feuilles, donc ma numérotation LoD commence à la qualité la plus basse (racine) et augmente à mesure que les morceaux deviennent plus petits. Parce que LoD est maintenant relatif au volume initial, ce n'est pas très utile lorsque je veux faire des choses à des tailles / qualités spécifiques.

Si vous corrigez votre octree racine à une "valeur suffisamment grande", alors "LoD par rapport au volume initial" ne devrait pas être un problème. Et comme mentionné ci-dessus, je ne pense pas qu'avoir un niveau supplémentaire au sommet aura un impact sur les performances globales.

Maintenir une collection d'octrees et ajouter / supprimer en fonction de la distance. Je ne vois pas comment je maillerais bien, et j'aurais besoin d'une liste de nœuds vides connus, surtout si je veux des surfaces 3D arbitraires (pour éviter de recalculer les volumes vides à plusieurs reprises)

Si je comprends bien, cette solution proposée consiste à réduire la LoD lorsque vous vous éloignez d'une zone précédemment détaillée. Je pense que cela devrait ressembler beaucoup au chemin du code "croissant LoD":

if (loDProvider.DesiredLod(bounds) <(is a lot less than)< currentLoD) { 
    for(i = 1 to 8) { 
        children[i].Destroy();
    }
    BuildMesh();
}

Ensuite, vous ne passez pas trop de temps à vérifier les nœuds distants car vous pouvez compter sur le fait que, bien que loin, il n'y a pas trop de nœuds "actifs", car tous les nœuds de plus haute résolution auront été supprimés.


En supposant que les petits nœuds sont à l'échelle de la roche, cela signifierait potentiellement des dizaines sinon des centaines de niveaux lorsque je voyage à travers un continent

Je pense que l'échelle logarithmique de l'octree le rend encore possible. Si votre niveau supérieur a une largeur de 1 000 000 000 000 m (ce serait 25 fois plus large que la Terre réelle et avec 625x la surface) et que vos bits de niveau le plus bas ont une largeur de 10 cm, cela fait 32 niveaux dans l'octree, ce qui est probablement assez gérable. Si vous vouliez une planète 100 fois plus large que la Terre (et avec 10000 fois plus de surface), ce ne sont que 3-4 niveaux supplémentaires dans votre octree. À ce stade, il faudrait des centaines d'années à un joueur pour parcourir le monde, et si vous utilisez des mathématiques en virgule flottante naïves, le monde accumulera des erreurs de précision.

Maintenir une collection d'octrees et ajouter / supprimer en fonction de la distance. Je ne vois pas comment je maillerais bien¹, et j'aurais besoin d'une liste de nœuds vides connus, surtout si je veux des surfaces 3D arbitraires (pour éviter de recalculer les volumes vides à plusieurs reprises)

N'est-ce pas fondamentalement équivalent à avoir l'octree d'un milliard de kilomètres de large, mais à garder une liste de pointeurs pour chaque bloc, disons, de 1 km? Ensuite, le «maillage transversal» reposerait simplement sur les nœuds de 2 km. Garder une référence locale à chaque "grand bloc" de niveau intermédiaire vous évite également d'avoir à parcourir les nœuds de niveau supérieur, si vous êtes préoccupé par les "peut-être des dizaines de niveaux d'octree supplémentaires"

Jimmy
la source
Merci de répondre. Je ne peux pas simplement choisir un volume initial massif car mon terrain est infini (c'est mon objectif). Regardez la vidéo pour vous faire une idée. En tant que tel, mon arbre de nœuds deviendrait de plus en plus élevé. En supposant que les petits nœuds sont à l'échelle de la roche, cela signifierait potentiellement des dizaines sinon des centaines de niveaux lorsque je voyage à travers un continent. Re: Maillage à travers, permettez-moi d'ajouter plus de détails à la question [Terminé]
Basic
en ce qui concerne le joueur, "un milliard de miles" est assez proche de "l'infini". Plus d'arguments pour un volume initial fixe ajoutés pour répondre.
Jimmy
Je ne suis toujours pas convaincu. Pourquoi avoir plus de 30 couches de traitements inutiles connus? Ce n'est pas élégant, et encore moins efficace. Je prends votre point sur le temps de traverser, mais nous parlons simplement de génération de terrain. Rien qui dit que je dois centrer à l'origine, ni que voler à grande vitesse n'est pas possible (même si je ne serais pas en prise à cette vitesse!). FWIW J'utilise des doubles en interne pour éviter ce problème de précision.
Basic