浏览全部资源
扫码关注微信
收稿日期：2021-07-05，
修回日期：2021-09-22，
录用日期：2021-9-29，
纸质出版日期：2022-02-16
移动端阅览
目的
2
结构化重建，即从离散点云或者原始三角网格中提取几何平面并将其拼接成紧凑的参数化3维模型，一直是计算机图形学领域中极具挑战性的问题。现有方法通常面临着两个挑战。一是传统的形状检测方法通常只考虑物体的局部特征，无法保证整体结果的准确性。二是现有的形状拼接算法往往受限于计算复杂度，从而只能处理由一百多个几何平面组成的物体，极大地限制了算法的应用场景。针对这些问题，提出了一种快速、鲁棒的结构化重建算法以自动地生成轻量的多边形网格。
方法
2
提出了一种多源区域增长算法，全局地从原始3维数据中提取特征平面。该策略保证了原始数据可以被正确地聚类到所属的平面区域。为了减轻几何平面分割3维空间带来的计算负担，采用了一种基于二叉空间分割树的结构将3维空间切分为凸多面体。提出了一种基于光线射击的马尔可夫能量方程以提取水密、无自相交的多边形网格。
结果
2
实验结果表明，本文方法可以在没有并行化方案的标准计算机上处理由上万个几何平面组成的物体。与传统的全相交分割相比，本文方法得到的多面体数目和运行时间都降低了至少两个数量级，总耗时可控制在5 s/万点以内。此外，模型化简前后的均方根误差平均控制在1%以内，面片化简比例控制在1.5%以内。
结论
2
本文方法在计算效率以及结果的准确性上均取得了较大的进步，能够恢复有部分缺陷的表面模型，保留重要结构细节，在复杂性和保真度之间提供了一种较好的方案。
Objective
2
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
2
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
2
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
2
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.
Arikan M, Schwärzler M, Flöry S, Wimmer M and Maierhofer S. 2013. O-snap: optimization-based snapping for modeling architecture. ACM Transactions on Graphics, 32(1): #6[DOI: 10.1145/2421636.2421642]
Barnes C, Shechtman E, Finkelstein A and Goldman D B. 2009. PatchMatch: a randomized correspondence algorithm for structural image editing. ACM Transactions on Graphics, 28(3): #24[DOI: 10.1145/1531326.1531330]
Bauchet J P and Lafarge F. 2020. Kinetic shape reconstruction. ACM Transactions on Graphics, 39(5): #156[DOI: 10.1145/3376918]
Boykov Y and Kolmogorov V. 2004. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(9): 1124-1137[DOI: 10.1109/TPAMI.2004.60]
Chauve A L, Labatut P and Pons J P. 2010. Robust piecewise-planar 3D reconstruction and completion from large-scale unstructured point data//Proceedings of 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Francisco, USA: IEEE: 1261-1268[ DOI: 10.1109/CVPR.2010.5539824 http://dx.doi.org/10.1109/CVPR.2010.5539824 ]
Chen J and Chen B. 2008. Architectural modeling from sparsely scanned range data. International Journal of Computer Vision, 78(2/3): 223-236[DOI: 10.1007/s11263-007-0105-5]
Cohen-Steiner D, Alliez P and Desbrun M. 2004. Variational shape approximation. ACM Transactions on Graphics, 23(3): 905-914[DOI: 10.1145/1015706.1015817]
Fang H, Lafarge F and Desbrun M. 2018. Planar shape detection at structural scales//Proceedings of 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Salt Lake City, USA: IEEE: 2965-2973[ DOI: 10.1109/CVPR.2018.00313 http://dx.doi.org/10.1109/CVPR.2018.00313 ]
Fang H and Lafarge F. 2020. Connect-and-Slice: an hybrid approach for reconstructing 3D objects//Proceedings of 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Seattle, USA: IEEE: 13487-13495[ DOI: 10.1109/CVPR42600.2020.01350 http://dx.doi.org/10.1109/CVPR42600.2020.01350 ]
Furukawa Y and Ponce J. 2010. Accurate, dense, and robust multiview stereopsis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(8): 1362-1376[DOI: 10.1109/TPAMI.2009.161]
Garland M and Heckbert P S. 1997. Surface simplification using quadric error metrics//Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. Los Angeles, USA: ACM: 209-216[ DOI: 10.1145/258734.258849 http://dx.doi.org/10.1145/258734.258849 ]
Hu F Q, Huang Y and Li H. 2020. A review of 3D reconstruction methods applied in buildings. Intelligent Building and Smart City, (5): 10-14
胡芳侨, 黄永, 李惠. 2020. 建筑3维重建方法综述. 智能建筑与智慧城市, (5): 10-14[DOI: 10.13655/j.cnki.ibci.2020.05.005]
Hulik R, Spanel M, Smrz P and Materna Z. 2014. Continuous plane detection in point-cloud data based on 3D Hough transform. Journal of Visual Communication and Image Representation, 25(1): 86-97[DOI: 10.1016/j.jvcir.2013.04.001]
Kaiser A, Ybanez Zepeda J A and Boubekeur T. 2019. A survey of simple geometric primitives detection methods for captured 3D data. Computer Graphics Forum, 38(1): 167-196[DOI: 10.1111/CGF.13451]
Kazhdan M, Bolitho M and Hoppe H. 2006. Poisson surface reconstruction//Proceedings of the 4th Eurographics Symposium on Geometry Processing. Cagliari, Italy: Eurographics Association: 61-70
Lafarge F and Alliez P. 2013. Surface reconstruction through point set structuring. Computer Graphics Forum, 32(2pt2): 225-234
Li M L and Nan L L. 2021. Feature-preserving 3D mesh simplification for urban buildings. ISPRS Journal of Photogrammetry and Remote Sensing, 173: 135-150[DOI: 10.1016/j.isprsjprs.2021.01.006]
Li Y Y, Wu X K, Chrysathou Y, Sharf A, Cohen-Or D and Mitra N J. 2011. GlobFit: consistently fitting primitives by discovering global relations. ACM Transactions on Graphics, 30(4): #52[DOI: 10.1145/2010324.1964947]
Lu Z D, Guo J W, Xiao J, Wang Y, Zhang X P and Yan D M. 2021. Extracting cycle-aware feature curve networks from 3D models. Computer-Aided Design, 131: #102949[DOI: 10.1016/j.cad.2020.102949]
Mehra R, Zhou Q N, Long J, Sheffer A, Gooch A and Mitra N J. 2009. Abstraction of man-made shapes. ACM Transactions on Graphics, 28(5): 1-10[DOI: 10.1145/1618452.1618483]
Mitra N J, Wand M, Zhang H, Cohen-Or D, Kim V and Huang Q X. 2014. Structure-aware shape processing//SIGGRAPH Asia 2013 Courses. Hong Kong, China, ACM: #1[ DOI: 10.1145/2542266.2542267 http://dx.doi.org/10.1145/2542266.2542267 ]
Newcombe R A, Izadi S, Hilliges O, Molyneaux D, Kim D, Davison A J, Kohi P, Shotton J, Hodges S and Fitzgibbon A. 2011. KinectFusion: real-time dense surface mapping and tracking//Proceedings of the 10th IEEE International Symposium on Mixed and Augmented Reality. Basel, Switzerland: IEEE: 127-136[ DOI: 10.1109/ISMAR.2011.6092378 http://dx.doi.org/10.1109/ISMAR.2011.6092378 ]
Salinas D, Lafarge F and Alliez P. 2015. Structure-aware meshdecimation. Computer Graphics Forum, 34(6): 211-227[DOI: 10.1111/cgf.12531]
Schnabel R, Wahl R and Klein R. 2007. Efficient RANSAC for point-cloud shape detection. Computer Graphics Forum, 26(2): 214-226[DOI: 10.1111/j.1467-8659.2007.01016.x]
Shamir A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum, 27(6): 1539-1556[DOI: 10.1111/j.1467-8659.2007.01103.x]
Sharma G, Liu D F, Maji S, Kalogerakis E, Chaudhuri S and Měch R. 2020. ParSeNet: a parametric surface fitting network for 3D point clouds//Proceedings of the 16th European Conference on Computer Vision. Glasgow, UK: Springer: 261-276[ DOI: 10.1007/978-3-030-58571-6_16 http://dx.doi.org/10.1007/978-3-030-58571-6_16 ]
Tulsiani S, Su H, Guibas L J, Efros A A and Malik J. 2017. Learning shape abstractions by assembling volumetric primitives//Proceedings of 2017 IEEE Conference on Computer Vision and Pattern Recognition. Honolulu, USA: IEEE: 1466-1474[ DOI: 10.1109/CVPR.2017.160 http://dx.doi.org/10.1109/CVPR.2017.160 ]
Verdie Y, Lafarge F and Alliez P. 2015. LOD generation for urban scenes. ACM Transactions on Graphics, 34(3): #30[DOI: 10.1145/2732527]
Wu L H and Huang H. 2015. Survey on points-driven computer graphics. Journal of Computer-Aided Design and Computer Graphics, 27(8): 1341-1353
伍龙华, 黄惠. 2015. 点云驱动的计算机图形学综述. 计算机辅助设计与图形学学报, 27(8): 1341-1353[DOI: 10.3969/j.issn.1003-9775.2015.08.001]
Zhang L, Guo J W, Xiao J, Zhang X P and Yan D M. 2020. Blending surface segmentation and editing for 3D models[J/OL]. IEEE Transactions on Visualization and Computer Graphics, https://ieeexplore.ieee.org/document/9296787 https://ieeexplore.ieee.org/document/9296787 [ DOI: 10.1109/TVCG.2020.3045450 http://dx.doi.org/10.1109/TVCG.2020.3045450 ].
相关作者
相关机构
京公网安备11010802024621