Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
An approach of using Delaunay refinement to mesh continuous height fields
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2017 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
: En metod att använda Delaunay-raffinemang för att skapa polygonytor av kontinuerliga höjdfält (Swedish)
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
2017.
Keywords [en]
Delaunay, height field, height map, chunks, procedural terrain generation, topological surface
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-208391OAI: oai:DiVA.org:kth-208391DiVA, id: diva2:1106042
Supervisors
Examiners
Available from: 2017-06-19 Created: 2017-06-06 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

fulltext(5715 kB)55 downloads
File information
File name FULLTEXT01.pdfFile size 5715 kBChecksum SHA-512
4be9dac7cd716e735b0bd3c02a440d39cda8be7ad805a94236a89cd835f006fcf752ebbf85dad1527693179f32c48789ddecd580bd6dfe952810f0eba8585b72
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 55 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 75 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf