Bruno Lévy: Goodshape, optimising sampling

Computer modelling of 3D objects is the bedrock of computer-generated images, naturally, but is also used in certain types of digital simulation, whether for aerodynamic calculations for aircraft, chemistry research or subsurface models for the oil industry. The first stage consists of sampling the object, by distributing a set of points across the object as uniformly as possible. Since the 1960s, this sampling has often been calculated using the Lloyd-Max algorithm, which does not "converge" quickly enough to be applied to complex objects. "I intuitively felt that it could be done better and faster," says Bruno Lévy. "Seeing some of the work done by my colleague Pierre Alliez (GEOMETRICA), based on that algorithm, I felt a certain analogy between the sampling problem and that of the heat equation, which we know how to optimise from a mathematical viewpoint."  He therefore tried a new approach based on the theory of numerical optimisation with Wenping Wang, a researcher at the University of Hong Kong. The outcome was sampling that is 10 to 100 times faster and gives much more accurate results. This already makes it possible to sample much larger objects and address more complex problems. Fond of images, he summarises the increased performance quite simply: "Calculating the Lloyd-Max function up to the second derivative is a bit like moving into second gear in the car." 

The 1.1 million euro  grant from the European Research Council will enable us to finance 4 doctoral theses, 2 post-doctoral researchers, one engineer, and organise an international workshop during the five years of the GoodShape project.

The result is however not quite all we had hoped, because these derivatives "vary a fair bit", as if the road was winding and prevented the driver from accelerating! We need to find another route to do better, i.e. develop other algorithms with other numerical optimisation methods. "We will be exploring these avenues under the GoodShape project, funded by the European Research Council since August 2008,"  he announces. Optimising sampling is also expected to enable improvements to be made in the results for many digital simulations. "The idea is to adapt the sampling as calculations progress, in other words, at the same time as the phenomenon being calculated," he explains. He has formalised this concept, which will be trialled in GoodShape, under the name "mobile functions base". It enables sampling of objects from the most significant parameters according to calculation results. It is difficult to predict the benefits – certainly better accuracy and, in some cases, a shorter calculation time. What is certain is that there are many applications. Specialists in computer-generated images, researchers are firstly going to test the concept on simulations that use the light equation to produce more accurate images, with proper shadows – a weakness in computer-generated images. A PhD has just started on this topic. Work is also planned in chemistry with Bernard Maigret (Orpailleur project) to more effectively simulate molecule vibrations from a limited number of parameters. Ditto in subsurface modelling to improve the accuracy of predictions, and even in image and video compression.