La détection de collision est une tâche essentielle pour la simulation physique d’environnements virtuels. De nos jours, la détection de collision est l’un des goulets d’étranglement calculatoire dans les applications de réalité virtuelle dû à la complexité des environnements que l’on souhaite simuler et par la contrainte d’interaction en temps-réel. Nous avons concentré nos travaux sur la seconde étape de la détection de collision (narrow-phase) dans laquelle les tests de collisions sont effectués sur des paires d’objets. Contrairement à la première étape, les tests de collisions sont effectués sur des versions détaillées des modèles géométriques et sont donc très sensible au niveau calculatoire à la complexité géométrique de ceux-ci.Cette thèse vise à améliorer les performances de la détection de collision lors de l’utilisation d’objets géométriques complexes (formes représentées par un maillage, éventuellement non-convexe et/ou déformable). Nos méthodes permettent d’accélérer le calcul de la narrow-phase. Les algorithmes proposés peuvent être implémentés sur GPU pour profiter de leur puissance de calcul et ainsi améliorer les performances.Pour réaliser la narrow-phase, nous proposons un pipeline adapté à une implémentation GPU. Celui-ci permet de réaliser la narrow-phase à l’aide d’algorithmes basés lancer de rayon. Notre méthode repose sur un principe commun où tous les tests de collision sont effectués par lancer de rayon à partir des sommets des objets. Cette généricité nous permet de réaliser les tests sur des maillages ayant n’importe quelles propriétés (rigide ou déformable, convexe ou non-convexe). Les algorithmes de lancer de rayon utilisés étant choisis en fonction des propriétés des objets pour optimiser les performances.Nous avons généralisé la méthode de détection de collision utilisée pour supporter, en plus des objets volumiques, des objets surfaciques (tels que des tissus). Cette méthode est compatible avec le pipeline proposé et permet de réaliser des tests de collisions entre n’importe quelle combinaison d’objets.De plus, nous proposons d’exploiter la cohérence temporelle pour améliorer les performances. Le résultat de la détection de collision est généralement très semblable entre deux pas de temps successifs. Suite à cette observation, nous proposons un algorithme de lancer de rayon itératif qui intègre le résultat du pas précédent pour exploiter cette cohérence temporelle. Cet algorithme peut être utilisé conjointement avec des algorithmes de lancer de rayon standard. Il permet de remplacer certains tests unitaires pour mettre à jour de manière incrémentale le résultat de la détection de collision. L’algorithme de lancer de rayon itératif est ajouté au pipeline en tant qu’alternative aux autres algorithmes de lancer de rayon et est utilisé prioritairement dû à son faible coût calculatoire. / Collision detection is an essential task for physical simulation of virtual environments. Nowadays, collision detection is one of the main bottleneck of virtual reality applications. This is due to the complexity of the environments we want to simulate and the real-time interaction constraint. We have concentrated our work on the second phase of collision detection, the narrow-phase, in which collision queries are performed on pairs of objects. Contrary to the first phase of collision detection, collision queries are performed on the full representation of the objects (with all details) and are thus sensible to the geometric complexity of the objects in term of computation time.This thesis is aimed to improve the performances of collision detection when using geometrically complex objects (represented with triangle meshes, potentially non-convex and deformable). Our methods are able to reduce computation times. Our proposed algorithms can be implemented on GPU to take advantage of their computational power and thus further improve the performances of our methods.To implements our narrow-phase, we propose a pipeline which is adapted for GPU execution. This pipeline perform collision detection with ray-tracing algorithms. Our methods rely on a shared principle where all collision queries are performed by casting rays from the vertices of the objects. This genericity allow us to perform collision detection on triangle meshes with any properties (rigid or deformable, convex or non-convex). The ray-tracing algorithms used are dynamically selected depending on the properties of the objects to improve the performances.We have generalized the collision detection method we use in our pipeline to handle, in addition to volumetric objects (represented by their surface), surface objects (such as cloth). This method is compatible with our pipeline and allow us to perform collision detection with any combination of volumetric and surface objects.Furthermore, we propose to exploit temporal coherency to improve performances. The result of collision queries (contact points) are generally similar between successive time-step. Starting from this observation, we propose a ray-racing algorithm which use the result of the previous time-step to exploit this temporal coherency. This ray-tracing algorithm can be used in conjunction to standard ray-tracing algorithms. It is used to replace standard ray-tracing algorithms in specific condition to update the result of the previous time-step instead of computing it from scratch. The iterative ray-tracing algorithm is added in our pipeline as an alternative to other ray-tracing algorithms and is used in priority due to his lower computational cost compared to other algorithms.

Le lancer de rayon est un algorithme permettant de représenter des scènes 3D de façon très réaliste. Son principe, simple et puissant, repose sur les lois de l'optique géométrique : l'image que voit un observateur est le fruit des interactions entre des photons 6mis par des sources lumineuses et des objets possédant des propriétés géométriques et optiques. L'utilisation d'un modèle basé sur la physique permet une bonne approche des phénomènes naturels suivants : l'éclairement par des sources lumineuses, la réflexion de la lumière sur des objets et la transmission de la lumière à travers des objets transparents. L'algorithme dérivant de ce modèle possède pourtant un inconvénient majeur : le temps de traitement d'une image est très important. Bien que de nombreuses méthodes d'accélération aient été proposées pour tenter d'améliorer sa vitesse d'exécution, ce problème demeure bien présent. Toutefois, avec le développement actuel des machines parallèles à mémoire distribuée et des réseaux d'ordinateurs, une voie d'accélération très prometteuse se développe : la parallélisation. De plus, la mise en commun des capacités ''mémoire" de chaque composante d'une architecture parallèle rend possible le traitement de scènes comportant un plus grand nombre d'objets aux propriétés de plus en plus complexes. Le chapitre 1 présente l'algorithme de lancer de rayon ainsi que les accélérations séquentielles proposées dans la littérature. D apparaît que les techniques les plus efficaces sont basées soit sur l'utilisation de volumes englobants soit sur des subdivisions de l'espace. Malgré ces optimisations, la parallélisation demeure la source d'accélération au plus fort potentiel. Le chapitre 2 recense les différents types d'architectures parallèles et expose les familles d'algorithmes utilisées pour la parallélisation du lancer de rayon sur des machines parallèles à mémoire distribuée. Deux stratégies permettent une distribution de la base de données : 1' envoi de rayons et l'envoi d'objets. Dans le chapitre 3, après avoir présenté nos contraintes, nous comparons les algorithmes parallèles pouvant y répondre grâce à leur modélisation. Les résultats obtenus vont nous amener à proposer deux nouveaux algorithmes de parallélisation basés sur un nouveau type de flot. Enfin, dans le chapitre 4 nous présentons nos résultats expérimentaux et leur analyse. Nos tests sont réalisés sur des machines massivement parallèles et sur un réseau de stations de travail.

Ces travaux de recherche s’inscrivent dans la problématique scientifique de reconstruction du relief sous un couvert végétal à partir d’observations aéroportées. Le scanner laser aéroporté est une technique d’imagerie très prometteuse, notamment pour l’observation des zones forestières. Sa déclinaison "onde complète" consiste à émettre une impulsion laser et à enregistrer temporellement l’intégralité des échos de retour réfléchis par la scène. La forme des échos de retour fournit des informations sur l’épaisseur optique du couvert végétal. De nombreux systèmes commerciaux sont en exploitation, en particulier en topographie ou en bathymétrie. Mais ces systèmes ne sont pas dédiés à l’observation de la végétation. L’objectif de cette thèse est l’étude de l’intérêt de ces systèmes pour la construction de modèle numérique de terrain (MNT) sous couvert végétal. Elle est basée sur le développement d’outils de simulation du signal temporel incident au capteur lidar et de traitement des données. Dans un premier temps, le modèle physique de lidar onde complète, DELiS (n-Dimensional Estimation of Lidar Signals) a été développé. Il permet de simuler l’observation de scènes de végétation réalistes, tout en incluant la prise en compte de l’environnement extérieur (atmosphère, soleil) ainsi que des caractéristiques de la source et de la chaîne de détection (bruits de mesure). DELiS a été validé par confrontation à des résultats analytiques. Ensuite, DELIS a permis de comprendre et d’évaluer l’importance des diffusions multiples dans le couvert en fonction du champ de vue du lidar mais aussi de justifier l’utilisation d’acquisitions aéroportées petit champ pour simuler le signal d’un lidar spatial plus grand champ. Dans une deuxième étape, ses capacités de simulation ont été utilisées afin d’étudier l’intérêt du lidar onde complète pour la reconstruction d’un MNT sous couvert végétal. Dans ce but, nous avons développé et implémenté numériquement une méthode originale de traitement et de classification des données lidar onde complète permettant de séparer les échos lidar provenant du sol de ceux provenant de la végétation. Après classification des échos, nous avons reconstruit la géométrie du sol et des objets occultés par la végétation. Enfin, nous avons étudié comment combiner des données aéroportées acquises sous différents points de vue afin d’améliorer les reconstructions. Nos travaux montrent que le scanner laser aéroporté onde complète pourrait permettre d’obtenir en milieux forestier des reconstructions de la géométrie du terrain à des résolutions sub-métriques et avec une précision de l’ordre de 10 à 20 centimètres. La combinaison de visées multi-angulaire permet, par l’apport d’une quantité importante d’information supplémentaire, d’améliorer encore la reconstruction du MNT. Nous montrons cependant que les visées inclinées sont plus sensibles à la présence des troncs et branchages des arbres, éléments qui sont susceptibles d’introduire une erreur importante dans les processus de classification et de reconstruction. Pour cette raison, nous recommandons l’utilisation de la visée nadir pour la reconstruction mono-vue des modèles numériques de terrain, et nous proposons une méthode permettant de choisir de façon optimale les visées inclinées à ajouter pour l’observation détaillée d’une portion plus restreinte de la scène. / This research work regards the scientific challenge of reconstructing the ground and the object presents under a vegetation cover from airborne observations. Airborne laser scanning is a promising technology. Full-waveform devices are able to record the complete temporal return signal following the emission of a short laser pulse towards the ground. This offers a great potential for remote sensing of forested areas, since the laser pulse will travel through the vegetation. Many commercial systems are already operated for topography or bathymetry. Scientists have been using these systems for vegetation observation, even if they are not dedicated to this purpose. The objective of this thesis is to study the relevance of full-waveform lidars for the geometric reconstruction of digital terrain models (DTM) under vegetation. We also aim at developing simulation and data processing toolsthat will help design and optimize future sensors dedicated to vegetation observation. Our first task was the development of a new physical simulator for full-waveform lidar measurement. The DELiS model (n-Dimensional Estimation of Lidar Signals) is able tosimulate the observation of complex and realistic vegetation scenes while accounting for atmosphere and sun perturbations, and simulating the multiple scattering of the laser pulse in the canopy. We have also implemented a sensor model for simulation of the measurement, amplification and digitization noises. This operational simulation tool is a key asset for future physical studies as well as for designing and optimizing future sensors and data processing methods. After validating the DELiS model by confrontation with analytical results, we have used it for studying the interest of full-waveform lidar for digital terrain models reconstruction under vegetation. For this purpose, we have developed a full-waveform lidar data processing method for decomposition of the signals and classification of the lidar echoes into two classes : ’ground’ and ’vegetation’. We were then able to reconstruct ground geometry.Finally, we have led a study on the combination of multi-angular acquisitions for improvement of the reconstructions.Our work shows that airborne full-waveform lidar observations may allow ground reconstruction with sub-metric resolutions and a precision of 10 to 20 centimeters in forested areas. Combining multiple viewing angles provides additional data, and helps improving the precision of the reconstructions. Yet, we show that non-nadir viewing is much more sensitive to trunks and branches. These elements may be the cause of an additional error in the classification and reconstruction processes. For this reason, we recommend using nadir viewing for single-view ground reconstruction, and propose a method for optimally selecting non-nadir views for the detailed observation of restricted areas of interest.

Simuler efficacement l'éclairage global est l'un des problèmes ouverts les plus importants en infographie. Calculer avec précision les effets de l'éclairage indirect, causés par des rebonds secondaires de la lumière sur des surfaces d'une scène 3D, est généralement un processus coûteux et souvent résolu en utilisant des algorithmes tels que le path tracing ou photon mapping. Ces techniquesrésolvent numériquement l'équation du rendu en utilisant un lancer de rayons Monte Carlo. Ward et al. ont proposé une technique nommée irradiance caching afin d'accélérer les techniques précédentes lors du calcul de la composante indirecte de l'éclairage global sur les surfaces diffuses. Krivanek a étendu l'approche de Ward et Heckbert pour traiter le cas plus complexe des surfaces spéculaires, en introduisant une approche nommée radiance caching. Jarosz et al. et Schwarzhaupt et al. ont proposé un modèle utilisant le hessien et l'information de visibilité pour raffiner le positionnement des points de la cache dans la scène, raffiner de manière significative la qualité et la performance des approches précédentes. Dans ce mémoire, nous avons étendu les approches introduites dans les travaux précédents au problème du radiance caching pour améliorer le positionnement des éléments de la cache. Nous avons aussi découvert un problème important négligé dans les travaux précédents en raison du choix des scènes de test. Nous avons fait une étude préliminaire sur ce problème et nous avons trouvé deux solutions potentielles qui méritent une recherche plus approfondie. / Efficiently simulating global illumination is one of the most important open problems in computer graphics. Accurately computing the effects of indirect illumination, caused by secondary bounces of light off surfaces in a 3D scene, is generally an expensive process and often solved using algorithms such as path tracing or photon mapping. These approaches numerically solve the rendering equation using stochastic Monte Carlo ray tracing. Ward et al. proposed irradiance caching to accelerate these techniques when computing the indirect illumination component on diffuse surfaces. Krivanek extended the approach of Ward and Heckbert to handle the more complex case of glossy surfaces, introducing an approach referred to as radiance caching. Jarosz et al. and Schwarzhaupt et al. proposed a more accurate visibility-aware Hessian-based model to greatly improve the placement of records in the scene for use in an irradiance caching context, significantly increasing the quality and performance of the baseline approach. In this thesis, we extended similar approaches introduced in these aforementioned work to the problem of radiance caching to improve the placement of records. We also discovered a crucial problem overlooked in the previous work due to the choice of test scenes. We did a preliminary study of this problem, and found several potential solutions worth further investigation.

Milieu où les ultrasons se propagent environ 10% plus rapidement qu’au sein des tissus environnants, le cristallin est connu pour être la source majeure d’aberrations de phase du milieu oculaire. De fait, l’échographie ophtalmique trans cornéenne est affectée par ses effets qui se manifestent sur les B-scans par une dégradation marquée de la résolution spatiale et du contraste, accompagnée de plus, d’importantes distorsions, particulièrement notables au niveau du fond de l’œil. Face à ce problème et en vue de l’arrivée prochaine de barrettes US HF dans la pratique ophtalmologique, un beamforming adapté a été développé au cours de cette thèse. Basé sur un lancer de rayon à 2 points fixes, il permet le calcul de délais de focalisation qui compensent les aberrations induites par le cristallin, en prenant en compte les effets réfractifs à son interface avec les humeurs. Les résultats obtenus in vitro et ex vivo avec une barrette 20MHz et un échographe de recherche (ECODERM) sont rapportés. / In ophthalmic ultrasonography the crystalline lens is known to be the main source of phase aberration, as ultrasounds (US) propagate about 10% faster than in the surrounding intra-ocular medium. Hence, it impairs significantly both spatial and contrast resolution of axial B-scans, and in addition causes important distortion, especially on the ocular fundus. To deal with this issue and in view of the next coming of US arrays in ophthalmologic practice, we developed in this thesis an adapted beamforming (BF) free from crystalline lens aberrations. It lies on a two point ray tracing approach to compute focusing delays that take into account crystalline lens aberrations including refraction at the interface. Initially developed considering a uniform US velocity in the lens, the adapted BF has been extended to consider the velocity gradient that exists in the real lens. In vitro and ex vivo results obtained with a 20 MHz linear array driven by a US research scanner (the ECODERM) are reported.