Loop Subdivision与Modified Butterfly Subdivision

记一下做图形学subdivision实验时候踩的大小坑

crease是什么

当说一条边是crease edge的时候，我们的意思其实是说这条边是sharp edge.

为的是在Subdivision的时候能够保留一些锐利的部分，例如

正常的Loop Subdivision

下图中的色边即为标记的sharp edge，标记出来的目的是为了在之后的Subdivision过程中还能保持锐利。

添加了对crease处理的Loop Subdivision

Loop Subdivision

参考：*Piecewise Smooth Surface Reconstruction*

Loop Subdivision包含3个阶段：为每条边计算一个新的顶点；更新原有旧顶点的位置；更新网格的拓补结构。

预处理

进行下面的操作之前，需要识别出每一个顶点的类型。

A smooth vertex is one where the number of incident sharp edges s is zero; a dart vertex has s = 1; a crease vertex has s = 2; and a corner vertex has s > 2. Crease vertices are further classified as regular and non-regular depending on the arrangement of smooth edges.An interior crease vertex is regular if it has valence 6 with exactly two smooth edges on each side of the crease; a boundary crease vertex is regular if it has valence 4. All other crease vertices, whether interior or boundary, are non-regular.

将每个点按照crease边的入度s分别划分为normal vertex(s=0)、dart vertex(s=1)、crease vertex(s=2)和corner vertex(s>=3)，其中crease vertex根据边的数量以及排列分为regular crease vertex和non-regular crease vertex.

regular crease vertex有两种情况

(a)如果顶点不在边界上（在mesh内部），要求顶点共与6条边相连，且两条crease一边有2条smooth边（即普通边）。如下图：

(b)如果顶点在边界上，那么只要周围相连边的数量为4即是regular

crease vertex中不是regular的就是non-regular

(1)为每条边计算一个新的顶点

根据边上两个端点的类型，查表Table.1，得到的序号去上图找对应的权重分配策略。

注意：只有crease边才需要查表，普通边直接按照下图的smooth edge来计算，边界边两个顶点权重1/2

crease边采取(2)(3)的权重分配方式，最终生成的新顶点必定也会在这条边上，因此就能保持crease边的“锐利”。而smooth edge就会受到周围另外两个顶点的影响，所以会使新生成的点“弓起来”。

(2)更新原有旧顶点的位置

根据顶点的类型来更新其位置。

图中数值为权重

(3)更新网格的拓补结构

Modified Butterfly Subdivision

可以参考 : 改进的蝴蝶算法的详细介绍 - 羊习习 - 博客园 (opens new window)

一条边的两个顶点v1和v2，寻找v1和v2各自周围点，根据其连接边的数量不同，采取不同的权重分配策略（共四种）

(a)没什么好说的

(b)当v1和v2其中一个连接边的数量为6，另一个不为6时。不为6的那个点称为k-vertex（上图中是v1），该点的权重为3/4，剩下1/4的权重按该点周围点的数量分配给周围点（v2也是v1的周围点s0）。

注意特殊情况：如果处理的模型是非闭合的，即处理的模型有开口。那么当寻找v1周围的顶点并保存时，应该注意存储顶点的顺序问题（k=4,>=5的情况）

****

当前处理的边是(v1,v2)，假设一向上找周围顶点，找到边(v1,3)遇到边界边停止，想要找剩下的顶点就需要从(v1,v2)向下寻找，找到点的顺序是5,4.在最终存储时需要将向下寻找时找到的点倒序存到123后面才能保证顺序正确。

(c)分别对v1和v2各执行一次b，计算出的两个新顶点取平均值

(d)处理边界边和crease边

先说边界边的情况，下图中红色的为boundary edge，假设当前处理的边为AB，那么就需要找到AC和BD，顶点C和D的权重为-1/16,A和B的权重为9/16

如果处理的是crease边，那么左右两边的数量不一定为1,可能有多条

也可能一条也没有。

如果一条也没有，直接令这一侧的顶点权重为1/2.如果有多条crease边，则让它们平分这-1/16的权重。