Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

L'objet de cette thèse est le développement et l'étude des algorithmes de planification de mouvement pour les systèmes hautement dimensionnés que sont les robots humanoïdes et les acteurs virtuels. Plusieurs adaptations des méthodes génériques de planification de mouvement randomisées sont proposées et discutées. Une première contribution concerne l'utilisation de techniques de réduction de dimension linéaire pour accélérer les algorithmes d'échantillonnage. Cette méthode permet d'identifier en ligne quand un processus de planification passe par un passage étroit de l'espace des configurations et adapte l'exploration en fonction. Cet algorithme convient particulièrement bien aux problèmes difficiles de la planification de mouvement pour l'animation graphique. La deuxième contribution est le développement d'algorithmes randomisés de planification sous contraintes. Il s'agit d'une intégration d'outils de cinématique inverse hiérarchisée aux algorithmes de planification de mouvement randomisés. On illustre cette méthode sur différents problèmes de manipulation pour robots humanoïdes. Cette contribution est généralisée à la planification de mouvements corps-complet nécessitant de la marche. La dernière contribution présentée dans cette thèse est l'utilisation des méthodes précédentes pour résoudre des tâches de manipulation complexes par un robot humanoïde. Nous présentons en particulier un formalisme destiné à représenter les informations propres à l'objet manipulé utilisables par un planificateur de mouvement. Ce formalisme est présenté sous le nom d'« objets documentés». / This thesis deals with the development and analysis of motion planning algorithms for high dimensional systems: humanoid robots and digital actors. Several adaptations of generic randomized motion planning methods are proposed and discussed. A first contribution concerns the use of linear dimensionality reduction techniques to speed up sampling algorithms. This method identifies on line when a planning process goes through a narrow passage of some configuration space, and adapts the exploration accordingly. This algorithm is particularly suited to difficult problems of motion planning for computer animation. The second contribution is the development of randomized algorithms for motion planning under constraints. It consists in the integration of prioritized inverse kinematics tools within randomized motion planning. We demonstrate the use of this method on different manipulation planning problems for humanoid robots. This contribution is generalized to whole-body motion planning with locomotion. The last contribution of this thesis is the use of previous methods to solve complex manipulation tasks by humanoid robots. More specifically, we present a formalism that represents information specific to a manipulated object usable by a motion planner. This formalism is presented under the name of "documented object".

L’essentiel du corpus théorique consacré au design et à la responsabilité de son praticien adopte une approche prescriptive où leurs auteurs dictent les contours d’une pratique responsable. Mais compte tenu de l’impact du design graphique sur notre quotidien, ne serait-il pas utile d’appréhender plus précisément le sens que ses praticiens donnent à leur responsabilité ? À notre avis, oui. L’objectif de notre recherche est donc de recueillir et de comprendre les significations de la responsabilité, et ainsi d’analyser les délibérations et les modélisations morales des praticiens du design graphique pour en proposer une description. Par le biais d’une étude qualitative, via des entretiens de groupes, nous avons réalisé une analyse en deux temps. D’abord, une synthèse de chaque groupe nous a permis d’identifier que la responsabilité fait sens comme habitude — au sens peircien du terme — qui se structure par rapport à la représentation que se fait le designer des enjeux de sa pratique au sein d’un réseau de parties prenantes. Ensuite l’examen des schémas individuels, qui ont donné lieu à la modélisation de trois des périmètres potentiels de ce maillage d’acteurs. / Design theory tends to adopt a prescriptive approach to designers’ responsibility, taking it upon itself to lay out guidelines for good conduct. However, given the impact of graphic design on human behavior and the fabric of society as a whole it seems essential to study how designers’ themselves define their responsibility. Thus, the purpose of our research is to collect, interpret and describe the meanings practitioners assemble with regard to their moral obligations. A qualitative study, built upon group interviews, has offered us a dual assessment. First, the analysis of each group allowed us to identify responsibility as a habit, in the Peircean sense of the term, that each designer establishes in relation to a network of stakes and stakeholders he or she articulates around his or practice. Secondly, the study of individual discourses revealed models of three potential perimeters of the system within which they evaluate their obligations.

Le travail de thèse, qui s'inscrit dans le cadre du projet européen PAPYRUS (Plug and Play monitoring and control architecture for optimization of large scale production processes) du 7ème PCRD, a concerné tout d'abord la synthèse et la mise en œuvre d'une approche de modélisation, de diagnostic et de reconfiguration originale. Celle-ci se fonde sur la génération de graphes causaux permettant de modéliser en temps réel le comportement d'un système complexe dans un premier temps. La cible de cette première étude a été la papeterie Stora Enso d'Imatra en Finlande, qui était le procédé d'application du projet PAPYRUS. En suite logique à cette première partie, une approche permettant l'accommodation du système à certains défauts particuliers a été définie par l'ajustement des signaux de consigne de diverses boucles de régulation. Le manuscrit est structuré en trois parties. Dans la première, le projet européen PAPYRUS est présenté. Le rôle de chaque partenaire y est décrit au travers des différents « workpackages » et le travail de thèse y est positionné. La seconde partie de la thèse a pour objectif la génération d'un modèle utile au diagnostic en se fondant uniquement sur les différents signaux mesurés du système. Plus précisément, un modèle causal graphique est présenté par la mise en évidence des liens de causalité entre les différentes variables mesurées. Des analyses à base d'inter-corrélation, de transfert d'entropie et du test de causalité de Granger sont effectuées. Une approche de diagnostic fondée sur le modèle graphique ainsi obtenu est ensuite proposée en utilisant un test d'hypothèse séquentiel. La dernière partie est dédiée au problème d'accommodation aux défauts. Le graphe utilisé pour établir le diagnostic du système est remanié afin de faire apparaitre les différentes boucles de régulation du système. Une stratégie permettant la sélection de consignes influentes est alors proposée avec l'objectif d'ajuster ces dernières afin de compenser l'effet du défaut survenu / The thesis deals with modelling, diagnosis and fault tolerance of large scale processes. It is a part of the European project PAPYRUS (7th FWP). First, the European PAPYRUS project is described with details on the role of each partner through work package descriptions. The positioning of the thesis in this respect is also given. The second part of the thesis is about modelling graphical models for diagnosis purpose; more precisely, graphical causal model is used to highlight the causal links between the different variables of the process. To obtain such a model from data, several methods are proposed based on cross-correlation, entropy transfer and Granger causality. A diagnosis-based approach on the resulting graphical model is then proposed using statistical test and causal model of the process. This approach is illustrated using data from an industrial process and results are validated. The final section addresses fault tolerance based on digraph inferences and reference governor. This approach is illustrated using a MATLAB simulation which has a functional architecture similar to Board Machine 4 of Stora Enso IMATRA in Finland

Dans cette thèse, nous présentons une nouvelle approche efficace pour le rendu de scènes vastes et d'objets détaillés en temps réel. Notre approche est basée sur une nouvelle représentation pré-filtrée et volumique de la géométrie et un lancer de cone basé-voxel qui permet un rendu précis et haute performance avec une haute qualité de filtrage de géométries très détaillées. Afin de faire de cette représentation voxel une primitive de rendu standard pour le temps-réel, nous proposons une nouvelle approche basée sur les GPUs conçus entièrement pour passer à l'échelle et supporter ainsi le rendu des volumes de données très volumineux. Notre système permet d'atteindre des performances de rendu en temps réel pour plusieurs milliards de voxels. Notre structure de données exploite le fait que dans les scènes CG, les détails sont souvent concentrées sur l'interface entre l'espace libre et des grappes de densité et montre que les modèles volumétriques pourrait devenir une alternative intéressante en tant que rendu primitif pour les applications temps réel. Dans cet esprit, nous permettons à un compromis entre qualité et performances et exploitons la cohérence temporelle. Notre solution est basée sur une représentation hiérarchiques des données adaptées en fonction de la vue actuelle et les informations d'occlusion, couplé à un algorithme de rendu par lancer de rayons efficace. Nous introduisons un mécanisme de cache pour le GPU offrant une pagination très efficace de données dans la mémoire vidéo et mis en œuvre comme un processus data-parallel très efficace. Ce cache est couplé avec un pipeline de production de données capable de charger dynamiquement des données à partir de la mémoire centrale, ou de produire des voxels directement sur le GPU. Un élément clé de notre méthode est de guider la production des données et la mise en cache en mémoire vidéo directement à partir de demandes de données et d'informations d'utilisation émises directement lors du rendu. Nous démontrons notre approche avec plusieurs applications. Nous montrons aussi comment notre modèle géométrique pré-filtré et notre lancer de cones approximé peuvent être utilisés pour calculer très efficacement divers effets de flou ainsi d'éclairage indirect en temps réel. / In this thesis, we present a new approach to efficiently render large scenes and detailed objects in real-time. Our approach is based on a new volumetric pre-filtered geometry representation and an associated voxel-based approximate cone tracing that allows an accurate and high performance rendering with high quality filtering of highly detailed geometry. In order to bring this voxel representation as a standard real-time rendering primitive, we propose a new GPU-based approach designed to entirely scale to the rendering of very large volumetric datasets. Our system achieves real-time rendering performance for several billion voxels. Our data structure exploits the fact that in CG scenes, details are often concentrated on the interface between free space and clusters of density and shows that volumetric models might become a valuable alternative as a rendering primitive for real-time applications. In this spirit, we allow a quality/performance trade-off and exploit temporal coherence. Our solution is based on an adaptive hierarchical data representation depending on the current view and occlusion information, coupled to an efficient ray-casting rendering algorithm. We introduce a new GPU cache mechanism providing a very efficient paging of data in video memory and implemented as a very efficient data-parallel process. This cache is coupled with a data production pipeline able to dynamically load or produce voxel data directly on the GPU. One key element of our method is to guide data production and caching in video memory directly based on data requests and usage information emitted directly during rendering. We demonstrate our approach with several applications. We also show how our pre-filtered geometry model and approximate cone tracing can be used to very efficiently achieve blurry effects and real-time indirect lighting.

En informatique graphique, le rendu des matériaux occupe une place très importante dans la qualité de l’image finale. De nombreux modèles ont contribué à améliorer l’apparence des matériaux. Aujourd’hui, certains matériaux restent encore difficiles à représenter à cause de leur complexité. Parmi ceux ci,la famille des matériaux anisotropes reste peu étudiée et complexe. Dans cette thèse nous proposons une meilleure compréhension des matériaux anisotropes au travers d’un modèle pour les représenter ainsi qu’un outil permettant de mieux en contrôler l’apparence. Notre modèle de matériaux brossés ou rayés se base sur la simulation du transport lumineux au sein de la micro-géométrie d’une rayure pour restituer tous les détails en conservant des temps de rendus suffisamment courts pour rendre la scène de manière interactive.Notre outil d’édition des reflets anisotropes utilise le champ d’orientation des BRDF pour donner à l’utilisateur l’impression de dessiner ou de déformer des reflets directement sur l’objet. / In computer graphics, material appearance is a fundamental component of the final image quality. Many models have contributed to improve material appearance. Today, some materials remains hard to represent because of their complexity. Among them, anisotopic materials are especially complex and little studied. In this thesis, we propose a better comprehension of anisotropic materials providing a representation model and an editing tool to control their appearance. Our scratched material model is based on a light transport simulation in the micro-geometry of a scratch, preserves all the details and keeps an interactive rendering time. Our anisotropic reflections edition tool uses BRDF orientation fields to give the user the impression to draw or deform reflections directly on the surface.

L'automatique est une discipline qui traite entre autres de la commande et du diagnostic des systèmes industriels. Une première étape à l'obtention de schémas de commande et de diagnostic est d'analyser les propriétés du système considéré. Les principales propriétés analysées sont la commandabilité, l'observabilité, la diagnosticabilité, la stabilité... Des critères, souvent basés sur des approches algébriques ou géométriques, permettent de caractériser ces propriétés. En outre, des travaux publiés dans les années 1970 ont permis d'introduire une nouvelle représentation de systèmes à base de graphes orientés. De ces travaux, il résulte que l'approche graphique fournit des solutions simples et est ainsi très bien adaptée pour analyser des systèmes de grande dimension et/ou incertains. Malheureusement, peu de travaux basés sur des méthodes graphiques traitent des systèmes non linéaires. Par notre travail, nous avons souhaité combler ce manque en étudiant les propriétés d'observabilité et de diagnosticabilité des systèmes bilinéaires structurés à l'aide d'une approche graphique. Des conditions graphiques nécessaires et suffisantes d'observabilité de l'ensemble et d'une partie de l'état d'un système sont formulées. Par la suite le problème de placement de capteurs est abordé afin de recouvrer les propriétés d'observabilité. Enfin, nous nous sommes focalisés sur la propriété de diagnosticabilité. Après avoir donné une condition graphique nécessaire et suffisante de solubilité du problème de détection de défauts, nous avons alors étudié différents cas particuliers de commande afin de donner des conditions de solubilité au problème actif de détection de défauts.

La perception visuelle est un élément déterminant pour interagir avec notre environnement. Lors des activités physiques et sportives, la prise d'informations visuelles permet notamment à un athlète d'extraire et de sélectionner les indices visuels nécessaires pour anticiper le mouvement adverse. L'analyse de cette prise d'informations visuelles a fait l'objet de nombreuses recherches dans le domaine sportif, cependant toutes les méthodes employées semblent limitées sur le plan fonctionnel ou matériel. Ce travail a pour objectif l'évaluation et la mise en oeuvre d'une nouvelle méthodologie d'analyse de la prise d'informations visuelles fondée sur l'utilisation des environnements virtuels. Cette méthodologie est appliquée à l'activité du gardien de but de handball en situation de duel. Dans un premier temps, nous comparons les performances des gardiens de but face à notre méthodologie avec ceux obtenus face à une séquence filmée afin de démontrer l'intérêt des environnements virtuels dans ce domaine. Puis, nous abordons la mise en place de notre méthodologie en nous focalisant sur l'influence du niveau de détail et de la représentation graphique de l'action de tir sur la performance du gardien de but de handball. Enfin, nous utilisons notre méthodologie pour étudier la prise d'informations visuelles du gardien de but de handball. Plus précisément, nous estimons l'importance relative des informations visuelles issues de la trajectoire du ballon et du mouvement de tir

In this thesis, we focus on "structural information" in computer graphics, that is the information concerning the structure of 3D objects or scenes. More specifically, we define structural information as a two-scale notion, namely the object and the scene levels and propose a way of structuring 3D Geometry at both levels using the information of symmetry and instancing. In the first part of this thesis, we propose an original method to structure the geometry at the object level based on the information of symmetry. Inspired by the work on principal component analysis, we introduce for this purpose the generalized moment functions of a 3D shape. From the symmetry information that we have computed on the objects of the scene, we present in the second part of this thesis an approach to represent an unstructured 3D scene as a hierarchy of instances adapted to common tasks such as rendering or geometry editing.

A rapidly growing computer graphics community has contributed to dramatic increase in complexity with respect to geometry as well as physical phenomena. Simulating, approximating and visualizing geometry consisting of tens of millions of polygons simultaneously tested for collision or visibility is becoming increasingly common. Further, recent technological innovations from graphics card vendors have given impetus to achieving these results at very high frame rates. Despite tremendous developments in graphics hardware, capturing the complete surrounding environment poses a significant challenge. Given the added time constraint for real-time or interactive rates, simplified representations and suitable approximations of physical effects are of key importance.<br /><br />This dissertation focuses on simplified representations and computations to achieve real-time performance for complex tasks and concentrates on a variety of topics including simplification, visibility, soft shadows and voxelization.