Symmetry Detection Using Feature Lines

In this paper, we describe a new algorithm for detecting structural redundancy in geometric data sets. Our algorithm computes rigid symmetries, i.e., subsets of a surface model that reoccur several times within the model differing only by translation, rotation or mirroring. Our algorithm is based on matching locally coherent constellations of feature lines on the object surfaces. In comparison to previous work, the new algorithm is able to detect a large number of symmetric parts without restrictions to regular patterns or nested hierarchies. In addition, working on relevant features only leads to a strong reduction in memory and processing costs such that very large data sets can be handled. We apply the algorithm to a number of real world 3D scanner data sets, demonstrating high recognition rates for general patterns of symmetry.     

Perception of Visual Artifacts in Image‐Based Rendering of Façades

Image‐based rendering (IBR) techniques allow users to create interactive 3D visualizations of scenes by taking a few snapshots. However, despite substantial progress in the field, the main barrier to better quality and more efficient IBR visualizations are several types of common, visually objectionable artifacts. These occur when scene geometry is approximate or viewpoints differ from the original shots, leading to parallax distortions, blurring, ghosting and popping errors that detract from the appearance of the scene. We argue that a better understanding of the causes and perceptual impact of these artifacts is the key to improving IBR methods. In this study we present a series of psychophysical experiments in which we systematically map out the perception of artifacts in IBR visualizations of façades as a function of the most common causes. We separate artifacts into different classes and measure how they impact visual appearance as a function of the number of images available, the geometry of the scene and the viewpoint. The results reveal a number of counter‐intuitive effects in the perception of artifacts. We summarize our results in terms of practical guidelines for improving existing and future IBR techniques.     

Intrinsic Shape Matching by Planned Landmark Sampling

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.     

A Global Parity Measure for Incomplete Point Cloud Data

Shapes with complex geometric and topological features such as tunnels, neighboring sheets, and cavities are susceptible to undersampling and continue to challenge existing reconstruction techniques. In this work we introduce a new measure for point clouds to determine the likely interior and exterior regions of an object. Specifically, we adapt the concept of parity to point clouds with missing data and introduce the parity map, a global measure of parity over the volume. We first examine how parity changes over the volume with respect to missing data and develop a method for extracting topologically correct interior and exterior crusts for estimating a signed distance field and performing surface reconstruction. We evaluate our approach on real scan data representing complex shapes with missing data. Our parity measure is not only able to identify highly confident interior and exterior regions but also localizes regions of missing data. Our reconstruction results are compared to existing methods and we show that our method faithfully captures the topology and geometry of complex shapes in the presence of missing data.     

Non‐Rigid Registration Under Isometric Deformations

We present a robust and efficient algorithm for the pairwise non‐rigid registration of partially overlapping 3D surfaces. Our approach treats non‐rigid registration as an optimization problem and solves it by alternating between correspondence and deformation optimization. Assuming approximately isometric deformations, robust correspondences are generated using a pruning mechanism based on geodesic consistency. We iteratively learn an appropriate deformation discretization from the current set of correspondences and use it to update the correspondences in the next iteration. Our algorithm is able to register partially similar point clouds that undergo large deformations, in just a few seconds. We demonstrate the potential of our algorithm in various applications such as example based articulated segmentation, and shape interpolation.     

Synthesis of Responsive Motion Using a Dynamic Model

Synthesizing the movements of a responsive virtual character in the event of unexpected perturbations has proven a difficult challenge. To solve this problem, we devise a fully automatic method that learns a nonlinear probabilistic model of dynamic responses from very few perturbed walking sequences. This model is able to synthesize responses and recovery motions under new perturbations different from those in the training examples. When perturbations occur, we propose a physics‐based method that initiates motion transitions to the most probable response example based on the dynamic states of the character. Our algorithm can be applied to any motion sequences without the need for preprocessing such as segmentation or alignment. The results show that three perturbed motion clips can sufficiently generate a variety of realistic responses, and 14 clips can create a responsive virtual character that reacts realistically to external forces in different directions applied on different body parts at different moments in time.     

A Resolution Independent Approach for the Accurate Rendering of Grooved Surfaces

This paper presents a method for the accurate rendering of path‐based surface details such as grooves, scratches and similar features. The method is based on a continuous representation of the features in texture space, and the rendering is performed by means of two approaches: one for isolated or non‐intersecting grooves and another for special situations like intersections or ends. The proposed solutions perform correct antialiasing and take into account visibility and inter‐reflections with little computational effort and memory requirements. Compared to anisotropic BRDFs and scratch models, we have no limitations on the distribution of grooves over the surface or their geometry, thus allowing more general patterns. Compared to displacement mapping techniques, we can efficiently simulate features of all sizes without requiring additional geometry or multiple representations.     

Discrete Line Congruences for Shading and Lighting

Two‐parameter families of straight lines (line congruences) are implicitly present in graphics and geometry processing in several important ways including lighting and shape analysis. In this paper we make them accessible to optimization and geometric computing, by introducing a general discrete version of congruences based on piecewise‐linear correspondences between triangle meshes. Our applications of congruences are based on the extraction of a so‐called torsion‐free support structure, which is a procedure analogous to remeshing a surface along its principal curvature lines. A particular application of such structures are freeform shading and lighting systems for architecture. We combine interactive design of such systems with global optimization in order to satisfy geometric constraints. In this way we explore a new area where architecture can greatly benefit from graphics.     

River Networks for Instant Procedural Planets

Realistic terrain models are required in many applications, especially in computer games. Commonly, procedural models are applied to generate the corresponding models and let users experience a wide variety of new environments. Existing algorithms generate landscapes immediately with view‐dependent resolution and without preprocessing. Unfortunately, landscapes generated by such algorithms lack river networks and therefore appear unnatural. Algorithms that integrate realistic river networks are computationally expensive and cannot be used to generate a locally adaptive high resolution landscape during a fly‐through. In this paper, we propose a novel algorithm to generate realistic river networks. Our procedural algorithm creates complete planets and landscapes with realistic river networks within seconds. It starts with a coarse base geometry of a planet without further preprocessing and user intervention. By exploiting current graphics hardware, the proposed algorithm is able to generate adaptively refined landscape geometry during fly‐throughs.     

Learning Style Compatibility Between Objects in a Real‐World 3D Asset Database

Large 3D asset databases are critical for designing virtual worlds, and using them effectively requires techniques for efficient querying and navigation. One important form of query is search by style compatibility: given a query object, find others that would be visually compatible if used in the same scene. In this paper, we present a scalable, learning‐based approach for solving this problem which is designed for use with real‐world 3D asset databases; we conduct experiments on 121 3D asset packages containing around 4000 3D objects from the Unity Asset Store. By leveraging the structure of the object packages, we introduce a technique to synthesize training labels for metric learning that work as well as human labels. These labels can grow exponentially with the number of objects, allowing our approach to scale to large real‐world 3D asset databases without the need for expensive human training labels. We use these synthetic training labels in a metric learning model that analyzes the in‐engine rendered appearance of an object—combining geometry, material, and texture—whereas prior work considers only object geometry, or disjoint geometry and texture features. Through an ablation experiment, we find that using this representation yields better results than using renders which lack texture, materiality, or both.     

Global Illumination using Photon Ray Splatting

We present a novel framework for efficiently computing the indirect illumination in diffuse and moderately glossy scenes using density estimation techniques. Many existing global illumination approaches either quickly compute an overly approximate solution or perform an orders of magnitude slower computation to obtain high-quality results for the indirect illumination. The proposed method improves photon density estimation and leads to significantly better visual quality in particular for complex geometry, while only slightly increasing the computation time. We perform direct splatting of photon rays, which allows us to use simpler search data structures. Since our density estimation is carried out in ray space rather than on surfaces, as in the commonly used photon mapping algorithm, the results are more robust against geometrically incurred sources of bias. This holds also in combination with final gathering where photon mapping often overestimates the illumination near concave geometric features. In addition, we show that our photon splatting technique can be extended to handle moderately glossy surfaces and can be combined with traditional irradiance caching for sparse sampling and filtering in image space.     

Interactive Geometric Simulation of 4D Cities

We present a simulation system that can simulate a three-dimensional urban model over time. The main novelty of our approach is that we do not rely on land-use simulation on a regular grid, but instead build a complete and inherently geometric simulation that includes exact parcel boundaries, streets of arbitrary orientation, street widths, 3D street geometry, building footprints, and 3D building envelopes. The second novelty is the fast simulation time and user interaction at interactive speed of about 1 second per time step.     

Range Scan Registration Using Reduced Deformable Models

We present an unsupervised method for registering range scans of deforming, articulated shapes. The key idea is to model the motion of the underlying object using a reduced deformable model. We use a linear skinning model for its simplicity and represent the weight functions on a regular grid localized to the surface geometry. This decouples the deformation model from the surface representation and allows us to deal with the severe occlusion and missing data that is inherent in range scan data. We formulate the registration problem using an objective function that enforces close alignment of the 3D data and includes an intuitive notion of joints. This leads to an optimization problem that we solve using an efficient EM-type algorithm. With our algorithm we obtain smooth deformations that accurately register pairs of range scans with significant motion and occlusion. The main advantages of our approach are that it does not require user specified markers, a template, nor manual segmentation of the surface geometry into rigid parts.     

Hybrid Data Visualization Based on Depth Complexity Histogram Analysis

In many cases, only the combination of geometric and volumetric data sets is able to describe a single phenomenon under observation when visualizing large and complex data. When semi‐transparent geometry is present, correct rendering results require sorting of transparent structures. Additional complexity is introduced as the contributions from volumetric data have to be partitioned according to the geometric objects in the scene. The A‐buffer, an enhanced framebuffer with additional per‐pixel information, has previously been introduced to deal with the complexity caused by transparent objects. In this paper, we present an optimized rendering algorithm for hybrid volume‐geometry data based on the A‐buffer concept. We propose two novel components for modern GPUs that tailor memory utilization to the depth complexity of individual pixels. The proposed components are compatible with modern A‐buffer implementations and yield performance gains of up to eight times compared to existing approaches through reduced allocation and reuse of fast cache memory. We demonstrate the applicability of our approach and its performance with several examples from molecular biology, space weather and medical visualization containing both, volumetric data and geometric structures.     

Sample‐Based Manifold Filtering for Interactive Global Illumination and Depth of Field

We present a fast reconstruction filtering method for images generated with Monte Carlo–based rendering techniques. Our approach specializes in reducing global illumination noise in the presence of depth‐of‐field effects at very low sampling rates and interactive frame rates. We employ edge‐aware filtering in the sample space to locally improve outgoing radiance of each sample. The improved samples are then distributed in the image plane using a fast, linear manifold‐based approach supporting very large circles of confusion. We evaluate our filter by applying it to several images containing noise caused by Monte Carlo–simulated global illumination, area light sources and depth of field. We show that our filter can efficiently denoise such images at interactive frame rates on current GPUs and with as few as 4–16 samples per pixel. Our method operates only on the colour and geometric sample information output of the initial rendering process. It does not make any assumptions on the underlying rendering technique and sampling strategy and can therefore be implemented completely as a post‐process filter.     

kDet: Parallel Constant Time Collision Detection for Polygonal Objects

We define a novel geometric predicate and a class of objects that enables us to prove a linear bound on the number of intersecting polygon pairs for colliding 3D objects in that class. Our predicate is relevant both in theory and in practice: it is easy to check and it needs to consider only the geometric properties of the individual objects – it does not depend on the configuration of a given pair of objects. In addition, it characterizes a practically relevant class of objects: we checked our predicate on a large database of real‐world 3D objects and the results show that it holds for all but the most pathological ones. Our proof is constructive in that it is the basis for a novel collision detection algorithm that realizes this linear complexity also in practice. Additionally, we present a parallelization of this algorithm with a worst‐case running time that is independent of the number of polygons. Our algorithm is very well suited not only for rigid but also for deformable and even topology‐changing objects, because it does not require any complex data structures or pre‐processing. We have implemented our algorithm on the GPU and the results show that it is able to find in real‐time all colliding polygons for pairs of deformable objects consisting of more than 200k triangles, including self‐collisions.     

Skeleton computation of orthogonal polyhedra

Skeletons are powerful geometric abstractions that provide useful representations for a number of geometric operations. The straight skeleton has a lower combinatorial complexity compared with the medial axis. Moreover, while the medial axis of a polyhedron is composed of quadric surfaces the straight skeleton just consist of planar faces. Although there exist several methods to compute the straight skeleton of a polygon, the straight skeleton of polyhedra has been paid much less attention. We require to compute the skeleton of very large datasets storing orthogonal polyhedra. Furthermore, we need to treat geometric degeneracies that usually arise when dealing with orthogonal polyhedra. We present a new approach so as to robustly compute the straight skeleton of orthogonal polyhedra. We follow a geometric technique that works directly with the boundary of an orthogonal polyhedron. Our approach is output sensitive with respect to the number of vertices of the skeleton and solves geometric degeneracies. Unlike the existing straight skeleton algorithms that shrink the object boundary to obtain the skeleton, our algorithm relies on the plane sweep paradigm. The resulting skeleton is only composed of axis‐aligned and 45° rotated planar faces and edges.     

Scalable Symmetry Detection for Urban Scenes

In this paper, we present a novel method for detecting partial symmetries in very large point clouds of 3D city scans. Unlike previous work, which has only been demonstrated on data sets of a few hundred megabytes maximum, our method scales to very large scenes: We map the detection problem to a nearest‐neighbour problem in a low‐dimensional feature space, and follow this with a cascade of tests for geometric clustering of potential matches. Our algorithm robustly handles noisy real‐world scanner data, obtaining a recognition performance comparable to that of state‐of‐the‐art methods. In practice, it scales linearly with scene size and achieves a high absolute throughput, processing half a terabyte of scanner data overnight on a dual socket commodity PC.