TY - CONF
T1 - Fast swept volume approximation of complex polyhedral models
AU - Kim, Young J.
AU - Varadhan, Gokul
AU - Lin, Ming C.
AU - Manocha, Dinesh
N1 - Funding Information:
This research was supported in part by ARO Contract DAAD 19-99-1-0162, NSF awards ACI-9876914, IIS-982167, ACI-0118743, ONR Contracts N00014-01-1-0067 and N00014-01-1-0496, Intel Corporation, and the Ewha womans university research grant of 2003. We thank Kenny Hoff for his HAVOC software, Leif Kobbelt for providing us with his Extended Marching Cubes software, and Dan Halperin and the reviewers for their feedback and suggestions.
PY - 2003
Y1 - 2003
N2 - 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 five-stage pipeline. This includes computing a bounded-error approximation of each surface primitive, computing unsigned distance fields on a uniform grid, classifying all grid points using fast marching front propagation, iso-surface 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 level-set 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 bounded-error approximation in tens of seconds for models composed of thousands of polygons sweeping along a complex trajectory.
AB - 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 five-stage pipeline. This includes computing a bounded-error approximation of each surface primitive, computing unsigned distance fields on a uniform grid, classifying all grid points using fast marching front propagation, iso-surface 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 level-set 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 bounded-error approximation in tens of seconds for models composed of thousands of polygons sweeping along a complex trajectory.
KW - Distance Fields
KW - Implicit Modeling
KW - Swept Volume
UR - http://www.scopus.com/inward/record.url?scp=0038717916&partnerID=8YFLogxK
U2 - 10.1145/781611.781613
DO - 10.1145/781611.781613
M3 - Paper
AN - SCOPUS:0038717916
SP - 11
EP - 22
T2 - Eighth ACM Symposium on Solid Modeling and Applications
Y2 - 16 June 2003 through 20 June 2003
ER -