使用 deBoor 算法问题的均匀 B 样条曲线

Question

我有一个非常简单的案例，我需要绘制一个单一的 2 阶均匀 B 样条线段（4 个控制点）并且我正在尝试在 C# 中实现 deBoor 算法(https://en.wikipedia.org/wiki/De_Boor%27s_algorithm)但我运行陷入了一个问题，无论阅读和研究多少都无法帮助我找出发生了什么。

在我的例子中，我在 Point[] 数组中只定义了 4 个控制点（p1、p2、p3 和 p4）。所以我只需要点 p2 和 p3 之间的曲线段。因此，我构建了一个没有前导和尾随结 [0, 1, 2, 3] 的统一结数组 - 基本上我可以在这种情况下使用 i 但我这样做是为了坚持公式。我从维基百科构建了一个递归公式的实现：

看起来像这样：

    Point deBoor(int i, int k, float t, int[] knots)
    {
        //i - knot span index
        //k - degree
        // t - time [0-knots.Length-1]
        //knots - the knots array
        if (k == 0) return points[knots[i]]/3f;
        return ((t - knots[i]) / (knots[i + k] - knots[i])) * deBoor(i, k - 1, t, knots) + ((knots[i + k + 1] - t) / (knots[i + k + 1] - knots[i + 1])) * deBoor(i + 1, k - 1, t, knots);
    }

我尝试像这样从 deBoor 方法中获取要点：

float t = time * (points.Length - 1); //time ranges from 0 to 1
int[] knots = new int[] { 0, 1, 2, 3 };
point = deBoor(0, 2, t, knots);

不幸的是，我得到的结果不正确。此图像显示了我的控制点的样子、我期望得到的以及我实际得到的：

我查看了其他实现，比如这个：https://gist.github.com/soraphis/61ee9185416ee23d0d40 它们似乎都做同样的事情，只是编码不同。我试图复制他们的解决方案，但结果更糟。所有这些让我觉得我错过了一些非常明显的东西。

Answer 1

您似乎混淆了节点和控制点。我们需要在您的解决方案中改进几处才能使其发挥作用。

零度函数

正如@fang 已经指出的那样，您对 k==0 的解决方案很奇怪。我建议更换

if (k == 0) return points[knots[i]]/3f;

通过更接近原始公式的东西，例如

if (k==0)
{
  if (t <= knots[i] && t < knots[i+1])
    return 1;
  else
    return 0;
}

结向量

@fang 也指出，对于具有四个控制点的二次样条，您需要七个结。你提到你想要统一的结，根据你的预期图片我会推荐

int[] knots = new float[] {0, 1/6, 2/6, 3/6, 4/6, 5/6, 1};

请注意，节点现在介于 0 和 1 之间；这意味着 t 和 time 将相同，即

float t = time; //time ranges from 0 to 1 and so does t

如果您坚持要使用 int 结（恕我直言，这让您感到困惑），请使用

int[] knots = new int[] { 0, 1, 2, 3, 4, 5, 6 };
float t = time * 6; //time ranges from 0 to 1 and t from 0 to 6

注意交换顺序：t 必须 time 缩放以覆盖整个结范围。

评价

De Boor 算法计算一个 B 样条曲线，即其中一个基函数（有些人使用相互冲突的命名法，并使用 B 样条这个词来表示整个样条函数而不仅仅是基函数之一；这有时会导致混淆。

通俗地说，对于给定的 t，您的 deBoor 函数为您提供第 i 个控制点的系数，这是一个标量。因此，deBoor 的 return 值必须是 float 或 double 或类似的东西，当然不是 point.

对于每个 t，您需要对按这些系数缩放的控制点求和。所以你的最终结果将类似于

point value = deBoor(0, 2, t, knots) * points[0]
  + deBoor(1, 2, t, knots) * points[1]
  + deBoor(2, 2, t, knots) * points[2]
  + deBoor(3, 2, t, knots) * points[3];

请注意，* 表示 float 和 point 的乘法（您可能需要重载这样的运算符），+ 表示两个的和points（同样，可能需要运算符重载）。我不是很精通 C#，所以可能有一种更优雅的写法；例如，我邀请您使用 for 循环。

如果您仍然感到困惑，我建议您先熟悉 Bézier 曲线，然后再学习 B 样条。可以找到比较简洁的介绍例如here。这些图片有点90年代风格，但这些想法仍然有效，并且以一种易于理解和简洁的方式呈现。

使用 deBoor 算法问题的均匀 B 样条曲线

Uniform B-Spline using deBoor's algorithm issue

c#

recursion

bezier

curve

spline

零度函数

结向量

评价