Comment puis-je optimiser un monde Minecraft-esque voxel?

J'ai trouvé les merveilleux grands mondes de Minecraft extrêmement lents à naviguer, même avec une carte graphique quad core et charnue.

Je suppose que la lenteur de Minecraft provient de:

• Java, comme le partitionnement spatial et la gestion de la mémoire sont plus rapides en C ++ natif.
• Partition du monde faible.

Je peux me tromper sur les deux hypothèses. Cependant, cela m'a amené à réfléchir à la meilleure façon de gérer de grands mondes voxels. Comme c'est un vrai monde 3D, où un bloc peut exister n'importe où dans le monde, il s'agit fondamentalement d'un grand tableau 3D [x][y][z], où chaque bloc du monde a un type (c'est BlockType.Empty = 0-à- dire BlockType.Dirt = 1, etc.)

Je suppose que pour que ce genre de monde fonctionne bien, vous devez:

• Utilisez un arbre d’une certaine variété ( oct / kd / bsp ) pour séparer tous les cubes; il semble que la meilleure option serait d'oct / kd, car vous pouvez simplement partitionner au niveau par cube et non par triangle.
• Utilisez un algorithme pour déterminer quels blocs peuvent être vus actuellement, car des blocs plus proches de l'utilisateur pourraient masquer les blocs derrière, rendant inutile le rendu de ces derniers.
• Conservez l’objet bloc en tant que tel, de manière à pouvoir l’ajouter et le supprimer rapidement des arbres.

Je suppose qu'il n'y a pas de bonne réponse à cela, mais je serais intéressé de voir les opinions des gens sur le sujet. Comment amélioreriez-vous les performances dans un grand monde basé sur voxel?

En ce qui concerne Java vs C ++, j'ai écrit un moteur voxel dans les deux versions (version C ++ ci-dessus). J'écris aussi des moteurs de voxels depuis 2004 (quand ils n'étaient pas à la mode). :) Je peux dire sans hésiter que les performances du C ++ sont de loin supérieures (mais il est également plus difficile de coder). Il s’agit moins de la vitesse de calcul que de la gestion de la mémoire. Sans aucun doute, lorsque vous allouez / libérez autant de données que dans un monde de voxels, C (++) est le langage à battre. pourtant, vous devriez penser à votre objectif. Si les performances sont votre priorité absolue, optez pour C ++. Si vous voulez juste écrire un jeu sans performances démesurées, Java est définitivement acceptable (comme en témoigne Minecraft). Il existe de nombreux cas triviaux / marginaux, mais en général, vous pouvez vous attendre à ce que Java s'exécute environ 1,75 à 2,0 fois plus lentement que le C ++ (bien écrit). Vous pouvez voir une ancienne version de mon moteur mal optimisée en action ici (EDIT: une version plus récente ici ). Bien que la génération de morceaux puisse sembler lente, gardez à l'esprit qu'elle génère des diagrammes 3D de voronoï de manière volumétrique, en calculant les normales à la surface, l'éclairage, les objets en sortie et les ombres sur le processeur à l'aide de méthodes à force brute. J'ai essayé diverses techniques et je peux obtenir une génération de blocs environ 100x plus rapide en utilisant diverses techniques de mise en cache et d'instanciation.

Pour répondre au reste de votre question, vous pouvez améliorer le rendement de nombreuses manières.

1. Caching Chaque fois que vous le pouvez, vous devez calculer les données une fois. Par exemple, je fais cuire la lumière dans la scène. Il pourrait utiliser un éclairage dynamique (dans l’écran, en post-traitement), mais cuire au four dans cet éclairage signifie que je n’ai pas à passer aux normales pour les triangles, c’est-à-dire ....

2. Passez le moins de données possible sur la carte vidéo. Une chose que les gens ont tendance à oublier est que plus vous transmettez de données au GPU, plus cela prend du temps. Je passe dans une seule couleur et une position de sommet. Si je veux faire des cycles jour / nuit, je peux simplement faire un étalonnage des couleurs, ou je peux recalculer la scène à mesure que le soleil change.

3. La transmission de données au GPU étant très coûteuse, il est possible d'écrire un moteur dans un logiciel plus rapide à certains égards. L'avantage du logiciel est qu'il peut effectuer toutes sortes de manipulations de données / d'accès à la mémoire, ce qui n'est tout simplement pas possible sur un GPU.

4. Jouez avec la taille du lot. Si vous utilisez un GPU, les performances peuvent varier considérablement en fonction de la taille de chaque tableau de vertex que vous transmettez. En conséquence, jouez avec la taille des morceaux (si vous utilisez des morceaux). J'ai trouvé que les morceaux 64x64x64 fonctionnent plutôt bien. Quoi qu'il en soit, gardez vos morceaux cubiques (pas de prismes rectangulaires). Cela facilitera le codage et diverses opérations (comme les transformations) et, dans certains cas, le rendra plus performant. Si vous ne stockez qu'une valeur pour la longueur de chaque dimension, gardez à l'esprit que deux registres de moins sont intervertis lors du calcul.

5. Considérez les listes d’affichage (pour OpenGL). Même s'ils sont "à l'ancienne", ils peuvent être plus rapides. Vous devez transformer une liste d’affichage en variable ... si vous appelez des opérations de création de liste d’affichage en temps réel, le processus sera lent. Comment une liste d'affichage est-elle plus rapide? Il ne met à jour que les attributs état, vs attributs par sommet. Cela signifie que je peux passer jusqu'à six faces, puis une couleur (par rapport à une couleur pour chaque sommet du voxel). Si vous utilisez GL_QUADS et des voxels cubiques, vous pouvez économiser jusqu'à 20 octets (160 bits) par voxel! (15 octets sans alpha, bien que vous souhaitiez généralement que les éléments soient alignés sur 4 octets.)

6. J'utilise une méthode brute-force de rendu des "morceaux", ou des pages de données, qui est une technique courante. Contrairement aux octrees, il est beaucoup plus facile / rapide de lire / traiter les données, bien que beaucoup moins convivial en mémoire (cependant, de nos jours, vous pouvez obtenir 64 gigaoctets de mémoire pour 200 $ à 300 $) ... pas que l'utilisateur moyen l'ait. De toute évidence, vous ne pouvez pas allouer un grand tableau pour le monde entier (un ensemble de voxels 1024x1024x1024 correspond à 4 Go de mémoire, en supposant qu'un int de 32 bits est utilisé par voxel). Donc, vous allouez / désaffectez de nombreux petits tableaux, en fonction de leur proximité avec le spectateur. Vous pouvez également affecter les données, obtenir la liste d’affichage nécessaire, puis vider les données pour économiser de la mémoire. Je pense que l'idéal serait d'utiliser une approche hybride d'octrees et de tableaux - stocker les données dans un tableau lors de la génération procédurale du monde, de l'éclairage, etc.

7. Rendre près de loin ... un pixel coupé est un gain de temps. Le GPU lancera un pixel s'il ne réussit pas le test du tampon de profondeur.

8. Rendu uniquement les morceaux / pages dans la fenêtre d'affichage (explicite). Même si le gpu sait comment clipser les polgyons en dehors de la fenêtre d'affichage, le transfert de ces données prend encore du temps. Je ne sais pas quelle serait la structure la plus efficace pour cela ("honteusement", je n'ai jamais écrit d'arborescence BSP), mais même un simple raycast par morceau pourrait améliorer les performances, et des tests contre le tronc de visualisation seraient évidemment gagner du temps.

9. Informations évidentes, mais pour les débutants: supprimez tous les polygones qui ne sont pas à la surface - c'est-à-dire si un voxel est composé de six faces, supprimez les faces qui ne sont jamais restituées (touchent un autre voxel).

10. En règle générale, tout ce que vous faites dans la programmation: CACHE LOCALITY! Si vous parvenez à conserver des éléments locaux en mémoire cache (même pendant un court laps de temps, cela fera une différence énorme. Cela signifie que vos données doivent rester congruentes (dans la même région de mémoire) et que les zones de mémoire ne doivent pas trop souvent être modifiées. dans l’idéal, travaillez sur un bloc par thread et conservez cette mémoire exclusive dans le thread (cela ne s’applique pas uniquement au cache du processeur): pensez à la hiérarchie du cache comme ceci (la plus lente à la plus rapide): réseau (nuage / base de données / etc.) -> disque dur (obtenez un disque SSD si vous n'en avez pas déjà un), une mémoire RAM (obtenez un canal triple ou une RAM supérieure si vous ne l'avez pas déjà), un ou plusieurs caches de processeur, enregistrez-vous. Essayez de conserver vos données sur dernier point, et ne l’échangez pas plus que nécessaire.

11. Filetage Fais le. Les mondes Voxel sont bien adaptés au filetage, car chaque partie peut être calculée (la plupart du temps) indépendamment des autres. routines pour le filetage.

12. N'utilisez pas les types de données char / byte. Ou des shorts. Votre consommateur moyen aura un processeur AMD ou Intel moderne (comme vous probablement). Ces processeurs ne disposent pas de registres 8 bits. Ils calculent les octets en les plaçant dans un emplacement de 32 bits, puis les reconvertissent (peut-être) en mémoire. Votre compilateur peut faire toutes sortes de vaudous, mais utiliser un nombre de 32 ou 64 bits vous donnera les résultats les plus prévisibles (et les plus rapides). De même, une valeur "bool" ne prend pas 1 bit; le compilateur utilisera souvent 32 bits complets pour un booléen. Il peut être tentant de faire certains types de compression sur vos données. Par exemple, vous pouvez stocker 8 voxels sous forme d'un nombre unique (2 ^ 8 = 256 combinaisons) s'ils étaient tous du même type / couleur. Cependant, vous devez penser aux conséquences de ceci - cela pourrait économiser beaucoup de mémoire, mais cela peut également nuire aux performances, même avec un petit temps de décompression, car même une petite quantité de temps supplémentaire est proportionnelle à la taille de votre monde. Imaginez-vous en train de calculer un raycast; pour chaque étape du raycast, vous devrez exécuter l'algorithme de décompression (à moins que vous ne trouviez un moyen intelligent de généraliser le calcul de 8 voxels par pas de rayon).

13. Comme Jose Chavez le mentionne, le modèle de conception flyweight peut être utile. Tout comme vous utiliseriez une image bitmap pour représenter une tuile dans un jeu 2D, vous pouvez créer votre monde à partir de plusieurs types de tuiles 3D (ou blocs). L'inconvénient est la répétition de textures, mais vous pouvez améliorer cela en utilisant des textures de variance qui s'emboîtent. En règle générale, vous souhaitez utiliser l’instanciation chaque fois que vous le pouvez.

14. Évitez de traiter les vertex et les pixels dans le shader lors de la sortie de la géométrie. Dans un moteur Voxel, vous aurez inévitablement beaucoup de triangles, de sorte que même un simple pixel shader peut considérablement réduire votre temps de rendu. Il est préférable de rendre le rendu dans un tampon, puis vous pixel shader en post-traitement. Si vous ne pouvez pas faire cela, essayez de faire des calculs dans votre vertex shader. Les autres calculs doivent être intégrés aux données de sommet si possible. Des passes supplémentaires deviennent très coûteuses si vous devez restituer toute la géométrie (telle que le mappage des ombres ou le mappage de l'environnement). Parfois, il vaut mieux abandonner une scène dynamique au profit de détails plus riches. Si votre jeu contient des scènes modifiables (terrain destructible, par exemple), vous pouvez toujours recalculer la scène au fur et à mesure de la destruction des objets. La recompilation n'est pas chère et devrait prendre moins d'une seconde.

15. Détendez vos boucles et gardez les tableaux à plat! Ne fais pas ça:

    for (i = 0; i < chunkLength; i++) {
     for (j = 0; j < chunkLength; j++) {
      for (k = 0; k < chunkLength; k++) {
       MyData[i][j][k] = newVal;
      }
     }
    }
    //Instead, do this:
    for (i = 0; i < chunkLengthCubed; i++) {
     //figure out x, y, z index of chunk using modulus and div operators on i
     //myData should have chunkLengthCubed number of indices, obviously
     myData[i] = newVal;
    }
    

    EDIT: Grâce à des tests plus approfondis, j'ai trouvé que cela pouvait être faux. Utilisez le cas qui convient le mieux à votre scénario. En règle générale, les tableaux doivent être plats, mais l'utilisation de boucles multi-index peut souvent être plus rapide, selon le cas.

EDIT 2: lorsqu’on utilise des boucles multi-index, il est préférable de boucler dans l’ordre z, y, x plutôt que l’inverse. Votre compilateur pourrait optimiser cela, mais je serais surpris de le faire. Cela maximise l'efficacité de l'accès mémoire et de la localité.

for (k < 0; k < volumePitch; k++) {
    for (j = 0; j < volumePitch; j++) {
        for (i = 0; i < volumePitch; i++) {
            myIndex = k*volumePitch*volumePitch + j*volumePitch + i;
        }
    }
}

16. Parfois, vous devez faire des suppositions, des généralisations et des sacrifices. Le mieux que vous puissiez faire est de supposer que la plus grande partie de votre monde est complètement statique et ne change que tous les quelques milliers d'images. Pour les parties animées du monde, celles-ci peuvent être effectuées dans un laissez-passer séparé. Supposons également que la majeure partie de votre monde est complètement opaque. Les objets transparents peuvent être rendus dans une passe séparée. Supposons que les textures ne varient que toutes les x unités ou que les objets ne peuvent être placés que par incréments de x. Supposons une taille de monde fixe… aussi tentant qu'un monde infini soit, cela peut conduire à des exigences système imprévisibles. Par exemple, pour simplifier la génération de motifs de voronoï dans les roches ci-dessus, j'ai supposé que chaque point central de voronoï était situé dans une grille uniforme, avec un léger décalage (autrement dit, un hachage géométrique implicite). Supposons un monde qui n’emballe pas (a des bords). Cela peut simplifier de nombreuses complexités introduites par un système de coordonnées d'emballage, à un coût minimal pour l'expérience utilisateur.

Vous pouvez en savoir plus sur mes implémentations sur mon site

Il y a beaucoup de choses que Minecraft pourrait faire plus efficacement. Par exemple, Minecraft charge des piliers verticaux entiers d'environ 16x16 dalles et les rend. J'estime qu'il est très inefficace d'envoyer et de rendre ce nombre de tuiles inutilement. Mais je ne pense pas que le choix de la langue soit important.

Java peut être assez rapide, mais pour ce qui est de cette donnée, C ++ présente un avantage considérable, avec beaucoup moins de temps système pour accéder aux tableaux et travailler dans les octets. D'un autre côté, il est beaucoup plus facile d'effectuer le threading sur toutes les plateformes Java. Sauf si vous envisagez d'utiliser OpenMP ou OpenCL, vous ne trouverez pas cette commodité en C ++.

Mon système idéal serait une hiérarchie légèrement plus complexe.

La mosaïque est une unité unique, probablement autour de 4 octets, destinée à conserver des informations telles que le type de matériau et l'éclairage.

Le segment serait un bloc de tuiles 32x32x32.

1. Des drapeaux seraient placés pour chacun des six côtés, si tout ce côté était constitué de blocs pleins. Cela permettrait au moteur de rendu d’obstruer des segments derrière ce segment. Actuellement, Minecraft ne semble pas effectuer de test d’occlusion. Mais il a été mentionné la possibilité de disposer d’une fonction d’abattage d’occlusion matérielle, ce qui peut être coûteux, mais mieux que de générer des quantités énormes de polygones sur des cartes de bas de gamme.
2. Les segments ne seraient chargés en mémoire que pendant l'activité (joueurs, PNJ, physique de l'eau, croissance des arbres, etc.). Sinon, ils seraient envoyés directement aux clients toujours compressés à partir du disque.

Les secteurs seraient un bloc de segments 16x16x8.

1. Les secteurs suivraient le segment le plus élevé pour chaque colonne verticale afin que les segments supérieurs à celui-ci puissent être rapidement déterminés vides.
2. Il suivrait également le segment occlus en bas, de sorte que chaque segment devant être rendu à partir de la surface puisse être rapidement saisi.
3. Les secteurs suivraient également la prochaine mise à jour de chaque segment (physique de l'eau, croissance des arbres, etc.). De cette façon, un chargement dans chaque secteur suffirait à maintenir le monde en vie et un chargement uniquement par segments suffisamment long pour mener à bien leurs tâches.
4. Toutes les positions des entités seraient suivies par rapport au secteur. Cela éviterait les erreurs de virgule flottante présentes dans Minecraft lors de déplacements très éloignés du centre de la carte.

Monde serait une carte infinie de secteurs.

1. Le monde serait responsable de la gestion des secteurs et de leurs prochaines mises à jour.
2. Le monde enverrait de manière préemptive des segments aux joueurs le long de leurs chemins potentiels. Minecraft envoie de manière réactive les segments demandés par le client, ce qui entraîne un délai.

Minecraft est assez rapide, même sur mon 2-core. Java ne semble pas être un facteur limitant, bien qu’il y ait un peu de décalage du serveur. Les jeux locaux semblent faire mieux, alors je vais supposer quelques inefficacités, là-bas.

En ce qui concerne votre question, Notch (auteur de Minecraft) a longuement blogué sur la technologie. En particulier, le monde est stocké dans des "morceaux" (vous en voyez parfois, surtout quand il en manque un, car le monde n'est pas encore rempli.), La première optimisation consiste à décider si un morceau peut être vu ou non. .

Au sein d'un bloc, comme vous l'avez deviné, l'application doit décider si un bloc peut être vu ou non, en fonction du fait qu'il est masqué ou non par d'autres blocs.

Notez également qu'il existe des FACES de bloc, qui peuvent être supposés non visibles, en raison du fait qu'ils sont obscurcis (un autre bloc recouvre le visage) ou de la direction dans laquelle la caméra est dirigée (si la caméra fait face au nord, vous pouvez ne voyez pas la face nord de TOUS les blocs!)

Les techniques courantes consisteraient également à ne pas conserver des objets blocs distincts, mais plutôt un "bloc" de types de blocs, avec un seul bloc prototype pour chaque bloc, ainsi qu'un ensemble minimal de données décrivant comment ce bloc peut être personnalisé. Par exemple, il n’existe pas de blocs de granit personnalisés (à ma connaissance), mais l’eau dispose de données permettant de déterminer sa profondeur le long de chaque face latérale, à partir desquelles on peut calculer la direction de son écoulement.

Votre question n'est pas claire si vous souhaitez optimiser la vitesse de rendu, la taille des données ou quoi. Une clarification serait utile.

Voici quelques mots d’informations générales et de conseils que je peux vous donner comme modérateur trop expérimenté de Minecraft (qui peut vous donner au moins une partie des conseils.)

La raison pour laquelle Minecraft est lent a BEAUCOUP à faire avec certaines décisions de conception de niveau inférieur douteuses - par exemple, chaque fois qu'un bloc est référencé par positionnement, le jeu valide les coordonnées avec environ 7 instructions si pour s'assurer qu'il n'est pas hors limites. . De plus, il n’ya aucun moyen de saisir un «bloc» (une unité de blocs de 16x16x256 avec laquelle le jeu fonctionne) puis de référencer directement des blocs dans celui-ci, afin de contourner les recherches dans le cache et, entre autres, les problèmes de validation stupides (iow, chaque référence de bloc implique également une recherche de morceau, entre autres choses.) Dans mon mod, j’ai créé un moyen de saisir et de changer directement le tableau de blocs, ce qui a permis à la génération de donjons de passer d’une latence inimaginable à une vitesse incroyablement rapide.

EDIT: Suppression de l'affirmation selon laquelle la déclaration de variables dans un périmètre différent entraînait des gains de performances, cela ne semble en réalité pas être le cas. Je crois qu'au moment où j'ai fusionné ce résultat avec quelque chose que j'essayais d'expérimenter (en particulier, la suppression des transtypages entre doublons et flottants dans le code relatif aux explosions en consolidant les doublons ... naturellement, cela a eu un impact énorme!)

De plus, bien que ce ne soit pas le domaine dans lequel je passe beaucoup de temps, l'essentiel de l'étouffement des performances dans Minecraft est un problème de rendu (environ 75% du temps de jeu y est consacré sur mon système). Évidemment, vous ne vous souciez pas beaucoup si le souci est de supporter plus de joueurs en multijoueur (le serveur ne rend rien), mais cela compte dans la mesure où les machines de chacun peuvent même jouer.

Ainsi, quel que soit le langage que vous choisissez, essayez de vous familiariser avec les détails de mise en œuvre / de bas niveau, car même un petit détail dans un projet tel que celui-ci pourrait faire toute la différence (un exemple pour moi en C ++ était "La fonction inline statique du compilateur "Oui, c'est possible! Cela a fait une différence incroyable dans l'un des projets sur lesquels je travaillais, car j'avais moins de code et l'avantage d'inline.)

Je n'aime vraiment pas cette réponse parce que cela rend la conception de haut niveau difficile, mais c'est la vérité douloureuse si la performance est une préoccupation. J'espère que vous avez trouvé cela utile!

De plus, la réponse de Gavin couvre certains détails que je ne voulais pas répéter (et bien plus encore! Il est clairement plus au courant que moi sur le sujet) et je suis d'accord avec lui pour l'essentiel. Je vais devoir expérimenter avec son commentaire concernant les processeurs et les tailles variables plus courtes, je n'en ai jamais entendu parler - je voudrais me prouver que c'est vrai!

Le problème est de penser à la manière dont vous chargeriez les données en premier lieu. Si vous transmettez vos données cartographiques en mémoire lorsque cela est nécessaire, il y a toujours une limite naturelle à ce que vous pouvez restituer. Il s'agit déjà d'une mise à niveau des performances de rendu.

Ce que vous faites avec ces données est alors à vous. Pour les performances GFX, vous pouvez ensuite utiliser Découpage pour découper des objets cachés, des objets trop petits pour être visibles, etc.

Si vous ne faites que rechercher des techniques de performance graphique, je suis sûr que vous pouvez trouver des tonnes de choses sur le net.

Quelque chose à regarder est le modèle de conception Flyweight . Je crois que la plupart des réponses ici font référence à ce modèle de conception d’une manière ou d’une autre.

Bien que je ne connaisse pas la méthode exacte utilisée par Minecraft pour minimiser la mémoire pour chaque type de bloc, il s'agit d'une solution possible dans votre jeu. L'idée est de n'avoir qu'un seul objet, tel qu'un objet prototype, contenant des informations sur tous les blocs. La seule différence serait l'emplacement de chaque bloc.

Mais même la localisation peut être minimisée: si vous savez qu'un bloc de terrain est d'un type, pourquoi ne pas stocker les dimensions de ce terrain sous la forme d'un bloc géant, avec un ensemble de données de localisation?

Évidemment, le seul moyen de savoir est de commencer à mettre en œuvre votre propre système et de faire quelques tests de mémoire pour en vérifier les performances. Tiens nous au courant de comment ça se passe!