Comment puis-je implémenter un éclairage à base de voxels avec occlusion dans un jeu de style Minecraft?

13

J'utilise C # et XNA. Mon algorithme actuel d'éclairage est une méthode récursive. Cependant, cela coûte cher , au point où un bloc de 8x128x8 est calculé toutes les 5 secondes.

  • Existe-t-il d'autres méthodes d'éclairage qui créeront des ombres à obscurité variable?
  • Ou la méthode récursive est-elle bonne, et peut-être que je me trompe?

Il semble que les choses récursives soient fondamentalement chères (forcées de parcourir environ 25 000 blocs par bloc). Je pensais utiliser une méthode similaire au lancer de rayons, mais je ne sais pas comment cela fonctionnerait. Une autre chose que j'ai essayée était de stocker des sources de lumière dans une liste, et pour chaque bloc d'obtenir la distance à chaque source de lumière, et de l'utiliser pour l'éclairer au niveau correct, mais ensuite l'éclairage passerait à travers les murs.

Mon code de récursivité actuel est ci-dessous. Ceci est appelé de n'importe quel endroit du morceau qui n'a pas un niveau de lumière nul, après avoir effacé et rajouté la lumière du soleil et la torche.

world.get___atest une fonction qui peut obtenir des blocs en dehors de ce bloc (c'est à l'intérieur de la classe de bloc). Locationest ma propre structure qui ressemble à un Vector3, mais utilise des entiers au lieu de valeurs à virgule flottante. light[,,]est le lightmap pour le morceau.

    private void recursiveLight(int x, int y, int z, byte lightLevel)
    {
        Location loc = new Location(x + chunkx * 8, y, z + chunky * 8);
        if (world.getBlockAt(loc).BlockData.isSolid)
            return;
        lightLevel--;
        if (world.getLightAt(loc) >= lightLevel || lightLevel <= 0)
            return;
        if (y < 0 || y > 127 || x < -8 || x > 16 || z < -8 || z > 16)
            return;
        if (x >= 0 && x < 8 && z >= 0 && z < 8)
            light[x, y, z] = lightLevel;

        recursiveLight(x + 1, y, z, lightLevel);
        recursiveLight(x - 1, y, z, lightLevel);
        recursiveLight(x, y + 1, z, lightLevel);
        recursiveLight(x, y - 1, z, lightLevel);
        recursiveLight(x, y, z + 1, lightLevel);
        recursiveLight(x, y, z - 1, lightLevel);
    }

la source
1
Quelque chose ne tourne pas rond si vous faites 2 millions de blocs par bloc - d'autant plus qu'il n'y a en fait que 8 192 blocs dans un bloc 8 * 128 * 8. Que pourriez-vous faire si vous parcourez chaque bloc ~ 244 fois? (cela pourrait-il être 255?)
doppelgreener
1
J'ai mal fait mes calculs. Désolé: P. En changeant. Mais la raison pour laquelle vous devez y aller si nombreux est que vous devez "sortir" de chaque bloc jusqu'à ce que vous atteigniez un niveau de lumière supérieur à celui de votre réglage. Cela signifie que chaque bloc peut être écrasé 5 à 10 fois avant d'atteindre le niveau de lumière réel. 8x8x128x5 = beaucoup
2
Comment stockez-vous vos Voxels? C'est important pour réduire les temps de traversée.
Samaursa
1
Pouvez-vous publier votre algorithme d'éclairage? (vous demandez si vous le faites mal, nous n'avons aucune idée)
doppelgreener
Je les stocke dans un tableau de "blocs", et un bloc se compose d'une énumération pour le matériel, plus un octet de métadonnées pour une utilisation future.

Réponses:

6
  1. Chaque lumière a une position précise (virgule flottante) et une sphère limite définie par une valeur de rayon de lumière scalaire, LR .
  2. Chaque voxel a une position précise (virgule flottante) en son centre, que vous pouvez facilement calculer à partir de sa position dans la grille.
  3. Parcourez chacun des 8192 voxels une seule fois, et pour chacun, voyez s'il tombe dans chacun des volumes englobants sphériques de N lumières en vérifiant |VP - LP| < LR, où VP est le vecteur de position du voxel par rapport à l'origine et LPle vecteur de position de la lumière par rapport à l'origine. Pour chaque lumière , dont le rayon du voxel courant est jugée, incrémenter son facteur de lumière par la distance entre le centre de lumière, |VP - LP|. Si vous normalisez ce vecteur puis obtenez son amplitude, ce sera dans la plage 0,0-> 1,0. Le niveau de lumière maximal qu'un voxel peut atteindre est de 1,0.

Le runtime est O(s^3 * n), où sest la longueur latérale (128) de votre région de voxel etn nombre de sources de lumière. Si vos sources lumineuses sont statiques, ce n'est pas un problème. Si vos sources de lumière se déplacent en temps réel, vous pouvez travailler uniquement sur les deltas plutôt que de recalculer l'ensemble du shebang à chaque mise à jour.

Vous pouvez même stocker les voxels que chaque lumière affecte, comme références dans cette lumière. De cette façon, lorsque la lumière se déplace ou est détruite, vous pouvez parcourir uniquement cette liste, en ajustant les valeurs de lumière en conséquence, plutôt que d'avoir à parcourir à nouveau l'intégralité de la grille cubique.

Ingénieur
la source
Si j'ai bien compris son algorithme, il essaie de faire une sorte de pseudo-radiosité, en permettant à la lumière d'atteindre des endroits éloignés même si cela signifie qu'elle doit "contourner" certains coins. Ou, en d'autres termes, un algorithme de remplissage des espaces "vides" (non solides) avec une distance maximale limitée de l'origine (la source de lumière) et la distance (et à partir de là, l'atténuation de la lumière) étant calculée selon le chemin le plus court vers l'origine. Donc - pas tout à fait ce que vous proposez actuellement.
Martin Sojka
Merci pour le détail @MartinSojka. Oui, ça ressemble plus à un remblai intelligent. Avec toute tentative d'éclairage global, les coûts ont tendance à être élevés même avec des optimisations intelligentes. Il est donc bon de tenter ces problèmes en 2D en premier, et s'ils sont même à distance chers, sachez que vous aurez un défi certain à relever en 3D.
Ingénieur
4

Minecraft lui-même ne fait pas la lumière du soleil de cette façon.

Vous remplissez simplement la lumière du soleil de haut en bas, chaque couche recueille la lumière des voxels voisins dans la couche précédente avec atténuation. Très rapide - passage unique, pas de listes, pas de structures de données, pas de récursivité.

Vous devez ajouter des torches et d'autres lumières non inondables dans un passage ultérieur.

Il y a tellement d'autres façons de le faire, y compris la propagation de lumière directionnelle fantaisie, etc., mais elles sont évidemment plus lentes et vous devez déterminer si vous souhaitez investir dans le réalisme supplémentaire compte tenu de ces sanctions.

Bjorn Wesen
la source
Attendez, alors comment Minecraft le fait-il exactement? Je n'ai pas pu obtenir exactement ce que vous disiez ... Que signifie "chaque couche recueille la lumière des voxels voisins dans la couche précédente avec atténuation"?
2
Commencez par le calque le plus haut (tranche de hauteur constante). Remplissez-le de soleil. Ensuite, allez au calque ci-dessous, et chaque voxel là-bas obtient son éclairage des voxels les plus proches dans le calque précédent (au-dessus). Mettez zéro lumière dans les voxels solides. Vous avez deux façons de décider du "noyau", du poids des contributions des voxels ci-dessus, Minecraft utilise la valeur maximale trouvée, mais la diminue de 1 si la propagation n'est pas directe. Il s'agit de l'atténuation latérale, de sorte que les colonnes verticales non bloquées de voxels obtiendront la pleine propagation de la lumière du soleil et les virages lumineux autour des coins.
Bjorn Wesen
1
Veuillez noter que cette méthode n'est en aucun cas basée sur une quelconque physique réelle :) Le principal problème est que vous essayez essentiellement d'approximer une lumière non directionnelle (la diffusion atmosphérique) ET de rebondir la radiosité avec une simple heuristique. Ça a l'air plutôt bien.
Bjorn Wesen
3
Qu'en est-il d'une «lèvre» qui plane, comment la lumière monte-t-elle? Comment la lumière se déplace-t-elle vers le haut? Lorsque vous descendez uniquement de haut en bas, vous ne pouvez pas remonter pour remplir les surplombs. Également des torches / autres sources lumineuses. Comment ferais-tu ceci? (ils ne pouvaient que baisser!)
1
@Felheart: ça fait un moment maintenant que j'ai regardé ça, mais en substance il y a un niveau de lumière ambiante minimum qui est généralement suffisant pour le dessous des surplombs afin qu'ils ne soient pas complètement noirs. Quand j'ai implémenté cela moi-même, j'ai ajouté un deuxième passage de bas en haut, mais je n'ai pas vraiment vu de grandes améliorations esthétiques par rapport à la méthode ambiante. Les torches / projecteurs doivent être traités séparément - je pense que vous pouvez voir le modèle de propagation utilisé dans MC si vous mettez une torche au milieu d'un mur et expérimentez un peu. Dans mes tests, je les propage dans un champ lumineux séparé puis j'ajoute.
Bjorn Wesen
3

Quelqu'un a dit de répondre à votre propre question si vous l'aviez compris, alors oui. J'ai trouvé une méthode.

Ce que je fais est le suivant: Tout d'abord, créez un tableau booléen 3D de "blocs déjà modifiés" superposés sur le bloc. Ensuite, remplissez la lumière du soleil, la torche, etc. (allumant simplement le bloc sur lequel il est allumé, pas encore d'inondation). Si vous avez changé quelque chose, cliquez sur "blocs modifiés" à cet endroit sur true. Allez aussi bien et changez chaque bloc solide (et donc pas besoin de calculer l'éclairage) pour "déjà changé".

Maintenant, pour les choses lourdes: passez par le morceau entier avec 16 passes (pour chaque niveau de lumière), et si son «déjà changé» continue. Ensuite, obtenez le niveau de lumière pour les blocs autour de lui. Obtenez le plus haut niveau de lumière d'entre eux. Si ce niveau de lumière est égal au niveau de lumière des passes actuelles, définissez le bloc sur lequel vous vous trouvez au niveau actuel et définissez "déjà modifié" pour cet emplacement sur vrai. Continuer.

Je sais que c'est un peu compliqué, j'ai essayé d'expliquer de mon mieux. Mais le fait important est que cela fonctionne et est rapide.


la source
2

Je suggère un algorithme qui combine en quelque sorte votre solution multi-passes avec la méthode récursive d'origine, et est très probablement un peu plus rapide que l'un ou l'autre.

Vous aurez besoin de 16 listes (ou tout type de collections) de blocs, une pour chaque niveau d'éclairage. (En fait, il existe des moyens d'optimiser cet algorithme pour utiliser moins de listes, mais cette méthode est plus simple à décrire.)

Tout d'abord, effacez les listes et définissez le niveau d'éclairage de tous les blocs sur zéro, puis initialisez les sources lumineuses comme vous le faites dans votre solution actuelle. Après (ou pendant) cela, ajoutez tous les blocs avec un niveau de lumière non nul à la liste correspondante.

Maintenant, parcourez la liste des blocs avec le niveau de lumière 16. Si l'un des blocs à côté d'eux a un niveau de lumière inférieur à 15, réglez leur niveau de lumière sur 15 et ajoutez-les à la liste appropriée. (S'ils étaient déjà sur une autre liste, vous pouvez les supprimer, mais cela ne fait aucun mal même si vous ne le faites pas.)

Répétez ensuite la même chose pour toutes les autres listes, par ordre décroissant de luminosité. Si vous trouvez qu'un bloc de la liste a déjà un niveau de lumière plus élevé qu'il ne devrait l'être sur cette liste, vous pouvez supposer qu'il a déjà été traité et ne vous embêtez même pas à vérifier ses voisins. (Là encore, il pourrait être plus rapide de simplement vérifier les voisins - cela dépend de la fréquence à laquelle cela se produit. Vous devriez probablement essayer les deux façons et voir quelle est la plus rapide.)

Vous pouvez noter que je n'ai pas précisé comment les listes devraient être stockées; vraiment n'importe quelle implémentation raisonnable devrait le faire, tant que l'insertion d'un bloc donné et l'extraction d'un bloc arbitraire sont des opérations rapides. Une liste chaînée devrait fonctionner, mais il en irait de même pour une implémentation à mi-chemin décente de tableaux de longueur variable. Utilisez simplement ce qui vous convient le mieux.


Addenda: si la plupart de vos lumières ne bougent pas très souvent (et les murs non plus), il peut être encore plus rapide de stocker, pour chaque bloc éclairé, un pointeur sur la source de lumière qui détermine son niveau d'éclairage (ou sur l'un des eux, si plusieurs sont liés). De cette façon, vous pouvez éviter les mises à jour globales de l'éclairage presque entièrement: si une nouvelle source de lumière est ajoutée (ou une source existante éclaircie), vous n'avez qu'à effectuer une seule passe d'éclairage récursive pour les blocs qui l'entourent, tandis que si une est supprimée (ou grisé), il vous suffit de mettre à jour les blocs qui le désignent.

Vous pouvez même gérer les changements de mur de cette façon: lorsqu'un mur est supprimé, il suffit de commencer un nouveau passage d'éclairage récursif sur ce bloc; une fois ajouté, effectuez un recalcul de l'éclairage pour tous les blocs qui pointent vers la même source de lumière que le bloc récemment muré.

(Si plusieurs changements d'éclairage se produisent en même temps - par exemple si une lumière est déplacée, ce qui compte comme une suppression et un ajout - vous devez combiner les mises à jour en une seule, en utilisant l'algorithme ci-dessus. Fondamentalement, vous mettez à zéro le niveau de lumière de tous des blocs pointant vers des sources de lumière supprimées, ajoutez les blocs allumés qui les entourent ainsi que toutes les nouvelles sources de lumière (ou les sources de lumière existantes dans les zones de mise à zéro) aux listes appropriées et exécutez les mises à jour comme ci-dessus.)

Ilmari Karonen
la source