Triangle - Delaunay Triangulator
<a href="mailto:[email protected]">[email protected]</a>
Abstract. Triangle is a 2D quality mesh generator and Delaunay triangulator. Triangle was created as part of the Quake project in the school of Computer Science at Carnegie Mellon University by Jonathan R. Shewchuk. Triangle is a small C program and its Delaunay refinement algorithm for quality mesh generation is a hybrid one. It includes divide-and-conquer and incremental insertion algorithms and sweepline Delaunay triangulation algorithm. This paper is focused on the usage of the Triangle and visualization the triangulation result in OpenSceneGraph.
Key words. Triangle, Delaunay Triangulator, Mesh Generator
1. Introduction
Triangle可以生成精确的Delaunay三角剖分，限定Delaunay三角剖分（Constrained Delaunay Triangulation），Conforming Delaunay Triangulation，Voronoi圖（Voronoi Diagrams）和高品質的三角網格，即生成的網格中沒有瘦長的三角形，是以适用于有限元分析（Finite Element Analysis）。
在OpenCascade6.2.0版本之前，OpenCascade中網格的生成就是使用了這個開源庫，由此可見Delaunay三角剖分算法和網格生成算法的重要性及廣泛應用。
Figure 1.1 Triangle - A 2D Quality Mesh Generator and Delaunay Triangulator
下載下傳Triangle的源程式及更多與Triangle相關資訊的網址如下所示：
<a href="http://www.cs.cmu.edu/~quake/triangle.html">http://www.cs.cmu.edu/~quake/triangle.html</a>
下載下傳到源程式後，如果是Windows作業系統，還需要在triangle.h之前做些配置，如定義以下幾個宏：
#define REAL double
#define ANSI_DECLARATORS
#include "triangle.h"
#undef REAL
在triangle.c中定義宏：#define NO_TIMER。有了上面的宏定義，可以編譯出一個triangle.exe程式了。如果要将triangle用在自己的程式中，還需要定義#define TRILIBRARY。更多宏定義可以參考源程式。
2. Triangle Usage
Triangle有很多開關，可以選擇三角剖分和生成網格的方式，如下圖所示：
Figure 2.1 Options for the Triangle
如對示例檔案box.poly進行三角剖分，使用指令及生成結果統計資訊如下所示：
Figure 2.2 Triangle Usage
出現統計資訊的同時也生成了一些檔案，如頂點檔案box.1.node和三角形檔案box.1.ele，如下圖所示：
Figure 2.3 Nodes and Triangles data generated by Triangle
Figure 2.4 Triangulation Mesh Generated by Triangle[-pc]
Figure 2.5 Triangulation Mesh Generated by Triangle[-pqc]
3. Displaying Meshes
在下載下傳的程式中有用于顯示網格的示例程式showme.c，不過隻能用于Unix作業系統，不能用于Windows。
Figure 3.1 Displaying the Meshes by ShowMe
為了在Windows作業系統中看到生成的網格，用OpenSceneGraph編寫了一個小程式TriangleViewer顯示網格。其中讀取node和element檔案中資料的主要程式片段如下所示：
std::string TriangleMesh::ReadLine(std::ifstream &theFile)
{
std::string theBuffer;
bool IsReadNextLine = false;
do
{
getline(theFile, theBuffer);
// skip comment here.
if ('#' == theBuffer[0])
{
IsReadNextLine = true;
}
else
IsReadNextLine = false;
}
while (IsReadNextLine);
return theBuffer;
}
void TriangleMesh::BuildMesh(const std::string& aPolyFile)
std::stringstream ss;
std::string theNodeFileName(aPolyFile + ".node");
std::string theElementFileName(aPolyFile + ".ele");
std::ifstream theNodeFile(theNodeFileName.c_str());
std::ifstream theElementFile(theElementFileName.c_str());
Standard_Integer theIndex = 0;
Standard_Integer theNodeCount = 0;
Standard_Integer theTriangleCount = 0;
Standard_Integer theIndex1 = 0;
Standard_Integer theIndex2 = 0;
Standard_Integer theIndex3 = 0;
Standard_Real x = 0.0;
Standard_Real y = 0.0;
// Read mesh size.
ss << ReadLine(theNodeFile);
ss >> theNodeCount;
ss.str("");
ss.clear();
ss << ReadLine(theElementFile);
ss >> theTriangleCount;
mMesh = new Poly_Triangulation(theNodeCount, theTriangleCount, Standard_True);
// Read nodes information.
TColgp_Array1OfPnt2d& theNodes2d = mMesh->ChangeUVNodes();
for (Standard_Integer n = 1; n <= theNodeCount; ++n)
ss.str("");
ss.clear();
ss << ReadLine(theNodeFile);
ss >> theIndex >> x >> y;
theNodes2d.SetValue(theIndex, gp_Pnt2d(x, y));
// Read triangles information.
Poly_Array1OfTriangle& theTriangles = mMesh->ChangeTriangles();
for (Standard_Integer t = 1; t <= theTriangleCount; ++t)
ss << ReadLine(theElementFile);
ss >> theIndex >> theIndex1 >> theIndex2 >> theIndex3;
theTriangles.SetValue(theIndex, Poly_Triangle(theIndex1, theIndex2, theIndex3));
如下圖所示為顯示一個用不同指令生成的Smiley Face的網格：
Figure 3.2 Generate Smiley Face Mesh by Triangle [-pc]
Figure 3.3 Generate Smiley Face Mesh by Triangle [-pqc]
從上面兩幅圖中的網格可知，下面圖中的網格品質較高，為去掉了瘦長的三角形而增加了一些頂點。
4. Conclusions
在給Triangle程式輸入資料時，頂點Vertex資料很好了解，隻是一些二維點，但是如果加上開孔Hole後有些問題。後來才知道，需要在Poly檔案中的Segments部分輸入與孔相關線段形成的閉合區域，在孔Hole部分隻需要輸入位于孔中的任意一個點即可。
将Triangle生成的結果可視化，可以看到Triangle生成的網格，友善看到Triangle的不同選項生成的網格效果。
在OpenCascade6.2.0版本中，就以此二維Delaunay三角剖分工具為基礎，實作了任意三維曲面的三角剖分，進而對其可視化。是以學習Triangle的用法，結合OpenCascade的源程式便于了解任意曲面的可視化實作的方法。
對Delaunay三角剖分算法感興趣的讀者，可以參考相關書籍[3],[4],[5],[6]。
5. References
2. Jonathan R. Shewchuk, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangualtor, Springer-Verlag, Berlin, 1996
3. 汪嘉業 王文平 屠長河 楊承磊. 計算幾何及應用. 科學出版社. 2011
4. 王成恩. 面向科學計算的網格劃分與可視化技術. 科學出版社. 2011
5. 周培德. 計算幾何－算法設計與分析. 清華大學出版社. 2008
6. Berg M D著 鄧俊輝譯. 計算幾何－算法與應用. 清華大學出版社. 2009