We propose a novel framework for reconstructing lightweight polygonal surfaces from point clouds. Unlike traditional methods that focus on either extracting good geometric primitives or obtaining proper arrangements of primitives, the emphasis of this work lies in intersecting the primitives (planes only) and seeking for an appropriate combination of them to obtain a manifold polygonal surface model without boundary.
We show that reconstruction from point clouds can be cast as a binary labeling problem. Our method is based on a hypothesizing and selection strategy. We ﬁrst generate a reasonably large set of face candidates by intersecting the extracted planar primitives. Then an optimal subset of the candidate faces is selected through optimization. Our optimization is based on a binary linear programming formulation under hard constraints that enforce the ﬁnal polygonal surface model to be manifold and watertight. Experiments on point clouds from various sources demonstrate that our method can generate lightweight polygonal surface models of arbitrary piecewise planar objects. Besides, our method is capable of recovering sharp features and is robust to noise, outliers, and missing data.
Sharp edges are important shape features and their extraction has been extensively studied both on point clouds and surfaces. We consider the problem of extracting sharp edges from a sparse set of colour-and-depth (RGB-D) images. The noise-ridden depth measurements are challenging for existing feature extraction methods that work solely in the geometric domain (e.g. points or meshes). By utilizing both colour and depth information, we propose a novel feature extraction method that produces much cleaner and more coherent feature lines. We make two technical contributions. First, we show that intensity edges can augment the depth map to improve normal estimation and feature localization from a single RGB-D image. Second, we designed a novel algorithm for consolidating feature points obtained from multiple RGB-D images. By utilizing normals and ridge/valley types associated with the feature points, our algorithm is effective in suppressing noise without smearing nearby features.
We present the first computational tool to help ordinary users create transforming pop-up books. In each transforming pop-up, when the user pulls a tab, an initial flat 2D pattern, i.e. a 2D shape with a superimposed picture, such as an airplane, turns into a new 2D pattern, such as a robot, standing up from the page. Given the two 2D patterns, our approach automatically computes a 3D pop-up mechanism that transforms one pattern into the other; it also outputs a design blueprint, allowing the user to easily make the final model. We also present a theoretical analysis of basic transformation mechanisms; combining these basic mechanisms allows more flexibility of final designs. Using our approach, inexperienced users can create models in a short time; previously, even experienced artists often took weeks to manually create them. We demonstrate our method on a variety of real world examples.
Computing centroidal Voronoi tessellations (CVT) has many applications in computer graphics. The existing methods, such as
the Lloyd algorithm and the quasi-Newton solver, are efficient and easy to implement; however, they compute only the local optimal solutions due to the highly non-linear nature of the CVT energy. This paper presents a novel method, called manifold differential evolution (MDE), for computing globally optimal geodesic CVT energy on triangle meshes. Formulating the mutation operator using discrete geodesics, MDE naturally extends the powerful differential evolution framework from Euclidean spaces to manifold domains. Under mild assumptions, we show that MDE has a provable probabilistic convergence to the global optimum. Experiments on a wide range of 3D models show that MDE consistently outperforms the existing methods by producing results with lower energy. Thanks to its intrinsic and global nature, MDE is insensitive to initialization and mesh tessellation. Moreover, it is able to handle multiply-connected Voronoi cells, which are challenging to the existing geodesic CVT methods.
Intrinsic Delaunay triangulation (IDT) naturally generalizes Delaunay triangulation from R^2 to curved surfaces. Due to many favorable properties, the IDT whose vertex set includes all mesh vertices is of particular interest in polygonal mesh processing. To date, the only way for constructing such IDT is the edge-flipping algorithm, which iteratively flips non-Delaunay edges to become locally Delaunay. Although this algorithm is conceptually simple and guarantees to terminate in finite steps, it has no known time complexity and may also produce triangulations containing faces with only two edges. This article develops a new method to obtain proper IDTs on manifold triangle meshes.We first compute a geodesic Voronoi diagram (GVD) by taking all mesh vertices as generators and then find its dual graph. The sufficient condition for the dual graph to be a proper triangulation is that all Voronoi cells satisfy the so-called closed ball property. To guarantee the closed ball property everywhere, a certain sampling criterion is required. For Voronoi cells that violate the closed ball property, we fix them by computing topologically safe regions, inwhich auxiliary sites can be addedwithout changing the topology of theVoronoi diagram beyond them.Given a meshwith n vertices, we prove that by adding at most O(n) auxiliary sites, the computed GVD satisfies the closed ball property, and hence its dual graph is a proper IDT. Our method has a theoretical worst-case time complexity O(n^2 + tn log n), where t is the number of obtuse angles in the mesh. Computational results show that it empirically runs in linear time on real-world models.
We present a real-time approach for acquiring 3D objects with high fidelity using hand-held consumer-level RGB-D scanning
devices. Existing real-time reconstruction methods typically do not take the point of interest into account, and thus might fail
to produce clean reconstruction results of desired objects due to distracting objects or backgrounds. In addition, any changes
in background during scanning, which can often occur in real scenarios, can easily break up the whole reconstruction process. To address these issues, we incorporate visual saliency into a traditional real-time volumetric fusion pipeline. Salient regions detected from RGB-D frames suggest user-intended objects, and by understanding user intentions our approach can put more emphasis on important targets, and meanwhile, eliminate disturbance of non-important objects. Experimental results on real world scans demonstrate that our system is capable of effectively acquiring geometric information of salient objects in cluttered real-world scenes, even if the backgrounds are changing.
We consider the Stokes conjecture concerning the shape of extreme 2-dimensional water waves. By new geometric methods including a non-linear frequency formula, we prove the Stokes conjecture in the original variables. Our results do not rely on structural assumptions needed in previous results such as isolated singularities, symmetry and monotonicity. Part of our results extends to the mathematical problem in higher dimensions.
Min ZhangStony Brook UniversityRen GuoOregon State UniveristyWei ZengSchool of Computing and Information Sciences, Florida International UniversityFeng LuoRutgers UniversityShing Tung YauHarvard UniversityXianfeng GuStony Brook Univerisity
Computational GeometryDifferential GeometryGeometric Modeling and ProcessingConvex and Discrete Geometry mathscidoc:1612.01001
Graphical Models/Geometric Modeling and Processing 2014, 76, (5), 321-339, 2014.9
Ricci ﬂow deformsthe Riemannian metric proportionallyto the curvature, such that the curvatureevolves accordingto a heat diffusion process and eventually becomes constant everywhere. Ricci ﬂow has demonstrated its great potential by solving various problems in many ﬁelds, which can be hardly handled by alternative methods so far. This work introduces the uniﬁed theoretic framework for discrete Surface Ricci Flow, including all the common schemes: Tangential Circle Packing, Thurston’s Circle Packing, Inversive Distance Circle Packing and Discrete Yamabe Flow. Furthermore, this work also introduces a novel schemes, Virtual Radius Circle Packing and the Mixed Type schemes, under the uniﬁed framework. This work gives explicit geometric interpretation to the discrete Ricci energies for all the schemes with all back ground geometries, and the corresponding Hessian matrices. The uniﬁed frame work deepens our understanding to the the discrete surface Ricci ﬂow theory, and has inspired us to discover the new schemes, improved the ﬂexibility and robustness of the algorithms, greatly simpliﬁed the implementation and improved the efﬁciency. Experimental results show the uniﬁed surface Ricci ﬂow algorithms can handle general surfaces with different topologies, and is robust to meshes with different qualities, and is effective for solving real problems.