# Bump Mapping a Simple Surface

In my last post, I started discussing Bump Mapping and showed a mechanism through which we can generate a normal map from any diffuse texture. At the time, I signed off by mentioning next time I would show you how to apply a bump map on a trivial surface. This is what we are going to do today.

In the video above you can see the results of the effect we are trying to achieve. This video was generated from a GIF file created using the Vortex Engine. It clearly shows the dramatic lighting effect bump mapping achieves.

Although it may seem as if this image is composed of a detailed mesh of the boss’ head, it is in fact just two triangles. If you could see the image from the side, you’d see it’s completely flat! The illusion of curvature and depth is generated by applying per-pixel lighting on a bump mapped surface.

How does bump mapping work? Our algorithm will take as input two images: the diffuse map and the bump map. The diffuse map is just the colors of each pixel in the image, whereas the bump map consists in an encoded set of per-pixel normals that we will use to affect our lighting equation.

Here’s the diffuse map of the Boss door:

Diffuse map of the boss door. Image taken from the Duke3D HRP project.

And here’s the bump map:

Bump map of the boss door. Image taken from the Duke3D HRP project.

I’m using these images taken from the excellent Duke3D High Resolution Pack (HRP) for educational purposes. Although we could’ve generated the bump map using the technique from my previous post, this especially-tailored bump map will provide better results.

Believe it or not, there are no more input textures used! The final image was produced by applying the technique on these two. This is the reason I think bump mapping is such a game changer. This technique alone can significantly up the quality and realism of the images our renderers produce.

It is especially shocking when we compare the diffuse map with the final bump-mapped image. Even if we applied per-pixel lighting to the diffuse map in our rendering pipeline, the results would be nowhere close to what we can achieve with bump mapping. Bump mapping really makes this door “pop out” of its surface.

Bump Mapping Theory

The theory I develop in these sections is heavily based on the books Mathematics for 3D Game Programming and Computer Graphics from Eric Lengyel and More OpenGL from David Astle. You should check those books for the definitive reference on bump mapping. Here, I try to explain the concepts in simple terms.

So far, you might have noticed I’ve been mentioning that the bump map consists of the “deformed” normals that we should use when applying the lighting equation to the scene. But I haven’t mentioned how these normals are actually introduced into our lighting equations.

Remember from my previous post how we mentioned that normals are stored in the RGB image? Remember that normals close to (0,0,1) looked blueish? Well, that is because normals are stored in a coordinate system that corresponds to the image. This means that, unfortunately, we can’t just take each normal N and plug it into our lighting equation. If we call L the vector that takes each 3D point (corresponding to each fragment) to the light source, the problem here is that L and N are in different coordinate systems.

L is, of course, in camera or world space, depending on where you like doing your lighting math. But where is N? N is defined in terms of the image. That’s neither of those spaces.

Where is it then? Well, N is actually in its own coordinate system that authors refer to as “tangent space”. It’s its own coordinate system.

In order to apply per-pixel lighting using the normals coming from the bump map, we’ll have to bring all vectors to the same coordinate system. For bump mapping, we usually bring the L vector into tangent space instead of bringing all the normals back into camera/world space. It seems more convenient and should produce the same results.

Once L has been transformed, we will retrieve N from the bump map and use the Lambert equation between these two to calculate the light intensity at the fragment.

From World Space to Tangent Space

How can we convert from camera space to tangent space? Tangent space is not by itself defined in terms of anything that we can map to our mesh. So, we will have to use one additional piece of information to determine the relationship between these two spaces.

Given that our meshes are composed of triangles, we will assume the bump map is to be mapped on top of each triangle. The orientation will be given by the direction of the texture coordinates of the vertices that comprise the triangle.

This means that if we have a triangle that has an edge: (-1,1)(1,1) with texture coordinates: (0,1)(1,1), a horizontal vector (1,0) represents a vector tangent to the vertices that is aligned with the horizontal texture coordinates. We will call this the tangent.

Now, we need two more vectors in order to define the coordinate system. Well, the other vector we can use is the normal of the triangle. This vector is, by definition, perpendicular to the surface and will be perpendicular to the tangent.

The final vector we will use to define the coordinate system has to be perpendicular to both, the normal and the tangent, so we can calculate it using a cross product. There is an ongoing debate whether this vector should be called the “bitangent” or the “binormal” vector. According to Eric Lengyel the term “binormal” makes no sense from a mathematical standpoint, so we will refer to it as the “bitangent”.

Now that we have three vectors that define the tangent space, we can create a transformation matrix that takes vector L and puts it in the same coordinate system that the normals for that specific triangle. Doing this for every triangle will allow applying bump mapping on the triangle.

Responsibility – who does what

Although we can compute the bitangent and the transform matrix in our vertex shader, we will have to supply the tangent vectors as input to our shader program. Tangent vectors need to be calculated using the CPU, but (thankfully) only once. Once we have them, we supply them as an additional vertex array.

Calculating the tangent vectors is trivial for a simple surface like our door, but can become very tricky for an arbitrary mesh. The book Mathematics for 3D Game Programming and Computer Graphics provides a very convenient algorithm to do so, and is widely cited in other books and the web.

For our door, composed of the vertices:

(-1.0, -1.0, 0.0)
(1.0, -1.0, 0.0)
(1.0, 1.0, 0.0)
(-1.0, 1.0, 0.0)


Tangents will be:

(1.0, 0.0, 0.0)
(1.0, 0.0, 0.0)
(1.0, 0.0, 0.0)
(1.0, 0.0, 0.0)


Once we have the bitangents and the transformation matrix, we rotate L in the vertex shader, and pass it down to the fragment shader as a varying attribute, interpolating it over the surface of the triangle.

Our fragment shader can just take L, retrieve (and decode) N from the bump map texture and apply the Lambert equation on both of them. The rest of the fragment shading algorithm need not be changed if we are not applying specular highlights.

In Conclusion

Bump mapping is an awesome technique that greatly improves the lighting in our renderers at limited additional costs. Its implementation is not without a challenge, however.

Here are the steps necessary for applying the technique:

• After loading the geometry, compute the per-vertex tangent vectors in the CPU.
• Pass down the per-vertex tangents as an additional vertex array to the shader, along with the normal and other attributes.
• In the vertex shader, compute the bitangent vector.
• Compute the transformation matrix.
• Compute vector L and transform it into tangent space using this matrix.
• Interpolate L over the triangle as part of the rasterization process.
• In the fragment shader, normalize L.
• Retrieve the normal from the bump map by sampling the texture. Decode the RGBA values into a vector.
• Apply the Lambert equation using N and the normalized L.
• Finish shading the triangle as usual.

On the bright side, since this technique doesn’t require any additional shading stages, it can be implemented in both OpenGL and OpenGL ES 2.0 and run on most of today’s mobile devices.

In my next post I will show bump mapping applied to a 3D model. Stay tuned!

# Bump Map Generation

Bump mapping is a texture-based technique that allows improving the lighting model of a 3D renderer. I’m a big fan of bump mapping; I think it’s a great way to really make the graphics of a renderer pop at no additional geometry processing cost.

Bump mapping example. Notice the improved illusion of depth generated by the technique. Image taken from http://3dmodeling4business.com

Much has been written about this technique, as it’s widely used in lots of popular games. The basic idea is to perturb normals used for lighting at the per-pixel level, in order to provide additional shading cues to the eye.

The beauty of this technique is that it doesn’t require any additional geometry for the model, just a new texture map containing the perturbed normals.

This post covers the topic of bump map generation, taking as input nothing but a diffuse texture. It is based on the techniques described in the books “More OpenGL” by Dave Astle and “Mathematics for 3D Games And Computer Graphics” by Eric Lengyel.

Let’s get started! Here’s the Imp texture that I normally use in my examples. You might remember the Imp from my Shadow Mapping on iPad post.

Diffuse texture map of the Imp model.

The idea is to generate the bump map from this texture. In order to do this, what we are going to do is analyze the diffuse map as if it were a heightmap that describes a surface. Under this assumption, the bump map will be composed of the surface normals at each point (pixel).

So, the question is, how do we obtain a heightmap from the diffuse texture? We will cheat. We will convert the image to grayscale and hope for the best. At least this way we will be taking into account the contribution of each color channel for each pixel we process.

Let’s call H the heightmap and D the diffuse map. Converting an image to grayscale can be easily done programatically using the following equation:

$\forall (i,j) \in [0..width(D), 0..height(D)], H_{i,j} = red(D_{i,j}) * 0.33 + green(D_{i,j})* 0.66 + blue(D_{i,j}) * 0.11$

As we apply this formula to every pixel, we obtain a grayscale image (our heightmap), shown in the next figure:

A grayscale conversion of the Imp diffuse texture.

Now that we have our heightmap, we will study how the grayscale colors vary in the horizontal $s$ and in the vertical $t$ directions . This is a very rough approximation of the surface derivative at the point and will allow approximating the normal later.

If $H_{i,j}$ is the grayscale value stored in the heightmap at the point $(i,j)$, then we approximate the derivatives $s$ and $t$ like so:

$s_{i,j} = (1, 0, H_{i+1,j}-H_{i-1,j}) \\ t_{i,j} = (0, 1, H_{i, j+1}-H_{i,j-1})$

$s$ and $t$ are two vectors perpendicular to the heightmap at point $(i,j)$. What we can now do is take their cross product to find a vector perpendicular to both. This vector will be the normal of the surface at point $(i,j)$ and is, therefore, the vector we were looking for. We will store it in the bump map texture.

$N = \frac{s \times t}{||s \times t||}$

After applying this logic to the entire heightmap, we obtain our bump map.

We must be careful when storing a normalized vector in a texture. Because vector components will be in the [-1,1] range, but values we can store in the bitmap need to be in the [0, 255] range, we will have to convert between both value ranges to store our data as color.

A linear conversion produces an image like the following:

Bump map generated from the Imp’s diffuse map, ready to be fed into the video card.

Notice the prominence of blue, which represents normals close to the (unperturbed) $(0,0,1)$ vector. Vertical normals end up being stored as blueish colors after the linear conversion.

We are a bit more interested in the darker areas, however. This is where the normals are more perturbed and will make the Phong equation subtly affect shading, expressing “discontinuities” in the surface that the eye will interpret as “wrinkles”.

Other colors will end up looking like slopes and/or curves.

In all fairness, the image is a bit more grainy than I would’ve liked. We can apply a bilinear filter on it to make it smoother. We could also apply a scale to the $s$ and $t$ vectors to control how steep calculated normals will be.

However, since we are going to be interpolating rotated vectors during the rasterization process, these images will be good enough for now.

I’ve written a short Python script that implements this logic and applies it on any diffuse map. It is now part of the Vortex Engine toolset.

In my next post I’m going to discuss how to implement the vertex and fragment shaders necessary to apply bump mapping on a trivial surface. Stay tuned!

# Linux Journal Article available online

I’m very glad to announce that the Introductory CUDA article I wrote for RealityFrontier (and that was published by the Linux Journal Magazine) is now available for online reading.

You can access the article here: http://goo.gl/jFz3z; it features an introduction to Parallel Programming using the NVIDIA CUDA technology and some cool screenshots made using a renderer I wrote specifically for representing the concepts being treated in the article.

I can also provide links to the full source code used for the benchmarks, in case you want to have a look at it.

Just drop me a line in the comments. Enjoy!

# Parallel Programming with NVIDIA CUDA

The Linux Journal Magazine is currently running my article in their November issue. The articles features an introduction to Parallel Programming using the NVIDIA CUDA technology. I wrote this article for RealityFrontier and was kindly sponsored by CoroWare Inc. The Linux Journal introduces the article in their latest issue:

“If all that seems a bit too fluffy for your technology taste, you might just love Alejandro Segovia’s in-depth piece on parallel computing with NVIDIA’s CUDA technology. Video cards are great for gaming, but it’s amazing how powerful they can be when you use them for straight up mathematical processing. Alejandro shows how to take advantage of the little powerhouse sitting inside your computer case.”

As Raphael states in his post at the RealityFrontier website, a big thank you to CoroWare for the opportunity to write the article and to the Linux Journal for publishing it!

# C as a programming learning language

Recently we were talking with a colleague from my University about how programming is taught nowadays in college.

In my University, the programming language used for teaching how to program is Java. I was discussing with a colleague the disadvantages I saw in using it as a language for teaching programming basics and why, in my mind, it didn’t stack up against teaching a language such as plain C. The following story aims to reproduce the high points in the conversation.

Suppose you are a first year professor, teaching programming fundamentals, and I’m one of your students.

How would you start? If you’re anything like me, the first “hands-on” lab, you’ll probably write a classic “Hello World” program on the whiteboard and ask your students to copy that.

In order to do so, you instruct them to open up their “IDEs”, create a new class and copy that into a “method”…

Wait… what? As your student, chances are that by now, I’m probably wondering what an “IDE” is anyway.

As a teacher on a basic programming course, you’ll probably just tell me that IDEs are used for programming and that I’ll most likely have to use that every time I want to write a program (otherwise, what are we using it for?)

Okay, but “why don’t I have to use an IDE every time I want to use an application in my Windows”? Bam… now you must either explain the difference between code “in development” and code “in production” or ask me just to trust you and please focus on the example on the board for now.

Okay, let’s move on. You said I had to copy what you wrote into a “class’ main method”… What is a “class” and what is a “method”? Ahh, okay. Here, you are trapped. Clearly these are OOP concepts, and you certainly don’t want to start digging into that before your students even write their first “Hello World” application. All you can do here is to ask them, once again, to just trust you by saying that “that’s the way things work in Java”.

So, your students have finally created a project in an “IDE”, created a “class”, defined a “public static” “method” and wrote the snippet you typed at the whiteboard in their IDE’s text editor.

The final code looks something like this:

public class HelloWorld
{
public static void main(String[] args)
{
System.out.println("Hello, world!");
}
}

They press “Play” on their “IDEs” and it just works. Everything is good.

Quick question: how many things in this code do you think are completely strange to your students? Probably all of it, since it’s the first time they’ve seen a program being coded. That’s okay, but how many of these things do you think are feasible to be explained in a programming 101 course? just println, maybe?

Why? Because in order to explain what a “class” is, what a “method” is, what “public”, “static”, “String[]”, “System” and “out” mean, you have to start digging into OOP concepts from day one. And you don’t want to do that, because chances are 1) you’ll end up confusing everyone and 2) most of that stuff will not really be useful for the course at all!

So… if teaching this way seems to be so complicated, why are we using Java for teaching programming? Well, I think we shouldn’t. C would be a much better candidate.

Compare the previous Java program with the following C equivalent:

#include <stdio.h>
int main()
{
printf("Hello, world!");
return 0;
}

Which one do you think is easier to explain? At most, what your will probably end up asking is “what does #include mean?”. You can just answer that it’s a file where printf is defined. That’s it. No strings attached. No “public static void Main(String[] args)”. Just a plain and simple printf.

What about all that “IDE” mess? Well, it turns out you can just use a plain text editor with some syntax highlighting and a C compiler and you are good to go. Compiling C code is extremely simple, if the system is correctly configured. Just issuing a command like the following will be enough for producing an executable file:

gcc hello.c -o hello.exe

It’s that easy. And best of all is that you get an executable. A plain .exe file on Windows. That’s what your students are expecting. That’s what a program is to them. An .exe file! In Java, your compiler would’ve generated a “.class” file, and then you would have to teach your students how to invoke the Java Virtual Machine, explain what a Runtime is and why is it needed to have your code (which is already complied, isn’t it?) run.

Another final advantage? By asking them to compile their code by hand, you indirectly have them learn how to use the Terminal application (believe me, most students don’t know what that is or how it’s used nowadays) and you are laying the foundation for them to learn how to use a non-GUI operating system.

You can achieve all this (and more) without having to ask them to “trust you” or to hold their questions for one to two years, until they have their first OOP course.

You could argue that, even though Java might seem more complicated at first, it’s more popular and thus it could never be a mistake to teach it. I completely agree, but I think it should be taught as a second or third language, not as the first one. Not only does Java require the student to wait until he or she goes through 2 or 3 programming courses in order to be able to fully “get” the language, but also, there are some concepts that they will just never learn this way, such as memory management or pointers.

So, please, if you’re a programming 101 teacher who’s doing Java, I ask you to reconsider. C does not have to be hard, and your students will thank you for conducting a exhaustive, self-contained course.