自动网格生成法
二维网格生成—Advancing Front方法
从概念上来讲，Advancing front方法是最简洁的方法之一。单位元素生成算法始于一个特殊边界条件所定义的“front”,此算法逐级地生成各个元素，同时“front”元素离散地前进，直至整个区域都被元素所覆盖。
网格生成过程包括三个主要步骤：
1、在边界上生成节点，形成一个离散的区域边界。
2、在离散区域边界内生成元素（亦或节点）。
3、强化节点形状以提高网格图形清晰度。
在介绍这个方法之前我们先介绍以下有关于二维空间地几何表示。
一、二维网格的几何特征
我们利用网格参数（一般是空间的函数）来表征网格的一些性质，诸如节点尺寸，节点形状和节点方向等等。网格参数包括两个相互正交的单位矢量a1和a2表示的方向参数，和由两个相互正交代表节点形状的矢量的模值h1和h2。前者表征网格节点伸展的方向，注意的是，只有在生成的是非各向同性的网格内，方向参数才有定义，否则方向矢量是常单位矢量，而尺寸参数有h1=h2，这样就定义了各向同性的平凡网格。
二、区域的几何表示
边界曲线的表示：
我们一般用组合参数样条线表示曲线边界单位，利用参数t，我们利用二维矢量函数表达出曲线边界：
r t=x t,y t,0≤t≤1
一般来讲，一条组合样条曲线至少是C1连续的，以保证边界曲线平滑和算法要求的数学连续性。我们下面将要用厄米三阶样条线，当然还有许多就不一一举例了。
样条线的参数表达式如下：
X t=H0t,H1t,G0t,G1t∗x0,x1,x,t0,x,t1T,0≤t≤1
转置的前两项是曲线的两个端点，而后两项是它们对t求导现在端点处的值。另外G和H分别是四个三阶厄米多项式：
H0t=1−3t2+2t3 ; H1t=3t2−2t3
G0t=t−2t2+t3 ; G1t=−t2+t3
此时，参数表达式可以通过一个系数矩阵来描述：
X t=1,t,t2,t3M x0,x1,x,t0,x,t1T,0≤t≤1
其中M矩阵读者很容易写出，是一个4*4的方阵，而每一列是这些厄米多项式的系数排列而成。我们把这个表示称之为样本表示。每个边界都包含n个这样的数据点：
x i,i=1,2,3,……,n
利用内插法可以构造出如下形式的关系式：
X u=H0t x u i−1+H1t x u i+Δi G0t x,t u i−1+Δi G1t x,t u i
其中Δi是单位区间的长度。同时参数t也变为离散的取值是单位区间从原点到任意点所有的个数。如果参数的离散取值正好是i，那么u的表达式将简化为：
t =u − i −1 Δi
;u =t +i −1
这样由内插法画出的边界曲线就如下图所示：
三、 三角形格点的生成
接下来我们讨论三角形格点生成算法的主要思想。为了简化生成格点网格图的过程我们用方向矢量生成一个对称变换：
T x =
1i
2
i =1αi (x )αi (x )T 容易证明由此算符导出的定域变换是一种标度变换，i 方向上乘以hi 的倒数,如同下图中所画：
如图中所示，经过标度变换，下面的图两个尺寸变为一样，也就是进行了归一化。 边界节点的生成：
边界节点生成的算法步骤有以下几方面构成：
1、对于一个具有特征长度L的边界曲线，如同刚刚提到过的利用三阶厄米多项式生成
边界曲线一样，我们也得到一系列的离散边界点，如图所示：
根据一般欧氏空间几何方法，可以得出图中的与曲线相切的矢量为：
2、通过背景网格计算每一点的尺寸参数和方向参数，进而形成每一点的标度变换。
3、为了找到曲线上新的节点的位置，需要沿着曲线定义节点的尺寸分布函数：在切线
方向上可以定义一个新的矢量：
τl=ℎs
l
t l
应用标度变换，将以上矢量变换为归一化后的形式：
因此，利用上式很容易定义样本点的尺寸（切线矢量线长），在归一化的条件下，这个量是二维的欧几里得矩阵张量。
4、假设在x l的邻域内，变换矩阵T l是常数矩阵，ℎs
l
是参数u的函数，我们可以利用内插公式，构造连续的尺寸分布函数：
h u=ℎs
l N l u
m
l=0
密度函数定义如下：沿着曲线的单位长度，元素的个数，表示成上述定义的函数的倒数。
5、需要产生的N的总数需要与特定的元素尺寸自洽，这里我们用密度函数来表征这种
自洽性，因此，有下述积分：
然而，A并不严格是一个积分，为了描述N与A的关系，定义一个商：
由于曲线的两端点的位置是已知的：
X0=x0u0 ; X m=x m u m
我们只需要再额外生成(N-1)个新的节点就可以了。
6、假设边界上的每一个节点都是由相同的θ所形成，一个新的节点（例如第k个）有
下述积分描述：
那么第k+1个节点的特征积分为：
由于我们已经假设所有新的节点的特征积分是一样的，所以上面的两个积分实际上
是相等的，这样给出的关系式是：
其中k=0,1,2…(N-2),一般来讲我们可以用迭代的方法来求解上述积分
7、知道了节点的个数，利用三阶的厄米多项式样条线，就可以确定节点的位置。
元素的生成问题：
接下来介绍三角元素的生成，如图所示，生成的过程分以下几步：
1、一个方向为正的连接节点a和节点b的side是利用generation front来产生的，我们
将这个矢量作为生成新元素的基准点。为了生成的网格图节点的尺寸是光滑渐变的过程，首先考虑最小的节点，在generation front方法中，我们对sides进行分类，根据它们的长度进行更新，同时算法的效率也在不断变高。
2、取基准side的中点为m，计算此点的方向和尺寸，再从背景网格内插入新的节点。
3、元素的生成过程是可以被大大简化的，当基准side上的点m和其他的节点的坐标都进
行之前我们定义的标度变换时，我们将在新的“归一化”矢量空间内，进行计算和演化过程，使生成的三角形尽可能趋近于等边三角形的形状。
4、定义一个理想的次级基准点形成一个理想的正三角形，如同上图所示。这里标准的线段
ab的尺寸是：
