Mise en oeuvre
Gérer des images avec l'API java
L'API java permet la gestion des images par différents biais : tout d'abord, faisant partie de la classe Applet, la fonction Image loadImage( String filename ) retournant un objet de type image. L'inconvénient est que la classe Image ne contient pas d'informations sur les dimensions de l'image. C'est ainsi que nous nous sommes tournés vers la classe IconImage. En effet, nous pouvons charger des images à l'aide du constructeur : IconImage( String filename ) puis accéder aux dimensions de l'image par int getIconWidth() et int getIconHeight(). Nous devons aussi pouvoir lire dans cette image directement. Nous avons donc décidé de construire un tableau de pixels (de type int[]) et de le remplir à l'aide de la classe PixelGrabber.
Une fois que ces notions ont été comprises, pour éviter la duplication des informations (IconImage et tableau de pixels), nous avons implémenté la classe ReadableImage héritant de IconImage permettant l'encapsulation du tableau de pixels.
Pour commencer, quelques mots à propos de la technique du double buffering. Cette technique est employée pour éviter que ce qui est visible à l'écran ne soit rafraîchit alors que l'on ai pas fini de calculer ce qui doit être affiché. Admettons que vous êtes dans un jeu où votre personnage se déplace. Si le jeu est mal fait, il sera possible que le personnage ne soit pas entièrement fini de dessiner mais que l'écran soit rafraîchi à ce moment là. Ceci aura pour conséquence l'affichage d'une partie du personnage à sa nouvelle position alors que l'autre partie n'aura pas bougé, c'est à dire que votre personnage apparaîtra coupé en deux ou scintillera ! Pour éviter cela, tous les calculs sont faits dans une zone non visible (un tableau de pixels) qui sera copié entièrement vers la zone visible de l'écran (cette opération est possible en un temps inférieur au balayage vertical de l'écran par le faisceau d'électrons). Il en résulte une image stable.
Pour construire l'image représentant notre paysage, nous sommes amenés à écrire pixel par pixel la couleur appropriée. De plus, l'emploi de la technique du double buffering s'avère indispensable étant donnée la complexité des calculs (sous peine d'observer des clignotements incessants). L'objet MemoryImageSource correspond parfaitement à nos besoins : il s'agit de construire un tableau de pixels, puis de l'associer à notre objet MemoryImageSource via le constructeur de ce dernier. Enfin, lors du rafraîchissement de l'applet, il suffit de copier entièrement l'image calculée vers l'affichage. Ceci est fait par la fonction getGraphics.drawImage de l'applet ainsi que la fonction createImage( MemoryImageSource ) de l'applet.
Les calculs de position suivent les formules trigonométriques suivantes :
--------------------------------- Retour à la liste des problèmes ---------------------------------
1. PrincipeLe raysurfing est en fait une technique de lancer de rayon (raytracing) spécialisée. En effet, pour calculer une image, le raytracing impliquera de lancer un rayon par pixel alors que le raysurfing nécessitera de lancer un rayon par colonne de pixels, moyennant des objets de formes adaptées (nous y reviendrons plus tard en voyant les limitations de cette technique).
2. Voxels et heightmap
Pour comprendre la base de cet algorithme, il nous faut introduire la notion de voxel : de même qu'un pixel est un carré élémentaire en 2D, un voxel est un parallélépipède en 3D. Les voxels sont très employés pour la représentation de paysages pour une principale raison : la simplicté : nous aurons à disposition une carte des hauteurs indiquant pour un voxel donné (aux coordonnées (X,Z) ) sa hauteur Y. L'information peut donc être stockée dans une simple image bitmap 256 couleurs !
3. Du raytracing au raysurfing
Passons maintenant à ce qui constitue la restriction du raytracing pour obtenir le raysurfing. Pour le raytracing, nous devons trouver tout d'abord l'équation du rayon passant par le pixel de l'écran dont nous voulons calculer la couleur puis ensuite se déplacer le long de ce rayon afin de trouver l'intersection avec le plan. Cependant, cette méthode est extrêmement lente : nous devons calculer ces informations pour chaque pixel de l'écran. L'idée du raysurfing est de calculer seulement une équation de rayon au départ puis d'en déduire celles pour les rayons partant des pixels de la même colonne si on trouve l'intersection avec le paysage. Ensuite, repartir du point d'intersection avec l'équation du nouveau rayon déduite de la précédente et continuer jusqu'à une certaine condition d'arrêt. Un des gros avantages de cette méthode est que les parties non visibles du paysage ne sont pas calculées, épargnant ainsi le calcul des zones visibles.
Pour cela, nous avons besoin de plusieurs restrictions : tout d'abord, les paysages ne pourront pas contenir de zones surplombantes. Ensuite, la caméra devra toujours avoir son axe tangent parallèle au paysage (les rotations sont autorisées seulement selon les axes Y et X).4. Un algorithme
Nous pouvons donc maintenant obtenir l'agorithme, pour une colonne de pixels :
Trouver les incréments servant à se déplacer sur le rayon (dx, dy, dz)
Tant que l'on a pas atteind la distance de vision maximaleRécupérer l'altitude du point situé à la verticale du point courant du rayonFin tant que
Tant que le point courant se situe en dessous du niveau du paysageAppliquer la bonne couleur au point sur l'écranFin tant que
Remonter d'un pixel sur l'écran
Augmenter l'ordonnée du point courant du rayon de 1
Recalculer dy
Mettre à jour le point courant du rayonIl suffit alors de répéter ceci sur chaque colonne de pixels.
Pour ensuite appliquer une texture à l'ensemble, nous effectuons un texturage plannaire, et nous prenons donc les coordonnées X et Z du point courant sur le rayon comme coordonnées de texel.
Deux méthodes de tracé du ciel ont été testées : par raytracing naïf puis par raysurfing, afin d'optimiser la vitesse de rendu.
1. Raytracing naïfTout d'abord, considérons l'équation d'un plan horizontal infini (normal à la direction y) : elle sera de la forme y = constante. Partant de ce principe, il n'est pas difficile de revenir aux coordonnées d'intersection du plan étant donné l'angle de départ du rayon :
soient alpha et bêta les angles de départ du rayon selon respectivement la direction tangente à la camera et l'axe y. On aura donc :
Étant donné que nous allons effectuer un mapping planaire, nous utilisons directement ces coordonnées comme coordonnées dans la texture, après les avoir ramené à la taille de celle-ci par modulo. De plus, dans l'implémentation finale, pour simuler le fait que les nuages ne peuvent être atteints, nous ne prenons pas en compte l'altitude de la caméra, ce qui donne comme formule :
Cependant, la présence de nombreuses fonctions trigonométriques pénalise la vitesse de cette méthode. Nous allons donc revenir au raycasting, étant donné que le plan respecte les restrictions inhérentes à la spécialisation des rayons.
2. Raysurfing
L'algorithme du raysurfing reprend exactement celui cité plus haut. Seulement, au lieu d'avoir à lire une hauteur dans la heightmap, nous raisonnons par rapport à une constante. De plus, en cas de collision, nous faisons varier l'altitude de la position sur le rayon de -1 au lieu de 1 (pour se retrouver en dessous du ciel, et non au dessus).
3. Résultat
Le brouillard est un des effets donnant le meilleur rapport difficulté d'implémentation / amélioration du rendu final. En effet, le fait de voir des montagnes s'arrêter net, sans suite au paysage est très désagréable, surtout quand le paysage est animé. Pour remédier à cela, il suffit d'ajouter aux couleurs du pixel que l'on veut écrire, une certaine quantité de blanc, cette quantité dépendant naturellement de la distance à la caméra. Nous prendrons ainsi deux distances caractéristiques de la caméra : la distance de vision maximale qui donnera un coefficient de 1 et la distance de début du brouillard où le coefficient sera de 0. Pour vous convaincre de l'utilité de cet effet, voici deux captures d'écran.
Vue sans brouillard
Vue avec brouillard
1. La réflexion
La mer est un plan horizontal défini par une altitude. Dès lors, la modélisation de la surface de la mer est beaucoup plus simple que celle des montagnes. Les points à traiter en tant que surface de la mer sont les points dont l’altitude (coordonnée Y) est égale au niveau de la mer. Une fois repérés, ces points devront être l’origine d’un nouveau rayon.D’après les lois de réflexion de la lumière, le rayon incident et le rayon réfléchi doivent avoir un angle opposé par rapport à la normale au plan de projection. En d’autres termes et dans notre repère, nous devons lancer un nouveau rayon avec le même angle Ry et un angle Rxz opposé :
Jusque là, notre eau est une mer d’huile, un vrai miroir. Pour donner un aspect visuel plus réaliste, la mer doit être agitée par le vent : c’est la naissance des vagues. Visuellement, la représentation des vagues se traduit par une légère variation périodique de l’angle de réflexion, selon les deux axes du plan.
3. Mais quelle est la forme d’une vague ?
Une première forme de vagues périodiques selon les deux directions du plan est la forme sinusoidale simple. L’angle de réflexion suivrait alors l’équation de surface suivante :
La formule donne des vagues très régulières, et toutes alignées.
Une seconde formule donne des vagues un peu moins régulières, un peu plus réalistes :
On peut comparer le rendu des deux méthodes
Première formule
(sinusoïde simple)
Deuxième formule
1. Qu'est ce que l'effet Lens FlareL’effet de lentille affiche à l’écran une série de halo lumineux quand une source lumineuse intense est dans le champ de vision. Dans la réalité, cet effet est du aux différentes lentilles de l’objectif d’une caméra ou d’un appareil photo.
2. Comment afficher un halo lumineux ?Un halo est l’éclaircissement d’une zone (généralement un disque) de l’image. Le halo doit donc être appliqué sur l’image après que celle-ci ait été calculée (i.e. tous les rayons aient été lancés).
En fonction des paramètres suivants on détermine d’abord si le soleil est dans le champ de vision de la caméra, puis si c’est le cas les coordonnées de projection du soleil sur l’écran :
- la position du soleil dans le ciel (une direction, i.e. dans notre repère un couple d’angle (Ry,Rxz))
- l’orientation de la caméra (les angles Ry et Rxz de la caméra)
- la champ de vision de la caméra (un angle d’ouverture calculé à partir de la distance de projection FOV et des dimensions de l’écran de projection dimX et dimY)Puis on place 4 halos lumineux sur la droite passant par le soleil et le centre de l’écran. On applique des coefficients barycentriques constants pour la position de chaque halo (les coefficients sont déterminés de manières arbitraires, ils dépendent de la position de chaque lentille dans l’objectif, nous ne rentrerons pas à ce niveau de précision !).
Puis pour l’affichage, nous réutilisons la classe ReadableImage implémentée pour la lecture d’une heightmap. Pour l’affichage d’un halo, on calque une ReadableImage sur l’image calculée.
On dispose de « tâches » en niveaux de gris (fichiers .gif). Pour chaque halo, on « posera » une tâche (notre calque) sur notre paysage : chaque pixel de la tâche est associé à un pixel du paysage. Puis on teste pour chaque pixel de la tâche si le pixel en question dépasse un seuil (un niveau de gris déterminé eu préalable). Si le pixel est plus clair que le seuil fixé, on éclaircit le pixel du paysage correspondant, en fonction de la marge de dépassement du seuil : plus le pixel du calque tend vers le blanc, plus le paysage est éclairci.
3. Le résultatLe résultat final avec quatre halos :
--------------------------------- Retour à la liste des problèmes ---------------------------------
1. PrincipePour effectuer un raytracing ou un raysurfing, nous devons passer par chaque pixel de l'écran afin de trouver la couleur qui lui correspond. Souvent, nous ne nécessitons que le calcul des coordonnées du texel correspondant au pixel de l'écran puis affecter sa couleur à celle du point à afficher. Une première idée serait donc de lancer un rayon à intervalles réguliers (un sur 2, 4 ou 8 par exemple) puis d'effectuer une interpolation des couleurs pour déterminer celle des pixels intermédiaires. Cependant, il en résultera une impression d'image floue donnant envie d'essayer de nettoyer son écran. L'idée suivante consiste donc à stocker non pas la couleur mais les coordonnées du texel puis d'effectuer l'interpolation sur ces coordonnées.
Pourquoi le terme bilinéaire ? Et bien tout simplement car nous sommes en dimension 2 : nous aurons à effectuer une interpolation suivant deux axes et ce, linéairement.2. Les formules
soit un carré de coté nLa formule pour trouver les coordonnées du texel correspondant à P est :
L'algorithme naïf de l'interpolation bilinéaire serait d'appliquer cette formule à chaque pixel de l'écran. Néanmoins, aux vues du nombre de multiplications qu'elle contient, nous perdrions beaucoup de temps, ce qui est gênant pour une technique sensée accélérer le programme. Remarquons que nous avons cité le terme linéaire ; ceci signifie que les quantités varient de manière plus ou moins constante selon x et y. Nous pouvons donc calculer les dérivées partielles correspondant à la formule :
De plus, nous pouvons remarquer que ces quantités ne sont pas constantes : elles dépendent chacune soit de x, soit de y. Étant donné que nous raisonnons d'abord par ligne puis par colonne, nous allons calculer la variation de dv / dx quand nous changeons de ligne.
3. L'algorithme
Pour une ligne sur n de l'écran
Pour un point sur n de cette ligne PFin pourcalculer dv / dx en P.y = 0Fin pour
calculer dv / dy en P.x = 0
calculer d²v / dxdyvaleurAgauche = P1
Pour j allant de P.y à P.y + n
texelCourant = valeurAgaucheFin pourPour i allant de P.x à P.x + n
affecter au pixel de l'écran la couleur du texel courantFin pour
TexelCourant += dv / dxdv / dx += d²v / dxdy
valeurAgauche += dv / dy4. Résultats et conclusion
Je pense qu'une image parle plus que des mots. Voici une capture d'écran de l'application mettant en oeuvre cette optimisation avec n = 8, soit le lancer de un rayon sur 64 !
Encerclés en rouge, des exemples d'erreurs effectuées à cause de l'interpolation linéaire.
Comme nous pouvons le voir, les flancs des montagnes sont rendus correctement, cependant, des problèmes apparaissent lors des franchissements de colline. Ceci est du au fait que nous ne pouvons pas considérer un paysage comme un espace linéaire : la distance entre deux rayons peut varier de manière très importante ou très faible selon que l'on change de colline ou non. Cette technique d'interpolation ne peut donc pas être employée de manière satisfaisante pour le tracé de nos paysages.
Néanmoins, cette technique peut être utilisée dans le rendu du ciel (voir le dossier de maintenance, au chapitre améliorations)
--------------------------------- Retour à la liste des problèmes ---------------------------------
1. PrincipeUn constat sur le calcul de l'image nous a amené à remarquer que nous utilisions la même précision pour ce qui concerne l'avant plan et le lointain. Hors, pour les éléments de paysage situés dans la distance, le fait que l'image soit un peu moins précise n'est pas particulièrement gênant aux vues des gains en vitesse que cela pourrait nous apporter.
2. Deux approches différentes
Nous avons imaginé deux principales solutions pour adapter le niveau de détail : la première consiste à changer la vitesse à laquelle nous nous déplaçons sur le rayon en fonction de la distance. La seconde est d'utiliser des distances de vision différentes selon les rayons puis d'en déduire les informations manquantes. Nous avons choisi d'implémenter la seconde méthode car la première pourrait conduire à des erreurs conséquentes sur la représentation du paysage. En effet, en augmentant l'incrément, nous risquons de complètement sauter une montagne si celui ci est trop grand. Cependant, cette méthode peut être utilisée en combinaison avec la seconde en utilisant des tailles d'incrément raisonnables.
3. Explication de la seconde méthode
Le principe de cette méthode sera de faire varier régulièrement la distance maximale à laquelle pourront être lancés les rayons (voir le schéma explicatif ci-dessous).
Pour un rayon sur 4, nous lancerons à distance maximale. Pour le rayon suivant, à une distance minimale, pour le 3e, à une distance intermédiaire et enfin un 4e à une distance minimale. Il va en résulter que nous devrons retrouver les informations manquantes pour les rayons lancés à une distance minimale ou intermédiaire. Comme nous savons que de toute façon nous ne nous déplaçons sur l'écran que vers le haut, nous pouvons dire que des informations manquent si le voisin d'un rayon de distance minimale ou intermédiaire a été projeté jusqu'à une position plus haute sur l'écran. Dans un tel cas, nous devrons déduire les informations de celles contenues dans les colonnes correspondant aux rayons ayant été lancés à une distance plus grande. Dans le cas de notre adaptation à trois distances différentes, nous aurons au loin des blocs de pixels de largeur 4 puisque les informations pour les rayons 2, 3 et 4 seront déduites de celles du premier rayon.
4. Modifications de l'algorithme de lancé de rayon
Les adaptations à faire pour modifier l'algorithme précédent ne sont pas très conséquentes : il faut tout d'abord ne pas lancer les rayons successivement, mais par ordre de distance de vision maximale : tous les rayons de distance maximale, puis les rayons de distance intermédiaire et enfin ceux de distance minimale. Ensuite, il nous faudra une structure de donnée nous permettant de stocker les différentes hauteurs atteintes par les rayons 1 et 3 afin de détecter la perte d'information comme expliqué dans le 3. Concernant le lancer du rayon proprement dit, nous lançons le rayon
5. Résultat
Zone 1 : distance de vision maximale - paysage très pixelisé.
Zone 2 : distance intermédiaire - paysage moins grossier
Avant plan : paysage netNous pouvons noter que le paysage dans le fond nuit un peu à la qualité graphique de l'ensemble. Cependant, l'ajout de brouillard permet aisément de gommer ce défaut en atténuant cette zone de l'image.
1. BouclesDe manière générale, nous devons sortir un maximum de calculs des boucles, et à plus forte raison encore, des boucles imbriquées. Ainsi, le calcul de la position d'un pixel dans le buffer ( position = BufferWidth * Y + X) pourra être calculée en dehors de la boucle puis incrémentée :
Pour y allant de 0 à dimY
Pour x allant de 0 à dimX
Buffer[ dimX*y+x ] = ...
Fin pour
Fin pourdevient :
offset = 0
Pour y allant de 0 à dimY
Pour x allant de 0 à dimX
Buffer[ offset ] = ...
offset ++
Fin pour
Fin pour2. Fonction modulo
La fonction modulo actuellement présente dans la classe Java n'est pas performante. En effet, nous pouvons nous limiter à une utilisation avec des textures et heightmaps de tailles correspondantes à des puissances de 2 (256. 512. 1024, ...). Ainsi, un modulo équivaudra à l'application d'un ET binaire :
résultat = modulo( valeur, 256 ) sera équivalent à résultat = valeur & 255
3. Tables précalculées
Comme nous pouvons nous en rendre compte, nous allons avoir besoin d'accéder à des cos, sin et tan ; autant de calculs long à effectuer. Il peut donc sembler judicieux de précalculer des tables de valeur pour ces fonctions, selon la précision voulue. Ce sera le cas pour le calcul des vagues par exemple.
--------------------------------- Retour au sommaire de cette page ---------------------------------
