Fast Swept Volume Approximation of Complex Polyhedral Models  
Young J. Kim  youngkim [at] cs [dot] unc [dot] edu  
Gokul Varadhan  varadhan [at] cs [dot] unc [dot] edu  
Ming C. Lin  lin [at] cs [dot] unc [dot] edu  
Dinesh Manocha  dm [at] cs [dot] unc [dot] edu 
Abstract: We present an efficient algorithm to approximate the swept volume (SV) of a complex polyhedron along a given trajectory. Given the boundary description of the polyhedron and a path specified as a parametric curve, our algorithm enumerates a superset of the boundary surfaces of SV. It consists of ruled and developable surface primitives, and the SV corresponds to the outer boundary of their arrangement. We approximate this boundary by using a fivestage pipeline. This includes computing a boundederror approximation of each surface primitive, computing unsigned distance fields on a uniform grid, classifying all grid points using fast marching front propagation, isosurface reconstruction, and topological refinement. We also present a novel and fast algorithm for computing the signed distance of surface primitives as well as a number of techniques based on surface culling, fast marching levelset methods and rasterization hardware to improve the performance of the overall algorithm. We analyze different sources of error in our approximation algorithm and highlight its performance on complex models composed of thousands of polygons. In practice, it is able to compute a boundederror approximation in tens of seconds for models composed of thousands of polygons sweeping along a complex trajectory.
PUBLICATION 
Fast
Swept Volume Approximation of Complex Polyhedral Models Young J. Kim, Gokul Varadhan, Ming C. Lin, and Dinesh Manocha, ACM Symposium on Solid Modeling and Applications, June 1620, 2003. (Awarded the best paper at the ACM Symposium on Solid Modeling and Applications 2003) 
Examples 

RELATED LINKS 
SV Reading List 
last updated: 07/19/2003