高斯投影下的人機交互式物體仿真算法研究

杜麗美，連 瑋

長治學(xué)院 計算機系，山西 長治046000

1 引言

物體重建技術(shù)是當(dāng)今研究的熱點問題之一，主要手段可以借助激光掃描技術(shù)、紅外線測距技術(shù)或相關(guān)軟件獲取真實物體表面三維點云數(shù)據(jù)，由于測量誤差的存在，通過各種途徑獲取的點云數(shù)據(jù)會摻雜噪聲點，所以從物體表面獲取較高質(zhì)量的點云數(shù)據(jù)直接影響后期的物體重建效果。一般從物體表面獲取的三維點云數(shù)據(jù)量非常龐大，針對不同的物體可能需要提取成千甚至上萬的數(shù)據(jù)點，如果直接將這些數(shù)據(jù)點顯示在屏幕上，雖然也可以展現(xiàn)出物體的全貌，但是卻得不到一個完整的物體，因為物體由點描述其結(jié)構(gòu)較松散，導(dǎo)致無法使用在一些專業(yè)領(lǐng)域中，所以要做的是將這些點云數(shù)據(jù)重構(gòu)出相應(yīng)的面片，使其成為一個結(jié)構(gòu)完整的整體。物體的重構(gòu)技術(shù)可以應(yīng)用到許多領(lǐng)域、比如醫(yī)學(xué)重建、古建筑物修復(fù)、3D打印等。

文獻[1]提出一種點云融合技術(shù)，在重建過程中采用類似投影的方式重建網(wǎng)格模型，最終將重建的模型用于3D 打印過程中。文獻[2]采用物體重建的方法對建筑物損傷部位進行修復(fù)，重建過程借助最小二乘法原理進行曲面擬合達到了很好的效果。文獻[3]對蘋果樹葉片進行三維重建，用到了包圍盒法對點云數(shù)據(jù)進行去噪，又用到了精簡算法對點云數(shù)據(jù)進行精簡，最后使用Delaunay 三角網(wǎng)格劃分算法進行了重建。以上文獻中介紹了不同的網(wǎng)格重建算法，這些算法只是針對解決特定的問題提出，因而本身具有很大的局限性。本文將提出一種通用的網(wǎng)格劃分算法用來對給定的物體進行仿真重建。

2 點云數(shù)據(jù)處理

利用三維激光掃描技術(shù)，通過三維激光掃描儀發(fā)射出來的光束，照射到物體表面，從而獲取到物體表面的三維點云數(shù)據(jù)坐標(biāo)，并將數(shù)據(jù)保存在后綴名為.obj的文檔中，保存格式如圖1所示，圖1所示文件中第一行為該物體的紋理信息，存儲在.mtl 的文件中（若物體沒有紋理特征，則刪除本行），以“v”開頭的信息即為掃描到的三維數(shù)據(jù)點坐標(biāo)。采用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)存儲圖1 中的數(shù)據(jù)點（注意：這里定義的數(shù)據(jù)結(jié)構(gòu)應(yīng)至少包括點的三個坐標(biāo)值，點的索引值，以及指向前一個點和后一個點的指針），由于數(shù)據(jù)點中必定摻雜噪聲，所以第一步要做的就是進行去噪處理，由于采集了大量的數(shù)據(jù)點，這里可以采用概率統(tǒng)計中的方法來去噪[4-5]，去噪思想是通過球內(nèi)大量點的數(shù)據(jù)信息估算出點的大致規(guī)律，如果目標(biāo)點滿足這一規(guī)律則留下，否則去掉。

圖1 點云數(shù)據(jù)的存儲

具體的去噪方法如圖2所示：要判斷點P 是否為噪聲點，先以P(X0,Y0,Z0)為球心，以r 為半徑作球（r 的值根據(jù)實際情況自行設(shè)定），利用公式（1）判斷所有數(shù)據(jù)點哪些落在球內(nèi)部，設(shè)集合A 中的點{p1,p2,…,pk}均為落在球內(nèi)部的點，然后分別計算集合A 外的所有點到集合A 中p1 的平均距離、p2 的平均距離、…、pk 的平均距離，利用公式（2）和（3）求出這些平均距離的平均值μ 以及方差σ2：

圖2 去噪過程

3 初始網(wǎng)格模型的構(gòu)造

由于物體表面的點云數(shù)據(jù)都是三維點的坐標(biāo)，直接對這些點進行三角網(wǎng)格的劃分會導(dǎo)致難度過大，而且效率低下。目前為止人們對于二維數(shù)據(jù)點的三角網(wǎng)格劃分算法研究得比較成熟，而且算法相對簡單，為此本文的主要思想是先將三維數(shù)據(jù)點投影到二維平面上，如果直接進行投影，必定會改變點與點之間的位置信息，導(dǎo)致重建出的三維模型不準(zhǔn)確或者是失真等現(xiàn)象，本章將提出一種新的投影方法來解決此問題。

3.1 分區(qū)域生成三角網(wǎng)格

為了保證將三維數(shù)據(jù)點投影到二維平面上后，點與點之間的角度等信息不變，這里將使用高斯投影的方法，高斯投影是一種等角投影方法，借助地理坐標(biāo)系統(tǒng)中經(jīng)度和緯度的概念，主要思想是將橢球面按一定的經(jīng)度間隔劃分成若干區(qū)域塊，然后分別將每個區(qū)域塊的點投影到二維平面上，這種投影方法可以保證橢球面上的點在投影前后的相對位置保持不變。

利用高斯投影[6-7]的思想，這里將橢球面看成圓球，首先求出點云數(shù)據(jù)在X 方向上的最大長度length Y 方向上的最大寬度width以及Z 方向上的最大高度height，設(shè)定圓球的半徑為R=max(length,width,height)/2，球心為O(length/2,width/2,height/2) ，也就是所作圓球內(nèi)要包含所有點云數(shù)據(jù)如圖3所示，然后從球心分別指向每一個數(shù)據(jù)點的射線必定與球面交于一點如圖4 所示，例如球心與數(shù)據(jù)點P 的連線交球面于點P′，那么點P 與P′就建立了一對一的關(guān)系，P′的坐標(biāo)可以由相應(yīng)的經(jīng)度和緯度表示，如圖5 所示，作P′在XOY 平面上的垂線并交于P″，則∠P″OX 所對度數(shù)為點P′的經(jīng)度用α 表示，∠P′OP″所對度數(shù)為點P′的緯度用β 表示，設(shè)P′坐標(biāo)為(x,y,z)，由于此時的球心坐標(biāo)并不是（0，0，0），故先使用公式（4）計算OP' 的坐標(biāo)，然后經(jīng)度α 和緯度β 可由公式（5）和（6）求出。

圖3 作圓球包含所有數(shù)據(jù)點

圖4 球心與數(shù)據(jù)點連線

圖5 計算P′的經(jīng)度α 和緯度β

由于點云數(shù)據(jù)點較多，直接投影難免會遇到一些未知錯誤，所以這里借助大地經(jīng)度和緯度的知識，將球面按經(jīng)差n 度進行分帶（n 可以選擇6的整數(shù)倍，如6，12，18，24 等），這樣球面會被劃分成360/n 個區(qū)域，將每一區(qū)域中的點云數(shù)據(jù)采用簡化后的高斯投影公式（7）和（8）分別投影到二維平面中，得到對應(yīng)的二維數(shù)據(jù)點坐標(biāo)(x,y)，公式中的R 為球面半徑，β 為點的緯度，l 為點的經(jīng)度與中央子午線經(jīng)度的差值（此處的中央子午線經(jīng)度值指的是每一帶的中間位置所對的經(jīng)度值）。公式（7）和（8）中的A、A′、t、ρ 分別由公式（9）、（10）、（11）和（12）給出。

對每一區(qū)域內(nèi)投影到平面上的二維數(shù)據(jù)點進行三角網(wǎng)格的劃分如圖6所示，重點得到二維平面上點與點的連接關(guān)系，將這種連接關(guān)系反映射[8-10]回原三維數(shù)據(jù)點上，即完成了每一區(qū)域內(nèi)三維數(shù)據(jù)點的網(wǎng)格劃分。

圖6 高斯投影演示

3.2 區(qū)域間拼接

由3.1節(jié)中的算法可將每個區(qū)域內(nèi)的三維數(shù)據(jù)點進行三角網(wǎng)格的劃分如圖7所示，本節(jié)主要完成區(qū)域間的拼接。要想進行區(qū)域間的無縫拼接，第一步就是提取圖7 中每個區(qū)域的邊界信息如圖8 所示，假設(shè)這些區(qū)域為S1,S2,…，對于區(qū)域S1的邊界提取具體做法為：

（1）首先找到S1中第一個邊界三角形D0，在區(qū)域S1中隨機取出一個三角形D，判斷該三角形的三條邊是否有向外延伸的其他三角形，如果D 的三條邊均有向外延伸的其他三角形，則表明D 不是邊界三角形，繼續(xù)判斷D 周圍的三角形；如果D 中某些邊沒有向外延伸的三角形，則表明該三角形是邊界三角形，記為D0，并將邊界邊的信息（包括邊和兩個頂點）存儲在指定數(shù)據(jù)結(jié)構(gòu)Edge和Vetex中。

（2）找到第一個邊界三角形D0后，就可以逐步判斷與D0有公共邊的那些三角形是否為邊界三角形，如果是則將相應(yīng)的邊界邊的信息存儲在Edge和Vetex中。

（3）按照上面步驟的方法，將區(qū)域S1中找到的邊界邊的信息都存儲在Edge 和Vetex 中。為了保證能夠?qū)ふ业剿械倪吔邕?，可以將Edge中的邊首尾順次存儲，如果所有邊構(gòu)成了一個環(huán)，說明找到了所有的邊界邊，其中Edge對應(yīng)的數(shù)據(jù)結(jié)構(gòu)如圖9所示。

圖7 區(qū)域內(nèi)網(wǎng)格劃分

圖8 每個區(qū)域邊界提取

圖9 邊界邊的存儲

根據(jù)上面的步驟最終找到了每個區(qū)域S1S2…的邊界邊和邊界點，接下來要做的就是實現(xiàn)區(qū)域間的無縫拼接，根據(jù)3.1節(jié)的方法將整個點云數(shù)據(jù)劃分成了360/n個區(qū)域，即有360/n 個Edge和Vetex數(shù)據(jù)結(jié)構(gòu)。在這些區(qū)域間進行無縫拼接，其實就是將所有Edge 中的邊和相鄰區(qū)域Vetex 中的點進行三角網(wǎng)格劃分的過程，但是要保證如下兩個條件成立：

（1）一個區(qū)域中的邊只能和其他區(qū)域的點形成邊。

（2）新形成的邊不能和所有Edge中的邊相交，也不能和新邊相交。

區(qū)域與區(qū)域之間進行拼接的具體做法為：

（1）先從第一個區(qū)域S1中的第一條邊界邊為出發(fā)點，向外尋找相鄰區(qū)域Vetex中的邊界點，然后邊和點構(gòu)成三角形，但要滿足如上兩個條件。比如以邊界邊AB為例，其中點A 坐標(biāo)為(x1,y1,z1)，點B 坐標(biāo)為(x2,y2,z2)，然后在其相鄰區(qū)域的Vetex 中尋找邊界點，可以采用如圖10 的方法，尋找距離邊AB 的中點O 最近的點P ，為了保證點P 的選取確實在邊AB 的相鄰位置，可以先判斷線段OP 的長度是否小于給定的閾值T0（閾值T0為點O 到相鄰區(qū)域中的最高點與最低點所在的直線的距離），然后判斷PA 與PB 會不會與其他邊相交，若PA 與PB 不與其他邊相交，則可構(gòu)成△PAB，繼續(xù)尋找下一條邊界邊對應(yīng)的邊界點，直到區(qū)域S1中的邊都遍歷到為止。

圖10 邊界間拼接

（2）再從區(qū)域S2中的邊界邊出發(fā)，首先檢查每條邊是否已經(jīng)與相鄰區(qū)域的邊界點構(gòu)成三角形，如果沒有，那么采用步驟（1）的方法尋找相鄰區(qū)域的邊界點構(gòu)成三角形。

（3）參照步驟（2）的方法，對其余區(qū)域的邊界邊向外尋找邊界點，直到360/n 個區(qū)域中的邊界邊都與其他區(qū)域的邊界點構(gòu)成三角形，停止。

這里要補充說明，三維空間中的邊與邊之間的關(guān)系有三種：平行、異面和相交。設(shè)有兩點A(x1,y1,z1)和B(x2,y2,z2) 組成的邊AB ，以及兩點C(x3,y3,z3) 和D(x4,y4,z4)組成的邊CD，則AB 和CD 所在直線可用兩點式表示，若AB 與CD所在向量對應(yīng)成比例，則表示AB 與CD 平行；若公式（13）成立，則表示AB 與CD 共面；若公式（13）不成立，則表示AB 與CD 異面。若AB與CD 共面且不平行，則還要繼續(xù)判斷線段AB 與線段CD 是否相交。

判斷線段AB 與線段CD 是否相交，首先可以使用x 坐標(biāo)或y 坐標(biāo)或z 坐標(biāo)的位置來判斷，具體為判斷一條線段較大的x 值是否小于另一條線段的較小的x值，如果是，則表明兩線段沒有交點；或者判斷一條線段的較大的y 值是否小于另一條線段的較小的y 值，如果是，則表明兩線段沒有交點；或者判斷一條線段的較大的z 值是否小于另一條線段的較小的z 值，如果是，則表明兩線段沒有交點。相應(yīng)的算法可由公式（14）實現(xiàn)，若公式（14）的值為1 則表明兩線段不可能有交點。若公式（14）的值為0，則需采用向量叉乘法繼續(xù)判斷是否相交，判斷方法為：如果公式（15）成立，則表明A 點和B 點在線段CD 的兩側(cè)；如果公式（16）成立，則表明C點和D 點在線段AB 的兩側(cè)；公式（15）（16）同時成立，則說明線段AB 與線段CD 相交（注：“×”為差乘，“·”為點乘）

3.3 優(yōu)化模型

通過以上步驟已經(jīng)建立了最初的三角網(wǎng)格模型，但是考慮到從物體表面提取的數(shù)據(jù)點有些是處在一個平面上的，而在同一平面上生成的三角網(wǎng)格是沒有任何意義的，為了精簡模型中三角形的數(shù)目，需要對模型進行優(yōu)化處理[11]。

計算所有三角形面片所在的法向量，針對每個三角形面片判斷是否與其相鄰的三角形面片共面，若共面則將這些共面三角形的公共邊去掉融為一個多邊形，從而達到優(yōu)化模型縮減網(wǎng)格數(shù)量的目的。

4 人機交互細分網(wǎng)格模型

以上建立的初始網(wǎng)格模型只是還原了物體概貌，模型表面還不是很光滑，重建出來的模型棱角較多失真現(xiàn)象嚴重。本章將通過人機交互的方式，對初始網(wǎng)格進行插值細分，以期達到物體表面光滑的效果[12-13]。由于物體表面可能存在三角形面片和多邊形面片兩種，對于這兩種不同形態(tài)的面片，分別使用不同的細分方法。

如果要細分的是三角形面片，這里采用Bezier曲面來尋找新的控制點，三次Bezier曲面可由10個控制點來確定，這10個控制點對應(yīng)在△ABC 上的大致位置如圖11 所示，分別為P003、P300、P030、P102、P201、P012、P021、P210、P120和P111。其中P003、P300和P030為△ABC 三個頂點的坐標(biāo)，只需要根據(jù)公式求出其余7個控制點的坐標(biāo)。這7個控制點的坐標(biāo)可由文獻[13-14]中的方法求出，重點得到控制點P111的坐標(biāo)，然后P111與△ABC 的三個頂點相連，這樣就實現(xiàn)了三角形的細分。

如果要細分的是多邊形面片如圖12 所示，可以借助此多邊形面片周圍的三角形面片來實現(xiàn)細分過程。首先找到與其存在公共邊的鄰域三角形，如圖13 所示的鄰域三角形有△1、△2、△3、△4 和△5。以△1 為例，△1 與多邊形存在公共邊，在△1 上進行Bezier 曲面插值的時候，此公共邊上會生成兩個新的控制點，如圖11 所示這兩個新的控制點可能是P012、P021，同理可以求出其他三角形△2、△3、△4 和△5 與多邊形的公共邊所對應(yīng)的新的控制點，將這些控制點取平均值，即為多邊形面片新的控制點P11，最后如圖13 所示將P11與多邊形的各個頂點連接，這樣就實現(xiàn)了多邊形面片的細分。

圖11 尋找新的控制點

圖12 不規(guī)則多邊形的細分

圖13 尋找新的控制點

對于本章的細分過程，可借助OpenGL中的函數(shù)來實現(xiàn)人機交互的效果[15-16]，具體可由鍵盤上的按鍵來控制細分的次數(shù)以及控制物體的旋轉(zhuǎn)、縮放和平移。本文實現(xiàn)了由鍵盤上的A 鍵控制細分的次數(shù)，F(xiàn)1、F2、F3 和F4 鍵控制物體的上、下、左、右旋轉(zhuǎn)，F(xiàn)5 和F6 鍵控制物體的縮放，↑、↓、←、→箭頭控制物體的上下左右平移。式（17）為OpenGL中處理普通按鍵比如字母、數(shù)字等消息的函數(shù)，式（18）為OpenGL中處理特殊按鍵比如箭頭、F1等消息的函數(shù)。

式（17）和（18）中的func 函數(shù)為當(dāng)按下相應(yīng)按鍵后，需要調(diào)用的函數(shù)，x 和y 為當(dāng)按下按鍵時鼠標(biāo)相對于窗口左上角的位置。

此外還可以對仿真出的模型進行光照和材質(zhì)等的設(shè)置，使模型更加逼近真實物體，具體的光照函數(shù)為式（19）所示，其中參數(shù)1表示要創(chuàng)建的光源號，參數(shù)2表示光源特性，參數(shù)3表示光源特性值。材質(zhì)設(shè)置函數(shù)為式（20）所示，其中參數(shù)1 表示將當(dāng)前材質(zhì)作用在哪個面上，參數(shù)2表示材質(zhì)特性，參數(shù)3表示材質(zhì)特性值。

5 實驗結(jié)果

為了驗證本文提出算法的正確性，這里采集了各種物體表面的離散數(shù)據(jù)點，圖14 的物體是每個面都為五邊形的球面（正十二面體），圖15的物體是一只兔子，圖16的物體是一只球鞋。

圖14 正十二面體仿真過程

圖15 兔子仿真過程

圖14 中的正十二面體，共采集了20 個數(shù)據(jù)點如圖14（a）所示，通過初始網(wǎng)格劃分以及優(yōu)化模型，共形成了12個正5邊形面片如圖14（b）所示，對圖14（b）進行光照和材質(zhì)等的設(shè)置如圖14（c）所示，要注意的是對于這里仿真的正十二面體，不需要進行網(wǎng)格的細分過程，否則會破壞正十二面體的表面結(jié)構(gòu)特征。

圖15 中的兔子，共采集了502 個數(shù)據(jù)點如圖15（a）所示，圖15（e）為對初始網(wǎng)格進行兩次細分后的結(jié)果（這里的細分采用鍵盤上的A鍵來進行，細分一次按一次A鍵，細分兩次按兩次A鍵），通過兩次細分物體表面近似光滑。圖15（f）和圖15（g）為使用鍵盤上的按鍵來控制兔子的方向，從而實現(xiàn)人機交互展現(xiàn)出兔子的正面結(jié)構(gòu)和背面結(jié)構(gòu)。

圖16 中的球鞋，共采集了1 841 個數(shù)據(jù)點如圖16（a）所示，圖16（b）為優(yōu)化后的初始網(wǎng)格模型，最終形成的初始網(wǎng)格中包括三角形面片和四邊形面片兩種，圖16（d）為圖16（c）的放大效果。圖16（e）為經(jīng)過一次細分后球鞋表面的光滑效果，圖16（f）為經(jīng)過第二次細分后球鞋表面的光滑效果。圖16（g）和圖16（h）為在鍵盤控制下球鞋的各個角度展示。

圖16 球鞋仿真過程

圖15 與圖16分別對兔子與球鞋模型進行了兩次細分，第一次細分后的仿真效果要比直接對初始網(wǎng)格的仿真效果較光滑，但是還存在一些不光滑的棱角區(qū)域，為此又進行了第二次細分，通過第二次細分后幾乎看不到之前的棱角部分，模型表面已經(jīng)很光滑幾乎接近真實物體表面。

以上三個物體在重建過程中每個階段的數(shù)據(jù)統(tǒng)計見表1所示，表中第三列區(qū)域個數(shù)(QY)指的是第3.1節(jié)中所述的劃分區(qū)域的問題，其中要注意的是對于兔子模型的重建，需要將兔子耳朵單獨分割出來進行。表2為對于球鞋模型使用本文所提算法和使用傳統(tǒng)的區(qū)域生長算法進行重建的相關(guān)參數(shù)比較，從表中可以看到對于同一批球鞋數(shù)據(jù)點，使用本文算法形成的初始網(wǎng)格個數(shù)要少于區(qū)域生長算法，原因在于本文算法在生成初始網(wǎng)格的過程中進行了模型的優(yōu)化處理。從時間上來看，本文算法比較占優(yōu)勢。表1 和表2 中num 表示從物體表面采集的數(shù)據(jù)點個數(shù)，QY 表示劃分的區(qū)域個數(shù)，m0表示初始網(wǎng)格個數(shù)，m1 表示第一次細分后網(wǎng)格個數(shù)，m2 表示第二次細分后網(wǎng)格個數(shù)，t 表示運行時間，d 表示細分次數(shù)。

表3 是判斷兔子表面某一點P 是否為噪聲點的部分數(shù)據(jù)展示，若P=（-0.170 739，0.219 018，0.013 140），以P 點為球心，r=0.06 為半徑做球，落在球內(nèi)部的點有27個，點P 到這27個點的距離見表3所示，由此可算出點P 到這27 個點的平均距離為0.041 6，再通過這27 個點利用公式（2）和（3）計算出相應(yīng)的取值區(qū)間為（0.038 9，0.123 0），因為0.041 6 ∈（0.038 9，0.123 0），所以點P 是正常點。

表1 物體仿真數(shù)據(jù)

表2 本文算法與區(qū)域生長算法比較（球鞋）

表3 r=0.06 時球內(nèi)部的27個點到點P 的距離

6 結(jié)語

本文實現(xiàn)了人機交互式的物體仿真建模過程，建模過程中使用了地理坐標(biāo)下的高斯投影算法，在細分時使用了Bezier 曲面的插入控制點的方法，最后使用OpenGL中的鍵盤控制函數(shù)、光照函數(shù)、材質(zhì)函數(shù)等完成了重建過程。本文所提算法可以很好地應(yīng)用于古建筑物的修復(fù)或者3D打印等領(lǐng)域中。

相比其他算法，本文算法可以對大部分表面較為光滑的物體進行重建，但是本文算法也有很多不足之處，比如在進行初始三角網(wǎng)的構(gòu)建時，使用高斯投影的思想是將三維數(shù)據(jù)點投影到二維平面上再進行三角網(wǎng)的劃分，這種方法對于原始物體表面存在孔洞或是多處存在大幅度的凹陷的情況不是很適用，為此物體重建算法還是今后研究的重點方向之一。