Background: Recreating nature in a virtual environment comes with many aspects and challenges. Grass rendering is a part of this area, and both performance and visual results must be taken into consideration. A common optimization approach is through static level-of-detail (LOD), however, a certain visual loss comes with the use of this. Dynamic LOD is an alternative technique and exists in various forms, such as phong tessellation. The thesis will investigate the performance and visual implications of utilizing phong tessellation in grass rendering. Objectives: The main objective is to examine the implications of utilizing phong tessellation in grass rendering in terms of performance and visual results. Different scenarios will be examined, providing an overview while identifying performance and visual patterns of the technique. Methods: An experiment conducted via a DirectX 11 implementation was used to collect all data in scenarios that varied in the number of blades and how the tessellation falloff rate was described. The data collected was the average frame time during a 30-second duration as well were rendered images saved to disk from two points of view. Two reference scenes existed that only used a single LOD of either low- or high-quality grass, while no tessellation was applied. The data of each scenario and scene were compared to one another, and the visual differences were identified using the image difference evaluator FLIP. Results: The results show that different scenarios provide different benefits. Some scenarios contain smaller visual errors, while others perform efficiently. Overall a linear detail-falloff rate both performs well at various blade amounts and produces similar or smaller visual differences to the other scenarios. However, the results also show that the technique does not fit every set of hardware, at least not in demanding scenarios. Conclusions: The findings of this thesis show that the method has the potential to be a valid option in terms of performance and visual quality. It is, however, important to consider the specific use case as it is not applicable in every situation and to consider what hardware the application will run on.

This work evaluates a specific origami device known as the kaleidocycle and the broad classof rigidly foldable origami. Both of these have potential for application in the design of deployableand foldable arrays of spatial mechanisms.Origami is considered a compliant mechanisms because it achieves its motion through thedeflection of paper creases. Compliant mechanisms generally do not allow for continuous rotation;however, the compliant kaleidocycle represents an exception to this generality. Along with theirability to rotate continuously, kaleidocycles may also be designed to exhibit multistable behaviorduring this rotation. These two characteristics make the kaleidocycle an interesting device withpotential for applications in engineering. This work presents the multistable characteristics ofkaleidocycles, showing that devices can be made which exhibit one, two, three, or four distinctstable equilibrium positions. Kaleiocycles may also be designed to exhibit a range over which thedevice is neutrally stable.The second type of origami presented in this work is rigidly foldable origami, a special classof origami in which all deflection occurs at the creases, allowing the panels to remain rigid. Thistype of origami is of particular interest because of its ability to be constructed from materials muchstiffer than paper while retaining its mobility. This property allows rigidly foldable origami to beapplied to fields such as architecture and deployable mechanisms. This work presents a method forevaluating rigid foldability in origami tessellations. This method is used to define seven theoremsfor the rigid foldability of origami twists and to develop new rigidly foldable origami “gadgets”and tessellations.

Background. Rendering planets with high detail from orbit to surface level is becoming increasingly common in video games. In this thesis, two solutions to achieving this will be compared, a quadtree solution and a tessellation solution. These solutions both implement an adaptive level of detail on a spherical shape. The quadtree solution uses six quadtrees to construct the planetary terrain mesh on the CPU with higher detail closer to the viewer. The tessellation solution uses the GPU to subdivide areas of a basic low-resolution model to achieve higher levels of detail close to the viewer. Objectives. Related work that has implemented these solutions uses old hardware and there is a lack of performance data on these solutions running on modern hardware. The objective of this project is to provide performance data and a comparison between the quadtree solution and the tessellation solution on modern hardware. This comparison will include a discussion of the negative and positive performance aspects of the two solutions. Methods. The two solutions will be implemented to create two similar-looking applications with a focus on only the technical aspects of rendering a globe mesh with each of these solutions. The frame time both on the CPU and on the GPU will be measured for each solution. The measurements will be taken at four different distances from the globe, meaning four different levels of detail. Due to a limitation of tessellation, this solution has to be provided with a higher resolution base model to achieve similar detail levels at the surface level. Results. The results show the quadtree frame time increasing with measurements taken closer to the surface of the globe. The tessellation results show a larger performance impact, though this is due to the base globe mesh being swapped for a higher-resolution model. Conclusions. The result suggests that the tessellation solution performs worse, however, the tessellation solution still shows little to no performance loss when comparing frame time measured on the same base mesh, even though the detail difference between them is high. The quadtree solution has an overall better performance and provides more control over the detail levels. The lack of control over the detail levels in the tessellation solution means that the detail level can not be matched exactly, which leads to the tessellation solution giving a richer topology.

Au cours des deux dernières décennies, les applications temps réel ont montré des améliorations colossales dans la génération de rendus photoréalistes. Cela est principalement dû à la disponibilité de modèles 3D avec une quantité croissante de détails. L'approche traditionnelle pour représenter et visualiser des objets 3D hautement détaillés est de les décomposer en un maillage basse fréquence et une carte de déplacement encodant les détails. La tessellation matérielle est le support idéal pour implémenter un rendu efficace de cette représentation. Dans ce contexte, nous proposons une méthode générale pour la génération et le rendu de maillages multi-résolutions compatibles avec la tessellation matérielle. Tout d'abord, nous introduisons une métrique dépendant de la vue capturant à la fois les distorsions géométriques et paramétriques, permettant de sélectionner la le niveau de résolution approprié au moment du rendu. Deuxièmement, nous présentons une nouvelle représentation hiérarchique permettant d'une part des transitions temporelles et spatiales continues entre les niveaux et d'autre part une tessellation matérielle non uniforme. Enfin, nous élaborons un processus de simplification pour générer notre représentation hiérarchique tout en minimisant notre métrique d'erreur. Notre méthode conduit à d'énormes améliorations tant en termes du nombre de triangles affiché qu'en temps de rendu par rapport aux méthodes alternatives. / In the last two decades, real-time applications have exhibited colossal improvements in the generation of photo-realistic images. This is mainly due to the availability of 3D models with an increasing amount of details. Currently, the traditional approach to represent and visualize highly detailed 3D objects is to decompose them into a low-frequency mesh and a displacement map encoding the details. The hardware tessellation is the ideal support to implement an efficient rendering of this representation. In this context, we propose a general framework for the generation and the rendering of multi-resolution feature-aware meshes compatible with hardware tessellation. First, we introduce a view-dependent metric capturing both geometric and parametric distortions, allowing to select the appropriate resolution at rendertime. Second, we present a novel hierarchical representation enabling on the one hand smooth temporal and spatial transitions between levels and on the other hand a non-uniform hardware tessellation. Last, we devise a simplification process to generate our hierarchical representation while minimizing our error metric. Our framework leads to huge improvements both in terms of triangle count and rendering time in comparison to alternative methods.

In 1961, P. W. Kasteleyn provided a baffling-looking solution to an apparently simple tiling problem: how many ways are there to tile a rectangular region with dominos? We examine his proof, simplifying and clarifying it into this nearly self-contained work.

Physically-driven methods of simulating fluid dynamics and frequency-based ocean surface synthesis methods are of long-standing interest for the field of computer graphics. However, they have been historically used separately or without any interaction between them. This thesis focuses on the possibility of combining the approaches into one adaptive solution by proposing methods for unified surface representation, method result blending and one-way interaction between the methods. The thesis also outlines several future developments of the combined method and proposes a level-of-detail approach taking advantage of hardware tessellation that can be used regardless of what method was used for the simulation. Powered by TCPDF (www.tcpdf.org)

This work deals with the description and analysis of image data, which related to the initial stages of the thin film growth. The introductory retrieval section includes a description of thin films and methods of their deposition. The following part is an overview of the growth models of thin layers. The heart of my thesis is the analysis and modification of morphological methods and interpretation of their results. The emphasis is placed on the statistical aspect of methods and their optimal implementation due to the accuracy of the results. The work shows how to modify the radial distribution function and methods based on so-called Voronoi and Delaunay triangulation tessellation so that they can better affect the character of test data. New methods are tested both on the experimental and model data. Then we examine their robustness, sensitivity and their mutual independence. At the conclusion it is introduced and analyzed a new model of thin film growth.

Bobbin lace is a 500-year-old art form in which threads are braided together in an alternating manner to produce a lace fabric. A key component in its construction is a small pattern, called a bobbin lace ground, that can be repeated periodically to fill a region of any size. In this thesis we present a mathematical model for bobbin lace grounds representing the structure as the pair (Δ(G), ζ (v)) where Δ(G) is a topological embedding of a 2-regular digraph, G, on a torus and ζ(v) is a mapping from the vertices of G to a set of braid words. We explore in depth the properties that Δ(G) must possess in order to produce workable lace patterns. Having developed a solid, logical foundation for bobbin lace grounds, we enumerate and exhaustively generate patterns that conform to that model. We start by specifying an equivalence relation and define what makes a pattern prime so that we can identify unique representatives. We then prove that there are an infinite number of prime workable patterns. One of the key properties identified in the model is that it must be possible to partition Δ(G) into a set of osculating circuits such that each circuit has a wrapping index of (1,0); that is, the circuit wraps once around the meridian of the torus and does not wrap around the longitude. We use this property to exhaustively generate workable patterns for increasing numbers of vertices in G by gluing together lattice paths in an osculating manner. Using a backtracking algorithm to process the lattice paths, we identify over 5 million distinct prime patterns. This is well in excess of the roughly 1,000 found in lace ground catalogues. The lattice paths used in our approach are members of a family of partially directed lattice paths that have not been previously reported. We explore these paths in detail, develop a recurrence relation and generating function for their enumeration and present a bijection between these paths and a subset of Motzkin paths. Finally, to draw out of the extremely large number of patterns some of the more aesthetically interesting cases for lacemakers to work on, we look for examples that have a high degree of symmetry. We demonstrate, by computational generation, that there are lace ground representatives from each of the 17 planar periodic symmetry groups. / Graduate / 0389 / 0984 / 0405 / veronikairvine@gmail.com

Voronoi tessellation can be used within a couple of different fields. Some of these fields include healthcare, construction and urban planning. Since Voronoi tessellations are used in multiple fields, it is motivated to know the strengths and weaknesses of the algorithms used to generate them, in terms of their efficiency. The objectives of this thesis are to compare two CPU algorithm implementations for Voronoi tessellation in regards to execution time and see which of the two is the most efficient. The algorithms compared are The Bowyer-Watson algorithm and Fortunes algorithm. The Fortunes algorithm used in the research is based upon a pre-existing Fortunes implementation while the Bowyer-Watson implementation was specifically made for this research. Their differences in efficiency were determined by measuring their execution times and comparing them. This was done in an iterative manner, where for each iteration, the amount of data to be computed was continuously increased. The results show that Fortunes algorithm is more efficient on the CPU without using any acceleration techniques for any of the algorithms. It took 70 milliseconds for the Bowyer-Watson method to calculate 3000 input points while Fortunes method took 12 milliseconds under the same conditions. As a conclusion, Fortunes algorithm was more efficient due to the Bowyer-Watson algorithm doing unnecessary calculations. These calculations include checking all the triangles for every new point added. A suggestion for improving the speed of this algorithm would be to use a nearest neighbour search technique when searching through triangles.

An isohedral tiling is a tiling of congruent polygons that are also transitive, which is to say the configuration of degrees of vertices around each face is identical. Regular tessellations, or tilings of congruent regular polygons, are a special case of isohedral tilings. Viewing these tilings as graphs in planes, both Euclidean and non-Euclidean, it is possible to pose various problems of enumeration on the respective graphs. In this paper, we investigate some near-regular isohedral tilings of triangles and quadrilaterals in the hyperbolic plane. For these tilings we enumerate vertices as classified by number of edges in the shortest path to a given origin, by combinatorially deriving their respective generating functions.