当前位置: 首页 > 工具软件 > TetGen > 使用案例 >

# Tetgen数据结构学习

钱元徽
2023-12-01

Tetgen数据结构学习:

一、tetgenio:

用于在用户和TetGen的内部数据结构(类tetgenmesh)之间传输输入/输出数据的结构。

tetgen中用双精度浮点数来表示实数,即

define double REAL 

tetgen中可能认为点和conner是等价的

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CL2JmKsR-1667541107407)(D:\software\typora\Image.png)]

(1)内部结构体:

1.polygon:

“多边形”描述的是一个简单的多边形(没有孔)。它不一定是凸的。每个多边形包含一定数量的角(点)和相同数量的边(边)。多边形的点必须以逆时针或顺时针的顺序给出,它们形成一个环,所以每两个连续的点形成多边形的一条边。

typedef struct {
    int *vertexlist;
    int numberofvertices;
  } polygon;

2.facet:

“facet”描述的是一个多边形区域,其中可能有孔、边和浮动的点。每个面由一系列多边形和一系列孔点(孔点严格位于孔内)组成。

  typedef struct {
    polygon *polygonlist;
    int numberofpolygons;
    REAL *holelist;
    int numberofholes;
  } facet;

3.voroedge:

“voroedge”是Voronoi图的一条边。它对应于一个Delaunay的面。每个voroedge要么是连接两个Voronoi顶点的线段,要么是从Voronoi顶点到“无限顶点”的射线。'v1’和’v2’是指向Voronoi顶点列表的两个索引。'v1’必须是非负的,而’v2’如果是射线则可能是-1,在这种情况下,这条射线的单位法线用’vnormal表示

  typedef struct {
    polygon *polygonlist;
    int numberofpolygons;
    REAL *holelist;
    int numberofholes;
  } facet;

4.vorofacet:

“vorofacet”是Voronoi图的一个面。它对应于一条Delaunay边。每个Voronoi面都是由一系列Voronoi边组成的凸多边形,它可以不闭合。'cl’和’c2’是指向Voronoi单元格列表的两个索引,也就是说,两个单元格共享这个面。'elist’是指向Voronoi边列表的索引数组,'elist[0]'保存该面Voronoi边的数量(包括射线)。

 typedef struct {
    int c1, c2;
    int *elist;
  } vorofacet;

5.pointparam:

与输入(或网格)顶点相关的附加参数。

 typedef struct {
    REAL uv[2];
    int tag;
    int type; // 0, 1, or 2.
  } pointparam;

(2)一些回调函数:

 typedef REAL (* GetVertexParamOnEdge)(void*, int, int);
  typedef void (* GetSteinerOnEdge)(void*, int, REAL, REAL*);
  typedef void (* GetVertexParamOnFace)(void*, int, int, REAL*);
  typedef void (* GetEdgeSteinerParamOnFace)(void*, int, REAL, int, REAL*);
  typedef void (* GetSteinerOnFace)(void*, int, REAL*, REAL*);
  typedef bool (* TetSizeFunc)(REAL*, REAL*, REAL*, REAL*, REAL*, REAL);


  // Variable (and callback functions) for meshing PSCs.
  void *geomhandle;
  GetVertexParamOnEdge getvertexparamonedge;
  GetSteinerOnEdge getsteineronedge;
  GetVertexParamOnFace getvertexparamonface;
  GetEdgeSteinerParamOnFace getedgesteinerparamonface;
  GetSteinerOnFace getsteineronface;

  // A callback function.
  TetSizeFunc tetunsuitable;

(3)读入的PLC属性:

1.点:

REAL *pointlist:点坐标数组,每个点占用三个位置,分别储存一个点的x,y,z坐标
REAL *pointattributelist:点的属性数组,每一个点的属性占用 numberofpointattribute 个位置
REAL *pointmtrlist:点度量张量数组,每个点占用numberofpointmtr个位置
int *pointmarkerlist:点标记数组,每一个数组占据一个位置
int *point2tetlist:四面体索引数组,每个四面体占用一个位置

  REAL *pointlist;
  REAL *pointattributelist;
  REAL *pointmtrlist;
  int  *pointmarkerlist;
  int  *point2tetlist;
  pointparam *pointparamlist;
  int numberofpoints;
  int numberofpointattributes;
  int numberofpointmtrs;

2.四面体:

int *tetrahedronlist:四面体顶点数组,第一个四面体的第一个点的索引被放在 [0] 号位置,紧接着存放其他点的索引,当使用(-o2,second order option)时候会继续存储边上的六个顶点,不适用则不存,之后存储第二个顶点,每个顶点占用numberofconnners个位置
REAL: *tetrahedronattributelist:tetrahedronattributelist’:四面体属性数组。每一个四面体的属性占据了 numberoftetrahedronattribute 个位置。
int *tetrahedronvolumelist:四面体体积约束数组,只有在tetgenio在输入的时候才使用
int *neighborlist:每个四面体的相邻的四面体索引,每个四面体的邻居占据四个位置
int *tet2facelist:四面体面的数组,每个四面体占用四个位置
int *tet2edgelist:四面体边的数组,每个四面体占用6个位置

  int  *tetrahedronlist;
  REAL *tetrahedronattributelist;
  REAL *tetrahedronvolumelist;
  int  *neighborlist;
  int  *tet2facelist;
  int  *tet2edgelist;
  int numberoftetrahedra;
  int numberofcorners;
  int numberoftetrahedronattributes;

3.面:

facet *facetlist:面数组,每个面占用一个位置,即上文中的提到的facet结构体
int *facetmarkerlist:面标记数组,每个面一个标记
int numberoffacets:面的个数

  facet *facetlist;
  int *facetmarkerlist;
  int numberoffacets;

4.洞:

REAL *holelist:体里面的洞数组,每个洞由一个完全位于洞之内的点确定,每三个位置确定一个洞,分别存储点的x,y,z坐标
int numberofholes:洞的数量

 REAL *holelist;
 int numberofholes;

5.区域(region):

REAL *regionlist:区域数组,每个区域由一个完全在区域内的点确定,每个区域占据五个位置,前三个分别为上述的点的xyz坐标,第四个是区域的属性,第五个是区域内四面体的最大体积
int numberofregions:区域的数量

  REAL *regionlist;
  int numberofregions;

(4)约束属性:

1.体位置上:

int *refine_elem_list:需要被细化的四面体数组,每个四面体占用4个位置,分别存储该四面体四个顶点的位置。
REAL *refine_elem_vol_list:约束数组,即四面体的体积,每一个元素占用一个位置
int numberofrefineelems:需要细化的元素的数量

  int  *refine_elem_list;
  REAL *refine_elem_vol_list;
  int  numberofrefineelems;

2.面位置上:

REAL *facetconstraintlist:面约束数组,限制了该面上子面的最大面积,每个约束由两个位置组成,前一个位置是该面的marker标记,后一个位置记录了最大面积
int nemberoffavetconstraints:受约束面的个数

  REAL *facetconstraintlist;
  int numberoffacetconstraints;

3.段位置上:

REAL *segmentconstraintlist:段约束数组,限制了该段上字段的最大长度,每个约束由三个位置组成,前两个分别储存段的两个端点的索引,第三个位置储存约束的大小
int numberofsefmentconstraints:约束段的数量

  REAL *segmentconstraintlist;
  int numberofsegmentconstraints;

(5)三角面片属性:

int *trifacelist:三角面数组,每个面由三个位置构成,分别是三个顶点的索引
int *trifacemarkerlist:三角面标记数组,每个三角面占用一个位置(其实我觉得不如都放在trifacelist数组的属性里算了,每个面多加一个位置放标记,可能是我还没看到后面,这样作者油什么深意吧)
int *o2facelist:每个面的二阶节点数组,(只有当使用-o2)选项时候才能会被访问,每个面的二阶节点都有三个,分别占用三个位置
int *face2tetlist:共享每个三角面片的两个四面体的索引,每个三角面占用两个位置
int *face2edgelist:每个三角面的边下标数组,每个三角形有三条边因此占用三个位置
int numberoftrifaces:三角面片的数量

  int *trifacelist;
  int *trifacemarkerlist;
  int *o2facelist;
  int *face2tetlist;
  int *face2edgelist;
  int numberoftrifaces;

(6)边属性:

int *edgelist:边数组,每个边由两个端点表示,第一个边的第一个顶点位于[0]号位置,每个边占用两个位置
int *edgemaekerlist:边标记数组,每条边占用一个位置
int *o2edgelist:每条边的中点,当(-o2被使用时候才被访问)。每条边占用一个位置
int *edge2tetlist:四面体索引数组
int numberofedges:边的数量

  int *edgelist;
  int *edgemarkerlist;
  int *o2edgelist;
  int *edge2tetlist;
  int numberofedges;

(7)泰森多边形属性

REAL *vpointlist:Voronoi顶点坐标数组(如点列表,即xyz三个位置表示一个点)。
voroedge *vedgelist:Voronoi边数组(每一项都是之前提到过的voroedge类型的结构体)
vorofacet *vfacetliat:Voronoi面数组(每一项都是之前提到过的voroafacet类型的结构体)
int **vcelllist:一个二维数组,存了Voronoi图中的单元格,第一行储存的是该数组的长度(即单元格的数量),接下来每一行都用来储存一个vfacetlist的索引。
int numberofvpoints:点的数量
int numberofvedges:边的数量
int numberofvfacets:面的数量
int numberofvcells:单元格的数量

  REAL *vpointlist;
  voroedge *vedgelist;
  vorofacet *vfacetlist;
  int **vcelllist;
  int numberofvpoints;
  int numberofvedges;
  int numberofvfacets;
  int numberofvcells;

(8)大量输入输出文件的读写操作:

应该可以见名知意

  // Input & output routines.
  bool load_node_call(FILE* infile, int markers, int uvflag, char*);
  bool load_node(char*);
  bool load_edge(char*);
  bool load_face(char*);
  bool load_tet(char*);
  bool load_vol(char*);
  bool load_var(char*);
  bool load_mtr(char*);
  bool load_elem(char*);
  bool load_poly(char*);
  bool load_off(char*);
  bool load_ply(char*);
  bool load_stl(char*);
  bool load_vtk(char*);
  bool load_medit(char*, int);
  bool load_neumesh(char*, int);
  bool load_plc(char*, int);
  bool load_tetmesh(char*, int);
  void save_nodes(const char*);
  void save_elements(const char*);
  void save_faces(const char*);
  void save_edges(char*);
  void save_neighbors(char*);
  void save_poly(const char*);
  void save_faces2smesh(char*);

  // Read line and parse string functions.
  char *readline(char* string, FILE* infile, int *linenumber);
  char *findnextfield(char* string);
  char *readnumberline(char* string, FILE* infile, char* infilename);
  char *findnextnumber(char* string);

读取行函数并解析字符串函数:

readline:从一个文件中读取一个非空行,返回一个指向该行第一个非空字符的指针

findnextfield:查找字符串的下一个字段。通过搜索空白或逗号跳过当前字段,然后跳过空白或逗号查找下一个字段。返回下一个开始字段的指针。

readnumberline:和第一个差别不大,希望读入纯数字的一行

findnextnumber:和二差别不大,这里不做解释

(9)构造和析构

初始化:void initialize()(即按照找我上面介绍的顺序把它们设置为NULL或者默认值)
清空内存:void clean_memory()(即清除掉init中的全部对象)

  tetgenio() {initialize();}
  ~tetgenio() {clean_memory();}

二、tetgenbehavior:

用于维护TetGen内部数据结构和算法使用的开关和参数的结构。

(1)tetgen中的开关名称

// Switches of TetGen. 
  int plc;                   // '-p', 0. 四面体PLC
  int psc;                   // '-s', 0. 没有说是干嘛的(可能是关于平滑的)
  int refine;                // '-r', 0. 重构先前生成的网格。
  int quality;               // '-q', 0. 细化网格
  int nobisect;              // '-Y', 0. 保持输入网格不被细分
  int cdt;                   // '-D', 0. 和 -p配合使用生成CDT
  int cdtrefine;             // '-D#', 7.用户手册里也没讲可能需要看看之后的代码是怎么用的
  int coarsen;               // '-R', 0. 网格粗化(减少网格单元)。
  int weighted;              // '-w', 0. 生成加权Delaunay(常规)三角剖分。
  int brio_hilbert;          // '-b', 1. 手册里也没有(关于希尔伯特变换的?maybe)
  int flipinsert;            // '-L', 0. 手册里没有,增量翻转插入点吗?
  int metric;                // '-m', 0. 应用用户自定义的网格大小功能
  int varvolume;             // '-a', 0. 应用最大体积约束
  int fixedvolume;           // '-a', 0. 
  int regionattrib;          // '-A', 0. 在不同范围内四面体指定属性
  int insertaddpoints;       // '-i', 0. 插入附加点的列表
  int diagnose;              // '-d', 0. 检测PLC各方面的自交叉
  int convex;                // '-c', 0. 保留PLC的凸壳
  int nomergefacet;          // '-M', 0. 不合并共面的面
  int nomergevertex;         // '-M', 0. 不合并接近的点
  int noexact;               // '-X', 0. 不适用精确几何谓词
  int nostaticfilter;        // '-X', 0. 没有静态过滤器
  int zeroindex;             // '-z', 0. 对所有输出项从零开始编号
  int facesout;              // '-f', 0. 输出所有面到.face文件
  int edgesout;              // '-e', 0. 输出所有边到.edge文件
  int neighout;              // '-n', 0. 输出四面体邻居到。neigh文件
  int voroout;               // '-v', 0. 输出Voronoi图表到文件
  int meditview;             // '-g', 0. 将网格输出到。mesh文件,供Medit查看。
  int vtkview;               // '-k', 0. 输出网格到。vtk文件,以供Paraview查看。
  int vtksurfview;           // '-k', 0. 表面的?
  int nobound;               // '-B', 0. 抑制边界信息的输出
  int nonodewritten;         // '-N', 0.
  int noelewritten;          // '-E', 0.
  int nofacewritten;         // '-F', 0. 三个不输出
  int noiterationnum;        // '-I', 0. 抑制网格迭代次数
  int nojettison;            // '-J', 0. 不丢弃输出.node文件中未使用的顶点
  int docheck;               // '-C', 0. 检查最终网格的一致性。
  int quiet;                 // '-Q', 0. 除错误外无终端输出。
  int nowarning;             // '-W', 0. 不警告
  int verbose;               // '-V', 0. 输出细节信息

(2)tetgen各种开关参数

有很多都不认识估计需要去看后面源码的时候了解

 // Parameters of TetGen.
  int vertexperblock;                                           // '-x', 4092.
  int tetrahedraperblock;                                       // '-x', 8188.
  int shellfaceperblock;                                        // '-x', 2044.
  int supsteiner_level;                                           // '-Y/', 2.
  int addsteiner_algo;                                           // '-Y//', 1.
  int coarsen_param;                                               // '-R', 0.
  int weighted_param;                                              // '-w', 0.
  int fliplinklevel;                                                    // -1.
  int flipstarsize;                                                     // -1.
  int fliplinklevelinc;                                                 //  1.
  int opt_max_flip_level;                                          // '-O', 3.
  int opt_scheme;                                                // '-O/#', 7.
  int opt_iterations;                                             // -O//#, 3.
  int smooth_cirterion;                                              // -s, 1.
  int smooth_maxiter;                                                // -s, 7.
  int delmaxfliplevel;                                                   // 1.
  int order;                                                       // '-o', 1.
  int reversetetori;                                              // '-o/', 0.
  int steinerleft;                                                 // '-S', 0.
  int unflip_queue_limit;                                      // '-U#', 1000.
  int no_sort;                                                           // 0.
  int hilbert_order;                                           // '-b///', 52.
  int hilbert_limit;                                             // '-b//'  8.
  int brio_threshold;                                              // '-b' 64.
  REAL brio_ratio;                                             // '-b/' 0.125.
  REAL epsilon;                                               // '-T', 1.0e-8.
  REAL facet_separate_ang_tol;                                 // '-p', 179.9.
  REAL collinear_ang_tol;                                     // '-p/', 179.9.
  REAL facet_small_ang_tol;                                   // '-p//', 15.0.
  REAL maxvolume;                                               // '-a', -1.0.
  REAL maxvolume_length;                                        // '-a', -1.0.
  REAL minratio;                                                 // '-q', 0.0.
  REAL opt_max_asp_ratio;                                           // 1000.0.
  REAL opt_max_edge_ratio;                                           // 100.0.
  REAL mindihedral;                                              // '-q', 5.0.
  REAL optmaxdihedral;                                          // -o/# 177.0.
  REAL metric_scale;                                              // -m#, 1.0.
  REAL smooth_alpha;                                             // '-s', 0.3.
  REAL coarsen_percent;                                         // -R1/#, 1.0.
  REAL elem_growth_ratio;             // Growth ratio of # elements, -r#, 0.0.
  REAL refine_progress_ratio;

三、过滤精确几何谓词

orient3D test:它决定一个点相对于由其他三个非共线点定义的平面的位置

in sphere test:它决定了一个点相对于其他四个非共面点定义的球体的位置

void exactinit(int, int, int, REAL, REAL, REAL);

REAL orient3d(REAL *pa, REAL *pb, REAL *pc, REAL *pd);
REAL insphere(REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL *pe);
REAL orient4d(REAL *pa, REAL *pb, REAL *pc, REAL *pd, REAL *pe,
              REAL ah, REAL bh, REAL ch, REAL dh, REAL eh);

REAL orient2dexact(REAL *pa, REAL *pb, REAL *pc);
REAL orient3dexact(REAL *pa, REAL *pb, REAL *pc, REAL *pd);
REAL orient4dexact(REAL* pa, REAL* pb, REAL* pc, REAL* pd, REAL* pe,
                   REAL ah, REAL bh, REAL ch, REAL dh, REAL eh);


几何谓词的计算公式,一般只需要知道行列式的正负就可以进行判断,具体的可以参考Hang Si 博士的论文

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dzujOmYo-1667541107408)(C:\Users\25442\AppData\Local\Temp\Image.png)]

四、tetgenmesh:

四面体划分数据结构

三维分段线性复合体(PLC) X的四面体网格T是一个三维单纯复合体,它的底层空间等于X的空间。T包含一个二维子复合体S,它是X边界的三角形网格. S包含一个一维子复合体L,它是边界S的线性网格。TetGen的当前版本显式地分别存储子面和段(分别位于曲面网格S和线性网格L中)。在四面体和子面中分配额外的指针以彼此指向。TetGen使用基于四面体的数据结构。它存储四面体和顶点。该数据结构是基于指针的。每个四面体都包含指向其顶点和相邻四面体的指针。每个顶点都有它的x、y、z坐标,以及指向其中一个四面体的指针。四面体和顶点都可以包含用户数据。

(1)四面体结构:

由一个double类型的二维数组表示

  // The tetrahedron data structure.  It includes the following fields:
  //   - a list of four adjoining tetrahedra;
  //   - a list of four vertices;
  //   - a pointer to a list of four subfaces (optional
  // , for -p switch);
  //   - a pointer to a list of six segments  (optional, for -p switch);
  //   - a list of user-defined floating-point attributes (optional);
  //   - a volume constraint (optional, for -a switch);
  //   - an integer of element marker (and flags);
  // The structure of a tetrahedron is an array of pointers.  Its actual size
  //   (the length of the array) is determined at runtime.

  typedef REAL **tetrahedron;

我自己的理解,不知道是否正确,希望大家指正

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gGJPmSxU-1667541107409)(C:\Users\25442\AppData\Local\Temp\微信图片_20221028171917.jpg)]

(2)子面结构:

同样由一个二维数组表示

  // The subface data structure.  It includes the following fields:
  //   - a list of three adjoining subfaces;
  //   - a list of three vertices;
  //   - a list of three adjoining segments;
  //   - two adjoining tetrahedra;
  //   - an area constraint (optional, for -q switch);
  //   - an integer for boundary marker;
  //   - an integer for type, flags, etc.

  typedef REAL **shellface;

具体的形式可以参考四面体结构

疑惑的是最后一行的type和flags是指什么?

(3)点结构:

点的结构比起另外两个稍微多些

  // The point data structure.  It includes the following fields:
  //   - x, y and z coordinates;
  //   - a list of user-defined point attributes (optional);
  //   - u, v coordinates (optional, for -s switch);
  //   - a metric tensor (optional, for -q or -m switch);
  //   - a pointer to an adjacent tetrahedron;
  //   - a pointer to a parent (or a duplicate) point;
  //   - a pointer to an adjacent subface or segment (optional, -p switch);
  //   - a pointer to a tet in background mesh (optional, for -m switch);
  //   - an integer for boundary marker (point index);
  //   - an integer for point type (and flags).
  //   - an integer for geometry tag (optional, for -s switch).
  // The structure of a point is an array of REALs.  Its acutal size is 
  //   determined at the runtime.

  typedef REAL *point;

(4)Tetgen中的句柄(Handles)

四面体中的导航和操作是通过操作被称为句柄的结构来完成的。句柄是一对(t, v),其中t是指向四面体的指针,v是一个4位整数,范围从0到11。V被称为四面体的“版本”,它表示四面体的一个特定面的有向边。四面体中的四个点有12种偶排列,每一种偶排列都代表一条有向边,每条可以确定一个面,被称作闭环(edge rings),所以V的四位整数中上两位表示一个面中的一条有向边(索引从0~ 2),低两位存放面的索引(从0~3).
在四面体中,给每个面指定与它相对的节点相同的索引。将连接面i到面j的边表示为i/j。我们将12个版本编号如下:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-z56EK3eB-1667541107410)(C:\Users\25442\AppData\Roaming\Typora\typora-user-images\image-20221104125932623.png)]

类似地,(边界)三角剖分中的导航和操作是通过使用三角形句柄来完成的。每个句柄都是一对(s, v),其中s是一个指向三角形的指针,v是一个范围从0到5的版本。每个版本对应这个三角形的一条有向边。将三角形的三个顶点从O到2编号(根据它们在数据结构中的存储)。赋予每条边与三角形中对边的节点相同的下标。三角形的六种形式是:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jRxTJo2R-1667541107410)(C:\Users\25442\AppData\Roaming\Typora\typora-user-images\image-20221104125943873.png)]

两种句柄的定义,添加了等号运算符重载

  class triface {
  public:
    tetrahedron *tet;
    int ver; // Range from 0 to 11.
    triface() : tet(0), ver(0) {}
    triface& operator=(const triface& t) {
      tet = t.tet; ver = t.ver;
      return *this;
    }
  };

  class face {
  public:
    shellface *sh;
    int shver; // Range from 0 to 5.
    face() : sh(0), shver(0) {}
    face& operator=(const face& s) {
      sh = s.sh; shver = s.shver;
      return *this;
    }
  };

(5)Arraypool:

一种动态线性阵列。每个数组池包含一个指向多个块(blcoks)的指针数组。每个块包含相同固定数量的对象(object)。数组的每个索引都指向池中的一个特定对象。最高位指向包含该对象的块的索引。较低的位在块内寻址这个对象。

内部元素:

int objectbytes:块中一个对象的大小

int objectsperblock:每个块中对象的数量int

log2objectsperblock:以2为底objectsperblock的对数unsigned

long totalmemory:总内存

  class arraypool {

  public:

    int objectbytes;
    int objectsperblock;
    int log2objectsperblock;
    int objectsperblockmark;
    int toparraylen;
    char **toparray;
    long objects;
    unsigned long totalmemory;

    void restart();
    void poolinit(int sizeofobject, int log2objperblk);
    char* getblock(int objectindex);
    void* lookup(int objectindex);
    int newindex(void **newptr);

    arraypool(int sizeofobject, int log2objperblk);
    ~arraypool();
  };

(6)Memorypool:

分配内存的数据结构。

Firstblock是项目的第一个块。Nowblock是当前正在从中分配项的块。Nextitem指向某项的下一块可用内存。Deadi temstack是可回收的已释放项的链表(栈)的头。Unallocateditems是从nowblock中剩余要分配的项的数量。Traversal是遍历整个项目列表的过程,它与分配是分开的。注意,遍历将访问“deaditemstack”堆栈上的项以及活动项。Pathblock指向当前正在遍历的块。Pathitem指向下一个要遍历的项。Pathitemsleft是在路径块中仍然要遍历的项的数量。

  class memorypool {

  public:

    void **firstblock, **nowblock;
    void *nextitem;
    void *deaditemstack;
    void **pathblock;
    void *pathitem;
    int  alignbytes;
    int  itembytes, itemwords;
    int  itemsperblock;
    long items, maxitems;
    int  unallocateditems;
    int  pathitemsleft;

    memorypool();
    memorypool(int, int, int, int);
    ~memorypool();
    
    void poolinit(int, int, int, int);
    void restart();
    void *alloc();
    void dealloc(void*);
    void traversalinit();
    void *traverse();
  }; 

(7)“badface”

badeface用于形容以下几种情形:

​ -该面或者该四面体不是Delaunay的

​ -是一个被侵占的字段或者子面

​ -一个质量不好的四面体(比如由很大的边缘-半径比)

​ -是一个sliver,边缘半径比很小,但是体积和二面角很大

​ -一个刚被翻转的面(为以后取消翻转保存)

  class badface {
  public:
    triface tt; 
    face ss;
    REAL key, cent[6];  // 6条边的外圆角或cos(二面角)
    point forg, fdest, fapex, foppo, noppo;
    badface *nextitem; 
    badface() : key(0), forg(0), fdest(0), fapex(0), foppo(0), noppo(0),
      nextitem(0) {}
    void init() {
      key = 0.;
      for (int k = 0; k < 6; k++) cent[k] = 0.;
      tt.tet = NULL; tt.ver = 0;
      ss.sh = NULL; ss.shver = 0;
      forg = fdest = fapex = foppo = noppo = NULL;
      nextitem = NULL;
    }
  };

包含两种句柄,外心,和六个边的二面角余弦值,以及下一个需要处理的badface

(8)tetgen使用的标签

  // Labels that signify the type of a vertex. 
  enum verttype {UNUSEDVERTEX, DUPLICATEDVERTEX, RIDGEVERTEX, /*ACUTEVERTEX,*/
                 FACETVERTEX, VOLVERTEX, FREESEGVERTEX, FREEFACETVERTEX, 
                 FREEVOLVERTEX, NREGULARVERTEX, DEADVERTEX};
 
  // Labels that signify the result of triangle-triangle intersection test.
  enum interresult {DISJOINT, INTERSECT, SHAREVERT, SHAREEDGE, SHAREFACE,
                    TOUCHEDGE, TOUCHFACE, ACROSSVERT, ACROSSEDGE, ACROSSFACE,
                    SELF_INTERSECT};

  // Labels that signify the result of point location.
  enum locateresult {UNKNOWN, OUTSIDE, INTETRAHEDRON, ONFACE, ONEDGE, ONVERTEX,
                     ENCVERTEX, ENCSEGMENT, ENCSUBFACE, NEARVERTEX, NONREGULAR,
                     INSTAR, BADELEMENT, NULLCAVITY, SHARPCORNER, FENSEDIN,
                     NONCOPLANAR, SELF_ENCROACH};

五、数据结构篇完结

到此数据结构篇完全完结,其实tetgen中还有许多内容,但是限制与篇幅和我的个人能力难以继续,如果有人也在此方面处于起步阶段,希望我所写的对你有所帮助,对于在此方面耕耘多年的技术大牛希望可以容忍我在文章中犯得许多错误,并希望可以指正。建议大家去阅读源码,写的很好,但是限于本人的能力有些地方难以理解,希望大家可以私信与我分享学习经验。

 类似资料: