In this paper we address the problem of finding correspondences between related shapes of widely varying geometry. We propose a new method based on the observation that symmetry and regularity in shapes is often associated with their function. Hence, they provide cues for matching related geometry even under strong shape variations. Correspondingly, we decomposes shapes into overlapping regions determined by their regularity properties. Afterwards, we form a graph that connects these pieces via pairwise relations that capture geometric relations between rotation axes and reflection planes as well as topological or proximity relations. Finally, we perform graph matching to establish correspondences. The method yields certain more abstract but semantically meaningful correspondences between man-made shapes that are too difficult to recognize by traditional geometric methods.

In this article, we consider the problem of animation reconstruction, that is, the reconstruction of shape and motion of a deformable object from dynamic 3D scanner data, without using user-provided template models. Unlike previous work that addressed this problem, we do not rely on locally convergent optimization but present a system that can handle fast motion, temporally disrupted input, and can correctly match objects that disappear for extended time periods in acquisition holes due to occlusion. Our approach is motivated by cartography: We first estimate a few landmark correspondences, which are extended to a dense matching and then used to reconstruct geometry and motion. We propose a number of algorithmic building blocks: a scheme for tracking landmarks in temporally coherent and incoherent data, an algorithm for robust estimation of dense correspondences under topological noise, and the integration of local matching techniques to refine the result. We describe and evaluate the individual components and propose a complete animation reconstruction pipeline based on these ideas. We evaluate our method on a number of standard benchmark datasets and show that we can obtain correct reconstructions in situations where other techniques fail completely or require additional user guidance such as a template model.

Loopy belief propagation (LBP) is a powerful tool for approximate inference in Markov random fields (MRFs). However, for problems with large state spaces, the runtime costs are often prohibitively high. In this paper, we present a new LBP algorithm that represents all beliefs, marginals, and messages in a wavelet representation, which can encode the probabilistic information much more compactly. Unlike previous work, our algorithm operates solely in the wavelet domain. This yields an output-sensitive algorithm where the running time depends mostly on the information content rather than the discretization resolution. We apply the new technique to typical problems with large state spaces such as image matching and wide-baseline optical flow where we observe a significantly improved scaling behavior with discretization resolution. For large problems, the new technique is significantly faster than even an optimized spatial domain implementation.

Abstract Recently, the problem of intrinsic shape matching has received a lot of attention. A number of algorithms have been proposed, among which random‐sampling‐based techniques have been particularly successful due to their generality and efficiency. We introduce a new sampling‐based shape matching algorithm that uses a planning step to find optimized “landmark” points. These points are matched first in order to maximize the information gained and thus minimize the sampling costs. Our approach makes three main contributions: First, the new technique leads to a significant improvement in performance, which we demonstrate on a number of benchmark scenarios. Second, our technique does not require any keypoint detection. This is often a significant limitation for models that do not show sufficient surface features. Third, we examine the actual numerical degrees of freedom of the matching problem for a given piece of geometry. In contrast to previous results, our estimates take into account unprecise geodesics and potentially numerically unfavorable geometry of general topology, giving a more realistic complexity estimate.

This paper introduces a new shape matching algorithm for computing correspondences between 3D surfaces that have undergone (approximately) isometric deformations. The new approach makes two main contributions: First, the algorithm is, unlike previous work, robust to “topological noise” such as large holes or “false connections”, which is both observed frequently in real-world scanner data. Second, our algorithm samples the space of feasible solutions such that uncertainty in matching can be detected explicitly. We employ a novel randomized feature matching algorithm in order to find robust subsets of geodesics to verify isometric consistency. The paper shows shape matching results for real world and synthetic data sets that could not be handled using previous deformable matching algorithms.

In this paper, we present a novel algorithm for partial intrinsic symmetry detection in 3D geometry. Unlike previous work, our algorithm is based on a conceptually simple and straightforward probabilistic formulation of partial shape matching: based on a Markov random field model, we obtain a probability distribution over all possible intrinsic matches of a shape to itself, which reveals the symmetry structure of the object. Rather than examining this exponentially sized distribution directly, which is infeasible, we approximate marginals of this distribution using sum-product loopy belief propagation and show how the symmetry information can subsequently be extracted from this condensed representation. Using a parallel implementation on graphics hardware, we are able to extract symmetries of deformable shapes in general poses efficiently. We apply our algorithm on several standard 3D models, demonstrating that a concise probabilistic model yields a practical and general symmetry detection algorithm.

Among all forms of sculpture, bas-relief is arguably the closest to painting. Although inherently a two dimensional sculpture, a bas-relief suggests a visual spatial extension of the scene in depth through the combination of composition, perspective, and shading. There have been significant results on digital bas-relief generation but many of the existing techniques may wash out high level surface detail during the compression process. The primary goal of this work is to address the problem of fine features by tailoring a filtering technique that achieves good compression without compromising the quality of surface details. As a secondary application we explore the generation of artistic relief which mimic cubism in painting and we show how it could be used for generating Picasso like portraits.

This paper presents a GPU-based, fast, and accurate dynamic height field rendering technique that scales well to large scale height fields. Current real-time rendering algorithms for dynamic height fields employ approximate ray-height field intersection methods, whereas accurate algorithms require pre-computation in the order of seconds to minutes and are thus not suitable for dynamic height field rendering. We alleviate this problem by using maximum mipmaps, a hierarchical data structure supporting accurate and efficient rendering while simultaneously lowering the pre-computation costs to negligible levels. Furthermore, maximum mipmaps allow for view-dependent level-of-detail rendering. In combination with hierarchical ray-stepping this results in an efficient intersection algorithm for large scale height fields.

Fluid simulation is one of the most active research areas in computer graphics. However, it remains difficult to obtain measurements of real fluid flows for validation of the simulated data. In this paper, we take a step in the direction of capturing flow data for such purposes. Specifically, we present the first time-resolved Schlieren tomography system for capturing full 3D, non-stationary gas flows on a dense volumetric grid. Schlieren tomography uses 2D ray deflection measurements to reconstruct a time-varying grid of 3D refractive index values, which directly correspond to physical properties of the flow. We derive a new solution for this reconstruction problem that lends itself to efficient algorithms that robustly work with relatively small numbers of cameras. Our physical system is easy to set up, and consists of an array of relatively low cost rolling-shutter camcorders that are synchronized with a new approach. We demonstrate our method with real measurements, and analyze precision with synthetic data for which ground truth information is available.

We present a new method for real-time rendering of sophisticated lighting effects in and around refractive objects. It enables us to realistically display refractive objects with complex material properties, such as arbitrarily varying refractive index, inhomogeneous attenuation, as well as spatially-varying anisotropic scattering and reflectance properties. User-controlled changes of lighting positions only require a few seconds of update time. Our method is based on a set of ordinary differential equations derived from the eikonal equation, the main postulate of geometric optics. This set of equations allows for fast casting of bent light rays with the complexity of a particle tracer. Based on this concept, we also propose an efficient light propagation technique using adaptive wavefront tracing. Efficient GPU implementations for our algorithmic concepts enable us to render a combination of visual effects that were previously not reproducible in real-time.