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.

This master thesis is focused on parametrization of image point neighborhood. Some methods for point localization and point descriptors are described and summarized. Gabor filter is described in detail. The practical part of thesis is chiefly concerned with particle filter tracking system. The weight of each particle is determined by the Gabor filter.

Nous étudions dans cette thèse la génération de maillages anisotropes basée sur la triangulation de Delaunay et le diagramme de Voronoi. Nous considérons tout d'abord les maillages anisotropes localement uniformes, développés par Boissonnat, Wormser et Yvinec. Bien que l'aspect théorique de cette approche soit connu, son utilité pratique n'a été que peu explorée. Une étude empirique exhaustive est présentée et révèle les avantages, mais aussi les inconvénients majeurs de cette méthode. Dans un second temps, nous étudions les diagrammes de Voronoi anisotropes définis par Labelle et Shewchuk. Nous donnons des conditions suffisantes sur un ensemble de points pour que le dual du diagramme soit une triangulation plongée en toute dimension ; un algorithme générant de tels ensembles est conçu. Ce diagramme est utilisé pour concevoir un algorithme qui génère efficacement un maillage anisotrope pour des domaines de dimension intrinsèque faible plongés dans des espaces de dimension large. Notre algorithme est prouvable, mais les résultats sont décevants. Enfin, nous présentons le diagramme de Voronoi Riemannien discret, qui utilise des avancées récentes dans l'estimation de distances géodésiques et dont le calcul est grandement accéléré par l'utilisation d'un graphe anisotrope. Nous donnons des conditions suffisantes pour que notre structure soit combinatoirement équivalente au diagramme de Voronoi Riemannien et que son dual utilisant des simplexes droits mais aussi courbes est une triangulation plongée en toute dimension. Nous obtenons de bien meilleurs résultats que pour nos autres techniques, mais dont l'utilité reste limitée / In this thesis, we study the generation of anisotropic meshes using the concepts of Delaunay triangulations and Voronoi diagrams. We first consider the framework of locally uniform anisotropic meshes introduced by Boissonnat, Wormser and Yvinec. Despite known theoretical guarantees, the practicality of this approach has only been hardly studied. An exhaustive empirical study is presented and reveals the strengths but also the overall impracticality of the method. In a second part, we investigate the anisotropic Voronoi diagram introduced by Labelle and Shewchuk and give conditions on a set of seeds such that the corresponding diagram has a dual that is an embedded triangulation in any dimension; an algorithm to generate such sets is devised. Using the same diagram, we propose an algorithm to generate efficiently anisotropic triangulations of low-dimensional manifolds embedded in high-dimensional spaces. Our algorithm is provable, but produces disappointing results. Finally, we study Riemannian Voronoi diagrams and introduce discrete Riemannian Voronoi diagrams, which employ recent developments in the numerical computation of geodesic distances and whose computation is accelerated through the use of an underlying anisotropic graph structure. We give conditions that guarantee that our discrete structure is combinatorially equivalent to the Riemannian Voronoi diagram and that its dual is an embedded triangulation, using both straight and curved simplices. We obtain significantly better results than with our other methods, but the overall utility of

Visualization of glyphs has a long history in medical imaging but gains much more power when the glyphs are properly placed to fill the screen. Glyph packing is often performed via an iterative approach to improve the location of glyphs. We present an alternative implementation of glyph packing based on a Delaunay triangulation to speed up the clustering process and reduce costs for neighborhood searches. Our approach does not require a re–computation of acceleration structures when a plane is moved through a volume, which can be done interactively. We provide two methods for initial placement of glyphs to improve the convergence of our algorithm for glyphs larger and glyphs smaller than the data set’s voxel size. The main contribution of this paper is a novel approach to glyph packing that supports simpler parameterization and can be used easily for highly efficient interactive data exploration, in contrast to previous methods.

Today's modern aerospace systems exhibit strong interdisciplinary coupling and require a multidisciplinary, collaborative approach. Analysis methods that were once considered feasible only for advanced and detailed design are now available and even practical at the conceptual design stage. This changing philosophy for conducting conceptual design poses additional challenges beyond those encountered in a low fidelity design of aircraft. This thesis takes some steps towards bridging the gaps in existing technologies and advancing the state-of-the-art in aircraft design. The first part of the thesis proposes a new Pareto front approximation method for multiobjective optimization problems. The method employs a hybrid optimization approach using two derivative free direct search techniques, and is intended for solving blackbox simulation based multiobjective optimization problems with possibly nonsmooth functions where the analytical form of the objectives is not known and/or the evaluation of the objective function(s) is very expensive (very common in multidisciplinary design optimization). A new adaptive weighting scheme is proposed to convert a multiobjective optimization problem to a single objective optimization problem. Results show that the method achieves an arbitrarily close approximation to the Pareto front with a good collection of well-distributed nondominated points. The second part deals with the interdisciplinary data communication issues involved in a collaborative mutidisciplinary aircraft design environment. Efficient transfer, sharing, and manipulation of design and analysis data in a collaborative environment demands a formal structured representation of data. XML, a W3C recommendation, is one such standard concomitant with a number of powerful capabilities that alleviate interoperability issues. A compact, generic, and comprehensive XML schema for an aircraft design markup language (ADML) is proposed here to provide a common language for data communication, and to improve efficiency and productivity within a multidisciplinary, collaborative environment. An important feature of the proposed schema is the very expressive and efficient low level schemata. As a proof of concept the schema is used to encode an entire Convair B58. As the complexity of models and number of disciplines increases, the reduction in effort to exchange data models and analysis results in ADML also increases. / Ph. D.

Nous étudions les triangulations dans des espaces de courbure négative constante, en théorie et en pratique. Ce travail est motivé par des applications dans des domaines variés. Nous considérons les complexes de Delaunay et les diagrammes de Voronoï dans la boule de Poincaré, modèle conforme de l'espace hyperbolique, en dimension quelconque. Nous utilisons l'espace des sphères pour la description des algorithmes. Nous étudions aussi les questions algébriques et arithmétiques et observons que les calculs effectués sont rationnels. Les démonstrations sont basées sur des raisonnements géométriques et n'utilisent aucune formulation analytique de la distance hyperbolique. Nous présentons une implantation complète, exacte et efficace en dimension deux. Le code est développé en vue d'une intégration dans la bibliothèque CGAL, qui permettra une diffusion à un large public. Nous étudions ensuite les triangulations de Delaunay des surfaces hyperboliques fermées. Nous définissons une triangulation comme un complexe simplicial afin de permettre l'adaptation de l'algorithme incrémentiel connu pour le cas euclidien. Le cœur de l'approche consiste à montrer l'existence d'un revêtement fini dans lequel les fibres définissent toujours une triangulation de Delaunay. Nous montrons une condition suffisante sur la longueur des boucles non contractiles du revêtement. Dans le cas particulier de la surface de Bolza, nous proposons une méthode pour construire un tel revêtement, en étudiant les sous groupes distingués du groupe fuchsien définissant la surface. Nous considérons des aspects liés à l'implantation. / We study triangulations of spaces of constant negative curvature -1 from both theoretical and practical points of view. This is originally motivated by applications in various fields such as geometry processing and neuro mathematics. We first consider Delaunay complexes and Voronoi diagrams in the Poincaré ball, a conformal model of the hyperbolic space, in any dimension. We use the framework of the space of spheres to give a detailed description of algorithms. We also study algebraic and arithmetic issues, observing that only rational computations are needed. All proofs are based on geometric reasoning, they do not resort to any use of the analytic formula of the hyperbolic distance. We present a complete, exact, and efficient implementation of the Delaunay complex and Voronoi diagram in the 2D hyperbolic space. The implementation is developed for future integration into the CGAL library to make it available to a broad public. Then we study the problem of computing Delaunay triangulations of closed hyperbolic surfaces. We define a triangulation as a simplicial complex, so that the general incremental algorithm for Euclidean Delaunay triangulations can be adapted. The key idea of the approach is to show the existence of a finite-sheeted covering space for which the fibers always define a Delaunay triangulation. We prove a sufficient condition on the length of the shortest non-contractible loops of the covering space. For the specific case of the Bolza surface, we propose a method to actually construct such a covering space, by studying normal subgroups of the Fuchsian group defining the surface. Implementation aspects are considered.

A triangulação de Delaunay de um conjunto de pontos é uma importante entidade geométrica cujas aplicações abrangem diversas áreas da ciência. Triangulações regulares, que podem ser vistas como uma generalização da triangulação de Delaunay, onde pesos são associados aos vértices, também têm sido aplicadas em diversos problemas como reconstrução a partir de nuvens de pontos [5], geração de malha [12], modelagem molecular [7] e muitos outros. Apesar de ser muito utilizada, a fundamentação teórica referente à triangulação regular ainda não está tão desenvolvida quanto para triangulação de Delaunay. Por exemplo, pouco se sabe a respeito da dinâmica de uma triangulação regular [22] quando os pesos associados aos vértices mudam. Este trabalho tem como objetivo principal desenvolver um arcabouço teórico e computacional que permita representar uma triangulação qualquer como uma triangulação regular. Para isso, um estudo da dinâmica das operações de flip frente à variação de pesos nos vértices deve ser realizado. Este estudo tem como base o mapeamento da triangulação em um politopo que define os possíveis pesos para os vértices. Tal politopo pode ser obtido por meio de um sistema de inequações que gera um problema de programação linear cuja solução fornece os pesos adequados. A transformação de uma triangulação qualquer em triangulação regular permite o desenvolvimento de novas técnicas de morphing entre malhas e algoritmos para modelar níveis de detalhe, sendo este mais um objetivo deste trabalho / Delaunay triangulation of a set of points is an important geometrical entity whose applications encompass a range of scientfic fields. Regular triangulations, which can be seen as a generalization of Delaunay triangulation where weights are assigned to vertices, have also been widely employed in several problems, as for example mesh reconstruction from point clouds [5], mesh generation [12] and molecular modelling [7]. In spite of their applicability, the theoretical background of regular triangulations is not so developed as the theory of Delaunay triangulation. For example, the dynamic of regular triangulation is not completely known when the vertices weights change [22]. This work aims at developing a computational and theoretical framework that allow to represent a given triangulation as a regular triangulation. In this context, an investigation into the dynamic of edge ip operations regarding changes in the vertices weight must be accomplished. This investigation is based on mapping the triangulation in a polytope that defines the space of vertices weights. Such polytope can be built from an inequation system that can be associate to a linear program problem whose solution supplies the appropriated weights. By representing a triangulation as a regular triangulation one can conceive a new mesh morphing scheme and level of detail algorithm, being this another goal of this work

A triangulação de Delaunay de um conjunto de pontos é uma importante entidade geométrica cujas aplicações abrangem diversas áreas da ciência. Triangulações regulares, que podem ser vistas como uma generalização da triangulação de Delaunay, onde pesos são associados aos vértices, também têm sido aplicadas em diversos problemas como reconstrução a partir de nuvens de pontos [5], geração de malha [12], modelagem molecular [7] e muitos outros. Apesar de ser muito utilizada, a fundamentação teórica referente à triangulação regular ainda não está tão desenvolvida quanto para triangulação de Delaunay. Por exemplo, pouco se sabe a respeito da dinâmica de uma triangulação regular [22] quando os pesos associados aos vértices mudam. Este trabalho tem como objetivo principal desenvolver um arcabouço teórico e computacional que permita representar uma triangulação qualquer como uma triangulação regular. Para isso, um estudo da dinâmica das operações de flip frente à variação de pesos nos vértices deve ser realizado. Este estudo tem como base o mapeamento da triangulação em um politopo que define os possíveis pesos para os vértices. Tal politopo pode ser obtido por meio de um sistema de inequações que gera um problema de programação linear cuja solução fornece os pesos adequados. A transformação de uma triangulação qualquer em triangulação regular permite o desenvolvimento de novas técnicas de morphing entre malhas e algoritmos para modelar níveis de detalhe, sendo este mais um objetivo deste trabalho / Delaunay triangulation of a set of points is an important geometrical entity whose applications encompass a range of scientfic fields. Regular triangulations, which can be seen as a generalization of Delaunay triangulation where weights are assigned to vertices, have also been widely employed in several problems, as for example mesh reconstruction from point clouds [5], mesh generation [12] and molecular modelling [7]. In spite of their applicability, the theoretical background of regular triangulations is not so developed as the theory of Delaunay triangulation. For example, the dynamic of regular triangulation is not completely known when the vertices weights change [22]. This work aims at developing a computational and theoretical framework that allow to represent a given triangulation as a regular triangulation. In this context, an investigation into the dynamic of edge ip operations regarding changes in the vertices weight must be accomplished. This investigation is based on mapping the triangulation in a polytope that defines the space of vertices weights. Such polytope can be built from an inequation system that can be associate to a linear program problem whose solution supplies the appropriated weights. By representing a triangulation as a regular triangulation one can conceive a new mesh morphing scheme and level of detail algorithm, being this another goal of this work

<p>This thesis presents a complete and fully automatic method for estimating the volume of an airbag, through all stages of its inflation, with multiple synchronized high-speed cameras.</p><p>Using recorded contours of the inflating airbag, its visual hull is reconstructed with a novel method: The intersections of all back-projected contours are first identified with an accelerated epipolar algorithm. These intersections, together with additional points sampled from concave surface regions of the visual hull, are then Delaunay triangulated to a connected set of tetrahedra. Finally, the visual hull is extracted by carving away the tetrahedra that are classified as inconsistent with the contours, according to a voting procedure.</p><p>The volume of an airbag's visual hull is always larger than the airbag's real volume. By projecting a known synthetic model of the airbag into the cameras, this volume offset is computed, and an accurate estimate of the real airbag volume is extracted. </p><p>Even though volume estimates can be computed for all camera setups, the cameras should be specially posed to achieve optimal results. Such poses are uniquely found for different airbag models with a separate, fully automatic, simulated annealing algorithm.</p><p>Satisfying results are presented for both synthetic and real-world data.</p>