Abstract: Relief mapping is an image based technique for rendering surface details. It simulates depth on a polygonal model using a texture that encodes surface height. The presented method incorporates a quadtree structure to achieve a theoretically proven performance between W(log(p)) and O(pp) for computing the first intersection of a ray with the encoded surface, where p is the number of pixels in the used texture. In practice, the performance was found to be close to log(p) in most cases. Due to the hierarchical nature of our technique, the algorithm scales better than previous comparable techniques and therefore better accommodates to future games and graphics hardware. As the experimental results show, quadtree relief mapping is more efficient than previous techniques when textures larger than 512×512 are used. The method correctly handles self-occlusions, shadows, and irregular surfaces.