A multi-threaded algorithm for computing the largest non-colliding moving geometry

E. Shellshear, S. Tafuri, J. S. Carlson, Computer-Aided Design, April, 2014, 49, 1–7.


In this article we present an algorithm to compute the maximum size of an object, in three dimensions, that can move collision-free along a fixed trajectory through a virtual environment. This can be seen as a restricted version of the general problem of computing the maximum size of an object to move collision-free from a start position to a goal position. We compute the maximum size by dividing the object into numerous small boxes and computing which ones collide with the virtual environment during the movement along the given trajectory. The algorithm presented is optimized for multi-threaded computer architectures and also uses data structures that leave a small memory footprint making it suitable for use with large virtual environments (defined by, e.g., millions or billions of points or triangles).


The authors sincerely thank Mathias Sundbäck and Magnus Rönnäng from Volvo Cars for their support and assistance in carrying out this research. We also thank Volvo Cars for their kind allowance of the simulation photos and data used in this paper. This work was carried out at the Wingquist Laboratory VINN Excellence Centre, and is part of the Sustainable Production Initiative and the Production Area of Advance at Chalmers University of Technology. It was supported by the Swedish Governmental Agency for Innovation Systems.

Authors and Affiliations

  • Evan Shellshear, Fraunhofer-Chalmers Centre
  • Sebastian Tafuri, Fraunhofer-Chalmers Centre
  • Johan Carlson, Fraunhofer-Chalmers Centre

Photo credits: Nic McPhee