Scalable Height Field Self-Shadowing
Abstract
We present a new method suitable for general purpose graphics processing units to render self-shadows on dynamic height fields under dynamic light environments in real-time. Visibility for each point in the height field is determined as the exact horizon for a set of azimuthal directions in time linear in height field size and the number of directions. The surface is shaded using the horizon information and a high-resolution light environment extracted on-line from a high dynamic range cube map, allowing for detailed extended shadows. The desired accuracy for any geometric content and lighting complexity can be matched by choosing a suitable number of azimuthal directions. Our method is able to represent arbitrary features of both high- and low-frequency, unifying hard and soft shadowing. We achieve 23 fps on 1024x1024 height fields with 64 azimuthal directions under a 256x64 environment lighting on an Nvidia GTX 280 GPU.
Material
Full paper, 1.6 MB, 9 pagesComputer Graphics Forum (Proc. Eurographics Conference 2010)
Bibtex reference
Algorithm 1 pseudocode under MIT
Higher resolution paper images:
uniform lighting (1.2 MB)
hard and soft shadows (2.3 MB)
lighting resolution (3.7 MB)
azimuthal directions (7.1 MB)
2048x2048 terrain (2.8 MB)
Conference presentation slides, 18 MB
Screen captures
Video demonstration
Make sure to watch in HDDownload the video (.mov, h264, 1080p24) 357 MB.
Author's comments
Background
In the beginning of 2009 I got interested in ambient occlusion methods. Motivated by screen-space ambient occlusion that had recently gained high popularity in real-time computer graphics, I started to figure out ways to properly light geometry described via height maps (as the existing SSAO methods were approximative). What also bothered me with the existing methods was that it was obvious to me that they were doing redundant work.
After giving up on my first approach with image manipulation based methods, I focused my efforts on solving the problem geometrically. That path didn't seem so fundamentally doomed, and I started to get some decent results after a while. I had a crude proof-of-concept CPU implementation, and it was time to make it run fast. Following my perfectionist nature, I spent way too much time on figuring out the most efficient way possible to implement the algorithm using CUDA (implementation was not possible using traditional shader programs).
Then at one point, I found a recent paper (first-authored by a principal researcher at Microsoft) where an algorithm had been developed to solve the problem I had been working on. I was so mortified that I hadn't done my background research properly enough to find it earlier. However, I started to realize that although the Microsoft's method was the current state-of-the-art, it was far slower than the algorithm I had and it made approximations of the geometry that I didn't have to make.
The algorithm finalizes
When I knew I had to write a paper of some kind about the algorithm, I started to figure out scientific argumentation and quantification for it. Then it hit me: my algorithm solved a common visibility problem in O(n2) time whereas the literature so far only had to offer O(n3) solutions to the problem! Things started to clear up and it was now easy to argue why orders-of-magnitude speed-ups were possible over the existing methods.
When I presented proof of this to my supervisor, he thought I should submit the paper to Eurographics, whose deadline was a couple months ahead. Knowing that the conference was hardcore and had a very low acceptance rate, and that this was my first real paper, I thought "yeah, I guess we could try, but I'm not holding my breath."
Also, at this point, we decided that a large portion of the research I had done would not belong to this paper as the time complexity point alone would be enough and needed no further obscuration. Instead, I decided to hurry up and implement an idea for lighting I had had all along, as it would go well with the visibility algorithm.
All went well, and after another while I had a solution to light high-resolution height fields under high-resolution HDR cube light maps. It took over 12k lines of mostly CUDA code. And it wasn't the kind of code you write hundreds of lines a day -- for most parts I had even analyzed the clock cycles the operations would take, and some parts had hand-tuned PTX assembly. (I was to realize later that going that deep with the implementation is not really worth the time for a scientific paper.)
Results
I worked my ass off to get the paper written before the deadline, and the day of the deadline it was finally done, and I was actually very happy with it. Of course, it was my first time doing something like that and I had no way of estimating whether I had good chances of getting it accepted. Knowing that the conference is the second most respected forum in the whole of computer graphics, I already started to think what to do when it would get rejected.
At this point our laboratory was consulted by CSC for an article they were writing for MikroPC (a popular finnish computer magazine). The article was about GPGPU technology, and in addition to statements, they asked if we had some examples they could use in the article. We decided to give a screen capture of the algorithm I had made, but I wasn't sure it would even end up in the article. When the article got published, I was surprised to see it occupying half of the first page (see the actual article page here).
A few weeks later came the reviewers' comments from Eurographics. There were 5 reviewers and I couldn't believe what they had to say about the paper!
The use of ''marching convex hull'' for height field self-shadowing is a simple, clever, and elegant idea I wish I had thought of. It makes all-frequency self-shadowing possible for high-resolution height fields in real-time. I am very enthusiastic in recommending that this paper be accepted.
The paper has clear contributions that significantly improve the state of the art in height field illumination. I definitely want to see this paper being published at Eurographics.
Use of the incremental convex hull along an azimuthal direction is very clever and a beautiful contribution.
The resulting rendering solution has a significantly lower computational complexity than previous methods and is considered a significant contribution to the field.
Moreover, as a data representation, height fields play an important role, and I can see many applications for the presented visibility computation on dynamic height fields that are not even related to rendering. Overall, I believe that this is a high-impact paper.
So all-in-all the paper is a nice advance in the state of the art and about the nicest single gem of an idea I've seen recently.
Needless to say, I was ecstatic. My work had finally paid off.
See you at Eurographics Conference 2010 :-)
