Triangle - Delaunay Triangulator
eryar@163.com
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相關信息的網址如下所示：
http://www.cs.cmu.edu/~quake/triangle.html
下載到源程序后，如果是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.str("");
ss.clear();
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
1. Jonathan R. Shewchuk. Triangle: http://www.cs.cmu.edu/~quake/triangle.html
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