Mesostructures GSoC 2008

Introduction

Mesostructures are fine details on the surface and their rendering has become a hot topic in computer graphics. It is chiefly due to the amount of realism and visual effects (like occlusion, self-shadow and correct silhouettes) achieved by them. Techniques most commonly used in games and implemented in most game engines(Normal mapping, bump mapping) are not able produce such rich visual effects. The most traditional technique proposed for rendering fine structures is Displacement mapping. But due to the large number of polygons involved, this technique is very slow and no where close to real time. In recent years, this problem is being seen from a different perspective via Per-Pixel displacement mapping. This technique tries to achieve the same visual effects and realism as displacement mapping but does so in pixel domain giving real time performance. In recent years, lots of approaches have been proposed for per-pixel displacement mapping like Relief mapping, View dependent displacement mapping(VDM), Generalized displacement mapping(GDM), cone step mapping, sphere tracing using distance functions, pyramidal displacement mapping to name a few.

The main project is to develop an easy-to use C++ library for doing per-pixel displacement mapping. The main focus will be to provide per-pixel displacement mapping support for height field, non-height field & dynamic height field mesostructures. The effects being targeted are self shadow, silhouettes and 3D imposters.

Normal mapping

Support for the following per-pixel displacement mapping techniques –

1. Techniques –
   • Relief mapping : height field and non-height field
   • Sphere tracing using distance functions
   • Pyramidal displacement mapping
   • Maximum mipmaps for dynamic height field rendering
2. Effects –
   • 3D impostors
   • Self-shadow
   • Occlusion
   • Silhouette

Basic algorithm

General Overview

We start at the input texture coordinate in the direction of the viewing ray. Instead of using this bump-mapped texture coordinates, we trace a ray from a starting texture coordinate to the point where the ray hits the height field in the texture space. Based upon appropriate pre-processed data and rendering technique we find the intersection of this ray with the mesostructure, and use the texture coordinate of this point to access color texture, normal texture etc

Detailed description

Relief mapping

Height field

Relief mapping

Relief mapping, in short, consists of two steps – a linear step and a binary step. In the linear step(see figure below), we start from the input texture coordinates(A) and take constant sized steps in the viewing direction until we find a point inside the surface(3) where the height becomes less than the height of the surface at that texel.

Now we find the actual intersection point by using a binary step. We take the starting point(A) as t_s and the point 3 as t_e. We find the height of the midpoint of A and 3 along this ray. If the height of this midpoint is greater than the surface underneath, t_s becomes this midpoint. If height of midpoint is less than the surface t_e becomes this midpoint. If its equal we have found the intersection point.

Non-height field

In the case of non-height field intersection, the relief mapping intersection algorithm explained above is applied in parallel at relief maps of various depths. We take the intersection point which is the closest.

== Sphere tracing ==

Sphere tracing

Preprocessing step: For each point in the 3D space, we store the shortest distance to the nearest point on the surface - distance map. This distance map is created from either a height field or a detailed mesh. It is passed onto GPU as a 3D texture to be used in the rendering stage.

Rendering step: In the fragment shader, we start from texture coordinate p0 in the direction r. We access the distance map at this point to find distance to nearest point on the surface d0. By moving to point p1 = p0 + d0*r, we can guarantee of not missing any intersections. This step is repeated until we converge to the final intersection point.

References of related publications

1. Relief mapping : http://www.inf.ufrgs.br/~oliveira/RTM.html
2. Cone step mapping: http://www.lonesock.net/files/ConeStepMapping.pdf
3. VDM : http://research.microsoft.com/users/lfwang/vdm.pdf
4. GDM: http://research.microsoft.com/users/xtong/gdm_electronic.zip
5. Pyramidal displacement mapping : http://ki-h.com/article/ipdm.html
6. Sphere tracing : ftp://download.nvidia.com/developer/GPU_Gems_2/GPU_Gems2_ch08.pdf
7. Maximum Mipmaps for Fast, Accurate, and Scalable Dynamic Height Field Rendering : http://www.tevs.eu/project_i3d08.html