Img1. Hi-Res heightfield rendered with weighted surface normals averaged into a vertex normal

Introduction

Why am I writing this article?
A few months ago I returned to the GameDev.net community after having been away for a few years working on projects in the industry. I've since then spent a good amount of time in the beginners and DirectX forums answering people's questions the best I can. One question which I've seen come up many times is how to compute the normals of a heightfield for lighting calculations. After answering the question three or four times I decided to put together this little article. I hope everyone finds it useful.

The goal of this post is to explain the most common algorithms used for computing surface and vertex normals. After a survey of the most common algorithms we'll take an in-depth look at the two most common algorithms. These in-depth looks will include a logical analysis of why the method is effective, how the math can be simplified based on what we know about heightfields, and the relative performance of the particular algorithm. By the end of the article the reader should be comfortable with computing normals as they pertain to heightfields and be familiar with which method would be best suited for the desired look and performance.

Symbols and Notation
Throughout the rest of the article I will use the following notation to indicate parts of mathematical expressions. Additionally, it should be noted that the absence of an operator between a variable and a number or between two variables should be interpreted as multiplication.

Bold:          Bold items are always vectors.
| VecA |    Vertical bars indicate "magnitude of" whatever is inside. I.e. The magnitude of Vector A
2 * B         The * indicates multiplication of two terms, but will often just be written 2B
B / 2          The slash operator is used for division of two terms
A × B        The "cross" indicates cross-product of two terms
A · B         The "dot" indicates the dot product of two terms
Θ              Theta is a Greek letter used in this article to represent an angle
Σ               Sigma is a Greek letter used in this article to indicate the summation of many terms
∆               Delta is a Greek letter used in this article to indicate a "change in" some variable

Demo Attached
The performance calculations, results, and discussions throughout this article are based on the empirical evidence I gathered through research of my own heightfield normal calculations and renderer. Links to download the demo, source code, and a listing of hot keys can be found in Appendix A. Any corrections, comments, or correspondence regarding the demo or this article can be sent to Jeromy Walsh (jwalsh) via a PM here on GameDev.net. Additionally, the source code for this demo is provided as open source. Feel free to modify and/or distribute it for your own purposes. I ask only that you leave the copyright info at the top of the files.

Quick History of Normal Calculations of Polyhedra