欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

参考论文：Q-Morph an indirect approach to advancing front quad meshing
$\epsilon -\pi -\theta \in \cdot$

底边生成四边形

算法过程中每次从Front队列中根据状态取出一条优先级最高的边，处理并生成一个四边形。

每条边都有一个level, 初始front里的边为level 0, 之后为level 1, 依此类推。这样可保证下一行四边形生成要在当前行生成之后。

为了生成更高质量的网格，短的边需要优先处理，所以在选择边时，不仅要考虑状态，还需要结合边长来排序。

侧边生成

状态为 0-0，0-1，1-0的底边会生成1条或2条侧边。

生成侧边的方式有三种：1）沿用当前已经有三角边，2）当前三角边进行对角线翻转后使用，3）生成一条新的边来分割三角形。

情况一：

Nk为需要生成侧边的一个顶点。

EF1, EF2为当前Front中的边，Vk为其角平分线，作为侧边的理想位置。

计算Vk与Nk邻接的所有边Ei角度θi, 如果最小的θi<ε(=π/6), 则取Ei为侧边。

情况二：

如上图a)所示，Vm为E0翻转后的向量，如果Vm与Vk夹角<ε, 则Ek作为侧边。

情况三：

如上图b)所示，如果Vm与Vk夹角>ε 或 E0翻转后长度太长时（与EF1, EF2相比）, 需要对E0从Vk与之交点处分裂得到Ek作为侧边。

侧边生成综合公式如下：

顶边生成

根据一条底边生成两个侧边后，还剩下一个顶边就可以组成四边形了。

顶边自然是由侧边的两个上顶点连接而成，但是直接连接会与其他边相交，所以需要对这些相交的边进行翻转，直到没有相交。

上图为顶边ND-NC生成的过程，a)为侧边刚生成的状态，找到与虚线相交的所有边，b)翻转1，2，c)翻转3，d)翻转4，生成连接ND-NC的边。

Agl1 算法可以用来生成顶边如下：

查找相交边的过程：

以Nc为起点先找到与NCND相交且顶点为Nc的一个三角形的对边Ei。

根据三角形一边与直线相交，必有另一边与直线相交的原理。

去找到下一个相交的边，直到到达ND。

Agl2 算法可以用于查找相交边如下：

上述算法中带*的行是对原文的修正，经过验算原文中的符号判断有误。

上述算法有一种特殊情况，Vs刚好与三角形相交于顶点，一种比较简单的做法是把该顶点往Vs垂直方向移动一个很小的距离。

三维情况处理

Agl2 是在平面区域上计算的。如果要应用于三维曲面场景，需要做一些改动。

第5行和第16行（找星号的行）需要在曲面法平面上进行判断。

$P_c是N_c处平均法向，可以通过T(N_c)面法向得加权平均得到$

第5行判断条件改为
$((P_c\times V_s)\times P_c)\cdot ((P_c\times V_k)\times P_c)<0and((P_c\times V_s)\times P_c)\cdot ((P_c\times V_{k+1})\times P_c)>0$

$P_i是E_i处法平面的法向，可以通过T_i(E_i)和T_{i+1}(E_i)面法向加权平均法向得到$

第16行判断条件改为$((P_i\times V_s)\times P_i)\cdot ((P_i\times V_i)\times P_i)>0$

清除内部边

生成四边形后，内部还有很多三角面片和边，需要进行删除。

可以从四边形4个点开始广度优先遍历所有边，进行删除。

---

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。创作不易，帮忙点击公众号的链接，帮忙转发，感激不尽。