如何將常規高度網格轉換爲三角形不規則網絡？

Question

我正在尋找一種將高度規則網格（例如1024x1024）轉換爲三角形不規則網絡的算法。這裏是表示不規則三角網的一例的印象：

我看着在互聯網的算法將其轉換，但我只是找不到一個。基本上三角形的密度取決於粗糙度和/或像素誤差（光柵化時）或類似的東西。

Answer 1

這裏有一個兩步算法的思路：先做一個基於粗糙網格的Delaunay三角網，然後遞歸地平滑三角形，直到達到某個誤差標準。

第一步，確定Delaunay三角剖分的一組頂點。這些頂點與像素座標一致。極限點要麼高於要麼低於全部四個相鄰像素，因此應該在邊界上相鄰像素較低或較高邊界上的脊點上。這應該會產生粗糙的三角形網格。您還可以通過包含高曲率的像素來獲得更精細的網格。

第二步，遍歷所有三角形。沿像素網格掃描三角形，併爲三角形內的每個像素累積誤差平方，並識別最大和最小符號誤差點。如果每個像素的平均誤差不符合您的標準，請將最低和最高誤差點添加到您的三角測量中。驗證新的三角形並根據需要重新進行三角測量。

備註：

步驟1中的粗略三角測量應該相當快。如果高度圖是粗糙的，則可能在粗糙區域中出現太多頂點。在這種情況下，在應用算法之前，可以使用高斯濾波器對高圖進行平滑處理。

遞歸重新三角化可能不是那麼快，因爲確定錯誤需要反覆掃描三角形。 （當三角形尺寸減小時，該過程應該會更快，但仍然會更快。）在步驟1中找到頂點的一個好的標準可能會加快步驟2.

您可以通過查找像素的邊界框來掃描三角形。找出邊界框左下角的重心座標s，t以及對應於像素在x和y方向移動的重心增量（dsx，dtx）和（dsy，dty）。然後，您可以在包含的像素（x，y）上以兩個循環掃描邊界框，根據delta矢量計算重心座標（s，t），並在三角形內部累加誤差，即當s> 0時， t> 0和s + t < 1.

我還沒有實現這個算法（但它是一個有趣的任務），但我想在速度和網格質量之間找到一個很好的平衡是一個剪裁錯誤的問題標準和頂點選擇到當前高度圖。