Fast construction of 2D offset curve based on distance field
QIN Rui1,2, LIU Shengjun1,2, CHEN Zitai1,2, YUAN Weixiong1,2, ZHANG Fan1,2, LIU Xinru1,2
1. Institute of Engineering Modeling and Scientific Computing, Central South University, Changsha 410083, China;
2. School of Mathematics and Statistics, Central South University, Changsha 410083, China
Abstract：A fast approach of generating a 2D offset curve from any polygonal curve is presented, which preserves sharp features and is self-intersection free. The basic idea is first to establish a local signed distance field on a uniform grid according to the input curve and then employ a contouring algorithm to extract the offset curve from the distance field. Three filters are conducted to generate a narrowband signed distance field around the offset curve in a very efficient way to reduce computation redundancies in regions far from the offset curves. The initial offset curve is derived by a traditional MS (Marching Square) method, the accurate intersections between the grid edges and the offset curve are computed quickly by a hybrid method employing the analytical solutions and the bisection search. Based on these closest points, an exact offset curve composed of line and arc segments is constructed by merging short line segments and reconstructing sharp features. The derived offset curve is intersection-free and retains the sharp features. The quality and performance of this approach are demonstrated by a number of experimental tests on various examples.
[1] PHAM B. Offset curves and surfaces:A brief survey[J]. Computer-Aided Design,1992,24:223-239.
[2] MACKAWA T. An overview of offset curves and surfaces[J]. Computer-Aided Design,1992,31:165-173.
[3] LASEMI A, XUE D, GU P. Recent development in CNC machining of freeform surfaces:A state-of-the-art review[J]. Computer-Aided Design,2010,42:641-654.
[4] KIM K, JEONG J. Tool path generation for machining free-form pockets with islands[J]. Computers & Industrial Engineering,1995,28:399-407.
[5] CHOI B, PARK S. A pair wise offset algorithm for 2D point sequence curve[J]. Computer-Aided Design,1999,31(12):735-745.
[6] PARK S, CHOI B. Uncut free pocketing tool-paths generation using pair-wise offset algorithm[J]. Computer-Aided Design,2001,33:739-746.
[7] PARK S, CHUNG Y. Offset tool-path linking for pocket machining[J]. Computer-Aided Design,2002,34:299-308.
[8] LIU X Z, YONG J H, ZHENG G Q, et al. An offset algorithm for polyline curves[J]. Computers in Industry,2007,58:240-254.
[9] WONG T, WONG K. NC tool-path generation for arbitrary pockets with islands[J]. The International Journal of Advanced Manufacturing Technology,1996,12:174-179.
[10] LIN Z, FU J, HE Y, et al. A robust 2D point-sequence curve offset algorithm with multiple islands for contour-parallel tool path[J]. Computer-Aided Design,2013,45:657-670.
[11] KIM H, LEE S, YING M. A new offset algorithm for closed 2D lines with islands[J]. The International Journal of Advanced Manufacturing Technology,2006,29:1169-1177.
[12] KIM H. Tool path generation for contour parallel milling with incomplete mesh model[J]. The International Journal of Advanced Manufacturing Technology,2010,48:443-454.
[13] LEE C, PHAN T, KIM D. 2D curve offset algorithm for pockets with islands using a vertex offset[J]. International Journal of Precision Engineering and Manufacturing,2009(10):127-135.
[14] LAI Y, WU J, HUNG J, et al. A simple method for invalid loops removal of planar offset curves[J]. The International Journal of Advanced Manufacturing Technology,2006,27(1):1153-1162.
[15] MAPLE C. Geometric design and space planning using the marching squares and marching cube algorithms[C]//Proceedings of 2003 International Conference on Geometric Modeling and Graphics. London:Geometric Modeling and Graphics,2003:90-95.
[16] HATNA A, GRIEVE R J, BROOMHEAD P. Automatic CNC milling of pockets:Geometric and technological issues[J]. Computer Integrated Manufacturing System,1998,11:309-330.
[17] DRAGOMATZ D, MANN S. A classified bibliography of literature on NC milling path generation[J]. Computer-Aided Design,1997,29:239-247.
[18] PRESSON H. NC machining of arbitrarily shaped pockets[J]. Computer-Aided Design,1978,10:169-174.
[19] HELD M, LUKACS G, ANDO L. Pocket machining based on contour-parallel tool paths generated by means of proximity maps[J]. Computer-Aided Design,1994,26:189-203.
[20] BO Q. Recursive polygon offset computing for rapid prototyping applications based on Voronoi diagrams[J]. The International Journal of Advanced Manufacturing Technology,2010,49(9):1019-1028.
[21] DHANIK S, XIROUCHAKIS P. Contour parallel milling tool path generation for arbitrary pocket shape using a fast marching method[J]. The International Journal of Advanced Manufacturing Technology,2010,50(912):1101-1111.
[22] LIU S J, WANG C C L. Fast intersection-free offset surface generation from freeform models with triangular meshes[J]. IEEE Transactions on Automation Science and Engineering,2011,8(2):347-360.
[23] BAERENTZENJA, ANANAES H. Signed distance computation using the angle weighted pseudonormal[J]. IEEE Transactions on Visualization and Computer Graphics,2005,11(3):243-253.
[24] LARSEN E, GOTTSCHALK S, LIN M C, et al. Fast proximity queries with swept sphere volumes[C]//Proceedings of International Conference on Robotics and Automation. San Francisco:Technical Report of Department of Computer Science,1999:1-32.
2017, Vol. 44 
