In this dissertation, we study the triangular mesh simplification process, describing its main characteristics. We discuss an adaptation for triangular meshes of a mesh simplification process based on Voronoi coverage proposed by Peixoto [2002]. Moreover, we use Fast Marching Method as a distance function over the mesh and some different strategies for simplified mesh vertices selection, like curvature based selection. The simplification process is done by constructing an intrinsic Voronoi diagram over the original mesh. We discuss some necessary conditions to obtain a mesh, as Voronoi dual, without any singularities and topologically equivalent to the original mesh. / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Nesta dissertação, estudaremos o processo de simplificaçãoo de malhas triangulares, caracterizando-o com suas particularidades. Discutiremos uma adaptação para superfícies triangulares do método de simplificação baseado em uma cobertura de Voronoi proposto por Peixoto [2002]. Além disso, utilizaremos o método Fast Marching como uma nova métrica e diferentes estratégias para seleção de vértices da malha simplificada, como a seleção por curvatura. A simplificação ocorre a partir de um diagrama de Voronoi intrínseco à malha. Discutiremos algumas condições necessárias para que a partir do dual desse diagrama, obtenha-se uma malha sem singularidades que seja equivalente a malha original.

<p>Captured and generated 3D data can be so large that it creates a problem for today's computers since they do not fit into the main or graphics card memory. Therefore methods for handling and rendering the data must be developed. This thesis presents a way to pre-process and render out-of-core height map data for real time use. The pre-processing uses a mesh decimation API called Simplygon developed by Donya Labs to optimize the geometry. From the height map a normal map can also be created and used at render time to increase the visual quality. In addition to the 3D data textures are also supported. To decrease the time to load an object the normal and texture maps can be compressed on the graphics card prior to rendering. Three different methods for covering gaps are explored of which one turns out to be insufficient for rendering cylindrical equidistant projected data.At render time two threads work in parallel. One thread is used to page the data from the hard drive to the main and graphics card memory. The other thread is responsible for rendering all data. To handle precision errors caused by spatial difference in the data each object receives a local origin and is then rendered relative to the camera. An atmosphere which handles views from both space and ground is computed on the graphics card.The result is an application adapted to current graphics card technology which can page out-of-core data and render a dataset covering the entire earth at 500 meters spatial resolution with a realistic atmosphere.</p>

Captured and generated 3D data can be so large that it creates a problem for today's computers since they do not fit into the main or graphics card memory. Therefore methods for handling and rendering the data must be developed. This thesis presents a way to pre-process and render out-of-core height map data for real time use. The pre-processing uses a mesh decimation API called Simplygon developed by Donya Labs to optimize the geometry. From the height map a normal map can also be created and used at render time to increase the visual quality. In addition to the 3D data textures are also supported. To decrease the time to load an object the normal and texture maps can be compressed on the graphics card prior to rendering. Three different methods for covering gaps are explored of which one turns out to be insufficient for rendering cylindrical equidistant projected data.At render time two threads work in parallel. One thread is used to page the data from the hard drive to the main and graphics card memory. The other thread is responsible for rendering all data. To handle precision errors caused by spatial difference in the data each object receives a local origin and is then rendered relative to the camera. An atmosphere which handles views from both space and ground is computed on the graphics card.The result is an application adapted to current graphics card technology which can page out-of-core data and render a dataset covering the entire earth at 500 meters spatial resolution with a realistic atmosphere.

Polygonal meshes are a common way of representing 3D surface models in many different areas of computer graphics and geometry processing. However, these models are becoming more and more complex which increases the cost of processing these models. In order to reduce this cost, mesh simplification algorithms are developed. Another important property of a polygonal mesh model is that whether it is regular or not. Regular meshes have many advantages over the irregular ones in terms of memory requirements, efficient processing, rendering etc. In this thesis work, both mesh simplification and regular remeshing algorithms are studied. Moreover, some of the popular mesh libraries are compared with respect to their approaches and performance to the mesh simplification. In addition, mesh models with disk topology are remeshed and converted to regular ones.

This report describes an algorithm for computing 3D object hierarchies fit for hlod optimization. The algorithm is used as a pre-processing stage in an hlod pipeline that automatically optimizes 3D models containing multiple meshes. The algorithm for generating hierarchies groups together meshes in a hierarchical tree using operations on bounding spheres of the meshes. The algorithm prioritizes grouping close objects together in the early stages, and relaxes its constraints toward the end, resulting in a tree structure with a single root node. The hierarchical tree is then used by computing proxy meshes, i.e. simplified stand-in meshes, for the inner nodes of the hierarchy. Finally, the resulting proxy meshes, together with the generated hierarchy and the original meshes, are used to render the model using a tree-traversing hlod switching algorithm that renders deeper parts of the tree containing more detailed meshes when more detail is needed. In addition, a minor change to the clustering algorithm is proposed. By swapping the bounding spheres to AABBs (Axis-Aligned Bounding Boxes) in the clustering stage, hierarchies with different properties are generated. This change is shown to generate hierarchies with similar rendering performance as the hierarchies made with bounding spheres, while at the same time resulting in lower space requirements for all proxy meshes. Overall, the proposed automatic hlod pipeline is shown to increase rendering performance for all evaluated scenes in most frames, while never yielding noticeably worse performance than the original model as well.

[pt] O uso de modelos computacionais baseados em malhas 3D se torna cada vez mais frequente em diversas áreas da computação como em jogos, animações e simuladores de realidade virtual, por exemplo. Entretanto, malhas que possuem uma grande quantidade de elementos exigem um alto poder computacional para serem manipuladas. A fim de resolver este problema são utilizados métodos de simplicação para reduzir o número de elementos, preservando a topologia que o modelo apresenta. Neste trabalho é introduzido um método de Difusão Geométrica Markoviana - difusão calculada na forma de probabilidades de transição e construída sobre um conjunto de pontos organizados geometricamente - aplicado na malha. Esse método combina uma estratégia baseada em uma Cadeia de Markov de base geométrica, que controla probabilisticamente o comportamento das normais na malha, com métodos de simplicação que são capazes de avaliar o impacto que a remoção de um elemento provoca na estrutura da malha. Métricas de avaliação são utilizadas para comparar o erro cometido em relação à malha original. / [en] Computational models based on 3D meshes are ubiquitous in are such as game, animations and virtual reality. However, very large data sets are frequently produced, e.g. by scanners 3D and fluid dynamics simulations, wich require high computer power to be handled. Mesh simplification tecniques, preserving the topology and the geometry of the mesh, are then implemented to bring the datea to a size suited to be used in such areas. In this work we introduce a new tecnique wich we call Markov Geometric Diffusion based on probability transition matrix tecniques and built upon a data set organized geometricallyas a mesh. This method puts together a strategy based on a geometrically constructed Markov chain, wich control, in a probabilistic way, a normal vector field to the mesh, with a simplification method capable of estimating the impact of element removal in the mesh structure. Several error evaluation metrics are used tocompare the error of the simplified mesh with the original one.

Complex 3D digital objects are used in many domains such as animation films, scientific visualization, medical imaging and computer vision. These objects are usually represented by triangular meshes with many triangles. The simplification of those objects in order to keep them as close as possible to the original has received a lot of attention in the recent years. In this context, we propose a simplification algorithm which is focused on the accuracy of the simplifications. The mesh simplification uses edges collapses with vertex relocation by minimizing an error metric. Accuracy is obtained with the two error metrics we use: the Accurate Measure of Quadratic Error (AMQE) and the Symmetric Measure of Quadratic Error (SMQE). AMQE is computed as the weighted sum of squared distances between the simplified mesh and the original one. Accuracy of the measure of the geometric deviation introduced in the mesh by an edge collapse is given by the distances between surfaces. The distances are computed in between sample points of the simplified mesh and the faces of the original one. SMQE is similar to the AMQE method but computed in the both, direct and reverse directions, i.e. simplified to original and original to simplified meshes. The SMQE approach is computationnaly more expensive than the AMQE but the advantage of computing the AMQE in a reverse fashion results in the preservation of boundaries, sharp features and isolated regions of the mesh. For both measures we obtain better results than methods proposed in the literature.

Level of Detail (LOD) is an important area in game development and it is a term used to describe the complexity of 3D models. Complex 3D models that are rendered from a far distance can often be simplified, to minimise rendering costs. The visual appearance of a simplified model should be as close to the original model as possible. This process requires metrics that can produce a similarity score or a distance value between meshes of different quality.  In this report, four different metrics are evaluated on a dataset with models of different qualities. The metrics are the MSDM2, Chamfer Distance, Hausdorff Distance and Simplygon's internal distance called Maximum Deviation. The dataset is already annotated with subjective scores from an earlier experiment, and the metrics are evaluated using the Spearman and the Pearson Correlations between metric values and subjective scores. The metrics are evaluated on the whole model set, and on different categories of models. The correlation scores are calculated using three different regression techniques. These are a per-dataset regression, a scaled per-dataset regression, and an averaged per-model regression. In addition to this, the metrics are also evaluated on the same dataset but where the LOD:s are created using a different simplifying algorithm, Simplygon's own reducer.  The results show that MSDM2 is the best metric in correlation with subjective scores when using a per-dataset regression. It is also noticed that the other metrics are all quite similar. The difference between the MSDM2 metric and the other metrics is also much larger on categories like "Hard surface"- and "Complex" models. When using the less common regression techniques, MSDM2 has the worst correlation, and Chamfer Distance correlates the best.  When comparing the results from the two datasets, Simplygon's own reducer seem to have a greater correlation with the MSDM2 metric. There was no clear difference in scores for the other metrics.  The end result is that one metric is not always the best metric. The type of model, and the simplification algorithm used to create the LOD, can both affect the result. The evaluation technique also changes the result.

Le CEA développe et utilise des logiciels de calcul, également appelés codes de calcul, dans différentes disciplines physiques pour optimiser les coûts de ses installations et de ses expérimentations. Lors d'une étude, plusieurs phénomènes physiques interagissent. Un couplage et des échanges de données entre plusieurs codes sont nécessaires.Chaque code réalise ses calculs sur une géométrie, généralement représentée sous forme d'un maillage contenant des milliers voire des millions de mailles. Cette thèse se focalise sur le transfert de déformations géométriques entre les maillages spécifiques de chacun des codes de calcul couplés. Pour cela, elle présente une méthode de couplage de plusieurs codes, dont le calcul des déformations est réalisé par l'un d'entre eux. Elle traite également de la mise en place d'un modèle commun aux différents codes de l'étude regroupant l'ensemble des données partagées. Enfin, elle porte sur les transferts de déformations entre des maillages représentant une même géométrie ou des géométries adjacentes. Les modifications géométriques sont de nature discrète car elles s'appuient sur un maillage. Afin de les rendre accessible à l'ensemble des codes de l'étude et pour permettre leur transfert, une représentation continue est calculée. Pour cela, deux fonctions sont développées : l'une à support global, l'autre à support local. Toutes deux combinent une méthode de simplification et un réseau de fonctions de base radiale. Un cas d'application complet est traité dans le cadre du réacteur Jules Horowitz. L'effet des dilatations différentielles sur le refroidissement d'un dispositif expérimental est étudié. / The CEA develops and uses scientific software, called physical codes, in various physical disciplines to optimize installation and experimentation costs. During a study, several physical phenomena interact, so a code coupling and some data exchanges between different physical codes are required.Each physical code computes on a particular geometry, usually represented by a mesh composed of thousands to millions of elements. This PhD Thesis focuses on the geometrical modification transfer between specific meshes of each coupled physical code. First, it presents a physical code coupling method where deformations are computed by one of these codes. Next, it discusses the establishment of a model, common to different physical codes, grouping all the shared data. Finally, it covers the deformation transfers between meshes of the same geometry or adjacent geometries. Geometrical modifications are discrete data because they are based on a mesh. In order to permit every code to access deformations and to transfer them, a continuous representation is computed. Two functions are developed, one with a global support, and the other with a local support. Both functions combine a simplification method and a radial basis function network. A whole use case is dedicated to the Jules Horowitz reactor. The effect of differential dilatations on experimental device cooling is studied.

This thesis introduces a representation of graphical data, progressive meshes, and its fields of usage. The main part of this work is mathematical representation of progressive meshes and the simplification algorithm, which leads to this representation. Examples of changes in progressive mesh representation are also part of this thesis, along with few examples. The result is an application that implements the calculation of the Progressive Meshes model representation