本博客內(nèi)容來源于網(wǎng)絡(luò)以及其他書籍，結(jié)合自己學(xué)習(xí)的心得進(jìn)行重編輯，因為看了很多文章不便一一標(biāo)注引用，如圖片文字等侵權(quán)，請告知刪除。

傳統(tǒng)2D計算機(jī)視覺學(xué)習(xí)筆記目錄------->傳送門
傳統(tǒng)3D計算機(jī)視覺學(xué)習(xí)筆記目錄------->傳送門

前言

前些天，發(fā)現(xiàn)簡書暫停一個月的文章發(fā)布，這一周多也就沒寫什么，正好公司需要優(yōu)化一下當(dāng)前正在使用的網(wǎng)格簡化，加之之前確實了解了一些網(wǎng)格簡化的方法，但是一直沒有整理。要是突然被問用什么方法，有什么優(yōu)缺點還真說不上來，所以在此成文記錄一下我所了解的網(wǎng)格簡化以及網(wǎng)格近似的方法，并與大家分享。（終于可以發(fā)存貨了）

網(wǎng)格簡化近似

首先我們來說明一下什么是網(wǎng)格簡化？

大量網(wǎng)格原圖

簡化后少量網(wǎng)格圖

上圖用了幾十萬個三角型來表達(dá)一個沙發(fā)，而下圖只用了幾百個三角形，這個簡化是有點夸張，但也基本上表達(dá)出了一個沙發(fā)，當(dāng)然細(xì)節(jié)不如大量的三角面。

那么為什么要進(jìn)行網(wǎng)格簡化呢？

進(jìn)行網(wǎng)格簡化的原因大概有幾個方面：

1. 節(jié)省存儲空間
   每個三角面在空間儲存的大小是一樣的，減少三角面的數(shù)目，就減少了模型保存的文件大小，如果進(jìn)行網(wǎng)絡(luò)傳輸則大大縮短網(wǎng)絡(luò)傳輸時間。
2. 簡化后續(xù)處理步驟
   如果后續(xù)要對模型進(jìn)行一些計算，例如貼紋理，在最終效果基本上不變的情況下，計算時間會大量的縮短。
3. 節(jié)省渲染時間
   當(dāng)我們想要顯示模型的時候，需要對模型的每個三角面進(jìn)行空間渲染，需要大量的計算，三角面的數(shù)目減少，在不影響顯示效果的情況下，會大大的減少渲染計算的負(fù)擔(dān)。對于一個500MB的模型，一般4G內(nèi)存的顯卡就已經(jīng)能感覺到卡頓了。所以如果玩高逼真的主機(jī)游戲還是需要非常厲害的顯卡的。
4. 去除不需要不關(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)格簡化近似方法，大概分為以下四類：

• 頂點聚類算法
  頂點聚類的基本思想就是，將模型頂點，無論按照晶格劃分還是相近關(guān)系，將頂點進(jìn)行聚類，屬于同一類的頂點，由一個新的頂點進(jìn)行替換。

  頂點聚類算法擁有很高的效率和魯棒性(Robust)，算法的復(fù)雜度是線性的。其缺點在于生成網(wǎng)格的質(zhì)量不是特別令人滿意。

• 增量式刪除算法
  典型的就是QEM(Quadric Error Mactrics，二次誤差測度)模型簡化算法（后續(xù)單獨(dú)文章描述）
  具體的操作方法：頂點刪除(Vertex removal)法、邊坍塌(Edge Collapse)法和三角面片坍塌(Triangle collapse)法

• 重采樣算法

  重采樣算法也是一個比較常用的算法?；痉椒ň褪牵诰W(wǎng)格曲面上選擇新的采樣頂點，通過連接這些頂點，能夠構(gòu)建出一個新的網(wǎng)格。

  使用重采樣算法的主要目的是在于，通過重采樣我們能夠獲得想要的網(wǎng)格連接結(jié)構(gòu)。不過其主要的缺點在于，如果采樣模式與網(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)缺點，比如VSA從全局進(jìn)行優(yōu)化，得到的模型較好，但是時間較長，不能用于在線系統(tǒng)。

上面幾種具體的算法基本上都需要一篇文章才能講明白，接下來，來解釋一下增量式刪除的三種基本刪除方法

基本刪除方法詳解

• 頂點刪除法

刪除網(wǎng)格中的一個頂點，然后對它相鄰三角形形成的空洞，進(jìn)行三角刨分

• 邊坍塌（折疊）法

將網(wǎng)格里面的一條邊壓縮為一個頂點，退化了該邊相鄰的兩個三角形

• 三角面片坍塌（折疊）法

如圖，將網(wǎng)格內(nèi)的一個面片收縮為一個頂點，退化了該面片以及臨邊的三個面片

總結(jié)

本文簡單的介紹了有關(guān)網(wǎng)格簡化的概念，以及列舉了網(wǎng)格簡化近似的一些方法。網(wǎng)格簡化作為計算機(jī)圖形學(xué)中一個重要的部分，免不了大量的數(shù)學(xué)計算，并且因為涉及到圖的拓?fù)浣Y(jié)構(gòu)，代碼也較為復(fù)雜。

接下來，會獨(dú)立來詳細(xì)的描述每一種網(wǎng)格簡化的方法，希望自己能把這些解釋清楚。

重要的事情說三遍：

如果您看到我的文章對您有所幫助，那就點個贊唄 ( * ^ __ ^ * )

如果您看到我的文章對您有所幫助，那就點個贊唄( * ^ __ ^ * )

如果您看到我的文章對您有所幫助，那就點個贊唄( * ^ __ ^ * )

傳統(tǒng)2D計算機(jī)視覺學(xué)習(xí)筆記目錄------->傳送門
傳統(tǒng)3D計算機(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)工作。