Quick Cone Map Generation on the GPU

Abstract

We propose an efficient conservative cone map generation algorithm that has T(N^2 logN) complexity for textures of dimension N ×N in contrast to the T(N^4) complexity of brute-force approaches. This is achieved by using a maximum mip texture of a heightmap to process all texels during the search for cone apertures, resulting in real-time generation times. Furthermore, we show that discarding already visited regions of neighboring mip texels widens the obtained cones considerably while still being conservative. Finally, we present a method to increase cone aperture tangents further at the expense of conservativeness. We compare our methods to brute-force and relaxed cone maps in generation and rendering performance.