Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Parallel Construction of Local Clearance Triangulations
Blekinge Tekniska Högskola, Fakulteten för datavetenskaper, Institutionen för datavetenskap.
Blekinge Tekniska Högskola, Fakulteten för datavetenskaper, Institutionen för datavetenskap.
2019 (engelsk)Independent thesis Advanced level (degree of Master (One Year)), 20 poäng / 30 hpOppgave
Abstract [en]

The usage of navigation meshes for path planning in games and otherdomains is a common approach. One type of navigation mesh that recently has beendeveloped is the Local Clearance Triangulation (LCT). The overall aim of the LCT isto construct a triangulation in such a way that a property called theLocal Clearancecan be used to calculate a path in a more efficient and cheap way. At the time ofwriting the thesis there only exists one solution that creates an LCT, this solution isonly using the CPU. Since the process of creating an LCT involves the insertion ofmany points and edge flips which only affects a local area it would be interesting toinvestigate the potential performance gain of using the GPU.

The objective of the thesis is to develop a GPU version based on thecurrent CPU LCT solution and to investigate in which cases the proposed GPU al-gorithm performs better.

A GPU version and a CPU version of the proposed algorithm has beendeveloped to measure the performance gain of using the GPU, there are no algorith-mic differences between these versions. To measure the performance of the algorithmtwo tests have been constructed, the first test is called the Object Insertion test andmeasures the time it takes to build an LCT using generated test maps. The sec-ond test is called the Internal test and measures the internal performance of thealgorithm. A comparison between the GPU algorithm with an LCT library called Triplanner was also done.

The proposed algorithm performed better on larger maps when imple-mented on a GPU compared to a CPU implementation of the algorithm. The GPU performance compared to the Triplanner was faster in some of the larger maps.

An algorithm that builds an LCT from scratch is presented. Theresults show that using the proposed algorithm on the GPU substantially increasesthe performance of the algorithm compared to when implementing it on a CPU.

sted, utgiver, år, opplag, sider
2019.
Emneord [en]
LCT, GPGPU, GPU, Navmesh
HSV kategori
Identifikatorer
URN: urn:nbn:se:bth-18895OAI: oai:DiVA.org:bth-18895DiVA, id: diva2:1369203
Fag / kurs
Degree Project in Master of Science in Engineering 30,0 hp
Utdanningsprogram
PAACI Master of Science in Game and Software Engineering
Veileder
Examiner
Tilgjengelig fra: 2019-11-11 Laget: 2019-11-11 Sist oppdatert: 2019-11-11bibliografisk kontrollert

Open Access i DiVA

fulltext(947 kB)6 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 947 kBChecksum SHA-512
8d9cb92602887aa2a0011b7375b454ae5034c540d9b2cc2c0413da2bfb65b0ce7bb4812e8efeb115e5ef42eda887379b2e7cd9bf9635b82f4b089c89fc4f0155
Type fulltextMimetype application/pdf

Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 6 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 126 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf