Dans cette thèse, nous identifions et exploitons des similarités partielles dans des objets 3D pour répondre à des besoins courants du domaine de la Conception Assistée par Ordinateur (CAO). De nouvelles méthodes sont introduites, d'une part pour détecter les similarités partielles, d'autre part pour utiliser ces similarités dans des applications spécifiques telles que l'édition de forme, la compression et l'indexation d'objets 3D. Grâce au développement des applications de la modélisation géométrique, ces modèles sont de plus en plus nombreux et sont disponibles à travers plusieurs modalités. Pour augmenter la productivité dans la création de tels objets virtuels, la réutilisation et l'adaptation des modèles existants est un choix prioritaire. Cela exige donc des méthodes facilitant le stockage, la recherche et l'exploitation de ces modèles. Heureusement, les similarités dans des objets 3D est un phénomène fréquent. De nombreux objets sont composés de parties similaires à une rotation, à une translation ou à une symétrie près. De ce fait, la détection des similarités partielles dans ces modèles est capable de répondre aux problématiques courantes : la taille du stockage est réduite en conservant seulement une partie au lieu de toutes les parties répétées d'un modèle; l'indexation des modèles 3D requiert a priori l'orientation canonique des modèles. Or, la symétrie dans un objet 3D est toujours une référence d'orientation cohérente avec la perception humaine. Nous utilisons donc la symétrie partielle pour aligner ces modèles et ainsi renforcer la robustesse des méthodes d'indexation. Dans un premier temps, nous introduisons une approche similaire à la Transformée de Hough pour détecter des similarités partielles dans des modèles BRep-NURBS. Cette approche identifie non seulement les parties similaires mais aussi les transformations qui les lient. À travers la classification des isométries dans l'analyse des transformations, notre approche peut distinguer la nature de transformation liant des parties similaires d'un modèle, c'est-à-dire, les parties similaires à une rotation, à une translation ou à une symétrie près. Dans le deuxième temps, nous proposons deux applications héritées directement des résultats obtenus par la détection. Tout d'abord, pour la compression, un modèle se transforme en un graphe de similarités d'où les faces principales à conserver sont sélectionnées dans la structure compressée. Ensuite, pour l'orientation, le plan de la symétrie dominante et la projection orthographique d'un modèle autour de ce plan permettent de définir un repère canonique pour aligner ce modèle. / In this thesis, we identify and exploit the partial similarities within 3D objects to answer the current needs of the Computer Aided Design field (CAD). Novel methods are introduced, on the one hand to detect the partial similarities, on the other hand to use these similarities for specific applications such as shape editing, compression and indexation of 3D objects. Because of the development of geometric modeling applications, 3D models are getting more numerous and available through many channels. To increase the productivity in creating such 3D virtual objects, the reuse and the adaptation of existing models becomes a prior choice. Thus, it requires methods easing the storage, the searching and the exploitation of these models. Fortunately, similarities within the 3D objects is a popular phenomenon. Many objects are composed of similar patches up to an approximated rotation, translation or symmetry. Hence, detecting the partial similarities within NURBSBRep models is able to solve the current issues : the storage size is reduced by coding a single patch instead of repeated patches of a model ; 3D model indexation requires a canonical orientation of these models. Furthermore, the symmetry within a 3D object is a good orientation reference, coherent with the human perception. Accordingly, we use the partial symmetries to align 3D models and so reinforce the robustness of indexation methods. In a first phase, we introduce an orginal approach similar to the Hough Transform to detect partial similarities within NURBS-BRep models. This approach identifies not only similar patches but also identifies the corresponding transformations that connect them. Additionally, through the classification of isometries in transformations analysis, our approach can distinguish the nature of transformations of similar patches of a model, that is, the patches similar up to an approximated rotation, translation or symmetry. This classification is advantageous for further applications : the similar patches of other transformation natures are considered in compressing ; the symmetric patches are used to normalize 3D models aim at a robust indexation. In the second phase, we propose two applications inherited directly from the obtained results of the detection. Firstly, for the compression, a model is transformed into a similarity graph where the principal faces to be coded are selected to form the compressed structure. Secondly, for the orientation, the plane of the dominant symmetry and the orthographic projection of a model around this plane generate a canonical frame to align this model.

Les travaux de l'état de l'art en compression progressive de maillages se sont concentrés sur les maillages triangulaires. Mais les maillages contenant d'autres types de faces sont aussi couramment utilisés. Nous proposons donc une nouvelle méthode de compression progressive qui peut efficacement encoder des maillages polygonaux. Ce nouvel algorithme atteint un niveau de performance comparable aux algorithmes dédiés aux maillages triangulaires. La compression progressive est liée à la décimation de maillages car ces deux applications génèrent des niveaux de détail. Par conséquent, nous proposons une nouvelle métrique volumique simple pour guider la décimation de maillages polygonaux. Nous montrons ensuite que les possibilités offertes par les algorithmes de compression progressive peuvent être exploitées pour adapter les données 3D en proposant un nouveau cadre applicatif pour la visualisation scientifique distante. Les algorithmes de compression progressive avec accès aléatoire peuvent mieux adapter les données 3D aux différentes contraintes en prenant en compte les régions d'intérêt de l'utilisateur. Notre premier algorithme de ce type est basé sur une segmentation préliminaire du maillage d'entrée. Chaque grappe est ensuite compressée de manière indépendante par un algorithme progressif. Notre second algorithme est basé sur le groupement hiérarchique des sommets obtenu par la décimation. Cette seconde méthode offre une forte granularité d'accès aléatoire et génère des maillages décompressés en une pièce avec des transitions lisses entre les parties décompressées à différents niveaux de détail. Des résultats expérimentaux démontrent l'efficacité des deux approches. / Previous work on progressive mesh compression focused on triangle meshes but meshes containing other types of faces are commonly used. Therefore, we propose a new progressive mesh compression method that can efficiently compress meshes with arbitrary face degrees. Its compression performance is competitive with approaches dedicated to progressive triangle mesh compression. Progressive mesh compression is linked to mesh decimation because both applications generate levels of detail. Consequently, we propose a new simple volume metric to drive the polygon mesh decimation. We apply this metric to the progressive compression and the simplification of polygon meshes. We then show that the features offered by progressive mesh compression algorithms can be exploited for 3D adaptation by the proposition of a new framework for remote scientific visualization. Progressive random accessible mesh compression schemes can better adapt 3D mesh data to the various constraints by taking into account regions of interest. So, we propose two new progressive random-accessible algorithms. The first one is based on the initial segmentation of the input model. Each generated cluster is compressed independently with a progressive algorithm. The second one is based on the hierarchical grouping of vertices obtained by the decimation. The advantage of this second method is that it offers a high random accessibility granularity and generates one-piece decompressed meshes with smooth transitions between parts decompressed at low and high levels of detail. Experimental results demonstrate the compression and adaptation efficiency of both approaches.

A Preservação Digital 3D é uma área da Computação Gráfica que visa gerar modelos tridimensionais virtuais de objetos que possuem valor cultural ou cientifico. A preservação digital possibilita a visualização realística do objeto através de museus virtuais ou aplicações científicas; e a restauração do objeto preservado, em caso de desgaste natural ou acidentes. Nesta área, a representação detalhada das caracteristicas do objeto é essencial, visto que armazena informações importantes sobre o objeto preservado. Neste contexto, este trabalho apresenta um estudo sobre a geração de textura para modelos tridimensionais. Nele, é feita uma revisão sobre a modelagem da geometria e da fotometria, e é desenvolvido um algoritmo para preservar a aparência do objeto original através do uso de fotografias de alta resolução na geração de textura para o modelo 3D. Os modelos 3D renderizados com as texturas obtidas através do processo desenvolvido neste trabalho são exibidos em um museu virtual. Entre os patrim^onios digitalizados estão artefatos indígenas pertencentes ao acervo do Museu de Arqueologia e Etnologia da UFPR, e conchas e fósseis pertencentes ao Museu de Ciências Naturais da UFPR. O algoritmo desenvolvido calcula a textura de um objeto a partir do seu modelo 3D e um conjunto de imagens obtidas por um scanner a laser e uma câmera fotográfica de alta resolução. O método desenvolvido gera texturas de alta qualidade, aumentando substancialmente o realismo do modelo 3D em comparação com texturas geradas apenas por imagens do scanner. Ele também não requer nenhum aparato especial ou um grande número de fotografias coloridas, simplificando seu uso por outros pesquisadores._________________________________________________________________________________________ ABSTRACT: 3D Digital Preservation aims to generate tridimensional virtual models of objects that have cultural or scientific value. The digital preservation provides realistic visualization of objects through virtual museums or scientific applications; and the preserved object’s restoration, in case of natural wear or accidents. In this area, the detailed representation of the object characteristics is essential since they store important information about the preserved object. In this context, this work presents a study about texture generation for 3D models of objects. It makes a review about the geometric and photometric modeling, and develops an algorithm to preserve the appearance of the original object, through the use of high resolution photographs during the 3D models texture generation. The 3D models using the generated texture are exhibited in a 3D virtual museum. Amongst the preserved assets, there are Brazilian Indigenous artworks, from UFPR’s Archaeology and Ethnology Museum, and shells and fossils from UFPR’s Natural Science Museum. The developed algorithm calculates the texture of an object from its 3D model and a set of images obtained from a laser scanner and a high resolution photographic camera. It generates high quality textures, improving substantially the realism of the 3D model as compared to textures generated only from scanner images. Also, it does not require any special apparatus nor a large number of color images, simplifying its use by other researchers.

Vårt magisterarbete är en 3D-animation som ska simulera en bergochdalbana. Vår uppgift har varit att ta reda på hur man genom illusioner kan lura människans hjärna att se djup även då bilden är helt platt. Vårt främsta verktyg vi använt oss av är glasögon med röd- och cyanfärgade filter. Till vår produktion har vi anlitat andra studenter för att komponera musik och mixa 5.1-ljud. Allt för att öka upplevelsen ännu mer. / Detta är en reflektionsdel till en digital medieproduktion. Mattias e-mail: mape78@gmail.com, Johan e-mail: atra@telia.com

Abstrakt Produkten som jag har utvecklat är en mjukvarubaserad 3D-renderare. För att göra en sådan produkt är man tvungen att gå djupt in i området 3D och utföra alla beräkningar på egen hand. Dessa tar annars grafikkortet hand om. Denna rapport förklarar varför jag har valt att göra en egen mjukvarubaserad 3D- renderare och vad den är för något och i vilka områden den används. Här förklaras även min syn på programmering, digitala spel, vad programmering innebär för mig och hur min syn på spel har påverkat mig med tiden. Jag tar även upp mina tankar om spelindustrin och samhällets misstolkade värderingar av spel samt vad för sorts spel jag anser skulle gynna mänskligheten i framtiden. Vad jag tycker om utbildningen Digitala spel nämns också samt hur jag tror att den skulle kunna förbättras. Slutligen följer en kortfattad beskrivning av hur mitt projekt har genomförts. Abstract The product I have been developing is a software based 3D renderer. To do such a thing you need to go deeply into the 3D subject and do all calculations which normally would be handed over as tasks to the graphic card. This document explains why I have chosen to do my own software based 3D renderer and what it really is. The document also explains what a 3D renderer does and in which places it is being used. Here you will also find my own explanation about programming and digital games, the meaning of programming for me and how my vision towards games has affected me in time. My ideas of the gaming industry, the misunderstandings of games in society and what sort of games that I think would aid humanity in the future. What I think about the education Digital Games will also be brought up as well as how I think Digital Games could be improved. Finally, a short description how the process of my project has been carried out will be told. / Detta är en reflektionsdel till en digital medieproduktion. Tele: tel 0709-210255 Mail: mattiaspgames@gmail.com

3D-NoC architectures are the amalgamation of the 3D integration (Die stacking of 3D-IC Technology) with the increased scalability found in NoC. Originally, it was proposed to tackle the problem of increasing the number of cores in the 2D plane which seems incompetent due to long distance interconnects. This architecture is aimed to optimize performance, power consumption, achieve low latency and increase the network bandwidth. Nevertheless, as more dies were being stacked vertically, IC operating frequency increases and this leads to some thermal issues which include high power density which increases average temperature. In addition to that, longer heat dissipation path results in different heat dissipation in each layer of the NoC which worsen the situation. An increase in the overall power consumption increases the average temperature, reduces performance and reliability. In this paper, an adaptive thermal-aware management scheme was proposed for 3D-NoCs, concentrating more on the hotspot regions in the network. This proposed protocol employs the thermal state of intermediate nodes and flits properties in a random uniform distributive way for packet routing. The proposed algorithm increases network availability and tends to distribute the temperature of the system evenly and uniformly within the network and making sure that packets are not forwarded to the hotspot node(s) and only flits with certain properties in the distribution are forwarded to the hotspot node(s). Before or during transmission, these two distributions must be calculated alongside the current node temperature to knowing which state of the distribution that node and flit belong to. The simulation shows this gave better performance in throughput and reliability of the network by reducing the number of hotspot nodes in the NoC. The proposed algorithm also reduces power consumption which is a function of temperature. Simulations show that our proposed algorithm reduces the total power/energy consumed by more than 59\% and throughput is improved by 69\% compared to a traditional XYZ routing. / Graduate

En cardiologie interventionnelle, le clinicien pourrait bénéficier d'une fusion de deux informations complémentaires provenant d'un scanner CT préopératoire et du flux d'images radiographiques servant au guidage des outils manipulés dans les vaisseaux du patient. Une telle fusion nécessite d'aligner les deux modalités et de construire des correspondances pertinentes. Nous proposons une approche basée sur la préservation de la topologie des structures mises en correspondance par le biais d'un cadre général visant à recaler des courbes ainsi qu'une méthode d'appariement d'arbre. / In interventional cardiology, the clinician can benefit from a fused visualization of a diagnostic pre-operative CT scan and the live X-ray projective images used for the guidance of dedicated tools inside the patient's vasculature. This necessitates to align both modalities and build relevant pairings between them. We have developed a general framework combining a method to register curves with a tree pairing procedure, which is able to preserve the topology of the structures.

L’anthropométrie est le domaine scientifique qui étudie les dimensions du corps humain. La complexité de la morphologie du corps nécessite une analyse 3D, aujourd’hui permise par les progrès des scanners 3D. L’objectif de cette étude est de comparer les populations et utiliser les résultats pour mieux adapter les produits sportifs à la morphologie des utilisateurs. Des campagnes de mensuration 3D ont été réalisées et des algorithmes de traitement automatique ont été créés pour analyser les nuages de points des sujets scannés. Basés sur les méthodes d’images et de géométrie, ces algorithmes repèrent des points anatomiques, calculent des mesures 1D, alignent les sujets scannés et créent des modèles anthropométriques 3D représentatifs des populations. Pour analyser les caractéristiques anthropométriques, des statistiques de premier ordre et factorielles ont été adaptées pour être utilisées dans l’espace 3D. Les méthodes ont été appliquées à trois parties : le pied, la tête et la poitrine. Les différences morphologiques entre les populations, mais également au sein d’une population donnée, ont été révélées. Par exemple, la différence à chaque point de la tête entre des têtes a été calculée. Les statistiques en trois dimensions ont aussi permis de mettre en évidence l’asymétrie de la tête. La méthode de création de modèles anthropométriques est plus adaptée à nos applications que les méthodes dans la littérature. L’analyse en trois dimensions permet d’obtenir des résultats qui ne sont pas visibles par les analyses 1D. Les connaissances acquises par cette étude sont utilisées pour la conception de différents produits vendus dans les magasins DECATHLON à travers le monde. / Anthropometry is the scientific field that studies human body dimensions (from the greek άνθρωπος (human) + μέτρον (measure)). Anthropometrical analysis is based actually on 1D measurements (head circumference, length, etc). However, the body’s morphological complexity requires 3D analysis. This is possible due to recent progress of 3D scanners. The objective of this study is to compare population’s anthropometry and use results to adapt sporting goods to user’s morphology. For this purpose, 3D worldwide measurement campaigns were realized and automated treatment algorithms were created in order to analyze the subjects’ point cloud. Based on image processing methods and on shape geometry, these algorithms detect anatomical landmarks, calculate 1D measurements, align subjects and create representative anthropometrical 3D models. In order to analyze morphological characteristics, different statistical methods including components’ analysis, were adapted for use in 3D space. The methods were applied in three body parts: the foot, the head and the bust. The morphological differences between and inside the populations were studied. For example, the difference in each point of the head, between Chinese and European head, was calculated. The statistics in three dimensions, permitted also to show the asymmetry of the head. The method to create anthropometrical models is more adapted to our applications than the methods used in the literature. The analysis in three dimensions, can give results that they are not visible from 1D analyses. The knowledge of this thesis is used for the conception of different products that they are sold in DECATHLON stores around the world.

Ce rapport présente et analyse les différentes possibilités de modélisation directe et de grande envergure de la forme du fond des voies naviguables. Cette étude est motivée par le fait que dans la modélisation de rivière, les incertitudes quant à la prédiction de la profondeur et du mouvement du lit, peuvent souvent être affectées par sa forme. La forme du fond constitue le facteur dominant dans le transport solide de nombreux cours d´eau qui nécessitent donc d´être entretenus par les autorités compétantes.Des expériences hydrodynamiques et morphodynamiques ont été menées au sein de l´institut fédéral allemand de la recherche et de l´ingénieurie des cours d´eau (BAW). Des mesures en haute résolution ont été effectuées et ont révélé la formation naturelle de dunes tridimensionelles à l´équilibre avec le champ d´écoulement environnant. Le modèle hydrodynamique est calibré sur cette base de données pour modéliser le régime d´écoulement complexe à travers une suite de dunes tridimensionelles. Les résultats de la simulation montrent qu´il est possible de reproduire le champ d´écoulement turbulent mesuré dans la configuration précédemment citée et que le niveau d´eau mesuré et simulé est également en accord avec cette même configuration. La résolution verticale et horizontale du maillage, le coefficient de friction, la forme du lit à petite échelle et la modélisation turbulente sont identifiés comme paramètres sensibles durant le calibrage.La seconde partie de cette thèse se concentre sur les simulations morphodynamiques de ce même canal expérimental mais cette fois avec un lit mobile. La numérisation du fond mesuré en haute résolution montrant la formation et le développement des dunes au fil du temps, est mis à disposition pour la comparaison. La hauteur et la largeur des dunes tout comme le moment de distribution, l´inclinaison et l´aplatissement sont utilisés pour comparer les dimensions des dunes ainsi que leur forme et leur distribution spatiale. Les formules du transport solide, de l´inclinaison, de l´aplatissement, les conditions aux limites et la considération des éléments de rugosité de sous échelle sont les paramètres qui influencent le plus la qualité des résultats. Durant cette étude, une attention toute particulière a été portée sur l´intégration des fluctuations turbulentes dans le calcul de la contrainte de cisaillement du fond. Un nouveau calcul total de cette contrainte est proposé et incorpore les vitesses d´écoulement principales et l´énergie cinétique turbulente fournit par le modèle turbulent. Grâce à cette approche, le modèle numérique est capable de reproduire quantitativement et qualitativement les dimensions de la forme du lit principal mesurée et les moments de forme des dunes physiques. Cela s´avère être la seule façon de reproduire le bon moment de distribution (aplatissement) du champ de dunes.Finalement, le modèle est appliqué à l´échelle du projet et testé sur une portion de l´Elbe (Allemagne). Les simulations morphodynamiques en haute résolution couplées à l´hydrodynamique-3D sont menées durant plusieurs jours sur la portion de rivière choisit d´une longueur de 4 kilomètres. Les formes des dunes préservent les paramètres de forme et la vitesse des dunes est en accord avec celle mesurée. La simulation montre des résultats prométeurs concernant la possibilité d´un usage opérationel du modèle dans l´avenir. Des problèmes locaux et communs comme les stratégies d´entretien tel que les changements dans les sections transversales d´écoulement, les brises lames et le revêtement sont des missions possibles qui peuvent être examinées / In this work the possibilities of direct modelling of large scale bed forms in waterways are highlighted and analysed. It is motivated by the fact that in river modelling, uncertainties in predicting water depth and bed movement can often be attributed to bed forms. Those bed forms are the dominating factor for bed load transport in many river stretches, which need to be maintained by the responsible waterways authorities.Hydrodynamic and morphodynamic experiments have been conducted at the Federal Waterways Engineering and Research Institute of Germany (BAW). High-resolution measurements have been performed over fixed, naturally formed three-dimensional sand dunes, which are at equilibrium with the surrounding flow field.Using these measured data sets, the hydrodynamic model is calibrated to simulate the complex flow situation over a train of several three-dimensional dunes. Simulation results show that it is possible to reproduce the measured turbulent flow field in the wake of the fixed dunes and that the measured and simulated water levels agree for the chosen configuration. Vertical and horizontal mesh resolution, friction coefficient, small scale bed forms and turbulence modelling are identified as most sensitive parameters during the calibration.The second part of this thesis focuses on morphodynamic simulations of the same experimental flume but with a mobile bed. High resolution measured bottom scans of the dune forms, developing over time, are available for comparison. Dune height and length, as well as the distribution moments, skewness and kurtosis are used to compare the dimensions of the dunes and also their shape and spatial distribution.Bed load transport formulation, skewness and kurtosis formulae, boundary conditions and the consideration of sub-grid scale roughness elements are the parameters which influence the quality of the results the most. A particular focus during the study is the inclusion of turbulent fluctuations in bed shear stress calculation. A new, total bed shear stress calculation is proposed, which incorporates mean flow velocities and turbulent kinetic energy provided by the turbulence model. With this approach, the numerical model is able to reproduce both qualitatively and quantitatively the measured mean bed forms dimensions and the shape moments of the physical dunes. It proves to be the only way to also produce the right distribution moment (kurtosis) of the dune field.Finally, the model is applied to project scale and tested on a stretch of the riverElbe, Germany. High resolution morphodynamic simulations coupled to 3D-hydrodynamics are conducted over several days for the chosen river stretch which is 4km in length. The dune forms preserve form and shape parameters and the dune speed agrees with the measured one. The simulations show promising results concerning the possibility of operational use of the model in the future. Local problems and statements, e.g. maintenance strategies such as changes in flow cross section, groynes and revetments, are possible tasks that can be examined

Les modèles 3D sont des contenus précieux très utilisés dans l'industrie, et donc la cible potentielle de piratages. Le tatouage robuste pour les maillages 3D apporte une réponse au problème du traçage de traître. Dans l'état de l'art du domaine, la couche d'adaptation du contenu en particulier est testée face des attaques standards. Une approche robuste à la pose est alors étudiée. Elle utilise une estimation robuste de l'épaisseur, définie comme la distance un nuage de points construits à partir de mesures du diamètre. Les performances expérimentales montrent qu'elle forme un point de départ prometteur pour le tatouage robuste de maillages 3D posés. Pour les maillages statiques, la modulation des distances radiales est une approche efficace du tatouage. Elle a été formulée comme un problème d'optimisation quadratique sous contrainte, dont nous proposons plusieurs extensions : une transformée par étalement, des primitives de référence calculées de manière intégrale, des directions de déplacement arbitraires, et de nouvelles métriques pour minimiser la distorsion perçue par un utilisateur. Des expériences illustrent leurs bénéfices pour le compromis entre la robustesse et la fidélité du tatouage. La sécurité est analysée par l'intermédiaire de deux mécanismes de protection et par une série d'attaques et de contre-Mesures. Un système de resynchronisation est intégré afin d'améliorer la résistance au rognage. Des points de recalage sont insérés dans une configuration spécifique qui porte les informations habituellement éliminées par l'attaque. Au décodage, elles sont récupérées de manière aveugle. Un gain significatif des performances est mesuré expérimentalement. / 3D models are valuable assets widely used in the industry and likely to face piracy issues. This dissertation deals with robust mesh watermarking that is used for traitor-Tracing. Following a review of state-Of-The-Art 3D watermarking systems, the robustness of several content adaptation transforms are benchmarked. An embedding domain robust against pose is investigated, with a thickness estimation based on a robust distance function to a point cloud constructed from some mesh diameters. A benchmark showcases the performance of this domain that provides a basis for robust watermarking in 3D animations. For static meshes, modulating the radial distances is an efficient approach to watermarking. It has been formulated as a quadratic programming problem minimizing the geometric distortion while embedding the payload in the radial distances. This formulation is leveraged to create a robust watermarking framework, with the integration of the spread-Transform, integral reference primitives, arbitrarily selected relocation directions and alternate metrics to minimize the distortion perceived. Benchmarking results showcase the benefits of these add-Ons w.r.t the fidelity vs. robustness watermarking trade-Off. The watermark security is then investigated with two obfuscation mechanisms and a series of attacks that highlight the remaining limitations. A resynchronization approach is finally integrated to deal with cropping attacks. The resynchronization embeds land-Marks in a configuration that conveys synchronization information that will be lost after cropping. During the decoding, this information is blindly retrieved and significant robustness improvements are achieved.