3.4 曲线的弧长参数化[3]

有了路径，还需要能够方便地在路径上匀速运动，其他运动可以由匀速运动变化和复合得到。从朴素的需求角度出发，我们希望曲线的参数t与曲线的长度L为线性关系：

此时，我们可以仅通过参数t的匀速变化得到点在曲线上的匀速移动。显而易见，这个关系只有直线自然成立。

对于大于一次的多项式曲线，这里采用如下处理方式。

设为连接点的曲线，其在间的长度为L；另设参数u，建立和曲线长度的线性关系：

即由参数u表达的曲线长度计算函数；设一个参数u到参数t的变换t(u)，且满足t(0)=0, t(1)=1。将变换带入曲线参数方程中，可以得到一个新的曲线参数方程：

由于的长度函数为，在此变换下对应的长度函数应有

从而变换为

为得到变换，需要求出的反函数。

由于没有解析解，这里采用最小二乘法进行拟合求近似解。

（1）在[0,1]区间进行等曲线长度的划分，得到n条等长曲线段，对应的参数区间为。

（2）对每一条曲线段，采样m个在该区间的值，得到点集,…,，其中,。

（3）以长度为自变量，用最小二乘法拟合满足采样点的多项式方程，得到在区间的近似解。

（4）在剩余的区间重复步骤2和步骤3，求出在所有区间的近似解，则组成的分段函数。

步骤1划分等曲线长度区间的目的是消除使用时查找分段函数表的遍历操作。当使用三次多项式作为拟合的基函数时，其系数可以用Vector4保存，则的分段函数可以保存为Vector4的数组Vector4[n]。对于给定的长度l，在等曲线长度的划分下，其对应的分段函数的系数索引为Clamp((int)((l/L)*n),0, n-1)。如果是其他形式的不满足等曲线长度的划分，则需要额外记录每个划分的长度，在使用时遍历Vector4[n]找到l对应的分段函数的系数。

在步骤1使用等曲线长度区间划分时，由于此时尚未求出，只能使用迭代法寻找等长划分点。这里使用Newton-Raphson法[4]来求解方程：

其迭代形式为

其中，A、B、C 参见“端点间二次样条的构建”。为严格单调函数，适合使用Newton-Raphson法。可以将同样划分数量下同序号的等参间隔点作为迭代的初值t i(0)以加速收敛。

构造的计算量分析如下：

（1）寻找等曲线长度的划分点，默认最大迭代次数为10，在实际计算过程中到不了这个次数就会收敛。n个划分需要求解n-1个划分点，总迭代次数≤10(n-1)。

（2）对每条曲线段进行m次的采样，排除两个已经计算的端点，总的调用次数为n(m-2)。

（3）在最小二乘法拟合部分，设Kp为拟合多项式的阶数，则构造方程系数矩阵的复杂度为，用高斯消元法求解部分的复杂度为。

（4）的计算不受刚体变换的影响，不需要针对刚体变换重新计算。

项目中，n=20,m=11,，连接两个路点的曲线需要用80个浮点数表示。如果需要运行时动态构建曲线，为避免计算量过大造成卡顿，可以采用分帧计算的方法将计算量分摊到多帧。注意到每段路径之间没有相互依赖，只共享路点信息，也可以采用多线程并行计算。另外，根据项目情况也可以适当降低分段数目和采样点数目。

将表示的带入原曲线方程中，得到新的归一化曲线方程：

其对应的长度计算为

对于使用弧长参数化后的曲线方程gs(u)，其求值的计算比原始的曲线方程fs(t)多一次多项式求值的计算（具体而言，使用三次多项式拟合，多了3次加法、5次乘法、1次除法），但是对应的长度计算大幅简化，只需要1次乘法。

弧长参数化后的曲线方程gs(u)与原始的曲线方程fs(t)在等参取点时的对比如图3.3所示。

图中上面的为原始曲线，下面的为弧长参数化后的曲线，重参数化后，等参对应曲线上的等距。