It can be difficult to quickly and easily create realistic sandstone terrain. Film makers often need to generate realistic terrain for establishing the setting of their film. Many methods have been created which address terrain generation. One such method is using heightmaps which encode height as a gray-value in a 2d image. Most terrain generation techniques don't admit concavities such as overhangs and arches. We present an algorithm that operates on a voxel grid for creating 3d terrain. Our algorithm uses curvature estimation to weather away the terrain. We speed up our method using a caching mechanism that stores the curvature estimate. We generate piles of colluvium, the broken away pieces of weathered rock, with a simple deposition algorithm to improve the realism of the terrain. We explore the possibility of generating our sandstone terrain on the GPU using OpenCL. With our algorithm, an artist is able to quickly and easily create 3d terrain with concavities and colluvium.

Synthetically generated terrain models are useful across a broad range of applications, including computer generated art & animation, virtual reality and gaming, and architecture. Existing algorithms for terrain generation suffer from a number of problems, especially that of being limited in the types of terrain that they can produce and of being difficult for the user to control. Typical applications of synthetic terrain have several factors in common: first, they require the generation of large regions of believable (though not necessarily physically correct) terrain features; and second, while real-time performance is often needed when visualizing the terrain, this is generally not the case when generating the terrain. In this thesis, I present a new, design-by-example method for synthesizing terrain height fields. In this approach, the user designs the layout of the terrain by sketching out simple regions using a CAD-style interface, and specifies the desired terrain characteristics of each region by providing example height fields displaying these characteristics (these height fields will typically come from real-world GIS data sources). A height field matching the user's design is generated at several levels of detail, using a genetic algorithm to blend together chunks of elevation data from the example height fields in a visually plausible manner. This method has the advantage of producing an unlimited diversity of reasonably realistic results, while requiring relatively little user effort and expertise. The guided randomization inherent in the genetic algorithm allows the algorithm to come up with novel arrangements of features, while still approximating user-specified constraints.

Video game characters must almost always be able to travel from point A to point B and this task can be solved in various ways. There exist grid maps, waypoints, mesh navigation and hierarchical techniques to solve this problem. On randomly generated terrain we make use of automatically generated waypoints to solve pathfinding queries. The waypoints are connected by edges to create a waypoint graph and the graph can be used in real time pathfinding for a single agent in a static environment. This is done by finding the vertices of the blocked triangles from the terrain and place a waypoint on each. We make use of the GPU to create the waypoint graph. The waypoints are connected by utilizing a serialized GPU quad tree to find the relevant blocked geometry to do a line-triangle intersection test. If a line between two waypoints do not intersect any blocked geometry the connection is valid and stored. We found out that it is possible to generate a waypoint graph during the startup of the game with acceptable time results, make use of such a graph for real time pathfinding and that players perceive the paths generated by the algorithm as realistic and responsive. Our conclusion is that our solution is well suited for a deterministic environment with agents of the same size.

Context. Procedural Terrain Generation refers to the algorithmical creation of terrains with limited or no user input. Terrains are an important piece of content in many video games and other forms of simulations. Objectives. In this study a tile-based approach to creating endless terrains is investigated. The aim is to find if real-time performance is possible using the proposed method and possible performance increases from utilization of the GPU. Methods. An application that allows the user to walk around on a seemingly endless terrain is created in two versions, one that exclusively utilizes the CPU and one that utilizes both CPU and GPU. An experiment is then conducted that measures performance of both versions of the application. Results. Results showed that real-time performance is indeed possible for smaller tile sizes on the CPU. They also showed that the application benefits significantly from utilizing the GPU. Conclusions. It is concluded that the tile-based approach works well and creates a functional terrain. However performance is too poor for the technique to be utilized in e.g. a video game.

Context. Triangulated irregular network (TIN) can produce terrain meshes with a reduced triangle count compared to a regular grid. At the same time, TIN meshes are more challenging to optimize in real-time in comparison to other approaches. Objectives. This thesis explores efficient generation of view-dependent, adaptive TIN meshes for terrain during runtime with no or minimal preprocessing. Methods. Since the workings of the proposed technique is a novel approach, an empirical strategy was employed to present the findings instead of partial comparisons to related techniques. Results. To determine the result of the technique, run-time performance is measured and presented to provide incentives for implementation and improvements on the proposed algorithm. Several problem sizes are tested with varying terrain features to determine the effectiveness as a result of the features in the mesh.  Conclusions. We conclude that reducing the problem of mesh simplification to that of 2D Delaunay triangulation on sampled points spanning terrains is valid approach for triangulating on-the-fly. Moreover, this approach opens up for further improvements which may soon allow real-time triangulation of TINs.

A procedural method is proposed to generate volumetric data for terrain using a surface height map and information about materials as input. In contrast to previous explored methods this approach takes advantage of the extensive research on surface terrain generation by adapting the material layers to the topology of the input terrain. The method allows the user to specify materials as stratified or eroded, which are generated differently: stratified materials are stacked to generate material layers while eroded materials accumulate on even terrain. We compare a thermal erosion method and an original approach that uses information about the slope of the terrain as a shortcut to generate eroded layers and performs significantly better. The advantages and drawbacks of each technique are explored and discussed. / En proceduell metod har framställts för att generera volymdata för terränger med hjälp av en höjdkarta samt information om terrängens material. Till skillnad från tidigare metoder har följande nyttjat den omfattande forskningen kring genererad terräng. Det här genom att anpassa materialens lager till terrängens topologi. Metoden tillåter användaren att specifiera materialen som stratifierade eller eroderade, vilket genereras olika: stratifierat material staplas och generar på så vis materialen i lager, medan eroderat material samlas på jämn terräng. Vi jämför en termisk erosionsmetod med originellt tillvägagångssätt som nyttjar användarinformation om terrängens lutning som en genväg till att generera eroderade lager samt presterar signifikant bättre. Fördelar samt nackdelar med båda teknikerna utforskas och diskuteras.

Delaunay refinement is a mesh triangulation method with the goal of generating well-shaped triangles to obtain a valid Delaunay triangulation. In this thesis, an approach of using this method for meshing continuous height field terrains is presented using Perlin noise as the height field. The Delaunay approach is compared to grid-based meshing to verify that the theoretical time complexity O(n log n) holds and how accurately and deterministically the Delaunay approach can represent the height field. However, even though grid-based mesh generation is faster due to an O(n) time complexity, the focus of the report is to find out if Delaunay refinement can be used to generate meshes quick enough for real-time applications. As the available memory for rendering the meshes is limited, a solution for providing a cohesive mesh surface is presented using a hole filling algorithm since the Delaunay approach ends up leaving gaps in the mesh when a chunk division is used to limit the total mesh count present in the application. The methods were implemented in the programming language C++ using the open source library libnoise to generate the Perlin noise and the off-the-shelf solution CGALmesh provided a Delaunay refinement implementation. The video game engine Unity was used to render the output meshes created by the Delaunay and grid approach by interfacing with C++ via a Windows DLL. The time complexity of Delaunay refinement was verified to hold, although it was not possible to draw any conclusions regarding the Delaunay refinement's impact on the mesh's accuracy due to the test parameters used. It was also found that the CGALmesh implementation failed to provide a deterministic generation which is a significant drawback compared to the grid-based approach. Disregarding this, the Delaunay approach was found to be suitable for real-time applications as the generation time took less than 1 second, and is promising for volumetric terrain mesh generation. / Delaunay-raffinemang är en trianguleringsmetod med målet att generera reguljära trianglar för att uppnå en giltig Delaunay-triangulering. I denna avhandling presenteras en metod användandes Delaunay-raffinemang för att skapa polygonytor av kontinuerliga höjdfältsterränger, där Perlin noise används som höjdfält. Delaunay-metoden jämförs med en rutnätsbaserad metod för att verifiera att tidskomplexiteten O(n log n) gäller och hur exakt och deterministiskt som Delaunay-metoden förhåller sig till att representera höjdfältet. Även fast rutnätsmetoden är snabbare på grund av en O(n) tidskomplexitet är rapportens fokus att ta reda på om Delaunay-raffinemang är snabb nog för att användas i realtidsapplikationer för att generera polygonytor. Eftersom det tillgängliga minnet för att rendera polygonytorna är begränsat presenteras en lösning för att få sammanhängande ytor genom en hålutfyllningsalgoritm då Delaunaymetoden lämnar hål i ytan när chunk-uppdelning används för att begränsa det totala antalet polygonytor i applikationen. Metoderna implementerades i programmeringsspråket C++ användades biblioteket libnoise för att generera Perlin noise och den färdiga lösningen CGALmesh användes som implementation av Delaunay-raffinemang. Datorspelsmotorn Unity användes för att rendera polygonytorna som skapades av Delaunay- och rutnätsmetoden genom ett C++-gränssnitt via en Windows DLL. Tidskomplexiteten av Delaunay-raffinemang gällde, men det var inte möjligt att dra några slutsatser gällande hur exakt metoden förhållde sig till höjdfältet på grund av testparametrarna som användes. Ytterligare visade det sig att CGALmesh-implementationen var oförmögen att deterministiskt generera ytorna vilket är en stor nackdel jämfört med rutnätsmetoden. Bortsett från detta så visade sig Delaunay-metoden användbar för realtidsapplikationer då generingstiden tog mindre än 1 sekund, och metoden har dessutom potential för volymetrisk terränggenerering.

<p>To be able to run a flight simulator a large area of terrain needs to be visualized. The simulator must update the screen in real-time to make the simulation work well. One way of managing large terrains is to tile the area into quadratic tiles to be able to work with different detailed representations of the terrain at different distances from the user. The tiles need to match with the adjacent tiles in the edge points to avoid cracks. When every tile can have a number of different levels of detail this means that the different levels of detail need to match too. This was previously done by having the same edge points in all levels of detail, giving an unnicessarily large polygon count in the less detailed levels. the method developed in this report uses different versions of borders with their own level of detail, adapting to different detail levels at the adjacent tile, reducing hte number of polygons.</p>

To be able to run a flight simulator a large area of terrain needs to be visualized. The simulator must update the screen in real-time to make the simulation work well. One way of managing large terrains is to tile the area into quadratic tiles to be able to work with different detailed representations of the terrain at different distances from the user. The tiles need to match with the adjacent tiles in the edge points to avoid cracks. When every tile can have a number of different levels of detail this means that the different levels of detail need to match too. This was previously done by having the same edge points in all levels of detail, giving an unnicessarily large polygon count in the less detailed levels. the method developed in this report uses different versions of borders with their own level of detail, adapting to different detail levels at the adjacent tile, reducing hte number of polygons.

This thesis describes the implementation and evaluation of a modular approach for generating 2D side-scroller game levels from a procedurally generated 3D world. Manually generating large amounts of game levels can take considerable amounts of time, and it maybe desirable to automate this process, using procedural content generation. The problem with using procedural content generation is that it is hard to generate coherent game levels. We implement a modular pipeline which, given a set of heightmaps, generates a 3Dworld. From this world, 2D game levels are generated by pathing and extracting terrain features which influence the content in the game levels. The resulting 2D game levels will, using our approach, have a coherent and logical look. The game levels themselves do not contain any interesting gameplay. Instead they rely on a game level designer to add gameplay elements. The resulting modular implementation is considered a success, it proves that it is possible to generate 2D game levels from a procedurally generated 3Dworld, using the features of that world.