posts - 422, comments - 576, trackbacks - 0, articles - 0

Triangle - Delaunay Triangulator

Posted on 2014-03-29 16:43 eryar 阅读(8936) 评论(17)  编辑 收藏 引用 所属分类: 2.OpenCASCADE


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三角剖分算法和网格生成算法的重要性及广泛应用。

wps_clip_image-6384

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有很多开关,可以选择三角剖分和生成网格的方式,如下图所示:

wps_clip_image-16944

Figure 2.1 Options for the Triangle

如对示例文件box.poly进行三角剖分,使用命令及生成结果统计信息如下所示:

wps_clip_image-27287

Figure 2.2 Triangle Usage

出现统计信息的同时也生成了一些文件,如顶点文件box.1.node和三角形文件box.1.ele,如下图所示:

wps_clip_image-2721

Figure 2.3 Nodes and Triangles data generated by Triangle

wps_clip_image-3509

Figure 2.4 Triangulation Mesh Generated by Triangle[-pc]

wps_clip_image-3599

Figure 2.5 Triangulation Mesh Generated by Triangle[-pqc]

3. Displaying Meshes

在下载的程序中有用于显示网格的示例程序showme.c,不过只能用于Unix操作系统,不能用于Windows。

wps_clip_image-5805

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的网格:

wps_clip_image-11392

Figure 3.2 Generate Smiley Face Mesh by Triangle [-pc]

wps_clip_image-13806

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

 

Feedback

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2014-05-04 10:58 by Mr Li
我正在研究这个三角剖分的源码

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2014-05-04 15:42 by eryar
厉害!

@Mr Li

# re: Triangle - Delaunay Triangulator[未登录]  回复  更多评论   

2014-05-19 14:46 by D
怎么在tcl语言中呢

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2014-05-20 21:30 by eryar
这个可以参考netgen,
@D

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2015-01-14 15:20 by 付振宇
楼主你好,我运行Triangle之后,结果确实产生了一系列的开关选择项,但结果的最后一行却是“press any key to continue”,直接不给我选择开关的 机会程序就结束了,请问怎么才能选择这些开关呢?

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2015-01-14 18:17 by eryar
@付振宇
Hi 付振宇,

你好!

Triangle的用法请参考Figure 2.2 Triangle Usage 中红色线框中的部分。
各开关的用法请仔细看Figure 2.1 Options for the Triangle其说明。

Best Regards,
Shing Liu

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2015-01-15 14:14 by 付振宇
@eryar
感谢博主,我现在明白了,原来是在命令提示符里运行源程序编译产生的exe文件和相应的开关指令,而并非在Visual c++里运行。

可是为什么产生的结点坐标和单元信息文件的后缀名是.node和.ele呢,能否通过修改源程序让它们都为.txt文件,然后再编写一段c++程序读出这些信息,画出网格剖分图?

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2015-01-15 17:55 by eryar
@付振宇

生成的文件后缀名没有什么关系的,对于程序来说都是文本文件,自己写程序直接读数据都可以了。

有些程序可以用来显示Triangle生成的这些文件,加个后缀好分辨文件中保存的数据。

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2015-03-10 15:03 by 付振宇
@eryar
博主您好,我想用源文件夹中的tricall.c来调用triangle,于是在triangle.c中定义了#define TRILIBRARY,并把tricall.c添加到工作空间来,可是编译的时候总是报错,问题就出在头文件triangle.h中的一行奇怪代码上
“#include "triangle.h"
给出的错误提示貌似是说出现了循环调用,于是我就把“#include "triangle.h"给删除了,然后再编译,这下一编译更不得了,出现了几十个语法错误。

请问这到底是怎么回事,为什么triangle.h要自己引用自己,怎么解决这个问题?

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2015-03-10 19:21 by eryar
@付振宇
Hi 付振宇,

你好!

请仔细看看这段话:

~~~~~~~~~~~~~~~~~~~~~~~~~
下载到源程序后,如果是Windows操作系统,还需要在triangle.h之前做些配置,如定义以下几个宏:
#define REAL double
#define ANSI_DECLARATORS
#include "triangle.h"
#undef REAL

在triangle.c中定义宏:#define NO_TIMER。有了上面的宏定义,可以编译出一个triangle.exe程序了。如果要将triangle用在自己的程序中,还需要定义#define TRILIBRARY。
~~~~~~~~~~~~~~~~~~~~~~~~~~
这些内容加在tricall.c中,再编译试试看。

你可以看看makefile,里面有些选项的。

Best Regards,
Shing Liu

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2015-03-10 20:02 by 付振宇
@eryar
您的意思是在triangle.h中定义宏:
#define REAL double
#define ANSI_DECLARATORS

在triangle.c中定义宏:
#define NO_TIMER
#define TRILIBRARY


至于那个” #include "triangle.h" “ ,我发现在tricall.c中已经有了,就不用再添加了吧。

按照上面的做法,最终运行成功了。

我之前是把下面的代码都添加到了triangle.h中,才报错的。
#define REAL double
#define ANSI_DECLARATORS
#include "triangle.h"
#undef REAL

谢谢啦!

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2015-03-11 19:30 by eryar
@付振宇

运行成功就好。

不客气。

# re: Triangle - Delaunay Triangulator[未登录]  回复  更多评论   

2015-07-30 21:40 by LI
楼主您好,我想知道调用Triangle中 triangulateio 里面定义的
REAL *pointattributelist;
int *pointmarkerlist;
int numberofpointattributes;

int *trianglelist;
REAL *triangleattributelist;
REAL *trianglearealist;
int *neighborlist;
int numberoftriangles;
int numberofcorners;
int numberoftriangleattributes;*/

int *segmentlist;
int *segmentmarkerlist;
int numberofsegments;
REAL *holelist;
int numberofholes;

REAL *regionlist;
int numberofregions;

int *edgelist;
int *edgemarkerlist;
REAL *normlist;
int numberofedges;

这些都是什么意思,要控制三角形的最小角和面积应该怎么设置参数???
谢谢!
网上关于这些介绍比较少,望楼主帮忙,谢谢了!!

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2015-07-30 22:52 by eryar
@LI

你好!

那些参数是三角剖分的输入数据。

控制剖分行为的参数设置是在结构体behavior中:
/* Data structure for command line switches and file names. This structure */
/* is used (instead of global variables) to allow reentrancy. */

struct behavior {

/* Switches for the triangulator. */
/* poly: -p switch. refine: -r switch. */
/* quality: -q switch. */
/* minangle: minimum angle bound, specified after -q switch. */
/* goodangle: cosine squared of minangle. */
/* vararea: -a switch without number. */
/* fixedarea: -a switch with number. */
/* maxarea: maximum area bound, specified after -a switch. */
/* usertest: -u switch. */
/* regionattrib: -A switch. convex: -c switch. */
/* weighted: 1 for -w switch, 2 for -W switch. jettison: -j switch */
/* firstnumber: inverse of -z switch. All items are numbered starting */
/* from `firstnumber'. */
/* edgesout: -e switch. voronoi: -v switch. */
/* neighbors: -n switch. geomview: -g switch. */
/* nobound: -B switch. nopolywritten: -P switch. */
/* nonodewritten: -N switch. noelewritten: -E switch. */
/* noiterationnum: -I switch. noholes: -O switch. */
/* noexact: -X switch. */
/* order: element order, specified after -o switch. */
/* nobisect: count of how often -Y switch is selected. */
/* steiner: maximum number of Steiner points, specified after -S switch. */
/* incremental: -i switch. sweepline: -F switch. */
/* dwyer: inverse of -l switch. */
/* splitseg: -s switch. */
/* nolenses: -L switch. docheck: -C switch. */
/* quiet: -Q switch. verbose: count of how often -V switch is selected. */
/* usesegments: -p, -r, -q, or -c switch; determines whether segments are */
/* used at all. */
/* */
/* Read the instructions to find out the meaning of these switches. */

int poly, refine, quality, vararea, fixedarea, usertest;
int regionattrib, convex, weighted, jettison;
int firstnumber;
int edgesout, voronoi, neighbors, geomview;
int nobound, nopolywritten, nonodewritten, noelewritten, noiterationnum;
int noholes, noexact, nolenses;
int incremental, sweepline, dwyer;
int splitseg;
int docheck;
int quiet, verbose;
int usesegments;
int order;
int nobisect;
int steiner;
REAL minangle, goodangle;
REAL maxarea;

/* Variables for file names. */

#ifndef TRILIBRARY
char innodefilename[FILENAMESIZE];
char inelefilename[FILENAMESIZE];
char inpolyfilename[FILENAMESIZE];
char areafilename[FILENAMESIZE];
char outnodefilename[FILENAMESIZE];
char outelefilename[FILENAMESIZE];
char outpolyfilename[FILENAMESIZE];
char edgefilename[FILENAMESIZE];
char vnodefilename[FILENAMESIZE];
char vedgefilename[FILENAMESIZE];
char neighborfilename[FILENAMESIZE];
char offfilename[FILENAMESIZE];
#endif /* not TRILIBRARY */

}; /* End of `struct behavior'. */

最小角看字面应该是:minangle
最大面积是:maxarea

Best Regards,
Shing Liu

# re: Triangle - Delaunay Triangulator[未登录]  回复  更多评论   

2015-08-03 13:30 by LI
@eryar
谢谢您的答复!
但是我还有一些疑问,写在给您的邮件中,期待您的回复!
谢谢!

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2015-08-04 21:26 by eryar
@LI
不客气。

建议你还是先把triangle编译出一个exe,仔细看看相关命令选项,
如"-a"就可以设置最大面积约束;

再把你的数据放到文件中,再用那个exe程序带不同的选项来试试看。

# re: Triangle - Delaunay Triangulator  回复  更多评论   

2016-03-17 09:34 by 王亚辉
@付振宇
您好,请问您的“press any key to continue”问题是怎么解决的呢?

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理