网址在这里

Introduction

这个笔记由几位专业人士准备，因而感觉非常好读。主要关于subdivision，从最基础的数学介绍到应用，还有一些bonus代码。

Advantages:

• arbitrary topology
• scalability
• uniformity of representation
• numerical stability
• code simplicity.

比起样条（spline）更便利，同时是recursive structure，方便实现和计算，效率比较高。

Foundations I: Basic Ideas

细分思想

先从插值细分（Interpolating Subdivision）开始讲起。我个人理解是，在一段线段里再插入几个点，让线段变成几条小线段，从而使折线更平滑。原来的点不变，只是多了插入的点。

Subdivision defines a smooth curve or surface as the limit of a sequence of successive refinements.

也就是说，细分是想用有限的序列不断地精细化，来表现平滑曲线曲面。
在插值细分中，需要确定一个规则，即如何决定在哪里插入新的点。不同的规则自然会导致不同平滑度和不同形状的曲线曲面。
规则需要考虑到的点有以下几条：

• Efficiency：用少量浮点运算计算新点位置，e.g. 加权平均
• Compact support: 当一个点插入时，其影响应当是有限的，能够控制住的
• Local definition: 新点的计算规则不应该基于较远的点
• Affine invariance: 点集的affine transformation不会影响曲线曲面的形状，e.g. 加权平均中权重和为1
• Simplicity: 规则要简明
• Continuity: 注意产生的曲线曲面的连续性和可微性

细分与其他方式的对比：

• Efficiency: 细分是比较高效的。其实有些细分就是spline modeling中knot insertion的推论和归纳。但是隐式曲面（不是很懂）计算就比较低效了。

An algorithm such as marching cubes is required to generate the polygonal approximation needed for rendering.Variational surfaces can be even worse: a global optimization problem has to be solved each time the surface is changed.

• Arbitrary topology: 细分是在研究者们尝试解决spline的任意拓扑问题时产生的。这个也是隐式曲面的特长所在。（不是很懂）
• Surface features: 即对于形状大小的控制。variational surfaces很好，灵活性高，也能精确创造性状。隐式曲面则不行。spline虽然可以，但是计算上非常低效。细分比spline好。
• Complex geometry: 这个应该是subdivision的专长了，由于是计算决定精细度，很容易实现level-of-detail rendering。

复习样条的内容

Splines are piecewise polynomial curves of some chosen degree.

样条是B-样条（即basis spline）的线性组合。这些B-样条是控制点的系数。想要连接样条，连接处的曲线段的各级导数最好是相等的，这样才能维持住spline整体的连续性。同时控制点的移动仅会影响一小部分的曲线。这里有一个小动画，通过拖动控制点，可以很清楚地看到其移动带来的影响是local的。p.s. 加载可能要vpn

下面介绍如何用repeated convolution构建B-splines。

x(t) = ∑x_iB^i_0(t)
_表示下标，^表示上标。目前没找到在markdown里加latex的方法……

如果 x(t) 是piecewise constant coordinate functions，那么 B_0(t) 就是一个box function，在 [0,1) 上为1，其他为0。然后上标 i 表示translation，即把 B_0(t) 右移 i。

the continuous convolution of two functions f and g: (f ⊗ g)(t) = integrate{ f(s) g(t−s) ds }.

于是B_1(t)= integrate{ B_0(s) B_0(t−s) ds }，是一个linear hat function。

于是a B-spline of degree p可以归纳为：

B_p(t)= integrate{ B_p−1(s) B_0(t−s) ds }.

其连续性有以下定理：

Theorem 1 If f(t) is C^k continuous, then (B_0 ⊗ f )(t) is C^k+1 continuous.

即一个n级spline是C^n-1 continuous。

B-样条的微调能力

B-样条遵从一个refinement equation。这是一条连接样条和细分的性质。

In other words, the B-spline of degree l can be written as a linear combination of translated (k) and dilated (2t) copies of itself.