Fast and Scalable Mesh Superfacets

In the field of computer vision, the introduction of a low‐level preprocessing step to oversegment images into superpixels – relatively small regions whose boundaries agree with those of the semantic entities in the scene – has enabled advances in segmentation by reducing the number of elements to be labeled from hundreds of thousands, or millions, to a just few hundred. While some recent works in mesh processing have used an analogous oversegmentation, they were not intended to be general and have relied on graph cut techniques that do not scale to current mesh sizes. Here, we present an iterative superfacet algorithm and introduce adaptations of undersegmentation error and compactness, which are well‐motivated and principled metrics from the vision community. We demonstrate that our approach produces results comparable to those of the normalized cuts algorithm when evaluated on the Princeton Segmentation Benchmark, while requiring orders of magnitude less time and memory and easily scaling to, and enabling the processing of, much larger meshes.     

Guided Mesh Normal Filtering

The joint bilateral filter is a variant of the standard bilateral filter, where the range kernel is evaluated using a guidance signal instead of the original signal. It has been successfully applied to various image processing problems, where it provides more flexibility than the standard bilateral filter to achieve high quality results. On the other hand, its success is heavily dependent on the guidance signal, which should ideally provide a robust estimation about the features of the output signal. Such a guidance signal is not always easy to construct. In this paper, we propose a novel mesh normal filtering framework based on the joint bilateral filter, with applications in mesh denoising. Our framework is designed as a two‐stage process: first, we apply joint bilateral filtering to the face normals, using a properly constructed normal field as the guidance; afterwards, the vertex positions are updated according to the filtered face normals. We compute the guidance normal on a face using a neighboring patch with the most consistent normal orientations, which provides a reliable estimation of the true normal even with a high‐level of noise. The effectiveness of our approach is validated by extensive experimental results.     

Single‐View Modeling of Layered Origami with Plausible Outer Shape

Modeling 3D origami pieces using conventional software is laborious due to the geometric constraints imposed by the complicated layered structure. Targeting origami models used in visual content such as CG illustrations and movies, we propose an interactive system that dramatically simplifies the modeling of 3D origami pieces with plausible outer shapes, while omitting accurate inner structures. By focusing on flat origami models with a front‐and‐back symmetry commonly found in traditional artworks, our system realizes easy and quick modeling via single‐view interface; given a reference image of the target origami piece, the user draws polygons of planar faces onto the image, and assigns annotations indicating the types of folding operations. Our system automatically rectifies the manually‐specified polygons, infers the folded structures that should yield the user‐specified polygons with reference to the depth order of layered polygons, and generates a plausible 3D model while accounting for gaps between layers. Our system is versatile enough for modeling pseudo‐origami models that are not realizable by folding a single sheet of paper. Our user study demonstrates that even novice users without the specialized knowledge and experience on origami and 3D modeling can create plausible origami models quickly.     

Remeshing‐assisted Optimization for Locally Injective Mappings

Constructing locally injective mappings for 2D triangular meshes is vital in applications such as deformations. In such a highly constrained optimization, the prescribed tessellation may impose strong restriction on the solution. As a consequence, the feasible region may be too small to contain an ideal solution, which leads to problems of slow convergence, poor solution, or even that no solution can be found. We propose to integrate adaptive remeshing into interior point method to solve this issue. We update the vertex positions via a parameter‐free relaxation enhanced geometry optimization, and then use edge‐flip operations to reduce the residual and keep a reasonable condition number for better convergence. For more robustness, when the iteration of interior point method terminates but leaves the positional constraints unsatisfied, we estimate the edges in the current tessellation that block vertices moving based on the convergence information of the optimization, and then split neighboring edges to break the restriction. The results show that our method has better performance than the solely geometric optimization approaches, especially for extreme deformations.     

An Eulerian approach for constructing a map between surfaces with different topologies

3D objects of the same kind often have different topologies, and finding correspondence between them is important for operations such as morphing, attribute transfer, and shape matching. This paper presents a novel method to find the surface correspondence between topologically different surfaces. The method is characterized by deforming the source polygonal mesh to match the target mesh by using the intermediate implicit surfaces, and by performing a topological surgery at the appropriate locations on the mesh. In particular, we propose a mathematically well‐defined way to detect the topology change of surface by finding the non‐degenerate saddle points of the velocity fields that tracks implicit surfaces. We show the effectiveness and possible applications of the proposed method through several experiments.     

Multi‐style paper pop‐up designs from 3D models

Paper pop‐ups are interesting three‐dimensional books that fascinate people of all ages. The design and construction of these pop‐up books however are done manually and require a lot of time and effort. This has led to computer‐assisted or automated tools for designing paper pop‐ups. This paper proposes an approach for automatically converting a 3D model into a multi‐style paper pop‐up. Previous automated approaches have only focused on single‐style pop‐ups, where each is made of a single type of pop‐up mechanisms. In our work, we combine multiple styles in a pop‐up, which is more representative of actual artist's creations. Our method abstracts a 3D model using suitable primitive shapes that both facilitate the formation of the considered pop‐up mechanisms and closely approximate the input model. Each shape is then abstracted using a set of 2D patches that combine to form a valid pop‐up. We define geometric conditions that ensure the validity of the combined pop‐up structures. In addition, our method also employs an image‐based approach for producing the patches to preserve the textures, finer details and important contours of the input model. Finally, our system produces a printable design layout and decides an assembly order for the construction instructions. The feasibility of our results is verified by constructing the actual paper pop‐ups from the designs generated by our system.     

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.     

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.     

GWCNN: A Metric Alignment Layer for Deep Shape Analysis

Deep neural networks provide a promising tool for incorporating semantic information in geometry processing applications. Unlike image and video processing, however, geometry processing requires handling unstructured geometric data, and thus data representation becomes an important challenge in this framework. Existing approaches tackle this challenge by converting point clouds, meshes, or polygon soups into regular representations using, e.g., multi‐view images, volumetric grids or planar parameterizations. In each of these cases, geometric data representation is treated as a fixed pre‐process that is largely disconnected from the machine learning tool. In contrast, we propose to optimize for the geometric representation during the network learning process using a novel metric alignment layer. Our approach maps unstructured geometric data to a regular domain by minimizing the metric distortion of the map using the regularized Gromov–Wasserstein objective. This objective is parameterized by the metric of the target domain and is differentiable; thus, it can be easily incorporated into a deep network framework. Furthermore, the objective aims to align the metrics of the input and output domains, promoting consistent output for similar shapes. We show the effectiveness of our layer within a deep network trained for shape classification, demonstrating state‐of‐the‐art performance for nonrigid shapes.     

Designing Camera Networks by Convex Quadratic Programming

In this paper, we study the problem of automatic camera placement for computer graphics and computer vision applications. We extend the problem formulations of previous work by proposing a novel way to incorporate visibility constraints and camera‐to‐camera relationships. For example, the placement solution can be encouraged to have cameras that image the same important locations from different viewing directions, which can enable reconstruction and surveillance tasks to perform better. We show that the general camera placement problem can be formulated mathematically as a convex binary quadratic program (BQP) under linear constraints. Moreover, we propose an optimization strategy with a favorable trade‐off between speed and solution quality. Our solution is almost as fast as a greedy treatment of the problem, but the quality is significantly higher, so much so that it is comparable to exact solutions that take orders of magnitude more computation time. Because it is computationally attractive, our method also allows users to explore the space of solutions for variations in input parameters. To evaluate its effectiveness, we show a range of 3D results on real‐world floorplans (garage, hotel, mall, and airport).     

Advection‐Based Function Matching on Surfaces

A tangent vector field on a surface is the generator of a smooth family of maps from the surface to itself, known as the flow. Given a scalar function on the surface, it can be transported, or advected, by composing it with a vector field's flow. Such transport is exhibited by many physical phenomena, e.g., in fluid dynamics. In this paper, we are interested in the inverse problem: given source and target functions, compute a vector field whose flow advects the source to the target. We propose a method for addressing this problem, by minimizing an energy given by the advection constraint together with a regularizing term for the vector field. Our approach is inspired by a similar method in computational anatomy, known as LDDMM, yet leverages the recent framework of functional vector fields for discretizing the advection and the flow as operators on scalar functions. The latter allows us to efficiently generalize LDDMM to curved surfaces, without explicitly computing the flow lines of the vector field we are optimizing for. We show two approaches for the solution: using linear advection with multiple vector fields, and using non‐linear advection with a single vector field. We additionally derive an approximated gradient of the corresponding energy, which is based on a novel vector field transport operator. Finally, we demonstrate applications of our machinery to intrinsic symmetry analysis, function interpolation and map improvement.     

Sets of Globally Optimal Stream Surfaces for Flow Visualization

Stream surfaces are a well‐studied and widely used tool for the visualization of 3D flow fields. Usually, stream surface seeding is carried out manually in time‐consuming trial and error procedures. Only recently automatic selection methods were proposed. Local methods support the selection of a set of stream surfaces, but, contrary to global selection methods, they evaluate only the quality of the seeding lines but not the quality of the whole stream surfaces. Global methods, on the other hand, only support the selection of a single optimal stream surface until now. However, for certain flow fields a single stream surface is not sufficient to represent all flow features. In our work, we overcome this limitation by introducing a global selection technique for a set of stream surfaces. All selected surfaces optimize global stream surface quality measures and are guaranteed to be mutually distant, such that they can convey different flow features. Our approach is an efficient extension of the most recent global selection method for single stream surfaces. We illustrate its effectiveness on a number of analytical and simulated flow fields and analyze the quality of the results in a user study.     

String‐Based Synthesis of Structured Shapes

We propose a novel method to synthesize geometric models from a given class of context‐aware structured shapes such as buildings and other man‐made objects. The central idea is to leverage powerful machine learning methods from the area of natural language processing for this task. To this end, we propose a technique that maps shapes to strings and vice versa, through an intermediate shape graph representation. We then convert procedurally generated shape repositories into text databases that, in turn, can be used to train a variational autoencoder. The autoencoder enables higher level shape manipulation and synthesis like, for example, interpolation and sampling via its continuous latent space. We provide project code and pre‐trained models.     

2D‐D Lifting for Shape Reconstruction

We present an algorithm for shape reconstruction from incomplete 3D scans by fusing together two acquisition modes: 2D photographs and 3D scans. The two modes exhibit complementary characteristics: scans have depth information, but are often sparse and incomplete; photographs, on the other hand, are dense and have high resolution, but lack important depth information. In this work we fuse the two modes, taking advantage of their complementary information, to enhance 3D shape reconstruction from an incomplete scan with a 2D photograph. We compute geometrical and topological shape properties in 2D photographs and use them to reconstruct a shape from an incomplete 3D scan in a principled manner. Our key observation is that shape properties such as boundaries, smooth patches and local connectivity, can be inferred with high confidence from 2D photographs. Thus, we register the 3D scan with the 2D photograph and use scanned points as 3D depth cues for lifting 2D shape structures into 3D. Our contribution is an algorithm which significantly regularizes and enhances the problem of 3D reconstruction from partial scans by lifting 2D shape structures into 3D. We evaluate our algorithm on various shapes which are loosely scanned and photographed from different views, and compare them with state‐of‐the‐art reconstruction methods.     

Automatic Modeling of Urban Facades from Raw LiDAR Point Data

Modeling of urban facades from raw LiDAR point data remains active due to its challenging nature. In this paper, we propose an automatic yet robust 3D modeling approach for urban facades with raw LiDAR point clouds. The key observation is that building facades often exhibit repetitions and regularities. We hereby formulate repetition detection as an energy optimization problem with a global energy function balancing geometric errors, regularity and complexity of facade structures. As a result, repetitive structures are extracted robustly even in the presence of noise and missing data. By registering repetitive structures, missing regions are completed and thus the associated point data of structures are well consolidated. Subsequently, we detect the potential design intents (i.e., geometric constraints) within structures and perform constrained fitting to obtain the precise structure models. Furthermore, we apply structure alignment optimization to enforce position regularities and employ repetitions to infer missing structures. We demonstrate how the quality of raw LiDAR data can be improved by exploiting data redundancy, and discovering high level structural information (regularity and symmetry). We evaluate our modeling method on a variety of raw LiDAR scans to verify its robustness and effectiveness.     

Template Assembly for Detailed Urban Reconstruction

We propose a new framework to reconstruct building details by automatically assembling 3D templates on coarse textured building models. In a preprocessing step, we generate an initial coarse model to approximate a point cloud computed using Structure from Motion and Multi View Stereo, and we model a set of 3D templates of facade details. Next, we optimize the initial coarse model to enforce consistency between geometry and appearance (texture images). Then, building details are reconstructed by assembling templates on the textured faces of the coarse model. The 3D templates are automatically chosen and located by our optimization‐based template assembly algorithm that balances image matching and structural regularity. In the results, we demonstrate how our framework can enrich the details of coarse models using various data sets.     

Learning 3D Deformation of Animals from 2D Images

Understanding how an animal can deform and articulate is essential for a realistic modification of its 3D model. In this paper, we show that such information can be learned from user‐clicked 2D images and a template 3D model of the target animal. We present a volumetric deformation framework that produces a set of new 3D models by deforming a template 3D model according to a set of user‐clicked images. Our framework is based on a novel locally‐bounded deformation energy, where every local region has its own stiffness value that bounds how much distortion is allowed at that location. We jointly learn the local stiffness bounds as we deform the template 3D mesh to match each user‐clicked image. We show that this seemingly complex task can be solved as a sequence of convex optimization problems. We demonstrate the effectiveness of our approach on cats and horses, which are highly deformable and articulated animals. Our framework produces new 3D models of animals that are significantly more plausible than methods without learned stiffness.