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

9

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.

Mythiques
la source
Après toutes vos optimisations, vous rencontrez toujours des problèmes de performances? Avez-vous essayé de profiler le code pour voir où sont les problèmes?
MichaelHouse
@ Byte56 Oh, ce n'est certainement pas du tout un problème de performances actuellement. Il pourrait en être un à l'avenir lorsque j'essaierai de mettre ce que j'apprends à utiliser pour un vrai jeu. Pour l'instant cependant, je veux simplement apprendre. Je n'ai rien dit de tout cela parce que je semble obtenir moins d'aide si je veux juste apprendre des choses simplement pour les apprendre.
Mythics
Je pense que je devrais également dire que si je parviens à essayer de jouer correctement avec cela, je voudrai que le monde visible soit ÉNORME. Je ne voudrais pas que le personnage ait 2 blocs de haut et 1 bloc de large comme Minecraft et bien d'autres, mais plutôt 3 blocs de large / long et 6-9 de haut. Terrain probablement statique cependant.
Mythics
1
Ah, OK Tim. Merci pour l'explication. J'ai fait des recherches à ce sujet lorsque je créais le moteur de mon jeu. Étant donné que mon paysage est dynamique, je ne pensais pas que cela valait le coût des performances chaque fois que quelque chose était changé. Cependant, cet article peut vous aider à résoudre le problème du rectangle maximal. C'est essentiellement l'algorithme dont vous parlez pour fusionner des visages similaires (peut-être pas gourmand, mais optimal). Bonne chance!
MichaelHouse
@ Byte56 Merci, je l'apprécie énormément. Cela ressemble certainement plus au type d'algorithme que je recherche, si ce n'est sur place. Je vais devoir bricoler un peu pour voir si je peux obtenir tous les rectangles maximum en une seule fois. Je pourrais peut-être en tirer un avantage pour un peu, car je pense que la question et une réponse détaillée pourraient en aider beaucoup d'autres à l'avenir.
Mythics

Réponses:

4

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?

Phil
la source
Les rectangles sont ce que je veux. Byte56 a lié un algorithme beaucoup plus simple à suivre que gourmand, mais je ne peux pas accepter un commentaire comme réponse. J'ai supposé qu'il avait commenté à la place parce qu'il ne se liait qu'à un algorithme plutôt que de l'expliquer. Je ne sais pas ce que tu veux dire concernant mes listes. J'ai généralement 1-2 appels de tirage par bloc. Mes listes sont stockées dans un tampon par bloc. Je change les plages à dessiner par image. Je peux me tromper, mais envoyer des données inutiles au GPU semble contre-productif. Un tirage supplémentaire ou deux par morceau semble préférable à l'envoi de plus de données au processeur graphique et à le forcer à être également éliminé.
Mythics
Je n'ai pas de problèmes de performances. J'aime simplement apprendre ces choses. Je vais modifier ma question pour le dire, mais comme je l'ai également dit à Byte56, je reçois moins d'aide si ce que j'essaie de faire ne résout pas réellement un problème. Pour répondre à votre question, je rend actuellement 200 à 260 morceaux au maximum par image. C'est un tirage 500I DrawIndexedPrimitives assez courant par image. J'obtiens régulièrement 100-130 FPS sans vsync, ce qui fait 65 000 appels par seconde. Je n'essaie pas d'être impoli, mais peu de choses que vous avez dites ont du sens pour moi. Je ne comprends peut-être pas, je vous prie donc de préciser si j'ai mal compris. Peut-être que cela a à voir avec XNA?
Mythics
Ah, désolé, je voulais dire par image, pas par seconde. Vous vous rapprochez d'une limite supérieure là-bas, et si vous n'êtes que sur le terrain, vous êtes presque épuisé.
Phil
J'ai attribué +1 à votre réponse car elle m'a fait penser à quelques améliorations que je pourrais apporter, mais rien à voir avec la question. Aussi, j'ai pensé que je devrais partager une réponse de Nathan Reed sur le lien
Mythics
Je vais devoir trouver l'article que j'ai lu qui a cité 400-500 comme limite. Un rapide google ne m'a pas aidé.
Phil
0

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.

AndrewS
la source