 |
Grâce à la synthèse d'images, l'utilisateur devient, via des périphériques comme l'écran et la souris, à la fois observateur et acteur de mondes de synthèse que l'on dit virtuels. Insatiable, nous voulons toujours plus d'objets, d'animations et d'interactions. Qu'elles soient d'intérieur ou d'extérieur, les scènes sont toujours plus complexes : les formes et les mouvements s'enrichissent et l'immersion n'en est que plus crédible.
Parmi les caractéristiques contribuant à la richesse d'un monde virtuel, la précision joue un rôle fondamentale (cf. figure 1.1). Celle-ci est la motivation d'un des plus beaux défis lancé à l'informatique graphique : la modélisation et le rendu multi-échelle. L'objectif de cette thèse est l'affichage de scènes tridimensionnelles avec de grande, variation, dans l'échelle d'observation.
Ce chapitre est composé de trois sections :
Dans cette section, nous nous attarderons d'abord sur les limites biologiques de nos perceptions. Nous décrirons ensuite une expérience imaginaire : un voyage à travers les échelles de l'univers. Ensuite, nous expliquerons (très succinctement!) comment l'Homme dépasse ses limites par l'utilisation d'outils.
La réalité nous offre un spectacle d'une complexité infinie. Dommage que nous soyons si mal loti pour en profiter...
D'un point de vue biologique, nos limites sont incontournables. Nous nous déplaçons lentement. Dans nos moments de gloire aéronautique, nous fonçons à quelques dizaines de kilomètres par seconde, ce qui nous laisse à près d'un million d'année de l'étoile la plus proche après le soleil. Nos moyens de transport favoris, tels la marche à pied, le vélo ou la voiture, nous permettent de nous déplacer à des vitesses un milliard de fois inférieures à celle de la lumière.
L'
il est l'un des organes les plus sophistiqués du corps humain.
Pourtant, nous sommes, pour ainsi dire, pratiquement aveugles.
Notre champ de vision a un angle solide d'environ 
.
Malheureusement, nous n'y voyons précisément que dans un angle de 
.
Nous ne distinguons quasiment rien en dessous du millimètre.
Les couleurs que nous percevons sont une très grossière approximation des rayons électromagnétiques qui nous entourent.
Nous percevons l'écoulement du temps à peu près toujours au même rythme et les mouvements trop rapides nous sont imperceptibles.
Notre spectre de perception est ridiculement petit. Si nous n'avons pas conscience de ces limites, c'est qu'il en a toujours été ainsi.
Les limites de notre corps induisent irrémédiablement des limites intellectuelles. En effet, notre cerveau se forge en partie grâce aux signaux extérieurs qu'il reçoit. Par exemple, il est notoire que beaucoup de musiciens ont une bonne oreille. Il est bien sûr possible d'améliorer la qualité de son audition. Néanmoins, l'acuité d'une oreille favorise sans aucun doute le développement d'une certaine intelligence musicale1.1.
La stimulation neuronale est la base de l'intelligence, c'est une forme évoluée du principe de ``action-réaction''. Avides de nouvelles sensations, nous cherchons, par le moyen de notre corps, cette nourriture de l'esprit. Il est décidément regrettable que nous soyons intrinsèquement contraints par un corps dont aux facultés de perception si limitées.
Débarrassons nous de nos contraintes corporelles, notre imagination est faite pour cela. Je vous invite à devenir un super-observateur. Imaginez un outil capable de se transformer soit en microscope, soit en télescope, en passant par tous les intermédiaires possibles. Rajoutez à cela une paire d'ailes : vous êtes le premier voyageur multi-échelle.
Notre voyageur est sur Terre, il regarde la Lune. Il décolle et s'en rapproche en quelques secondes, la voyant grossir pour progressivement occuper tout son champ de vision. Il s'arrête et regarde la terre. Il se dit qu'on l'a tellement vue à la télévision que ce n'est même pas impressionnant, alors il regarde le soleil et fait marche arrière, très vite, si bien que bientôt il voit aussi toutes les planètes du système solaire. Alors il fait un tour sur Jupiter parce que c'est la plus grosse mais comme il se rapproche il voit que ce n'est qu'une boule de gaz dans laquelle il s'enfonce comme dans un brouillard.
Il décide ensuite d'aller plus loin, toujours en marche arrière. Le brouillard de Jupiter s'estompe, le système solaire s'enfuit. La voie lactée est toujours visible, comme depuis la terre : c'est une vaste ceinture transparente. Une multitude d'étoiles entoure le voyageur, réparties aléatoirement autour de lui. Mais alors qu'il continue à reculer, il constate qu'il laisse derrière lui un amas d'étoiles dont il vient juste de sortir. Toutes les étoiles le constituant se rassemblent comme un nuage de points lumineux toujours plus dense. Se concentrant sur ce nuage, il oublie de regarder autour, ce qui est bien dommage, car il s'écarte de la galaxie et un nouveau nuage prend forme sous ses yeux, toujours plus dense, en forme de spirale.
Alors il visite d'autres galaxies, s'en rapprochant à des vitesses bien supérieures à celle de la lumière et ralentissant au fur et à mesure qu'elles se rapprochent de sorte qu'il ne faut que quelques secondes pour sauter d'une galaxie à une autre. Il regarde encore quelques objets célestes, nébuleuses, quasars et même quelques trous noirs. Alors il recule encore...
De retour sur terre, notre voyageur n'est pas devenu fou, ce qui est remarquable compte tenu toutes les choses qu'il vient de voir. Après cette longue ballade, il veut se reposer. Mais pendant qu'il dort, il se fait piquer par un moustique et se réveille. Le voyageur se dit qu'il a envie de voir à quoi ressemble l'insecte qui vient de s'envoler plein de son sang. Alors il rappetisse et s'envole à sa poursuite. Celui-ci, vu de près, n'est pas très joli, plutôt effrayant même.
Alors il se rapproche de son il et devient si petit que le moustique lui-même ne peut le voir.
L'il du moustique devient une grande surface lisse au début mais très vite de nombreuses irrégularités apparaissent.
En se rapprochant encore, une multitude de petites briques surgissent, les cellules.
Notre voyageur en choisit une et entre dedans.
Une immense machinerie est en marche et de grosses molécules vaquent à leurs occupations.
Le voyageur se concentre sur le noyau dans lequel il distingue un long filament. Il se rapproche et perçoit alors la structure du filament : celui-ci est enroulé sur lui même. Il se rapproche d'un enroulement et constate qu'un second niveau d'enroulement succède au premier, puis encore un... Enfin, il perçoit une structure hélicoïdale, l'ADN. De près, on distingue les molécules qui la composent.
En se rapprochant de celles-ci, il distingue les atomes de chaque molécule et constate que ceux-ci sont en fait formés de plusieurs petites boules : les neutrons et les protons. En se rapprochant encore, il constate que ces boules sont en faits constituées de trois petites boules, les quarks. Il décide alors de se rapprocher des quarks pour voir de quoi ils sont constitués...
Soyons clairs, la ballade virtuelle décrite plus haut n'a pas été réalisée au cours de cette thèse. Même si le travail présenté ici va dans cette direction, la route est longue. Avant de générer un monde aussi complexe, il faut nous munir des bons outils.
C'est grâce à l'outil que l'Homme se dépasse. Avec nos mains, nous avons aiguisé des pierres pendant plusieurs millions d'années. C'est le temps qu'il nous a fallu pour parvenir aux premières abstractions : ``Je donne un coup de pierre là, puis un coup là, comme ça j'aurais plus de chance de ne pas casser la pierre avec le dernier coup que je donnerai là''... Il nous a fallu environ 10 millions d'années pour formuler une telle phrase.
A l'échelle du temps géologique, l'ordinateur vient tout se suite après la pierre. C'est l'outil le plus sophistiqué que nous ayons jamais conçu. Grâce à lui, on peut automatiser de nombreuses tâches ennuyeuses et se concentrer sur l'essentiel. Il nous permet de communiquer et de coopérer. Les jeux vidéos nous font vivre des expériences que la réalité ne peut pas nous donner : nous conduisons des engins imaginaires à des vitesses folles, construisons et détruisons des empires, devenons Dieu ou le Diable...
Bonne ou mauvaise, une chose est sûre : l'informatique élargit le spectre de nos perceptions. Elle met à notre disposition une gigantesque quantité de médias et nous aide, dans une certaine mesure, à ne pas nous perdre dans cet océan d'informations.
Toujours plus, toujours plus vite. L'explosion des technologies ``multimédias'' a inexorablement conduit à une énorme production d'informations. La quantité de son, d'image et de texte produite durant les 50 dernières années dépasse toute celle produite depuis l'aube de l'humanité. Un tel raz-de-marée pose quelques problèmes à nos petits cerveaux.
Devant une telle affluence, notre réaction varie entre l'abrutissement et l'abstinence. Heureusement, ces deux extrêmes ne sont pas les seules solutions. Pour arriver à percevoir dans tout ce brouhaha un peu de pertinence, il nous faut prendre le temps de discerner, d'analyser et de prendre du recul.
Prendre du recul et aller à l'essentiel : nous devons apprendre à naviguer. Et bien sûr, pour nous aider dans cette tâche, de nouveaux outils doivent nous assister et incidemment former notre intelligence à ce nouvel exercice que l'on pourrait nommer : la perception multi-échelle.
La lutte pour la perception multi-échelle a déjà commencé. En fait, elle existe depuis que l'Homme existe : nos capacités d'abstraction sont l'une des caractéristiques de notre espèce. Simplement le besoin a grandi et plus que jamais, nous avons besoin de hiérarchiser nos pensées. Il nous faut acquérir la souplesse de sauter de concept en sous-concepts, d'argumenter le général et le détail, sans jamais perdre de vue l'ensemble.
Par exemple, peut-être vous souvenez-vous avoir appris à l'école que le corps est constitué de cellules. Puis quelques semaines plus tard est venu une seconde révélation : les cellules sont constituées de molécules qui sont elles-mêmes constituées d'atomes. Personnellement, je suis resté perplexe devant ce discours. Je ne remettais pas la chose en question, mais j'avais beaucoup de mal à imaginer mon corps immense comparé à un atome et ridiculement petit comparé à une galaxie.
Essayons d'imaginer l'outil adéquat dans la situation de l'écolier face à l'infiniment grand et l'infiniment petit. La difficulté ici n'est pas de se familiariser avec l'existence des galaxies et des atomes. En effet, quelques images ou schémas bien sentis permettent d'appréhender de tels objets en les ramenant à notre échelle. La difficulté réside dans le passage d'une échelle à l'autre. Comment rendre compte de variations d'échelle de plusieurs dizaines d'ordres de grandeur ?
Mais pour nous entraîner à naviguer entre le détail et le général, j'ai la conviction qu'une aide visuelle serait du plus grand secours. Pour revenir à l'exemple de l'écolier, un film similaire à la ballade décrite en 1.1.2 serait parfaitement adéquat. Un observateur se déplacerait de l'autre bout de l'univers jusqu'à une molécule ADN d'un arbre terrien.
Dans cette section, les principaux problèmes liés à la modélisation et à l'affichage de scènes avec de grandes variations d'échelle sont énumérés, ce qui nous conduit à préciser les objectifs de ce travail. Ensuite, les principales contributions de cet ouvrage sont brièvement décrites. Enfin, nous présenterons l'articulation du document.
L'observation multi-échelle exacerbe les problèmes d'aliasing1.2 et leurs conséquences néfastes. Dans le cas d'application avec de grandes variations d'échelle, les méthodes de simplification sont difficilement utilisables. En revanche, la modélisation procédurale, bien que délicate à mettre en oeuvre, est plus adéquate.
Lors de la modélisation, un modèle 3D est la plupart du temps échantillonné dans l'espace à une certaine résolution. Lors d'une observation du modèle, celui-ci est usuellement projeté sur un écran, c'est dire une grille de pixels 2D à une autre résolution. Si le pas d'échantillonnage du modèle 3D après projection et à peu près celui de l'écran, l'affichage se passe plutôt bien.
Lors d'observations multi-échelles, on autorise la caméra à se rapprocher ou à s'éloigner du modèle. Ce genre de déplacement fait varier le pas d'échantillonnage du modèle 3D après projection. En conséquence, si celui-ci est constant dans l'espace 3D, il existe forcément des positions de caméra pour lesquelles l'écart entre la résolution du modèle projeté et celle de l'écran est grand. L'affichage souffre alors inexorablement des fameux problèmes d'aliasing [Whi81] et la qualité du rendu se dégrade.
De très nombreux travaux proposent des méthodes multi-échelles pour garder le pas d'échantillonnage de la projection du modèle 3D le plus proche possible du pas d'échantillonnage de l'écran.
De nombreuses méthodes multi-échelles supposent la connaissance du modèle à sa précision maximum pour en extraire automatiquement des versions simplifiées. Lors de l'affichage, on choisira le bon degré de simplification en fonction de la distance à la caméra. Ce sont les méthodes de simplification ; elles seront étudiées dans le chapitre 2.
Simplifier automatiquement un modèle en gardant de bonnes propriétés visuelles devient de plus en plus difficile à mesure que le modèle initial est précis. Symétriquement, les simplifications extrêmes sont de mauvaise qualité.
De plus, le coût mémoire nécessaire à une description fine d'un modèle n'est pas acceptable lorsque qu'une grande précision est requise.
Intuitivement, un modèle observé de 
fois plus près devra être fois plus précis, et donc environ 
fois plus volumineux en mémoire (dans le cas tridimensionnelles).
Enfin, pour assurer un affichage efficace, ces méthodes reposent généralement sur des précalculs lourds limitant sérieusement les possibilités d'animation.
Certaines méthodes décrivent un modèle par des fonctions plutôt que par des données brutes. Ce sont les méthodes procédurales ; elles seront étudiées dans le chapitre 3. Appliquées à la multi-échelle, elles permettent de ne pas décrire un modèle à son niveau le plus fin et d'échapper ainsi aux limitations des algorithmes de simplification.
Des algorithmes de modélisation procédurale multi-échelle existent notamment depuis 1975 [Man75] sous le nom de fractales.
Les objets fractales sont très répétitifs et non-animés.
De rares travaux ont récemment permis d'introduire l'animation et de diminuer la répétitivité en ajoutant plus de contrôle.
Mais chacun d'entre eux est appliqué à un cas particulier et à chaque fois leur mise en uvre est laborieuse.
Notre objectif est simple et ambitieux : nous voulons modéliser et afficher des modèles 3D sans contraintes sur les variations d'échelle.
Nous désirons modéliser des phénomènes massivement animés (prairie et arbre sous le vent par exemple). Toute structure algorithmique trop statique, nuisant au possibilité d'animation, sera donc évitée.
Nous visons des performances temps-réel, mais aussi un contrôle fin sur la qualité requise lors de l'affichage.
Ces deux critères sont inexorablement antinomiques.
Lorsque la qualité augmente, les performances diminuent : c'est en quelque sorte le produit
qui est constant.
Nous voulons donc offrir le maximum de contrôle sur ce coefficient
et notamment permettre de régler celui-ci pour un rendu temps-réel.
Remarquons ici que le terme qualité n'est pas défini rigoureusement car il dépend de valeurs perceptuelles difficilement quantifiables.
Par conséquent, le terme
est lui-même assez approximatif.
Néanmoins, j'ai choisi de l'utilisé dans cette ouvrage puisqu'il exprime une balance certe imprécise mais bel et bien réelle.
Très généralement, nos contributions sont une analyse du problème posé par la multi-échelle, l'introduction d'un formalisme pour la modélisation par complexification et une mise en pratique de ce concept.
Nous avons identifié les méthodes de simplification comme étant intrinsèquement incapables d'assurer globalement un rendu temps-réel de scènes complexes et animées avec de grandes variations d'échelle.
La réalisation d'un algorithme temps-réel de rendu de prairie sous le vent nous a fait prendre conscience des avantages de la modélisation procédurale multi-échelle.
En revanche, cette approche nécessitait jusqu'à présent une modélisation au cas par cas laborieuse compte tenu de l'absence d'outil dédié à cette tâche.
Nous montrons que les problèmes d'affichage multi-échelle sont intimement liés au langage descriptif (ou représentation) choisi pour représenter les modèles.
Nous proposons un nouveau langage descriptif procédurale multi-échelle que nous appelons représentation par complexification permettant de décrire une très grande variété de formes tridimensionnelles.
Ce langage impose de décrire un modèle par un ensemble de fonctions ajoutant de la précision à une forme tridimensionnelle initiale. Ces fonctions enrichissent non seulement l'apparence d'un modèle, mais aussi son animation.
Un nouvel outil de modélisation, nommé Dynamic Graph, offre un environnement de travail facilitant la modélisation par complexification pour une grande classe d'objets tridimensionnelles. Deux intervenants extérieurs l'ont testé pendant deux mois et ont notamment réalisé un modèle d'arbre multi-échelle animé.
Nous proposons un nouvel algorithme de rendu qui permet un affichage des modèles avec de grandes variations d'échelle.
Afin d'assurer un rendu efficace, il rejoue les fonctions ajoutant des détails données lors de la modélisation jusqu'à satisfaire la précision requise par l'observateur.
Des réglages sur la précision permettent un excellent contrôle sur le coefficient
.
Un nouvel algorithme de détection d'occultation permet, sans aucun précalcul, d'ignorer les parties occultées de scènes animées.
 |
Cette thèse est bâtie autour du processus de création schématisé dans la figure 1.2. Celui décrit l'acte de modélisation de la façon suivante :
uvre dont il contrôle les paramètres ;
Cette thèse est composée des chapitres suivants (cf. figure 1.3) :
 |