Efficient Intersection of Terrain Geometry in Real-Time Applications

Examensarbete på grundnivå

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/250170
Download file(s):
File Description SizeFormat 
250170.pdfFulltext928.55 kBAdobe PDFView/Open
Type: Examensarbete på grundnivå
Title: Efficient Intersection of Terrain Geometry in Real-Time Applications
Authors: SJÖSTRAND, TIM
Abstract: n interactive computer graphics applications it is often desirable to draw some form of terrain; ground planes with visually interesting features such as valleys and hills. These are typically stored as a height map image file and converted into a collection of triangles at run-time. When such geometry is used it soon becomes necessary to calculate the intersection point of a ray through the geometry, most notably to map user cursor interaction into 3D space. However, such calculations scale poorly with the number of triangles generated from very large height maps. The traditional optimization has been to reduce the number of calculations required by utilizing a quadtree data structure to search the height map and discard triangles that do not lie inside quadtree leaf nodes along the path of the ray. This paper introduces an extension of this optimization by projecting the line through quad tree leaf nodes onto the height map plane, reducing the number of calculations by a considerable amount. Our testing of a worst-case scenario suggests improvements in calculation speed of about 50x compared to the traditional optimization, which should be interesting for anyone implementing 3D terrain based on a height map.
Keywords: Informations- och kommunikationsteknik;Data- och informationsvetenskap;Information & Communication Technology;Computer and Information Science
Issue Date: 2017
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
URI: https://hdl.handle.net/20.500.12380/250170
Collection:Examensarbeten på grundnivå // Basic Level Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.