Avant de tracer tous les éléments constitutifs de notre terrain vous devrez déterminer ce qui est visible et ce qui ne l'est pas. C'est à la fois un problème de performance et de correction. Si un élément de terrain qui est partiellement visible ou totalement caché est tracé, alors il y a un problème de correction. Si vous demandez à tracer un élément de terrain qui est situé derrière votre caméra ou dehors de votre champ de vision alors vous avez dépensé de précieux cycles de votre processeur pour rien.

C'est le deuxième article dans notre série d'articles sur le terrain en voxel et il fait suite à Moteur de terrain par voxel - Construire le terrain.

Le deuxième jour vint la visibilité

L'image ci dessus représente ce que vous pouvez voir depuis un point de vue donné (en rouge), la plupart des zones noires seront en dehors de votre écran et quelques parties qui peuvent être sur votre écran à l'intérieur de votre champ de vision (frustum) sont en fait caché par des parties du terrain qui se trouvent en face d'elles. Ce n'est pas réaliste en temps de calcul de prendre chaque petit élément de notre carte et déterminer s'ils sont clippés en dehors du frustum. À la place on va utiliser une représentation hiérarchique de notre terrain à deux niveau. Un niveau détaillé (detailed level) et un niveau grossier (coarse level). Je considèrerai les pixels du niveau détaillé que lorsque j'aurai déterminé au niveau grossier qu'ils sont totalement visibles ou partiellement visibles (ambigu).

On pourrait avoir plus de niveaux mais le bénéfice de l'ajout d'un niveau, n'est plus aussi intéressant quand on a déjà une structure hiérarchique en place. Bien entendu, le niveau grossier doit être suffisamment petit pour ne pas avoir à faire tout le travail de clipping au niveau le plus bas (limiter le cas ambigu) et doit être suffisamment grand pour que tout clipping d'une zone grossière apporte un gain en performance suffisant. J'ai opté pour des grandes zones de 256x256 éléments de terrain dont je peux déterminer rapidement la visibilité.

En rouge pur, vous avez les zones qui sont à 100% à l'intérieur du frustum (le frustum est le cone de visibilité, ou encore la zone délimitée par nos deux lignes en vert où se trouve la partie potentiellement visible de notre monde pour une position et rotation donnée). En rose ce sont les zones qui ne sont pas entièrement à l'intérieur du frustum mais que l'on doit inclure parce que certains de leurs éléments seront visibles. Dans le cas le pire cela veut dire que seul un élément de terrain peut être visible sur les 65536 que constitue notre zone. C'est mal mais on est obligé de vivre avec à moins d'aller pour une grille de départ moins grossière.

Le clipping est une opération assez simple, vous avez à tester chaque angle d'un quadrangle qui délimite une zone contre les trois droites que j'ai appelé "left, right et near" (gauche droite proche). J'ai mis la droite "near" à une courte distance de notre position de caméra, parce que je devrai diviser plus tard par z (la distance le long de l'axe de vue) et je veux éviter les divisions par zéro. Remarquez que plus on pousse notre droite "near" loin, meilleures seront les performances mais le risque est d'augmenter les artefacts de clipping.

Avant de clipper il faut déterminer les équations de chacune de ces droites. Trouver l'équation est équivalent à chercher les normales à chacune des droites dans le plan 2D. Les normales sont définies en terme de fov et rho, les deux angles caractéristiques de notre configuration.

Si je pose x1, y1, x2, y2 les quatre coordonnées de notre boite d'encadrement (bounding box) aligné sur les axes. Alors nous utiliserons le code suivant pour clipper selon le plan proche :

    dist1 = m_nearplane.a * x1 + m_nearplane.b * y1 + m_nearplane.c;
    dist2 = m_nearplane.a * x2 + m_nearplane.b * y1 + m_nearplane.c;
    dist3 = m_nearplane.a * x2 + m_nearplane.b * y2 + m_nearplane.c;
    dist4 = m_nearplane.a * x1 + m_nearplane.b * y2 + m_nearplane.c;

    if (dist1 <= 0 && dist2 <= 0 && dist3 <= 0 && dist4 <= 0)
    {
        // clipped by near plane

    }

On répète l'opération pour chaque ligne (plan). Nous avons travaillé uniquement en 2D jusqu'ici. Nous n'aborderons la troisième dimension que quand on commencera à projeter des choses sur notre écran (temporairement avant de revenir à la 2D de notre écran).

Peintre inversé

Aparté.. L'algorithme du peintre et une méthode très simple à comprendre pour tracer des éléments 3D qui se dissimulent les uns les autres. Cela consiste à trier tous les éléments du monde de l'arrière vers l'avant. Chaque nouvel élément tracé ne se soucie pas de ce qui a été tracé auparavant et les nouveaux pixels touchés par notre objet remplaceront les pixels précédents. La garantie que cela soit correct tient dans le tri initial parce que tout nouvel objet est garanti être situé devant tous les objets tracés précédemment. Un inconvénient majeur de cet algorithme c'est qu'il est très couteux parce que nous devons tracer tout le monde meme les objets qui pourraient être cachés par d'autres. Ce phénomène est appelé overdraw (je ne sais pas s'il y a un équivalent français). Il y a de rares occasions où l'overdraw est bon c'est quand on trace des objets transparents, dans ce cas il ne s'agit pas à proprement parler d'overdraw puisque les objets ne sont pas dissimulés. Un autre inconvénient qui le rend peu pratique dans le monde réel c'est que même si l'overdraw était gratuit il n'est pas toujours possible de trier de l'arrière vers l'avant. Le problème n'est pas soluble de manière simple dans le cas général (il peut être nécessaire de subdiviser des polygones en cours de triage pour une précision au pixel). Fin de l'aparté.

Nous ne voulons pas d'overdraw, en fait on peut avoir zéro overdraw sans rien sacrifier d'autre. Ce que j'appelle peintre inversé est un jeu de mot sur l'algo du peintre ci dessus parce que nous faisons tout à l'envers. Tout d'abord nous trions tous nos éléments de l'avant vers l'arrière. Ensuite quand on touche un pixel on s'assure tout d'abord que rien n'a été tracé sur ce pixel précédemment. Comme c'est trié de l'avant vers l'arrière tout objet précédemment sur ce pixel dissimule l'objet courant, donc on n'a pas à écrire notre couleur dans notre buffer.

Trier c'est facile dans notre cas, on a des gros blocs de données rectangulaires qui ne s'intersectent pas. Au début de chaque nouveau rendu, je considère toutes les zones autour de la caméra, je les place dans une structure triée de l'avant vers l'arrière (une std::map ferait l'affaire). Ensuite je parcours la structure dans l'ordre et je les trace élément par élément encore une fois en utilisant un ordre particulier pour que l'affichage soit correct au final.

Ce que je veux dire par ordre correct, c'est que l'on a un rectangle de 256x256 éléments que je ne peux pas tracer dans n'importe quel ordre. Celui utilisé par le stockage a une chance sur quatre d'être bon (cela dépend de la vue !), mais au final ce n'est pas bien dur, nous avons quatre cas possibles :

La flèche indique dans quelle direction l'observateur regarde la zone concernée. Vous pouvez vous demander si le fait de faire un déplacement de chaque élément ne va pas bouleverser cet ordre prédéfini. Ce serait le cas si le déplacement pouvait être arbitraire (avec des problèmes de continuité) mais ici le déplacement ne se fait que dans une direction constante et dans un axe qui ne change pas la relation d'ordre par rapport à la caméra et c'est tout ce qui importe.

Si vous êtes familier avec l'accélération 3D, vous connaissez probablement l'algorithme du Z-Buffer. Cet algorithme assure que si vous tracez votre géométrie dans un ordre arbitraire indépendemment de votre vue le z-buffer se chargera de déterminer les pixels visibles et les pixels cachés. Cela pourrait marcher pour notre terrain bien entendu mais on n'a pas besoin de ça. Le ZBuffer a un surcout. Le cout est la consultation du buffer, son écriture et le fait que si vous ne triez pas comme on le fait alors le cas le pire est aussi mauvais en terme d'overdraw que l'algorithme du peintre que l'on a abordé plus haut (si par accident vous triez toute de l'arrière vers l'avant). De plus vous êtes limité par la résolution de votre Zbuffer et deux éléments très proches ne peuvent pas être correctement tracés. Sans compter que l'on doit allouer un zbuffer de taille égale à la taille du tampon de couleur multiplié par le supersampling (suréchantillonnage pour l'antialiasing). On peut accélerer les calculs d'occlusion avec une structure de Z hiérarchique mais encore une fois cela n'est vraiment pas nécessaire avec tout ce que l'on a fait jusqu'à présent et pour la suite. Meme dans la situation où j'ai besoin de l'information du ZBUffer pour un rendu ultérieur où j'utilise une méthode plus classique pour afficher des objets sur mon terrain (méthode dite de frankenrender), alors je peux générer l'information de Z de manière optimale une fois par pixel, exactement de la même façon dont je génére l'information de couleur. Mais si l'on reste dans les voxels, on n'a pas besoin de cette information de Z pour traiter l'occlusion.

Y-Buffer

Comment déterminer de manière optimale si un pixel a déjà été tracé ? De manière générale, on peut s'en sortir en stockant un seul bit par pixel qui indique si le pixel est "on" ou "off". En groupant ces bits par groupes de données sur 32 bits ou 64 bits (tiles de 32 ou 64 pixels) on peut rapidement éliminer des parties entières du rendu. Mais on peut faire mieux que ça encore parce que l'on se contente de tracer une série de lames verticales alignées sur l'écran. J'ai appelé cet algorithme YBuffer en référence au ZBuffer plus général décrit plus haut. On n'a qu'à maintenir une simple ligne de données entières qui indiqueront pour chaque colonne verticale de pixel, combien de ces pixels ont été tracés par notre moteur.

Comment cela fonctionne ? Chaque lame de terrain, occupe la zone située sous son sommet vertical. La seule condition selon laquelle ça ne descend pas jusqu'èn bas de l'écran, c'est si cette lame de terrain est dissimulée tout ou partie par un tracé précédent sur la même colonne (meme X). Cela signifie que quand on trace une lame à la position X,Y, alors on la compare au Y stocké précédemment pour cette colonne X. Si la précédente lame était à un Y supérieur au Y courant, alors on passe le tracé (occlusion) ou sinon on trace une couleur simple depuis le Y courant jusqu'au niveau du Y précédent. De cette manière on trace chaque pixel seulement une fois et la visibilité de chaque pixel est correcte grâce à toutes les dispositions prises précédemment.

Niveau de détail

Parce que l'on utilise une perspective conique, les zones qui sont le plus loin de notre point de vue vont couvrir une zone assez petite sur l'écran. Il n'y a pas besoin de passer à travers une carte de 65536 éléments quand seul un ou deux pixels seront au final tracé.

Nous utiliserons donc un système assez basique de niveau de détail (LOD). Ce système s'appelle mip mapping (multum in parvo, beaucoup dans peu). À la place de considérer les 256x256, nous allons estimer grossièrement combien d'espace cette zone peut couvrir horizontalement sur l'ecran, et on va choisir la plus petite représentation qui permet de mettre encore une fois grossièrement un élément par pixel horizontal (on peut aussi choisir de couvrir plusieurs pixels ce qui accélère pas mal les calculs mais pour une qualité moindre). Donc si le terrain couvre 16 pixel sur l'écran horizontalement, on décide d'utiliser une version réduite de 16x16. Chaque représentation de NxN est une version préfiltrée de la représentation plus large de 2Nx2N.

Cela signifie que pour chaque zone de terrain de 256x256, nous avons 8 autres représentations possibles de plus petite taille (128x128, 64x64, 32x32 etc.). On filtre à la fois l'info de couleur (albedo) et l'élévation.

Mapping de texture

Habituellement, texturer un objet en 3D est un peu complexe, parce que l'on a de la correction de perspective à appliquer aux UV dans l'espace de l'écran, du filtrage à faire etc. Maintenant on est plutot chanceux parce qu'à cause de notre algorithme on peut travailler dans l'espace de la texture directement sans devoir faire d'interpolation des données de texture autrement que de manière linéaire. On traverse notre zone de 256x256 avec un pas fixe et on ne prend aucun raccourci pour projeter l'élément sur l'écran. À chaque élément de terrain, on lit une nouvelle élévation de notre carte d'élévation, et une simple couleur diffuse de notre carte de diffusion et la position sur l'écran sera calculée de manière précise par notre processus de projection.

Résumé

Voilà ce qui sort de notre moteur jusqu'ici. Nous avons ajouté en prime un peu de perspective aérienne (teinte bleue qui croit avec la distance), je traiterai ça dans la deuxième partie. Nous avons toujours une faible qualité parce que j'utilise une selection de niveau de détail qui fait couvrir en moyenne deux pixels horizontalement à chaque élément de terrain.

Maintenant, que faut-il faire pour améliorer la qualité ? En premier on peut faire que chaque élément couvre un pixel ou moins horizontalement (malheureusement on ne peut pas faire de détermination très fine pour le détail vertical, parce qu'il est plus complexe de déterminer en avance de combien il sera étendu sur l'écran). Ensuite on peut utiliser du suréchantillonnage (supersampling) et tracer un ciel un peu moins plat. Je rentrerai dans ce genre de détail dans la deuxième partie. À suivre.

Voir la partie III : Moteur de terrain par voxel - Amélioration du rendu.