基于外存八叉樹STL 模型的拓撲重建方法

翟晨龍， 朱冬梅， 賀可太， 孟曉偉

（北京科技大學機械工程學院， 北京 100083）

0 引言

快速成型技術幾年來發展迅速， 如Selective laser melting（選擇性激光熔化）、Fused Deposition Modeling（熔融沉積制造）、Digital Light Processing（數字光處理）等，這些制造方式改變了原來的制造方式由減材制造轉向增材制造，STereoLithography（STL）文件是增材制造領域常用模型文件， 隨著增材制造技術發展需要打印的模型具有的結構也變得更復雜，STL 模型文件所需的存儲空間變大。STL 模型由大量三角面片組成，儲存信息時每個三角面片三個頂點坐標和法向量[1]，由于STL 文件不包含任何拓撲信息和表面結構， 模型上某一頂點將被多個三角面片共有， 共有的頂點數據被重復保存導致大量信息冗余。 STL 文件儲存方式可分為二進制和ASCII 碼兩種方式各有優缺點， 二進制儲存形式占用空間小但不可修改信息不可見讀取速度快，ASCII 碼形式占用空間大讀取速度慢內容可修改， 這就導致打開大型模型文件時需要更多時間， 在進行大數量網格模型縮放或者移動時就會導致卡頓， 為了滿足增長性能要求同時盡可能保證模型特征，需要優化模型組織和管理方法，使用多分辨率對象在網絡波動時平滑地適應圖形環境視覺質量， 還可以利用貪婪調度策略最小化用戶收到的錯誤[2]實現不同分辨率下動態表示模型可以采用Levels of Detail（LOD 技術，LOD技術意為多細節層次， 它能夠根據視距和視角不同采用不同分辨率顯示模型，能夠很好符合人機交互的要求，所以LOD 技術常被應用與大規模數據管理和調度。 在表示三維地形使用細節層次模型（LOD）、四叉樹和局部曲率熵，通過三者結合可以靈活控制四叉樹深度并動態調度大規模LOD 地形，利用四叉樹可以消除不同LOD 之間裂紋[3]；加載大規模攝影三維模型同樣可以使用分層多分辨率的思想，采用網格+四叉樹+十六進制樹構建空間索引，使用分層分塊的3D 模型，滿足海量模型可視化和實時交互的要求[4]。在制圖軟件中打開STL 文件時可以看到模型由三角網格構成，在曲率變化大的部分細節表達不夠充分，可以使用等人提出基于視覺顯著度加權的算法用于解決網格簡化中尖銳特征保持差的問題， 通過平衡不同區域權重，優化局部區域特征保持問題[5]。 三角網格在拓撲結構中屬于非結構化網格， 它與結構化網格區別在于非結構化網格每個結點周圍的單元數目可能不相同如三角網格一個頂點至少有三個及其以上的三角單元； 雖然在信息訪問不如結構化網格簡單和求解程序更有效率， 但表達復雜幾何體時非結構畫網格存在優勢， 非結構化網格因其形狀具有任意性所以它具有良好的幾何適應性， 網格生成算法自動化程度更高，Delaunay 三角剖分法是一種構建三角網格的算法具有拓撲性、最大化最小角和易于擴展性的優點，Guo J 等人使用約束的Delaunay 三角剖分調整參數域的邊界實現了高精度和高質量的重新網格化算法[6]，雙曲面Delaunay 三角剖分由最小剖分數量的問題[7]。八叉樹是一種數據結構，具有訪問效率高、數據插入和刪除操作便利且高效和數據有序空間利用率高的優點，Koh N，Jayaraman P K 等提出一種新的八叉樹結構截斷八叉樹，它可以自適應地修建頂部去截斷樹，擴展了節點隨機訪問和大數據集的核心外流提供了高效的查詢性能[8]，Saputra A 等人利用八叉樹分解分層網格將RVE 轉換成數值模型，將每個八叉樹單元建模為邊界多面體元素，取得更好的模型均勻化效果[9]將坐標信息存儲到子結點中讀取不同子節點可以實現模型網格的變化，Tu T 提出將外存八叉樹映射到數據庫結構， 所有八叉樹操作可以通過查詢和更新數據庫來完成[10]。 本文將STL 文件坐標存入八叉樹結構， 解決上述使用非結構化網格和STL 存儲特性導致文件讀取速度慢的問題，實現多細節層次管理，提出基于八叉樹多細節層次三維網格模型， 對STL 文件進行拓撲重建。

1 實驗流程

用于智能制造領域，三維建模方向，提高STL 模型打開效率和實現多分辨率顯示要求， 采用基于八叉樹存儲結構對STL 模型進行拓撲重建首先將三維模型投影到二維平面，在二維平面進行網格劃分，并將劃分好的網格映射到三維模型上，如圖1 所示。

圖1 整體流程圖

總方法可以分為三個部分首先將模型進行分割并將分割好的子分部投影到平面上并將點集儲存到八叉樹樹中第二部分在平面使用Delaunay 三角形法進行網格劃分第三部分將劃分好的網格投影到對應子部分表面。

2 STL 模型拓撲重建方法提出

2.1 三維模型分割和平面點集獲取

三維模型分割可以在空間根據特征不同將模型分割， 在三維模型進行簡化時采用引入圖卷積神經網絡的模型分割簡化算法，經過訓練后分割效果良好[11]，也可以將模型分成多模態二維進行表示，Pires C 提出一種級聯模型模型分為兩個階段， 第一階段檢測階段提取邊界特征，然后將這些邊界框送去第二分割階段，通過這種方法提高了圖像處理時間并獲得了更好的分割分數[12]QinNN等人通過掃描點云提取出幾個低層判別局部特征將三維地形轉變為多模態二維表示， 通過并取得了理想的識別地形點云的效果[13]模型分割中存在過度歸一化問題，Zhu L[14]提出一種Explored Normalized Cut（ENCut）模型分割方法一定程度上解決了過度歸一化問題增強小對象分割，大型三維模型結構復雜分割算法運行時間更長，Yu L 等[15]將MobileNetv3 與DeepLabv3+ 相結合提出改進的DeepLabv3+網絡輕量級語義分割算法， 提高了兩者結合降低模型復雜度，提高模型運行效率。

本文采用將三維STL 模型根據法向量夾角不同將模型進行分割，再將分割子部分投影到平面獲得點集，三維模型往往都是封閉的實體， 在投影到二維平面存在同一個（x，y）坐標上存在不只一個坐標，如果直接將三維模型投影到二維平面就會導致模型重疊如圖2 所示這兩個三角面片在Z 方向上投影的話就會發生干涉現象， 這樣劃分出來網格會有部分缺失的現象。

圖2 某方向上三角面片重疊現象

所以需要對三維模型STL 文件進行處理， 避免產生上述問題。 采用的方法是基于法向量分割模型， 利用STL 文件儲存特征進行模型的分割，STL 文件存儲了每個三角面片法向量和頂點坐標，根據法向量夾角大小可以將封閉的三維模型剖分看，首先任選一個三角面片作為基準從該三角面片向外進行擴散判斷其他三角面片法向量與基準法向量的夾角是否小于設定閾值， 如果小于閾值則與基準三角面片構成新的模型， 直到有三角面片法向量與基準法向量夾角大于閾值則停止該方向的判斷，所有方向都判斷完畢，保存第一部分分割模型。 開始下一次分割模型首先從剩余三角面片選一片作為基準， 與其他三角面片進行法向量夾角判斷直到整個模型被分割成幾個子區域并記錄最后一個三角面片坐標值，確定該三角面片為特征三角面片，該面片某一條邊位于特征邊上，不同子部分由特征邊分隔開，以典型零件凸輪為例，查看分割效果如圖3 所示，不同子部分表使用不同顏色表示。 當對某個子部分進行投影時，使用AABB 包圍盒將子分部包裹， 然后進行三維空間坐標變換， 使得基準法向量與Z 軸重合。 空間中的坐標變換可以拆分為旋轉和平移， 只需要求出旋轉矩陣和平移矩陣就可以讓每個子部分基準法向量與世界坐標系Z 軸重合。

圖3 典型零件模型分割

其中：RxRyRz為沿X 軸、Y 軸和Z 軸的旋轉矩陣，X1Y1Z1為基準法向量局部坐標系三維坐標，X、Y、Z 為基準法向量世界坐標系下的坐標。

其中：α、β 和δ 分別為沿X、Y 和Z 軸方向轉角。

而后進行平移操作，使得兩個坐標系原點重合。

其中：T—平移矩陣；△x、△y 和△z 為X、Y 和Z 軸平移量。

由于STL 模型是由點和法向量形成的三角面片組成，所以將三維Z 坐標歸零可以在二維平面上的點云，將包圍盒和三維坐標（x，y，z）中Z 坐標值歸零，同時將構成子部分邊界的點和包圍盒點以Z 坐標為零的形式存儲到TZBList 表中并調用TZBList 表， 在二維平面將子分部邊界點都連接可以將模型輪廓描繪出來同時也形成了包圍框，實現三維模型的平面化效果如圖4 所示，最外圍的邊框是AABB 包圍盒的投影。

圖4 三維曲面平面化

當點集投影到平面后，將點集存儲到八叉樹中。

2.1.1 分割和點集投影算法流程

創建Vertex 函數表示具有x，y 和z 坐標點，Triangle函數包含三個頂點實例和三角形的法向量，Mesh 結構包含所有Triangle 實例。

（1） 調用ReadSTL 函數讀取STL 文件三角面片信息并將數據存儲在Mesh 結構中。

（2）調用SegmentModel 函數，SegmentModel 功能是將一個三角網格模型（由一組三角形組成）根據給定的角度閾值分割成不同的部分。具體來說，函數將輸入的三角形列表按照一定的方式分組， 使得每個分組內的三角形法線向量之間的夾角小于等于給定的角度閾值。這樣，分組后的每個部分都可以看做是在一個平面上的一個封閉的曲面區域， 可以被單獨處理或渲染。 該函數接受兩個參數： 一個Triangle 類型的向量和一個double 類型的角度閾值。 函數返回一個Triangle 類型的向量的向量，每個向量都表示一個被分割出來的部分，其中包含一組三角形。

該函數的實現過程可以描述如下：

初始化一個Triangle 類型的向量列表parts。 遍歷輸入的三角形列表，對于每個三角形Triangle：如果parts 為空，將Triangle 添加到一個新的向量內，將該向量添加到parts 中。 否則，遍歷parts 中的所有向量part，找到法線向量與Triangle 法線向量夾角最小的向量。使用使用Cosine函數計算兩個Vertex 實例之間的角度的余弦值之后用IsAngleGreaterThan 函數檢查兩個向量之間的角度是否大于給定的閾值。 如果該向量的法線向量與tri 法線向量夾角小于等于給定的角度閾值， 將Triangle 添加到該向量中。 否則，將Triangle 添加到一個新的向量內，將該向量添加到parts 中。 返回parts。

（3）調用writeSTL 函數將分割后子分部寫入STL 文件中， 它需要接受兩個參數第一個是std：：string 類型的文件名，表示要寫入的文件的路徑和文件名。第二個參數是一個Triangle 類型的向量，包含要寫入的三角形數據。

（4）將分割好的子部分進行點集投影首先調用read-STL 函數讀取STL 文件中的三角形信息。 然后選擇其中一個三角形的法向量作為平面的法向量， 并將平面上的一個點設置為原點。接下來，將所有三角形的頂點投影到這個平面上，并將所有的投影點保存到一個向量projectedPoints 中。最后，將所有投影點輸出到一個文本文件中。

2.1.2 二維平面進行八叉樹網格劃分

在讀取平面點集后， 通過Delaunay 三角形法進行平面網格劃分，Delaunay 三角形法是將給定點集進行連線，劃分三角網格的網格劃分方法， 它劃分三角形原理是保證組成三角網格三個頂點形成的外接圓內不能包含其他點， 這樣做可以減少出現夾角狹小的三角形的可能性算法具體步驟如下：①將點集進行Delaunay 三角剖分，得到由三角形組成的網格；②進行邊從屬判斷，判斷這條邊屬于幾個三角形（至多兩個）如果只屬于一個三角形。 那么將加入到最終網格中，如果屬于兩個三角形的公共邊，則將兩個三角形組合成四邊形， 再將四邊形拆分成兩個三角形存入最終的三角網格； ③進行三角形外接圓閾值判斷，當半徑小于設定閾值時拆分成三個小的三角形，這么做是因為當半徑過于小時意味著這個三角形的形狀非常扁平，會造成數值計算的不穩定和精度問題，將狹長三角形拆分成三個小的三角形可以保證三角形外形更合理提高穩定性，拆分這個操作還會提高三角網格局部穩定性。

2.2 算法流程

（1） 調用PointReader：：readpoints 函數讀取點集文件， 讀取后存儲在vector〈PointZ〉pointsZ 中遍歷pointsZ，將每個元素x，y 坐標存儲在vector〈point〉points 中， 之后遍歷Points 將其每個元素的x，y 坐標輸出到控制臺。

（2）創建名為”Points”的窗口，并在窗口繪制points 中的每個點。

（3）進行Delaunay 三角剖分，通過調用OpenCV 庫中的Subdiv2D 類和getTriangleList 函數來完成。 該函數將points 中的點作為輸入，生成了一組三角形，并將其存儲在vector〈Vec6f〉 triangles 中。

（4）遍歷triangles，繪制了每個三角形，并生成名為"delaunay.png" 的PNG 文件。 另外， 代碼還將points 和triangles 存儲在一個名為"output.obj" 的OBJ 文件中。

2.3 步驟三將劃分好的二維網格映射到三維模型

2.3.1 基于樸素反映射算法

二維平面與三維模型子部分存在對應關系， 都過同一個基準法向量， 如果想要找到二維網格在三維模型上的點，直接的方法是通過某一網格結點做一條直線，通過遍歷所有三角面片求交點但這計算量無疑太大。

擬用將三維模型投影到二維平面的方法逆向解決上述計算量大的問題， 首先將二維平面上網格結點坐標擴展到三維空間，每個結點Z 坐標都設置為0 即（x，y）轉標為（x，y，0）通過將每個三角面片的頂點投影到二維平面上， 以某一網格結點為起始點計算到每個三角面片距離記錄下最短距離的對應點， 并從該點去尋找包含該點的三角面片然后做過網格結點且平行于基準法向量的直線與上面找到的三角面片求交點， 而后將求得點的Z 坐標存入到網格結點。

3.2 算法流程

掃描二維平面網格結點建立結點線性表WPointList，建立STL 模型頂點列表SPointList 用于存儲頂點投影到二維平面后的坐標， 建立存儲三維空間STL 模型子區域三角面片線性表PlaneList 以矩形三角面片為例見圖5，表1。

表1 平面網格結點線性表

表2 STL 模型頂點線性表

表3 STL 模型三角面片線性表

圖5 矩形三角面片

遍歷表WPointList 將存儲的二維坐標擴展到三維，Z 軸坐標為零。

遍歷三維模型子部分將坐標存入表SPointList，并將Z 坐標歸零。

循環遍歷表WPointList直至最后一個坐標值，并進行以下操作。

（1）取出表WPointList 順序第一值Q 點與表SPointList中的值進行距離計算找到最短的距離對應點的坐標并記為A 點。

（2）遍歷表PlaneList，找到含A 點的三角面片，將三角面片存入到ZList。

（3）做過Q 點且并行與Z 軸的直線，與ZList 中的三角面片求交集，將求出的Z 坐標保存到對應Q 點的Z 坐標上。

（4）接著遍歷WPointList 取下一個點同樣記為Q 點，直至遍歷WPointList 所有點。

3 實驗

本次進行實驗在Windows10 64 位操作系統進行，設備的配置信息：CPU 為i5-8300H，GPU 使用NVIDIA GTX1060， 內存16GB，SSG 為512GB， 實驗使用Visual Studio 軟件C++語言，使用OpenCV 庫展現生成點集和網格，使用Eigen 庫進行矩陣和向量計算。

基于第二部分提出的算法思想， 編寫了相應的網格生成程序，本節對算法進行實例驗證，以圓錐體和正方體為例，模型如圖6 和圖7 所示，通過限制同一部分三角面片之間法向量夾角， 將圓錐分為了兩個子部分分別是錐體和底面圓形，子部分如圖6 所示。

圖6 圓錐體與劃分的子部分

圖7 正方體與分割后模型

正方體則被分成了6個面片將模型分開后沿對應法向量進行投影可以保證在一個Z 坐標下不會有兩個點，將導出結點存入八叉樹數據結構中， 后面使用Opencv 把得到的八叉樹點集畫出來（圖8），并使用Delaunay 三角形法進行平面網格劃分， 最終得到子部分進行網格劃分后的模型，如圖9 所示。

圖8 八叉樹點集

圖9 Delaunay 法劃分網格

4 結論

本文基本STL 文件使用八叉樹結構對模型進行拓撲重建這一主題進行研究，提出了基于STL 模型分割和重建網格算法， 研究算法中的關鍵技術，通過Visual studio 實現計算機程序，并進行了簡單的實例驗證主要工作為提出了一種基于STL 模型文件分割和網格劃分算法， 基于每個三角面片法向量夾角大小對整體模型進行分割， 將封閉的模型分割成多個子區域， 再將生成的子區域投影到所選三角面片法向量垂直的平面上， 得到平面點集再將這些平面點集使用八叉樹結構儲存， 之后使用Delaunay 三角形法進行平面網格劃分，最終得到具有拓撲結構的網格模型。