本博客內(nèi)容來源于網(wǎng)絡(luò)以及其他書籍逮矛，結(jié)合自己學(xué)習(xí)的心得進(jìn)行重編輯窑滞，因?yàn)榭戳撕芏辔恼虏槐阋灰粯?biāo)注引用，如圖片文字等侵權(quán)电爹，請告知刪除蔫仙。
傳統(tǒng)2D計(jì)算機(jī)視覺學(xué)習(xí)筆記目錄------->傳送門
傳統(tǒng)3D計(jì)算機(jī)視覺學(xué)習(xí)筆記目錄------->傳送門
前言
前些天，發(fā)現(xiàn)簡書暫停一個月的文章發(fā)布丐箩，這一周多也就沒寫什么摇邦，正好公司需要優(yōu)化一下當(dāng)前正在使用的網(wǎng)格簡化，加之之前確實(shí)了解了一些網(wǎng)格簡化的方法屎勘，但是一直沒有整理施籍。要是突然被問用什么方法，有什么優(yōu)缺點(diǎn)還真說不上來概漱，所以在此成文記錄一下我所了解的網(wǎng)格簡化以及網(wǎng)格近似的方法丑慎，并與大家分享。（終于可以發(fā)存貨了）
網(wǎng)格簡化近似
首先我們來說明一下什么是網(wǎng)格簡化瓤摧？
所謂網(wǎng)格簡化竿裂，就是將大量的三角形網(wǎng)格簡化為少量的三角形或者將大量的多邊形簡化為少量的多邊形來近似表達(dá)模型的空間形狀。如下圖：
上圖用了幾十萬個三角型來表達(dá)一個沙發(fā)照弥，而下圖只用了幾百個三角形铛绰，這個簡化是有點(diǎn)夸張，但也基本上表達(dá)出了一個沙發(fā)产喉，當(dāng)然細(xì)節(jié)不如大量的三角面捂掰。
那么為什么要進(jìn)行網(wǎng)格簡化呢敢会？
進(jìn)行網(wǎng)格簡化的原因大概有幾個方面：
- 節(jié)省存儲空間
每個三角面在空間儲存的大小是一樣的，減少三角面的數(shù)目这嚣，就減少了模型保存的文件大小鸥昏，如果進(jìn)行網(wǎng)絡(luò)傳輸則大大縮短網(wǎng)絡(luò)傳輸時間。 - 簡化后續(xù)處理步驟
如果后續(xù)要對模型進(jìn)行一些計(jì)算姐帚，例如貼紋理吏垮，在最終效果基本上不變的情況下，計(jì)算時間會大量的縮短罐旗。 - 節(jié)省渲染時間
當(dāng)我們想要顯示模型的時候膳汪，需要對模型的每個三角面進(jìn)行空間渲染，需要大量的計(jì)算九秀，三角面的數(shù)目減少遗嗽，在不影響顯示效果的情況下，會大大的減少渲染計(jì)算的負(fù)擔(dān)鼓蜒。對于一個500MB的模型痹换，一般4G內(nèi)存的顯卡就已經(jīng)能感覺到卡頓了。所以如果玩高逼真的主機(jī)游戲還是需要非常厲害的顯卡的都弹。 - 去除不需要不關(guān)心的細(xì)節(jié)部分
比如對于一面墻娇豫，墻上有一些小凹凸，但是對用使用者來說并不關(guān)系畅厢，更希望能夠刪除掉這些部分冯痢，來優(yōu)化視覺效果，網(wǎng)格簡化通常能夠達(dá)到這些效果框杜。
在了解到什么是網(wǎng)格簡化以及為什么要進(jìn)行網(wǎng)格簡化后系羞，那么什么時候一個好的網(wǎng)格簡化算法呢？
一個好的網(wǎng)格簡化算法霸琴，需要在這幾個方面進(jìn)行度量：
- 簡化后網(wǎng)格與初始網(wǎng)格的相似度椒振，越高越好
- 簡化到同等網(wǎng)格數(shù)，時間越短越好
- 在同等相似度下梧乘，網(wǎng)格數(shù)目越少越好
這幾個度量方式相互牽制澎迎，總體來說，就是在最短的時間內(nèi)簡化到網(wǎng)格數(shù)最少选调，并且模型相似度可以接受夹供。每種方法都有自己的優(yōu)劣，下面我們來看看常見的網(wǎng)格簡化算法有什么仁堪。
常見網(wǎng)格簡化近似方法
常見的網(wǎng)格簡化近似方法哮洽，大概分為以下四類：
-
頂點(diǎn)聚類算法
頂點(diǎn)聚類的基本思想就是，將模型頂點(diǎn)弦聂，無論按照晶格劃分還是相近關(guān)系鸟辅，將頂點(diǎn)進(jìn)行聚類氛什，屬于同一類的頂點(diǎn)，由一個新的頂點(diǎn)進(jìn)行替換匪凉。頂點(diǎn)聚類算法擁有很高的效率和魯棒性(Robust)枪眉，算法的復(fù)雜度是線性的。其缺點(diǎn)在于生成網(wǎng)格的質(zhì)量不是特別令人滿意再层。
增量式刪除算法
典型的就是QEM(Quadric Error Mactrics贸铜，二次誤差測度)模型簡化算法（后續(xù)單獨(dú)文章描述）
具體的操作方法：頂點(diǎn)刪除(Vertex removal)法、邊坍塌(Edge Collapse)法和三角面片坍塌(Triangle collapse)法-
重采樣算法
重采樣算法也是一個比較常用的算法聂受≥锴兀基本方法就是，在網(wǎng)格曲面上選擇新的采樣頂點(diǎn)蛋济，通過連接這些頂點(diǎn)棍鳖，能夠構(gòu)建出一個新的網(wǎng)格。
使用重采樣算法的主要目的是在于瘫俊，通過重采樣我們能夠獲得想要的網(wǎng)格連接結(jié)構(gòu)。不過其主要的缺點(diǎn)在于悴灵，如果采樣模式與網(wǎng)格區(qū)域沒有對齊扛芽，那么就會出現(xiàn)走樣，拓?fù)浣Y(jié)構(gòu)可能發(fā)生變化积瞒。對這個方法進(jìn)行優(yōu)化川尖，可以提前將網(wǎng)格根據(jù)其特征將其分割為不同的區(qū)域，比如區(qū)域都是凸包茫孔，不含有環(huán)狀的結(jié)構(gòu)等叮喳。
模型逼近算法
常見算法如：Variational Shape Approximation (VSA) （后續(xù)單獨(dú)文章介紹）
以上各種方法各有自己的優(yōu)缺點(diǎn)，比如VSA從全局進(jìn)行優(yōu)化缰贝，得到的模型較好馍悟，但是時間較長，不能用于在線系統(tǒng)剩晴。
上面幾種具體的算法基本上都需要一篇文章才能講明白锣咒，接下來，來解釋一下增量式刪除的三種基本刪除方法
基本刪除方法詳解
-
頂點(diǎn)刪除法
刪除網(wǎng)格中的一個頂點(diǎn)赞弥，然后對它相鄰三角形形成的空洞毅整，進(jìn)行三角刨分
-
邊坍塌（折疊）法
將網(wǎng)格里面的一條邊壓縮為一個頂點(diǎn)，退化了該邊相鄰的兩個三角形
-
三角面片坍塌（折疊）法
如圖绽左，將網(wǎng)格內(nèi)的一個面片收縮為一個頂點(diǎn)悼嫉，退化了該面片以及臨邊的三個面片
總結(jié)
本文簡單的介紹了有關(guān)網(wǎng)格簡化的概念，以及列舉了網(wǎng)格簡化近似的一些方法拼窥。網(wǎng)格簡化作為計(jì)算機(jī)圖形學(xué)中一個重要的部分戏蔑，免不了大量的數(shù)學(xué)計(jì)算蹋凝，并且因?yàn)樯婕暗綀D的拓?fù)浣Y(jié)構(gòu)，代碼也較為復(fù)雜辛臊。
接下來仙粱，會獨(dú)立來詳細(xì)的描述每一種網(wǎng)格簡化的方法，希望自己能把這些解釋清楚彻舰。
重要的事情說三遍：
如果您看到我的文章對您有所幫助伐割，那就點(diǎn)個贊唄 ( * ^ __ ^ * )
如果您看到我的文章對您有所幫助，那就點(diǎn)個贊唄( * ^ __ ^ * )
如果您看到我的文章對您有所幫助刃唤，那就點(diǎn)個贊唄( * ^ __ ^ * )
傳統(tǒng)2D計(jì)算機(jī)視覺學(xué)習(xí)筆記目錄------->傳送門
傳統(tǒng)3D計(jì)算機(jī)視覺學(xué)習(xí)筆記目錄------->傳送門
任何人或團(tuán)體隔心、機(jī)構(gòu)全部轉(zhuǎn)載或者部分轉(zhuǎn)載、摘錄尚胞，請保留本博客鏈接或標(biāo)注來源硬霍。博客地址：開飛機(jī)的喬巴
作者簡介：開飛機(jī)的喬巴（WeChat：zhangzheng-thu），現(xiàn)主要從事機(jī)器人抓取視覺系統(tǒng)以及三維重建等3D視覺相關(guān)方面笼裳，另外對slam以及深度學(xué)習(xí)技術(shù)也頗感興趣唯卖，歡迎加我微信或留言交流相關(guān)工作。
