Laser scanning is an effective tool for acquiring geometric attributes of trees and vegetation,
which lays a solid foundation for 3-dimensional tree modelling. Existing studies on tree modelling
from laser scanning data are vast. However, some works cannot guarantee sufficient modelling
accuracy, while some other works are mainly rule-based and therefore highly depend on user inputs.
In this paper, we propose a novel method to accurately and automatically reconstruct detailed 3D
tree models from laser scans. We first extract an initial tree skeleton from the input point cloud by
establishing a minimum spanning tree using the Dijkstra shortest-path algorithm. Then, the initial tree
skeleton is pruned by iteratively removing redundant components. After that, an optimization-based
approach is performed to fit a sequence of cylinders to approximate the geometry of the tree branches.
Experiments on various types of trees from different data sources demonstrate the effectiveness and
robustness of our method. The overall fitting error (i.e., the distance between the input points and the
output model) is less than 10 cm. The reconstructed tree models can be further applied in the precise
estimation of tree attributes, urban landscape visualization, etc. The source code of this work is freely
available at https://github.com/tudelft3d/adtree
In 3D printing, it is critical to use as few as possible supporting materials for efficiency
and material saving. Multiple model decomposition methods and multi-DOF (degrees
of freedom) 3D printers have been developed to address this issue. However, most
systems utilize model decomposition and multi-DOF independently. Only a few
existing approaches combine the two, i.e. partitioning the models for multi-DOF
printing. In this paper, we present a novel model decomposition method for multidirectional 3D printing, allowing consistent printing with the least cost of supporting
materials. Our method is based on a global optimization that minimizes the surface
area to be supported for a 3D model. The printing sequence is determined inherently
by minimizing a single global objective function. Experiments on various complex
3D models using a five-DOF 3D printer have demonstrated the effectiveness of our
This paper presents a method for generative design of decorative architectural parts such as corbel,moulding and panel, which
usually have clear structure and aesthetic details. The method is composed of two components: offline learning and online
generation. The offline learning trains a 2D CurveInfoGAN and a 3D VoxelVAE that learn the feature representations of the
parts in a dataset. The online generation proceeds with an evolution procedure that evolves to product new generation of
part components by selecting, crossing over and mutating features, followed by a feature-driven deformation that synthesizes
the 3D mesh representation of new models. Built upon these technical components, a generative design tool is developed,
which allows the user to input a decorative architectural model as a reference and then generates a set of new models that
are “more of the same” as the reference and meanwhile exhibit some “surprising” elements. The experiments demonstrate
the effectiveness of the method and also showcase the use of classic geometric modelling and advanced machine learning
techniques in modelling of architectural parts.
Wenqing OuyangUniversity of Science and Technology of ChinaYue PengUniversity of Science and Technology of ChinaYuxin YaoUniversity of Science and Technology of ChinaJuyong ZhangUniversity of Science and Technology of China Bailin DengCardiff University
Geometric Modeling and Processingmathscidoc:2012.16004
Computer Graphics Forum (Symposium on Geometry Processing), 39, (5), 2020.8
The alternating direction multiplier method (ADMM) is widely used in computer graphics for solving optimization problems that can be nonsmooth and nonconvex. It converges quickly to an approximate solution, but can take a long time to converge to a solution of high‐accuracy. Previously, Anderson acceleration has been applied to ADMM, by treating it as a fixed‐point iteration for the concatenation of the dual variables and a subset of the primal variables. In this paper, we note that the equivalence between ADMM and Douglas‐Rachford splitting reveals that ADMM is in fact a fixed‐point iteration in a lower‐dimensional space. By applying Anderson acceleration to such lower‐dimensional fixed‐point iteration, we obtain a more effective approach for accelerating ADMM. We analyze the convergence of the proposed acceleration method on nonconvex problems, and verify its effectiveness on a variety of computer graphics including geometry processing and physical simulation.
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.