Bruno Lévy : Goodshape, optimiser l'échantillonnage

La modélisation d’objets 3D par ordinateur est le fondement des images de synthèse, bien sûr, mais également de certains types de simulations numériques, que ce soit pour les calculs aérodynamiques des avions, les recherches en chimie ou les modélisations du sous-sol pour l’industrie pétrolière. La première étape consiste à échantillonner l’objet, à savoir distribuer sur l’objet un ensemble de points de la manière la plus homogène possible. Depuis les années soixante, on calcule souvent cet échantillonnage par l’algorithme de Lloyd-Max, qui ne "converge" pas assez rapidement pour être appliqué à des objets complexes.

« J’ai eu l’intuition que l’on pouvait faire bien mieux et bien plus vite, raconte Bruno Lévy. En voyant plusieurs travaux de mon collègue Pierre Alliez (Geometrica), fondés sur cet algorithme, j’ai pressenti une certaine analogie entre le problème de l’échantillonnage et celui de l’équation de la chaleur, que l’on sait très bien optimiser du point de vue mathématique. »

Il a donc tenté avec Wenping Wang, chercheur de l’université de Hong Kong, une nouvelle approche fondée sur la théorie de l’optimisation numérique. Résultat : l’échantillonnage est dix à cent fois plus rapide et le résultat est beaucoup plus précis. D’ores et déjà, cela permet d’échantillonner des objets bien plus grands et d’aborder des problèmes plus complexes. Friand d’images, il résume avec simplicité ces performances accrues : « Calculer la fonction de Lloyd-Max jusqu’à la dérivée seconde, c’est un peu comme passer la seconde en voiture. » 

La bourse de 1,1 million d’euros  du Conseil européen de la recherche va nous permettre de financer quatre thèses de doctorat, deux postdoctorants, un ingénieur, et d’organiser un workshop international pendant les cinq années du projet GoodShape.

Le résultat n’est néanmoins pas à la hauteur de ses espérances car ces dérivées « oscillent pas mal » , comme si la route était sinueuse et empêchait l’automobiliste d’accélérer ! Il faut trouver d’autres routes pour faire mieux, c’est-à-dire développer d’autres algorithmes avec d’autres méthodes d’optimisation numérique. « Nous explorerons ces pistes dans le cadre du projet GoodShape, financé par le Conseil européen de la recherche depuis août 2008 », annonce Bruno Lévy.

Optimiser l’échantillonnage devrait également permettre d’améliorer les résultats de nombreuses simulations numériques. « L’idée est d’adapter l’échantillonnage au fur et à mesure des calculs, autrement dit, en même temps que le phénomène que l’on calcule », explique- t-il. Il a formalisé ce concept, qui va être expérimenté dans GoodShape, sous le nom de "base de fonctions mobiles". Il permet d’échantillonner les objets à partir des paramètres les plus significatifs selon le résultat des calculs. Difficile de prédire les avantages : sûrement une meilleure précision et, dans certains cas, un temps de calcul inférieur. Ce qui est certain, c’est que les applications sont nombreuses. Spécialistes en images de synthèse, ces chercheurs vont d’abord tester le concept sur les simulations qui utilisent l’équation de la lumière pour réaliser des images plus précises, avec de belles ombres – point faible des images de synthèse. Une thèse vient de commencer sur le sujet. Des travaux sont également prévus en chimie avec Bernard Maigret (équipe-projet Orpailleur) pour simuler plus efficacement les vibrations des molécules à partir d’un nombre limité de paramètres. Idem en modélisation du sous-sol pour améliorer la précision des prédictions et même en compression d’images et de vidéos.