An efficient data structure approach for BIM-to-point-cloud change detection using modifiable nested octree

• Published in: Automation in construction 2021-12, Vol.132, p.103922, Article 103922
• Main Authors: Park, Sangyoon, Ju, Sungha, Yoon, Sanghyun, Nguyen, Minh Hieu, Heo, Joon
• Format: Article
• Language: English
• Subjects: Algorithms; BIM; Building information modeling; Building management systems; Change detection; Cloud computing; Complexity; Computer graphics; Data structure; Data structures; Facility management; Octrees; Point cloud
• ISSN: 0926-5805; 1872-7891
• DOI: 10.1016/j.autcon.2021.103922

Change detection between as-planned building information modeling (BIM) and the as-is point cloud requires significant computational overhead because it must deal with every geometric face in the BIM and every point in the point cloud one-to-one. To address this problem, this study presents a high-performance algorithm to detect discrepancies between an as-planned BIM and the as-is point cloud automatically. This method is a data structure approach based on modifiable nested octree indexing of surface meshes and point clouds. The results of experiments showed a significant computation performance improvement: 25.3 and 12.1 times faster than the baseline method for a complex plant facility and a simple indoor building, respectively. Furthermore, it was demonstrated that as the number of meshes in the BIM geometry increased, the time complexity of the proposed approach could be represented as a big O-notation,O(logN), where N is the number of meshes in the BIM geometry. •A data structure approach is developed for BIM-to-Point-Cloud change detection.•BIM geometry and point cloud are indexed with modifiable nested octree based method.•Computation speed of the proposed approach is faster than conventional approaches•The proposed method shows better performance as BIM geometry becomes more complex.