基于距離場的二維偏移曲線快速生成方法

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

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

基于距離場的二維偏移曲線快速生成方法

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

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

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

偏移曲線；距離場；無自相交；過濾器；解析法

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

0 引 言

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

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

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

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

(1)

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

本文的主要貢獻：

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

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

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

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

圖1 實例展示現(xiàn)有方法的不足Fig.1 Examples showing the limitations of the existing methods(a)基于邊偏移的方法，需要解決自相交和不連續(xù)性問題[4-8];(b)文獻[14]失敗的例子;(c)文獻[11-12]失敗的例子;(d)文獻[13]誤判的例子;(e)文獻[10]生成不準確的等距曲線，即使經(jīng)過截斷，其中虛線圓弧段為準確偏移線，黑色點橫線為算法執(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 相關工作

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

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

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

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

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

2 算法概述

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

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

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

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

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

圖2 算法框架Fig.2 The method framework(a)嵌入到一個均勻剖分的網(wǎng)格中，對給定的二維多邊形曲線，計算局部距離場；(b)找到有效網(wǎng)格邊，計算偏移曲線與網(wǎng)格邊的交點；(c)抽取出等距偏移曲線；(d)簡化和特征重構(gòu)生成準確等距曲線.(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 局部距離場快速構(gòu)造

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

3.1 分層掃掠圓片過濾器

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

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

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

(2)

3.2 四叉樹過濾器

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

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

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

(3)

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

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

圖3 四叉樹過濾器示意圖Fig.3 Quad-tree filter實心點為有效點，空心點為無效點.Solid points are valid, while empty points are invalid.

定義2 對于一個對角線長度為2δ的包圍盒，若其中心cb到給定曲線L的距離滿足

(4)

則稱為無效包圍盒.否則，稱為有效包圍盒.

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

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

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

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

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

(5)

其中nc為點p在給定曲線L上的最近點pc處的角度加權法向.

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

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

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

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

f(p1)f(p2)<0，

(6)

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

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

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

(7)

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

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

4.1 混合法

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

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

(8)

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

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

算法1 混合法計算交點

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

輸出 交點p.

步驟：

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

(2)使用解析法計算交點p(見5.2節(jié))；

(3)ELSE；

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

(5)END IF；

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

(7) 輸出交點p;

(8)ELSE；

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

(10)END IF.

對處于線段2個端點位置的情況需要進一步計算，以便判斷p1,c和p2,c是否在同一條線段上.因為最近點計算過程給出的結(jié)果可能是2個點不在同一條線段上，但屬于下列情況之一：

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

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

4.2 解析解

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

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

圖4 偏移曲線與網(wǎng)格邊交點解析計算示意圖Fig.4 Illustration for analytically computing the intersections between the grid edges and the offset curve(a)一條線段與其2個端點處的垂線將平面分為3個區(qū)域；(b)處于線區(qū)域的線段;(c)處于端點區(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)的所有點q的最近點都落在線段l內(nèi)部，如圖4(a)所示的區(qū)域2；

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

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

(9)

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

(10)

計算，其中α∈[0,1].

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

5 準確偏移曲線的生成

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

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

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

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

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

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

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

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

圖5 等距曲線簡化與特征重構(gòu)Fig.5 Offset curve simplification and feature reconstruction(a)抽取出的初始等距曲線，每一個頂點保留其最近點所在原始曲線中邊的信息，并根據(jù)這些信息進行分組;(b)根據(jù)(a)的分組結(jié)果進行拼合，形成長的直線段并重構(gòu)圓弧特征，減少頂點數(shù)；(c)根據(jù)交點最近點信息的變化，計算直線段之間.直線段與圓弧段，及圓弧段之間的交點，重構(gòu)尖銳特征，生成準確的偏移曲線.(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 實驗結(jié)果與討論

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

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

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

圖7 給定曲線形狀在不同分辨率網(wǎng)格上使用不同偏移距離進行偏移的結(jié)果Fig.7 The offsetting results in different resolution grids with different offset distances for the given curve shapes其中，黑色實線為給定的曲線形狀,第1行與第3行為初始偏移曲線，第2行與第4行為簡化及特征重構(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.

曲線形狀頂點數(shù)偏移距離計算時間/msT1T2T3Ttol初始偏移曲線頂點數(shù)平均誤差簡化偏移曲線頂點數(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)的時間，T2為分辨率為512×512的網(wǎng)格上構(gòu)造距離場的時間，T3為抽取偏移曲線的時間，包括抽取初始偏移曲線和簡化的時間，Ttol為前3項的總和.

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

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

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

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

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

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

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

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

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

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

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

7 結(jié) 論

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

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

國家自然科學基金資助項目(61572527,61602524)；湖南省科技計劃重點項目(2014FJ2008).

秦 睿(1995-)，ORCID:http://orcid.org/0000-0002-0914-5104，男，本科生，主要從事幾何計算與優(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