引言
B样条曲线（B-Spline Curve）是计算机图形学和几何建模中的核心工具，它通过一组控制点和节点向量定义了一条平滑、可控的参数曲线。与贝塞尔曲线相比，B样条具有局部控制性——修改一个控制点只会影响曲线的一部分而非整体。这一特性使其在游戏开发中广受欢迎：角色移动路径平滑、相机轨道插值、UI动画缓动、赛车游戏赛道生成等场景都离不开B样条。本文将用Java实现均匀B样条的de Boor递推算法，深入讲解节点向量与基函数的数学原理，并提供可直接运行的路径平滑系统。
算法核心思想
B样条的数学定义
一条p次B样条曲线定义为：
C(u) = Σ Ni,p(u) · Pi
其中：
– Pi 是控制点（i = 0, …, n）
– Ni,p(u) 是p次B样条基函数
– u 是参数，定义在节点向量上
节点向量与基函数
节点向量 U = {u0, u1, …, um} 是一个非递减序列，其中 m = n + p + 1。基函数通过Cox-de Boor递推公式定义：
- 0次（p=0）：Ni,0(u) = 1 若 ui ≤ u < ui+1，否则为0
- p次：Ni,p(u) = (u – ui)/(ui+p – ui) · Ni,p-1(u) + (ui+p+1 – u)/(ui+p+1 – ui+1) · Ni+1,p-1(u)
de Boor算法
de Boor算法是B样条求值的数值稳定算法，类似于贝塞尔曲线的de Casteljau算法。对于参数u ∈ [uk, uk+1)，通过逐层插值计算曲线上的点：
- 确定u所在的节点区间 [uk, uk+1)
- 取出相关的p+1个控制点 dk,0 = Pk-p, …, dk,0 = Pk
- 进行p轮递推：dk,j = (1 – α) · d(k-1),(j-1) + α · d(k),(j-1)
- 最终dk,p即为曲线上的点
Java实现
import java.util.*;
/**
* B样条曲线（B-Spline Curve）实现
* 支持均匀/非均匀节点向量，使用de Boor算法求值
*/
public class BSplineCurve {
// 二维点/向量
static class Vec2 {
double x, y;
public Vec2(double x, double y) {
this.x = x;
this.y = y;
}
public Vec2 add(Vec2 other) {
return new Vec2(x + other.x, y + other.y);
}
public Vec2 scale(double s) {
return new Vec2(x * s, y * s);
}
@Override
public String toString() {
return String.format("(%.3f,%.3f)", x, y);
}
}
private List<Vec2> controlPoints; // 控制点
private double[] knots; // 节点向量
private int degree; // 次数p
private int n; // 控制点数量减1
/**
* 构造函数
* @param controlPoints 控制点列表
* @param degree 曲线次数（1=线性，2=二次，3=三次）
* @param uniform 是否使用均匀节点向量
*/
public BSplineCurve(List<Vec2> controlPoints, int degree, boolean uniform) {
if (controlPoints.size() < degree + 1) {
throw new IllegalArgumentException("控制点数量必须 >= 次数 + 1");
}
this.controlPoints = new ArrayList<>(controlPoints);
this.degree = degree;
this.n = controlPoints.size() - 1;
if (uniform) {
buildUniformKnots();
} else {
buildClampedKnots(); // 默认使用clamped（开放均匀）
}
}
/**
* 构建均匀节点向量（适合闭曲线）
*/
private void buildUniformKnots() {
int m = n + degree + 1;
knots = new double[m + 1];
for (int i = 0; i <= m; i++) {
knots[i] = i;
}
}
/**
* 构建clamped节点向量（曲线通过首尾控制点，适合开放路径）
*/
private void buildClampedKnots() {
int m = n + degree + 1;
knots = new double[m + 1];
// 前degree+1个节点为0
for (int i = 0; i <= degree; i++) {
knots[i] = 0;
}
// 中间均匀分布
int internalCount = n - degree;
for (int i = 1; i <= internalCount; i++) {
knots[degree + i] = (double) i / (internalCount + 1);
}
// 后degree+1个节点为1
for (int i = 0; i <= degree; i++) {
knots[n + 1 + i] = 1.0;
}
}
/**
* 使用de Boor算法计算曲线在参数u处的点
* u ∈ [0, 1]（对于clamped节点向量）
*/
public Vec2 evaluate(double u) {
// 找到u所在的节点区间 [knots[k], knots[k+1])
int k = findSpan(u);
// de Boor递推
// d[i][0] = controlPoints[k - degree + i]
Vec2[] d = new Vec2[degree + 1];
for (int i = 0; i <= degree; i++) {
int cpIdx = k - degree + i;
cpIdx = Math.max(0, Math.min(cpIdx, n));
d[i] = controlPoints.get(cpIdx);
}
for (int r = 1; r <= degree; r++) {
for (int i = degree; i >= r; i--) {
int idx = k - degree + i;
double alpha = (u - knots[idx]) / (knots[idx + degree - r + 1] - knots[idx]);
if (Double.isNaN(alpha)) alpha = 0;
d[i] = d[i - 1].scale(1 - alpha).add(d[i].scale(alpha));
}
}
return d[degree];
}
/**
* 找到参数u所在的节点区间
*/
private int findSpan(double u) {
int m = knots.length - 1;
// 处理边界
if (u >= knots[n + 1]) return n;
if (u <= knots[degree]) return degree;
// 二分查找
int low = degree;
int high = n + 1;
int mid = (low + high) / 2;
while (u < knots[mid] || u >= knots[mid + 1]) {
if (u < knots[mid]) {
high = mid;
} else {
low = mid;
}
mid = (low + high) / 2;
}
return mid;
}
/**
* 采样曲线上的点
* @param samples 采样数量
*/
public List<Vec2> sample(int samples) {
List<Vec2> points = new ArrayList<>();
double uStart = knots[degree];
double uEnd = knots[n + 1];
for (int i = 0; i < samples; i++) {
double t = (double) i / (samples - 1);
double u = uStart + t * (uEnd - uStart);
points.add(evaluate(u));
}
return points;
}
/**
* 计算曲线在某点的切线方向（一阶导数）
*/
public Vec2 tangent(double u) {
// 简化的切线计算：取相邻两点差分
double eps = 1e-6;
Vec2 p1 = evaluate(Math.max(u - eps, knots[degree]));
Vec2 p2 = evaluate(Math.min(u + eps, knots[n + 1]));
Vec2 tan = new Vec2(p2.x - p1.x, p2.y - p1.y);
double len = Math.hypot(tan.x, tan.y);
if (len < 1e-10) return new Vec2(1, 0);
return new Vec2(tan.x / len, tan.y / len);
}
// ========== 游戏应用：平滑路径系统 ==========
/**
* 游戏路径类：沿B样条曲线移动的对象
*/
static class PathFollower {
BSplineCurve path;
double speed; // 移动速度（单位距离/秒）
double distance; // 当前已走的弧长距离
double totalLength; // 曲线总弧长
List<Double> arcLengths; // 参数到弧长的对照表
List<Vec2> sampledPoints;
public PathFollower(BSplineCurve path, double speed, int samples) {
this.path = path;
this.speed = speed;
this.distance = 0;
this.sampledPoints = path.sample(samples);
// 预计算弧长表（用于弧长参数化）
arcLengths = new ArrayList<>();
arcLengths.add(0.0);
double total = 0;
for (int i = 1; i < sampledPoints.size(); i++) {
Vec2 a = sampledPoints.get(i - 1);
Vec2 b = sampledPoints.get(i);
total += Math.hypot(b.x - a.x, b.y - a.y);
arcLengths.add(total);
}
this.totalLength = total;
}
/**
* 根据弧长距离获取曲线上的点
*/
public Vec2 getPositionByDistance(double dist) {
if (dist <= 0) return sampledPoints.get(0);
if (dist >= totalLength) return sampledPoints.get(sampledPoints.size() - 1);
// 在弧长表中查找
int idx = 0;
while (idx < arcLengths.size() - 1 && arcLengths.get(idx + 1) < dist) {
idx++;
}
double segStart = arcLengths.get(idx);
double segEnd = arcLengths.get(idx + 1);
double t = (dist - segStart) / (segEnd - segStart);
Vec2 a = sampledPoints.get(idx);
Vec2 b = sampledPoints.get(idx + 1);
return a.scale(1 - t).add(b.scale(t));
}
/**
* 更新位置（按时间步长）
*/
public Vec2 update(double deltaTime) {
distance += speed * deltaTime;
if (distance > totalLength) distance = totalLength;
return getPositionByDistance(distance);
}
public boolean isFinished() {
return distance >= totalLength;
}
}
/**
* Catmull-Rom到B样条转换
* Catmull-Rom样条是B样条的特例，通过控制点可转换
*/
public static BSplineCurve fromCatmullRom(List<Vec2> points, int degree) {
// Catmull-Rom控制点可直接作为B样条控制点（适当调整）
return new BSplineCurve(points, degree, false);
}
public static void main(String[] args) {
System.out.println("=== B样条曲线基础测试 ===");
// 测试1：三次B样条（最常用）
List<Vec2> cp1 = Arrays.asList(
new Vec2(0, 0),
new Vec2(1, 3),
new Vec2(3, 4),
new Vec2(5, 2),
new Vec2(6, 0)
);
BSplineCurve spline3 = new BSplineCurve(cp1, 3, false);
System.out.println("三次B样条（clamped），控制点: " + cp1.size());
System.out.println("节点向量: " + Arrays.toString(spline3.knots));
List<Vec2> samples = spline3.sample(10);
System.out.print("采样点: ");
for (Vec2 p : samples) {
System.out.print(p + " ");
}
System.out.println();
// 测试2：二次B样条
System.out.println("\n=== 二次B样条测试 ===");
BSplineCurve spline2 = new BSplineCurve(cp1, 2, false);
List<Vec2> samples2 = spline2.sample(8);
System.out.print("二次采样: ");
for (Vec2 p : samples2) {
System.out.print(p + " ");
}
System.out.println();
// 测试3：路径跟随系统
System.out.println("\n=== 游戏路径跟随演示 ===");
List<Vec2> pathCp = Arrays.asList(
new Vec2(0, 0),
new Vec2(2, 5),
new Vec2(5, 5),
new Vec2(7, 2),
new Vec2(10, 3),
new Vec2(12, 0)
);
BSplineCurve gamePath = new BSplineCurve(pathCp, 3, false);
PathFollower follower = new PathFollower(gamePath, 2.0, 100);
System.out.println("路径总长: " + String.format("%.2f", follower.totalLength));
System.out.println("移动模拟（速度=2.0, 每步dt=0.5）:");
double dt = 0.5;
int step = 0;
while (!follower.isFinished() && step < 20) {
Vec2 pos = follower.update(dt);
Vec2 tan = gamePath.tangent(follower.distance / follower.totalLength);
System.out.println(" t=" + String.format("%.1f", step * dt) +
" pos=" + pos +
" tangent=" + tan);
step++;
}
// 测试4：局部控制性验证
System.out.println("\n=== 局部控制性验证 ===");
Vec2 originalMid = spline3.evaluate(0.5);
System.out.println("原始中点: " + originalMid);
// 修改中间控制点
cp1.set(2, new Vec2(3, 6));
BSplineCurve modified = new BSplineCurve(cp1, 3, false);
Vec2 modifiedMid = modified.evaluate(0.5);
System.out.println("修改P2后中点: " + modifiedMid);
System.out.println("起点不变: " + spline3.evaluate(0.0) + " vs " + modified.evaluate(0.0));
System.out.println("终点不变: " + spline3.evaluate(1.0) + " vs " + modified.evaluate(1.0));
}
}
复杂度分析
- de Boor求值：对于p次B样条，每次求值需要进行O(p²)次操作（p轮递推，每轮最多p次插值）。对于常用的三次B样条（p=3），每次求值仅需约9次向量运算。
- 采样：采样N个点的时间复杂度为O(N·p²)。
- 弧长参数化：预计算弧长表为O(N)，后续按距离查询为O(log N)或O(1)（若使用缓存索引）。
- 空间复杂度：O(n)存储控制点和节点向量，O(N)存储采样点与弧长表。
总结
B样条曲线通过节点向量和de Boor递推算法，实现了对平滑曲线的精确数学控制。本文实现的三次B样条配合弧长参数化，可直接用于游戏中的角色路径跟随、相机轨道和平滑动画。与贝塞尔曲线相比，B样条的局部控制性和多段连续拼接能力使其在复杂路径编辑中更具优势。在实际引擎中，可进一步扩展为非均匀有理B样条（NURBS）以支持圆锥曲线，或结合碰撞检测实现动态路径修正。
