基于距离场的二维偏移曲线快速生成

第４４卷第１期２０１７年０１月浙　江　大　学　学　报(理学版)()JournalofZheianniversitcienceEditionjgUyS:///httww．zuournals．comscipwjjVol．４４No．１Jan．２０１７ :/DOI１０．３７８５．issn．１００８Ｇ９４９７．２０１７．０１．００２j 基于距离场的二维偏移曲线快速生成方法 ()１．中南大学 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 建模与科学计算研究所,湖南长沙４１００８３;２．中南大学数学与统计学院,湖南长沙４１００８３摘　要:提出了一种快速生成二维偏移曲线的方法．对于无自相交的二维多边形曲线,该方法能构造无自相交、保留准确尖锐特征的二维等距偏移曲线．算法的基本思想:先在一个均匀网格上根据给定的曲线采样一个局部有向距离场,然后使用等值线抽取方法从有向距离场中获取偏移曲线．在构造局部距离场时引入３个过滤器,在远离偏 ()移曲线的区域消除大量冗余计算．采用经典M方法抽取初始多边形偏移曲线,通过一个混合解Smarchinuaregsq析解和二分搜索方法,快速计算得到偏移曲线与网格边的准确交点．根据最近点位置信息对初始多边形偏移曲线 ,进行简化和特征重构(如尖角和圆弧)构造无自相交、顶点数少、具有尖锐特征、含混合直线和圆弧段的准确偏移 曲线．大量数据实例说明该方法性能良好． 关　键　词:偏移曲线;距离场;无自相交;过滤器;解析法２２２２２２∗,,,,,秦　睿１,刘圣军１,陈子泰１,袁炜雄１,张　帆１,刘新儒１, ()中图分类号:TP３９１　　　　文献标志码:A　　　　文章编号:１００８Ｇ９４９７２０１７０１Ｇ０１０Ｇ１２ １２１２１２１２１２１２,,,,(QINRuiLIUShenunCHENZitaiYUANWeixionZHANGFanLIUXinru１．Instituteogjg,f,,,,,, oathematicsandStatistics,CentralSouthUniversitChansha４１００８３,China)fMy,g ():４４１０１０Ｇ０２１EnineerinodelinndScientiicComutinCentralSouthUniversitChansha４１００８３,China;２．SchoolggMgafpg,y,g),Fastconstructionof２Doffsetcurvebasedondistancefield．JournalofZheianniversitScienceEdition２０１７,jgUy( :Af,wAbstractastaroachofgeneratinDoffsetcurvefromanolonalcurveispresentedhichpreservesppga２ypyg formgridaccordinotheinutcurveandthenemloontourinlorithmtoextracttheoffsetcurvefromthegtppyacgag verfficientwatoreducecomutationredundanciesinreionsfarfromtheoffsetcurves．Theinitialoffsetcurveisyeypg offsetcurvearecomutedquicklbridmethodemloinheanalticalsolutionsandthebisectionsearch．pybyahypygty shortlinesementsandreconstructinhareatures．ThederivedoffsetcurveisintersectionＧfreeandretainstheggspfshareatures．Thequalitndperformanceofthisaroacharedemonstratedbumberofexerimentaltestsonpfyappyanpvariousexamles．p,Basedontheseclosestpointsanexactoffsetcurvecomosedoflineandarcsementsisconstructedberinpgymgg)m,derivedbraditionalMS(MarchinuareethodtheaccurateintersectionsbetweenthegridedesandtheyatgSqgdistancefield．ThreefiltersareconductedtogenerateanarrowbandsineddistancefieldaroundtheoffsetcurveinagshareaturesandisselfＧintersectionfree．ThebasicideaisfirsttoestablishalocalsineddistancefieldonauniＧpfg :;;;;KeordsoffsetcurvedistancefieldintersectionＧfreefilteranalticsolutionyyW ]１Ｇ３,加工和分层加工[可生成轮廓线平行的刀具路０　引　言 二维曲线偏移广泛应用于平面几何造型、型腔CAM软件迫切需要快速稳定的偏移算法．现有的经典二维曲线偏移算法包括基于边偏移/径．然而,曲线偏移是一项困难的几何操作．CAD收稿日期:２０１６Ｇ０７Ｇ２５．);)基金项目:国家自然科学基金资助项目(湖南省科技 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 重点项目(６１５７２５２７,６１６０２５２４２０１４FJ２００８．,:///作者简介:秦　睿(男,本科生,主要从事几何计算与优化算法研究．１９９５－)ORCID:httorcid．or００００Ｇ０００２Ｇ０９１４Ｇ５１０４,pg:///:∗通信作者,ORCID:httorcid．or００００Ｇ０００１Ｇ５４２７Ｇ０１７８,EＧmailliuxinru＠csu．edu．cn．pg 　第１期秦　睿,等:基于距离场的二维偏移曲线快速生成方法 １１ ]４Ｇ８９Ｇ１３] 的算法[和基于点偏移的算法[通常,偏移操． 作会导致在偏移曲线中出现无效问题,最终的偏移曲线是去除无效偏移段的结果．但大部分算法都存 [０]在无法处理的案例(见图１)提出了一种．LIN等１基于卡圆解决局部无效问题的方法,尽管此方法通 造局部有向距离场．构造的３个过滤器用于在局部有向距离场的计算中消除冗余计算;在抽取偏移曲线的过程中,提出了一种结合解析法和二分法的快速计算网格边与等距曲线交点的混合算法;为了获得顶点数少且保留尖锐特征的准确等 [５] 值线, 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 了一个后处理过程以改进MS算法１的初始结果． 过修剪内角大于１的偏移线可减小偏移曲线的８０°逼近误差,但当形状复杂时很难生成准确的偏移曲()线,见图１e． 本文提出一种基于距离场的准确等距曲线快速 构造方法,无须处理自相交和局部无效问题．等距偏移曲线Lr实际上由平面上到原始曲线L的最短距离为r的所有点构成,偏移距离为r的等距偏移曲线Lr可采用以下隐函数表示: ()采用基于距离场的隐式函数定义二维等距１偏移曲线,避免了局部无效和自相交问题; 本文的主要贡献: ()使用３个过滤器:分层扫掠圆片过滤器、内/２ 外过滤器和四叉树过滤器,加速了局部有向距离场的计算,可消除９２．９％~９４．３％的冗余距离计算;典的二分搜索法其计算效率有很大提高． ()引入一种结合解析计算和二分搜索的混合３方法,用于计算隐式偏移曲线与网格边的交点,较经()基于最近点所在原始曲线中的信息,对初始４ 偏移曲线进行简化,最终形成由较少直线段和圆弧段构成的偏移曲线,同时重构了尖锐特征和准确偏移曲线 ． (()＝disL)－r＝０,１f(p)p, (其中,为disL)r上的点,p为平面上偏移曲线Lp,返回平面上点到给定曲线L的有向距离的函数,正值表示点p在曲线内部,负值则表示在曲线外部,曲线L的顶点按逆时针方向排列．偏移值r可以是正值或负值,只要计算偏移曲线周围局部区域内的网格点即可,所以本文需在均匀网格上构 ()]()()例子;文献[失败的例子;文献[误判的例子;文献[生成不c１１Ｇ１２d１３]e１０]准确的等距曲线,即使经过截断,其中虚线圆弧段为准确偏移线,黑色点横线为算(),waThemethodbasedonedeshiftiniththeproblemsaboutselfＧintersectiongg法执行过程中给定曲线的更新． ４Ｇ８]();()]基于边偏移的方法,需要解决自相交和不连续性问题[文献[失败的ab１４ Fi．１　Examlesshowinhelimitationsoftheexistinethodsgpgtgm 图１　实例展示现有方法的不足 ),,resectivel．(eTheinexactoffsetcurvegeneratedb１０]evenbetrimmedpyy[udatedcurvefortheoriinaldurinhealorithmprocessin．pggtgg ,wherethedashedarcsaretheexactoffsetsandtheblackdashdotlinesarethe [４Ｇ８]()(),(),[,,anddisoint．b,cdarethefailedcasesfor[１４]１１Ｇ１２]and[１３]j １　相关工作 ]研究工作可参考文献[有关二维曲线偏移算１６Ｇ１７． 研究者提出了多种二维曲线偏移算法,早期的 法的主要工作可归纳为:基于Voronoi图的算 ]１４,１８Ｇ２０４Ｇ８] 、法[基于边偏移的算法[和基于点偏移的]９Ｇ１３ 算法[． 当偏移曲线所在区域已知时,使用边界的 只要简单连接每一个区域的偏移曲线Voronoi图, １２浙江大学学报(理学版)　第４４卷　 段即可．PRESSON[１８]引入Voronoi图生成无岛且 被线段包围的轮廓平行刀具路径,提出了使用．．LAI等１提出了一个基于向前位置跟踪VH[９] 在此orEoLnD等１ 基础上进行了改进oi图处理带 岛的曲线[４] 的无效环剔除算法线段都可通过．在他们的工作中,所有的退化曲交V点o遍ron而无效环的剔除则历oi图消除通过将二维问题转换．为一维区间识别问题移距离较大时．然而,当曲线相邻的,他们使用的２个内角之和大于Voronoi图方法会出错１８０°且偏, 如图１(b)所示．另外,尽管通过构造Voronoi图可以避免自相交,但这些方法只适用于形状相对简单的曲线,且有数值误差,特别是接近圆弧的区域基于边偏移的方法是逻辑上最直接和简单的一． 类偏移曲线生成方法,其基本思想是以给定的偏移距离沿着法向方向偏移每一条线段的起点和终点这类方法的主要缺陷是需要 检测 工程第三方检测合同工程防雷检测合同植筋拉拔检测方案传感器技术课后答案检测机构通用要求培训 和解决所有自相交．和不连续性问题(如图基于分段干涉测试的偏移方法１(a)所示,)将所有线段分为整．文献[５Ｇ７]提出了体干涉、部分干涉和反向干涉３类,定义了２个操作并对干涉线段进行处理解决曲线在偏移方向上．然而,除干涉问题外,还要内角大于曲线不连续问题１８０引起的偏移刀具路径的生成过程外．文献[８,]°更多是应用于计算机图形除了可以应用于数控加工学．他们的主要贡献是可处理自相交、重叠和小圆弧问题．初始偏移曲线采用基本的分段偏移获得,本文主要研究局部问题的处理千上万条直线段,非常耗时．一条轮廓线通常包含成,因此不适合数控加工领域． 基于点偏移的方法是通过在每个顶点的角平分 线上选择偏移点,使之到相邻,然后根据原始给定曲线的顶点连接关系顺２条线段的距离为偏移距离次连接各顶点对应的偏移点,得到偏移曲线主要在于偏移曲线上无效部．不同方法之间的差异分的去 除．WONG等[９] 在采用角平分线方法生成初始偏移 曲线时,如果相邻２条角平分线相交,那么他们之间的线段将被删除,通过其相连的．通过检测环的方向判定全局环的有效性２条边构造新的角平分线,与原始曲线方向相反的则为无效环,将其从偏移曲线中剔除．文中没有详细给出对局部无效环进行剔除 的算法圈的方法解决由相邻角平分线相交造成的局部无效．LIN等[１０] 受文献[９ ]的启发,提出了基于卡问题对原始给定曲线进行更新．通过卡圈及相应的规则,采用不同的三边模板,从而生成无局部无效段的偏移曲线．最后,采用树 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 过程收集所有全局有效环,得到最终的偏移曲线．文献[１１Ｇ１２ ]通过比较偏移边与对应原始边的方向以确定无效边,通过去除无效偏移边以解决局部无效问题,通过检查环的 方向确定和去除全局无效环１(c)所示的无效问题．LEE等．但此算法无法处理图[１３] 在解决局部无效问题时,除了验证偏移边的方向有效性外,还验证了偏 移边的位置有效性效性决定偏移边的有效性是不合适的．但他们用偏移边２个端点的有,如图示１)判例．尽管文献[,但仍未包含１３]给出了处理无效问题的,导致文献[５种不同(d所所有判例法实现正确的曲线偏移．基于点偏移的１３方]方法法虽无不会生成不连续的偏移曲线,但由于局部无效和全 [局无效的检测和处理非常复杂,即使采用文献 所示１０]的方法． ,生成的偏移曲线也不准确,如图１(e )采用基于距离场的方法生成二维偏移曲线[ ２１] 和三维偏移曲面[２２] ,可避免前述方法出现的偏移曲 [线自相交、不连续及无效检测与处理的问题．文献 偏微分方程２１ ]将偏移问题定义为求解初值为原始给定曲线的,并采用快速跟踪方法得到方程的解．该方法在求解过程中,网格点处的距离值是所采用小包围盒边长或对角线的求和,而不是准确的到原始给定曲线的距离,导致最后得到的解是一条近似偏移曲线部三维距离场．文献[２,２然后采用一种改进的等值面抽取方]通过设计４个过滤器快速计算局法生成三角网格模型的偏移曲面其三角片数量越多．偏移曲面采用三角片网格表示,精度越高,,对后续处理的影响越大二维偏移曲线问题．本文基于文献[２２的思想求解、直线段与直线段之间的距离．针对曲线计算过程中主要涉及]点与直线段,设计了与直线段或多边形相关的,并设计混合解析法和二分法的３个过滤器,以快速实现局部二维距离场创建偏移曲线与网格边的交点计算方法,从而实现０内生成一条偏移曲线现与原始给定曲线顶点个数相近且保持尖锐特征的．２５s ．最后,通过简化曲线实准确偏移曲线． 　算法概述 在实际工程应用中,如分层加工,轮廓线通过平面与给定工件实体模型求交得到,因而是一条或多条带内环的无自相交的封闭多边形曲线曲线,目标是获得无自相交的偏移曲线并保留其尖．对于这类锐特征．算法分３步: 和偏移曲线的空间中(１ )将给定的多边形曲线L嵌入到一个包围它．该空间在均匀网格上被采样 ２ 　第１期秦　睿,等:基于距离场的二维偏移曲线快速生成方法 １３ 成一个偏移曲线Lr周围窄带区域的局部有向距离场快速计算距离场,见第 ４节．设计了． ３个过滤器用于与原始曲线之间的位置关系(２)计算网格边和偏移曲线的交点,推导了解析计算交点．根据网格边的公式,并与二分搜索法结合形成一个快速计算交点的混合方法,尖锐特征的无自相交的等距偏移曲线(３ )见第设计了一个简化及特征重构过程５节． ,生成保留和直线段对偏移曲线进行简化,获得了更准确的曲．并使用圆弧线偏移结果,见第图离场采样在均匀分布的网格上２给出了本文算法框架的主要步骤６节． ,最小距离计算和交．局部距点计算均可在多核计算机上并行处理,方法简单且易于实现． 图算法框架 (Fig ．２　Th２em　ethodframework线a ),嵌入到一个均匀剖分的网格中计算局部距离场;(,对给定的二维多边形曲与网格边的交点;(重构生成准确等距曲线c)抽取出等距偏移曲线b)找到有效网格边;,(计d)算简化和特征偏移曲线l(ioac)aAldgiisvtean２nceDfieplodlybgaosne． edomnbtehdedepdoliynaugonn．if(obr)mDegtreicdti,ngandaalＧadSnidgrmptidlhifeoedgyffessetancdurcvoem．pu(tcin)Egxtthreacitnitnegrstehceotionffssebtetcwuerevnet．hv(edm)structingintghet shheiapneitfieaaleturxetsrafcotretdheofefxseatcctoufrfvseeatcnudrrvee．conＧ３　局部距离场快速构造 为了在一个n×n的均匀剖分网格上构造给定曲 线L的有向距离场,最直接的方法是计算(n＋１ 网格节点到曲线L的最短距离)２ 个通过计算其到曲．网格点p到曲线L的最短距离可线L上所有线段距 离中的最小值获得．在找到点p在曲线L上的最近点pc后, 两点之间有向距离的符号就可以通过点p处于曲线所包围区域的内部还是外部判断．有许多方法可以实现点与多边形位置关系的判定,如射线法、累计角度法、编码法等．本文采用角度加权法 向[２３]来快速判断点与多边形的内外关系．此方法尽 管可以快速确定距离的符号,但最近点的计算非常耗时,尤其当n非常大时．下面介绍速计算． ３个过滤器的加．１　分层扫掠圆片过滤器 扫掠圆片层次结构过滤器可用于点p到给定多边形曲线L距离的加速计算．基本思想是建立起曲线L上直线段的包围盒层次结构,使得远离点直线段扫掠包围球体改造为直线段扫掠包围圆片２]p的直线段不必进行距离计算测试．将文献[２中的, 应用于二维空间中点与曲线的最近距离计算离,本文只需计算点到直线段之间的距离２４]需计算线段与线段． 不同于文献[．之直线段可间的距以表示成参数形式: pt其中,t∈)＝p１＋t(２－１),线投影点的参数[０,１]．(pp 通过计算点􀭰p到直线段pt．根据􀭰t(t的取值情况获得点)p所在直在直线段p(t)上的最近点pcìpïïp１c＝íï pîp (􀭰t,)　, 　,􀭰t≤０,􀭰t　≥０１＜,􀭰t＜１,(２ )２进而计算最近距离d,上的最近点pc便于在后继计算中使用、最近点min＝记录点p在曲线ppc－所在的直线段或顶点p c．,． ．２　四叉树过滤器 尽管使用分层扫掠圆片过滤器可以快速计算 函数f场依然费时(p) ,但在具有n２ 个结点的网格上构造距离．实验显示,在一台个人电脑上使用扫掠圆片层次结构过滤器计算点p到具有条边的直线的最近点,需要１．２×１０３ １３ ２ 个结点的网格上构造０．０距１离ms场． 当在具有时,需要含在一系３２ms． 通常情况下,一条曲线的偏移曲线被包列的小网格内．只需要找到偏移曲线附近的这些小网格,构建一个窄带内的局部距离场,即可快速构造等距曲线． 在介绍包围盒层次结构过滤器之前,首先给出有(无)效网格点和有(无)效包围盒的概念． 定义１　对于任何网格结点,若其位置点p满足 dis(p, L)－r≤s,(３ )３L３５２６ １４浙江大学学报(理学版)　第４４卷　 其中s为小网格的边长,r为偏移距离,表示点p到给定曲线L的有向距离,则称之为有效dis(􀅰,􀅰)网格结点如果直接检测每一个网格点是否有效．否则,为无效网格结点． ,需计算 点到给定曲线的距离．为了避免冗余计算,引入包围盒盒中．将网格点分组,,如图３(a )使之包含在具有更大边长的包围所示．图F３ig 　四叉树过滤器示意图 实心点为有效点．３　Qua,d空心点为无效点Ｇtreefilter． 定义Solid２poi　nts对于一个对角线长度为arevalid,whileemptyp ointsa若其中心c２rδein的包围盒valid．, b到给定曲线则称为无效包围盒dis(cL的距离满足 b．否则, L),－称为有效包围盒r＞s＋δ,． (４ )由式(点都是无效的３)和．而在有效包围盒中(４) ,可得在无效包围盒中的网格结,包含有效和无效网格结点． 尽管使用包围盒可以快速剔除无效网格点,但选择恰当大小的包围盒比较困难．当选择的包围盒太大时,有效包围盒中依然存在许多无效网格点．而当选择太小时,会增加大量有效性检测操作．为了更有效地剔除无效网格点,本文采用自适应分层包围盒过滤器———四叉树过滤器,如图每一个有效包围盒B３(所包围盒Bub计算小包,对其一分为四围盒,b形成)示．对于s４个小的的距离,若满足式．所有包含于该小包围盒内的网格点被标记为无效４B(),则小包围盒sub中心点到给定曲线Bsub不再细分,且． 否则,Bsub将继续细分下去,直到包围盒所包含的网格点不多于．３　内/外过滤器 ４个． 根据偏移方向,确定偏移曲线处于给定曲线的内部还是外部．为了只在偏移曲线附近构建局部有向距离场,检测网格点或包围盒中心点到给定曲线的有向距离ndis(dpis,L(p), ＝Ls)g,n((p－pc其中)􀅰nc)dmin,(c为点p在给定曲线L上的最近点pc处的角５)度加权法向．通常设定nc指向曲线L包围区域的外部． 偏移距离r为正的偏移曲线Lr处于给定曲线L的外部, 那么所有处于曲线L所包围区域内部的网格点为无效点;反之,偏移距离r为负的偏移曲线Lr处于给定曲线L的内部,那么所有处于曲线L包围区域外部的网格点为无效点．无效包围盒的判定应满足式(４)． ４　网格边上等距曲线交点的快速计算 使用第偏移曲线L３节介绍的３个过滤器,可以快速构造 r附近的一个局部有向距离场f,距离场内只计算了网格点上的有向距离值(p．不过．)根据这些有向距离值,能找到与偏移曲线相交的小网格． 定义３　在有向距离场中的和p２个有效网格点p１ ２之间的一条网格边ef(pf,若p１和p２满足１)２则称e为有效网格边．否则为无效网格边(p )＜０,． (６ )为了生成准确的偏移曲线,在应用MS算法抽 取分段线性连续的初始偏移曲线的基础上,采用简化方法自动重构尖锐特征,减少结果偏移曲线的顶点数．在均匀网格上,,并记录交点在原始曲线上的最MS算法计算有效网格边与隐式偏移曲线的交点近点及其所在边的序号,以便用于曲线简化．有效网格边上的交点可通过求解下列方程得到: f由于函数((１－α)p１＋αpf的,方程((􀅰)中的２) 有＝０向,　距０离≤α函≤数１是．非线(７)法得到． ７)的解可以通过最简单但缓慢的二分搜索性 为了加速交点计算,提出了结合解析法和二分搜索法的混合计算方法,并推导了交点的解析计算公式． ４．１　混合法 分析发现,对于一条有效边e的p ２个端点p１和 ２,如果其最近点p１,c和p２,c都处于给定曲线L的同一条直线段l上,则能在边定曲线e上解析计算式(个解p,其离给L的最近点p７ 线)的一c在直段l上,且p－pc－ r＝０．在实际造型时,只有当网格边足够短时,满足解析方法计算交点的条件的可能性才比较高．当不满足解析计算交点的条件时,则将网格边一分为二,找到交点可能存在的区段,然后测试该区段是否满足解析计算交点的条件．重复上述过程,直到找到交点．解析计算的交点将通过一次距离验证: |dis(pL其中ε＝１０ －５ 为公差限, ．若距离偏)－r|≤ε差,不小于ε,则(８ 将)３ 　第１期秦　睿,等:基于距离场的二维偏移曲线快速生成方法 １５ 包含交点的区段进行一次二分,继续交点计算的过程．在实现中,二分搜索法的终止条件也为式(根据以上描述,在算法１中列出了用混合法计８)．算交点的基本步骤． 算法１　混合法计算交点 输入　有效网格边e的２个端点p１和p２应最近点　p,p, 其相１,c２,c和给定曲线L输出交点p．;步骤: (１２))IFp１,c和p２,c在同一条线段上; (使用解析法计算交点p(见５．２节) ;((３４ ))E将网格边LSE;e一分为二,使用包含交点的新区段更新边e(p ,同时更新p１１,c和p２,c,回到第(１)步;、p ２和相应最近点(５)(６)ENDIF;);(７(８)IF交点９ ))E输出交点p满足式(将网格边LSE; p;８e一分为二,用包含交点的新区段更新边e,同时更新p１、２和相应最(１对处于线段１０p),c和p２ENDIF,c２． ,回到第(１)步;p近点个端点位置的情况需要进一步计 算,以便判断p１,c和p２,c是否在同一条线段上．因为最近点计算过程给出的结果可能是条线段上,但属于下列情况之一: ２个点不在同一(１)p１,c在线段lv１内部,p２,c在与l１相邻的线段２的一个端点上,v也是但这２２)lp１的一个端点; (１,c和p２,c分别在个点是另外一条线段的２条不同线段的端点上,．２　解析解 ２个端点．对于２个端点p１和p２的最近点p１,c和p２,c处于同一条直线段上的有效边e移曲线L的交点p的解析计算公式,本节． 将给出其与偏r分析发现,平面上线段l周围的一个点q线段上的最近点q线段的,它在c将落在线段内部或端点处．平面上线段l周围的区域通２个处的垂线分成３个区域,如图４()常被线段端点所示．都落在线段(定义１ )４　平面上线段l周围的区域称为 a 线区域l内部,如果该区域内的所有点q,如图４(a)的最近点所示的区域２;都落在线段(２ )点区域和l,如果该区域内的所有点q的最近点两个端点上,如图３ ． ４(a )所示的区域１图Fig．４４　偏移曲线与网格边交点解析计算示意图 　Illustrationforanalyti(ai)n一条线段与其tersectionsb２et个端点处的垂线将平面分为weenthegridedg ceasllayncdotmputingt he３he个区域offset;(cbu)r处于ve线区域的线段;((art)hTohg roenealarlienaesoc sant)处于端点区域的线段rehaetiptlsanteawoeredndivpidoiendb．ts;(yabli)nTesheelginmeaentreaacndtashee(c)Thepointareacase． ;基于这个区域的分类,推导解析计算网格边与 偏移曲线交点的公式线段l的线区域内,如图．如果一条线段p＝ff()p１p ２完全落在２)４b 所示,则交点p为１)如果线段(p２)(pp－p (１)p１－f２在线段)(p１fp(p－lf的(p１端)p ２．(９)２完全落点v对应的点区域内,如图式 ４(c)所示,则交点p可以通过公{ v－(１－α)p１－αp２ ２ p＝计算,其中α∈[０(,１１－]． α)p＝r ２ ,１＋αp２ (１０ )尽管解析法可以快速计算偏移曲线与网格边的 交点,但网格边通常会跨越多个区域．使用上述解析方法计算交点,需先将网格边e剖分为多段,使得每一子段都完全落在同一个区域内．如果一个子段的 个端点ps,１和ps,２满足f(ps,１)fs,２点不在该子段上,舍去该子段．而(p 对于)满＞足０,f表(p明交s,１),的交点(p s２),＜在实现中则直接取第其余子段不予考虑０的子段,． １个子段　准确偏移曲线的生成 在使用经典与偏移曲线交点的基础上MS算法抽取第,利用每个交点在原始多４节中得到的网格边形曲线上最近点的所在线段或端点的信息,简化与重构特征,获取准确的偏移曲线经典MS算法可以保证抽取的偏移曲线是无自相 ． 交的．但是,由于经典MS算法通过逐个处理每个小网格,连接每个小网格边上的交点得到偏移曲线,因而抽取的偏移曲线存在(直线段组成,即使这些直线段是在一条直线或一段圆２个问题:１)偏移曲线由许多条短弧上,顶点数亦太多;(２ )连接交点成短直线段时没有ol４２f５ １６浙江大学学报(理学版)　第４４卷　 考虑交点的法向信息,丢失了偏移曲线上的尖锐特征,导致生成的偏移曲线不准确．即使使用自适应网格生成的偏移曲线也无法完全解决上述问题．为此,设计了一个包含简化与特征重构的后处理过程． 对平面上的多边形曲线,其准确偏移曲线由直线段和圆弧段组合而成．其中,直线段由原始曲线中的直线段偏移得到,圆弧段则由原始曲线中的顶点将MS算法抽取初始的等距偏移多边形曲线之后,考察偏移多边形曲线上所有顶点的最近点所在的原始曲线的边或顶点的信息,具有相同原始曲线的边或顶点信息的偏移多边形曲线上的所有相邻顶点将形成一条直线段或圆弧段． 在算法实现中,用(表示原始多边形曲idid１,２)偏移得到．基于平面偏移曲线的性质,在采用经典 点p１和p２的最近点所在原始多边形曲线的边或顶 ,点的信息为(和(idididid１,２)３,４)()如果i且i则表１didididdid１＝３,２＝４,１≠２, 示２个顶点是由原始多边形曲线L的同一条边上()上,图５中红色虚线矩形框所包围的点;a()如果i且i则表２didididdid１＝３,２＝４,１＝２, 示２个顶点由原始多边形曲线L的同一个顶点偏()中红色虚线椭圆框所包围的点;a ()如果i则表示２个顶点３diddid１≠３或i２≠４,分别由原始多边形曲线L的３条边上的点或１条边与１个顶点或２个顶点偏移生成,偏移曲线Lr在这圆框和蓝色虚线矩形框所包围的点．()移曲线,如图５所示 ．c 的点偏移生成,在偏移曲线Lr中处于同一条直线段 移生成,在偏移曲线L图５r中处于同一圆弧段上, 线L的边和顶点信息,其中i为原始多dk＝１,２,k,边形曲线顶点的序号．顶点被认为是退化的边．例()如,表示一条２个端点在原始多边形曲线顶点３,４()序列中的序号分别为３和４的边,表示一个序４,４号为４的顶点．给定初始偏移曲线Lr上２个相邻顶 ２个点之间会形成２条直线段或１条线段１条圆弧 )段或２条圆弧段的交点,如图５(所示绿色虚线椭a())图５所示;由式(重构尖锐特征,生成准确的偏b３ )通过式(和(减少偏移曲线上的顶点数,如１２) ()())抽取出的初始等距曲线,每一个顶点保留其最近点所在原始曲线中边的信息,并根据这些信息进行分组;根据(的分组结果进行拼aba()合,形成长的直线段并重构圆弧特征,减少顶点数;根据交点最近点信息的变化,计算直线段之间．直线段与圆弧段,及圆弧段之间的交c点,重构尖锐特征,生成准确的偏移曲线． Fi．５　Offsetcurvesimlificationandfeaturereconstructiongp 图５　等距曲线简化与特征重构 ,structedandthenanexactoffsetcurveiseneratedaccordintothevariationsoftheintersectionscomutedbetweenlinesementslineseＧggpgg,mentandarcsementandarcsements．gg ,;()mentandarcfeaturesarerecoveredberintheverticesaccordintotheclustersandverticesarereducedcSharfeaturesarereconＧymgggp ();()aAnextractedinitialoffsetcurvewhereallverticesaregrouedwiththeirclosestpointsandrelatinriinaledesbLonerlineseＧpgogggg ６　实验结果与讨论 个人手提电脑上使用不同的数据实例进行算法测试．使用本文算法对不同的平面多边形曲线采用不同的偏移值进行向内和向外偏移,得到了一系列结果和统计数据,如图６、７和表１~４所示． 图６给出了采用本文方法在５１２×５１２网格上使用V并在普通配置的C＋＋实现本文算法, １８３１,１７８１和２０７５个顶点．５条不同形状曲线 的给定距离偏移曲线的计算时间及误差的统计信息见表１．由表１可知,所有给定曲线的偏移曲线都可在不超过０．对抽取的初２５s的时间内生成．始偏移曲线进行简化及特征重构,可减少偏移曲 “马”和“老鼠”曲线形状中分别包含１８８,１３０３, 线的顶点数,提高偏移曲线的逼近精度．由表２知,简化后的偏移曲线顶点数不到初始偏移曲线 ６ 倍,达到了１基本上可以认为是准确偏移１００－８,曲线． 生成不同偏移距离并经过简化和特征重构的５条 顶点数的２精度至少是初始偏移曲线的５％, ““不同形状的偏移曲线,其中“手”花”京剧脸谱” 　第１期秦　睿,等:基于距离场的二维偏移曲线快速生成方法 １７ Fi．６　Offsettinesultswithdifferentoffsetdistancesggr Thedimensionsofthegridis５１２×５１２ ． 网格分辨率５１２×５１２． 图６　使用不同偏移距离进行偏移的结果 arethefinaloffsetresultsaftersimlificationandfeaturereconstruction．p ,,Heretheblackcurvearethegivenshaesandthefirstandthirdrowsaretheinitialoffsetcurveswhilethesecondandfourthrowsp 其中,黑色实线为给定的曲线形状,第１行与第３行为初始偏移曲线,第２行与第４行为简化及特征重构后的偏移曲线． Fi．７　Theoffsettinesultsindifferentresolutiongridswithdifferentoffsetdistancesforthegivencurveshaesggrp 图７　给定曲线形状在不同分辨率网格上使用不同偏移距离进行偏移的结果 ),Table１tatisticsaboutthecomutinime(msthenumberofverticesandtheerrorpgt 曲线形状手花脸谱马老鼠 顶点数１８８ 偏移距离－２２－１１－２２－２５－２５ 计算时间/ms 初始偏移曲线 表１　偏移曲线计算时间、顶点数及误差统计 简化偏移曲线 平均误差０．０００．００ －９ ２．２×１０－１０８×１０ T１０ T２１０９１５６１５７１８７１７２ T３１６３２３１３１３１ Ttol１２５２０４２０３２３４２１９ 顶点数１９５８２１８６２０４０２４１６２２５８ 平均误差 －４ ９．９×１０－３１．３×１０－３１．４×１０－３１．８×１０－３１．７×１０ 顶点数１５１３７８３２３２０５１９１ １３０３１８３１１７８１２０７５ １６１５１６１６ ０．００ 初始偏移曲线和简化的时间,Ttol为前３项的总和． 包括抽取　　注　T１为构造扫掠圆片层次结构的时间,T２为分辨率为５１２×５１２的网格上构造距离场的时间,T３为抽取偏移曲线的时间, 可以先采　　当原始曲线采用一般样条曲线表时, 用直线段自适应进行近似,转化成多边形曲线,然后使用本文算法进行处理．初始偏移曲线的简化依然可以提高偏移曲线的精度． 在不同分辨率的网格上进行不同距离的偏移结果,同时给出了简化前后的曲线形状及顶点,顶点用红色进行标记．形状简单的“五角星”曲线包含 图７显示的是对２个形状复杂性不同的曲线 １８浙江大学学报(理学版)　第４４卷　 偏移距离为２而形状复杂的“猪”的１０个顶点,５,曲线包含１２偏移距离为１图中对于７１个顶点,５．使用分辨率较高的网格生成的偏移曲线,由于顶))点太多,无法显示曲线的顶点,见图７(和(的de第１个和第３个图．图７中第１行与第３行为初始偏移曲线,第２行与第４行为对应简化及特征重构 后的偏移曲线．由图７知,在分辨率较小的网格上,抽取出的初始偏移曲线丢失了尖锐特征,且圆)弧特征的逼近很粗糙,如图７(第１和第３个结a果所示．随着分辨率的增大,曲线上的尖锐特征逐())第１行和第３行所示．b~(e 步恢复,且圆弧特征的逼近精度逐渐改善,如图７ Table２　Statisticsforthegeneratedoffsetcurvesinthegridswithdifferentdimensions 曲线形状 偏移距离 分辨率３２ 时间/ms１６１１０３１６２３１ 初始偏移曲线 顶点数１５２２５５４１１２４７４６１０ 最大误差３．５９０．９６０．２８２．３１ －３ ２．４×１０ 表２　不同分辨率网格中生成偏移曲线的统计数据 简化偏移曲线 平均误差０．２０ 顶点数１５１５１０３ －４ ５．９×１０ 最大误差０．０００．０００．０００．７９ －７ ７．３×１０ 平均误差０．０００．０００．０７５０．００ 五角星 ２５１２８５１２１２８５１２３２ １．８×１０－４ ０．０３０２６００．２９ ０．０１３ １５ 猪 １５ １７２１９１０ ０．６０２１８０．１５－３ １．１×１０ 当采用　　从图７第２行和第４行的结果中发现, 分辨率较小的网格,如３偏移曲线的简化和２×３２,在低分辨率的网格上对简单曲线构造的偏移曲线进行简化和特征重构,简化后的偏移曲线逼近精度比在高分辨率网格上构造的初始偏移曲线更高,且与它们的简化结果曲线相同,见图７第２行的偏移曲线,表２中的数据也说明了这点．所以使用本文方法在构造包含长直线段曲线的偏移曲线时,可先在低分辨率的网格上生成初始偏移曲线,然后进行简化． 然而,对于具有复杂形状的曲线,尽管简化与特 短的线段,当分辨率太低时,网格的步长大于这些线段,消除了他们对偏移曲线的贡献,使简化过程中的特征重构操作亦无法将其恢复．因而,为了构造高逼近精度的偏移曲线,必须使网格步长小于给定曲线的最小边长． 为了研究本文提出的过滤器的性能,在构造局 特征重构效果非常明显,尤其是对形状简单的曲线． 部距离场时测试了所能减少的最近距离计算次数．这里,最近距离计算指使用基于分层扫掠圆片过滤器的方法进行的点到曲线最近距离计算．分别对简单的均匀划分网格上构造偏移曲线附件的窄带距离形状曲线“五角星”和复杂形状曲线“猪”在５１３×５１３()使用包m×m表示２个方向上使用m个包围盒;２ ()()围盒和内/外过滤器;四叉树过滤器;使用内/３４外过滤器和四叉树过滤器．由表３的统计数据不难约９２．９％~９４．３％的无效计算． 测试了混合计算有效边上交点的算法效率．基发现,使用内/外和四叉树过滤器可以剔除网格点上()场．测试了４种过滤器组合形式:只使用包围盒,１ 征重构过程能提高偏移曲线的逼近精度,使低分辨率网格上的简化偏移曲线与更高分辨率网格上构造的初始偏移曲线的逼近精度相似,但采用高分辨率网格构建距离场,对偏移曲线的逼近精度影响很大,尤其是简化偏移曲线．如表２中“猪”的曲线所示,不同分辨率网格中抽取的初始偏移曲线逼近误差近似,线性关系提高．而当结合简化与特征重构过程中移曲线的最大误差只提高了~１,而分辨率为 ４ ５１２×５１２的简化偏移曲线最大误差是初始偏移曲线的１．这是由于形状复杂的曲线包含很多比较 ５６)采用低分辨率网格(时,简化偏３２×３２或１２８×１２８ 于顶点数不同的曲线形状,表４统计了不同分辨率９８．５％的边使用混合方法可在不超过６次细分操作 下找到交点,而使用二分查找法,只有不到２０％的混合方法大大提高了求交的效率． 网格中具有交点的有效网格边数量．不难发现,边能在不超过６次细分操作下找到交点．由此可见, 　第１期秦　睿,等:基于距离场的二维偏移曲线快速生成方法 １９ Table３　Comutinimesfortheclosestdistancesbetweenpointsandthecurveusinifferentfilterspgtgd 包围盒 ８×８个 １６×１６３２×３２６４×６４个 个 个 ８×８个 包围盒＋内/外过滤器１６×１６３２×３２６４×６４个 个 个 四叉树过滤器６４×６４个２２１６７２０００１２７０４５２５２４４ 表３　使用不同过滤器进行点到曲线最近距离计算次数的统计 内/外＋四叉树过滤器６４×６４个１５５４９１４９５９１９０４２１８６０ ４ 曲线形状 顶点数 偏移距离 五角星猪 １０１２７１ １５２５１５２５ １８８４９１１３４０５３７３２９１４４０５９１８０５０９１０７９４４４１１３８２９５５３２０８３２４１１２９９１６１６６７４０５０７１８０３７７７８８７８４０７５２２９２９１１７６８６６１３４３０６８５６４４５４３４４１６８８６６１１４７７５６５０７７３６７２２１９７１２５１５２５１６８６４８３５０９３７１８１１０７１３１７１３５６００５３５２３７ Fi．８　ExactoffsetcurvesgeneratedburmethodcorresondinofivecasesinFi．１gyopgtgTable４　Thenumberofedeswithdifferentdividinimesforcomutinintersectionswithtwoggtpg 曲线形状五角星 顶点数 偏移距离１５ methodsingridswithdifferentresolutions有效边数６１８ 混合方法 ２３６３８７９６５ ０次二分１２３０２４７４３０６７５５６１１ １次二分 分辨率１２８２５６５１２１２８２５６５１２ 二分法 ２次二分 ３４４７４６５４２ 小于６次１２３９２４８４４６７９４９６１７ 小于６次００２６０ 图８　用本文方法对图１中的５种曲线生成准确的偏移曲线 表４　不同分辨率网格中具有交点的有效网格边数统计 １０１２４０２４８４４７４９５２ 猪 １２７１１５ １９１０１７１０１９０７ １２０３７５ 　　本文方法能有效处理图１中文献[４Ｇ８,１０Ｇ１４] 方法难以解决的问题,能生成连续、准确的偏移曲线．图８给出了本文方法处理对应于图１中示例的结果．黑实线为原始给定多边形曲线,浅色线为生成的偏移曲线． []方法生成的偏移曲线结果的比较．在生成偏移１０ 曲线过程中,本文方法采用了分辨率为５１２×５１２的 表５给出了３条给定的原始曲线用本文和文献 ]均匀网格,因而耗时比文献[方法长．但依然能达１０到交互的计算速率,满足用户交互设计的要求．另外,本文方法生成的偏移曲线比文献[方法更准１０]]确,平均精度超过文献[图９给出了对应１０１００倍．图形显示的比较结果,可明显看到,在内角大于处,本文方法生成的偏移曲线更光滑、准确．采１８０° ]用文献[程序生成结果时,发现只能处理内偏移,１０对较大偏移距离无法得到结果或所得结果错误． ]１０ 表５　本文方法与卡圆方法[的比较 Table５　Comarisonswiththemethodp时间/ms０．３ ０．３２．８ ]文献[方法１０最大误差１．４６ １．４９２．００ 平均误差０．０６ ０．０２０．０８ 曲线形状五角星 手老鼠 顶点数１０１８８２０７５ 偏移距离２５ １０１０ 本文方法 时间/ms１１０ １２５２５０ 最大误差０ ００．０２０ 平均误差０ ０６．３×１０－４ ２０浙江大学学报(理学版)　第４４卷　 :AsmachininffreeformsurfacestateＧofＧtheＧartreviewgo[]４　KIMK,JEONGJ．ToolpathgenerationformachiＧ ,IndustrialEnineerin１９９５,２８:３９９Ｇ４０７．gg []ninreeＧformpocketswithislandsJ．Comuters&gfp[],,:J．ComuterＧAidedDesin２０１０４２６４１Ｇ６５４．pg []５　CHOIB,PARKS．Apairwiseoffsetalorithmforg ():１９９９,３１１２７３５Ｇ７４５． [],２DpointseuencecurveJ．ComuterＧAidedDesinqpg [],CHO６　PARKSIB．UncutfreepocketinoolＧathsgtp]enerationusinairＧwiseoffsetalorithm[J．ComＧggpg 　(a图)ourmethod　　　(b)themethod[１０ ][７]　　 Fig．９　Com９p a　生成的偏移曲线结果比较 risonsofthegeneratedoffsetcurves[８]　结　论 [９]提出了一种快速、鲁棒计算平面多边形曲线的无自相交、准确偏移曲线的方法．算法的基本思想是在一个均匀网格上基于给定曲线的局部有向距离场[１０采样,然后利用等值线抽取算法得到偏移曲线距离场的方法可以减少经典方法中对偏移曲线上某．基于段有效性的判断及相关处理工作[１１滤器消除在距离场构造过程中的大量冗余计算．通过使用３个过,从而高效生成局部有向距离场取方法可以获得初始偏移曲线．采用经典的等值线抽采用基于解析解和二分法的混合交点计算方法．在曲线抽取过程中, ,大[１２大缩短了查找过程,实现了等值线的快速抽取,根据保存的最．在偏移曲线与网格边的交点计算过程中近点的位置信息,用长直线段或圆弧段表示端点具有相同最近点位置信息的短线段,并进行合并．初始[１３偏移曲线上相邻顶点的最近点位置信息的变化,标识了原始曲线中线段的变化,据此可在偏移曲线上计算相邻直线段之间、直线段与圆弧段、圆弧段之间[１４的交点,以重构偏移曲线上的尖锐特征,最终获得准确的偏移曲线．文中的大量例子和统计数据都有力地说明了本方法的良好性能和优势．[１５参考文献(References ):[１]　P[JHAM]．ComBp．uOtefrfＧsAetidceudDrveessiag nnds,１９u９r２fa,c２e４s::２２Ab３Ｇ２r３i９ef．survey[２]　MACKAWAT．AnoverviewofoffsetcurvesandsurＧ[１６[３]　LfaAceSsE[JM]IA．C,oXmpUuEDterＧ,AiGdUPedD．eRsiegcnen,t１９d９ev２el,３o１p m:１e６n５tＧi１nC７３N．CputerＧAidedDesinpoAcRkeKtmSa,g chCiHUningN,[G２００JY．O１,３３．Comf:f７ps３uettt９Ｇ７erＧo４Ao６ildＧ．epdathlDesiing nkin２g００f ２or３４:２９９Ｇ３０８． ],,alIgUriXZthmf,YorOpNoGJHlyline,cuZrHveEsNJGG．CQom,p etutaelrs．iAnInonfdfsuest try o,２００７,５８:２４０Ｇ２５４．[]ＧraOryNp GTo,WONGK．NCtoolＧp athgenerationforarbiＧAdvancedMcketaswnufitahctiusrlianngdsTe[cJh]n．olTohgeyI, n１t９e９rn６a,t１i２on:a１l７J４Ｇo１ur７n９al．ofqIueNncZec,FurUJveo,ffHseEtaYl,goetritahlm．Arwitohbumstul２tiDp leipoisnltaＧnsedＧ forcontourＧparalleltoolpath[J]．Comp uterＧAidedsDesig nIMH,２,０L１３E,ES４５:６,５Y７IＧ６N７fJoG０．M．Anorurclnoasleod２fADldviannecswedMithanisulfaanctdusr[eiJn]woffsetalg orithmg．TTehcehnIonltoegry na２ti０o０n６al２９:１１６９Ｇ１１７７． ,,mIillMingH．Twithoionlcopmatp hletgemeneersathmionfodoelrc[Jo]ntourparallel tionalJournalofAdvancedManufacturing．TTheechInnotleorgnyaＧ２０,E１EC０,４８,:P４４HA３Ｇ４N５４T． rithmforpocketsw,itKhiIMslaD．ndsu２Dsincugrvaveoefrftseexotaflfg soeＧa[JndM]．IanntuefrancattuiroinnalJournalofPrecisionEngineeringtiInAnvtaIYelrind,atlioWUJoonpaslre,g JmHU,２ouorvnaalN００loGJ９(１fop,０):１２７Ｇ１３５．flaentaarlo．fAsfseitmcp ulremvese[tJh]o．dTfohreTechnology ,AdvancedManufacturing２００６,２７(１):１１５singPtLhEeCma．rcGheionmgetsrqiucdesig３Ｇna１１n６ds２．paceplanningu Ｇritheomsn[CG]e/o/Proceedingsaroefsa２０n０d３ImnatrecrnhiantigoncaulbCeaonlfg eroＧＧencmetricModelingandGrap hics．LondonGeometricModelingandGraphics,２００３:９０Ｇ９５．:matiTcANCmA,iGllRinIgEoVfERJp ocke,tBsR:OGeOMHometrEicAaDPndt．eAchuntooＧ loicalissues[J]．ComuterIntＧSy gstem,１９９８,１１:３０９Ｇ３３p０．egratedManufacturing　P　L７　Wt]　L]　K]　K]　L]　L]　MA]　HA