[pt] Malhas são amplamente usadas na discretização de domínios geométricos em aplicações na engenharia, como simulações de fluxo, transmissão de calor e deformação mecânica. O problema de geração de malhas é bem conhecido e estudado, mas a geração automática de malhas para um domínio físico com geometrias complexas, criando elementos que obedeçam a forma do objeto, e de tamanho e qualidade adequados, ainda é um desafio. Neste trabalho, foram estudados e implementados métodos para gerar malhas com restrições arbitrárias. O gerador implementado é do tipo de Delaunay, que constrói malhas Delaunay com restrições, e utiliza as propriedades da malha para inserir novos vértices e melhorar a qualidade dos elementos. / [en] Meshes are widely used in the discretization of geometric domains for engineering applications such as fluid flow simulator, heat transfer simulations and mechanical deformation. The mesh generation problem is well known and studied, nevertheless the automatic generation of meshes to domains with complex geometry, creating elements that conform to the forms, and of adequate size and quality, is still a challenge. In this work, mesh generation methods capable of generation mesh of arbitrary restrictions were studied and implemented. The implemented generator is a Delaunay generator, which constructs constrained Delaunay meshes, and utilizes the properties of the mesh to insert new vertices and improve the quality of the elements.

No description available.

No description available.

This thesis presents the numerical algorithms to carry out the face transformation. The main efforts are denoted to the finite volume method (FVM) with the Delaunay triangulation to solve the Laplace equations in the harmonic transformation undergone in face images. The advantages of the FVM with the Delaunay triangulation are: (1) Easy to formulate the linear algebraic equations, (2) Good to retain the geometric and physical properties, (3) less CPU time needed. The numerical and graphical experiments are reported for the face transformations from a female to a male, and vice versa. The computed sequential and absolute errors are and , where N is division number of a pixel into subpixels. Such computed errors coincide with the analysis on the splitting-shooting method (SSM) with piecewise constant interpolation in [Li and Bui, 1998c].

Magistro baigiamajam darbui pasirinkta tema yra Trimačiai objektai: atvaizdavimo ir deformacijos algoritmai. Ši tema nagrinėja paviršiaus rekonstrukciją iš taškų debesies ir galimybes pritaikyti paviršiaus deformacijos algoritmus. Analizės etapo metu išsiaiškinta, kad pagrindinė paviršiaus atstatymo iš taškų debesies problema yra lėtas algoritmų veikimas. Šiame darbe siūlomas atvirkštinės inžinerijos metodas, veikiantis 2D Delaunay trianguliacijos pagrindu. Pateikiami algoritmai padalina taškų debesį į kelias dalis, tada iš trimatės erdvės taškų debesies dalys yra transformuojamos į dvimatę erdvę, suskaičiuojama 2D Delaunay trianguliacija ir gautas trikampių tinklelis vėl transformuojamas į trimatę erdvę. Taip pat pateikiamos teorinės galimybės gautą paviršių transformuoti jau žinomu algoritmu. Po algoritmų praktinio įgyvendinimo buvo nustatyta, kad jie veikia taip kaip tikėtasi, rezultatas gaunamas greičiau nei naudojant kitus žinomus algoritmus. Taip pat buvo pastebėta, kad 2D Delaunay trianguliaciją geriau naudoti kai taškų skaičius taškų debesyje yra labai didelis, o kai taškų skaičius neviršija 2000 geriau naudoti 3D Delaunay trianguliaciją. / The chosen theme of the Master of Science degree paper is “Three dimensional objects: visualization and deformation algorithms“. This subject considers surface reconstruction from point clouds and the possibilities to apply surface deformation algorithms. During the analysis phase we found that the main problem of the algorithms of surface reconstruction from scanned point clouds is the lack of speed. So in this paper a method, based on 2D Delaunay triangulation, for reverse engineering is proposed. This method divides point clouds into several parts, and then maps all the points of those point cloud parts to the plane. Then a 2D Delaunay triangulation is computed and the mesh is mapped back to the point cloud. We also give theoretical possibilities to apply a known algorithm for surface deformation. During the implementation phase we found that our algorithms work as expected, but quicker than the other methods proposed earlier. We also noticed that it’s better to use 2D Delaunay triangulation for bigger point clouds and 3D Delaunay triangulation for point clouds, which contains no more than approximately 2000 points.

Thesis (MSc (Mathematical Sciences. Applied Mathematics))--University of Stellenbosch, 2007. / Image morphing is a popular technique used to create spectacular visual effects, by gradually transforming one image into another. This thesis explains what exactly is meant by the terms “image morphing” / “warping”, where it is used and how it is done. A few existing morphing techniques are described and finally an implementation using Delaunay triangulation and texture mapping is presented.

abstract: Mostly, manufacturing tolerance charts are used these days for manufacturing tolerance transfer but these have the limitation of being one dimensional only. Some research has been undertaken for the three dimensional geometric tolerances but it is too theoretical and yet to be ready for operator level usage. In this research, a new three dimensional model for tolerance transfer in manufacturing process planning is presented that is user friendly in the sense that it is built upon the Coordinate Measuring Machine (CMM) readings that are readily available in any decent manufacturing facility. This model can take care of datum reference change between non orthogonal datums (squeezed datums), non-linearly oriented datums (twisted datums) etc. Graph theoretic approach based upon ACIS, C++ and MFC is laid out to facilitate its implementation for automation of the model. A totally new approach to determining dimensions and tolerances for the manufacturing process plan is also presented. Secondly, a new statistical model for the statistical tolerance analysis based upon joint probability distribution of the trivariate normal distributed variables is presented. 4-D probability Maps have been developed in which the probability value of a point in space is represented by the size of the marker and the associated color. Points inside the part map represent the pass percentage for parts manufactured. The effect of refinement with form and orientation tolerance is highlighted by calculating the change in pass percentage with the pass percentage for size tolerance only. Delaunay triangulation and ray tracing algorithms have been used to automate the process of identifying the points inside and outside the part map. Proof of concept software has been implemented to demonstrate this model and to determine pass percentages for various cases. The model is further extended to assemblies by employing convolution algorithms on two trivariate statistical distributions to arrive at the statistical distribution of the assembly. Map generated by using Minkowski Sum techniques on the individual part maps is superimposed on the probability point cloud resulting from convolution. Delaunay triangulation and ray tracing algorithms are employed to determine the assembleability percentages for the assembly. / Dissertation/Thesis / Ph.D. Mechanical Engineering 2011

Representações computacionais de formas podem ser criadas em ferramentas CAD ou geradas a partir de um objeto físico já existente. Esta última abordagem oferece como vantagens rapidez e fidelidade ao objeto original, que são os aspectos fundamentais em muitas aplicações, como Simulações Numéricas de Equações Diferenciais Parciais e Imagens Médicas. A reconstrução (ou geração de malhas superficiais) a partir de pontos amostrados de uma superfície de um objeto é um problema clássico de representação de formas. Nesta dissertação apresentamos um vasto levantamento bibliográfico deste tipo de reconstrução, classificando e descrevendo os principais trabalhos presentes na literatura. A partir do levantamento bibliográfico, selecionamos um conjunto de algoritmos sobre os quais foram realizadas comparações teóricas e empíricas cujos resultados são apresentados. Para finalizar, apresentamos aplicações de nossas implementações em Simulação Numérica de Equações Diferenciais Parciais e processamento de Imagens / Computational representations of shapes can be developed using CAD applications or created from data acquired from a real physical object. This latter is advantageous with respect to time and fidelity to the original object which are essential to several applications, such as Numerical Simulation of Partial Differential Equations and Medical Imaging. A classical shape representation problem is that of reconstruction (or superficial mesh generation) from points sampled over the surface of an object. In this Master\'s thesis we describe a broad survey of these reconstruction methods. We focus in the classification and characterization of the main algorithms proposed in the literature. From this survey, we selected some algorithms and conducted some theoretical and practical comparisons. We conclude this work describing applications of the algorithms implemented in Numerical Simulations of Differential Partial Equations and Image Processing

Procedural content generation inom spel refererar till algoritmiskt, procedurellt skapande av digitalt innehåll i syfte att automatisera och minska mängden arbete för designers och grafiker. Ett område procedural content generation används för inom spel är dungeon generering. Målet för detta arbete var att utforska en 2D algoritm som används i spelet TinyKeep för just generering av dungeons och se hur den algoritmen kunde prestera om den modifierades för generering i en 3D rymd. Den modifierade algoritmen utvärderades baserat på attributen variation, justerbarhet, pålitlighet samt tidseffektivitet. Resultatet visade visade att det är möjligt att använda algoritmen i spelet TinyKeep i en 3D-rymd med godtagbart prestationsresultat. Som värst visade den modifierade algoritmen på en viss svaghet angående genereringstid vid en större tom rymd med större antal rum hos en dungeon. För framtida arbete vore det intressant att dela upp av delar av den modifierade algoritmen på separata trådar. / <p>Det finns övrigt digitalt material (t.ex. film-, bild- eller ljudfiler) eller modeller/artefakter tillhörande examensarbetet som ska skickas till arkivet.</p>

Many architecure, medical and engineering applications need a spacial support for various numerical computations (i.e. FEM simulations). Tetrahedral meshes are one of perspective spatial representations for them. In this thesis, several possibilities of effective tetrahedral mesh representation for its generating and processing are described. A computer library for the mesh processing is proposed which can be characterized by memory  efficient imposition of the mesh while preserving the ability to apply topological and geometric algorithms effectively. The library is implemented in C++ language using templates. Time and space complexity of typical mesh operations is compared with CGAL library and according to measurements the proposed library has lower memory requirements than CGAL.