DivideConcept.net

le blog de divide.

Archive pour janvier 2005

Dans cette dernière partie consacrée au displacement mapping, nous allons aborder les pistes de recherches actuelles.

Comme expliqué dans la partie 2, les pistes les plus prometteuses sont rendus possibles grâce au développement des vertex et pixel shaders : sans reellement créer de géometrie supplémentaire, mais en "creusant" des polygones simples grâce à des algorithmes, il est possible de recréer du displacement mapping (en évitant ainsi une surcharge mémoire et processeur).

Où il est question de précision et d’efficacité

Le principale problème du parallax mapping (outre l’effet "silhouette" qui sera abordé un peu plus bas) est son manque évident de précision. Pour obtenir un résultat plus réaliste il faut un algorithme qui soit capable de prendre en charge n’importe quelle displacement map sous n’importe quel angle, avec un minimum d’imprécision.

Ceci implique le développement d’algorithmes plus complexes, et donc forcément plus coûteux en terme de consommation mémoire et processeur que l’algorithme du parallax mapping.
Le grand problème est alors de trouver la méthode qui consommera le moins en calculant le mieux !

Sans rentrer dans le détail de toute les pistes de recherches actuelles, je donnerai comme exemple la méthode de Fabio Policarpo qui a l’avantage d’être simple à comprendre :

Il subdivise en 15 étapes le trajet entre l’entrée "dans" le polygone et le "fond" du polygone (relief minimum possible - concept déja abordé dans l’article 2).
Puis une fois qu’une intersection a été detectée, il resubdivise l’espace avant et après l’intersection en 5 étape, pour avoir une meilleur précision.
Il lui faut donc une vingtaine d’échantillonnages pour fournir un résultat acceptable.

Avantages : pas de précalcul nécessaire au niveau de la map de displacement, de meilleurs résultats que l’algorithme du parallax.

Inconvénients : nécessite beaucoup d’échantillonnage.
De plus, si il existe un pic de relief entre 2 échantillons, il ne sera pas détecté.

Cela peut donner lieu à des artefacts assez génant :

William Donnelly a réduit cet échantillonnage à 10 étapes grâce à un précalcul, et sa méthode est plus précise (elle ne rate aucun obstacle).
Inconvénient : La consommation mémoire pour chaque map de displacement est 16 fois supérieure !
Ceci est du à l’utilisation de textures 3d pour stocker des valeurs complémentaires, à la manière dont la technique du normal map détourne les composantes RVB pour coder des vecteurs (voir article 1).

Entre consommation processeur et consommation mémoire, il y a donc un délicat compromis à trouver.
Il est peu probable que l’année 2005 voit la standardisation d’un algorithme dans ce domaine, chaqu’un y allant de ses expérimentations.

Mais cela suffit-il à faire un displacement mapping correct ?
Et bien, non ! Il existe également un autre problème, couramment désigné comme effet "silhouette" (ou effet "de bord").

L’effet silhouette

Prenons l’exemple le plus simple possible, un triangle.
Le bon sens voudrait qu’on obtienne ceci :

Mais il n’en est rien ! En réalité, les algorithmes que nous venons de voir nous produiront cela :

Que s’est-il passé ?

L’algorithme, incapable de détecter les bords du volume de displacement réservé au triangle, a continué en considérant que l’espace intérieur est infini !

Il faut donc développer une méthode efficace de détection des bords.
Sans rentrer dans le détail des algorithmes, 3 techniques sont experimentés actuellements:
-extrapolation de la courbure équivalente générée par les triangles voisins (mais les résultats sont limités)
-décomposition du volume de displacement en tétraèdres et détection algébrique du bord de ces tétraèdres (mais grosse consommation processeur)
-détection des bords sans décomposition (méthodes en cours d’expérimentation)

Note personelle

J’arrive pour l’instant à des résultats assez satisfaisant avec mes propres algorithmes, puisque j’obtient des résultats similaires à ceux de William Donnelly sans augmenter la consommation mémoire !
Ma méthode de détection des bords (du 3em type) commence à se montrer également efficace.

Pour conclure, voici une liste de thread opengl.org en rapport avec le sujet :

Le thread à l’origine de la généralisation du Parallax mapping
L’algorithme de Fabio Policarpo (FPO)
Les résultats de la méthode d’extrapolation par courbure sur l’algorithme de FPO

Le displacement mapping est à la géométrie ce que la texture est à la couleur
Autrement dit, une bonne technique de displacement mapping permettra d’atteindre le niveau de géométrie ultime !

Cet article clôt la série sur le displacement mapping.
La prochaine fois, nous aborderons un autre aspect du développement 3d.

Dans l’article précédent les techniques les plus couramment utilisés pour simuler une complexité géométrique ont été abordés.
Nous allons maintenant voir le cas particulier du displacement mapping, qui reste à l’heure actuel un domaine encore hautement expérimental.

Tout d’abord, un exemple concret de ce qu’est censé générer géométriquement une map de displacement :

La première des approches pour arriver à ce résultat consiste tout simplement à subdiviser les polygones sur lesquels on souhaite appliquer la map de displacement en autant micro-polygones (termes employés fréquements dans les logiciels de 3d) que la map contient de texels (nombre de pixels sur une texture) et à déplacer ces micro-polygones pour épouser le relief virtuel définit par la map de displacement.
Cette approche a le mérite de la simplicité, mais elle a l’inconvénient majeur d’exploser la consommation mémoire et processeur.

Elle reste cependant la plus utilisée dans les logiciels de 3d tels que 3dsmax, maya, etc..
Ceux qui ont l’habitude d’utiliser ces logiciels et qui ont déjà expérimenté l’utilisation du displacement mapping savent de quoi je parle !

Bien que tentée dans une ancienne carte matrox (la g400), cette approche n’est pas viable pour le temps réel et à vrai dire, peu élégante.

Comment éviter cette surconsommation ?
En trouvant d’autres approches qui ne nécessitent pas de subdivisions de la géométrie.
Les cartes graphiques modernes mettent justement à notre disposition un outil formidable, les vertex et pixel shaders.

Mais késako ?

Si ces termes sont fréquemment employés, peu savent en revanche à quoi ils correspondent réellement.

Voici le schéma (simplifié et arbitraire) du pipeline graphique tel qu’il était dans les anciennes cartes graphiques (avant la geforce 3 -exception faite de la gf4mx- et avant la radeon 9500) :

Les vertex et pixel shaders se sont intercallés sur la carte graphique dans le processus entre la réception des polygones et le rendu final.

Oui mais c’est quoi ?

Les vertex et pixel shaders offrent la possibilité au développeur d’inserer des programmes plus ou moins complexes sur la carte graphique qui modifient le traitement des polygones qu’elle reçoit et de leur rendu !

Les vertex shaders recoivent en entrée comme leur nom l’indique un sommet (3 sommets définissant une face) et eventuellement quelques attributs propres à ce sommet, leur font subir un traitement définit par le développeur, et redonnent en sortie un sommet (avec le même nombre d’attribut).
Ils servent généralement a établir les calculs préliminaires pour les pixels shaders.

Les pixel shaders recoivent le résultat de la rasterization (interpolation pixel par pixel effectuée par le gpu entre les 3 sommets composant une face), c’est à dire un pixel en entrée, avec des attributs qui dépendent des attributs donnés en sortie par le vertex shader (coordonnées de textures, couleur, vecteurs divers..).
Ils fournissent en sortie, selon le programme définit par le développeur et tenant compte de tout les attributs donnés en entrée, une couleur (RVBA) en sortie et éventuellement une profondeur (si celle-ci est différente de celle calculée automatiquement par interpolation).

Devant la puissance de calcul parallèle et la rapidité de plus en plus croissante des processeurs graphiques, l’avantage ne se discute plus !

Après cette parenthèse, retour au displacement mapping.

La première des approches exploitant la puissance du GPU pour simuler du displacement mapping est le maintenant bien connu Parallax mapping aka Offset bump mapping aka Virtual displacement mapping.
Cette technique est utilisée dans l’Unreal Engine 3 et le futur Morrowind (Elder Scroll IV).
Mais attention ! Il ne s’agit que d’une simulation qui n’a rien de correct mathématiquement.

Voici comment elle fonctionne :

On considère un polygone dans lequel on va "creuser" le relief définit par la map de displacement.
Cette approche est commune à toute les nouvelles technique expérimentale per-pixel visant à reproduire du displacement mapping.

La particularité de chaque algorithme est la méthode de recherche de la première intersection entre chaque rayon émanent de la caméra et le relief définit virtuellement.
L’algorithme utilisé par le parallax mapping est assez simpliste : il fait l’assomption qu’en allant jusqu’au bout du parcours du rayon (donc en touchant le fond du volume global définit par la map de displacement) il obtiendra une valeur de hauteur qu’il peut generaliser pour l’ensemble de la zone dans laquelle il se trouve.
Le schéma suivant illustre plus clairement ceci :

Avantage : un calcul rapide à effectuer, un résultat qui donne l’illusion de relief.

Inconvénient : beaucoup trop approximatif ! Si la map de displacement définit des variations de relief trop marqués, ou si la caméra fait un angle trop aigu avec le polygone, le calcul devient complétement faux et l’illusion disparait (en générant un magma informe).

De plus, cet algorithme ne prend pas en compte les effets de bord (nous y reviendront en détail dans le prochain article).
Cette méthode a cependant le mérite de pouvoir fonctionner sur des cartes ne permettant pas l’exécution de pixels shaders complexes, en offrant un rapport illusion/consommation intéressant.

Dans le prochain article nous aborderons le futur du displacement mapping : les pistes de recherche et les résultats obtenus.

Il se trouve que je développe un moteur 3d depuis un peu plus d’an maintenant dont la particularité est de mettre en oeuvre une technique jusque là non exploitée (ou sous exploitée) dans le temps reel, le displacement mapping.

Tout d’abord, le concept. Pour l’exemple, j’utiliserai un Imp de Doom 3

dont voici la texture diffuse (couleur brute) :

Vous êtes tous habitués maintenant à voir du bump mapping, voire du normal mapping dans les jeux video.
Vous savez aussi sans doute comment ces techniques fonctionnent :
Dans le cas du bump-mapping, il s’agit d’une texture supplémentaire en niveau de gris qui vient perturber le calcul de la lumière sur la surface, pour donner l’illusion d’un relief plus complexe.

Le normal mapping (utilisé notamment dans Doom 3 et Far Cry) est une version ameliorée du bump mapping, qui repose non plus sur une seule composante (niveau de gris) mais sur 3 (niveaux de rouge, vert, bleu). Ces 3 informations ne doivent bien sur pas être interpretés comme des informations de couleurs dans ce cas particulier, mais comme les composantes d’un vecteur à 3 dimensions. Ainsi, le rouge codera la composante X du vecteur, le bleu codera pour le Y, et le rouge pour le Z. Pour chaque pixel de cette texture normale, on a donc un vecteur 3D associé.
Mais a quoi correspond ce vecteur 3D ?
Et bien il est orienté selon la normale de la surface à cet endroit la. En gros, il indique dans quelle direction était orienté la surface du modèle high poly (tres détaillé) à cet endroit la par rapport à la version low poly (peu détaillée, utilisé dans le jeu video).
Ca permet d’effectuer un calcul de lumière beaucoup plus juste sur la surface (le calcul de la lumière en lui même est très simple, il s’agit d’un simple produit scalaire du vecteur indiquant la direction de la lumière et du vecteur indiquant l’orientation de la surface).

Le displacement mapping repose sur un principe similaire aux 2 techniques précédentes, sauf qu’il effectue plus qu’une altération de la lumière : il fait également subir une altération à la géometrie.
Techniquement, son codage repose sur un niveau de gris (les points clairs représentant les niveaux les plus élevés).
Mathématiquement, on peut dire que le displacement mapping est l’intégrale du normal mapping (le normal mapping code des pentes, le displacement mapping code des surfaces) - et vice-versa, le normal mapping est la dérivée du displacement mapping.

Il est donc théoriquement possible de calculer une displacement map à partir d’une normal map.


(displacement map reconstituée à l’aide du logiciel Displacement Creator (www.ryanclark.net) )

Cette technique, qui permet d’aboutir à un niveau de détail optimum n’est actuellement utilisée dans aucun jeu vidéo, devant le temps de calcul effroyablement long qu’elle engendre.
Cependant il est possible de mettre en oeuvre des techniques le simulant de manière approximative (parallax mapping, aka virtual displacement mapping, utilisé dans l’Unreal Engine 3 et le futur Elder Scroll IV) voire de le reproduire fidèlement !

Ces techniques, leurs avantages et leurs inconvénients seront abordés en détail dans le prochain article.