Please enable Javascript to view the contents

计算机辅助几何设计(7):细分曲线与曲面

 ·  ☕ 5 分钟

1. 简介

样条曲面的局限性

  • 连续张量积样条曲面的参数域仅在特定的方形网格上定义,因此拓扑受限
  • 将多个参数域装配到一个曲面非常繁琐,很难获得连续性保证
  • 曲线的处理与剪枝很困难

细分方法的优点

  • 提供几何体的粗略表示
  • 获得光滑的表示
  • 通过递归进行实现

image-20220104150438787

细分方法的缺点

  • 没有了参数化的表示

细分方法的基本步骤

  1. 细分当前多边形/网格
  2. 插入插值点(分裂)
  3. 移动点:局部加权平均(均一化)
    • 对于所有的点:逼近方法
    • 仅对于新生成的点:插值方法

image-20220104150754125

image-20220104150809205

2. 细分曲线

2.1. Corner Cutting Splines

image-20220104150950736

2.1.1. 基本流程:

  1. 将每条线段分为两半
  2. 顺时针地与其邻接点求平均
  3. 重复上述操作

能够收敛至二次B样条曲线

2.1.2. 矩阵表示

image-20220104151232751

记:

  • $l$阶控制点为:$\pmb p_i^{(l)}$
  • $l+1$阶分裂点为:$\tilde{\pmb p}_i^{(l+1)}$
  • $l+1$阶平均控制点:$\pmb p_i^{(l+1)}$

分裂操作的矩阵表示:
$$
\begin{pmatrix}
\vdots\\\tilde x_{2i}^{(l+1)}\\\tilde x_{2i+1}^{(l+1)}\\\vdots
\end{pmatrix}_{2n\times 1}=
\begin{pmatrix}
\ddots\\
&1\\
&\frac{1}{2}&\frac{1}{2}\\
&&1\\
&&\frac{1}{2}&\frac{1}{2}\\
&&&&\ddots
\end{pmatrix}_{2n\times n}
\begin{pmatrix}
\vdots\\ x_{i}^{(l)}\\ x_{i+1}^{(l)}\\\vdots
\end{pmatrix}_{n\times 1}
$$
平均操作的矩阵表示:
$$
\begin{pmatrix}
\vdots\\ x_{2i}^{(l+1)}\\ x_{2i+1}^{(l+1)}\\\vdots
\end{pmatrix}_{2n\times 1}=
\begin{pmatrix}
\ddots\\
&\frac{1}{2}&\frac{1}{2}\\
&&\frac{1}{2}&\frac{1}{2}\\
&&&&\ddots
\end{pmatrix}_{2n\times 2n}
\begin{pmatrix}
\vdots\\\tilde x_{2i}^{(l+1)}\\\tilde x_{2i+1}^{(l+1)}\\\vdots
\end{pmatrix}_{2n\times 1}
$$

2.1.3. Chaikin’s Corner Cutting表示方法

image-20220104152149469

  • 对每条边,插入$\frac{1}{4}$和$\frac{3}{4}$的点,删除旧点,进行重复操作
  • 极限曲线将是$C^1$连续的

对于第$k+1$阶细分,有:
$$
\begin{aligned}
P^{(k+1)}_ {2i}&=\frac{3}{4}P^{(k)}_ i+\frac{1}{4}P^{(k)}_ {i+1}\\\\
P^{(k+1)}_ {2i+1}&=\frac{1}{4}P^{(k)}_ i+\frac{3}{4}P^{(k)}_ {i+1}
\end{aligned}
$$
每次迭代,点数加倍,写成矩阵形式:
$$
\begin{pmatrix}
\vdots\\
p^{k+1}_{2i-2}\\
p^{k+1}_{2i-2}\\
p^{k+1}_{2i-2}\\
p^{k+1}_{2i-2}\\
p^{k+1}_{2i-2}\\
p^{k+1}_{2i-2}\\
\vdots
\end{pmatrix}_{2n\times 1}
=\frac{1}{4}
\begin{pmatrix}
\ddots\\
& 3 & 1 & 0 & 0\\
& 1 & 3 & 0 & 0\\
& 0 & 3 & 1 & 0\\
& 0 & 1 & 3 & 0\\
& 0 & 0 & 3 & 1\\
& 0 & 0 & 1 & 3\\
& & & & &\ddots\
\end{pmatrix}_{2n\times n}
\begin{pmatrix}
\vdots\\
p^{k+1}_{i-1}\\
p^{k+1}_{i}\\
p^{k+1}_{i+1}\\
p^{k+1}_{i+2}\\
\vdots\
\end{pmatrix}_{n\times 1}
$$

2.2. Lane - Riesenfeld Subdivision

2.2.1. 基本流程

  • 各条边加中点
  • 将每条边用中点代替,重复迭代$d$次($d+1$次B样条细分)

示例:

$d=2$

image-20220104152918481

image-20220104153155104
$$
\begin{aligned}
a_1&=\frac{A+B}{2}\\
c_1&=\frac{B+C}{2}
\end{aligned}
$$
image-20220104153300049
$$
\begin{aligned}
a_2&=\frac{B+a_1}{2}\\
c_2&=\frac{B+c_1}{2}
\end{aligned}
$$
image-20220104153350175
$$
\begin{aligned}
b_1&=\frac{a_2+c_2}{2}\\
&=\frac{a_1+2B+c_1}{4}\\
&=\frac{A+6B+C}{8}
\end{aligned}
$$
即:
$$
\begin{pmatrix}
a_1\\b_1\\c_1
\end{pmatrix}=
\frac{1}{8}\begin{pmatrix}
4&4&0\\
1&6&1\\
0&4&4
\end{pmatrix}
\begin{pmatrix}
A\\B\\C
\end{pmatrix}
$$

2.2.2. 三次B样条细分的矩阵表示

当$d=2$时,
$$
\begin{pmatrix}
\vdots\\
\pmb p_{2i}^{(l+1)}\\
\pmb p_{2i+1}^{(l+1)}\\
\vdots
\end{pmatrix}_{2n\times1}=
\begin{pmatrix}
\ddots\\
&\frac{1}{8}&\frac{3}{4}&\frac{1}{8}\\
&&\frac{1}{2}&\frac{1}{2}\\
&&\frac{1}{8}&\frac{3}{4}&\frac{1}{8}\\
&&&\frac{1}{2}&\frac{1}{2}\\
&&&&&\ddots
\end{pmatrix}_{2n\times n}
\begin{pmatrix}
\vdots\\
\pmb p_{i}^{(l)}\\
\pmb p_{i+1}^{(l)}\\
\vdots
\end{pmatrix}_{n\times 1}
$$
即:
$$
\begin{aligned}
\pmb p_{2i}^{(l+1)}&=\frac{1}{2}\pmb p_i^{(l)}+\frac{1}{2}\pmb p_{i+1}^{(l)}\\\\
\pmb p_{2i+1}^{(l+1)}&=\frac{1}{8}\pmb p_i^{(l)}+\frac{6}{8}\pmb p_{i+1}^{(l)}+\frac{1}{8}\pmb p_{i+2}^{(l)}
\end{aligned}
$$

将平均与分裂操作分开表示:
$$
\begin{pmatrix}
\vdots\\
\pmb p_{2i}^{(l+1)}\\
\pmb p_{2i+1}^{(l+1)}\\
\vdots
\end{pmatrix}_{2n\times1}=
\underbrace{
\begin{pmatrix}
\ddots\\
&\frac{1}{4}&\frac{1}{2}&\frac{1}{4}\\
&&\frac{1}{4}&\frac{1}{2}&\frac{1}{4}\\
&&&\frac{1}{4}&\frac{1}{2}&\frac{1}{4}\\
&&&&\frac{1}{4}&\frac{1}{2}&\frac{1}{4}\\
&&&&&&\ddots
\end{pmatrix}_{2n\times 2n}}_{\mathrm{averaging}}
\underbrace{
\begin{pmatrix}
\ddots\\
&1\\
&&\frac{1}{2}&\frac{1}{2}\\
&&&1\\
&&&\frac{1}{2}&\frac{1}{2}\\
&&&&&\ddots
\end{pmatrix}_{2n\times n}}_{\mathrm{spliting}}
\begin{pmatrix}
\vdots\\
\pmb p_{i}^{(l)}\\
\pmb p_{i+1}^{(l)}\\
\vdots
\end{pmatrix}_{n\times 1}
$$
极限曲线具有$C^2$连续性

核表示为:
$$
h=\frac{1}{8}[\cdots,0,0,1,4,6,4,1,0,0,\cdots]
$$
对于一般情况,核为:
$$
\frac{1}{2^{d+1}}\left(\dots,C_{d+2}^0,\dots,C_{d+2}^{d+2},\dots\right)
$$

2.2.3. 谱收敛分析

谱极限技巧

为了解决以下问题:

  • 为了得到良好的逼近需要进行多次细分
  • 过多的细分可能会导致控制点过剩(类比LOD)
  • 能否直接计算控制点的极限位置?

image-20220104161649609

注意到:

  • 每一个曲线上的点只受一定数量的控制点影响
  • 每个点$\pmb p^{(l+1)}$影响的范围均小于$\pmb p^{(l)}$的影响范围
  • 对于每个邻域,都使用相同的细分矩阵

以三次B样条细分为例,
$$
\left( \begin{array} { c }
{ x _ { - } ^ { ( l + 1 ) } } \\
{ x ^ { ( l + 1 ) } } \\
{ x _ { + } ^ { ( l + 1 ) } } \end{array}
\right)
= \left( \begin{array} { c c c } { \frac { 1 } { 2 } } & { \frac { 1 } { 2 } } & { 0 } \\
{ \frac { 1 } { 8 } } & { \frac { 3 } { 4 } } & { \frac { 1 } { 8 } } \\
{ 0 } & { \frac { 1 } { 2 } } & { \frac { 1 } { 2 } }
\end{array} \right)
\left( \begin{array} { c }
{ x _ { - } ^ { ( l ) } } \\
{ x ^ { ( l ) } } \\
{ x _ { + } ^ { ( l ) } }
\end{array} \right)
$$
其中,

  • $x_-$为左邻域点
  • $x$为当前点
  • $x_+$为右邻域点

对转移矩阵进行相似对角化:
$$
M
=\left( \begin{array} { c c c }
{ \frac { 1 } { 2 } } & { \frac { 1 } { 2 } } & { 0 } \\
{ \frac { 1 } { 8 } } & { \frac { 3 } { 4 } } & { \frac { 1 } { 8 } } \\
{ 0 } & { \frac { 1 } { 2 } } & { \frac { 1 } { 2 } }
\end{array} \right)
=\left( \begin{array} { c c c }
{ 1 } & { -1 } & { -2 } \\
{ 1 } & { 0 } & { 1 } \\
{ 1 } & { 1 } & { -2 }
\end{array} \right)
\left( \begin{array} { c c c }
{ 1 } & { 0 } & { 0 } \\
{ 0 } & { \frac{1}{2} } & { 0 } \\
{ 0 } & { 0 } & { \frac{1}{4} }
\end{array} \right)
\left( \begin{array} { c c c }
{ \frac{1}{6} } & { \frac{2}{3} } & { \frac{1}{6} } \\
{ -\frac{1}{2} } & { 0 } & { \frac{1}{2} } \\
{ -\frac{1}{6} } & { \frac{1}{3} } & { -\frac{1}{6} }
\end{array} \right)\triangleq UDU^{-1}
$$
则求极限:
$$
\begin{aligned}
\begin{pmatrix}
x_-^{(\infty)}\\x^{(\infty)}\\x_+^{(\infty)}
\end{pmatrix}&=
\lim_{l\rightarrow\infty}M^l\begin{pmatrix}
x_-^{(0)}\\x^{(0)}\\x_+^{(0)}
\end{pmatrix}\\
&=\lim_{l\rightarrow\infty}UD^lU^{-1}\begin{pmatrix}
x_-^{(0)}\\x^{(0)}\\x_+^{(0)}
\end{pmatrix}\\
&=U\lim_{l\rightarrow\infty}D^lU^{-1}\begin{pmatrix}
x_-^{(0)}\\x^{(0)}\\x_+^{(0)}
\end{pmatrix}\\
&=U\lim_{l\rightarrow\infty}\begin{pmatrix}
1&0&0\\
0&0&0\\
0&0&0
\end{pmatrix}U^{-1}\begin{pmatrix}
x_-^{(0)}\\x^{(0)}\\x_+^{(0)}
\end{pmatrix}
\end{aligned}
$$
解得:
$$
x^{(\infty)}=\begin{pmatrix}\dfrac{1}{6}&\dfrac{2}{3}&\dfrac{1}{6}\end{pmatrix}\begin{pmatrix}
x_-^{(0)}\\x^{(0)}\\x_+^{(0)}
\end{pmatrix}
$$

  • 收敛的必要条件:最大特征值的绝对值应为1
  • 仿射不变性要求局部矩阵行和为 1,这意味着 $\pmb{1}$ 向量必须是特征值 $1$ 的特征向量

3. 细分曲面

3.1. 张量积B样条细分曲面

  • 从一个四边形网格出发
  • 对每一步细分操作
    • 将每个四边形划分成四个(四叉树细分)
    • 对顶点进行线性插值
    • 使用二维的平均掩膜

image-20220104163633925

image-20220104163801566

3.1.1. 双二次细分曲面

image-20220104163833077

B样条块的矩阵表示:
$$
P(u,v)=
\begin{pmatrix}
1&u&u^2
\end{pmatrix}
MPM^T
\begin{pmatrix}
1\\v\\v^2
\end{pmatrix}
$$
其中,
$$
\begin{aligned}
M&=\frac{1}{2}\begin{pmatrix}
1&1&0\\
-2&2&0\\
1&-2&1
\end{pmatrix}\\\\
P&=\begin{pmatrix}
P_{0,0}&P_{0,1}&P_{0,2}\\
P_{1,0}&P_{1,1}&P_{1,2}\\
P_{2,0}&P_{2,1}&P_{2,2}
\end{pmatrix}
\end{aligned}
$$
考虑$2\times2$块中的一个象限,例如$u,v\in[0,\frac{1}{2}]$,考虑新的曲面块$P'$参数为$u'=\frac{u}{2}$和$v'=\frac{v}{2}$

则有:
$$
\begin{aligned}
P^\prime(u,v)
&=P(\frac{u}{2},\frac{v}{2})\\\\
&=\left[\begin{matrix}
1&\frac{u}{2}&\frac{u^2}{4}
\end{matrix}\right]MPM^\top
\left[\begin{matrix}
1\\\frac{v}{2}\\\frac{v^2}{4}
\end{matrix}\right]\\\\
&\dots\\\\
&=\left[\begin{matrix}
1 & u & u^2
\end{matrix}\right]MP^\prime M^\top \left[\begin{matrix}
1\\v\\v^2
\end{matrix}\right]
\end{aligned}
$$
其中,
$$
P^\prime=SPS^T
$$

$$
S=M^{-1}\left[\begin{matrix}
1 & 0 & 0\\
0 & \frac{1}{2} & 0\\
0 & 0 & \frac{1}{4}
\end{matrix}\right]M=\frac{1}{4}\left[\begin{matrix}
3 & 4 & 0\\
1 & 3 & 0\\
0 & 3 & 1
\end{matrix}\right]
$$

image-20220104165539088

3.1.2. 双三次细分曲面

B样条块的矩阵表示:
$$
P(u,v)=
\begin{pmatrix}
u^3&u^2&u&1
\end{pmatrix}
MPM^T
\begin{pmatrix}
u^3\\u^2\\u\\1
\end{pmatrix}
$$
其中,
$$
M=\frac{1}{6}\begin{pmatrix}
-1&3&-3&1\\
3&-6&3&0\\
-3&0&3&0\\
1&4&1&0
\end{pmatrix}
$$
同样考虑$3\times 3$曲面块的一个象限,例如$u,v\in[0,\frac{1}{2}]$,考虑新的曲面块$P'$参数为$u'=\frac{u}{2}$和$v'=\frac{v}{2}$

能够得到相似的结果:
$$
\begin{aligned}
P'&=SPS^T\\\\
S&=\frac{1}{8}\begin{pmatrix}
4 & 4 & 0 & 0\\
1 & 6 & 1 & 0\\
0 & 4 & 4 & 0\\
0 & 1 & 6 & 1
\end{pmatrix}
\end{aligned}
$$

3.1.3. 细分与平均掩膜Mask

细分掩膜

image-20220104171335453

平均掩膜

image-20220104171356648

3.2. Catmull-Clark Subdivision

3.2.1. 动机

B样条细分曲面存在的问题:

  • 仅适用于内部或常规四边形网格
  • 相比标准的B样条构造并没有灵活性优势
  • 需要一个更好的方法:
    • 处理任意拓扑的四边形网格
    • 处理边界区域的情况

解决方法:Catmull-Clark细分方法

3.2.2. 算法流程

img

记:

  • 对于不是四边形的面,称为Non-quad face
  • 所有度不为4的顶点称为奇异点

算法流程:

  1. 在每个面中添加一个点,每条边的中点也添加一个点,面上的新顶点连接所有边上的新顶点,如图所示:

    img

    可以看到:

    • 有几个非四边形面就会多出几个奇异点
    • 新多出来的奇异点的度数与原来所在面的边数相等
    • 第一次细分后所有面都会变成四边形面,且往后奇异点数目不再增加
  2. 进行顶点位置的偏移

    • 对于面顶点

      image-20220104195149228
      $$
      f=\frac{v_1+v_2+v_3+v_4}{4}
      $$

    • 对于边顶点

      image-20220104195247894
      $$
      e=\frac{v_1+v_2+f_1+f_2}{4}
      $$

    • 对于原来的顶点

      image-20220104195423190
      $$
      v=\frac{f_1+f_2+f_3+f_4+2(m_1+m_2+m_3+m_4)+4p}{16}
      $$
      其中,$m$为边中点,$p$为旧顶点

image-20220104200010961

3.3. 三角细分

3.3.1. 基本流程

  • 使用1:4三角划分
  • 重复:
    • 使用线性插值进行分裂操作
    • 应用平均掩膜

image-20220104200437491

3.3.2. Loop细分

算法流程:

  1. 将每个三角形一分为四(4:1细分)

    4-1 Subdivision

    • 先分裂三角网格的每一条边

    • 若新边一端为新顶点,另一端为旧顶点,则进行翻转

      Subdivision via flipping

  2. 对新生成的顶点赋予权重

    Loop subdivision weights

3.3.3. Butterfly细分

image-20220104201103502

  • 原来的顶点保持不变(插值)
  • 新点取平均
  • $C^1$连续,除了异常顶点
分享

Wenbo Chen
作者
Wenbo Chen
CG Student

目录