Efficient Intersection of Terrain Geometry in Real-Time Applications

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.