Himmelstein J.C.,1312 Labege |
Ferre E.,1312 Labege |
Laumond J.-P.,LAAS CRNS
IEEE Transactions on Automation Science and Engineering | Year: 2010
We present a fast algorithm to approximate the swept volume (SV) boundary of arbitrary polygon soup models. Despite the extensive research on calculating the volume swept by an object along a trajectory, the efficient algorithms described have imposed constraints on both the trajectories and geometric models. By proposing a general algorithm that handles flat surfaces as well as volumes and disconnected objects, we allow SV calculation without resorting to preprocessing mesh repair nor deforming offsets. This is of particular interest in the domain of product lifecycle management (PLM), which deals with industrial computer aided design (CAD) models that are malformed more often than not. We incorporate the bounded distance operator used in path planning to efficiently sample the trajectory while controlling the total error. We develop a triangulation scheme that draws on the unique data set created by an advancing front level-set method to tessellate the SV boundary in linear time. We analyze its performance, and demonstrate its effectiveness both theoretically and on real cases taken from PLM. Note to Practitioners-Swept volumes are useful for collision detection, ergonomics, mechanical assembly, and many other fields. We successfully tested our method on actual industrial models, including a digital actor. Therefore, no additional work is required in order to put our technique into practice for polygon soup models. Additionally, the graphics card is only used in a way that is easily accessible without special GPU programming. © 2009 IEEE.