一、mesh算法是什么？

三維模型有不同格式的存儲(chǔ)方式，如基于BREP的STEP格式，基于面片數(shù)據(jù)的STL/OBJ，使用xml組織文件樹(shù)的DAE。然而計(jì)算機(jī)系統(tǒng)只能處理離散的數(shù)字信號(hào)。對(duì)于一些復(fù)雜連續(xù)、追求光滑的曲面定義（比如紡錘體，球面，NURBS），就需要將其離散成一個(gè)個(gè)非常微小的面元，計(jì)算出屏幕上每一個(gè)像素點(diǎn)的顏色和灰度，才能最終形成人眼看到的畫(huà)面。

將連續(xù)的幾何表達(dá)分割成有大量三角形微元組成的過(guò)程，稱(chēng)為三角形網(wǎng)格化（也就是mesh）。CAD建模、有限元仿真、光線(xiàn)追蹤渲染等眾多技術(shù)場(chǎng)景，都離不開(kāi)三角形網(wǎng)格化手段的幫助。

二、追光幾何面臨的技術(shù)挑戰(zhàn)

追光幾何上線(xiàn)運(yùn)行以來(lái)，廣受用戶(hù)好評(píng)。但也陸陸續(xù)續(xù)收到用戶(hù)反饋一些圖形渲染相關(guān)的問(wèn)題，比如部分結(jié)構(gòu)缺失、破面、面贅生、自相交等。這些問(wèn)題的背后，都與mesh算法有著千絲萬(wàn)縷的聯(lián)系。

拍立得模型：左側(cè)為追光幾何渲染效果，右側(cè)為SolidWorks渲染效果可以看到左側(cè)存在明顯的破面現(xiàn)象。

另外對(duì)于追光幾何這樣SaaS平臺(tái)來(lái)說(shuō)，速度是影響用戶(hù)體驗(yàn)的一大因素。在硬件配置不變的情況下，需要解析的面片數(shù)量越少，占用的硬件資源（內(nèi)存/cpu）等也就越少，直觀上模型的加載速度也會(huì)更快。因此，如何在盡可能不丟失圖形信息情況下，減少三角面片的數(shù)量，優(yōu)化mesh算法，成為追光幾何技術(shù)團(tuán)隊(duì)關(guān)注的焦點(diǎn)。

三、追光幾何的解決之路

???? 問(wèn)題定位  ????

我們首先對(duì)問(wèn)題模型做了細(xì)致的拆解。比如對(duì)前文的拍立得模型，我們定位到”破面“現(xiàn)象產(chǎn)生的原因，是兩層距離非常接近（約0.3mm）的曲面發(fā)生了相交。

前文提到，對(duì)于光滑曲面，mesh本質(zhì)就是化曲為直。而影響邊界點(diǎn)采樣最重要的兩個(gè)參數(shù)是線(xiàn)性誤差和角度誤差。理論上，這兩個(gè)誤差定得越小，那么采樣點(diǎn)越密集，效果應(yīng)該也會(huì)更好，代價(jià)是面片數(shù)量會(huì)增加。

??做出假設(shè)：提高精度解千愁？??

帶著這樣的假（huan）設(shè)（xiang），我們測(cè)試了多種線(xiàn)性誤差等級(jí)下的效果。結(jié)果令人非常失望。

  紅色：邊界點(diǎn)線(xiàn)性誤差0.01；藍(lán)色：邊界點(diǎn)線(xiàn)性誤差0.001；紫色：邊界點(diǎn)線(xiàn)性誤差0.0001

即使線(xiàn)性誤差降低到0.0001，雖然面片數(shù)量增加了不少（白線(xiàn)肉眼可見(jiàn)的濃密起來(lái)），破面的面積仍然沒(méi)有縮小。這是因?yàn)槠泼姘l(fā)生在邊界內(nèi)，而降低線(xiàn)性誤差只改表了邊界區(qū)域的點(diǎn)和面片的數(shù)量，對(duì)于邊界內(nèi)的點(diǎn)沒(méi)有影響。

另外在如果優(yōu)化mesh算法時(shí)，無(wú)底線(xiàn)地提高mesh精度，也會(huì)給前端解析帶來(lái)過(guò)大的性能負(fù)擔(dān)，不可避免地引起卡頓崩潰等bug發(fā)生。可見(jiàn)，此路不通。

???? 追本溯源 ????

輕易向困難低頭絕不是幾何er 們的風(fēng)格。為了追求更快更完美的mesh效果，2022年追光幾何有幸邀請(qǐng)到大連理工機(jī)械學(xué)院孫亮教授團(tuán)隊(duì)，一同針對(duì)step/iges類(lèi)型文件的mesh算法進(jìn)行專(zhuān)項(xiàng)研究。通過(guò)閱讀源碼，我們基本梳理了三維模型mesh算法的基本流程，以開(kāi)源內(nèi)核opencascade為例，主要包括：

 通過(guò)其中分析mesh算法的繼承關(guān)系，我們可以看到具體執(zhí)行的是Delaunay算法模塊。

  ??德勞內(nèi)三角化：

Delaunay指的是鮑里斯.尼古拉耶維奇.德勞內(nèi)（1890-1980），他不僅是沙俄/蘇聯(lián)時(shí)代偉大的數(shù)學(xué)家，更是一位很厲害的登山家，屬于“文體兩開(kāi)花”的模范人物。

1934年，德勞內(nèi)在其論文中提出一種思想，即存在一種剖分 DT(P) ,平面上給定的點(diǎn)集P，使得在 P 中沒(méi)有點(diǎn)嚴(yán)格處于 DT(P) 中任意一個(gè)三角形外接圓的內(nèi)部。這也就是大名鼎鼎的“德勞內(nèi)三角化”。

Delaunay三角化幾乎是后世所有mesh算法的基礎(chǔ)，不管是后來(lái)的Lawson算法還是Bowyer-Watson算法，都是對(duì)Delaunay三角化的一種繼承和發(fā)展。

Delauney算法能生成質(zhì)量不錯(cuò)的網(wǎng)格，主要基于以下兩點(diǎn)：

• 空?qǐng)A特性

Delaunay三角網(wǎng)格中的任意四點(diǎn)不能共圓，任一三角形的外接圓范圍內(nèi)不會(huì)有其它點(diǎn)存在，所以嚴(yán)格意義上的Delaunay三角網(wǎng)格具有唯一性。

最大化最小角

在散點(diǎn)集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大，三角面片的縱橫比和最大拐角也會(huì)得到盡可能的優(yōu)化。由于盡可能降低了最小角度，使得mesh算法中出現(xiàn)尖銳的silver angle的數(shù)量盡可能少。silver angle數(shù)量越少，插值算法由于受極值的影響可能性越少，表現(xiàn)越好。

三角剖分的基本流程

1. 生成已連接若干點(diǎn)離散點(diǎn)的三角網(wǎng)格

2. 在三角網(wǎng)格中加入一個(gè)新的點(diǎn)P

3. 找到所有外接圓中包含P 的三角形，剔除這些三角形并形成空腔

4. 空腔中當(dāng)前存在的所有點(diǎn)與點(diǎn)P 連接，形成新的三角網(wǎng)格

5. 刷新網(wǎng)格數(shù)據(jù)，并返回第二步繼續(xù)執(zhí)行直到所有點(diǎn)的插入

6. 

7. 
   

???? 從內(nèi)部點(diǎn)突破 ????

到這里，我們都清楚了mesh算法中影響mesh內(nèi)部頂點(diǎn)排布的過(guò)程是Discreze Face中的Delaunay剖分。那么是否參考edge discrete中邊界采樣點(diǎn)一樣，可以通過(guò)參數(shù)調(diào)整角誤差和線(xiàn)性誤差優(yōu)化最后的排布情況呢？

??很幸運(yùn)，我們找到了。

內(nèi)部點(diǎn)線(xiàn)性誤差和角度誤差圖示。和邊界點(diǎn)不同的是，內(nèi)部點(diǎn)的角度誤差研究的是三個(gè)頂點(diǎn)的法向量。

??在拍立得模型上稍作嘗試了一下，效果非常nice～

左側(cè)為原始效果，右側(cè)為加入內(nèi)部點(diǎn)優(yōu)化后的效果

并且我們發(fā)現(xiàn)，在設(shè)置了適宜的內(nèi)部點(diǎn)參數(shù)的情況下，邊界點(diǎn)線(xiàn)性誤差可放得很寬（0.01->0.1），這就大大降低了最終的面片數(shù)量！

???? 批量驗(yàn)證 ????

為了驗(yàn)證內(nèi)部點(diǎn)優(yōu)化mesh算法的策略是否具有普適性，我們準(zhǔn)備了涵蓋不同大小的37個(gè)step模型（其中最大174.76MB，最小0.381MB）和18個(gè)iges模型作為測(cè)試集，研究了不同內(nèi)部點(diǎn)優(yōu)化參數(shù)組合對(duì)面片數(shù)量的影響。

其中，網(wǎng)格數(shù)量減少百分比=（原算法面片數(shù)-內(nèi)部點(diǎn)優(yōu)化方法面片數(shù)）/（原算法面片數(shù)）

圖例數(shù)字代表具體參數(shù)

從上述數(shù)據(jù)不難看出，參數(shù)設(shè)置合適的情況下，測(cè)試集三角面片數(shù)量均有不同程度的下降，最高減少了90%。

為了檢查優(yōu)化前后模型渲染是否存在過(guò)大的差異，我們選擇其中43個(gè)模型，使用圖像對(duì)比的工具計(jì)算驗(yàn)證。結(jié)論是，優(yōu)化前后模型圖像相似度可以達(dá)到99%以上，人眼幾乎看不出兩者之間的差異。

綜上，通過(guò)合理調(diào)整內(nèi)部點(diǎn)線(xiàn)性誤差和角度誤差參數(shù)，可以在保證圖形正確渲染的同時(shí)，降低加載的面片數(shù)量，從而提高渲染的效率，完成mesh算法的進(jìn)化。

四、結(jié)束語(yǔ)

機(jī)械從來(lái)不是一件隨便的事。

EverCraft技術(shù)團(tuán)隊(duì)在追求極致體驗(yàn)的道路上始終如一，助力用戶(hù)設(shè)計(jì)更美好的未來(lái)！

如果您想了解更多關(guān)于機(jī)械圖紙管理協(xié)作軟件相關(guān)知識(shí)訊息，可搜索關(guān)注公眾號(hào)：追光幾何。關(guān)注追光幾何回復(fù)【模型】還能免費(fèi)獲取3D模型圖哦~更多精彩內(nèi)容，等你來(lái)看！