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.

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.