Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2017, Vol. 44 Issue (1): 10-21    DOI: 10.3785/j.issn.1008-9497.2017.01.002
Chinagraph 2016-几何计算     
基于距离场的二维偏移曲线快速生成方法
秦睿1,2, 刘圣军1,2, 陈子泰1,2, 袁炜雄1,2, 张帆1,2, 刘新儒1,2
1. 中南大学 工程建模与科学计算研究所, 湖南 长沙 410083;
2. 中南大学 数学与统计学院, 湖南 长沙 410083
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
 全文: PDF(4018 KB)   HTML  
摘要： 提出了一种快速生成二维偏移曲线的方法.对于无自相交的二维多边形曲线，该方法能构造无自相交、保留准确尖锐特征的二维等距偏移曲线.算法的基本思想：先在一个均匀网格上根据给定的曲线采样一个局部有向距离场，然后使用等值线抽取方法从有向距离场中获取偏移曲线.在构造局部距离场时引入3个过滤器,在远离偏移曲线的区域消除大量冗余计算.采用经典MS （marching square）方法抽取初始多边形偏移曲线，通过一个混合解析解和二分搜索方法，快速计算得到偏移曲线与网格边的准确交点.根据最近点位置信息对初始多边形偏移曲线进行简化和特征重构（如尖角和圆弧），构造无自相交、顶点数少、具有尖锐特征、含混合直线和圆弧段的准确偏移曲线.大量数据实例说明该方法性能良好.
关键词： 偏移曲线;  距离场;  无自相交;  过滤器;  解析法    
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.
Key words: offset curve    distance field    intersection-free    filter    analytic solution
收稿日期: 2016-07-25 出版日期: 2017-01-22
CLC:  TP391  
基金资助: 国家自然科学基金资助项目（61572527，61602524）；湖南省科技计划重点项目（2014FJ2008）
通讯作者: 刘新儒,ORCID:http://orcid.org/0000-0001-5427-0178,E-mail:liuxinru@csu.edu.cn     E-mail: liuxinru@csu.edu.cn
作者简介: 秦睿(1995-),ORCID:http://orcid.org/0000-0002-0914-5104,男,本科生,主要从事几何计算与优化算法研究.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
秦睿
刘圣军
陈子泰
袁炜雄
张帆
刘新儒

引用本文:

秦睿, 刘圣军, 陈子泰, 袁炜雄, 张帆, 刘新儒. 基于距离场的二维偏移曲线快速生成方法[J]. 浙江大学学报（理学版）, 2017, 44(1): 10-21.

QIN Rui, LIU Shengjun, CHEN Zitai, YUAN Weixiong, ZHANG Fan, LIU Xinru. Fast construction of 2D offset curve based on distance field. Journal of Zhejiang University (Science Edition), 2017, 44(1): 10-21.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2017.01.002    或    https://www.zjujournals.com/sci/CN/Y2017/V44/I1/10

[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 S
[1] 罗月童, 韩承村, 杜华, 严伊蔓. 基于拉伸特征的B-Rep→CSG转换算法及其应用[J]. 浙江大学学报（理学版）, 2021, 48(2): 151-158.
[2] 吕德生, 孙煜超, 王嘉忆. 虚拟场景中图形化交互组件的深度冲突缓解研究[J]. 浙江大学学报（理学版）, 2020, 47(5): 564-571.
[3] 李君轶, 任涛, 陆路正. 游客情感计算的文本大数据挖掘方法比较研究[J]. 浙江大学学报（理学版）, 2020, 47(4): 507-520.
[4] 宋建文, 罗江林, 王博, 张倩, 王献悦. 基于故事情景链语法的偶动画短片分析与建模[J]. 浙江大学学报（理学版）, 2020, 47(3): 284-296.
[5] 吕欣, 程雨夏. 基于语义相似度与XGBoost算法的英语作文智能评价框架研究[J]. 浙江大学学报（理学版）, 2020, 47(3): 329-336.
[6] 潘志庚, 袁庆曙, 陈胜男, 张明敏. 文化遗产数字化展示与互动技术研究与进展[J]. 浙江大学学报（理学版）, 2020, 47(3): 261-273.
[7] 陈佳舟, 王宇航, MohammedAmal Ahmed Hasan, 黄可妤, 卢周扬, 彭群生. 基于图像的二维剪纸自动生成方法[J]. 浙江大学学报（理学版）, 2020, 47(3): 274-283.
[8] 焦清局, 刘永革, 仇利萍, 金园园, 熊晶, 刘国英, 高峰. 网络驱动的未识甲骨字特性及场景语义预测[J]. 浙江大学学报（理学版）, 2020, 47(2): 142-150.
[9] 张迪, 查东东, 刘华勇. 三次DP曲线定义区间的扩展及其形状优化[J]. 浙江大学学报（理学版）, 2020, 47(2): 178-190.
[10] 卢家品, 罗月童, 黄兆嵩, 张延孔, 陈为. 基于排名学习和多源信息的地图匹配方法[J]. 浙江大学学报（理学版）, 2020, 47(1): 27-35.
[11] 赵喆, 张天野, 黄彦浩, 郑文庭, 陈为. 面向仿真数据的电网运行方式可视分析[J]. 浙江大学学报（理学版）, 2020, 47(1): 36-44.
[12] 刘一璟, 张旭斌, 张建伟, 周哲磊, 冯元力, 陈为. DenseNet-centercrop: 一个用于肺结节分类的卷积网络[J]. 浙江大学学报（理学版）, 2020, 47(1): 20-26.
[13] 李军成, 李兵, 易叶青. 保参数方向的形状可调过渡曲线与曲面[J]. 浙江大学学报（理学版）, 2019, 46(4): 422-430.
[14] 李丽, 高若婉, 梅树立, 赵海英. 基于Shannon-Cosine小波精细积分法的壁画降噪修复方法[J]. 浙江大学学报（理学版）, 2019, 46(3): 279-287.
[15] 郑锐, 钱文华, 徐丹, 普园媛. 基于卷积神经网络的刺绣风格数字合成[J]. 浙江大学学报（理学版）, 2019, 46(3): 270-278.