Normal Map Culling

A CSC 570Q Final Project by James Patterson

Introduction

To optimize rendering, it is good for a program to only render polygon faces that can be seen by the camera. Removal of faces that would not appear in the scene is called culling. One popular form of culling is back face culling, the removal of polygon faces whose normals point away from the camera. Back face culling is a simple process described as follows:

foreach face F in polygon
    let V = the view vector of the camera
    let N = the normal of the polygon face
    if (V · N > 0)
        throw away face
    end if
end foreach

The purpose of this project was to implement an optimization of back face culling called normal map culling. For normal map culling, all of the polygon faces are stored in the hierarchical data structure based on the direction the normal is facing. Each node contains an average normal direction and tolerance level for the faces in its child nodes. If the dot product of the average normal is above a calculated tolerance value, the entire subtree is culled. While back face culling only culls one polygon face at a time, normal map culling can cull large numbers of polygons faces at once. Theoretically, this could result in a significant performance increase.

Building the normal map

To build the normal map, a recursive algorithm was used to divide the normals. In the first step, we assigned each face of the polygon to a normal node and sorted each of the nodes according to their normal magnitude in the x direction. The half of the nodes with the higher normal value were placed into one child node, and the lower half were placed into another child node. For each of these child nodes, the process was repeated in the y direction. The process splits the set of normals in half, alternating between the x, y, and z directions.

Each node in the tree contains contains a set of faces with corresponding normals, an average normal, a tolerance value and up to 2 children. The tolerance value helps to determine if a face can be culled or not. It represents the maximum angle from the average normal that any normal in the node can have. A normal map can only be culled if the angle between the view vector and the average normal is more than 90 degrees plus the tolerance angle.

Examples from the Project

This project was implemented with 3 culling modes: Back face culling on, normal map culling on, and all culling off. To illustrate the normal maps, each of the faces within a given normal maps are drawn with the same color.

Normal Map Render at drawLevel = 3	Normal Map Render at drawLevel = 18

A second camera was added to visually illustrate that the faces are being culled.

Normal Map Culling Render from 2nd Camera	Back Face Culling Render from 2nd Camera

Illustration of Cat using Normal Map Culling

Project Performance

The normal map culling was a significant improvement over back face culling as shown in the following table.

As you can see, the performance of the normal map culling algorithm was almost twice as efficient as using no culling and over 60% more efficient than using back face culling.

Program Commands