Hermite曲线

Project Warship绝赞推进中。虽然说依然停留在船体生成器的部分，但其实现在已经重构到了V3了，里面最重要的部分就是如何从只是长宽高这样的数值数据构建出一个形状美观合理的船体出来。V3的代码还没有完工进行测试，但我对V3的效果还是有着蛮高的期望的。趁着需要调查装甲结构改动V3部分代码的时间来把船体生成器目前为止的进化过程记录一下。

样条曲线

样条是个什么玩意？简单来说就是可以以函数和控制点来定义曲线，常见的有比如B样条。样条这个名字的来源还挺有意思，英文是spline，一开始指的是

A long, narrow, and relatively thin piece or strip of wood, metal, etc.^1

还有一个更晚一点的

flexible strip of wood or hard rubber used by draftsmen in laying out broad sweeping curves^1

总之似乎一开始是形容木工里一小条什么东西。大陆一开始把这个翻译成齿函数，似乎是更形象一些，但后来因为工程学术语中放样一词就都在用样条了。比起放样，一方面很在意“样”字的偏旁是木，另一方面早期的英语解释也都提到木头，难不成是老祖宗在用木头搓手办的时候就已经在用这种方法了。

优先考虑的是俯瞰甲板的形状。船的总长度设定好了之后，先定义了一个甲板宽度的数组，一开始是5个数，再加上艏艉最尖端的宽度为0一共七个点，需要用一条平滑的曲线来连接。

Catmull-Rom

通常的样条曲线都是不过控制点的，但因为我这里是给定了的宽度，一定要经过设定的控制点，于是采用了三次Catmull-Rom插值样条曲线，形式如下：

给定四个控制点 $P_{i-1}, P_i, P_{i+1}, P_{i+2}$ ，样条在区间 $[ P_i, P_{i+1} ]$ 上的插值曲线定义为：

$\begin{align*} C(t) = \tfrac{1}{2} \Big[ \, & (2P_i) \\ + & (-P_{i-1} + P_{i+1})t \\ + & (2P_{i-1} - 5P_i + 4P_{i+1} - P_{i+2})t^2 \\ + & (-P_{i-1} + 3P_i - 3P_{i+1} + P_{i+2})t^3 \Big] \end{align*}$

$t=0$ 时曲线必在 $P_i$ ， $t=1$ 时曲线必在 $P_{i+1}$ ，也就是说这个曲线必然经过中间两个控制点。在绘制曲线的时候，对七个点中间的六段每一段选取这样四个控制点（首尾的话同样的点重复两次），就可以得到一条经过每一个点的平滑曲线。

Catmull-Rom因为这个特点常被用作路径的插值中，比如游戏内NPC或摄像机的轨迹，或者也可以是具体的动画中某个IK的轨迹。虽然经过特定的点这一条件满足了，但一方面这个曲线是针对每一段单独定义的，另一方面它只有一次导数连续，导致了在某些奇奇怪怪的地方并不是很平滑。

插值

除了甲板宽还定义了水线宽和船底宽，这三条曲线之间的部分在V1里面就直接用线性插值来过渡了，显然不是明智之举。V2的改动主要是加了一些像鱼类鼓包、艏楼之类的小细节的逻辑，同时也把水线以下的插值方法细化了一下，加上了渐入渐出（ease in/ease out）的曲线。

渐入渐出这些如果做动画或者剪辑应该经常能见到，这两个的数学形式其实很简单，渐入就是 $t^k$ ，渐出就是 $1-(1-t)^k$ ， $k$ 用来控制渐入渐出的速度， $k=1$ 的时候就刚好是一条直线，也就是线性插值。在线性插值，也就是unity的Mathf.Lerp()里直接使用渐入或者渐出的公式作为 $t$ ，就能做出对应的形状。

为了解决在奇奇怪怪的地方不平滑的问题，我直接又定义了一堆固定位置的控制点，然后选用了Hermite曲线来直接连接各个控制点。Hermite曲线是直接由两个点和在两个点上的切向来定义的三次插值曲线，形式如下：

给定端点 $P_0, P_1$ 和它们的切向 $T_0, T_1$ ，则曲线定义为：

$C(t) = h_0(t)P_0 + h_1(t)P_1 + h_2(t)T_0 + h_3(t)T_1$

其中的四个Hermite基函数：

$\begin{align*} h_0(t) &= 2t^3 - 3t^2 + 1 \\ h_1(t) &= -2t^3 + 3t^2 \\ h_2(t) &= t^3 - 2t^2 + t \\ h_3(t) &= t^3 - t^2 \end{align*}$

保证Hermite曲线既经过端点，又符合端点的切向量。

Hermite也是一次导连续，但因为是由切向控制，如果是在编辑器内调整将会非常直观，尤其是在定义的某些控制点处，可能刚好是船体的一个折角，两侧的切向本来就不同，那么两侧的Hermite曲线分别定义，就可以轻松做出折角。

贝塞尔，B样条，和NURBS

Hermite虽好，但这个依然是常用在动画领域而非建模，原因是它不够精确。但考虑到精确度的问题，构造这些曲线本来就是为了去采样一些稀疏的点构造模型网格，精确度本身没有在追求，Hermite的直观特点也会对不太了解这方面的玩家非常友好，当前的目标就是尽快实现基于Hermite的网格生成来检查一下效果。

但万一遇到了比较专业的玩家，这里也探索一下业界使用的标准，也就是B样条和NURBS，这两个都是在工业建模中经常使用。

贝塞尔曲线（Bézier Curve）

说这两个之前还是得先来说说贝塞尔曲线。贝塞尔曲线是基于 Bernstein 多项式的参数曲线，必经过首尾点，中间还可以有任意个控制点，每个控制点都会影响整条曲线的形状。其定义为：

$B(t) = \sum_{i=0}^n P_i \binom n i (1 - t)^{n - i}t^i$

其中 $P_i$ 是每个控制点，一共有 $n$ 个。

Photoshop里的钢笔工具使用的就是4点贝塞尔，其实我在用的Hermite曲线也是4点贝塞尔的一种转换形式。贝塞尔曲线必定内切其控制点多边形，对于4点贝塞尔来说， $P_0$ 和 $P_1$ 的连线其实和Hermite中的 $T_0$ 方向一致，只不过二者的大小因为公式定义不同需要转换。

B样条（B-spline）

B样条的这个B是Basis，也就是基函数的意思，所以B样条也可以叫基样条。其定义为：

$P(t) = \sum_{i=0}^n P_i N_{i,k}(t)$

其中这个 $N_{i, k}(t)$ 就是一个神奇的基函数，定义为：

$N_{i,1}(t) = \begin{cases} 1, & u_i \leq t < u_{i+1} \\ 0, & \text{otherwise} \end{cases}$

$\begin{align*} N_{i,k}(t) &= \frac{t - u_i}{u_{i+k-1} - u_i} \, N_{i,k-1}(t) \;\\&+\; \frac{u_{i+k} - t}{u_{i+k} - u_{i+1}} \, N_{i+1,k-1}(t) \end{align*}$

具体含义可能有点难以理解，这里的 $k$ 是阶数，三次B样条的话阶数就是4。注意 $N_{i,1}(t)$ 的定义可以发现 $t$ 并非限制在 $[0, 1]$ ，这里的 $u_i$ 是节点向量的一项，用来划分各个控制点的区间，结合下面的递归函数可以发现，阶数代表着每一个控制点会影响到几段曲线，同时阶数越高也意味着连续性越高（三次B样条二次导连续，二次B样条一次导连续）。但因为递归带来的计算复杂性，通常使用三次B样条就能得到足够的平滑度，以及在局部控制盒总体控制当中取得平衡。

NURBS

非均匀有理B样条（Non-Uniform Rational B-Spline）简称NURBS，其实就是规则多了一些的B样条。

非均匀的部分体现在节点向量当中每个节点之间不一定等间距，从而可以让曲线在某些地方更紧或更松，实现的方法就是故意去降低某些节点的影响范围。

有理则是在基函数部分加入了权重的定义，即：

$R_{i, k}(t) = \frac{w_i N_{i, k}(t)}{\sum_{j=0}^n w_j N_{j, k}(t)}$

这又是N又是J又是t的，不禁让人想起了某个头眼很疼的游戏。

总之，NURBS给了超灵活的控制。甚至可以推广到二维，定义好了的话说不定一个NURBS曲面就能定义整个船，但这对于需要随时造船的游戏来说有点拿战列舰主炮打鱼雷艇的意思了。

最后再说两句

我这是又看了一遍B样条才发现我用的Hermite结果就是贝塞尔，也算是把还给老师的知识又重新要回来了。

因为最终的游戏存储每一艘船希望是以Hulldata.json的形式，在对局的时候根据参数把船搭建起来，只有舰炮之类的读取模型，所以希望船体生成器的底层逻辑能够尽可能简单以加快速度。从各个方面来讲，Hermite都足够满足需求了，NURBS就算能在某些非常细节的地方带来提升，但这些细节到底会不会因为网格采样的问题被模糊掉？或者可以以特殊情况来专门处理，有更方便的解决方案？

因为写代码的时候很注意模块化，真的想把Hermite换成NURBS应该也不算困难，关键在于到了玩家手里之后的编辑器，能否轻松的实现对NURBS进行编辑得到这些细节？读取文件生成模型的时候能否尽可能快的生成出来，还是说这样就需要保存模型直接读取了？

大概等Hermite的网格生成出来之后这些问题的答案也就都有了。下一次记录应该会是船体编辑器界面的各种Gizmo相关的内容，这部分我还从没碰过，UI的部分也会比较多，希望不会让我很恼吧。

~~后面会再加一点Chart.js来演示文中提到的各种曲线，不过大概要等网站发布前后。~~

↑已完成，Chart.js真好用。