基于文件內存映射和多線程的三角網格模型快速拓撲重構

陳義明，張應中，羅曉芳

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

0 引言

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

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

1 三角網格模型重構總體方案

1.1 STL三角網格模型重構需求

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

STL三角網格模型重構需求就是將無序的三角面集按照一個三角網格拓撲數據結構重新進行組織，構建三角面、邊和頂點之間的拓撲關系，為后續網格模型應用提供支撐。

1.2 基于面的三角網格拓撲數據結構

為了表示三角網格模型面、邊和頂點之間的拓撲關系，一個緊湊有效的拓撲數據結構是必要的。三角網格拓撲數據結構有很多，典型代表是半邊數據結構，但傳統半邊數據結構占用較大的內存，如果三角形頂點個數為，則需要180個字節，本文采用文獻提出的基于面的數據結構，該數據結構通過面和頂點表示一個三角形拓撲信息，僅占用52個字節（32 位編程），并且能夠表示流形和非流形三角網格信息，提供三角拓撲信息訪問機制，保證重構后的網格數據能夠實現高效的拓撲信息的查詢。該數據結構如圖1所示。

圖1 基于面的三角網格拓撲數據結構

主要內容如下：

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

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

1.3 文件內存映射及多線程并行處理

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

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

1.4 三角網格模型拓撲重構總體方案設計

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

圖2 STL三角網格拓撲并行重構總體方案

首先通過Windows 系統提供的文件內存映射機制，將要重構的三角網格文件映射到應用進程的虛擬內存中，映射過程中沒有數據的實際拷貝操作，文件只是邏輯上存在于進程的虛擬內存之中，系統通過缺頁中斷機制訪問位于磁盤上的文件數據。

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

將拓撲重構任務分配給多個處理線程，每個線程讀取內存映射文件的一個分段，共同并行地完成三角網格模型的拓撲重構。

2 STL三角網格文件映射分段及多線程設計

2.1 STL三角網格文件映射分段

本文采用Windows 提供用于大型文件內存映射機制的API函數實現STL三角網格文件映射分段，具體實現過程如下。

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

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

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

圖3 STL文件分段內存映射

具體分段步驟如下：

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

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

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

2.2 多線程設計

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

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

線程的執行是由CPU 進行調度的，一個CPU 在同一時刻只會執行一個線程，如果多個線程，操作系統一般采用時間片輪轉的方式，任務的切換會導致額外的開銷。本文涉及的重構計算主要依賴于CPU，因此選擇線程數量=CPU核數+1。

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

3 基于多線程的三角網格模型并行拓撲重構

3.1 三角網格模型拓撲重構算法分析

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

圖4 基于面的拓撲重構算法［6］

（1）創建三角面對象。每讀取一個三角面數據，就創建一個三角面對象，并加入到重構的三角網格模型中。

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

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

3.2 三角網格模型拓撲并行重構策略

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

（1）設置共享數據區。每個線程僅需要對部分三角面并行執行相同三角面重構操作，構造生成的頂點和三角面對象存儲在共同的Hash 點表和三角面表中，將共同的Hash 點表和三角面表設置為共享區域。

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

3.3 三角網格模型拓撲并行重構實現

基于上述STL 文件分段操作和并行重構策略，本文基于文獻［6］給出的三角網格拓撲重構算法基礎上，實現了網格模型拓撲并行重構，主要操作步驟如下。

（1）創建并行重構線程。根據設置的線程數量，創建并行重構線程。創建之前文件內存映射分段完畢，每一個線程設置讀取相應的文件分段的偏移長度，偏移長度按照3.1給出的方法計算。

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

圖5 三角網格并行拓撲重構算法流程

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

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

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

由于文件已經被映射到內存中，讀取文件幾乎和內存操作速度相當，沒必要單獨為未重構的模型分配內存，節省了內存空間。

4 重構實驗

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

圖6 STL三維網格文件模型顯示

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

表1 三種方法重構網格數據的時間對比

通過時間對比可以看到，內存映射技術能有效提高文件讀取速度，平均的讀取效率比普通單線程提高15%以上。在內存映射的基礎上使用多線程技術，由于利用了CPU 并行處理文件的優勢，使得讀取和重構效率比單線程的內存映射提高20%以上。綜合分析，多線程內存映射在讀取大規模的三角網格文件時，比起傳統的單線程方法效率提升顯著。

5 結語

三角網格文件的快速拓撲重構對后續的網格應用至關重要。針對大數據量的網格文件占用空間大，重構速度慢的問題，本文提出了一種基于內存映射和多線程的三角網格模型快速重構方法，通過對大型STL 三角網格文件內存分段映射，采用多線程并行對文件分段內容分別進行網格數據重構，重構出基于面的三角網格模型拓撲數據結構，與傳統的重構方法相比，重構效率得到了明顯提升，實驗表明了該方法的可行性。