No abstract uploaded!

We present a framework for generating street networks and parcel layouts. Our goal is the generation of high-quality layouts that can be used for urban planning and virtual environments. We propose a solution based on hierarchical domain splitting using two splitting types: streamline-based splitting, which splits a region along one or multiple streamlines of a cross field, and template-based splitting, which warps pre-designed templates to a region and uses the interior geometry of the template as the splitting lines. We combine these two splitting approaches into a hierarchical framework, providing automatic and interactive tools to explore the design space.

No abstract uploaded!

Forest above-ground biomass (AGB) can be estimated based on light detection and ranging (LiDAR) point clouds. This paper introduces an accurate and detailed quantitative structure model (AdQSM), which can estimate the AGB of large tropical trees. AdQSM is based on the reconstruction of 3D tree models from terrestrial laser scanning (TLS) point clouds. It represents a tree as a set of closed and complete convex polyhedra. We use AdQSM to model 29 trees of various species (total 18 species) scanned by TLS from three study sites (the dense tropical forests of Peru, Indonesia, and Guyana). The destructively sampled tree geometry measurement data is used as reference values to evaluate the accuracy of diameter at breast height (DBH), tree height, tree volume, branch volume, and AGB estimated from AdQSM. After AdQSM reconstructs the structure and volume of each tree, AGB is derived by combining the wood density of the specific tree species from destructive sampling. The AGB estimation from AdQSM and the post-harvest reference measurement data show a satisfying agreement. The coefficient of variation of root mean square error (CV-RMSE) and the concordance correlation coefficient (CCC) are 20.37% and 0.97, respectively. AdQSM provides accurate tree volume estimation, regardless of the characteristics of the tree structure, without major systematic deviations. We compared the accuracy of AdQSM and TreeQSM in modeling the volume of 29 trees. The tree volume from AdQSM is compared with the reference value, and the determination coefficient (R2), relative bias (rBias), and CV-RMSE of tree volume are 0.96, 6.98%, and 22.62%, respectively. The tree volume from TreeQSM is compared with the reference value, and the R2, relative Bias (rBias), and CV-RMSE of tree volume are 0.94, −9.69%, and 23.20%, respectively. The CCCs between the volume estimates based on AdQSM, TreeQSM, and the reference values are 0.97 and 0.96. AdQSM also models the branches in detail. The volume of branches from AdQSM is compared with the destructive measurement reference data. The R2, rBias, and CV-RMSE of the branches volume are 0.97, 12.38%, and 36.86%, respectively. The DBH and height of the harvested trees were used as reference values to test the accuracy of AdQSM’s estimation of DBH and tree height. The R2, rBias, and CV-RMSE of DBH are 0.94, −5.01%, and 9.06%, respectively. The R2, rBias, and CV-RMSE of the tree height were 0.95, 1.88%, and 5.79%, respectively. This paper provides not only a new QSM method for estimating AGB based on TLS point clouds but also the potential for further development and testing of allometric equations.

The goal of urban building mesh simplification is to generate a compact representation of a building from a given mesh. Local smoothness and sharp contours of urban buildings are important features for converting unstructured data into solid models, which should be preserved during the simplification. In this paper, we present a general method to filter and simplify 3D building mesh models, capable of preserving piecewise planar structures and sharp features. Given a building mesh model, a mesh filtering technique is firstly designed to yield piecewise planar regions and extract crease contours. The planar regions are used to constrain the simplification of the mesh. Mesh decimation is achieved through a series of edge collapse operations, which uses regional structural constraints and local geometric error metrics to handle planar and non-planar areas respectively. The proposed method preserves the mesh structure with meaningful levels of detail while reducing the number of faces. The effectiveness of this method is evaluated on various building models generated from different observation scales, and the performance is validated by extensive comparisons to state-of-the-art techniques.

No abstract uploaded!

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.

Cooperative dual-crane lifting is an important but challenging process involved in heavy and critical lifting tasks. This paper considers the path planning for the cooperative dual-crane lifting. It aims to automatically generate optimal dual-crane lifting paths under multiple constraints, i.e., collision avoidance, coordination between the two cranes, and balance of the lifting target. Previous works often used oversimplified models for the dual-crane lifting system, the lifting environment, and the motion of the lifting target. They were thus limited to simple lifting cases and might even lead to unsafe paths in some cases. We develop a novel path planner for dual-crane lifting that can quickly produce optimized paths in complex 3-D environments. The planner has fully considered the kinematic structure of the lifting system. Therefore, it is able to robustly handle the nonlinear movement of the suspended target during lifting. The effectiveness and efficiency of the planner are enabled by three novel aspects: 1) a comprehensive and computationally efficient mathematical modeling of the lifting system; 2) a new multiobjective parallel genetic algorithm designed to solve the path planning problem; and 3) a new efficient approach to perform continuous collision detection for the dual-crane lifting target. The planner has been tested in complex industrial environments. The results show that the planner can generate dual-crane lifting paths that are easy for conductions and optimized in terms of costs for complex environments. Comparisons with two previous methods demonstrate the advantages of the planner, including safer paths, higher success rates, and the ability to handle general lifting cases.

No abstract uploaded!

Ricci flow deformsthe Riemannian metric proportionallyto the curvature, such that the curvatureevolves accordingto a heat diffusion process and eventually becomes constant everywhere. Ricci flow has demonstrated its great potential by solving various problems in many fields, which can be hardly handled by alternative methods so far. This work introduces the unified 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 unified 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 unified frame work deepens our understanding to the the discrete surface Ricci flow theory, and has inspired us to discover the new schemes, improved the flexibility and robustness of the algorithms, greatly simplified the implementation and improved the efficiency. Experimental results show the unified surface Ricci flow algorithms can handle general surfaces with different topologies, and is robust to meshes with different qualities, and is effective for solving real problems.

No abstract uploaded!

We present a general computational framework to locally characterize any shape space of meshes implicitly prescribed by a collection of non-linear constraints. We computationally access such manifolds, typically of high dimension and co-dimension, through first and second order approximants, namely tangent spaces and quadratically parameterized osculant surfaces. Exploration and navigation of desirable subspaces of the shape space with regard to application specific quality measures are enabled using approximants that are intrinsic to the underlying manifold and directly computable in the parameter space of the osculant surface. We demonstrate our framework on shape spaces of planar quad (PQ) meshes, where each mesh face is constrained to be (nearly) planar, and circular meshes, where each face has a circumcircle. We evaluate our framework for navigation and design exploration on a variety of inputs, while keeping context specific properties such as fairness, proximity to a reference surface, etc.

3D scene modeling has long been a fundamental problem in computer graphics and computer vision. With the popularity of consumer-level RGB-D cameras, there is a growing interest in digitizing real-world indoor 3D scenes. However, modeling indoor 3D scenes remains a challenging problem because of the complex structure of interior objects and poor quality of RGB-D data acquired by consumer-level sensors. Various methods have been proposed to tackle these challenges. In this survey, we provide an overview of recent advances in indoor scene modeling techniques, as well as public datasets and code libraries which can facilitate experiments and evaluation.

We introduce a novel approach for the polygonization of Multi-view Stereo (MVS) meshes of buildings, which results in compact and topologically valid models. The main characteristic of our method is structure awareness, i.e., the recovery and preservation of the initial mesh primitives and their adjacencies. Our proposed methodology consists of three main stages: (a) primitive detection via mesh segmentation, (b) encoding of primitive adjacencies into a graph, and (c) polygonization. Polygonization is based on the approximation of the original mesh with a candidate set of planar polygonal faces. On this candidate set, we apply a binary labelling formulation to select and assemble an optimal set of faces under hard constraints that ensure that the final model is both manifold and watertight. Experiments on various building models demonstrate that our simplification method can produce simpler representations for both closed and open building meshes. Furthermore, these representations highly conform to the initial structure and are ready to be used for spatial analysis. The source code of this work is freely available at https://github.com/VasileiosBouzas/MeshPolygonization.

No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

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.

No abstract uploaded!

No abstract uploaded!

We present a novel remeshing algorithm that avoids triangles with small (acute) angles and those with large (obtuse) angles. Our solution is based on an extension of Centroidal Voronoi Tesselation (CVT).We augment the original CVT formulation with a penalty term that penalizes short Voronoi edges, while the CVT term helps to avoid small angles. Our results show significant improvements in remeshing quality over the state of the art.

No abstract uploaded!

The alternating direction method of multipliers (ADMM) is a popular approach for solving optimization problems that are potentially non-smooth and with hard constraints. It has been applied to various computer graphics applications, including physical simulation, geometry processing, and image processing. However, ADMM can take a long time to converge to a solution of high accuracy. Moreover, many computer graphics tasks involve non-convex optimization, and there is often no convergence guarantee for ADMM on such problems since it was originally designed for convex optimization. In this paper, we propose a method to speed up ADMM using Anderson acceleration, an established technique for accelerating fixed-point iterations. We show that in the general case, ADMM is a fixed-point iteration of the second primal variable and the dual variable, and Anderson acceleration can be directly applied. Additionally, when the problem has a separable target function and satisfies certain conditions, ADMM becomes a fixed-point iteration of only one variable, which further reduces the computational overhead of Anderson acceleration. Moreover, we analyze a particular non-convex problem structure that is common in computer graphics, and prove the convergence of ADMM on such problems under mild assumptions. We apply our acceleration technique on a variety of optimization problems in computer graphics, with notable improvement on their convergence speed.

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.

In this paper, we tackle the problem of tiling a domain with a set of deformable templates. A valid solution to this problem completely covers the domain with templates such that the templates do not overlap. We generalize existing specialized solutions and formulate a general layout problem by modeling important constraints and admissible template deformations. Our main idea is to break the layout algorithm into two steps: a discrete step to lay out the approximate template positions and a continuous step to refine the template shapes. Our approach is suitable for a large class of applications, including floorplans, urban layouts, and arts and design.