Concept Introduction

Relief generation is essentially a mapping from one surface to another. Neverthe-less, several algorithms in this research area, including ours, rely on appropriate 2D representations of shapes and borrow well-established techniques from im-age processing that are adapted to the specific needs of this area. To follow, we formally introduce the notations that are used later on, describe mandatory opera-tions, and explain the visualization.

2.2.1 Preprocessing

Given a 3D scene, we first convert the scene content to a so-called height field.

As a height field, we denote a two-dimensional functionhwhich stores distance information in regular discrete grid cells.

h:N×N → R h(x, y) = z

The entries of the lattice implicitly encode the shapes in a scene relative to the viewing plane up to occlusion. This is why it is also denoted as a 2.5D represen-tation. In practice, we capture height fields by rendering a scene and reading the depth buffer of the GPU. This is very fast and provides a preview such that camera position, situation of the objects, and height field resolution can be interactively adjusted beforehand. Henceforth, we use the termsdepth map andrange image as synonyms for height field.

We assume that the background pixels ofh, those outside the clipping planes, are set to a default valueδand derive a binarybackground mask b that allows us to distinguish foreground and background content.

b:N×N → {0,1}

b(x, y) =

0, ifh(x, y) =δ 1, else

Then, the height field is normalized in such a way that the background lies on the zero-level and the foreground entries range from zero to a positive value. This maximal foreground entry is denoted asR_T=0and indicates the initial depth inter-val range. The properties of the derivatives ofhare important for several steps of our algorithms. They would be negatively affected if foreground objects coincide with the height field boundary. To prevent this, we extend the boundary of both functionshand bby 2 pixels of value 0. This concludes the pre-processing step and defines the input for our compression methods.

From now on, we alternatively use all two-dimensional functions with a unary pixel indexiorj to achieve more compactness and readability in the notation.

2.2.2 Feature Enhancement

The main idea of relief generation is the preservation of small and high frequency details throughout the compression step. Therefore, it is important to distinguish visually important structures from those that are less important or coarse enough to “survive” the shrinking anyway. After representing the input appropriately, it is decomposed into a fine component, which is more sensitive to the compression, and a more robust coarse part. The details are then artificially boosted such that they also remain perceivable in the shrunken relief.

Unsharp Masking

The concept of unsharp masking is a key ingredient in our compression tech-niques. This term describes a feature enhancement technique that was initially designed to emphasize certain properties in images [LCD06] by manipulating the interplay between different frequency components of an underlying signal.

Among others, such a technique can also be applied to exaggerate characteristics of meshes [RSI⁺08]. In our scenario, the height field is decomposed into a coarse and a fine component. Then, the relative importance of fine features is enhanced at the expense of coarse structures.

Technically, an input imageIis convolved with a low pass kernelK, resulting in a smooth versionLofI. SubtractingLfromIleads to a high-frequency image H, containing sharp peaks at small scale details. Adding a multiple ofHback to Lleads to a relative emphasis of fine structures in the newly reassembled image I.

L = I⊗K H = I−L

I = λ·H+L

Boosting with a sufficiently largeλensures that even the fine details also remain perceivable in the compressed result. Whenever the relation between those com-ponents is influenced, it leads to a distortion of the shape. As described above, this effect is intended to fulfill the desired properties of the relief.

Bilateral Filtering

For the decomposition in the unsharp masking step, it was our idea to apply a bilateral filter. This is a tool commonly used in image processing. It permits edge-preserving smoothing of signals [TM98]. In contrast to regular Gaussian blurring, which leads to a smearing around transition areas, a bilateral filter overcomes this issue by diminishing the influence of pixels with differing entries.

Thus, it ensures the sharpness of local discontinuities and, at the same time, smoothes regions of similar values. Among other things, these properties are also provided by a diffusion filter but it is computationally more complicated and time-consuming. Gaussian as well as diffusion filtering have been used in earlier works.

The particular differences as well as their advantages and disadvantages compared to the bilateral filter are described in Section3.1.4

Technically, this is achieved by a convolution with a kernel that consists of a product of two non-linear weighting functions. The first one penalizes the spatial distance, whereas the second mapping only takes deviations of the values into account. Here, we introduce the bilateral weighting functionω which is used in the actual filtering process later on.

ω(f, i, j) = G_σs(||i−j||)·G_σv(|f(i)−f(j)|) (2.1) f : N² →R

i, j ∈ N²

As parameters, it takes a mappingf, a center pixeli, and a neighbor pixelj, both within the domain off. The symbolsG_σs andG_σv each denote one-dimensional Gaussian kernels with corresponding standard deviations. As the default, we ap-ply the same adaptive adjustment for both parameters as proposed in the imple-mentation of [PD06]¹. To be precise,σ_sis chosen as ₁₆¹ of the smaller resolution off (in x- or y-dimension), whereasσvcorresponds to 10% of its value range.

A bilateral filter is not separable but can be approximated [DD02, PD06].

Its computation is simple and can be done in parallel. The idea is independent of the domain and, among other things, also finds application in the denoising of meshes [FDCO03]. To gain deeper insight into the characteristics and the concept of bilateral filtering, we refer to [PKTD08].

2.2.3 Presentation

The output of our algorithms is again a depth map. In order to display a static result in a figure, we triangulate the range image according to the 2D lattice and displace each vertex by its corresponding entry along the z-direction. The result-ing mesh is then rendered usresult-ing Phong shadresult-ing. We vary the material colors, but always use white specular reflections and one single white light source.

1http://people.csail.mit.edu/jiawen/software/bilateralFilter.m

Model sources

The models that we use to depict the effects and capabilities of our algorithms throughout this part of the thesis have been provided by courtesy of the sources listed below:

• Stanford 3D Scanning Repository: Lucy statue, armadillo, bunny

• XYZ RGB Inc.: Thai statue, dragon

• Aim@Shape: Lion-dog, lion vase, filigree, Caesar, cup, pharaoh mask, Greek statue

• Google 3D Warehouse: Cinderella castle

• Cyberware: Satva statue

• The Digital Michelangelo Project: David head

• Graphics and Geometric Computing Group, Tsinghua University: Robot 3D animation sequence