Fun With Horizon Maps

Hello folks! How are your molecules doing?

Introduction

Back in the day, in a forgotten time, I was totally immersed in J.R.R. Tolkien’s Eä. I would always try to imagine the landscapes and scenes described in his books - you know, Tolkien gave descriptions of everything. Really, everything. From all the written details he gave, something always caught my attention: the duality present between light and dark.

A great implementation of this concept is the Battle for Wesnoth day/night cycle - lawful vs chaotic units. Besides being a great game, it also has some really great storytelling. Also, it is Open Source!

Being a nerd, choosing a fantasy/sci-fi (… and metal) background was an obvious course of action when developing the first demo of my beloved engine. I would need to reference something I like (I always do this) and the idea of an island was already in my mind, maybe because of the Crash Bandicoot 1 map, IDK!

During the first days of development, I was on a Megadeth marathon and stumbled upon the song Devil’s Island from the Peace Sells… but Who’s Buying? album. The moment I heard the song I thought: Snap! Got my theme. After some research, I also discovered that Star Trek TOS made some references to Devil’s Island. From this point on, I had no doubt about my demo theme: an island. And this was how my technical trip through the engine room started! Ask Garrus or Geordi if you don’t believe me!

So, in today’s wizardry trek, we talk about shadows and how I decided to use baked horizon maps. Whether it was a bad decision or not, I’ll only know for sure when I finish the demo. But for now, let’s take a trip through the land where the shadows lie.

Without further ado, let’s go!

Part I - Selecting a Shadowing Method

As you probably know, the standard method for rendering real-time shadows is Shadow Mapping [1]. And this was my first weapon of choice, but during my research for an atmospheric rendering solution I found a 2001 GDC paper [2] which used a technique called Horizon Mapping [3] as a pre-pass. I could have stuck to some filtering technique and just used SM instead of trying this algorithm, but the point in question was the possibility of just doing one baking pre-pass for the shadows and using it every time I ran the demo, even with a dynamic sun system. This seems like a big win, because I won’t have dynamic objects in the scene - just the water, but its change in height will be much smaller than the heightfield changes in slope, so the probability that the binary shadow function will change is very small. However, I haven’t tested this yet.

Thus, I decided to go with precomputed horizon-map shadows. This is an R&D situation: it may work or it may not. Either way, it is a learning opportunity and what matters is that in the end the demo will have a robust shadowing system; whether it will be horizon maps or shadow mapping is something that the project itself will tell.

Part II - Finding the Horizon Angles using the DDA Method

The construction process of the horizon map, a.k.a. the baking, is very simple: we ray-march in all 8 possible directions in our heightmap - like in a compass rose - and store the minimum horizon angle necessary so the specific point is visible in the selected direction. Nothing new here, just the old DDA method [4]! Look at the figure below:

So, how do we do that? First, assume we are at a point $P(x,y)$ in our heightmap. Then, the question we want to ask is the following: What is the minimum angle the sun must do with the horizon line so it can see me? We must answer that question for each of the 8 possible directions.

For each direction, we do the following: ray-march from the current starting point $P(x,y)$ to a new point, let’s call it $P(x,y)_i$. Then, check the angle formed by the vector going from $P(x,y)$ to $P(x,y)_i$ and the horizon vector; the horizon vector is just the projection of the vector onto the x,y plane. If this angle is greater than the current angle $\phi$, update the horizon angle and iterate again. When the iteration completes, we will have the minimum horizon angle for the particular point. This shows the global nature of this algorithm, something expected, as shadows are a global phenomenon.

For a visual take on the algorithm, look at Figure 2 below:

Part III - Storing & Sampling the Horizon Map

The next phase is very simple, and it is more of a take on API settings than the algorithm per se. As we have 8 angles per texel, it is clear we can’t store a horizon map, without compression, using only one planar texture. There are 2 options to solve this that I am aware of: the first is to use 2 32-bit planar textures, and the second is to use a volume texture. You can argue for both sides depending on your situation. For me, 2 linear RGBA8 textures are simpler and work just fine; see Figure 3.

Now we have only one step to go: Sampling! As it turns out, this is another very easy step. We will only need 2 variables to sample the map: the sun radiance’s direction, a.k.a. directional light source, and the horizon angle at the moment of sampling.

Finally, project the directional vector on the xy plane and use its contents to select which of the 8 values will be accessed, for example, I used a CCW orientation on the compass rose. Then, if the sampled angle is greater than the sun’s horizon angle, the vertex/fragment is in shadow. That simple!

Well, that is it for today, folks! I hope this post helped you in some way. Live Long & Prosper! And until next time.

Results

An example of the algorithm in use is given in the figures below:

References

• [1] Lance Williams (1978). Casting curved shadows on curved surfaces ACM SIGGRAPH Computer Graphics
• [2] Naty Hoffman, Kenny Mitchell (2001). Real-Time Photorealistic Terrain Lighting. 2001 Game Developer Conference
• [3] Max, N. L. (1988). Horizon mapping: shadows for bump-mapped surfaces. The Visual Computer
• [4] John F. Hughes, James D. Foley, Andries van Dam, Steven K. Feiner Computer Graphics: Principles and Practice in C. Addison–Wesley