Publications

We propose a highly efficient hierarchical representation for point sampled geometry that automatically balances sampling density and point coordinate quantization. The representation is very compact with a memory consumption of far less than 2 bits per point position which does not depend on the quantization precision. We present an efficient rendering algorithm that exploits the hierarchical structure of the representation to perform fast 3D transformations and shading. The algorithm is extended to surface splatting which yields high quality anti-aliased and water tight surface renderings. Our pure software implementation renders up to 14 million Phong shaded and textured samples per second and about 4 million anti-aliased surface splats on a commodity PC. This is more than a factor 10 times faster than previous algorithms.

Interest point detectors are commonly employed to reduce the amount of data to be processed. The ideal interest point detector would robustly select those features which are most appropriate or salient for the application and data at hand. There is however a tradeoff between the robustness and the discriminance of the selected features. Whereas robustness in terms of repeatability is relatively well explored, the discriminance of interest points is rarely discussed. This paper formalizes the notion of saliency and evaluates three state-of-the-art interest point detectors with respect to their capability of selecting salient image features in two recognition settings.

The Perceptive Workbench endeavors to create a spontaneous and unimpeded interface between the physical and virtual worlds. Its vision-based methods for interaction constitute an alternative to wired input devices and tethered tracking. Objects are recognized and tracked when placed on the display surface. By using multiple infrared light sources, the object’s 3D shape can be captured and inserted into the virtual interface. This ability permits spontaneity since either preloaded objects or those objects selected at run-time by the user can become physical icons. Integrated into the same vision-based interface is the ability to identify 3D hand position, pointing direction, and sweeping arm gestures. Such gestures can enhance selection, manipulation, and navigation tasks. The Perceptive Workbench has been used for a variety of applications, including augmented reality gaming and terrain navigation. This paper focuses on the techniques used in implementing the Perceptive Workbench and the system’s performance.

We present a new mesh decimation framework which is based on the probabilistic optimization technique of Multiple-Choice algorithms. While producing the same expected quality of the output meshes, the Multiple-Choice approach leads to a significant speed-up compared to the well-established standard framework for mesh decimation as a greedy optimization scheme. Moreover, Multiple-Choice decimation does not require a global priority queue data structure which reduces the memory overhead and simplifies the algorithmic structure. We explain why and how the Multiple- Choice optimization works well for the mesh decimation problem and give a detailed CPU profile analysis to explain where the speed-up comes from.

In this paper we introduce, analyze and quantitatively compare a number of surface simplification methods for point-sampled geometry. We have implemented incremental and hierarchical clustering, iterative simplification, and particle simulation algorithms to create approximations of point-based models with lower sampling density. All these methods work directly on the point cloud, requiring no intermediate tesselation. We show how local variation estimation and quadric error metrics can be employed to diminish the approximation error and concentrate more samples in regions of high curvature. To compare the quality of the simplified surfaces, we have designed a new method for computing numerical and visual error estimates for point-sampled surfaces. Our algorithms are fast, easy to implement, and create high-quality surface approximations, clearly demonstrating the effectiveness of point-based surface simplification.

Extracting isosurfaces from volumetric datasets is an essential step for indirect volume rendering algorithms. For physically measured data like it is used, e.g. in medical imaging applications one often introduces topological errors such as small handles that stem from measurement inaccuracy and cavities that are generated by tight folds of an organ. During isosurface extraction these measurement errors result in a surface whose genus is much higher than that of the actual surface. In many cases however, the topological type of the object under consideration is known beforehand, e.g., the cortex of a human brain is always homeomorphic to a sphere. By using topology preserving morphological operators we can exploit this knowledge to gradually dilate an initial set of voxels with correct topology until it fits the target isosurface. This approach avoids the formation of handles and cavities and guarantees a topologically correct reconstruction of the object's surface.

In this paper we propose a progressive 3D geometry transmission technique that is robust with respect to data loss. In a preprocessing step we decompose a given polygon mesh model into a set of overlapping ellipsoids, representing the coarse shape of the model, and a stream of sample points, representing its fine detail. On the client-side, we derive a coarse approximation of the model from the ellipsoid decomposition and then re-insert the sample points to reconstruct the fine detail. The overlapping ellipsoids as well as the sample points represent independent pieces of geometric information, hence partial data loss can be tolerated by our reconstruction algorithm and will only lead to a gradual degradation of the reconstruction quality. We present a transmission scheme that is especially well-suited for geometry broadcasting where we exploit that the order of the sample points can be arbitrarily permuted.

The term multiresolution techniques refers to a class of algorithms that decompose a given geometry into its global shape and detail information on different levels of resolution. The representation of an object on several levels of detail which are defined relative to each other gives rise to a number of applications that exploit the hierarchical nature of the representation. In this Chapter we explain the theoretical background of the multiresolution transform and show how the basic concepts can be generalized to arbitrary freeform surfaces.

We survey recent developments in compact representations of 3D mesh data. This includes: Methods to reduce the complexity of meshes by simplification, thereby reducing the number of vertices and faces in the mesh; Methods to resample the geometry in order to optimize the vertex distribution; Methods to compactly represent the connectivity data (the graph structure defined by the edges) of the mesh; Methods to compactly represent the geometry data (the vertex coordinates) of a mesh.

In this paper we present a simple technique to approximate the volume enclosed by a given triangle mesh with a set of overlapping ellipsoids. This type of geometry representation allows us to approximately reconstruct 3D-shapes from a very small amount of information being transmitted. The two central questions that we address are: how can we compute optimal fitting ellipsoids that lie in the interior of a given triangle mesh and how do we select the most significant (least redundant) subset from a huge number of candidate ellipsoids. Our major motivation for computing ellipsoid decompositions is the robust transmission of geometric objects where the receiver can reconstruct the 3D-shape even if part of the data gets lost during transmission.

We present new algorithms for the robust transmission of geometric data sets, i.e. transmission which allows the receiver to recover (an approximation of) the original geometric object even if parts of the data get lost on the way. These algorithms can be considered as hinted point cloud triangulation schemes since the general manifold reconstruction problem is simplified by adding tags to the vertices and by providing a coarse base-mesh which determines the global surface topology. Robust transmission techniques exploit the geometric coherence of the data and do not require redundant transmission protocols on lower software layers. As an example application scenario we describe the teletext-like broadcasting of 3D models.

We describe the implementation of a half-edge data structure for the static representation and dynamic handling of arbitrary polygonal meshes. The particular design of the data structures and classes aims at maximum flexibility and high performance. We achieve this by using generative programming concepts which allow the compiler to resolve most of the special case handling decisions at compile time. We evaluate our data structure based on prototypic implementations of mesh processing applications such as decimation and smoothing.