tetgen手册

Tetgen可以用来产生四面体网并且遵守格德洛内规则，四面体网格对有限元和有限体积法是非常有用的。这个算法在当前研究领域具有领先水平。文档简洁的介绍了一些可以被tetgen解决的问题，是一个非常详细用户指南。读者从中不仅可以了解到怎样直接使用来自命令行的输入文件去产生四面体网格，而且还可以了解其他程序怎样调用tetgen关键词：四面体网格，Delaunay四面体化，有约束的Delaunay四面体化，网格质量，网格产生内容1、介绍1.1Delaunay三角形与空间多面体1.2有约束的Delaunay四面体化1.2.1分段线性复杂1.3四面体网格质量1.3.1半径边缘比质量衡量标准2、入门指南2.1编译2.1.1unix/linux2.1.2windows9x/NT/2000/xp2.2测试2.3可视化2.3.1tetview2.3.2其他的网格可视化工具3、Tetgen使用3.1命令行语法3.2命令行开关3.2.1–p对一个PLC进行四面体化3.2.2-q网格生成质量3.2.3-a规定有限元3.2.2-A分配区域属性3.2.2-r重构或优化网格3.2.2-i插入一个点3.2.2-T设置公差3.2.2-Y边界禁止steiner点3.2.2其他开关命令3.3命令行举例3.3.1产生Delaunay四面体3.3.2产生带约束的Delaunay四面体3.3.3网格质量、网格大小控制4、文件格式4.1tetgen文件格式4.1.1.nodes文件4.1.2.poly文件4.1.3.smeshs文件4.1.4.ele文件4.1.5.face文件4.1.6.edges文件4.1.7.vol文件4.1.8.var文4.1.9.neigh文件4.2支持文件格式4.2.1.off4.2.2.ply4.2.3.stl4.2.4.mesh4.3文件格式举例4.3.1带两个边界标识的空间多面体4.3.2带两个区域的空间多面体5、其他程序调用tetgen5.1头文件5.2调用方法5.3tetgenio数据类型5.4数据描述5.4.1内存管理5.4.2facet数据结构5.5举例一些相关的扩展引用1、介绍Tetgen程序可以对三维物体进行四面体剖分。Tetgen的目的是为数值模拟产生合适的四面体网格，其中数值模拟有用到有限元和有限体积法。不仅如此，tetgen作为一个四面体网格生成器，它在许多科学与工程应用中也常被用来作为一个网格化组件。对于一个三维区域，它是由它的边界定义的（如表面网格文件）。Tetgen可以对这样一个有边界约束的区域进行四面体剖分，并且符合delaunay规则和网格质量标准。后者是恰好是线变，并且对产生的所有四面体的外接球半径与其最小边的比率是有限制的。对于一个三维域点集，tetgen可以对其进行delaunay四面体剖分，并且产生凸壳。Tetgen是的代码是用C++写的，这些代码可以被编译成直接执行的程序或者是集成到其他应用程序的库。Tetgen支持所有主流的操作系统，比如unix/linux，macos，windows系列等。tetgen使用的算法符合delaunay准则。这一章节的其他内容对用tetgen解决的网格问题作了一些简单描述，对Tetgen的算法实现也作了一些描述，有兴趣的读者参考文档给出的引用。然而，这些信息并不是对所有用户都真正有用，除了章节1.2.1和1.3.1，其他的部分浏览一下就可以了，章节1.2.1和1.3.1包含了一些解决问题的要点。点集的三角网划分（区别对待概念simplicialcomplex与simplex）三角形是基本的几何图形结构。点集V的一个三角形划分就是一个simplicialcomplex，这里称之为S，S包含的点可能只是点集V的一部分点，也可能是V的全部点，并且这里S的底部空间就是V的convexhull。对于一个点集，在它上面有许多不同的三角形划分，但毫无疑问，德洛内三角形划分是最好的一种。它的dual是点集的Voronoi图。德洛内三角形划分与Voronoi图有许多非常好的数学特性。它们在许多应用中被广泛使用。1.1Delaunay三角剖分法（点集的三角剖分）和凸壳点集的Delaunay三角形剖分法由Delaunay在1934年提出，它的许多有利的特性使得它成为一个非常有用的几何结构，它已经在高效的算法设计与实际的工程应用中被广泛应用。附录部分用来描述Delaunay三角剖分法，用户理解一些基本概念是非常有必要的，像凸壳，单形，单复形等。附录A提供了对这些基本概念简单的介绍假设V是ℝd中的一个点集，σ是点集V中的一个k-simplex(0≤k≤d)。这个σ的外接球包含了σ上所有点。如果K=d，σ有一个唯一的外接球，否则的话，σ就有无限的外接球。如果σ存在一个外接球，并且这个外接球没有包含点集V的其他顶点，这个simplex就是一个Delaunay。图1a展现了一个二维空间点集的delaunaysimplices。如果所有的simplices都是德洛内型，那么点集V的一个德洛内三角形划分（称之为D）就是一个simplicialcomplex，并且D的底部空间为点集V的convexhull。三维的德洛内三角形划分也叫德洛内四面体剖分。1.2约束Delaunay四面体剖分法约束德洛内四面体剖分就是把一个三维区域Ω划分成一个四面体网格，正如在表面网格呈现出来的边界∂Ω，总体来说，Ω可能在形状上是反复无常的变化，而且还很复杂，可能包含内边界（分割成不同的区域）和洞。这个问题也被称为边界网格生成或者边界整合。顶点集Ω的德洛内四面体剖分法没有必要符合这个∂Ω，由于∂Ω的面是非德洛内simplices（面片）。而约束德洛内四面体剖分法是一种变异的德洛内四面体剖分法，它需要遵守∂Ω规则。约束德洛内四面体剖分法（CDT）保持着德洛内四面体剖分法的许多特性。对于解决这类问题它们是再合适不过的结构了。为了简化一个算法的设计，我们可以假定认为∂Ω是一个三维空间多面体，也就是∂Ω是一个二维底层空间的单纯复形simplicalcomplex。更具体的说，∂Ω是一个三维空间顶点集和是一个多边形集。每一个多边形是一个带段边界约束的小平面。Tetgen使用了一个更通用的方法来表示∂Ω，它将在章节1.2.1分开介绍。下面关于CDT的定义是来源于shewchuk。点集V中的两个顶点p和q是可见的，但如果有一个约束的平面f，并且点p和q位于这个平面f的相反两边，pq之间的线段交叉与平面f（见图5），那么顶点p与q将变得不可见。由点集V的顶点形成的四面体t就是一个约束德洛内四面体，当然前提是它的外接球没有包含V的其他顶点，四面体t内的任何顶点都是可见的。像这样一个Ω空间的四面体T剖分被称作是约束四面体剖分，如果四面体T和空间Ω恰好有相同的顶点集，空间Ω的每一个多边形完全被四面体T的三角形面的集合所代替。T是∂Ω的四面体剖分，如果T是一个约束的四面体剖分并且T的每一个四面体都是约束德洛内四面体。直观地，对于约束德洛内四面体来说，德洛内四面体剖分和约束德洛内四面体剖分的定义是一样的，当球穿过一个约束的多边形时我们忽略了这个球队体积。注意在一个约束德洛内四面体剖分中，那些单形（四面体、三角形、边）并不总是德洛内型的构造一个德洛内四面体剖分是一种微妙的方式。一些多面体根本不能四面体剖分。图6中展示了两个例子。此外，ruppert和serdel展示了它是一个非完全多项式去决定一个简单的多面体是否能够被四面体剖分。尽管如此，每一个多面体是否能够被四面体剖分的条件是只要有额外的点被插入。德洛内四面体剖分算法是插入另外的顶点。当这些额外顶点是必须存在的时候，一个关键的问题是怎么样决定额外插入点的最佳数目。另一个要考虑的是，网格优化算法是怎么样去避免短边，这些短边将给非常小的四面体带来危险，因此，这些额外插入点的数目不应该太大。对于约束四面体网格剖分法来说，基于不同点插入方案的29,32,36,37,41方法是被提倡的。Shewchuk给出了一个条件确保四面体网格剖分的存在性，它对设计一个算法去构造四面体网格剖分法是非常有用。因为每一个空间多面体的多边形都是有分割边界的。一个要考虑的就是空间多面体所有的片段集。如果存在一个段s的外接球S，且没有多面体顶点集的其他顶点位于外接球S中，这个段s就是德洛内型。此外，如果没有空间中的其他顶点位于外接球内或位于外接球上，段s就是一个强德洛内型，并且这个空间多面体的德洛内四面体剖分就存在。这个条件是非常有用的，因为它表明额外的点唯一被插入到片段中。Tetgen算法的实现是被si和gartner给出的。这个算法扩展了在41中提出的片段恢复算法。这个算法和其他的约束德洛内四面体剖分[29,30,41]的主要区别是它实际的可利用性，一个强德洛内四面体剖分法的存在条件是它要求一个空间多面体顶点集没有局部的德洛内型。一个新的局部德洛内移除算法把顶点扰动和顶点插入结合起来构造一个新的顶点集，这个顶点集合空间多面体是一致的。在这个条件满足之后，一个实际的快速面片恢复算法用来构造这个德洛内四面体剖分。图7展示了二维模型中这个算法的主要思想。1.2.1分段线性复杂三维几何体对象一般是比多面体更复杂的。Tetgen库用一个非常广泛的输入叫做piecewiselinearcomplex（PLC），PLC是由miller，talmor，teng，walkington和wang定义的。一个PLCX是一个顶点，段，和小平面的的集合。每一个小平面都是多边形区域，在它里面它可能有许多面，也可能是非凸壳，可能还有洞，段，和顶点。一个小平面能够代表任何二维的笔直线性图形，这是一个非常流行的输入模型，许多二维网格算法使用都是这种模型。一个小平面实际上是一个二维的笔直线性图嵌入到三维中。图8给出了一个例子，阴影区域高亮了这个面。PLCs像其他复合体一样是有限制的。对于像XPLC，X的元素在内部区域里必须的闭合的。例如，两个分段只有在一个共同的顶点集并且这些点也是在X中才能交叉。X的两个面片只有在共享一个片段或者是一个顶点集或者是两个的集合时才可以相交。（因为小平面是非凸的）。图9展示了非闭合的配置的例子。PLCs的小平面的另一个限制是这些被用来定义小平面的顶点集必须是共面的。任何多面体都可以认为是一个PLC。此外，PLCs在表示三维集合体对象时比空间多面体更灵活。例如，图8的阴影面不能用任何的多边形来表示。对于一些有弯曲面的区域来说，这个表面三角形化在先前就是要求的，因此，PLCs差不多能够表示任何三维区域。1.3四面体网格质量Tetgen产生了一个四面体网格对于解决由有限元法和有限元体积法定义的偏微分方程不等式是非常有用的。问题是怎么样去产生一个四面体网格，这个产生四面体网格要遵守给出的域（空间多面体或者是PLC），而且这个域包含大小和网格元素形状的确切约束。它是验证产生的网格质量的一个典型问题。这个网格生成质量检验技术提供了形状与大小来保证这个网格：所有的元素都一个确切的质量衡量标准，并且这个元素的数目是在最小数目的常量因子之内。解决网格生成质量的方法包括octree，advancingfront，和德洛内方法。德洛内优化，一个德洛内四面体化是被迭代增加的顶点改善了。这些顶点的布置是被选中去迫使边界整合，并且提高网格的质量。德洛内优化已经成功应用到相应的二维问题。这些算法能够在chew和ruppert的作品中被找到。然而，在三维区域中这些算法不能移除这些裂片（非常扁平，几乎退化了四面体）。Tetgen处理这个问题实现的算法是来自shewchuk的德洛内优化算法。对于三维来说它是一个泛化的ruppert算法。在三维空间中给出一系列的顶点，约束段和小平面，以及不少于90度的输入角，这个算法能够产生一个半径边缘比列不大于2.0的德洛内四面体网格质量。在短距离上四面体从小到大是分等级的。这个算法产生的网格普遍胜过这理论界，并且在消除有最小或最大二面角的四面体时是非常有效的。除了四面体临近的最小输入角，这个裂片是最坏形状四面体在进行德洛内