[發(fā)明專利]基于映射法的散亂點(diǎn)云Delaunay三角剖分曲面重構(gòu)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410203455.3
• 申請(qǐng)日: 2014-05-14
• 公開（公告）號(hào): CN103985155B
• 公開（公告）日: 2017-01-25
• 發(fā)明（設(shè)計(jì)）人: 李鳳霞;霍達(dá);雷正朝;孫美玲;張鉑;趙三元
• 申請(qǐng)（專利權(quán)）人: 北京理工大學(xué)
• 主分類號(hào): G06T17/00
• 分類號(hào): G06T17/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于映射法的散亂點(diǎn)云Delaunay三角剖分曲面重構(gòu)方法，其特征在于：其具體步驟如下：

步驟一、獲取目標(biāo)的原始點(diǎn)云數(shù)據(jù)；

設(shè)定點(diǎn)云數(shù)據(jù)坐標(biāo)系：建立空間直角坐標(biāo)系，以平向右方向?yàn)閄軸正方向，豎直向上方向?yàn)閆軸正方向，垂直于X軸和Z軸所確定的平面的軸為Y軸；它們的正方向符合右手規(guī)則；

所述原始點(diǎn)云數(shù)據(jù)包含三維坐標(biāo)信息，還可能包含每個(gè)點(diǎn)的法向量信息；

步驟二、獲取原始點(diǎn)云數(shù)據(jù)中每個(gè)點(diǎn)的K階鄰域和單位法向量；

在步驟一操作的基礎(chǔ)上，獲取原始點(diǎn)云數(shù)據(jù)中每個(gè)點(diǎn)的K階鄰域和單位法向量，具體操作步驟為：

步驟2.1：獲取原始點(diǎn)云數(shù)據(jù)中每個(gè)點(diǎn)的K階鄰域；

步驟2.2：在步驟2.1操作的基礎(chǔ)上，獲取八叉樹點(diǎn)云數(shù)據(jù)中每個(gè)點(diǎn)的單位法向量，具體操作分為2種情況：

情況1：如果八叉樹點(diǎn)云數(shù)據(jù)中每個(gè)點(diǎn)包含法向量信息，對(duì)每個(gè)點(diǎn)的法向量進(jìn)行單位化得到其單位法向量；

情況2：如果八叉樹點(diǎn)云數(shù)據(jù)中每個(gè)點(diǎn)不包含法向量信息，則采用主元分析法計(jì)算點(diǎn)云數(shù)據(jù)的單位法向量；其步驟如下：

步驟2.2.1：對(duì)于點(diǎn)云中任意一點(diǎn)P，通過公式(1)使用最小二乘法為點(diǎn)P和點(diǎn)P的K階鄰域計(jì)算出一個(gè)局部平面S；

S(n,d)=argmin(n,d)Σi=1k(n·Pi-d)2---(1)]]>

其中，n為平面S的單位法向量；d為點(diǎn)P到坐標(biāo)原點(diǎn)的距離，P_i為點(diǎn)P的k個(gè)鄰近點(diǎn)，k為正整數(shù)，4≤k≤100；

步驟2.2.2：找到點(diǎn)P以及點(diǎn)P的k個(gè)鄰近點(diǎn)的質(zhì)心P＇，并通過公式(2)獲得半正定協(xié)方差矩陣M；然后對(duì)半正定協(xié)方差矩陣M進(jìn)行特征值分解，將半正定協(xié)方差矩陣M的最小特征值對(duì)應(yīng)的特征向量作為點(diǎn)P的法向量；

M=Σi=1k(Pi-P′)(Pi-P′)T/k---(2)]]>

步驟2.2.3：對(duì)步驟2.2.2得到的點(diǎn)P的法向量進(jìn)行單位化得到點(diǎn)P的單位法向量；

步驟2.2.4：由于步驟2.2.3計(jì)算出的單位法向量方向與真實(shí)的單位法向量可能相反，因此需要判斷單位法向量方向是否需要進(jìn)行調(diào)整，如果單位法向量方向與真實(shí)的單位法向量相反則進(jìn)行調(diào)整；

判斷單位法向量方向是否需要進(jìn)行調(diào)整以及調(diào)整方法為：

在八叉樹點(diǎn)云數(shù)據(jù)的所有點(diǎn)中，找到其Z坐標(biāo)值最大的點(diǎn)A，然后選取點(diǎn)A的鄰域中任意一點(diǎn)N，計(jì)算向量NA與點(diǎn)A的單位法向量na之間的夾角β(NA,na)，如果β(NA,na)>π/2，則將點(diǎn)A的單位法向量變換方向；以點(diǎn)A為基準(zhǔn)點(diǎn)調(diào)整其k個(gè)鄰域點(diǎn)的單位法向量n₁方向，計(jì)算單位法向量na與單位法向量n₁之間的夾角β(na,n₁)，如果β(na,n₁)>π/2，則改變?cè)撪徲螯c(diǎn)的單位法向量方向；此后再依次以點(diǎn)A的鄰域點(diǎn)為基準(zhǔn)點(diǎn)，調(diào)整點(diǎn)A的鄰域點(diǎn)的鄰域點(diǎn)的單位法向量，重復(fù)此過程，直到所有單位法向量都調(diào)整完畢；

步驟三、將點(diǎn)云數(shù)據(jù)進(jìn)行分片；

在步驟二計(jì)算點(diǎn)云數(shù)據(jù)單位法向量的基礎(chǔ)上，對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行分片；具體操作步驟如下：

步驟3.1：搜索種子點(diǎn)；

所述搜索種子點(diǎn)的方法為：在步驟二得到的點(diǎn)云數(shù)據(jù)中，從未分片的點(diǎn)中隨機(jī)選取一個(gè)點(diǎn)O＇，將點(diǎn)O＇的k個(gè)鄰域點(diǎn)的單位法向量投影到點(diǎn)O＇與點(diǎn)O＇的單位法向量確定的平面上，形成k條射線，對(duì)每一條射線L，以射線L的起點(diǎn)為起點(diǎn)，經(jīng)過點(diǎn)O＇的形成一個(gè)新的射線，如果該射線與射線L的夾角全部大于π或者全部都小于π，則點(diǎn)O＇為種子點(diǎn)，否則，點(diǎn)O＇不是種子點(diǎn)；如果點(diǎn)O＇不是種子點(diǎn)，重復(fù)該步驟，直到找到一個(gè)種子點(diǎn)O；

步驟3.2：將步驟3.1得到的種子點(diǎn)O加入到待拓展隊(duì)列Queue中，將該種子點(diǎn)為點(diǎn)云分片s的第一個(gè)點(diǎn)，同時(shí)將種子點(diǎn)標(biāo)記為已分片；

步驟3.3：若待拓展隊(duì)列Queue不為空，從隊(duì)列中取出一個(gè)點(diǎn)Q，遍歷點(diǎn)Q的k個(gè)鄰域點(diǎn)，判斷點(diǎn)Q的當(dāng)前鄰域點(diǎn)的法向量與種子點(diǎn)O的法向量夾角α是否低于一個(gè)閾值θ，其中，θ為人為設(shè)定值，如果α≤θ成立，則將該鄰域點(diǎn)加入待拓展隊(duì)列Queue和當(dāng)前的點(diǎn)云分片s中，同時(shí)標(biāo)記該鄰域點(diǎn)為已分片；重復(fù)此過程，直到待拓展隊(duì)列Queue為空時(shí)，點(diǎn)云的一個(gè)分片的分割完成；

步驟3.4：重復(fù)執(zhí)行步驟3.1至步驟3.3，直到所有的種子點(diǎn)都標(biāo)記為已分片；

步驟3.5：經(jīng)過步驟3.1至步驟3.4的操作，如果存在少數(shù)點(diǎn)沒有被劃分到任意一個(gè)分片當(dāng)中，或者分片中的點(diǎn)的數(shù)量少于閾值σ，其中，σ為人為設(shè)定值，5≤σ≤100；對(duì)于這樣的點(diǎn)，將其劃分到含有最多該點(diǎn)的領(lǐng)域點(diǎn)的分片中；

步驟3.6：對(duì)每一個(gè)分片的邊緣進(jìn)行拓展；其具體操作方法為：遍歷分片中全部點(diǎn)，查看每個(gè)點(diǎn)的鄰域點(diǎn)的所屬分片，若鄰域點(diǎn)的分片和該點(diǎn)的分片不同，則將該點(diǎn)加入到鄰域點(diǎn)所屬的分片中；

經(jīng)過步驟三的操作，即可完成全部點(diǎn)云數(shù)據(jù)的分片；

步驟四、參數(shù)化已分片的點(diǎn)云到二維平面；

在步驟三對(duì)點(diǎn)云數(shù)據(jù)分片的基礎(chǔ)上，進(jìn)行分片點(diǎn)云的無網(wǎng)格參數(shù)化，將空間的三維點(diǎn)云影射到二維平面空間；其具體操作步驟如下：

步驟4.1：從步驟三得到的分片中，取一個(gè)未參數(shù)化的分片，將該分片中的種子點(diǎn)O加入待參數(shù)化隊(duì)列Queue2；

步驟4.2：若待參數(shù)化隊(duì)列Queue2不為空，從待參數(shù)化隊(duì)列Queue2中取出一個(gè)點(diǎn)B，將點(diǎn)B標(biāo)記為已調(diào)整，將點(diǎn)B直接投影射到以點(diǎn)O和點(diǎn)O的法向量確定的平面上，得到投影點(diǎn)B′；對(duì)于點(diǎn)B的k個(gè)鄰域點(diǎn)中的每一點(diǎn)D，將點(diǎn)D直接投影射到以點(diǎn)O和點(diǎn)O的法向量確定的平面上，得到投影點(diǎn)D′；沿著B′D′的方向?qū)′D′延伸，得到一條長度為|BD|的線段，該線段記為B′D″，點(diǎn)B′和點(diǎn)D″為線段B′D″的兩個(gè)端點(diǎn)；點(diǎn)D″為點(diǎn)D經(jīng)過一次調(diào)整后得到的映射點(diǎn)；將點(diǎn)D″加入到點(diǎn)D的調(diào)整點(diǎn)集合coSet中；如果點(diǎn)D為未調(diào)整，則將點(diǎn)D加入待參數(shù)化隊(duì)列Queue2中；

步驟4.3：重復(fù)步驟4.2直到待參數(shù)化隊(duì)列Queue2為空；

步驟4.4：依次遍歷步驟4.1中所述分片中的點(diǎn)，對(duì)每一點(diǎn)計(jì)算其調(diào)整點(diǎn)集合coSet中所有點(diǎn)的坐標(biāo)平均值，將此均值坐標(biāo)作為參數(shù)化結(jié)果；

經(jīng)過步驟4.1至步驟4.4的操作，完成了一個(gè)分片的無網(wǎng)格參數(shù)化；

步驟4.5：重復(fù)執(zhí)行步驟4.1至步驟4.4，直到所有的分片都完成無網(wǎng)格參數(shù)化；

步驟五、在二維平面內(nèi)對(duì)點(diǎn)云進(jìn)行Delaunay三角剖分并映射回對(duì)應(yīng)的三維空間；

在步驟四操作的基礎(chǔ)上，對(duì)全部無網(wǎng)格參數(shù)化結(jié)果的點(diǎn)云分片進(jìn)行德勞內(nèi)三角網(wǎng)的構(gòu)建；具體操作步驟為：

步驟5.1：采用德勞內(nèi)三角網(wǎng)格的方法重構(gòu)無網(wǎng)格參數(shù)化結(jié)果的點(diǎn)云分片，德勞內(nèi)三角網(wǎng)所具有的空?qǐng)A特性和最大最小角特性，保證了德勞內(nèi)三角網(wǎng)中不會(huì)出現(xiàn)過于狹長的三角形，使得三角網(wǎng)的構(gòu)建更合理與準(zhǔn)確，從而具有極大的應(yīng)用價(jià)值；

步驟5.2：經(jīng)過步驟5.1對(duì)所有的點(diǎn)云分片進(jìn)行德勞內(nèi)三角網(wǎng)構(gòu)建完成后，將全部分片的構(gòu)網(wǎng)結(jié)果返回到三維空間，得到原始點(diǎn)云數(shù)據(jù)的初始三角網(wǎng)格模型；

步驟六、優(yōu)化初始三角網(wǎng)格模型；

在步驟五初始三角網(wǎng)格模型的基礎(chǔ)上，進(jìn)行網(wǎng)格重疊和空洞的優(yōu)化；具體操作步驟如下：

步驟6.1：統(tǒng)計(jì)步驟五得到的初始三角網(wǎng)格模型中，每條邊使用的次數(shù)count；若某一條邊使用次數(shù)count＝3，則表示共同使用該邊EF的有3個(gè)三角形，其中點(diǎn)E和點(diǎn)F為邊EF的兩個(gè)端點(diǎn)；計(jì)算使用此邊的三角形所在平面之間的夾角，選擇其中夾角最小的兩個(gè)三角形，將這兩個(gè)三角形分別稱為第一三角形和第二三角形，將另外一個(gè)三角形稱為第三三角形；第一三角形、第二三角形和第三三角形的另外一個(gè)頂點(diǎn)分別用符號(hào)G、H和I表示；選取邊EF的中點(diǎn)J，如果∠GJI>∠HJI，則刪除第二三角形；否則，刪除第一三角形；重復(fù)該步驟，直到每條邊的使用次數(shù)count均不大于2；

步驟6.2：統(tǒng)計(jì)步驟6.1得到的三角網(wǎng)格模型中，每條邊使用的次數(shù)count；若某一條邊使用次數(shù)count＝1，將此邊稱為邊界邊RT，其中點(diǎn)R和點(diǎn)T為邊RT的兩個(gè)端點(diǎn)；將使用邊界邊RT的三角形的另外一個(gè)頂點(diǎn)用符號(hào)V表示；將點(diǎn)R和點(diǎn)T稱為孔洞點(diǎn)；搜索點(diǎn)R和點(diǎn)T的鄰域點(diǎn)中的孔洞點(diǎn)，并組成點(diǎn)集SET；選取邊RT的中點(diǎn)U；如果點(diǎn)集SET不為空，則遍歷點(diǎn)集SET中的點(diǎn)W，選取∠VUW中的最大值對(duì)應(yīng)的點(diǎn)W_max；將點(diǎn)W_max、R和T組成一個(gè)新的三角形加入到三角網(wǎng)絡(luò)模型中，同時(shí)更新ΔW_maxRT的三條邊的使用次數(shù)count；如果點(diǎn)集SET為空，將邊界邊RT的使用次數(shù)count值更新為2；重復(fù)該步驟，直到每條邊的使用次數(shù)count均等于2；

經(jīng)過上述步驟的操作，得到原始點(diǎn)云數(shù)據(jù)的最終三角網(wǎng)格模型。

2.如權(quán)利要求1所述的一種基于映射法的散亂點(diǎn)云Delaunay三角剖分曲面重構(gòu)方法，其特征在于：步驟二中所述獲取原始點(diǎn)云數(shù)據(jù)中每個(gè)點(diǎn)的K階鄰域的具體操作步驟為：

步驟2.1.1：采用八叉樹結(jié)構(gòu)處理步驟一得到的點(diǎn)云數(shù)據(jù)，得到八叉樹點(diǎn)云數(shù)據(jù)；

步驟2.1.2：對(duì)于步驟2.1.1得到的八叉樹點(diǎn)云數(shù)據(jù)中的每一點(diǎn)P，通過搜索點(diǎn)P所在的葉子節(jié)點(diǎn)和與該節(jié)點(diǎn)相鄰的葉子節(jié)點(diǎn)中最近的k個(gè)點(diǎn)得到點(diǎn)P的K階鄰域；其中，k為正整數(shù)，4≤k≤100。