文/曹金俐

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

文/曹金俐

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

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

1 前言

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

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

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

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

2.2 Delaunay的三角剖分計(jì)算方法

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

2.3 區(qū)域的擴(kuò)張法

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

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

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

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

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

3.2 活躍邊檢測(cè)

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

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

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

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

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

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

在選擇最佳的匹配點(diǎn)時(shí)，需要確保改點(diǎn)和前邊生成新三角形可以將形體拓?fù)湫畔⒊浞址从吵鰜?。為縮小最佳的匹配點(diǎn)搜索的范圍，余搜索邊e最佳的匹配點(diǎn)能夠搜索邊e鄰近的區(qū)域，應(yīng)用柵格方法來查出兩個(gè)端點(diǎn)，確保點(diǎn)可領(lǐng)域可以有較好的連續(xù)性。

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

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

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

4 結(jié)語

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

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

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

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

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