目的 结构化重建，即从离散点云或者原始三角网格中提取几何平面并将其拼接成紧凑的参数化3维模型，一直是计算机图形学领域中极具挑战性的问题。现有方法通常面临着两个挑战。一是传统的形状检测方法通常只考虑物体的局部特征，无法保证整体结果的准确性。二是现有的形状拼接算法往往受限于计算复杂度，从而只能处理由一百多个几何平面组成的物体，极大地限制了算法的应用场景。针对这些问题，提出了一种快速、鲁棒的结构化重建算法以自动地生成轻量的多边形网格。方法 提出了一种多源区域增长算法，全局地从原始3维数据中提取特征平面。该策略保证了原始数据可以被正确地聚类到所属的平面区域。为了减轻几何平面分割3维空间带来的计算负担，采用了一种基于二叉空间分割树的结构将3维空间切分为凸多面体。提出了一种基于光线射击的马尔可夫能量方程以提取水密、无自相交的多边形网格。结果 实验结果表明，本文方法可以在没有并行化方案的标准计算机上处理由上万个几何平面组成的物体。与传统的全相交分割相比，本文方法得到的多面体数目和运行时间都降低了至少两个数量级，总耗时可控制在5 s/万点以内。此外，模型化简前后的均方根误差平均控制在1%以内，面片化简比例控制在1.5%以内。结论 本文方法在计算效率以及结果的准确性上均取得了较大的进步，能够恢复有部分缺陷的表面模型，保留重要结构细节，在复杂性和保真度之间提供了一种较好的方案。

Objective The conception of digital twin has attracted tremendous attention and developed rapidly in the fields of smart cities, smart transportation, urban planning, and virtual/augmented reality during past years. The basic objective is to visualize, analyze, simulate, and optimize real world scenes by projecting physical objects onto digital 3D models. To apply digital twin technology successfully to downstream applications such as real-time rendering, human-scene interaction, and numerical simulation, the reconstructed 3D models should preferably be geometrically accurate, vectorized, highly simplified, free of self-intersection, and watertight. To satisfy these requirements, a potential solution called structured reconstruction method extracts geometric planes from discrete point clouds or original triangular mesh and splices them into a compact parametric 3D model. Previous methods address this problem by detecting geometric shapes and then assembling them into a polygonal mesh, but these methods usually suffer from two obstacles. First, traditional shape detection methods such as region growing algorithm rely on iteratively propagating geometric constraints around selected seeds. This greedy strategy only considers local properties and cannot guarantee the quality of global configuration. Second, current shape assembly methods typically recover the surface model by slicing the 3D space into polyhedral cells and assigning inside-outside labels to each cell. Most of these slicing-based methods preserve a high computational complexity and can hardly process more than 100 shapes. In this paper, a novel automatic approach that generates concise polygonal meshes from point clouds or raw triangular meshes in an efficient, robust manner relying upon three ingredients is proposed. Method Our method consists of three steps:shape detection, space partition, and surface extraction. Our algorithm requires as input a point cloud with oriented normal or triangle mesh. The resulting model is guaranteed to be intersection-free and watertight. First, a multi-source region growing algorithm that detects planar shapes from input 3D data through a global way is proposed. This strategy ensures that points or triangular facets located near the boundary of two shapes can be correctly clustered into their corresponding group. Next, the detected planar shapes are used to partition the bounding box of the object into a polyhedral. To avoid the computational burden involved in the shape assembling step, the partition is performed in a hierarchical manner, that is, the 3D space is recursively divided to build a binary space partitioning (BSP) tree. Starting from the initial bounding box, the largest planar shapes are used to divide a polyhedron cell into two. The planar shapes in the polyhedron are also assigned to the new polyhedron cell. If a shape spans the two polyhedrons, it is divided into two to ensure that every shape in the new polyhedron does not exceed its scope. This operation continues until no divisible polyhedron cell remains. It is equivalent to building a BSP tree. Each leaf node of the BSP tree corresponds to a convex polyhedron cell, and all leaf nodes are combined into the initial bounding box. In such a way, a detected shape only partitions the space locally, without causing redundant partitioning. Hierarchical space partition is the key to reducing the search space and improving the overall pipeline efficiency. Finally, the surface is extracted from the hierarchical partition by labeling each polyhedron as inside or outside the reconstructed model. A ray-shooting-based Markov energy function is defined, and a min-cut is operated to find inside-outside labeling that minimizes the energy function. The output surface is defined as the interface facets between the inside and the outside polyhedral. Result The robustness and the performance of our method are demonstrated on a variety of man-made objects and even large-scale scenes from three aspects of fidelity, complexity, and running time. A large number of experimental results prove that our algorithm can process objects composed of tens of thousands of planar shapes on a standard computer without a parallelization scheme. Compared with traditional slicing methods, the number of polyhedral cells obtained through this simple, robust mechanism and the running time are reduced by at least two orders of magnitude. Approximately 70% of the calculation time is used for space partition, but the total time can be controlled within 5 s/10 000 points. In addition, the root-mean-square(RMS) error of the simplified model is mostly controlled within 1%, and the simplification ratio of the facets is controlled within 1.5%. The proposed method greatly improves the calculation efficiency and accuracy of the results, and provides a good trade-off between complexity and fidelity. Conclusion Our structural mesh reconstruction pipeline consists of three steps:shape detection, space partition, and surface extraction. Our method is especially suitable for models with rich structural features. The resulting model is guaranteed to be watertight and free of self-intersection while preserving the features of the structure. The limitation of this algorithm is that reconstruction quality mainly depends on the result of shape detection, which only considers the individual model and does not take advantage of the statistical information of the whole dataset. In addition, this algorithm is only for reconstructing watertight models. When the input data have a large area of missing parts (such as the bottom of the building data), the algorithm relies on the bounding box to close the surface. In the future, data-driven methods will be explored to improve shape detection and take advantage of the hierarchical partition for levels of detail (LOD) reconstruction.