Object Completion using k‐Sparse Optimization

We present a new method for the completion of partial globally‐symmetric 3D objects, based on the detection of partial and approximate symmetries in the incomplete input dataset. In our approach, symmetry detection is formulated as a constrained sparsity maximization problem, which is solved efficiently using a robust RANSAC‐based optimizer. The detected partial symmetries are then reused iteratively, in order to complete the missing parts of the object. A global error relaxation method minimizes the accumulated alignment errors and a non‐rigid registration approach applies local deformations in order to properly handle approximate symmetry. Unlike previous approaches, our method does not rely on the computation of features, it uniformly handles translational, rotational and reflectional symmetries and can provide plausible object completion results, even on challenging cases, where more than half of the target object is missing. We demonstrate our algorithm in the completion of 3D scans with varying levels of partiality and we show the applicability of our approach in the repair and completion of heavily eroded or incomplete cultural heritage objects.     

Intrinsic Symmetry Detection on 3D Models with Skeleton‐guided Combination of Extrinsic Symmetries

The existing methods for intrinsic symmetry detection on 3D models always need complex measures such as geodesic distances for describing intrinsic geometry and statistical computation for finding non‐rigid transformations to associate symmetrical shapes. They are expensive, may miss symmetries, and cannot guarantee their obtained symmetrical parts in high quality. We observe that only extrinsic symmetries exist between convex shapes, and two intrinsically symmetric shapes can be determined if their belonged convex sub‐shapes are symmetrical to each other correspondingly and connected in a similar topological structure. Thus, we propose to decompose the model into convex parts, and use the similar structures of the skeleton of the model to guide combination of extrinsic symmetries between convex parts for intrinsic symmetry detection. In this way, we give up statistical computation for intrinsic symmetry detection, and avoid complex measures for describing intrinsic geometry. With the similar structures being from small to large gradually, we can quickly detect multi‐scale partial intrinsic symmetries in a bottom up manner. Benefited from the well segmented convex parts, our obtained symmetrical parts are in high quality. Experimental results show that our method can find many more symmetries and runs much faster than the existing methods, even by several orders of magnitude.     

Data‐Driven Sparse Priors of 3D Shapes

We present a sparse optimization framework for extracting sparse shape priors from a collection of 3D models. Shape priors are defined as point‐set neighborhoods sampled from shape surfaces which convey important information encompassing normals and local shape characterization. A 3D shape model can be considered to be formed with a set of 3D local shape priors, while most of them are likely to have similar geometry. Our key observation is that the local priors extracted from a family of 3D shapes lie in a very low‐dimensional manifold. Consequently, a compact and informative subset of priors can be learned to efficiently encode all shapes of the same family. A comprehensive library of local shape priors is first built with the given collection of 3D models of the same family. We then formulate a global, sparse optimization problem which enforces selecting representative priors while minimizing the reconstruction error. To solve the optimization problem, we design an efficient solver based on the Augmented Lagrangian Multipliers method (ALM). Extensive experiments exhibit the power of our data‐driven sparse priors in elegantly solving several high‐level shape analysis applications and geometry processing tasks, such as shape retrieval, style analysis and symmetry detection.     

Packing Irregular Objects in 3D Space via Hybrid Optimization

Packing problems arise in a wide variety of practical applications. The basic problem is that of placing as many objects as possible in a non‐overlapping configuration within a given container. Problems involving irregular shapes are the most challenging cases. In this paper, we consider the most general forms of irregular shape packing problems in 3D space, where both the containers and the objects can be of any shapes, and free rotations of the objects are allowed. We propose a heuristic method for efficiently packing irregular objects by combining continuous optimization and combinatorial optimization. Starting from an initial placement of an appropriate number of objects, we optimize the positions and orientations of the objects using continuous optimization. In combinatorial optimization, we further reduce the gaps between objects by swapping and replacing the deployed objects and inserting new objects. We demonstrate the efficacy of our method with experiments and comparisons.     

Möbius Transformations For Global Intrinsic Symmetry Analysis

The goal of our work is to develop an algorithm for automatic and robust detection of global intrinsic symmetries in 3D surface meshes. Our approach is based on two core observations. First, symmetry invariant point sets can be detected robustly using critical points of the Average Geodesic Distance (AGD) function. Second, intrinsic symmetries are self‐isometries of surfaces and as such are contained in the low dimensional group of Möbius transformations. Based on these observations, we propose an algorithm that: 1) generates a set of symmetric points by detecting critical points of the AGD function, 2) enumerates small subsets of those feature points to generate candidate Möbius transformations, and 3) selects among those candidate Möbius transformations the one(s) that best map the surface onto itself. The main advantages of this algorithm stem from the stability of the AGD in predicting potential symmetric point features and the low dimensionality of the Möbius group for enumerating potential self‐mappings. During experiments with a benchmark set of meshes augmented with human‐specified symmetric correspondences, we find that the algorithm is able to find intrinsic symmetries for a wide variety of object types with moderate deviations from perfect symmetry.     

Feature Curve Co‐Completion in Noisy Data

Feature curves on 3D shapes provide important hints about significant parts of the geometry and reveal their underlying structure. However, when we process real world data, automatically detected feature curves are affected by measurement uncertainty, missing data, and sampling resolution, leading to noisy, fragmented, and incomplete feature curve networks. These artifacts make further processing unreliable. In this paper we analyze the global co‐occurrence information in noisy feature curve networks to fill in missing data and suppress weakly supported feature curves. For this we propose an unsupervised approach to find meaningful structure within the incomplete data by detecting multiple occurrences of feature curve configurations (co‐occurrence analysis). We cluster and merge these into feature curve templates, which we leverage to identify strongly supported feature curve segments as well as to complete missing data in the feature curve network. In the presence of significant noise, previous approaches had to resort to user input, while our method performs fully automatic feature curve co‐completion. Finding feature reoccurrences however, is challenging since naïve feature curve comparison fails in this setting due to fragmentation and partial overlaps of curve segments. To tackle this problem we propose a robust method for partial curve matching. This provides us with the means to apply symmetry detection methods to identify co‐occurring configurations. Finally, Bayesian model selection enables us to detect and group re‐occurrences that describe the data well and with low redundancy.     

Microtiles: Extracting Building Blocks from Correspondences

In this paper, we develop a theoretical framework for characterizing shapes by building blocks. We address two questions: First, how do shape correspondences induce building blocks? For this, we introduce a new representation for structuring partial symmetries (partial self‐correspondences), which we call “microtiles”. Starting from input correspondences that form point‐wise equivalence relations, microtiles are obtained by grouping connected components of points that share the same set of symmetry transformations. The decomposition is unique, requires no parameters beyond the input correspondences, and encodes the partial symmetries of all subsets of the input. The second question is: What is the class of shapes that can be assembled from these building blocks? Here, we specifically consider r‐similarity as correspondence model, i.e., matching of local r‐neighborhoods. Our main result is that the microtiles of the partial r‐symmetries of an object S can build all objects that are (r+ε)‐similar to S for any ε >0. Again, the construction is unique. Furthermore, we give necessary conditions for a set of assembly rules for the pairwise connection of tiles. We describe a practical algorithm for computing microtile decompositions under rigid motions, a corresponding prototype implementation, and conduct a number of experiments to visualize the structural properties in practice.     

Symmetry Hierarchy of Man‐Made Objects

We introduce symmetry hierarchy of man‐made objects, a high‐level structural representation of a 3D model providing a symmetry‐induced, hierarchical organization of the model's constituent parts. Given an input mesh, we segment it into primitive parts and build an initial graph which encodes inter‐part symmetries and connectivity relations, as well as self‐symmetries in individual parts. The symmetry hierarchy is constructed from the initial graph via recursive graph contraction which either groups parts by symmetry or assembles connected sets of parts. The order of graph contraction is dictated by a set of precedence rules designed primarily to respect the law of symmetry in perceptual grouping and the principle of compactness of representation. We show that symmetry hierarchy naturally implies a hierarchical segmentation that is more meaningful than those produced by local geometric considerations. We also develop an application of symmetry hierarchies for structural shape editing.     

Closed‐form Blending of Local Symmetries

We present a closed‐form solution for the symmetrization problem, solving for the optimal deformation that reconciles a set of local bilateral symmetries. Given as input a set of point‐pairs which should be symmetric, we first compute for each local neighborhood a transformation which would produce an approximate bilateral symmetry. We then solve for a single global symmetry which includes all of these local symmetries, while minimizing the deformation within each local neighborhood. Our main motivation is the symmetrization of digitized fossils, which are often deformed by a combination of compression and bending. In addition, we use the technique to symmetrize articulated models.     

Modeling and Exploring Co‐variations in the Geometry and Configuration of Man‐made 3D Shape Families

We introduce co‐variation analysis as a tool for modeling the way part geometries and configurations co‐vary across a family of man‐made 3D shapes. While man‐made 3D objects exhibit large geometric and structural variations, the geometry, structure, and configuration of their individual components usually do not vary independently from each other but in a correlated fashion. The size of the body of an airplane, for example, constrains the range of deformations its wings can undergo to ensure that the entire object remains a functionally‐valid airplane. These co‐variation constraints, which are often non‐linear, can be either physical, and thus they can be explicitly enumerated, or implicit to the design and style of the shape family. In this article, we propose a data‐driven approach, which takes pre‐segmented 3D shapes with known component‐wise correspondences and learns how various geometric and structural properties of their components co‐vary across the set. We demonstrate, using a variety of 3D shape families, the utility of the proposed co‐variation analysis in various applications including 3D shape repositories exploration and shape editing where the propagation of deformations is guided by the co‐variation analysis. We also show that the framework can be used for context‐guided orientation of objects in 3D scenes.     

Fast and Exact (Poisson) Solvers on Symmetric Geometries

In computer graphics, numerous geometry processing applications reduce to the solution of a Poisson equation. When considering geometries with symmetry, a natural question to consider is whether and how the symmetry can be leveraged to derive an efficient solver for the underlying system of linear equations. In this work we provide a simple representation‐theoretic analysis that demonstrates how symmetries of the geometry translate into block diagonalization of the linear operators and we show how this results in efficient linear solvers for surfaces of revolution with and without angular boundaries.     

Alignment of 3D models

In this paper we present a new method for alignment of 3D models. This approach is based on two types of symmetries of the models: the reflective symmetry and the local translational symmetry along a direction. Inspired by the work on the principal component analysis (PCA), we select the best optimal alignment axes within the PCA-axes, the plane reflection symmetry being used as a selection criterion. This pre-processing transforms the alignment problem into an indexing scheme based on the number of the retained PCA-axes. In order to capture the local translational symmetry of a shape along a direction, we introduce a new measure we call the local translational invariance cost (LTIC). The mirror planes of a model are also used to reduce the number of candidate coordinate frames when looking for the one which corresponds to the user’s perception. Experimental results show that the proposed method finds the rotation that best aligns a 3D mesh.     

Computational Design of Steady 3D Dissection Puzzles

Dissection puzzles require assembling a common set of pieces into multiple distinct forms. Existing works focus on creating 2D dissection puzzles that form primitive or naturalistic shapes. Unlike 2D dissection puzzles that could be supported on a tabletop surface, 3D dissection puzzles are preferable to be steady by themselves for each assembly form. In this work, we aim at computationally designing steady 3D dissection puzzles. We address this challenging problem with three key contributions. First, we take two voxelized shapes as inputs and dissect them into a common set of puzzle pieces, during which we allow slightly modifying the input shapes, preferably on their internal volume, to preserve the external appearance. Second, we formulate a formal model of generalized interlocking for connecting pieces into a steady assembly using both their geometric arrangements and friction. Third, we modify the geometry of each dissected puzzle piece based on the formal model such that each assembly form is steady accordingly. We demonstrate the effectiveness of our approach on a wide variety of shapes, compare it with the state‐of‐the‐art on 2D and 3D examples, and fabricate some of our designed puzzles to validate their steadiness.     

As‐Rigid‐AsPossible Distance Field Metamorphosis

Widely used for morphing between objects with arbitrary topology, distance field interpolation (DFI) handles topological transition naturally without the need for correspondence or remeshing, unlike surface‐based interpolation approaches. However, lack of correspondence in DFI also leads to ineffective control over the morphing process. In particular, unless the user specifies a dense set of landmarks, it is not even possible to measure the distortion of intermediate shapes during interpolation, let alone control it. To remedy such issues, we introduce an approach for establishing correspondence between the interior of two arbitrary objects, formulated as an optimal mass transport problem with a sparse set of landmarks. This correspondence enables us to compute non‐rigid warping functions that better align the source and target objects as well as to incorporate local rigidity constraints to perform as‐rigid‐aspossible DFI. We demonstrate how our approach helps achieve flexible morphing results with a small number of landmarks.     

Symmetry as a continuous feature

Symmetry is treated as a continuous feature and a continuous measure of distance from symmetry in shapes is defined. The symmetry distance (SD) of a shape is defined to be the minimum mean squared distance required to move points of the original shape in order to obtain a symmetrical shape. This general definition of a symmetry measure enables a comparison of the “amount” of symmetry of different shapes and the “amount” of different symmetries of a single shape. This measure is applicable to any type of symmetry in any dimension. The symmetry distance gives rise to a method of reconstructing symmetry of occluded shapes. The authors extend the method to deal with symmetries of noisy and fuzzy data. Finally, the authors consider grayscale images as 3D shapes, and use the symmetry distance to find the orientation of symmetric objects from their images, and to find locally symmetric regions in images     

Silhouette‐Aware Warping for Image‐Based Rendering

Image‐based rendering (IBR) techniques allow capture and display of 3D environments using photographs. Modern IBR pipelines reconstruct proxy geometry using multi‐view stereo, reproject the photographs onto the proxy and blend them to create novel views. The success of these methods depends on accurate 3D proxies, which are difficult to obtain for complex objects such as trees and cars. Large number of input images do not improve reconstruction proportionally; surface extraction is challenging even from dense range scans for scenes containing such objects. Our approach does not depend on dense accurate geometric reconstruction; instead we compensate for sparse 3D information by variational image warping. In particular, we formulate silhouette‐aware warps that preserve salient depth discontinuities. This improves the rendering of difficult foreground objects, even when deviating from view interpolation. We use a semi‐automatic step to identify depth discontinuities and extract a sparse set of depth constraints used to guide the warp. Our framework is lightweight and results in good quality IBR for previously challenging environments.     

Hierarchical Quad Meshing of 3D Scanned Surfaces

In this paper we present a novel method to reconstruct watertight quad meshes on scanned 3D geometry. There exist many different approaches to acquire 3D information from real world objects and sceneries. Resulting point clouds depict scanned surfaces as sparse sets of positional information. A common downside is the lack of normals, connectivity or topological adjacency data which makes it difficult to actually recover a meaningful surface. The concept described in this paper is designed to reconstruct a surface mesh despite all this missing information. Even when facing varying sample density, our algorithm is still guaranteed to produce watertight manifold meshes featuring quad faces only. The topology can be set‐up to follow superimposed regular structures or align naturally to the point cloud's shape. Our proposed approach is based on an initial divide and conquer subsampling procedure: Surface samples are clustered in meaningful neighborhoods as leafs of a kd‐tree. A representative sample of the surface neighborhood is determined for each leaf using a spherical surface approximation. The hierarchical structure of the binary tree is utilized to construct a basic set of loose tiles and to interconnect them. As a final step, missing parts of the now coherent tile structure are filled up with an incremental algorithm for locally optimal gap closure. Disfigured or concave faces in the resulting mesh can be removed with a constrained smoothing operator.