Voxel Face Crawling (simplification du maillage, éventuellement en utilisant du gourmand)

Edit: C'est juste pour ma propre expérience d'apprentissage, ce n'est PAS pour des raisons de performance que je pose cette question.

Il s'agit d'un moteur de terrain de type Minecraft. Je stocke des blocs en blocs (blocs 16x256x16 en bloc). Lorsque je génère un morceau, j'utilise plusieurs techniques procédurales pour définir le terrain et placer des objets. Lors de la génération, je garde un tableau 1D pour le bloc complet (solide ou non) et un tableau 1D séparé de blocs solides.

Après la génération, je parcourt les blocs solides en vérifiant leurs voisins, donc je ne génère que des faces de bloc qui n'ont pas de voisins solides. Je stocke les faces à générer dans leur propre liste (soit 6 listes, une par face possible / normale). Lors du rendu d'un bloc, je rend toutes les listes dans le bloc actuel de la caméra et uniquement les listes faisant face à la caméra dans tous les autres blocs. Je le fais en stockant les 6 listes dans un seul tampon, puis je change simplement les plages que je dessine.

En utilisant un atlas 2D avec ce petit truc de shader suggéré par Andrew Russell, je veux fusionner complètement des visages similaires. Autrement dit, s'ils sont dans la même liste (même normal), sont adjacents les uns aux autres, ont le même niveau de lumière, etc. Je sais que je vais toujours me retrouver avec des rectangles, mais cela devrait facilement réduire mon nombre de vertices de 50% ou mieux si mes estimations sont correctes.

Mon hypothèse serait d'avoir chacune des 6 listes triées par l'axe sur lequel elles reposent, puis par les deux autres axes (la liste pour le haut d'un bloc serait triée par sa valeur Y, puis X, puis Z).

Avec cela seul, je pourrais assez facilement fusionner des bandes de visages, mais je cherche à fusionner plus que des bandes ensemble lorsque cela est possible. J'ai lu cet algorithme de maillage gourmand, mais j'ai beaucoup de mal à le comprendre.

Donc, ma question: pour effectuer la fusion des faces comme décrit (en ignorant si c'est une mauvaise idée pour un terrain / éclairage dynamique), existe-t-il peut-être un algorithme plus simple à mettre en œuvre? Je serais également très heureux d'accepter une réponse qui me guide à travers l'algorithme gourmand d'une manière beaucoup plus simple (un lien ou une explication).

Cela ne me dérange pas une légère diminution des performances si elle est plus facile à mettre en œuvre ou même si c'est juste un peu mieux que de simplement faire des bandes. Je crains que la plupart des algorithmes se concentrent sur les triangles plutôt que sur les quads et en utilisant un atlas 2D comme je suis, je ne sais pas si je pourrais implémenter quelque chose de triangle basé sur mes compétences actuelles.

PS: J'effectue déjà un tri sélectif par morceau et comme décrit, j'élimine également les faces entre les blocs solides. Je n'abat pas encore d'occlusion et je ne le ferai peut-être jamais.

* Edit: j'ai implémenté ma propre petite technique, qui a probablement un nom, mais je passe simplement par mes 6 listes qui sont triées par les axes sur lesquels elles reposent, suivies par type de bloc, puis par niveau d'éclairage. Je les parcourt, créant de nouveaux rectangles au fur et à mesure et les agrandissant simultanément (avec un fort biais vers un certain axe). Ce n'est certainement pas optimal, mais il est en effet assez rapide et il réduit mon nombre de vertex de près de 50% en moyenne. Le commentaire de Byte56 est le placard, je pense à une vraie réponse, mais je ne peux pas sélectionner cela pour la réponse / prime.

Voici ma façon rapide et simpliste de gérer ce problème APRÈS avoir généré le terrain initial complet sans beaucoup d'optimisation. En supposant que tous les carrés donnés sont la même image, niveau d'éclairage, normal, etc. chaque couleur est un quadrillage différent que je rendrais. Avec mes listes triées comme elles sont, c'est une approche très facile / rapide.

Vous ne voulez faire que des bandes ou, au mieux, des rectangles. Il n'y a pas d'autres formes qui peuvent vous être résolues ou utiles.

Je voudrais également souligner qu'en gardant 6 listes par morceau, à tout moment vous allez utiliser 5 listes des morceaux dans les directions cardinales, et au moins 3 dans tous les autres. Vous perdez du temps ici, alors que non seulement la carte vidéo peut faire cette optimisation pour vous, mais même si vous l'avez fait vous-même, vous feriez mieux de garder tous les visages au même endroit et de comparer la normale à la direction de la caméra (produit de recherche DOT de vecteurs).

Les liens de CaptainRedMuff sur le maillage gourmand que vous avez déjà vu sont LA réponse à votre problème. Il devrait également ressortir de cela que vous vous retrouverez avec des mailles "Stripy", mais elles sont parfaitement efficaces, et venir avec quelque chose de plus optimal sera plus compliqué, et vous avez exprimé que le maillage gourmand est déjà trop compliqué.

Si vous rencontrez des problèmes de performances avec un seul morceau, cela me fait penser que quelque chose d'autre ne va vraiment pas.

Ma première supposition serait que vous appelez trop souvent une opération de tirage. Vous pouvez uniquement indiquer à la carte graphique de dessiner entre 50 et 400 ~ fois par seconde, selon le matériel. Combien d'appels à .setData ou .draw ____ Primitives effectuez-vous?

L'article auquel vous liez ne donne pas réellement d'algorithme pour générer le maillage; il indique un moyen d'évaluer les solutions possibles.

Généralement, cependant, l'article donne un bon résumé: 1) la solution naïve est mauvaise, 2) il y a une solution optimale, mais cela prendra du temps à écrire et à exécuter, 3) une élimination rapide donne de bien meilleurs résultats ( et c'est tout ce que Minecraft fait lui-même), et enfin 4) il pourrait y avoir une solution plus intelligente (l'algorithme gourmand).

La "solution" que vous indiquez dans l'image de votre question est l'algorithme gourmand. Il semble que votre question soit "ai-je correctement implémenté sa solution?" à laquelle je dois répondre "il n'a pas donné de solution; vous venez de le résoudre vous-même."

Votre solution peut-elle être meilleure? Meh. Sûr. Probablement pas la peine. Je pense que l'abattage d'occlusion ou LOD serait une meilleure étape suivante. Minecraft gaspille un bon nombre de cycles en dessinant la surface même lorsque vous êtes sous terre, ainsi qu'en dessinant de vastes réseaux de systèmes de grottes et de mines lorsque vous êtes en surface. Une fois que vous avez une bonne répartition du maillage, oui, se débarrasser des surfaces obscurcies peut être une bonne chose - mais (par exemple), il est généralement plus rapide de laisser votre carte vidéo effectuer une élimination de face arrière que de le faire sur le CPU.