基于耳切法的三維模型區(qū)域標(biāo)繪

韓曉明，馮孟奇，褚飛黃，白瑞婷

（國能數(shù)智科技開發(fā)（北京）有限公司，北京 100011）

三維綜合集成展示系統(tǒng)項目在當(dāng)前的安全監(jiān)控領(lǐng)域中具有重要的應(yīng)用價值。為了實現(xiàn)對設(shè)備的有效管理和監(jiān)控，準(zhǔn)確而高效的區(qū)域標(biāo)繪與設(shè)備框選技術(shù)成為項目中的關(guān)鍵環(huán)節(jié)。然而，現(xiàn)有的安防標(biāo)繪方法和設(shè)備框選技術(shù)在處理復(fù)雜場景、準(zhǔn)確性和效率等方面仍然存在一定的挑戰(zhàn)。耳切法作為一種經(jīng)典的計算幾何算法[1]，通過用戶標(biāo)記的方式，可以構(gòu)建出精確的區(qū)域模型來框住設(shè)備，同時具有較高的計算效率。本文將探索如何將耳切法應(yīng)用于智能安防項目中，并評估其在實際應(yīng)用中的性能和效果。本文的主要目的是設(shè)計和實現(xiàn)一個基于耳切法[2]的三維綜合集成展示系統(tǒng)三維區(qū)域標(biāo)繪與設(shè)備框選系統(tǒng)。本文將詳細(xì)介紹耳切法的原理和算法，并提出相應(yīng)的改進(jìn)和優(yōu)化方法以適應(yīng)實際應(yīng)用場景。通過大量的實驗和評估，驗證該系統(tǒng)在準(zhǔn)確性、效率和用戶體驗等方面的優(yōu)勢，并與其他相關(guān)方法進(jìn)行比較分析，期望能為三維綜合集成展示系統(tǒng)三維區(qū)域標(biāo)繪與設(shè)備框選提供一種高效準(zhǔn)確的解決方案，促進(jìn)三維綜合集成展示系統(tǒng)領(lǐng)域的進(jìn)一步發(fā)展。

1 三維區(qū)域標(biāo)繪的意義

在三維數(shù)字仿真系統(tǒng)中，區(qū)域標(biāo)繪和設(shè)備框選是其中最為重要的一部分。通過三維區(qū)域標(biāo)繪，可以以直觀的方式清晰地呈現(xiàn)復(fù)雜的工廠三維實景，提供直觀的信息剖析。通過精確的標(biāo)繪和設(shè)備框選，可以準(zhǔn)確地定位設(shè)備的位置并提供精確的區(qū)域信息，有助于系統(tǒng)的快速定位和監(jiān)控設(shè)備。此外，通過建立三維區(qū)域模型，還可以進(jìn)行區(qū)域設(shè)備之間的空間關(guān)聯(lián)性分析，有效幫助優(yōu)化布控和安防策略。

2 技術(shù)研究思路

在現(xiàn)有的三維系統(tǒng)中，區(qū)域標(biāo)繪和設(shè)備框選主要使用手動標(biāo)繪、基于深度學(xué)習(xí)的目標(biāo)檢測和基于點云處理的算法。

手動標(biāo)繪是通過人工方式在三維場景中繪制區(qū)域標(biāo)記和設(shè)備框選。雖然具備靈活性，但占用一定的人力和時間。

基于深度學(xué)習(xí)的目標(biāo)檢測是利用深度學(xué)習(xí)技術(shù)，如卷積神經(jīng)網(wǎng)絡(luò)（CNN）和目標(biāo)檢測算法，自動檢測和框選設(shè)備。這種方法可以實現(xiàn)自動化和高效性，但對于復(fù)雜場景和低質(zhì)量數(shù)據(jù)存在一定挑戰(zhàn)。

基于點云處理的算法利用點云數(shù)據(jù)處理和分析技術(shù)，如點云分割、點云配準(zhǔn)等進(jìn)行區(qū)域標(biāo)繪和設(shè)備框選。這種方法適用于三維點云數(shù)據(jù)，可以提取特定形狀和特征進(jìn)行標(biāo)繪和框選。

結(jié)合三維綜合集成展示系統(tǒng)的實際應(yīng)用情況和對標(biāo)繪算法的研究與比較，本文選擇了耳切法作為標(biāo)繪的技術(shù)方案。

3 區(qū)域標(biāo)繪

在三維仿真系統(tǒng)中，區(qū)域標(biāo)繪的操作方式一般是用戶通過在場景中標(biāo)繪點，然后系統(tǒng)根據(jù)這些點迅速構(gòu)建出一個多邊形或者多邊體。通常情況下，用戶標(biāo)繪的點數(shù)通常是四個，以構(gòu)建一個規(guī)整的矩形，系統(tǒng)在標(biāo)繪結(jié)束后才會進(jìn)行繪制。在我們的拓展中，用戶可以任意標(biāo)繪，且當(dāng)用戶標(biāo)繪的點數(shù)達(dá)到可以構(gòu)建一個三角面時，系統(tǒng)就開始進(jìn)行繪制，并支持增刪改的操作。各種多邊形，在三維中都是通過用戶輸入的點構(gòu)建非鏤空的面。構(gòu)建簡單多邊形的主要因素是通過點構(gòu)建三角面，再通過組合三角面形成簡單多邊形。因此，最關(guān)鍵的是構(gòu)建三角面，而構(gòu)建三角面最重要的是對三角面頂點的排序。要實現(xiàn)通過標(biāo)繪的點實時有序地構(gòu)建一個非鏤空的多邊形是一項非常復(fù)雜的任務(wù)。耳切法恰好是解決三維圖形頂點排序的一種算法。[3]

4 耳切法

4.1 簡介

在本算法中有一個問題，就是將簡單多邊形進(jìn)行轉(zhuǎn)化，變?yōu)橐唤M的三角形集合，三角形的所有頂點與原頂點相同。

簡單多邊形的簡介如下：由一組有序點構(gòu)成頂點，頂點設(shè)為P0 至Pn-1。兩兩頂點間均由邊（Pi，Pi-1）依次相連，并且最后一條邊（Pn-1，P0）將連接第一個點，每個頂點有且僅有連接兩條邊，邊與邊的交點均為頂點，如此組成的一個形狀為簡單多邊形。如圖1，圖中的三個圖形解釋了這個概念。可以看出，只有第一個是簡單多邊形，其他部分只是多邊形。我們需要將一個完整的多邊形拆分為多個小的三角形，由n 個頂點組成的簡單多邊形能夠根據(jù)幾何學(xué)原理劃分為n 減2個三角形[4-6]。耳切法（Ear Clipping）就是用來實現(xiàn)這個目標(biāo)的算法，其復(fù)雜度為O(n^2)。

圖1 簡單多邊形實例

4.2 Ear Clipping

簡單多邊形的“耳朵”是一個特定的三角形。該三角形由多邊形中相鄰的三個頂點Pn、Pn+1 和Pn+2組成的，并且在該三角形內(nèi)部不包含其他頂點。Pn 和Pn+2 之間的連線被稱為多邊形的對角線，其中點Pn+1則被稱為耳尖。根據(jù)這個特性，我們可以將大的簡單多邊形拆分為n-2 個小三角形，然后通過查找耳尖并將其所代表的三角形移除來實現(xiàn)拆分過程。

在耳切法的具體實現(xiàn)中，第一步是存儲多邊形的數(shù)據(jù)，在此采用的是雙向鏈表[7]結(jié)構(gòu)，雙向鏈表的結(jié)構(gòu)可以減少移除耳朵的時間復(fù)雜度，構(gòu)建鏈表的所占的復(fù)雜度為O(n)。第二步是對所有頂點進(jìn)行遍歷以查找出所有耳朵，需對每個頂點Pi 所在的圍繞該頂點的三角形進(jìn)行檢測，判斷是否有頂點在三角形內(nèi)部。如果沒有，則Pi 是一個耳朵，否則不是。在實際計算中，需要構(gòu)建四個鏈表，其中兩個是線性鏈表，兩個是循環(huán)鏈表。其中線性鏈表用于存儲凹頂點和凸頂點。通過計算兩邊的夾角來確定頂點的類型，夾角大于180 度則為凹頂點，小于180 度則為凸頂點。另外兩個循環(huán)鏈表一個用于存儲所有頂點的數(shù)據(jù)，另一個用于存儲所有耳尖頂點。

首先計算凹凸頂點，將耳尖與凸頂點相同，然后移除耳尖。如果通過耳尖構(gòu)建的三角形中存在其他頂點，則將該頂點從耳尖列表中移除。然后對耳尖進(jìn)行遍歷，每次遍歷都移除一個耳尖。由于移除一個耳尖后，其相鄰的點會發(fā)生變化，因此需要判斷相鄰的點是否發(fā)生改變，如果發(fā)生改變，則需要更新相關(guān)列表。

通過圖1 中的簡單多邊形，我們可以演示耳切法的實現(xiàn)過程和構(gòu)建。首先通過計算得到兩個凹頂點集合R={0,1,3,4,6,9}和C={2,5,7,8}，它們與耳尖相同。然后計算不屬于耳尖的頂點，最后得到耳尖集合E={3,4,6,9}。

遍歷循環(huán)依次移除耳尖頂點。移除耳尖3 后，我們可以觀察到耳尖所代表的三角形T1=<2,3,4>被移除，然后對與頂點3相關(guān)聯(lián)的頂點進(jìn)行判斷是否為耳尖，并更新列表，再次移除耳尖。重復(fù)這個過程直到耳尖列表為空，最后我們可以看到將圖1 中的簡單多邊形根據(jù)耳尖拆分為多個三角形。圖2 展示了耳切法移除耳尖的過程：

圖2 耳切法的實現(xiàn)表現(xiàn)過程

在三維物體的構(gòu)建過程中，每個需要顯示的物體都由多個頂點（點的數(shù)量大于等于3）構(gòu)建基本的三角面，然后通過組合這些面構(gòu)建整個物體。簡單的平面三維物體由四個點構(gòu)成的兩個三角面組合而成。通過耳切法的處理，通過對多個頂點進(jìn)行計算，我們可以獲得多個三角形以及三角形頂點的排列順序。這樣就可以在三維空間中構(gòu)建一個簡單多邊形的三維物體。（如圖3 所示）

圖3 耳切法最終結(jié)果

5 耳切法在三維展示系統(tǒng)中的應(yīng)用

在三維展示系統(tǒng)中，區(qū)域標(biāo)繪是一個不可或缺的組成部分，其主要功能是通過用戶點擊的點來構(gòu)建一個立體的區(qū)域，并將其以三維形式展示出來。通過應(yīng)用耳切法對用戶標(biāo)繪的點進(jìn)行計算，可以快速獲得簡單多邊形的頂點排列順序，從而能夠迅速地繪制用戶標(biāo)繪的區(qū)域。這種方法可以實現(xiàn)實時展示和實時編輯修改功能。（如圖4 所示）

圖4 耳切法在三維展示系統(tǒng)的應(yīng)用

6 結(jié)語

通過本次研究和應(yīng)用，我們充分利用了耳切法來解決三維展示系統(tǒng)中區(qū)域標(biāo)繪的多邊形構(gòu)建問題，極大地提高了拆分三角形的效率。在區(qū)域標(biāo)繪設(shè)備的框選功能中，大大增強了標(biāo)繪的效率，解決了用戶在標(biāo)繪過程中受限于規(guī)定的點數(shù)和形狀的限制，為用戶提供了更好的標(biāo)繪體驗。這種方法大大增強了三維展示系統(tǒng)的豐富性和實用性。

通過以上研究成果，我們?yōu)槿S展示系統(tǒng)的區(qū)域標(biāo)繪功能提供了一種高效且靈活的解決方案，為用戶提供了更好的操作體驗。在未來的研究和應(yīng)用中，我們可以進(jìn)一步探索耳切法在其他領(lǐng)域的應(yīng)用，并不斷改進(jìn)和優(yōu)化算法，以滿足不同場景下的需求。