秦 睿，劉圣軍，陳子泰，袁煒雄，張 帆，劉新儒*

(1. 中南大學(xué) 工程建模與科學(xué)計(jì)算研究所， 湖南 長(zhǎng)沙 410083; 2. 中南大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 湖南 長(zhǎng)沙 410083)

基于距離場(chǎng)的二維偏移曲線快速生成方法

秦 睿1,2，劉圣軍1,2，陳子泰1,2，袁煒雄1,2，張 帆1,2，劉新儒1,2*

(1. 中南大學(xué) 工程建模與科學(xué)計(jì)算研究所， 湖南 長(zhǎng)沙 410083; 2. 中南大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 湖南 長(zhǎng)沙 410083)

提出了一種快速生成二維偏移曲線的方法.對(duì)于無(wú)自相交的二維多邊形曲線，該方法能構(gòu)造無(wú)自相交、保留準(zhǔn)確尖銳特征的二維等距偏移曲線.算法的基本思想：先在一個(gè)均勻網(wǎng)格上根據(jù)給定的曲線采樣一個(gè)局部有向距離場(chǎng)，然后使用等值線抽取方法從有向距離場(chǎng)中獲取偏移曲線.在構(gòu)造局部距離場(chǎng)時(shí)引入3個(gè)過濾器,在遠(yuǎn)離偏移曲線的區(qū)域消除大量冗余計(jì)算.采用經(jīng)典MS(marching square)方法抽取初始多邊形偏移曲線，通過一個(gè)混合解析解和二分搜索方法，快速計(jì)算得到偏移曲線與網(wǎng)格邊的準(zhǔn)確交點(diǎn).根據(jù)最近點(diǎn)位置信息對(duì)初始多邊形偏移曲線進(jìn)行簡(jiǎn)化和特征重構(gòu)(如尖角和圓弧)，構(gòu)造無(wú)自相交、頂點(diǎn)數(shù)少、具有尖銳特征、含混合直線和圓弧段的準(zhǔn)確偏移曲線.大量數(shù)據(jù)實(shí)例說明該方法性能良好.

偏移曲線；距離場(chǎng)；無(wú)自相交；過濾器；解析法

Fast construction of 2D offset curve based on distance field.Journal of Zhejiang University(Science Edition), 2017,44(1):010-021

0 引 言

二維曲線偏移廣泛應(yīng)用于平面幾何造型、型腔加工和分層加工[1-3]，可生成輪廓線平行的刀具路徑.然而，曲線偏移是一項(xiàng)困難的幾何操作.CAD/CAM軟件迫切需要快速穩(wěn)定的偏移算法.

現(xiàn)有的經(jīng)典二維曲線偏移算法包括基于邊偏移的算法[4-8]和基于點(diǎn)偏移的算法[9-13].通常，偏移操作會(huì)導(dǎo)致在偏移曲線中出現(xiàn)無(wú)效問題，最終的偏移曲線是去除無(wú)效偏移段的結(jié)果.但大部分算法都存在無(wú)法處理的案例(見圖1).LIN等[10]提出了一種基于卡圓解決局部無(wú)效問題的方法，盡管此方法通過修剪內(nèi)角大于180°的偏移線可減小偏移曲線的逼近誤差，但當(dāng)形狀復(fù)雜時(shí)很難生成準(zhǔn)確的偏移曲線，見圖1(e).

本文提出一種基于距離場(chǎng)的準(zhǔn)確等距曲線快速構(gòu)造方法，無(wú)須處理自相交和局部無(wú)效問題.等距偏移曲線Lr實(shí)際上由平面上到原始曲線L的最短距離為r的所有點(diǎn)構(gòu)成，偏移距離為r的等距偏移曲線Lr可采用以下隱函數(shù)表示：

f(p)=dis(p,L)-r=0,

(1)

其中，p為平面上偏移曲線Lr上的點(diǎn)，dis(p,L)為返回平面上點(diǎn)到給定曲線L的有向距離的函數(shù)，正值表示點(diǎn)p在曲線內(nèi)部，負(fù)值則表示在曲線外部，曲線L的頂點(diǎn)按逆時(shí)針方向排列.偏移值r可以是正值或負(fù)值，只要計(jì)算偏移曲線周圍局部區(qū)域內(nèi)的網(wǎng)格點(diǎn)即可，所以本文需在均勻網(wǎng)格上構(gòu)造局部有向距離場(chǎng).構(gòu)造的3個(gè)過濾器用于在局部有向距離場(chǎng)的計(jì)算中消除冗余計(jì)算；在抽取偏移曲線的過程中，提出了一種結(jié)合解析法和二分法的快速計(jì)算網(wǎng)格邊與等距曲線交點(diǎn)的混合算法；為了獲得頂點(diǎn)數(shù)少且保留尖銳特征的準(zhǔn)確等值線，設(shè)計(jì)了一個(gè)后處理過程以改進(jìn)MS算法[15]的初始結(jié)果.

本文的主要貢獻(xiàn)：

(1)采用基于距離場(chǎng)的隱式函數(shù)定義二維等距偏移曲線，避免了局部無(wú)效和自相交問題；

(2)使用3個(gè)過濾器：分層掃掠圓片過濾器、內(nèi)/外過濾器和四叉樹過濾器，加速了局部有向距離場(chǎng)的計(jì)算，可消除92.9%～94.3%的冗余距離計(jì)算；

(3)引入一種結(jié)合解析計(jì)算和二分搜索的混合方法，用于計(jì)算隱式偏移曲線與網(wǎng)格邊的交點(diǎn)，較經(jīng)典的二分搜索法其計(jì)算效率有很大提高.

(4)基于最近點(diǎn)所在原始曲線中的信息，對(duì)初始偏移曲線進(jìn)行簡(jiǎn)化，最終形成由較少直線段和圓弧段構(gòu)成的偏移曲線，同時(shí)重構(gòu)了尖銳特征和準(zhǔn)確偏移曲線.

圖1 實(shí)例展示現(xiàn)有方法的不足Fig.1 Examples showing the limitations of the existing methods(a)基于邊偏移的方法，需要解決自相交和不連續(xù)性問題[4-8];(b)文獻(xiàn)[14]失敗的例子;(c)文獻(xiàn)[11-12]失敗的例子;(d)文獻(xiàn)[13]誤判的例子;(e)文獻(xiàn)[10]生成不準(zhǔn)確的等距曲線，即使經(jīng)過截?cái)?，其中虛線圓弧段為準(zhǔn)確偏移線，黑色點(diǎn)橫線為算法執(zhí)行過程中給定曲線的更新.(a)The method based on edge shifting, with the problems about self-intersection and disjoint[4-8]. (b),(c),(d) are the failed cases for [14], [11-12], and [13], respectively. (e)The inexact offset curve generated by [10], even be trimmed, where the dashed arcs are the exact offsets, and the black dash dot lines are the updated curve for the original during the algorithm processing.

1 相關(guān)工作

研究者提出了多種二維曲線偏移算法，早期的研究工作可參考文獻(xiàn)[16-17].有關(guān)二維曲線偏移算法的主要工作可歸納為：基于Voronoi圖的算法[14,18-20]、基于邊偏移的算法[4-8]和基于點(diǎn)偏移的算法[9-13].

當(dāng)偏移曲線所在區(qū)域已知時(shí)，使用邊界的Voronoi圖，只要簡(jiǎn)單連接每一個(gè)區(qū)域的偏移曲線段即可.PRESSON[18]引入Voronoi圖生成無(wú)島且被線段包圍的輪廓平行刀具路徑.HELD等[19]在此基礎(chǔ)上進(jìn)行了改進(jìn)，提出了使用Voronoi圖處理帶島的曲線.LAI等[14]提出了一個(gè)基于向前位置跟蹤的無(wú)效環(huán)剔除算法.在他們的工作中，所有的退化曲線段都可通過Voronoi圖消除.而無(wú)效環(huán)的剔除則通過將二維交點(diǎn)遍歷問題轉(zhuǎn)換為一維區(qū)間識(shí)別問題.然而，當(dāng)曲線相鄰的2個(gè)內(nèi)角之和大于180°且偏移距離較大時(shí)，他們使用的Voronoi圖方法會(huì)出錯(cuò)，如圖1(b)所示.另外，盡管通過構(gòu)造Voronoi圖可以避免自相交，但這些方法只適用于形狀相對(duì)簡(jiǎn)單的曲線，且有數(shù)值誤差，特別是接近圓弧的區(qū)域.

基于邊偏移的方法是邏輯上最直接和簡(jiǎn)單的一類偏移曲線生成方法，其基本思想是以給定的偏移距離沿著法向方向偏移每一條線段的起點(diǎn)和終點(diǎn).這類方法的主要缺陷是需要檢測(cè)和解決所有自相交和不連續(xù)性問題(如圖1(a)所示).文獻(xiàn)[5-7]提出了基于分段干涉測(cè)試的偏移方法，將所有線段分為整體干涉、部分干涉和反向干涉3類，定義了2個(gè)操作并對(duì)干涉線段進(jìn)行處理.然而，除干涉問題外，還要解決曲線在偏移方向上內(nèi)角大于180°引起的偏移曲線不連續(xù)問題.文獻(xiàn)[8]除了可以應(yīng)用于數(shù)控加工刀具路徑的生成過程外，更多是應(yīng)用于計(jì)算機(jī)圖形學(xué).他們的主要貢獻(xiàn)是可處理自相交、重疊和小圓弧問題.初始偏移曲線采用基本的分段偏移獲得，本文主要研究局部問題的處理.一條輪廓線通常包含成千上萬(wàn)條直線段，非常耗時(shí)，因此不適合數(shù)控加工領(lǐng)域.

基于點(diǎn)偏移的方法是通過在每個(gè)頂點(diǎn)的角平分線上選擇偏移點(diǎn)，使之到相鄰2條線段的距離為偏移距離，然后根據(jù)原始給定曲線的頂點(diǎn)連接關(guān)系順次連接各頂點(diǎn)對(duì)應(yīng)的偏移點(diǎn)，得到偏移曲線.不同方法之間的差異主要在于偏移曲線上無(wú)效部分的去除.WONG等[9]在采用角平分線方法生成初始偏移曲線時(shí)，如果相鄰2條角平分線相交，那么他們之間的線段將被刪除，通過其相連的2條邊構(gòu)造新的角平分線.通過檢測(cè)環(huán)的方向判定全局環(huán)的有效性，與原始曲線方向相反的則為無(wú)效環(huán)，將其從偏移曲線中剔除.文中沒有詳細(xì)給出對(duì)局部無(wú)效環(huán)進(jìn)行剔除的算法.LIN等[10]受文獻(xiàn)[9]的啟發(fā)，提出了基于卡圈的方法解決由相鄰角平分線相交造成的局部無(wú)效問題.通過卡圈及相應(yīng)的規(guī)則，采用不同的三邊模板對(duì)原始給定曲線進(jìn)行更新，從而生成無(wú)局部無(wú)效段的偏移曲線.最后，采用樹分析過程收集所有全局有效環(huán)，得到最終的偏移曲線.文獻(xiàn)[11-12]通過比較偏移邊與對(duì)應(yīng)原始邊的方向以確定無(wú)效邊，通過去除無(wú)效偏移邊以解決局部無(wú)效問題，通過檢查環(huán)的方向確定和去除全局無(wú)效環(huán).但此算法無(wú)法處理圖1(c)所示的無(wú)效問題.LEE等[13]在解決局部無(wú)效問題時(shí)，除了驗(yàn)證偏移邊的方向有效性外，還驗(yàn)證了偏移邊的位置有效性.但他們用偏移邊2個(gè)端點(diǎn)的有效性決定偏移邊的有效性是不合適的，如圖1(d)所示.盡管文獻(xiàn)[13]給出了處理無(wú)效問題的5種不同判例，但仍未包含所有判例，導(dǎo)致文獻(xiàn)[13]方法無(wú)法實(shí)現(xiàn)正確的曲線偏移.基于點(diǎn)偏移的方法雖不會(huì)生成不連續(xù)的偏移曲線，但由于局部無(wú)效和全局無(wú)效的檢測(cè)和處理非常復(fù)雜，即使采用文獻(xiàn)[10]的方法，生成的偏移曲線也不準(zhǔn)確，如圖1(e)所示.

采用基于距離場(chǎng)的方法生成二維偏移曲線[21]和三維偏移曲面[22]，可避免前述方法出現(xiàn)的偏移曲線自相交、不連續(xù)及無(wú)效檢測(cè)與處理的問題.文獻(xiàn)[21]將偏移問題定義為求解初值為原始給定曲線的偏微分方程，并采用快速跟蹤方法得到方程的解.該方法在求解過程中，網(wǎng)格點(diǎn)處的距離值是所采用小包圍盒邊長(zhǎng)或?qū)蔷€的求和，而不是準(zhǔn)確的到原始給定曲線的距離，導(dǎo)致最后得到的解是一條近似偏移曲線.文獻(xiàn)[22]通過設(shè)計(jì)4個(gè)過濾器快速計(jì)算局部三維距離場(chǎng)，然后采用一種改進(jìn)的等值面抽取方法生成三角網(wǎng)格模型的偏移曲面.偏移曲面采用三角片網(wǎng)格表示，精度越高，其三角片數(shù)量越多，對(duì)后續(xù)處理的影響越大.本文基于文獻(xiàn)[22]的思想求解二維偏移曲線問題.針對(duì)曲線計(jì)算過程中主要涉及點(diǎn)與直線段、直線段與直線段之間的距離，設(shè)計(jì)了與直線段或多邊形相關(guān)的3個(gè)過濾器，以快速實(shí)現(xiàn)局部二維距離場(chǎng)創(chuàng)建，并設(shè)計(jì)混合解析法和二分法的偏移曲線與網(wǎng)格邊的交點(diǎn)計(jì)算方法，從而實(shí)現(xiàn)0.25 s內(nèi)生成一條偏移曲線.最后，通過簡(jiǎn)化曲線實(shí)現(xiàn)與原始給定曲線頂點(diǎn)個(gè)數(shù)相近且保持尖銳特征的準(zhǔn)確偏移曲線.

2 算法概述

在實(shí)際工程應(yīng)用中，如分層加工，輪廓線通過平面與給定工件實(shí)體模型求交得到，因而是一條或多條帶內(nèi)環(huán)的無(wú)自相交的封閉多邊形曲線.對(duì)于這類曲線，目標(biāo)是獲得無(wú)自相交的偏移曲線并保留其尖銳特征.算法分3步：

(1)將給定的多邊形曲線L嵌入到一個(gè)包圍它和偏移曲線的空間中.該空間在均勻網(wǎng)格上被采樣成一個(gè)偏移曲線Lr周圍窄帶區(qū)域的局部有向距離場(chǎng).設(shè)計(jì)了3個(gè)過濾器用于快速計(jì)算距離場(chǎng)，見第4節(jié).

(2)計(jì)算網(wǎng)格邊和偏移曲線的交點(diǎn).根據(jù)網(wǎng)格邊與原始曲線之間的位置關(guān)系，推導(dǎo)了解析計(jì)算交點(diǎn)的公式，并與二分搜索法結(jié)合形成一個(gè)快速計(jì)算交點(diǎn)的混合方法，見第5節(jié).

(3)設(shè)計(jì)了一個(gè)簡(jiǎn)化及特征重構(gòu)過程，生成保留尖銳特征的無(wú)自相交的等距偏移曲線.并使用圓弧和直線段對(duì)偏移曲線進(jìn)行簡(jiǎn)化，獲得了更準(zhǔn)確的曲線偏移結(jié)果，見第6節(jié).

圖2給出了本文算法框架的主要步驟.局部距離場(chǎng)采樣在均勻分布的網(wǎng)格上，最小距離計(jì)算和交點(diǎn)計(jì)算均可在多核計(jì)算機(jī)上并行處理，方法簡(jiǎn)單且易于實(shí)現(xiàn).

圖2 算法框架Fig.2 The method framework(a)嵌入到一個(gè)均勻剖分的網(wǎng)格中，對(duì)給定的二維多邊形曲線，計(jì)算局部距離場(chǎng)；(b)找到有效網(wǎng)格邊，計(jì)算偏移曲線與網(wǎng)格邊的交點(diǎn)；(c)抽取出等距偏移曲線；(d)簡(jiǎn)化和特征重構(gòu)生成準(zhǔn)確等距曲線.(a)A given 2D polygon embedded in a uniform grid, and a local distance field based on the polygon. (b)Detecting valid grid edges and computing the intersections between them and the offset curve. (c)Extracting the offset curve. (d)Simplifying the initial extracted offset curve and reconstructing the shape features for the exact offset curve.

3 局部距離場(chǎng)快速構(gòu)造

為了在一個(gè)n×n的均勻剖分網(wǎng)格上構(gòu)造給定曲線L的有向距離場(chǎng)，最直接的方法是計(jì)算(n+1)2個(gè)網(wǎng)格節(jié)點(diǎn)到曲線L的最短距離.網(wǎng)格點(diǎn)p到曲線L的最短距離可通過計(jì)算其到曲線L上所有線段距離中的最小值獲得.在找到點(diǎn)p在曲線L上的最近點(diǎn)pc后，兩點(diǎn)之間有向距離的符號(hào)就可以通過點(diǎn)p處于曲線所包圍區(qū)域的內(nèi)部還是外部判斷.有許多方法可以實(shí)現(xiàn)點(diǎn)與多邊形位置關(guān)系的判定，如射線法、累計(jì)角度法、編碼法等.本文采用角度加權(quán)法向[23]來快速判斷點(diǎn)與多邊形的內(nèi)外關(guān)系.此方法盡管可以快速確定距離的符號(hào)，但最近點(diǎn)的計(jì)算非常耗時(shí)，尤其當(dāng)n非常大時(shí).下面介紹3個(gè)過濾器的加速計(jì)算.

3.1 分層掃掠圓片過濾器

掃掠圓片層次結(jié)構(gòu)過濾器可用于點(diǎn)p到給定多邊形曲線L距離的加速計(jì)算.基本思想是建立起曲線L上直線段的包圍盒層次結(jié)構(gòu)，使得遠(yuǎn)離點(diǎn)p的直線段不必進(jìn)行距離計(jì)算測(cè)試.將文獻(xiàn)[22]中的直線段掃掠包圍球體改造為直線段掃掠包圍圓片，應(yīng)用于二維空間中點(diǎn)與曲線的最近距離計(jì)算.

不同于文獻(xiàn)[24]需計(jì)算線段與線段之間的距離，本文只需計(jì)算點(diǎn)到直線段之間的距離.直線段可以表示成參數(shù)形式：

p(t)=p1+t(p2-p1)，

(2)

3.2 四叉樹過濾器

盡管使用分層掃掠圓片過濾器可以快速計(jì)算函數(shù)f(p)，但在具有n2個(gè)結(jié)點(diǎn)的網(wǎng)格上構(gòu)造距離場(chǎng)依然費(fèi)時(shí).實(shí)驗(yàn)顯示，在一臺(tái)個(gè)人電腦上使用掃掠圓片層次結(jié)構(gòu)過濾器計(jì)算點(diǎn)p到具有1.2×103條邊的直線的最近點(diǎn)，需要0.01 ms.當(dāng)在具有5132個(gè)結(jié)點(diǎn)的網(wǎng)格上構(gòu)造距離場(chǎng)時(shí)，需要2 632 ms.通常情況下，一條曲線的偏移曲線被包含在一系列的小網(wǎng)格內(nèi).只需要找到偏移曲線附近的這些小網(wǎng)格，構(gòu)建一個(gè)窄帶內(nèi)的局部距離場(chǎng)，即可快速構(gòu)造等距曲線.

在介紹包圍盒層次結(jié)構(gòu)過濾器之前，首先給出有(無(wú))效網(wǎng)格點(diǎn)和有(無(wú))效包圍盒的概念.

定義1 對(duì)于任何網(wǎng)格結(jié)點(diǎn)，若其位置點(diǎn)p滿足

(3)

其中s為小網(wǎng)格的邊長(zhǎng)，r為偏移距離，dis(·,·)表示點(diǎn)p到給定曲線L的有向距離，則稱之為有效網(wǎng)格結(jié)點(diǎn).否則，為無(wú)效網(wǎng)格結(jié)點(diǎn).

如果直接檢測(cè)每一個(gè)網(wǎng)格點(diǎn)是否有效，需計(jì)算點(diǎn)到給定曲線的距離.為了避免冗余計(jì)算，引入包圍盒.將網(wǎng)格點(diǎn)分組，使之包含在具有更大邊長(zhǎng)的包圍盒中，如圖3(a)所示.

圖3 四叉樹過濾器示意圖Fig.3 Quad-tree filter實(shí)心點(diǎn)為有效點(diǎn)，空心點(diǎn)為無(wú)效點(diǎn).Solid points are valid, while empty points are invalid.

定義2 對(duì)于一個(gè)對(duì)角線長(zhǎng)度為2δ的包圍盒，若其中心cb到給定曲線L的距離滿足

(4)

則稱為無(wú)效包圍盒.否則，稱為有效包圍盒.

由式(3)和(4)，可得在無(wú)效包圍盒中的網(wǎng)格結(jié)點(diǎn)都是無(wú)效的.而在有效包圍盒中，包含有效和無(wú)效網(wǎng)格結(jié)點(diǎn).

盡管使用包圍盒可以快速剔除無(wú)效網(wǎng)格點(diǎn)，但選擇恰當(dāng)大小的包圍盒比較困難.當(dāng)選擇的包圍盒太大時(shí)，有效包圍盒中依然存在許多無(wú)效網(wǎng)格點(diǎn).而當(dāng)選擇太小時(shí)，會(huì)增加大量有效性檢測(cè)操作.為了更有效地剔除無(wú)效網(wǎng)格點(diǎn)，本文采用自適應(yīng)分層包圍盒過濾器——四叉樹過濾器，如圖3(b)所示.對(duì)于每一個(gè)有效包圍盒B，對(duì)其一分為四，形成4個(gè)小的包圍盒Bsub.計(jì)算小包圍盒Bsub中心點(diǎn)到給定曲線的距離，若滿足式(4)，則小包圍盒Bsub不再細(xì)分，且所有包含于該小包圍盒內(nèi)的網(wǎng)格點(diǎn)被標(biāo)記為無(wú)效.否則，Bsub將繼續(xù)細(xì)分下去，直到包圍盒所包含的網(wǎng)格點(diǎn)不多于4個(gè).

3.3 內(nèi)/外過濾器

根據(jù)偏移方向，確定偏移曲線處于給定曲線的內(nèi)部還是外部.為了只在偏移曲線附近構(gòu)建局部有向距離場(chǎng)，檢測(cè)網(wǎng)格點(diǎn)或包圍盒中心點(diǎn)到給定曲線的有向距離dis(p,L)，

dis(p,L)=sgn((p-pc)·nc)dmin,

(5)

其中nc為點(diǎn)p在給定曲線L上的最近點(diǎn)pc處的角度加權(quán)法向.

通常設(shè)定nc指向曲線L包圍區(qū)域的外部.偏移距離r為正的偏移曲線Lr處于給定曲線L的外部，那么所有處于曲線L所包圍區(qū)域內(nèi)部的網(wǎng)格點(diǎn)為無(wú)效點(diǎn)；反之，偏移距離r為負(fù)的偏移曲線Lr處于給定曲線L的內(nèi)部，那么所有處于曲線L包圍區(qū)域外部的網(wǎng)格點(diǎn)為無(wú)效點(diǎn).無(wú)效包圍盒的判定應(yīng)滿足式(4).

4 網(wǎng)格邊上等距曲線交點(diǎn)的快速計(jì)算

使用第3節(jié)介紹的3個(gè)過濾器，可以快速構(gòu)造偏移曲線Lr附近的一個(gè)局部有向距離場(chǎng)f(p).不過，距離場(chǎng)內(nèi)只計(jì)算了網(wǎng)格點(diǎn)上的有向距離值.根據(jù)這些有向距離值，能找到與偏移曲線相交的小網(wǎng)格.

定義3 在有向距離場(chǎng)中的2個(gè)有效網(wǎng)格點(diǎn)p1和p2之間的一條網(wǎng)格邊e，若p1和p2滿足

f(p1)f(p2)<0，

(6)

則稱e為有效網(wǎng)格邊.否則為無(wú)效網(wǎng)格邊.

為了生成準(zhǔn)確的偏移曲線，在應(yīng)用MS算法抽取分段線性連續(xù)的初始偏移曲線的基礎(chǔ)上，采用簡(jiǎn)化方法自動(dòng)重構(gòu)尖銳特征，減少結(jié)果偏移曲線的頂點(diǎn)數(shù).在均勻網(wǎng)格上，MS算法計(jì)算有效網(wǎng)格邊與隱式偏移曲線的交點(diǎn)，并記錄交點(diǎn)在原始曲線上的最近點(diǎn)及其所在邊的序號(hào)，以便用于曲線簡(jiǎn)化.有效網(wǎng)格邊上的交點(diǎn)可通過求解下列方程得到：

f((1-α)p1+αp2)=0， 0≤α≤1.

(7)

由于函數(shù)f(·)中的有向距離函數(shù)是非線性的，方程(7)的解可以通過最簡(jiǎn)單但緩慢的二分搜索法得到.

為了加速交點(diǎn)計(jì)算，提出了結(jié)合解析法和二分搜索法的混合計(jì)算方法，并推導(dǎo)了交點(diǎn)的解析計(jì)算公式.

4.1 混合法

在實(shí)際造型時(shí)，只有當(dāng)網(wǎng)格邊足夠短時(shí)，滿足解析方法計(jì)算交點(diǎn)的條件的可能性才比較高.當(dāng)不滿足解析計(jì)算交點(diǎn)的條件時(shí)，則將網(wǎng)格邊一分為二，找到交點(diǎn)可能存在的區(qū)段，然后測(cè)試該區(qū)段是否滿足解析計(jì)算交點(diǎn)的條件.重復(fù)上述過程，直到找到交點(diǎn).解析計(jì)算的交點(diǎn)將通過一次距離驗(yàn)證:

|dis(p,L)-r|≤ε，

(8)

其中ε=10-5為公差限.若距離偏差不小于ε，則將包含交點(diǎn)的區(qū)段進(jìn)行一次二分，繼續(xù)交點(diǎn)計(jì)算的過程.在實(shí)現(xiàn)中，二分搜索法的終止條件也為式(8).

根據(jù)以上描述，在算法1中列出了用混合法計(jì)算交點(diǎn)的基本步驟.

算法1 混合法計(jì)算交點(diǎn)

輸入 有效網(wǎng)格邊e的2個(gè)端點(diǎn)p1和p2，其相應(yīng)最近點(diǎn)p1,c，p2,c和給定曲線L；

輸出 交點(diǎn)p.

步驟：

(1)IFp1,c和p2,c在同一條線段上；

(2)使用解析法計(jì)算交點(diǎn)p(見5.2節(jié))；

(3)ELSE；

(4)將網(wǎng)格邊e一分為二，使用包含交點(diǎn)的新區(qū)段更新邊e，同時(shí)更新p1、p2和相應(yīng)最近點(diǎn)p1,c和p2,c，回到第(1)步；

(5)END IF；

(6)IF交點(diǎn)p滿足式(8)；

(7) 輸出交點(diǎn)p;

(8)ELSE；

(9)將網(wǎng)格邊e一分為二，用包含交點(diǎn)的新區(qū)段更新邊e，同時(shí)更新p1、p2和相應(yīng)最近點(diǎn)p1,c和p2,c，回到第(1)步；

(10)END IF.

對(duì)處于線段2個(gè)端點(diǎn)位置的情況需要進(jìn)一步計(jì)算，以便判斷p1,c和p2,c是否在同一條線段上.因?yàn)樽罱c(diǎn)計(jì)算過程給出的結(jié)果可能是2個(gè)點(diǎn)不在同一條線段上，但屬于下列情況之一：

(1)p1,c在線段l1內(nèi)部，p2,c在與l1相鄰的線段l2的一個(gè)端點(diǎn)v上，v也是l1的一個(gè)端點(diǎn)；

(2)p1,c和p2,c分別在2條不同線段的端點(diǎn)上，但這2個(gè)點(diǎn)是另外一條線段的2個(gè)端點(diǎn).

4.2 解析解

對(duì)于2個(gè)端點(diǎn)p1和p2的最近點(diǎn)p1,c和p2,c處于同一條直線段上的有效邊e，本節(jié)將給出其與偏移曲線Lr的交點(diǎn)p的解析計(jì)算公式.

分析發(fā)現(xiàn)，平面上線段l周圍的一個(gè)點(diǎn)q，它在線段上的最近點(diǎn)qc將落在線段內(nèi)部或線段的2個(gè)端點(diǎn)處.平面上線段l周圍的區(qū)域通常被線段端點(diǎn)處的垂線分成3個(gè)區(qū)域，如圖4(a)所示.

圖4 偏移曲線與網(wǎng)格邊交點(diǎn)解析計(jì)算示意圖Fig.4 Illustration for analytically computing the intersections between the grid edges and the offset curve(a)一條線段與其2個(gè)端點(diǎn)處的垂線將平面分為3個(gè)區(qū)域；(b)處于線區(qū)域的線段;(c)處于端點(diǎn)區(qū)域的線段.(a)Three areas on the plane are divided by a line segment and the orthogonal lines are at its two end points； (b)The line area case; (c)The point area case.

定義4 平面上線段l周圍的區(qū)域稱為

(1)線區(qū)域，如果該區(qū)域內(nèi)的所有點(diǎn)q的最近點(diǎn)都落在線段l內(nèi)部，如圖4(a)所示的區(qū)域2；

(2)點(diǎn)區(qū)域，如果該區(qū)域內(nèi)的所有點(diǎn)q的最近點(diǎn)都落在線段l兩個(gè)端點(diǎn)上，如圖4(a)所示的區(qū)域1和3.

基于這個(gè)區(qū)域的分類，推導(dǎo)解析計(jì)算網(wǎng)格邊與偏移曲線交點(diǎn)的公式.如果一條線段p1p2完全落在線段l的線區(qū)域內(nèi)，如圖4(b)所示，則交點(diǎn)p為

(9)

如果線段p1p2完全落在線段l的端點(diǎn)v對(duì)應(yīng)的點(diǎn)區(qū)域內(nèi)，如圖4(c)所示，則交點(diǎn)p可以通過公式

(10)

計(jì)算，其中α∈[0,1].

盡管解析法可以快速計(jì)算偏移曲線與網(wǎng)格邊的交點(diǎn)，但網(wǎng)格邊通常會(huì)跨越多個(gè)區(qū)域.使用上述解析方法計(jì)算交點(diǎn)，需先將網(wǎng)格邊e剖分為多段，使得每一子段都完全落在同一個(gè)區(qū)域內(nèi).如果一個(gè)子段的2個(gè)端點(diǎn)ps,1和ps,2滿足f(ps,1)f(ps,2)>0，表明交點(diǎn)不在該子段上，舍去該子段.而對(duì)于滿足f(ps,1)f(ps,2)<0的子段，在實(shí)現(xiàn)中則直接取第1個(gè)子段的交點(diǎn)，其余子段不予考慮.

5 準(zhǔn)確偏移曲線的生成

在使用經(jīng)典MS算法抽取第4節(jié)中得到的網(wǎng)格與偏移曲線交點(diǎn)的基礎(chǔ)上，利用每個(gè)交點(diǎn)在原始多邊形曲線上最近點(diǎn)的所在線段或端點(diǎn)的信息，簡(jiǎn)化與重構(gòu)特征，獲取準(zhǔn)確的偏移曲線.

經(jīng)典MS算法可以保證抽取的偏移曲線是無(wú)自相交的.但是，由于經(jīng)典MS算法通過逐個(gè)處理每個(gè)小網(wǎng)格，連接每個(gè)小網(wǎng)格邊上的交點(diǎn)得到偏移曲線，因而抽取的偏移曲線存在2個(gè)問題：(1)偏移曲線由許多條短直線段組成，即使這些直線段是在一條直線或一段圓弧上，頂點(diǎn)數(shù)亦太多；(2)連接交點(diǎn)成短直線段時(shí)沒有考慮交點(diǎn)的法向信息，丟失了偏移曲線上的尖銳特征，導(dǎo)致生成的偏移曲線不準(zhǔn)確.即使使用自適應(yīng)網(wǎng)格生成的偏移曲線也無(wú)法完全解決上述問題.為此，設(shè)計(jì)了一個(gè)包含簡(jiǎn)化與特征重構(gòu)的后處理過程.

對(duì)平面上的多邊形曲線，其準(zhǔn)確偏移曲線由直線段和圓弧段組合而成.其中，直線段由原始曲線中的直線段偏移得到，圓弧段則由原始曲線中的頂點(diǎn)偏移得到.基于平面偏移曲線的性質(zhì)，在采用經(jīng)典MS算法抽取初始的等距偏移多邊形曲線之后，將考察偏移多邊形曲線上所有頂點(diǎn)的最近點(diǎn)所在的原始曲線的邊或頂點(diǎn)的信息，具有相同原始曲線的邊或頂點(diǎn)信息的偏移多邊形曲線上的所有相鄰頂點(diǎn)將形成一條直線段或圓弧段.

在算法實(shí)現(xiàn)中，用(id1,id2)表示原始多邊形曲線L的邊和頂點(diǎn)信息，其中idk，k=1,2，為原始多邊形曲線頂點(diǎn)的序號(hào).頂點(diǎn)被認(rèn)為是退化的邊.例如，(3,4)表示一條2個(gè)端點(diǎn)在原始多邊形曲線頂點(diǎn)序列中的序號(hào)分別為3和4的邊，(4,4)表示一個(gè)序號(hào)為4的頂點(diǎn).給定初始偏移曲線Lr上2個(gè)相鄰頂點(diǎn)p1和p2的最近點(diǎn)所在原始多邊形曲線的邊或頂點(diǎn)的信息為(id1,id2)和(id3,id4)，

(1)如果id1=id3，id2=id4，且id1≠id2，則表示2個(gè)頂點(diǎn)是由原始多邊形曲線L的同一條邊上的點(diǎn)偏移生成，在偏移曲線Lr中處于同一條直線段上，圖5(a)中紅色虛線矩形框所包圍的點(diǎn)；

(2)如果id1=id3，id2=id4，且id1=id2，則表示2個(gè)頂點(diǎn)由原始多邊形曲線L的同一個(gè)頂點(diǎn)偏移生成，在偏移曲線Lr中處于同一圓弧段上，圖5(a)中紅色虛線橢圓框所包圍的點(diǎn)；

(3)如果id1≠id3或id2≠id4，則表示2個(gè)頂點(diǎn)分別由原始多邊形曲線L的3條邊上的點(diǎn)或1條邊與1個(gè)頂點(diǎn)或2個(gè)頂點(diǎn)偏移生成，偏移曲線Lr在這2個(gè)點(diǎn)之間會(huì)形成2條直線段或1條線段1條圓弧段或2條圓弧段的交點(diǎn)，如圖5(a)所示綠色虛線橢圓框和藍(lán)色虛線矩形框所包圍的點(diǎn).

通過式(1)和(2)減少偏移曲線上的頂點(diǎn)數(shù)，如圖5(b)所示；由式(3)重構(gòu)尖銳特征，生成準(zhǔn)確的偏移曲線，如圖5(c)所示.

圖5 等距曲線簡(jiǎn)化與特征重構(gòu)Fig.5 Offset curve simplification and feature reconstruction(a)抽取出的初始等距曲線，每一個(gè)頂點(diǎn)保留其最近點(diǎn)所在原始曲線中邊的信息，并根據(jù)這些信息進(jìn)行分組;(b)根據(jù)(a)的分組結(jié)果進(jìn)行拼合，形成長(zhǎng)的直線段并重構(gòu)圓弧特征，減少頂點(diǎn)數(shù)；(c)根據(jù)交點(diǎn)最近點(diǎn)信息的變化，計(jì)算直線段之間.直線段與圓弧段，及圓弧段之間的交點(diǎn)，重構(gòu)尖銳特征，生成準(zhǔn)確的偏移曲線.(a)An extracted initial offset curve where all vertices are grouped with their closest points and relating original edges; (b)Longer line segment and arc features are recovered by merging the vertices according to the clusters, and vertices are reduced; (c)Sharp features are reconstructed and then an exact offset curve is generated according to the variations of the intersections computed between line segments, line segment and arc segment, and arc segments.

6 實(shí)驗(yàn)結(jié)果與討論

使用VC++實(shí)現(xiàn)本文算法，并在普通配置的個(gè)人手提電腦上使用不同的數(shù)據(jù)實(shí)例進(jìn)行算法測(cè)試.使用本文算法對(duì)不同的平面多邊形曲線采用不同的偏移值進(jìn)行向內(nèi)和向外偏移，得到了一系列結(jié)果和統(tǒng)計(jì)數(shù)據(jù)，如圖6、7和表1～4所示.

圖6給出了采用本文方法在512×512網(wǎng)格上生成不同偏移距離并經(jīng)過簡(jiǎn)化和特征重構(gòu)的5條不同形狀的偏移曲線，其中“手”“花”“京劇臉譜”“馬”和“老鼠”曲線形狀中分別包含188，1 303，1 831，1 781和2 075個(gè)頂點(diǎn).5條不同形狀曲線的給定距離偏移曲線的計(jì)算時(shí)間及誤差的統(tǒng)計(jì)信息見表1.由表1可知，所有給定曲線的偏移曲線都可在不超過0.25 s的時(shí)間內(nèi)生成.對(duì)抽取的初始偏移曲線進(jìn)行簡(jiǎn)化及特征重構(gòu)，可減少偏移曲線的頂點(diǎn)數(shù),提高偏移曲線的逼近精度.由表2知，簡(jiǎn)化后的偏移曲線頂點(diǎn)數(shù)不到初始偏移曲線頂點(diǎn)數(shù)的25%，精度至少是初始偏移曲線的106倍，達(dá)到了10-8，基本上可以認(rèn)為是準(zhǔn)確偏移曲線.

圖6 使用不同偏移距離進(jìn)行偏移的結(jié)果Fig.6 Offsetting results with different offset distances網(wǎng)格分辨率512×512.The dimensions of the grid is 512×512.

圖7 給定曲線形狀在不同分辨率網(wǎng)格上使用不同偏移距離進(jìn)行偏移的結(jié)果Fig.7 The offsetting results in different resolution grids with different offset distances for the given curve shapes其中，黑色實(shí)線為給定的曲線形狀,第1行與第3行為初始偏移曲線，第2行與第4行為簡(jiǎn)化及特征重構(gòu)后的偏移曲線.Here, the black curve are the given shapes, and the first and third rows are the initial offset curves while the second and fourth rows are the final offset results after simplification and feature reconstruction.

曲線形狀頂點(diǎn)數(shù)偏移距離計(jì)算時(shí)間/msT1T2T3Ttol初始偏移曲線頂點(diǎn)數(shù)平均誤差簡(jiǎn)化偏移曲線頂點(diǎn)數(shù)平均誤差手188-2201091612519589．9×10-41510．00花1303-11161563220421861．3×10-33780．00臉譜1831-22151573120320401．4×10-33230．00馬1781-25161873123424161．8×10-32052．2×10-9老鼠2075-25161723121922581．7×10-31918×10-10

注T1為構(gòu)造掃掠圓片層次結(jié)構(gòu)的時(shí)間，T2為分辨率為512×512的網(wǎng)格上構(gòu)造距離場(chǎng)的時(shí)間，T3為抽取偏移曲線的時(shí)間，包括抽取初始偏移曲線和簡(jiǎn)化的時(shí)間，Ttol為前3項(xiàng)的總和.

當(dāng)原始曲線采用一般樣條曲線表時(shí)，可以先采用直線段自適應(yīng)進(jìn)行近似，轉(zhuǎn)化成多邊形曲線，然后使用本文算法進(jìn)行處理.初始偏移曲線的簡(jiǎn)化依然可以提高偏移曲線的精度.

圖7顯示的是對(duì)2個(gè)形狀復(fù)雜性不同的曲線在不同分辨率的網(wǎng)格上進(jìn)行不同距離的偏移結(jié)果，同時(shí)給出了簡(jiǎn)化前后的曲線形狀及頂點(diǎn)，頂點(diǎn)用紅色進(jìn)行標(biāo)記.形狀簡(jiǎn)單的“五角星”曲線包含10個(gè)頂點(diǎn)，偏移距離為25，而形狀復(fù)雜的“豬”的曲線包含1 271個(gè)頂點(diǎn)，偏移距離為15.圖中對(duì)于使用分辨率較高的網(wǎng)格生成的偏移曲線，由于頂點(diǎn)太多，無(wú)法顯示曲線的頂點(diǎn)，見圖7(d)和(e)的第1個(gè)和第3個(gè)圖.圖7中第1行與第3行為初始偏移曲線，第2行與第4行為對(duì)應(yīng)簡(jiǎn)化及特征重構(gòu)后的偏移曲線.由圖7知，在分辨率較小的網(wǎng)格上，抽取出的初始偏移曲線丟失了尖銳特征，且圓弧特征的逼近很粗糙，如圖7(a)第1和第3個(gè)結(jié)果所示.隨著分辨率的增大，曲線上的尖銳特征逐步恢復(fù)，且圓弧特征的逼近精度逐漸改善，如圖7(b)～(e)第1行和第3行所示.

表2 不同分辨率網(wǎng)格中生成偏移曲線的統(tǒng)計(jì)數(shù)據(jù)

從圖7第2行和第4行的結(jié)果中發(fā)現(xiàn)，當(dāng)采用分辨率較小的網(wǎng)格，如32×32，偏移曲線的簡(jiǎn)化和特征重構(gòu)效果非常明顯，尤其是對(duì)形狀簡(jiǎn)單的曲線.在低分辨率的網(wǎng)格上對(duì)簡(jiǎn)單曲線構(gòu)造的偏移曲線進(jìn)行簡(jiǎn)化和特征重構(gòu)，簡(jiǎn)化后的偏移曲線逼近精度比在高分辨率網(wǎng)格上構(gòu)造的初始偏移曲線更高，且與它們的簡(jiǎn)化結(jié)果曲線相同，見圖7第2行的偏移曲線，表2中的數(shù)據(jù)也說明了這點(diǎn).所以使用本文方法在構(gòu)造包含長(zhǎng)直線段曲線的偏移曲線時(shí)，可先在低分辨率的網(wǎng)格上生成初始偏移曲線，然后進(jìn)行簡(jiǎn)化.

為了研究本文提出的過濾器的性能，在構(gòu)造局部距離場(chǎng)時(shí)測(cè)試了所能減少的最近距離計(jì)算次數(shù).這里，最近距離計(jì)算指使用基于分層掃掠圓片過濾器的方法進(jìn)行的點(diǎn)到曲線最近距離計(jì)算.分別對(duì)簡(jiǎn)單形狀曲線“五角星”和復(fù)雜形狀曲線“豬”在513×513的均勻劃分網(wǎng)格上構(gòu)造偏移曲線附件的窄帶距離場(chǎng).測(cè)試了4種過濾器組合形式：(1)只使用包圍盒，m×m表示2個(gè)方向上使用m個(gè)包圍盒；(2)使用包圍盒和內(nèi)/外過濾器；(3)四叉樹過濾器；(4)使用內(nèi)/外過濾器和四叉樹過濾器.由表3的統(tǒng)計(jì)數(shù)據(jù)不難發(fā)現(xiàn)，使用內(nèi)/外和四叉樹過濾器可以剔除網(wǎng)格點(diǎn)上約92.9%～94.3%的無(wú)效計(jì)算.

測(cè)試了混合計(jì)算有效邊上交點(diǎn)的算法效率.基于頂點(diǎn)數(shù)不同的曲線形狀，表4統(tǒng)計(jì)了不同分辨率網(wǎng)格中具有交點(diǎn)的有效網(wǎng)格邊數(shù)量.不難發(fā)現(xiàn)，98.5%的邊使用混合方法可在不超過6次細(xì)分操作下找到交點(diǎn)，而使用二分查找法，只有不到20%的邊能在不超過6次細(xì)分操作下找到交點(diǎn).由此可見，混合方法大大提高了求交的效率.

表3 使用不同過濾器進(jìn)行點(diǎn)到曲線最近距離計(jì)算次數(shù)的統(tǒng)計(jì)

圖8 用本文方法對(duì)圖1中的5種曲線生成準(zhǔn)確的偏移曲線Fig.8 Exact offset curves generated by our method corresponding to five cases in Fig.1

曲線形狀頂點(diǎn)數(shù)偏移距離分辨率有效邊數(shù)混合方法0次二分1次二分2次二分小于6次二分法小于6次五角星1015128618611236170256124012303412390512248424745224840豬12711512847430663474672625695275587469491205121910171096541907375

本文方法能有效處理圖1中文獻(xiàn)[4-8,10-14]方法難以解決的問題，能生成連續(xù)、準(zhǔn)確的偏移曲線.圖8給出了本文方法處理對(duì)應(yīng)于圖1中示例的結(jié)果.黑實(shí)線為原始給定多邊形曲線，淺色線為生成的偏移曲線.

表5給出了3條給定的原始曲線用本文和文獻(xiàn)[10]方法生成的偏移曲線結(jié)果的比較.在生成偏移曲線過程中，本文方法采用了分辨率為512×512的均勻網(wǎng)格，因而耗時(shí)比文獻(xiàn)[10]方法長(zhǎng).但依然能達(dá)到交互的計(jì)算速率，滿足用戶交互設(shè)計(jì)的要求.另外，本文方法生成的偏移曲線比文獻(xiàn)[10]方法更準(zhǔn)確，平均精度超過文獻(xiàn)[10]100倍.圖9給出了對(duì)應(yīng)圖形顯示的比較結(jié)果,可明顯看到，在內(nèi)角大于180°處，本文方法生成的偏移曲線更光滑、準(zhǔn)確.采用文獻(xiàn)[10]程序生成結(jié)果時(shí)，發(fā)現(xiàn)只能處理內(nèi)偏移，對(duì)較大偏移距離無(wú)法得到結(jié)果或所得結(jié)果錯(cuò)誤.

7 結(jié) 論

提出了一種快速、魯棒計(jì)算平面多邊形曲線的無(wú)自相交、準(zhǔn)確偏移曲線的方法.算法的基本思想是在一個(gè)均勻網(wǎng)格上基于給定曲線的局部有向距離場(chǎng)采樣，然后利用等值線抽取算法得到偏移曲線.基于距離場(chǎng)的方法可以減少經(jīng)典方法中對(duì)偏移曲線上某段有效性的判斷及相關(guān)處理工作.通過使用3個(gè)過濾器消除在距離場(chǎng)構(gòu)造過程中的大量冗余計(jì)算，從而高效生成局部有向距離場(chǎng).采用經(jīng)典的等值線抽取方法可以獲得初始偏移曲線.在曲線抽取過程中，采用基于解析解和二分法的混合交點(diǎn)計(jì)算方法，大大縮短了查找過程，實(shí)現(xiàn)了等值線的快速抽取.在偏移曲線與網(wǎng)格邊的交點(diǎn)計(jì)算過程中，根據(jù)保存的最近點(diǎn)的位置信息，用長(zhǎng)直線段或圓弧段表示端點(diǎn)具有相同最近點(diǎn)位置信息的短線段，并進(jìn)行合并.初始偏移曲線上相鄰頂點(diǎn)的最近點(diǎn)位置信息的變化，標(biāo)識(shí)了原始曲線中線段的變化，據(jù)此可在偏移曲線上計(jì)算相鄰直線段之間、直線段與圓弧段、圓弧段之間的交點(diǎn)，以重構(gòu)偏移曲線上的尖銳特征，最終獲得準(zhǔn)確的偏移曲線.文中的大量例子和統(tǒng)計(jì)數(shù)據(jù)都有力地說明了本方法的良好性能和優(yōu)勢(shì).

[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.

QIN Rui1,2, LIU Shengjun1,2, CHEN Zitai1,2, YUAN Weixiong1,2, ZHANG Fan1,2, LIU Xinru1,2

(1.InstituteofEngineeringModelingandScientificComputing,CentralSouthUniversity,Changsha410083,China; 2.SchoolofMathematicsandStatistics,CentralSouthUniversity,Changsha410083,China)

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.

offset curve; distance field; intersection-free; filter; analytic solution

2016-07-25.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61572527,61602524)；湖南省科技計(jì)劃重點(diǎn)項(xiàng)目(2014FJ2008).

秦 睿(1995-)，ORCID:http://orcid.org/0000-0002-0914-5104，男，本科生，主要從事幾何計(jì)算與優(yōu)化算法研究.

*通信作者，ORCID:http://orcid.org/0000-0001-5427-0178，E-mail：liuxinru@csu.edu.cn.

10.3785/j.issn.1008-9497.2017.01.002

TP 391

A

1008-9497(2017)01-010-12