第3章 NURBS曲线求值

第3章：NURBS曲线求值——de Boor算法、Horner算法与曲线点计算

好，咱们进入正题。

NURBS曲线写进CNC系统里，最终目的是什么？说白了，就是让刀尖沿着曲线走。那问题来了——你手里只有控制点、权因子和节点向量，怎么算出曲线上任意一点的位置？

这就是本章要聊的：NURBS曲线求值。

我个人习惯把求值方法分成两类：一类是通用型，适合任意阶次；另一类是优化型，适合特定场景。咱们一个一个说。

3.1 de Boor算法——通用求值利器

de Boor算法，你可以把它理解成“B样条曲线的递推求值法”。它不依赖曲线的特殊结构，只要是B样条或NURBS，都能算。

它的核心思想是：通过线性插值，逐步降低曲线阶次，直到得到点坐标。

de Boor递推公式（B样条部分）：

给定：控制点 d_i (i=0..n)，阶次 p，节点向量 u_j
对于参数 u ∈ [u_k, u_{k+1})，定义：
d_i^0 = d_i
d_i^r = (1 - α_i^r) * d_{i-1}^{r-1} + α_i^r * d_i^{r-1}
其中：
α_i^r = (u - u_i) / (u_{i+p+1-r} - u_i)
r = 1..p, i = k-p+r .. k
最终结果：C(u) = d_k^p

嗯，公式看着有点吓人。我刚开始学的时候也懵，后来在项目里手算过一次就明白了。

举个例子：一条3阶（p=2）B样条曲线，节点向量是 [0,0,0,1,2,3,3,3]，控制点有5个。我想算 u=1.5 处的点。

第一步，找到 u 所在的节点区间。1.5 在 [1,2) 之间，所以 k=3（节点索引从0开始）。

第二步，开始递推。从 r=1 开始，算出一层新点；再 r=2，算出最终点。每次插值用的 α 系数，都跟当前节点区间有关。

我的经验：de Boor算法在CNC里最大的好处是数值稳定。我曾经在调试五轴联动时，用另一种方法算曲线点，结果在节点边界处出现抖动。换成de Boor，问题立刻消失。所以，如果你对精度要求高，或者曲线阶次高，我建议优先用de Boor。

3.2 Horner算法——多项式求值的“快刀”

Horner算法，你可能更熟悉它的另一个名字：秦九韶算法。它专门用来高效计算多项式。

NURBS曲线在节点区间内，其实可以写成有理多项式形式。这时候，Horner就派上用场了。

Horner算法原理（以三次多项式为例）：

给定多项式：P(t) = a0 + a1*t + a2*t^2 + a3*t^3
Horner形式：P(t) = ((a3*t + a2)*t + a1)*t + a0
计算量：3次乘法 + 3次加法（传统方法需要9次乘法）

你想想看，如果一条NURBS曲线有几百个节点区间，每个区间都要算几十个点，Horner能省多少计算量？

不过，这里有个坑——Horner算法只适用于多项式形式。NURBS曲线在节点区间内是分片有理多项式，所以你得先把B样条基函数的多项式系数提取出来，才能用Horner。

我曾经踩过的坑：有一次，我图省事，直接用Horner算法去算整条NURBS曲线，没做分片处理。结果在节点处出现了不连续。后来才意识到，NURBS是分片定义的，每个区间多项式不同，不能一把梭。所以，用Horner之前，一定先确认你处理的是单个节点区间内的多项式。

3.3 曲线点计算——从理论到代码

好了，理论讲完，咱们看看实际怎么写代码。

我个人习惯把NURBS曲线点计算分成三步：

参数预处理：把刀路里的参数 u 映射到节点向量区间
基函数计算：用de Boor或标准递推算出B样条基函数值
加权求和：把控制点、权因子、基函数组合起来，得到最终坐标

下面是一个简化版的C语言实现，核心是de Boor算法：

// NURBS曲线求值 - de Boor算法实现
// 输入：参数 u，节点向量 knot，控制点 ctrlPts，权因子 weights，阶次 p
// 输出：曲线点坐标 (x, y, z)

void nurbsEval(double u, double* knot, double* ctrlPts, 
               double* weights, int p, double* result) {
    // 1. 找到节点区间索引 k
    int k = findSpan(u, knot, p);
    
    // 2. 复制控制点与权因子到临时数组
    double d[10][3]; // 假设最多10个控制点
    double w[10];
    for (int i = k-p; i <= k; i++) {
        d[i][0] = ctrlPts[i*3];
        d[i][1] = ctrlPts[i*3+1];
        d[i][2] = ctrlPts[i*3+2];
        w[i] = weights[i];
    }
    
    // 3. de Boor递推
    for (int r = 1; r <= p; r++) {
        for (int i = k-p+r; i <= k; i++) {
            double alpha = (u - knot[i]) / (knot[i+p+1-r] - knot[i]);
            // 对坐标和权因子同时做线性插值
            for (int j = 0; j < 3; j++) {
                d[i][j] = (1-alpha)*d[i-1][j] + alpha*d[i][j];
            }
            w[i] = (1-alpha)*w[i-1] + alpha*w[i];
        }
    }
    
    // 4. 有理化：除以权因子
    result[0] = d[k][0] / w[k];
    result[1] = d[k][1] / w[k];
    result[2] = d[k][2] / w[k];
}

实际项目中的优化点：

如果曲线阶次固定（比如CNC里常用3阶），可以把de Boor循环展开，减少分支判断
权因子递推可以跟坐标递推合并，减少一次除法
节点区间查找用二分法，比顺序查找快很多

3.4 两种算法的对比与选择

我整理了一个表格，方便你根据场景选：

对比项	de Boor算法	Horner算法
适用范围	任意B样条/NURBS	仅多项式形式
数值稳定性	高（递推过程稳定）	中（高次多项式可能振荡）
计算效率	O(p²)	O(p)
代码复杂度	中等	低
推荐场景	高精度插补、变阶次曲线	固定阶次、批量计算

我个人在CNC插补器里，默认用de Boor。原因很简单：它不需要预处理，直接拿控制点和节点向量就能算，而且数值稳定性好。Horner算法我一般用在离线预处理阶段，比如把NURBS曲线转成等距点云时，用它批量算点会快很多。

3.5 本章知识体系

下面这张图，帮你理清本章的核心逻辑：

这张图把求值流程画得很清楚。你从输入出发，先判断是否需要多项式形式。如果不需要，直接走de Boor；如果需要，先提取多项式系数，再用Horner加速。两条路最终都汇到曲线点坐标。

好了，关于NURBS曲线求值，咱们就聊到这儿。de Boor和Horner各有千秋，选哪个取决于你的场景。我个人建议：通用场景用de Boor，批量计算用Horner。记住这个原则，你在实际项目中就不会选错。

本章要点回顾：

de Boor算法：递推插值，数值稳定，适合任意阶次NURBS
Horner算法：多项式嵌套乘法，计算高效，适合批量处理
曲线点计算三步走：参数预处理 → 基函数计算 → 加权求和
实际项目中，de Boor是默认选择，Horner用于离线优化

📚 课程目录