The Taub Faculty of Computer Science Events and Talks

We present real-time algorithms for various geometric operations (collision detection, minimum and Hausdorff distance computation, surface-surface intersection, convex hull and distance field generation) on freeform geometric models including NURBS curves and surfaces. These algorithms are based on bounding volume hierarchies (BVHs) for freeform shapes, which are considerably more compact than conventional ones for mesh models. For static NURBS models, we often require 1000 times smaller memory space than usual, while observing only a slight degradation of computing speed. A big challenge is how to deal with freeform geometric shapes under continuous deformation. We introduce dynamic bounding volume hierarchies (DBVHs) for these deformable shapes, which assume virtually no preprocessing and thus no extra space for storing the prebuilt data structures. We demonstrate the effectiveness of our approach using several application scenarios.