點云模型的切片式曲面重構算法設計

陳華偉 袁小翠 伍 權

1(貴州師范大學機電工程學院 貴州 貴陽 550025)2(南昌工程學院江西省精密驅動與控制重點實驗室 江西 南昌 330099)

0 引 言

非均勻有理B樣條(Non-Uniform Rational B-Splines,NURBS)曲面[1-2]為雙參數曲面，其定義域為四邊域，具有規則的u、v方向控制點數(點陣)。因此，在進行曲面擬合時，要求規則的型值點輸入。而點云模型輸入是大數據量的散亂點云，對機械產品而言，常規的做法是根據正向建模的思想，提取點云形貌中的型線或型面特征，然后再逐面重新構建[3]。該方法可以精細化構面，但是對復雜點云模型，其逆向建模過程相當復雜，建模效率低。因而，在商業設計環境下，需要更快捷，而又不失建模質量的方法。切片法采用切片方式對模型進行分割，在二維分割面上提取切片邊界，然后通過蒙皮的方式構造曲面，可以很方便地構造NURBS曲面四邊域并重構曲面表面，因而成為NURBS曲面逆向建模的重要方法。輪船船身、飛機機翼等大曲面的模線法曲面重構[4]也是切片法的具體體現。

1 算法流程

NURBS是STEP標準中工業產品幾何形狀建模的基本數學方法，因而，由該方法構建的NURBS曲線面兼容于不同的CAD軟件，是當前曲線面建模的主要方法。NURBS曲線數學表達式為：

(1)

式中:ωi為權因子，Pi為控制點，Ni,p(u)為p次B樣條基函數，當p=3時，稱之為三次B樣條曲線。

對應地，NURBS曲面數學表達式為：

(2)

式中:ωi,j為權因子，Pi,j為控制點，Ni,p(u)、Nj,q(v)分別為u方向p次和v方向q次B樣條基函數，m、n分別為u、v方向的控制點數。當m=n=3時，稱之為雙三次B樣條曲面。

以散亂點云模型為輸入，通過切片法重構NURBS曲面，主要經過點云切片分割、切片邊界提取、曲面擬合等步驟，并逐步產生規則點集、線和面模型，實現模型的降維增維和有序化處理，處理流程如圖1所示。

2 點云切片式分割

2.1 切片設計

區域分割時首先需要確定分割方向，不失一般性，通過構造包圍盒，沿包圍盒主軸方向進行區域劃分。圖2中，包圍盒0123-4567可由最小坐標點0(xmin,ymin,zmin)和最大坐標點6(xmax,ymax,zmax)確定，并與XYZ坐標系方向一致。以Z軸為分割方向，可得其中一分割面0′1′2′3′。

圖2 沿包圍盒主軸方向分割

接下來，采用等區間分割法，將點云劃分至各等分區間。為了便于后續投影計算，設定每個分割面的影響范圍為其左右半區域內的點。如圖3所示，設分割方向為Z軸，則第i個分割面的Z坐標zi=zmin+i×seg(i=0,1,…,U)，其中seg=(zmax-zmin)/U為區間高度，U為區間數。

圖3 等區間分割

三點即可構面，在分割面內任取不共線的三點即可確定分割面方程，設已取三點Pti(xi,yi,zi),i=0,1,2，則可求分割面法矢：

分割面方程為：

F(x,y,z)=A(x-x0)+B(y-y0)+C(z-z0)=

Ax+By+Cz+D=0

(3)

式中：常數項D=-Ax0-By0-Cz0。

區域Ui由相鄰切平面Pi和Pi+1所夾，則按式(4)確定數據點與區域的歸屬關系：

FiFi+1<0

(4)

遍歷所有點，如果點滿足式(4)，則該點劃歸區域Ui。

2.2 切片數據結構設計

合理的切片數據結構設計將有效支撐切片式重構的各階段，其中，切片和切片邊界數據結構用于切片數據分割、存貯、邊界的對象和過程描述，其結果數據還可直接用于NURBS曲線、曲面擬合。不失一般性，給出這兩項重要的數據結構。

structSlice

//切片

{

Axis axis;

//分割方向為軸向X/Y/Z

std::vectorpl;

//分割面

std::vector>vL;

//左半區域點集

std::vector>vR;

//右半區域點集

};

切片數據結構Slice主要描述了切片方向axis、分割面pl和切片左右半區域(見圖2)的點集vL、vR。

structSliceBoundary

//切片邊界

{

Planepl;

boolbClosed;

std::vectorv;

};

切片邊界結構SliceBoundary主要描述了邊界所在分割面pl，邊界是否閉合bClosed和邊界點集v。

3 切片邊界提取

3.1 區域點向分割面投影

對于區域內的點，以半區域位置為界限，將通過算法將半區域內的點映射到鄰近分割面內。圖3中，首分割面只有右半區域(00′區域)，末分割面只有左半區域，將通過投影法直接將半區域內的點映射至對應分割面。假設D為平面ABC外一點，點D在平面上的投影點D′，由向量關系得DD′⊥AB，故有：

DD′·AB=0

(5)

同理，DP⊥AC，有：

DD′·AC=0

(6)

聯立式(3)、式(5)、式(6)為三元一次方程組，可求出D′。

3.2 分割面上點集的邊界提取

點云邊界提取算法很多，簡單模型可采用場力法和轉角法[5]。映射點集均位于分割面上，對平面內點云可以采用轉角法提取點集的凸包邊界，其主要思路為：

1) 預定義一坐標軸為參考方向，記為向量v1；搜尋最小坐標點作為邊界起點，記為startPoint。

2) 在startPoint鄰域內搜索下一點。遍歷鄰域內的點Ptk，Ptk與startPoint形成向量v2，計算向量夾角v1∧v2，將最大夾角對應的點Ptk加入邊界點集。

3) 置v1=v2，繼續上述搜索；直到找到一個邊界點與startPoint相同。

顯然，采用轉角法獲取的邊界為首尾相連的閉合邊界，而且邊界點集是有序點集，其順序就代表了邊界方向。

3.3 邊界閉合性和一致性調整

實際模型中，方向投影邊界有閉合和非閉合之分，而且為了保證后續曲面擬合，要求所有邊界同時為打斷或閉合狀態，對于非閉合邊界，還需要進行打斷或解環操作。

打斷后，邊界方向可能不一致，應及時更新邊界起點和邊界點序，如圖4。面向NURBS曲面擬合，應確保每個分割面上邊界方向一致性。定義分割面的法向為正，分割面內的邊界按右手法則為正。下面以PmaxI為基準面，進行邊界方向調整：1) 對于分割面PmaxI，采用三點法計算分割面法向dir，作為所有分割面的正向；2) 遍歷分割面Pi(i=0,1,…,U)，對每個分割面，計算其法向diri，判斷dir·diri>0，則認定Pi與PmaxI同向；否則為異向；3) 異向的情況下，采用二分算法倒置Pi內的邊界點序。

圖4 邊界方向

進行打斷操作后可獲得非閉合邊界，其邊界起點自然確定。但是對于閉合邊界，面向NURBS曲面擬合，還需要確保各條邊界起點位置的一致性。設第0條邊界上的第1個點為v0，邊界點集重心為vc0，另設第1條邊界點集的重心為vc1，構造平面p(v0,vc0,vc1)，如圖5所示。設定位于平面p右側，且與平面p及v0點距離和最短的點為邊界起點，即所求點vj位于p的法矢正向，且滿足max(|v0,vj|+|vj,vc0|)。確定了各邊界的起點之后，應對邊界其他點進行順調。

圖5 邊界起點一致性調整

4 NURBS曲面擬合

由分割面邊界點可直接擬合出各條邊界曲線[6]。在NURBS曲線擬合中，如果型值點數為n，控制點數為m，則要求m

曲線擬合中存在型值點分布不均的情況，這對曲線擬合影響不大，但會影響到曲面擬合的效果。NURBS曲面擬合需要輸入規則點陣，而且應盡量保證型值點陣分布的均勻性。對此，通過對擬合曲線進行采樣或插值[7-8]的方法，重新采集型值點，形成規則化的U×V型值點點陣，用于NURBS曲面擬合。

將初始點集向擬合后的曲面投影，計算初始點與投影點之間的距離即為擬合誤差[7-9]，統計所有擬合點的誤差，可得平均誤差、最大誤差等參數，作為曲面擬合質量評價。

總體上，NURBS曲面擬合過程包括以下四個步驟：

1) 曲線擬合：以分割面Pi邊界點集為輸入，擬合NURBS曲線Ci,i=0,1,…,U；

2) 均勻采樣：采用deBoor算法，對Ci進行等間隔插值采樣，得到U×V型值點點陣；

3) 曲面擬合：采用插值算法生成NURBS曲面S；

4) 誤差分析：采用投影算法計算初始點集至S的距離誤差，進行誤差分析。

5 實 驗

以上算法在CATIA RADE(Rapid Application Development Environment)開發平臺通過二次開發實現，其中，NURBS曲線曲面擬合和編輯功能由CAA開發接口提供，外界可直接調用，有關CATIA環境下NURBS曲線面重構算法可參考文獻[10]。下面以花瓶模型為例，對切片和NURBS曲線面擬合過程進行說明。

如圖6所示的實驗一是未對邊界作閉合性和一致性調整的結果，顯然，沿X軸和Y軸分割的曲面擬合結果是錯誤的，只有沿Z軸剖切的曲面擬合結果是正確的。這主要是由于剖切方向不同，引起分割面邊界線長短及其分布差距太大(圖6(b)、(d))，得到的點陣難以構成四邊域(圖6(d))等問題。但是從圖6(f)-(h))可見，與花瓶主軸方向一致的分割就能獲得很好的曲面重構效果。

圖6 實驗一(6個分割面)

為此，通過改進算法，并對分割面邊界進行閉合性和一致性調整，就能獲得更好的擬合效果，如圖7所示的實驗二。沿X軸分割時，由于在側邊緣上難以分割到足夠點，導致側邊緣部位邊界線趨短，右側曲面出現了漏洞；沿Y軸分割時，由于在后側難以分割到足夠點，導致后側邊緣部位邊界線趨短且不規則，后側上方花瓶口部位曲面出現劇烈變形；顯然，只有沿Z軸分割的曲面擬合結果最好。整體上，經過程序優化后，各方向分割均能得到直觀的曲面擬合效果。

圖7 實驗二(20個分割面)

由圖6(g)和圖7(d)對比可知，隨著分割面的密度增大，擬合曲面越光滑，說明通過適當增加分割曲線及其采樣型值點密度，可提高NURBS曲面擬合精度。圖7(a)中擬合面出現了明顯的褶皺，也可通過適當提高采樣密度的方法進一步提高曲面重構效果。

基于CATIA二次開發成果，還通過自主開發實現了上述算法。基于VC和OpenGL平臺開發，其中NURBS曲線曲面擬合算法通過集成NURBS++開源算法庫實現。如圖8所示的實驗三，通過模型主軸方向的分割和擬合均達到了預想的效果。

圖8 實驗三

6 結 語

NURBS曲面是四邊域曲面，重構過程中要求事先準確劃分四邊形區域，或者提取規范的型值點點陣。對散亂大數據點云模型擬合NURBS曲面，應順應模型特征，構造合適的四邊域。理論上，切片式分割擬合可規避復雜的模型特征，將三維曲面擬合問題降維至二維曲線擬合問題，提高曲面構建的效率和成本；曲面構建的精度則可以通過加密切片數量和增加型值點采樣密度實現。但是，對特征線面多(如機械零件)、細節特征多(雕塑)等復雜模型，簡單地通過一次剖切和重構就能實現曲面重構的想法顯然不切實際。根據CAD中正向設計的思想，通過點云區域分割、分片曲面擬合、曲面拼接步驟才能更準確地表達原始模型的型面特征，這也是有待展開研究的內容。