陳義明，張應(yīng)中，羅曉芳

（大連理工大學機械工程學院，大連 116023）

0 引言

隨著三維數(shù)字掃描技術(shù)的發(fā)展，很多復雜的實體對象，例如復雜零部件、大型建筑物和地理場景等，通過數(shù)字掃描獲取其三維數(shù)字模型，通常會將掃描的點云模型轉(zhuǎn)換成三角網(wǎng)格模型，并且隨著模型的精度的提高，由此產(chǎn)生的三角網(wǎng)格規(guī)模非常龐大，三角面數(shù)量達到幾百萬或者上千萬，其結(jié)果是文件大小常常達到了幾百MB 甚至數(shù)GB。此外，目前三角網(wǎng)格模型采用STL 格式存儲，STL 三角網(wǎng)格文件僅僅是一個三角面集的排列，包含大量的重復頂點，缺乏三角面、邊頂點之間的拓撲關(guān)系，三角網(wǎng)格模型的進一步應(yīng)用需要進行拓撲關(guān)系的重構(gòu)。因此如此大數(shù)據(jù)量的三角網(wǎng)格文件，若采用傳統(tǒng)的文件處理技術(shù)進行三角網(wǎng)格數(shù)據(jù)的讀取及重構(gòu)，勢必模型的處理效率較低，等待的時間過長。

目前對于提高大型數(shù)據(jù)文件處理效率主要途徑是采用文件內(nèi)存映射技術(shù)加快讀取速度，該方法通過將文件的全部或部分內(nèi)容映射到進程的虛擬內(nèi)存之中，減少了磁盤的I/O 操作，使應(yīng)用程序可以通過內(nèi)存直接訪問位于磁盤上的文件數(shù)據(jù)。在大規(guī)模計算方面，主要采用并行計算處理技術(shù)，對于現(xiàn)代多核計算機，多線程技術(shù)由于其高效的處理效率，已經(jīng)成為多任務(wù)處理中的主流方式。但在三角網(wǎng)格模型拓撲重構(gòu)方面，基于文件內(nèi)存映射和并行重構(gòu)研究較少。本文考慮到STL 網(wǎng)格文件中各個面的數(shù)據(jù)相互獨立的特點，多線程技術(shù)可以有效運用于文件處理操作中，融合內(nèi)存映射和多線程技術(shù)，實現(xiàn)了對大規(guī)模三角網(wǎng)格模型快速重構(gòu)，通過計算機多核多線程處理數(shù)據(jù)的優(yōu)勢，模型數(shù)據(jù)的重構(gòu)效率得到較大的提升。

1 三角網(wǎng)格模型重構(gòu)總體方案

1.1 STL三角網(wǎng)格模型重構(gòu)需求

STL文件存儲了三維網(wǎng)格模型中三角形面的幾何信息，包括面的法向量及該面的三個頂點坐標。STL三角網(wǎng)格文件格式簡單，但僅僅是一個三角面集的排列，包含大量的重復頂點，并且缺乏三角面、邊頂點之間的拓撲關(guān)系。如果三角網(wǎng)格模型需要進一步應(yīng)用，例如網(wǎng)格幾何運算、網(wǎng)格修復和網(wǎng)格特征識別等，重構(gòu)其拓撲關(guān)系是必要的。

STL三角網(wǎng)格模型重構(gòu)需求就是將無序的三角面集按照一個三角網(wǎng)格拓撲數(shù)據(jù)結(jié)構(gòu)重新進行組織，構(gòu)建三角面、邊和頂點之間的拓撲關(guān)系，為后續(xù)網(wǎng)格模型應(yīng)用提供支撐。

1.2 基于面的三角網(wǎng)格拓撲數(shù)據(jù)結(jié)構(gòu)

為了表示三角網(wǎng)格模型面、邊和頂點之間的拓撲關(guān)系，一個緊湊有效的拓撲數(shù)據(jù)結(jié)構(gòu)是必要的。三角網(wǎng)格拓撲數(shù)據(jù)結(jié)構(gòu)有很多，典型代表是半邊數(shù)據(jù)結(jié)構(gòu)，但傳統(tǒng)半邊數(shù)據(jù)結(jié)構(gòu)占用較大的內(nèi)存，如果三角形頂點個數(shù)為，則需要180個字節(jié)，本文采用文獻提出的基于面的數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)通過面和頂點表示一個三角形拓撲信息，僅占用52個字節(jié)（32 位編程），并且能夠表示流形和非流形三角網(wǎng)格信息，提供三角拓撲信息訪問機制，保證重構(gòu)后的網(wǎng)格數(shù)據(jù)能夠?qū)崿F(xiàn)高效的拓撲信息的查詢。該數(shù)據(jù)結(jié)構(gòu)如圖1所示。

圖1 基于面的三角網(wǎng)格拓撲數(shù)據(jù)結(jié)構(gòu)

主要內(nèi)容如下：

頂點類中用3個float變量存儲三角面三個頂點坐標，使用一個面類的指針指向該點所在的三角形面，通過該指針，可以訪問該點引用的三角面信息。頂點類的編碼如下：

面的結(jié)構(gòu)中包含存儲面的法向量，存儲該面的三個頂點指針，存儲該面與相鄰的其它3個面的指針，面類的編碼如下：

1.3 文件內(nèi)存映射及多線程并行處理

文件內(nèi)存映射技術(shù)是Windows 系統(tǒng)及Linux系統(tǒng)中廣泛使用的大文件讀寫技術(shù)，該技術(shù)通過將文件的全部或部分內(nèi)容映射到進程的虛擬內(nèi)存之中，減少了數(shù)據(jù)的拷貝操作，提高了讀取速度。映射過程中沒有數(shù)據(jù)的實際拷貝操作，文件只是邏輯上存在于進程的虛擬內(nèi)存之中，系統(tǒng)通過缺頁中斷機制訪問位于磁盤上的文件數(shù)據(jù)。由于不再需要執(zhí)行文件的I/O 操作，并且讀取過程中系統(tǒng)不用再為文件申請并分配緩存，使得內(nèi)存映射技術(shù)能夠有效提高大文件的讀取速度。

多線程并行處理技術(shù)是指從軟件或者硬件上實現(xiàn)多個線程并發(fā)執(zhí)行的技術(shù)。通常在一個Windows程序中，一個獨立運行的程序片段稱為“線程”（Thread），同時采用多個線程處理同一問題，稱為多線程處理。現(xiàn)代計算機通過軟硬件的配合能夠并行的運行多個線程，使計算機的整體性能得到較大提高。目前大部分計算機系統(tǒng)都有多核心處理器或同時多線程處理器，為開展多線程并行重構(gòu)三角網(wǎng)格模型提供條件。

1.4 三角網(wǎng)格模型拓撲重構(gòu)總體方案設(shè)計

基于上述分析，為了更高效地重構(gòu)三角網(wǎng)格模型，本文提出如圖2所示的STL三角網(wǎng)格模型多線程并行拓撲重構(gòu)總體方案。該方案主要包括如下3個步驟。

圖2 STL三角網(wǎng)格拓撲并行重構(gòu)總體方案

首先通過Windows 系統(tǒng)提供的文件內(nèi)存映射機制，將要重構(gòu)的三角網(wǎng)格文件映射到應(yīng)用進程的虛擬內(nèi)存中，映射過程中沒有數(shù)據(jù)的實際拷貝操作，文件只是邏輯上存在于進程的虛擬內(nèi)存之中，系統(tǒng)通過缺頁中斷機制訪問位于磁盤上的文件數(shù)據(jù)。

對于大型網(wǎng)格模型文件采用多線程并行分段處理可以大大提高拓撲重構(gòu)效率。線程的數(shù)量需要綜合考慮CPU 核的數(shù)量及要處理文件的大小，通過實驗確定出一個性能較優(yōu)化的線程數(shù)量，再依據(jù)線程數(shù)量確定文件分割的段數(shù)，使每一個線程對應(yīng)一個內(nèi)存映射文件的分段。

將拓撲重構(gòu)任務(wù)分配給多個處理線程，每個線程讀取內(nèi)存映射文件的一個分段，共同并行地完成三角網(wǎng)格模型的拓撲重構(gòu)。

2 STL三角網(wǎng)格文件映射分段及多線程設(shè)計

2.1 STL三角網(wǎng)格文件映射分段

本文采用Windows 提供用于大型文件內(nèi)存映射機制的API函數(shù)實現(xiàn)STL三角網(wǎng)格文件映射分段，具體實現(xiàn)過程如下。

首先使用CreateFile 函數(shù)創(chuàng)建文件內(nèi)核對象，得到文件內(nèi)核對象的句柄Handle，然后將該句柄傳入CreateFileMapping 函數(shù)中創(chuàng)建文件映射內(nèi)核對象，該函數(shù)用于指定文件的尺寸及訪問文件的方式，并返回映射對象的句柄MapHandle。

將上述文件映射對象句柄作為MapViewOf?File函數(shù)的參數(shù)，該函數(shù)負責將文件的全部或部分內(nèi)容映射到進程的虛擬內(nèi)存中，若映射成功，返回一個LPVOID 類型的指針，這是一個無類型的指針，通常將該指針強制轉(zhuǎn)換成char*類型的指針，使其指向文件映射的起始位置。最后當不再需要使用該映像數(shù)據(jù)時，通過Un?mapViewOfFile 函數(shù)卸載映射，文件讀取結(jié)束時，使用CloseHandle函數(shù)關(guān)閉文件映射對象。

由于STL 文件的數(shù)據(jù)規(guī)?？赡芎艽?，按照上述總體方案設(shè)計，需要對三角網(wǎng)格文件進行分段映射處理。由于Windows 操作系統(tǒng)通常按頁存取數(shù)據(jù)，并且系統(tǒng)中頁的分配粒度為64 kB，因此分段偏移地址必須取為64 kB的整數(shù)倍。但這樣的分段方式容易使一個完整的三角面數(shù)據(jù)被分在兩個不同的段中，導致該面的數(shù)據(jù)無法得到正常讀取。為解決此問題，本文提出如圖3所示的分段方法。

圖3 STL文件分段內(nèi)存映射

具體分段步驟如下：

（1）確定分段數(shù)量。按照總體方案設(shè)計，分段數(shù)量取決于選擇的線程數(shù)量。具體線程數(shù)量選擇在下一節(jié)介紹。

（2）計算跨界長度。二進制的STL 文件中每個三角形的幾何信息由固定的字節(jié)數(shù)表示。開頭的84個字節(jié)用于描述模型的文件信息，其中80個字節(jié)是文件頭，用于存儲零件名，剩下的4字節(jié)為一個整數(shù)，用于存儲文件中包含的三角形數(shù)量，之后用固定的字節(jié)數(shù)表示三角形的幾何信息，每個三角形數(shù)據(jù)占用50字節(jié)。如果，為自然整數(shù)，則跨界長度按如下公式計算：

（3）向后偏移跨界長度映射下一個分段。因為上一個分段一次性將64000*字節(jié)映射到內(nèi)存，在讀取最后一個三角面時，與映射數(shù)據(jù)相差一個跨界長度，因此從第2個分段開始，映射開始地址在前一分段結(jié)束位置處向后偏移一個跨界長度。

2.2 多線程設(shè)計

隨著CPU 多核技術(shù)的出現(xiàn)，多線程并行讀取文件和信息處理可以獲得較好的操作性能。但是線程的數(shù)量也不是越多越好，因為線程間的切換和調(diào)度會消耗CPU 資源和時間，如果設(shè)置線程數(shù)量過大，會影響處理性能，一個合適的線程數(shù)量設(shè)置是有必要的。在本文提出的方法中，線程數(shù)量設(shè)置主要考慮如下因素。

如果文件長度小于8 M，即采用單線程，否則采用多線程，線程數(shù)量由以下因素確定。

線程的執(zhí)行是由CPU 進行調(diào)度的，一個CPU 在同一時刻只會執(zhí)行一個線程，如果多個線程，操作系統(tǒng)一般采用時間片輪轉(zhuǎn)的方式，任務(wù)的切換會導致額外的開銷。本文涉及的重構(gòu)計算主要依賴于CPU，因此選擇線程數(shù)量=CPU核數(shù)+1。

如果工作任務(wù)是高強度計算，則要適當降低線程數(shù)量，否則如果工作任務(wù)是事務(wù)性的工作，有等待時間，可以適當提高線程數(shù)量。

3 基于多線程的三角網(wǎng)格模型并行拓撲重構(gòu)

3.1 三角網(wǎng)格模型拓撲重構(gòu)算法分析

按照上述重構(gòu)總體方案設(shè)計，拓撲重構(gòu)模型是采用文獻［6］給出的基于面的拓撲數(shù)據(jù)結(jié)構(gòu)。文獻［6］還給出了面向STL 文件的拓撲重構(gòu)算法，如圖4所示。從給出的算法看，拓撲重構(gòu)過程主要分為如下3個操作。

圖4 基于面的拓撲重構(gòu)算法［6］

（1）創(chuàng)建三角面對象。每讀取一個三角面數(shù)據(jù)，就創(chuàng)建一個三角面對象，并加入到重構(gòu)的三角網(wǎng)格模型中。

（2）查找或者創(chuàng)建新的頂點。由于STL 網(wǎng)格文件包含大量的重復頂點，因此創(chuàng)建一個新的頂點對象前要查詢在該頂點位置是否已經(jīng)創(chuàng)建頂點，如果有就直接引用該頂點，否則創(chuàng)建新頂點。一個大型的三角網(wǎng)格模型包含上百萬個頂點，查找的效率非常重要，采用文獻［6］給出的Hash表查找。

（3）查找相鄰三角面。頂點對象完成后，通過頂點對象對面的引用，查找三角面的三個相鄰面，一次操作可能完成不了，在所有面完成后還需要執(zhí)行一遍這樣的操作。需要有一個共有的三角面表容器。

3.2 三角網(wǎng)格模型拓撲并行重構(gòu)策略

根據(jù)上述三角網(wǎng)格模型拓撲重構(gòu)算法分析，可以看出重構(gòu)過程主要由一系列的重復操作組成，完全可以將重復操作分配給多個線程完成。為此提出如下并行重構(gòu)策略。

（1）設(shè)置共享數(shù)據(jù)區(qū)。每個線程僅需要對部分三角面并行執(zhí)行相同三角面重構(gòu)操作，構(gòu)造生成的頂點和三角面對象存儲在共同的Hash 點表和三角面表中，將共同的Hash 點表和三角面表設(shè)置為共享區(qū)域。

（2）設(shè)置共享數(shù)據(jù)區(qū)域加鎖保護機制。在多線程重構(gòu)過程中，為了保證處理數(shù)據(jù)的安全，可以通過對共享區(qū)域加鎖，保證同一時刻只有一個線程對共享數(shù)據(jù)區(qū)域進行修改操作。為此設(shè)置一個公有的可操作標志，當一個線程在進行頂點或者面創(chuàng)建操作時，可操作標志為0，操作完成后置為1。只有當可操作標志為1 時，線程的所有操作才可進行。這種加鎖解鎖機制有效實現(xiàn)了線程間的互斥訪問，保證了程序運行的穩(wěn)定性。

3.3 三角網(wǎng)格模型拓撲并行重構(gòu)實現(xiàn)

基于上述STL 文件分段操作和并行重構(gòu)策略，本文基于文獻［6］給出的三角網(wǎng)格拓撲重構(gòu)算法基礎(chǔ)上，實現(xiàn)了網(wǎng)格模型拓撲并行重構(gòu)，主要操作步驟如下。

（1）創(chuàng)建并行重構(gòu)線程。根據(jù)設(shè)置的線程數(shù)量，創(chuàng)建并行重構(gòu)線程。創(chuàng)建之前文件內(nèi)存映射分段完畢，每一個線程設(shè)置讀取相應(yīng)的文件分段的偏移長度，偏移長度按照3.1給出的方法計算。

（2）啟動并行重構(gòu)算法各個線程。每個線程基本上并行執(zhí)行相同的操作，其中線程執(zhí)行過程如圖5所示。

圖5 三角網(wǎng)格并行拓撲重構(gòu)算法流程

（3）讀取文件分段中的三角面片。每讀取一個三角面數(shù)據(jù)，開始構(gòu)建頂點對象和面對象，在操作前檢查公有標志：opFlag，只有當opFlag等于1時才執(zhí)行操作，如果要執(zhí)行頂點對象或者面對象的插入，首先將opFlag 置為0，待插入操作完成后，將opFlag 再置為1。因此當一個線程在執(zhí)行插入寫操作時，其它所有線程的操作被等待，直到opFlag變回到1。

（4）一個三角面的三個頂點都處理完成后，將讀取下一個三角面，如果三角面讀取處理完成，子線程結(jié)束，否則轉(zhuǎn)上面第（3）步。

（5）主線程等待所有子線程讀取結(jié)束，文件處理完成，主線程結(jié)束。

由于文件已經(jīng)被映射到內(nèi)存中，讀取文件幾乎和內(nèi)存操作速度相當，沒必要單獨為未重構(gòu)的模型分配內(nèi)存，節(jié)省了內(nèi)存空間。

4 重構(gòu)實驗

本文在Windows 10 操作系統(tǒng)上采用Visual C++和OpenGL 編程進行快速重構(gòu)實驗，實驗計算機配置i5 2.5 GHz CPU、4 G內(nèi)存。依次選用箱體模型、端蓋模型及馬的模型的STL文件為讀取對象，模型重構(gòu)后OpenGL顯示如圖6所示。

圖6 STL三維網(wǎng)格文件模型顯示

對以上模型采用普通單線程方法、單線程內(nèi)存映射方法以及多線程內(nèi)存映射方法依次讀取文件并重構(gòu)網(wǎng)格數(shù)據(jù)。由于系統(tǒng)CPU 為雙核處理器，故多線程內(nèi)存映射方法中的線程數(shù)確定為三個，經(jīng)實驗驗證，三個線程的讀取效率最高。從STL 網(wǎng)格文件開始讀取到網(wǎng)格數(shù)據(jù)拓撲關(guān)系的重構(gòu)，記錄系統(tǒng)總的運行時間，表1為三種方法對不同數(shù)據(jù)量的三角網(wǎng)格文件的讀取及重構(gòu)時間：

表1 三種方法重構(gòu)網(wǎng)格數(shù)據(jù)的時間對比

通過時間對比可以看到，內(nèi)存映射技術(shù)能有效提高文件讀取速度，平均的讀取效率比普通單線程提高15%以上。在內(nèi)存映射的基礎(chǔ)上使用多線程技術(shù)，由于利用了CPU 并行處理文件的優(yōu)勢，使得讀取和重構(gòu)效率比單線程的內(nèi)存映射提高20%以上。綜合分析，多線程內(nèi)存映射在讀取大規(guī)模的三角網(wǎng)格文件時，比起傳統(tǒng)的單線程方法效率提升顯著。

5 結(jié)語

三角網(wǎng)格文件的快速拓撲重構(gòu)對后續(xù)的網(wǎng)格應(yīng)用至關(guān)重要。針對大數(shù)據(jù)量的網(wǎng)格文件占用空間大，重構(gòu)速度慢的問題，本文提出了一種基于內(nèi)存映射和多線程的三角網(wǎng)格模型快速重構(gòu)方法，通過對大型STL 三角網(wǎng)格文件內(nèi)存分段映射，采用多線程并行對文件分段內(nèi)容分別進行網(wǎng)格數(shù)據(jù)重構(gòu)，重構(gòu)出基于面的三角網(wǎng)格模型拓撲數(shù)據(jù)結(jié)構(gòu)，與傳統(tǒng)的重構(gòu)方法相比，重構(gòu)效率得到了明顯提升，實驗表明了該方法的可行性。