PDQ: Parallel Distance Queries for deformable meshes

E. Shellshear, F. Bitar, U. Assarsson. Graphical Models, March 2013, 75(2), 69–78.


This paper presents a new algorithm to efficiently maintain Bounding-Volume Hierarchies (BVHs) for fast distance queries with deformable polygon meshes using multi-core architectures. The method involves inflating the bounding volumes in an efficient manner to guarantee the enclosure of the deformable model within the BVH at all times. This is done at low additional computation and memory cost without significantly degrading the quality of the BVH and also in a fashion that allows a simple parallel implementation. Additionally, to facilitate fast queries specifically for deforming meshes, we propose a novel algorithm for the bottom-up construction of BVHs that results in much faster distance queries


This work was supported by the Swedish Governmental Agency for Innovation Systems, VINNOVA through the FFI Sustainable Production Technology Program and the SSF Swedish Foundation for Strategic Research Proviking II program. It is part of the Sustainable Production Initiative and the Production Area of Advance at Chalmers University of Technology. The ben and hand models are from the UTAH 3D Animation Repository.

Authors and Affiliations

  • E. Shellshear, Fraunhofer Chalmers Centre
  • F. Bitar, Fraunhofer Chalmers Centre
  • U. Assarsson, Department of Computer Science and Engineering, Chalmers University of Technology

Photo credits: Nic McPhee