Tight and Efficient Surface Bounds in Meshless Animation

Denis Steinemann, Miguel Otaduy, Markus Gross

We present a fast approach for computing tight surface bounds in meshless animation, and its application to collision detection. Given a high-resolution surface animated by a comparatively small number of simulation nodes, we are able to compute tight bounding volumes with a cost linear in the number of simulation nodes. Our approach extends concepts about bounds of convex sets to the meshless deformation setting, and we introduce an efficient algorithm for finding extrema of these convex sets. The extrema can be used for efficiently updating bounding volumes such as AABBs or k-DOPs, as we show in our results.

The choice of particular bounding volume may depend on the complexity of the contact configurations, but in all cases we can compute surface bound orders of magnitude faster and/or tighter than with previous methods. While our approach pays off most in meshless animation, it may also be used for other deformation models where deformation of a surface vertex is defined by a convex combination of affine transformations defined by low-resolution deformation.

• D. Steinemann, M. A. Otaduy, M. Gross, Efficient Bounds for Point-Based Animations, Proceedings of the IEEE/Eurographics Symposium on Point-Based Graphics (Prague, Czech Republic, September 2-3, 2007), pp. 57-64
  [Abstract] [PDF] [Video]
• D. Steinemann, M. Otaduy, M. Gross, Tight and Efficient Surface Bounds in Meshless Animation, Computers & Graphics, Elsevier, vol. 32, no. 2, 2008, pp. 245-255
  [Abstract] [PDF]