Publications

During the last years the concept of multi-resolution modeling has gained special attention in many fields of computer graphics and geometric modeling. In this paper we generalize powerful multiresolution techniques to arbitrary triangle meshes without requiring subdivision connectivity. Our major observation is that the hierarchy of nested spaces which is the structural core element of most multi-resolution algorithms can be replaced by the sequence of intermediate meshes emerging from the application of incremental mesh decimation. Performing such schemes with local frame coding of the detail coefficients already provides effective and efficient algorithms to extract multi-resolution information from unstructured meshes. In combination with discrete fairing techniques, i.e., the constrained minimization of discrete energy functionals, we obtain very fast mesh smoothing algorithms which are able to reduce noise from a geometrically specified frequency band in a multiresolution decomposition. Putting mesh hierarchies, local frame coding and multi-level smoothing together allows us to propose a flexible and intuitive paradigm for interactive detail-preserving mesh modification. We show examples generated by our mesh modeling tool implementation to demonstrate its functionality.

We present the necessary theory for the integration of subdivision surfaces into general purpose rendering systems. The most important functionality that has to be provided via an abstract geometry interface are the computation of surface points and normals as well as the ray intersection test. We demonstrate how to derive the corresponding formulas and how to construct tight bounding volumes for subdivision surfaces. We introduce envelope meshes which have the same topology as the control meshes but tightly circumscribe the limit surface. An efficient and simple algorithm is presented to trace a ray recursively through the forest of triangles emerging from adaptive refinement of an envelope mesh.

Subdivision is a powerful paradigm for the generation of curves and surfaces. It is easy to implement, computationally efficient, and useful in a variety of applications because of its intimate connection with multiresolution analysis. An important task in computer graphics and geometric modeling is the construction of curves that interpolate a given set of points and minimize a fairness functional (variational design). In the context of subdivision, fairing leads to special schemes requiring the solution of a banded linear system at every subdivision step. We present several examples of such schemes including one that reproduces non-uniform interpolating cubic splines. Expressing the construction in terms of certain elementary operationswe are able to embed variational subdivision in the lifting framework, a powerful technique to construct wavelet filter banks given a subdivision scheme. This allows us to extend the traditional lifting scheme for FIR filters to a certain class of IIR filters. Consequently we show how to build variationally optimal curves and associated, stable wavelets in a straightforward fashion. The algorithms to perform the corresponding decomposition and reconstruction transformations are easy to implement and efficient enough for interactive applications.

In a broad range of computer graphics applications the representation of geometric shape is based on triangle meshes. General purpose data structures for polygonal meshes typically provide fast access to geometric objects (e.g. points) and topologic entities (e.g. neighborhood relation) but the memory requirements are rather high due to the many special configurations. In this paper we present a new data structure which is specifically designed for triangle meshes. The data structure enables to trade memory for access time by either storing internal references explicitly or by locally reconstructing them on demand. The trade-off can be hidden from the programmer by an object-oriented API and automatically adapts to the available hardware resources or the complexity of the mesh (scalability).

Due to their simplicity, triangle meshes are used to represent geometric objects in many applications. Since the number of triangles often goes beyond the capabilities of computer graphics hardware and the transmission time of such data is often inappropriately high, a large variety of mesh simplification algorithms has been proposed in the last years. In this paper we identify major requirements for the practical usability of general purpose mesh reduction algorithms to enable the integration of triangle meshes into digital documents. The driving idea is to understand mesh reduction algorithms as a software extension to make more complex meshes accessible with limited hardware resources (regarding both transmission and display). We show how these requirements can be efficiently satisfied and discuss implementation aspects in detail. We present a mesh decimation scheme that fulfills these design goals and which has already been evaluated by several users from different application areas. We apply this algorithm to typical mesh data sets to demonstrate its performance.

Density Estimation is a very popular method to compute global illumination solutions in a complex virtual scene. After simulating the reflection paths of a large number of photons in the scene, the illumination at a surface point is approximated by estimating the density of photon hits in the point's surrounding. In this paper we describe a novel approach to compute such a density approximation based on Delaunay triangulation and mesh modification techniques.

While the continuous Fourier transform is a well-established standard tool for the analysis of subdivision schemes, we present a new technique based on the discrete Fourier transform instead. We first prove a very general convergence criterion for arbitrary interpolatory schemes, i.e., for non-stationary, globally supported or even non-linear schemes. Then we use the discrete Fourier transform as an algebraic tool to transform subdivision schemes into a form suitable for the analysis. This allows us to formulate simple and numerically stable sufficient criteria for the convergence of subdivision schemes of very general type. We analyze some example schemes to illustrate the resulting easy-to-apply criteria which merely require to numerically estimate the maximum of a smooth function on a compact interval.

The decimation of highly detailed meshes has emerged as an important issue in many computer graphics related fields. A whole library of different algorithms has been proposed in the literature. By carefully investigating such algorithms, we can derive a generic structure for mesh reduction schemes which is analogous to a class of greedy-algorithms for heuristic optimization. Particular instances of this algorithmic template allow to adapt to specific target applications.We present a new mesh reduction algorithmwhich clearly reflects this meta scheme and efficiently generates decimated high quality meshes while observing global error bounds.

We propose an efficient and flexible scheme to fairly interpolate or approximate the vertices of a given triangular mesh. Instead of generating a piecewise polynomial representation, our output will be a refined mesh with vertices lying densely on a surface with minimum bending energy. To obtain those, we generalize the finite differences technique to parametric meshes. The use of local parameterizations (charts) makes it possible to cast the minimization of non-linear geometric functionals into solving a sparse linear system. Efficient multi-grid solvers can be applied which leads to fast algorithms that generate surfaces of high quality.

Many mathematical problems in geometric modeling are merely due to the difficulties of handling piecewise polynomial parameterizations of surfaces (e.g., smooth connection of patches, evaluation of geometric fairness measures). Dealing with polygonal meshes is mathematically much easier although infinitesimal smoothness can no longer be achieved. However, transferring the notion of fairness to the discrete setting of triangle meshes allows to develop very efficient algorithms for many specific tasks within the design process of high quality surfaces. The use of discrete meshes instead of continuous spline surfaces is tolerable in all applications where (on an intermediate stage) explicit parameterizations are not necessary. We explain the basic technique of discrete fairing and give a survey of possible applications of this approach.

In this paper we present an indirect volume visualization method, based on the deformable surface model, which is a three dimensional extension of the snake segmentation method. In contrast to classical indirect volume visualization methods, this model is not based on iso-values but on boundary information. Physically speaking it simulates a combination of a thin plate and a rubber skin, that is influenced by forces implied by feature information extracted from the given data set. The approach proves to be appropriate for data sets that represent a collection of objects separated by distinct boundaries. These kind of data sets often occur in medical and technical tomography, as we will demonstrate by a few examples. We propose a multilevel adaptive finite difference solver, which generates a target surface minimizing an energy functional based on an internal energy of the surface and an outer energy induced by the gradient of the volume. This functional tends to produce very regular triangular meshes compared to results of the marching cubes algorithm. It makes this method attractive for meshing in numerical simulation or texture mapping. Red-green triangulation allows an adaptive refinement of the mesh. Special considerations have been made to prevent self inter-penetration of the surfaces.