Automatic clustering method for real-time construction simulation

Simulation of construction activities in a virtual environment can prevent constructability problems and increase efficiency and safety at the physical construction site. The computation for collision checks creates a bottleneck during these simulations. A typical construction simulation requires collision checks to be performed between all pairs among thousands or even millions of objects, and each of these checks must be completed within 1/10th or even 1/20th of a second to provide a smooth real-time simulation. Therefore, the reduction of computational cost is paramount. An effective and commonly used method is to cluster the objects into groups and use a larger surrounding boundary shape in place of the individual objects. This significantly reduces the computational effort required. However, clustering objects manually is usually time consuming and is difficult especially for large scenarios. In this paper, we develop an automatic clustering method, called the Propagation Clustering Method (PCM). PCM employs k-means clustering to iteratively cluster objects into multiple groups. A quality index is defined to evaluate the clustering results. Once the clustering results satisfy the predefined quality requirement, the group of objects is replaced by a rectangular box using the axis-aligned bounding box (AABB) algorithm. The rectangular box is then stored in a tree structure. To verify the feasibility of the proposed PCM, we defined three testing scenarios: a site with scattered objects, such as a small plant construction; a common construction site; and a large site with both common structures and scattered objects. Experimental results show that PCM is effective for automatically grouping objects in virtual construction scenarios. It can significantly reduce the effort required to prepare a construction simulation.