在计算机图形学和计算几何领域，实时生成三维网格是一项挑战性的任务。过去，由于硬件和软件的限制，生成真实感的网格和可定制的源代码模块并不现实。然而，随着现代计算机和编程语言的发展，现在不仅可以实时生成简单的网格，而且代码的编写也变得更加易于理解和修改。作者认为，计算几何和计算机视觉正在进入一个新的时代，在这个时代中，实时处理对于越来越多的问题变得现实可行。
为了形成一个可以被图形卡着色的表面，目标是创建一个顶点列表，以及一个由顶点索引组成的三元组列表，这些索引形成逆时针三角形。无论是可视化有限元建模（FEM）求解的微分方程，还是查看三维物体的形状，第一步都是形成三角网格。
通常，选择一组点是容易的。对于像圆柱体或球体这样的简单物体，点的生成直接导致三角形的生成。从任意一组点生成网格是Delaunay三角剖分发挥作用的地方。代码的目标不是计算理想的三角剖分，而是为大多数实际的三维或FEM问题提供一个“足够好”的解决方案，并且能够快速完成。因此，代码在添加每个点后递归改进三角剖分，直到达到递归计数或达到理想的Delaunay三角剖分。这限制了网格计算所需的时间，并避免了软件错误导致的无限递归。
Delaunay三角剖分以Boris Delaunay命名。其基本概念是形成一个网格，其中每个三角形的三个点位于一个不包含任何其他点的圆的边缘。这意味着，给定任意两个相邻的三角形（四边形），它们对面的角的和小于180度。
例如，三角形a、b、d和b、c、d不符合Delaunay条件。但是，b、c、a和c、d、a符合。这是因为角bcd + dab > 180，但abc + cda < 180。这迫使网格的三角形尽可能均匀分布。
Bowyer-Watson算法通过一次添加一个点来迭代地将网格从一个Delaunay网格转换为另一个。该算法的工作原理是通过删除所有包含新点的外接圆的三角形，并重新形成网格。提供的代码采用了一种更简单的方法。
从上到下，三角形被翻转以满足Delaunay条件，使用3个点：
这同样的事情，但是使用了7个点。注意最初三角形大多是狭长的，而其他三角形则非常大。
每次插入后翻转一级，网格更加规则（如下）。
经过第二轮翻转后，第一轮翻转的效果随后根据需要进行翻转（如下）。
Bower-Watson算法有点复杂，因为：
添加一个点可能会导致一组三角形被删除并重新形成。
一次性重新形成集合会探索形成许多可能的三角剖分。
必须搜索受影响的三角形。
没有模式可以按顺序调整网格。
“外壳”技术也常用于从一点螺旋向外，从内向外重新形成三角剖分。这种方法的优点是它以有序的方式计算和重新计算网格。缺点是软件实时重新计算每个三角形的圆，并排序通过三角形。
提供的代码采用了一种混合方法，形成了一个三角形的链表。每个三角形由三个顶点组成，每一边都有一个指向相邻三角形的指针（或null）。代码具有以下优点：
每个三角形都有一个指向其邻居的链接。
如果一个三角形被改变，它的邻居可能会受到影响（没有圆）。
三角形通常不会被删除，它们会被添加或修改。
注意a->b->c是逆时针的，所以如果它有一个面被比如说direct3D渲染，它会从页面向外。三角形c->b->a是顺时针的，所以它的面朝向页面。只要方向保持一致，起始点就不相关，所以bdc与dcb或cbd相同。抽象代数中的这个概念通常被称为交换。
三角形1 = a,b,c，边b,c = 三角形2。
三角形2 = bdc，边c,b = 三角形1。
修复指针：
abe与边be应该指向ebc。
abe与边ea应该指向aec。
等等。
然后修复那些曾经指向abc的老相邻三角形：bdc边bc曾经指向abc，使其指向ebc。
检查每个三角形及其外邻：例如，bec与bdc共享一边。
检查对面的相邻边的角度。如果大于180度，翻转相邻线。
如果三角形没有翻转，跳到步骤10。
将旧三角形重新形成新三角形，修复三角形边缘。
对于每个三角形及其相邻三角形重复步骤5-8递归。
算法的关键是找到正确的三角形进行修改。
经典上，如果一个点在三角形的内部边，那么它就在三角形内。如果一条线通过两个点，这条线通常表示为y = mx + b，其中m是斜率，b是x=0的截距。线上方的区域可以表示为y > mx+b。
所以，如果一个三角形有边s, r，另一个点是t。那么如果测试点p，与点t在不等式的同一侧，那么测试点p就在与其他顶点相同的线上。
这意味着要计算一个点p是否在内部，代码比较看看它是否与边的顶点在同一侧。这是一个大量的计算。缓存信息可以加速比较，但还不够。大多数三角形不包含点，点也不在三角形附近。为了加速计算，只有靠近三角形的点需要使用经典方法进行测试。软件计算每个顶点与三角形中心之间的距离。如果点不比这个距离更近，它就不需要被测试。
三角形对象缓存按需计算的信息以形成网格。当一个三角形与其邻居“翻转”时，它的两边会改变，但两个点保持不变。当一个顶点移动时，它使关于这些边的现有信息无效。
例如，如果设置了点A、B、C，那么三角形的中心就会改变，设置点A、B、C会将计算设置为false，要求计算中心并设置标志。
Vertex m_Center;
public Vertex Center
{
get
{
if (m_centerComputed)
return m_center;
m_center = new Vertex(
(A.X + B.X + C.X) / 3f,
(A.Y + B.Y + C.Y) / 3f,
(A.Z + B.Z + C.Z) / 3f
);
float delta = m_center.DeltaSquared(A);
float tmp = m_center.DeltaSquared(B);
delta = delta > tmp ? delta : tmp;
tmp = m_center.DeltaSquared(C);
delta = delta > tmp ? delta : tmp;
FarthestFromCenter = delta;
m_centerComputed = true;
return m_center;
}
}
一旦计算出中心，软件就可以重用这些信息，只有在需要时才会重新计算。
表单提供了一个生成半聚集种子点集的演示。网格类具有以下API：
点 - 网格中使用的顶点对象列表。
面 - 网格的三角形面的列表。
边界 - 用于形成初始正方形区域的矩形边界。
递归 - 从初始更改的三角形向外迭代的次数。对于大多数网格，100以下，需要递归重新三角化超过5或6次的可能性很低。这允许用户在计算时间和网格质量之间进行权衡。
计算() - 根据顶点列表计算网格。
追加() - 向三角剖分中添加一个新的顶点。
设置() - 设置边界。
绘制() - 绘制到System.Drawing.Graphics对象的网格进行调试。
获取顶点索引() - 获取形成逆时针面的索引集（每个三角形3个）。
示例：
List set = new List();
Random.Random r = new Random.Random(seed);
for (int i = 0; i < count; i++)
{
set.Add(new Vertex(r.Float(0, width), r.Float(0, height), 0));
}
Mesh m = new Mesh();
m.Recursion = 6;
m.Compute(set, new RectangleF(0, 0, 640, 480));
m.Draw(g, 0, 0, 640, 680);
List p = m.Points;
// 直接X顶点缓冲区的点。
int[] indicies = m.GetVertexIndicies();
// 直接X表面的索引。
在笔记本电脑上（一台不错的I7，带Windows 7），算法在小网格上运行得足够快，可以在视频速度上完成。每个点都是搜索需要被分成三个的三角形，所以时间随着搜索的增长。目标是在另一个项目中使用这个，需要能够重用代码，维护它，并让它运行得相当快。虽然这相对快，但还有其他更快的，如果需要超级快的OpenCV提供了一个算法版本。
50个顶点 5毫秒
100个顶点 11毫秒
500个顶点 129毫秒
1k个顶点 380毫秒
5k个顶点 7.8秒
10k个顶点 31秒
60 Hz 16毫秒 150个顶点