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

Abstract

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 ex-periments 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.