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

杜麗美，連 瑋

長治學院 計算機系，山西 長治046000

1 引言

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

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

2 點云數據處理

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

圖1 點云數據的存儲

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

圖2 去噪過程

3 初始網格模型的構造

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

3.1 分區域生成三角網格

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

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

圖3 作圓球包含所有數據點

圖4 球心與數據點連線

圖5 計算P′的經度α 和緯度β

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

對每一區域內投影到平面上的二維數據點進行三角網格的劃分如圖6所示，重點得到二維平面上點與點的連接關系，將這種連接關系反映射[8-10]回原三維數據點上，即完成了每一區域內三維數據點的網格劃分。

圖6 高斯投影演示

3.2 區域間拼接

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

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

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

（3）按照上面步驟的方法，將區域S1中找到的邊界邊的信息都存儲在Edge 和Vetex 中。為了保證能夠尋找到所有的邊界邊，可以將Edge中的邊首尾順次存儲，如果所有邊構成了一個環，說明找到了所有的邊界邊，其中Edge對應的數據結構如圖9所示。

圖7 區域內網格劃分

圖8 每個區域邊界提取

圖9 邊界邊的存儲

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

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

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

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

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

圖10 邊界間拼接

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

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

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

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

3.3 優化模型

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

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

4 人機交互細分網格模型

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

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

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

圖11 尋找新的控制點

圖12 不規則多邊形的細分

圖13 尋找新的控制點

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

式（17）和（18）中的func 函數為當按下相應按鍵后，需要調用的函數，x 和y 為當按下按鍵時鼠標相對于窗口左上角的位置。

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

5 實驗結果

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

圖14 正十二面體仿真過程

圖15 兔子仿真過程

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

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

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

圖16 球鞋仿真過程

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

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

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

表1 物體仿真數據

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

表3 r=0.06 時球內部的27個點到點P 的距離

6 結語

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

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