In English

Efficient Intersection of Terrain Geometry in Real-Time Applications

TIM SJÖSTRAND
Göteborg : Chalmers tekniska högskola, 2017. 25 s.
[Examensarbete på grundnivå]

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.

Nyckelord: 3D Graphics, Intersection Algorithm, Terrain, Ray, Heightmap, Quadtree



Publikationen registrerades 2017-06-28. Den ändrades senast 2017-06-28

CPL ID: 250170

Detta är en tjänst från Chalmers bibliotek