Collision detection between point clouds using an efficient k-d tree implementation

Context: An important task in civil engineering is the detection of collisions of a 3D model with an environment representation. Existing methods using the structure gauge provide an insufficient measure because the model either rotates or because the trajectory makes tight turns through narrow passages. This is the case in either automotive assembly lines or in narrow train tunnels.Objective: Given two point clouds, one of the environment and one of a model and a trajectory with six degrees of freedom along which the model moves through the environment, find all colliding points of the environment with the model within a certain clearance radius.Method: This paper presents two collision detection (CD) methods called kd-CD and kd-CD-simple and two penetration depth (PD) calculation methods called kd-PD and kd-PD-fast. All four methods are based on searches in a k-d tree representation of the environment. The creation of the k-d tree, its search methods and other features will be explained in the scope of their use to detect collisions and calculate depths of penetration.Results: The algorithms are benchmarked by moving the point cloud of a train wagon with 2.5 million points along the point cloud of a 1144 m long train track through a narrow tunnel with overall 18.92 million points. Points where the wagon collides with the tunnel wall are visually highlighted with their penetration depth. With a safety margin of 5 cm kd-PD-simple finds all colliding points on its trajectory which is sampled into 19,392 positions in 77 s on a standard desktop machine of 1.6 GHz.Conclusion: The presented methods for collision detection and penetration depth calculation are shown to solve problems for which the structure gauge is an insufficient measure. The underlying k-d tree is shown to be an effective data structure for the required look-up operations.