An approach of using Delaunay refinement to mesh continuous height fields

Abstract: 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.