Optimal Spline Approximation via ℓ0‐Minimization

Splines are part of the standard toolbox for the approximation of functions and curves in ?^d. Still, the problem of finding the spline that best approximates an input function or curve is ill‐posed, since in general this yields a “spline” with an infinite number of segments. The problem can be regularized by adding a penalty term for the number of spline segments. We show how this idea can be formulated as an ?₀‐regularized quadratic problem. This gives us a notion of optimal approximating splines that depend on one parameter, which weights the approximation error against the number of segments. We detail this concept for different types of splines including B‐splines and composite Bézier curves. Based on the latest development in the field of sparse approximation, we devise a solver for the resulting minimization problems and show applications to spline approximation of planar and space curves and to spline conversion of motion capture data.     

Scale‐Invariant Directional Alignment of Surface Parametrizations

Various applications of global surface parametrization benefit from the alignment of parametrization isolines with principal curvature directions. This is particularly true for recent parametrization‐based meshing approaches, where this directly translates into a shape‐aware edge flow, better approximation quality, and reduced meshing artifacts. Existing methods to influence a parametrization based on principal curvature directions suffer from scale‐dependence, which implies the necessity of parameter variation, or try to capture complex directional shape features using simple 1D curves. Especially for non‐sharp features, such as chamfers, fillets, blends, and even more for organic variants thereof, these abstractions can be unfit. We present a novel approach which respects and exploits the 2D nature of such directional feature regions, detects them based on coherence and homogeneity properties, and controls the parametrization process accordingly. This approach enables us to provide an intuitive, scale‐invariant control parameter to the user. It also allows us to consider non‐local aspects like the topology of a feature, enabling further improvements. We demonstrate that, compared to previous approaches, global parametrizations of higher quality can be generated without user intervention.     

3D Skeletons: A State‐of‐the‐Art Report

Given a shape, a skeleton is a thin centered structure which jointly describes the topology and the geometry of the shape. Skeletons provide an alternative to classical boundary or volumetric representations, which is especially effective for applications where one needs to reason about, and manipulate, the structure of a shape. These skeleton properties make them powerful tools for many types of shape analysis and processing tasks. For a given shape, several skeleton types can be defined, each having its own properties, advantages, and drawbacks. Similarly, a large number of methods exist to compute a given skeleton type, each having its own requirements, advantages, and limitations. While using skeletons for two‐dimensional (2D) shapes is a relatively well covered area, developments in the skeletonization of three‐dimensional (3D) shapes make these tasks challenging for both researchers and practitioners. This survey presents an overview of 3D shape skeletonization. We start by presenting the definition and properties of various types of 3D skeletons. We propose a taxonomy of 3D skeletons which allows us to further analyze and compare them with respect to their properties. We next overview methods and techniques used to compute all described 3D skeleton types, and discuss their assumptions, advantages, and limitations. Finally, we describe several applications of 3D skeletons, which illustrate their added value for different shape analysis and processing tasks.     

Learning 3D Scene Synthesis from Annotated RGB‐D Images

We present a data‐driven method for synthesizing 3D indoor scenes by inserting objects progressively into an initial, possibly, empty scene. Instead of relying on few hundreds of hand‐crafted 3D scenes, we take advantage of existing large‐scale annotated RGB‐D datasets, in particular, the SUN RGB‐D database consisting of 10,000+ depth images of real scenes, to form the prior knowledge for our synthesis task. Our object insertion scheme follows a co‐occurrence model and an arrangement model, both learned from the SUN dataset. The former elects a highly probable combination of object categories along with the number of instances per category while a plausible placement is defined by the latter model. Compared to previous works on probabilistic learning for object placement, we make two contributions. First, we learn various classes of higher‐order object‐object relations including symmetry, distinct orientation, and proximity from the database. These relations effectively enable considering objects in semantically formed groups rather than by individuals. Second, while our algorithm inserts objects one at a time, it attains holistic plausibility of the whole current scene while offering controllability through progressive synthesis. We conducted several user studies to compare our scene synthesis performance to results obtained by manual synthesis, state‐of‐the‐art object placement schemes, and variations of parameter settings for the arrangement model.     

Real‐time Bas‐Relief Generation from Depth‐and‐Normal Maps on GPU

To design a bas‐relief from a 3D scene is an inherently interactive task in many scenarios. The user normally needs to get instant feedback to select a proper viewpoint. However, current methods are too slow to facilitate this interaction. This paper proposes a two‐scale bas‐relief modeling method, which is computationally efficient and easy to produce different styles of bas‐reliefs. The input 3D scene is first rendered into two textures, one recording the depth information and the other recording the normal information. The depth map is then compressed to produce a base surface with level‐of‐depth, and the normal map is used to extract local details with two different schemes. One scheme provides certain freedom to design bas‐reliefs with different visual appearances, and the other provides a control over the level of detail. Finally, the local feature details are added into the base surface to produce the final result. Our approach allows for real‐time computation due to its implementation on graphics hardware. Experiments with a wide range of 3D models and scenes show that our approach can effectively generate digital bas‐reliefs in real time.     

Real‐Time Symmetry‐Preserving Deformation

In this paper, we address the problem of structure‐aware shape deformation: We specifically consider deformations that preserve symmetries of the shape being edited. While this is an elegant approach for obtaining plausible shape variations from minimal assumptions, a straightforward optimization is numerically expensive and poorly conditioned. Our paper introduces an explicit construction of bases of linear spaces of shape deformations that exactly preserve symmetries for any user‐defined level of detail. This permits the construction of low‐dimensional spaces of low‐frequency deformations that preserve the symmetries. We obtain substantial speed‐ups over alternative approaches for symmetry‐preserving shape editing due to (i) the sub‐space approach, which permits low‐res editing, (ii) the removal of redundant, symmetric information, and (iii) the simplification of the numerical formulation due to hard‐coded symmetry preservation. We demonstrate the utility in practice by applying our framework to symmetry‐preserving co‐rotated iterative Laplace surface editing of models with complex symmetry structure, including partial and nested symmetry.     

Non‐Rigid Puzzles

Shape correspondence is a fundamental problem in computer graphics and vision, with applications in various problems including animation, texture mapping, robotic vision, medical imaging, archaeology and many more. In settings where the shapes are allowed to undergo non‐rigid deformations and only partial views are available, the problem becomes very challenging. To this end, we present a non‐rigid multi‐part shape matching algorithm. We assume to be given a reference shape and its multiple parts undergoing a non‐rigid deformation. Each of these query parts can be additionally contaminated by clutter, may overlap with other parts, and there might be missing parts or redundant ones. Our method simultaneously solves for the segmentation of the reference model, and for a dense correspondence to (subsets of) the parts. Experimental results on synthetic as well as real scans demonstrate the effectiveness of our method in dealing with this challenging matching scenario.     

Polyline‐sourced Geodesic Voronoi Diagrams on Triangle Meshes

This paper studies the Voronoi diagrams on 2‐manifold meshes based on geodesic metric (a.k.a. geodesic Voronoi diagrams or GVDs), which have polyline generators. We show that our general setting leads to situations more complicated than conventional 2D Euclidean Voronoi diagrams as well as point‐source based GVDs, since a typical bisector contains line segments, hyperbolic segments and parabolic segments. To tackle this challenge, we introduce a new concept, called local Voronoi diagram (LVD), which is a combination of additively weighted Voronoi diagram and line‐segment Voronoi diagram on a mesh triangle. We show that when restricting on a single mesh triangle, the GVD is a subset of the LVD and only two types of mesh triangles can contain GVD edges. Based on these results, we propose an efficient algorithm for constructing the GVD with polyline generators. Our algorithm runs in O(nNlogN) time and takes O(nN) space on an n‐face mesh with m generators, where N = max{m, n}. Computational results on real‐world models demonstrate the efficiency of our algorithm.     

Projective Feature Learning for 3D Shapes with Multi‐View Depth Images

Feature learning for 3D shapes is challenging due to the lack of natural paramterization for 3D surface models. We adopt the multi‐view depth image representation and propose Multi‐View Deep Extreme Learning Machine (MVD‐ELM) to achieve fast and quality projective feature learning for 3D shapes. In contrast to existing multi‐view learning approaches, our method ensures the feature maps learned for different views are mutually dependent via shared weights and in each layer, their unprojections together form a valid 3D reconstruction of the input 3D shape through using normalized convolution kernels. These lead to a more accurate 3D feature learning as shown by the encouraging results in several applications. Moreover, the 3D reconstruction property enables clear visualization of the learned features, which further demonstrates the meaningfulness of our feature learning.     

Harmonic Functions for Rotational Symmetry Vector Fields

Representing rotational symmetry vector as a set of vectors is not suitable for design due to lacking of a consistent ordering for measurement. In this paper we introduce a spectral method to find rotation invariant harmonic functions for symmetry vector field design. This method is developed for 3D vector fields, but it is applicable in 2D. Given the finite symmetry group G of a symmetry vector field v (x) on a 3D domain Ω, we formulate the harmonic function h(s) as a stationary point of group G. Using the real spherical harmonic (SH) bases, we showed the coefficients of the harmonic functions are an eigenvector of the SH rotation matrices corresponding to group G. Instead of solving eigen problems to obtain the eigenvector, we developed a forward constructive method based on orthogonal group theory. The harmonic function found by our method is not only invariant under G, but also expressive and can distinguish different rotations with respect to G. At last, we demonstrate some vector field design results with tetrahedron‐symmetry, cube‐symmetry and dodecahedron‐symmetry groups.     

Fast and Memory‐Efficient Voronoi Diagram Construction on Triangle Meshes

Geodesic based Voronoi diagrams play an important role in many applications of computer graphics. Constructing such Voronoi diagrams usually resorts to exact geodesics. However, exact geodesic computation always consumes lots of time and memory, which has become the bottleneck of constructing geodesic based Voronoi diagrams. In this paper, we propose the window‐VTP algorithm, which can effectively reduce redundant computation and save memory. As a result, constructing Voronoi diagrams using the proposed window‐VTP algorithm runs 3–8 times faster than Liu et al.'s method [ LCT11 ], 1.2 times faster than its FWP‐MMP variant and more importantly uses 10–70 times less memory than both of them.     

Pseudo‐Spline Subdivision Surfaces

Pseudo‐splines provide a rich family of subdivision schemes with a wide range of choices that meet various demands for balancing the approximation power, the length of the support, and the regularity of the limit functions. Special cases of pseudo‐splines include uniform odd‐degree B‐splines and the interpolatory 2n‐point subdivision schemes, and the other pseudo‐splines fill the gap between these two families. In this paper we show how the refinement step of a pseudo‐spline subdivision scheme can be implemented efficiently using repeated local operations, which require only the data in the direct neighbourhood of each vertex, and how to generalize this concept to quadrilateral meshes with arbitrary topology. The resulting pseudo‐spline surfaces can be arbitrarily smooth in regular mesh regions and C¹ at extraordinary vertices as our numerical analysis reveals.     

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.     

Feature‐Preserving Surface Completion Using Four Points

We present a user‐guided, semi‐automatic approach to completing large holes in a mesh. The reconstruction of the missing features in such holes is usually ambiguous. Thus, unsupervised methods may produce unsatisfactory results. To overcome this problem, we let the user indicate constraints by providing merely four points per important feature curve on the mesh. Our algorithm regards this input as an indication of an important broken feature curve. Our completion is formulated as a global energy minimization problem, with user‐defined spatial‐coherence constraints, allows for completion that adheres to the existing features. We demonstrate the method on example problems that are not handled satisfactorily by fully automatic methods.     

A Multi‐sided Bézier Patch with a Simple Control Structure

A new n‐sided surface scheme is presented, that generalizes tensor product Bézier patches. Boundaries and corresponding cross‐derivatives are specified as conventional Bézier surfaces of arbitrary degrees. The surface is defined over a convex polygonal domain; local coordinates are computed from generalized barycentric coordinates; control points are multiplied by weighted, biparametric Bernstein functions. A method for interpolating a middle point is also presented. This Generalized Bézier (GB) patch is based on a new displacement scheme that builds up multi‐sided patches as a combination of a base patch, n displacement patches and an interior patch; this is considered to be an alternative to the Boolean sum concept. The input ribbons may have different degrees, but the final patch representation has a uniform degree. Interior control points—other than those specified by the user—are placed automatically by a special degree elevation algorithm. GB patches connect to adjacent Bézier surfaces with G¹continuity. The control structure is simple and intuitive; the number of control points is proportional to those of quadrilateral control grids. The scheme is introduced through simple examples; suggestions for future work are also discussed.     

Hybrid Particle‐grid Modeling for Multi‐scale Droplet/Spray Simulation

This paper presents a novel hybrid particle‐grid method that tightly couples Lagrangian particle approach with Eulerian grid approach to simulate multi‐scale diffuse materials varying from disperse droplets to dissipating spray and their natural mixture and transition, originated from a violent (high‐speed) liquid stream. Despite the fact that Lagrangian particles are widely employed for representing individual droplets and Eulerian grid‐based method is ideal for volumetric spray modeling, using either one alone has encountered tremendous difficulties when effectively simulating droplet/spray mixture phenomena with high fidelity. To ameliorate, we propose a new hybrid model to tackle such challenges with many novel technical elements. At the geometric level, we employ the particle and density field to represent droplet and spray respectively, modeling their creation from liquid as well as their seamless transition. At the physical level, we introduce a drag force model to couple droplets and spray, and specifically, we employ Eulerian method to model the interaction among droplets and marry it with the widely‐used Lagrangian model. Moreover, we implement our entire hybrid model on CUDA to guarantee the interactive performance for high‐effective physics‐based graphics applications. The comprehensive experiments have shown that our hybrid approach takes advantages of both particle and grid methods, with convincing graphics effects for disperse droplets and spray simulation.     

Semi‐Automatic Conversion of 3D Shape into Flat‐Foldable Polygonal Model

This paper presents a method that can convert a given 3D mesh into a flat‐foldable model consisting of rigid panels. A previous work proposed a method to assist manual design of a single component of such flat‐foldable model, consisting of vertically‐connected side panels as well as horizontal top and bottom panels. Our method semi‐automatically generates a more complicated model that approximates the input mesh with multiple convex components. The user specifies the folding direction of each convex component and the fidelity of shape approximation. Given the user inputs, our method optimizes shapes and positions of panels of each convex component in order to make the whole model flat‐foldable. The user can check a folding animation of the output model. We demonstrate the effectiveness of our method by fabricating physical paper prototypes of flat‐foldable models.     

Skeleton‐driven Adaptive Hexahedral Meshing of Tubular Shapes

We propose a novel method for the automatic generation of structured hexahedral meshes of articulated 3D shapes. We recast the complex problem of generating the connectivity of a hexahedral mesh of a general shape into the simpler problem of generating the connectivity of a tubular structure derived from its curve‐skeleton. We also provide volumetric subdivision schemes to nicely adapt the topology of the mesh to the local thickness of tubes, while regularizing per‐element size. Our method is fast, one‐click, easy to reproduce, and it generates structured meshes that better align to the branching structure of the input shape if compared to previous methods for hexa mesh generation.