基于三維散亂點云的三角網(wǎng)格重構(gòu)關(guān)鍵技術(shù)

文/曹金俐

基于三維散亂點云的三角網(wǎng)格重構(gòu)關(guān)鍵技術(shù)

文/曹金俐

本文分析了多約束下三維網(wǎng)格的重構(gòu)方法，同時提出三維散亂點云三角網(wǎng)格構(gòu)造，以期給相關(guān)研究提供參考。

三維散亂點云 三角網(wǎng)格 重構(gòu)技術(shù)

1 前言

伴隨計算機的技術(shù)飛速發(fā)展，CAD/CAM的技術(shù)逐漸變成相關(guān)設(shè)計人員的研究工具，尤其三維造型的技術(shù)廣泛應(yīng)用于制造業(yè)中自動化的加工制造、產(chǎn)品設(shè)計與模具設(shè)計方面。通常傳統(tǒng)CAD/CAM的工作流程為：按照工程設(shè)計師圖紙或是構(gòu)思，通過CAD/CAM的軟件來設(shè)計產(chǎn)品三維的模型，再實施必要模型的修改，然后生成相應(yīng)模型數(shù)控的代碼，進而完成最終的產(chǎn)品加工。

2 多約束下三維網(wǎng)格的重構(gòu)方法

2.1 三角網(wǎng)格的三維重構(gòu)算法探究現(xiàn)狀

各種形式網(wǎng)格重構(gòu)可以適應(yīng)不同類型點云的數(shù)據(jù)，而本文研究的對象散亂點云數(shù)據(jù)。散亂點云網(wǎng)格重構(gòu)研究包含2個方向：其一，投影方式；其二，在三維的空間中實施構(gòu)造。因為在二維空間中點云的三角化算法相對成熟與穩(wěn)定，其應(yīng)用時間較長，所以經(jīng)常會在二維域內(nèi)投影三維數(shù)據(jù)，并在新平面上實施投影點三角化以后，將三角化以后所獲得三角網(wǎng)格可以反投至3D空間中。因為相較于2D平面而言，空間中領(lǐng)域點和數(shù)據(jù)點間關(guān)系可以如實的反映，以便在3D的空間中反射出平面的三角網(wǎng)格，并且不會出現(xiàn)畸變的三角形，也不會發(fā)生重疊的情況。

2.2 Delaunay的三角剖分計算方法

關(guān)于Delaunay的三角剖分計算方法主要是在Voronoi基礎(chǔ)上所獲得，主要方法為對點集中，探索各個方向K的領(lǐng)域，尋找相應(yīng)的臨近點，同時通過Voronoi的原理圖來實現(xiàn)三角化。假如三維空間之中存在某個點集X等于{X1，X2???XN}，對點集D之中相鄰的X1與X2進行連接，然后求解各連線中垂線，然后得出多邊形的網(wǎng)格圖。

2.3 區(qū)域的擴張法

常見經(jīng)點云數(shù)據(jù)在三維空間之中三角化的方法為區(qū)域的擴張法，這種方法途徑就是經(jīng)初始的邊或是三角形開始，根據(jù)設(shè)定檢測的過濾規(guī)則，選擇匹配點以構(gòu)成三角片，繼而實現(xiàn)網(wǎng)格模型構(gòu)建。而區(qū)域擴張方法過程如下：其一，對某個已知散亂的點云集R，構(gòu)建種子的三角形 i0，把其置于三角形的集合Ui等于{i0}中，在集合隊列中，僅有一個初始三角形的元素 i0；其二，對于集合的隊列Ui等于{i0，i1，…，in}之中已經(jīng)構(gòu)建含邊界邊每個三角片/ik，然后在集合的隊列Ui等于{i0，i1，…in}尋找和次邊界邊邊相互對應(yīng)最優(yōu)的活躍點O，然后生成新三角片in，同時加入到Ui等于{i0，i1，…in}的隊列之中；其三，對R中點狀態(tài)與Ui之中相鄰關(guān)系進行更新，再不斷地迭代，一直到結(jié)束三角化的過程。

3 三維散亂點云三角網(wǎng)格構(gòu)造

同城區(qū)域增長的方法就是把三個鄰近的點構(gòu)建種子三角形當(dāng)作網(wǎng)格的重建基礎(chǔ)，根據(jù)最優(yōu)匹配點選取原則進行不斷地的擴展，構(gòu)成新三角形，一直到結(jié)束網(wǎng)格重構(gòu)。

3.1 構(gòu)建初始的三角形

選擇點云的鏈表之中首個點作初始的頂點，應(yīng)用柵格方法來尋找與初始點相距較近的點當(dāng)做第2個頂點。連接兩個點構(gòu)成三角形第一條邊，在第二頂點與第一頂點鄰域中選擇與第一條邊兩個端點相距比較近的點當(dāng)做第三個頂點。

3.2 活躍邊檢測

在進行檢測邊擴張性的時候，第一步需要對邊隊列之中e有沒有內(nèi)邊進行判斷，對e是不是內(nèi)邊進行檢測時，采取的一種簡單方式就是檢測邊e兩個端點，把ej內(nèi)鄰接列表，若ei（ej）內(nèi)鄰接點的鏈表之中存在ej（ei），證明e是內(nèi)邊，從活躍邊的隊列中除去，若e不為內(nèi)邊，需要相應(yīng)屬性與條件use小于2相符合，然后匹配生成新三角形。

3.3 最優(yōu)的匹配點選擇

在重建三角網(wǎng)格的模型時，最佳的匹配點能夠合理的選擇，會導(dǎo)致網(wǎng)格模型生成質(zhì)量受到直接影響。因此，為提升運算的效率與避免全局的搜索，需要按照以下原則進行選擇。

3.3.1 二面角的準(zhǔn)則

為保證所生成網(wǎng)格的光滑性，當(dāng)前邊和備選點構(gòu)成三角形，需要和三角形平面構(gòu)成二面角，并且需要處在合適的閾值內(nèi)，將與上述條件相符點添到最佳的候選點列表之中。

3.3.2 K-鄰近的搜索準(zhǔn)則

在選擇最佳的匹配點時，需要確保改點和前邊生成新三角形可以將形體拓撲信息充分反映出來。為縮小最佳的匹配點搜索的范圍，余搜索邊e最佳的匹配點能夠搜索邊e鄰近的區(qū)域，應(yīng)用柵格方法來查出兩個端點，確保點可領(lǐng)域可以有較好的連續(xù)性。

3.3.3 已用點的優(yōu)先準(zhǔn)則

在進行網(wǎng)格擴張生成時，若生成新邊過多，容易導(dǎo)致擴張效率受到影響。因此，在對e最佳的匹配點進行確定時，需要優(yōu)先考慮網(wǎng)格模型之中已用點。在對某個點是否是已用點進行判斷時，可以應(yīng)用點與附近點空間幾何的相對位置進行排查，搜索該店鄰接點的列表，若列表是空，表示為外點，不然表示改點是已用點。如果邊e鄰近的區(qū)域中已用點中缺乏滿足最佳的匹配點選擇要求，需要從未使用點鐘選取與條件相符的點實施網(wǎng)格擴張，具體從圖1中可以看出。

圖1：已用點優(yōu)先的使用圖

4 結(jié)語

總之，伴隨計算機飛速發(fā)展，各種逆向工程的技術(shù)漸漸變成人們的研究重點，現(xiàn)階段，雖然精確、快速獲取物體表面點云模型比較容易。然而，在物體表面的信息數(shù)據(jù)之中，冗余點含量比較大，因此，需要借助三維散亂的點云三角網(wǎng)格的重構(gòu)技術(shù)，以便建立數(shù)據(jù)點拓撲關(guān)系，進而明確各個點的作用。

[1]段黎明,王浩宇,劉瑩.基于工業(yè)CT圖像重構(gòu)的網(wǎng)格模型的全局優(yōu)化方法[J].強激光與粒子束,2015,27(12):173-177.

[2]邸維巍,張旭東,胡良梅.基于可信度的TOF相機三維點云球覆蓋網(wǎng)格重建[J].合肥工業(yè)大學(xué)學(xué)報（自然科學(xué)版）,2014,23(12):1451-1455.

[3]秦緒佳,陳樓衡,譚小俊.結(jié)構(gòu)光視覺三維點云逐層三角網(wǎng)格化算法[J].計算機科學(xué),2016,43(z2):383-387,410.

作者單位武漢地震科學(xué)儀器研究院有限公司 湖北省武漢市 437100