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.
For the purpose of isogeometric analysis, one of the most common ways is to construct structured hexahedral meshes, which have regular tensor product structure, and fit them by volumetric T-Splines. This theoretic work proposes a novel surface quadrilateral meshing method, colorable quad-mesh, which leads to the structured hexahedral mesh of the enclosed volume for high genus surfaces.
The work proves the equivalence relations among colorable quad-meshes, finite measured foliations and Strebel differentials on surfaces. This trinity theorem lays down the theoretic foundation for quadrilateral/hexahedral mesh generation, and leads to practical, automatic algorithms.
The work proposes the following algorithm: the user inputs a set of disjoint, simple loops on a high genus surface, and specifies a height parameter for each loop; a unique Strebel differential is computed with the combinatorial type and the heights prescribed by the user’s input; the Strebel differential assigns a flat metric on the surface and decomposes the surface into cylinders; a colorable quad-mesh is generated by splitting each cylinder into two quadrilaterals, followed by subdivision; the surface cylindrical decomposition is extended inward to produce a solid cylindrical decomposition of the volume; the hexadhedral meshing is generated for each volumetric cylinder and then glued together to form a globally consistent hex-mesh.
The method is rigorous, geometric, automatic and conformal to the geometry. This work focuses on the theoretic aspects of the framework, the algorithmic details and practical evaluations will be given in the future expositions.
Zhang H, Wu C, Zhang J, et al. Variational Mesh Denoising Using Total Variation and Piecewise Constant Function Space[J]. IEEE Transactions on Visualization and Computer Graphics, 2015, 21(7): 873-886.
Xu L, Wang R, Zhang J, et al. Survey on sparsity in geometric modeling and processing[J]. Graphical Models \\/graphical Models and Image Processing \\/computer Vision, Graphics, and Image Processing, 2015: 160-180.
Sun Y, Schaefer S, Wang W, et al. Denoising point sets via L 0 minimization[J]. Computer Aided Geometric Design, 2015: 2-15.
Wang X, Hu J, Zhang D, et al. Efficient EMD and Hilbert spectra computation for 3D geometry processing and analysis via space-filling curve[J]. The Visual Computer, 2015: 1135-1145.
Lei Xiao · Felix Heide · Matthew Otoole · Andreas Kolb · Matthias B Hullin · Kyros Kutulakos · Wolfgang Heidrich. Defocus deblurring and superresolution for time-of-flight depth cameras. 2015.
Zhang W, Deng B, Zhang J, et al. Guided Mesh Normal Filtering[J]. Computer Graphics Forum, 2015, 34(7): 23-34.
Lu X, Deng Z, Chen W, et al. A Robust Scheme for Feature-Preserving Mesh Denoising[J]. IEEE Transactions on Visualization and Computer Graphics, 2016, 22(3): 1181-1194.
Yang C, Li S, Lan Y, et al. Coupling time-varying modal analysis and FEM for real-time cutting simulation of objects with multi-material sub-domains[J]. Computer Aided Geometric Design, 2016: 53-67.
Wu X, Zheng J, Cai Y, et al. Mesh Denoising using Extended ROF Model with L1 Fidelity[J]. Computer Graphics Forum, 2015, 34(7): 35-45.
Linlin Xu · Ruimin Wang · Zhouwang Yang · Jiansong Deng · Falai Chen · Ligang Liu. Surface approximation via sparse representation and parameterization optimization. 2016.
Wang Y, Jacobson A, Barbic J, et al. Linear subspace design for real-time shape deformation[J]. ACM Transactions on Graphics, 2015, 34(4).
Xu L, Wang R, Zhang J, et al. Survey on sparsity in geometric modeling and processing[J]. Graphical Models \\/graphical Models and Image Processing \\/computer Vision, Graphics, and Image Processing, 2015: 160-180.
Kosinka J, Bartoň M. Convergence of barycentric coordinates to barycentric kernels[J]. Computer Aided Geometric Design, 2016: 200-210.
Dmitry Anisimov · Chongyang Deng · K Hormann. Subdividing barycentric coordinates. 2016.
Philipp Von Radziewsky · Elmar Eisemann · Hanspeter Seidel · Klaus Hildebrandt. Optimized subspaces for deformation-based modeling and shape interpolation. 2016.
The polygonal approximation problem is a primary problem in computer graphics, pattern recognition, CAD/CAM, etc. In $R^2$, the cone intersection method (CIM) is one of the most eÆcient algorithms for approximating polygonal curves. With CIM Eu and Toussaint, by imposing an additional constraint and changing the given error criteria, resolve the three-dimensional weighted minimum number polygonal approximation problem with the parallel-strip error criterion (PS-WMN) under $L_2$ norm. In this paper, without any additional constraint and change of the error criteria, a CIM solution to the same problem with the line segment error criterion (LS-WMN) is presented, which is more frequently encountered than the PS-WMN is. Its time complexity is $O(n^3)$, and the space complexity is $O(n^2)$. An approximation algorithm is also presented, which takes $O(n^2)$ time and $O(n)$ space. Results of some examples are given to illustrate the eÆciency of these algorithms.
In this paper, we introduce a surface reconstruction method that can perform gracefully with non-uniformly-distributed, noisy, and
even sparse data. We reconstruct the surface by estimating an implicit function and then obtain a triangle mesh by extracting an iso-surface from it. Our implicit function takes advantage of both the indicator function and
the signed distance function. It is dominated by the indicator function
at the regions away from the surface and approximates (up to scaling)
the signed distance function near the surface. On one hand,
it is well defined over the entire space so that the extracted iso-surface
must lie near the underlying true surface and is free of spurious sheets.
On the other hand, thanks to the nice properties of the signed distance
function, a smooth iso-surface can be extracted using the approach of
marching cubes with simple linear interpolations.
More importantly, our implicit function can be estimated directly from
an explicit integral formula without solving any linear system.
This direct approach leads to a simple, accurate and robust reconstruction method,
which can be paralleled with little overhead.
We call our reconstruction method Gauss surface reconstruction.
We apply our method to both synthetic and real-world scanned
data and demonstrate the accuracy, robustness and efficiency of
our method. The performance of Gauss surface reconstruction is also compared with that of
several state-of-the-art methods.
We propose a framework for global registration of building scans. The first contribution of our work is to detect and use portals (e.g. doors and windows) to improve the local registration between two scans. Our second contribution is an optimization based on a linear integer programming formulation. We abstract each scan as a block and model the block registration as an optimization problem that aims at maximizing the overall matching score of the entire scene. We propose an efficient solution to this optimization problem by iteratively detecting and adding local constraints. We demonstrate the effectiveness of the proposed method on buildings of various styles and we show that our approach is superior to the current state of the art.
Manhattan-world urban scenes are common in the real world.
We propose a fully automatic approach for reconstructing such scenes
from 3D point samples. Our key idea is to represent the geometry of the
buildings in the scene using a set of well-aligned boxes. We first extract
plane hypothesis from the points followed by an iterative refinement step.
Then, candidate boxes are obtained by partitioning the space of the point
cloud into a non-uniform grid. After that, we choose an optimal subset of
the candidate boxes to approximate the geometry of the buildings. The
contribution of our work is that we transform scene reconstruction into a
labeling problem that is solved based on a novel Markov Random Field
formulation. Unlike previous methods designed for particular types of
input point clouds, our method can obtain faithful reconstructions from
a variety of data sources. Experiments demonstrate that our method is
superior to state-of-the-art methods.
Object proposals are currently used for increasing the computational efficiency of object detection. We propose a novel adaptive
pipeline for interleaving object proposals with object classification and use it as a formulation for asset detection. We first preprocess the images using a novel and efficient rectification technique. We then employ a particle filter approach to keep track of three priors, which guide proposed samples and get updated using classifier output. Tests performed on over 1000 urban images demonstrate that our rectification method is faster than existing methods without loss in quality, and that our interleaved proposal method outperforms current state-of-the-art. We further demonstrate that other methods can be improved by incorporating our interleaved proposals.
Man-made objects usually exhibit descriptive curved features (i.e., curve networks). The curve network of an object conveys
its high-level geometric and topological structure. We present a framework for extracting feature curve networks from unstructured point
cloud data. Our framework ﬁrst generates a set of initial curved segments ﬁtting highly curved regions. We then optimize these curved
segments to respect both data ﬁtting and structural regularities. Finally, the optimized curved segments are extended and connected
into curve networks using a clustering method. To facilitate effectiveness in case of severe missing data and to resolve ambiguities, we
develop a user interface for completing the curve networks. Experiments on various imperfect point cloud data validate the effectiveness
of our curve network extraction framework. We demonstrate the usefulness of the extracted curve networks for surface reconstruction
from incomplete point clouds.
Minglei LiInstitute of Remote Sensing and Digital Earth, Chinese Academy of Sciences, ChinaLiangliang NanKAUST, KSAShaochuang LiuInstitute of Remote Sensing and Digital Earth, Chinese Academy of Sciences, China
Geometric Modeling and Processingmathscidoc:1608.16113
International Journal of Digital Earth, 9, (8), 2016
We propose an approach for automatic generation of building models by assembling a
set of boxes using a Manhattan-world assumption. The method first aligns the point
cloud with a per-building local coordinate system, and then ts axis-aligned planes to
the point cloud through an iterative regularization process. The refined planes partition
the space of the data into a series of compact cubic cells (candidate boxes) spanning the
entire 3D space of the input data. We then choose to approximate the target building
by the assembly of a subset of these candidate boxes using a binary linear programming
formulation. The objective function is designed to maximize the point cloud coverage
and the compactness of the final model. Finally, all selected boxes are merged into
a lightweight polygonal mesh model, which is suitable for interactive visualization of
large scale urban scenes. Experimental results and a comparison with state-of-the-art
methods demonstrate the effectiveness of the proposed framework.
We present an automatic reconstruction pipeline for large scale urban scenes from aerial images captured by a camera mounted on
an unmanned aerial vehicle. Using state-of-the-art Structure from Motion and Multi-View Stereo algorithms, we ﬁrst generate a
dense point cloud from the aerial images. Based on the statistical analysis of the footprint grid of the buildings, the point cloud
is classiﬁed into different categories (i.e., buildings, ground, trees, and others). Roof structures are extracted for each individual
building using Markov random ﬁeld optimization. Then, a contour reﬁnement algorithm based on pivot point detection is utilized
to reﬁne the contour of patches. Finally, polygonal mesh models are extracted from the reﬁned contours. Experiments on various
scenes as well as comparisons with state-of-the-art reconstruction methods demonstrate the effectiveness and robustness of the
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.
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.
We present an algorithm for recognition and reconstruction of scanned 3D indoor scenes. 3D indoor reconstruction is particularly challenging due to object interferences, occlusions and overlapping which yield incomplete yet very complex scene arrangements. Since it is hard to assemble scanned segments into complete models, traditional methods for object recognition and reconstruction would be inefficient. We present a search-classify approach which interleaves segmentation and classification in an iterative manner. Using a robust classifier we traverse the scene and gradually propagate classification information. We reinforce classification by a template fitting step which yields a scene reconstruction. We deform-to-fit templates to classified objects to resolve classification ambiguities. The resulting reconstruction is an approximation which captures the general scene arrangement. Our results demonstrate successful classification and reconstruction of cluttered indoor scenes, captured in just few minutes.