使用 Direct2D 绘制样条曲线
Draw splines by using Direct2D
我有一条样条曲线的数据
- 学位
- 结
- 控制点
- 拟合点
我需要使用 Direct2D 绘制这条曲线。目前我正在使用 ID2D1GeometrySink interface 绘制几何图形，但它似乎没有实现可能的 AddSpline 方法。
有没有办法通过Direct2D绘制样条曲线？即使是可以在 Direct2D 应用程序中使用的 DirectX 实现也可以。
Direct2D，更清楚ID2D1GeometrySink，不支持样条曲线，但可以拼成样条曲线的三次贝塞尔曲线。相反，您可以从样条数据中获取 b 曲线，然后将它们添加到几何体中。
算法用这张图简单解释一下：.
可以找到一篇简明扼要的文章here。
您可以拆分样条曲线，直到控制点重叠并且可以降低阶数，甚至直到所有曲线都足够平坦以成为直线。最后一件事不是一个坏主意，因为您的硬件不知道曲线，所以您传递的曲线无论如何都会在以后转换为直线。当你做这个转换时，你可以确定平面度的公差并避免丑陋的边缘。
除非您已经有了基本 NURBS 操作的工作代码或者您是 NURBS 专家，否则我建议使用一些 NURBS 库。通常，与您的问题相关的操作集是：点评估、结插入、拆分、也许 仰角 。
为了概括起见，我将描述三种可能的解决方案。
按节分开
假设您的输入 NURBS 曲线是非有理数（无权重 = 单位权重），并且它们的阶数不能超过生成的贝塞尔曲线的最大允许阶数。那么样条的每一个跨度就是一条多项式曲线，所以可以提取为贝塞尔曲线。
根据您使用的库，算法的描述可能会有所不同。以下是可能的变体：
- 如果有将NURBS曲线分割成Bezier曲线的函数，直接调用即可。
- 假设有一个函数可以在给定参数下将一条曲线分成两条子曲线。然后在任何内部结中分割曲线（即不等于 min/max 结）。对每条子曲线执行相同操作，直到没有内部节点，这意味着所有曲线都是贝塞尔曲线。
- 任何 NURBS 库都必须具有结插入功能。对于多重性小于 D（度）的每个结 Ki，调用参数 = Ki 的结插入。您可以按任何顺序插入不同的结。该库还可以包含 "multiple knot insertion"，它允许将所有插入组合到一个调用中。最后，min/max个节点必须有多重度D+1，所有内部节点必须有多重度D。此时控制点完全描述了你需要的贝塞尔曲线：控制点[0..D]定义了第0贝塞尔曲线，[D..2D]定义第1贝塞尔曲线，...，[q D .. (q+1) D]控制点定义第q贝塞尔曲线。
如果您输入的 NURBS 曲线的阶数低于所需的贝塞尔曲线阶数，您还可以为原始 NURBS 曲线或生成的贝塞尔曲线调用阶数提升。说到ID2D1GeometrySink，它接受所有阶数<= 3的贝塞尔曲线（线性贝塞尔曲线只是一条线段），所以没有必要。
如果您的 NURBS 曲线可能具有不可接受的高阶数，或者可能是有理数，那么您必须使用三次样条（更硬更快）或折线（更简单但更慢）来逼近曲线。
保证折线近似
这是一个相当简单的递归算法，它构建 NURBS 曲线的折线近似，保证误差 <= MaxErr。
- 从曲线的第一个控制点到最后一个控制点画一条线段。
- 检查是否所有控制点都在离线段的 MaxErr 距离内。
- 如果是，则将线段添加到输出。
- 否则，将中间的曲线分割成两条子曲线，递归逼近。
要实现它，需要NURBS曲线分割操作（可以通过节点插入实现）。
启发式折线近似
如果手边没有 NURBS 库，执行节点插入可能会很痛苦。这就是为什么我描述了另一种解决方案，它仅使用 NURBS 曲线的点评估。您可以通过 de Boor 算法或定义（参见 basis functions and NURBS curve 定义）
来实现点评估
该算法是递归的，它接受原始曲线上的参数区间作为输入。
- 计算参数区间的起点和终点。
- 通过它们画一条线段。
- 评估参数区间内曲线上的一些点。
- 检查这些内部点是否在线段的 MaxErr 距离内。
- 如果是，则将线段添加到输出。
- 否则，将参数区间分成两半，并递归调用它们的逼近。
此算法是自适应的，在极少数情况下，它在实践中会产生错误的近似值。检查点可以在参数区间内统一选择。为了获得更高的可靠性，最好还对落在参数区间内的输入曲线的所有节点处的曲线进行评估。
第三方库
如果您不打算经常使用 NURBS，我建议使用 tinyspline 库。它在设计上非常小，没有依赖性，并且有 MIT 许可证。另外，好像在积极开发中，有什么问题可以和作者沟通。
看来第一种解法已经够开题了，下面是用tinyspline将NURBS拆分成Bezier曲线的代码：
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <math.h>
#include "tinysplinecpp.h"
#include "debugging.h"
int main() {
//create B-spline curve and set its data
TsBSpline nurbs(3, 2, 10, TS_NONE);
float knotsData[] = {0.0f, 0.0f, 0.0f, 0.0f, 0.3f, 0.3f, 0.5f, 0.7f, 0.7f, 0.7f, 1.0f, 1.0f, 1.0f, 1.0f};
for (int i = 0; i < nurbs.nKnots(); i++)
nurbs.knots()[i] = knotsData[i];
for (int i = 0; i < nurbs.nCtrlp(); i++) {
nurbs.ctrlp()[2*i+0] = 0.0f + i;
float x = 1.0f - i / float(nurbs.nCtrlp());
nurbs.ctrlp()[2*i+1] = x * x * x;
}
ts_bspline_print(nurbs.data());
//insert knots into B-spline so that it becomes a sequence of bezier curves
TsBSpline beziers = nurbs;
beziers.toBeziers();
ts_bspline_print(beziers.data());
//check that the library does not fail us
for (int i = 0; i < 10000; i++) {
float t = float(rand()) / RAND_MAX;
float *pRes1 = nurbs(t).result();
float *pRes2 = beziers(t).result();
float diff = hypotf(pRes1[0] - pRes2[0], pRes1[1] - pRes2[1]);
if (diff >= 1e-6f)
printf("Bad eval at %f: err = %f (%f;%f) vs (%f;%f)\n", t, diff, pRes1[0], pRes1[1], pRes2[0], pRes2[1]);
}
//extract bezier curves
assert(beziers.nCtrlp() % nurbs.order() == 0);
int n = beziers.nCtrlp() / nurbs.order();
int sz = nurbs.order() * 2; //floats per bezier
for (int i = 0; i < n; i++) {
float *begin = beziers.ctrlp() + sz * i;
float *end = beziers.ctrlp() + sz * (i + 1);
//[begin..end) contains control points of i-th bezier curve
}
return 0;
}
最后的注释
上面的大部分文本假定您的 NURBS 曲线是 clamped，这意味着最小和最大节点具有多重性 D+1。有时也使用未固定的 NURBS 曲线。如果你遇到一个，你可能还需要使用库的适当功能来限制它。上面使用的 tinyspline 的 toBeziers 方法会自动夹紧 NURBS，您不需要手动夹紧它。
我使用此示例代码将基数样条转换为三次贝塞尔曲线块列表：http://www.codeproject.com/Articles/31859/Draw-a-Smooth-Curve-through-a-Set-of-D-Points-wit
它是为 WPF 编写的，但由于 WPF 和 Direct2D 的区别仅在于它们的编程模型（声明式与命令式），因此它很容易转换为 Direct2D。
我有一条样条曲线的数据
- 学位
- 结
- 控制点
- 拟合点
我需要使用 Direct2D 绘制这条曲线。目前我正在使用 ID2D1GeometrySink interface 绘制几何图形，但它似乎没有实现可能的 AddSpline 方法。
有没有办法通过Direct2D绘制样条曲线？即使是可以在 Direct2D 应用程序中使用的 DirectX 实现也可以。
Direct2D，更清楚ID2D1GeometrySink，不支持样条曲线，但可以拼成样条曲线的三次贝塞尔曲线。相反，您可以从样条数据中获取 b 曲线，然后将它们添加到几何体中。
算法用这张图简单解释一下：
可以找到一篇简明扼要的文章here。 您可以拆分样条曲线，直到控制点重叠并且可以降低阶数，甚至直到所有曲线都足够平坦以成为直线。最后一件事不是一个坏主意，因为您的硬件不知道曲线，所以您传递的曲线无论如何都会在以后转换为直线。当你做这个转换时，你可以确定平面度的公差并避免丑陋的边缘。
除非您已经有了基本 NURBS 操作的工作代码或者您是 NURBS 专家，否则我建议使用一些 NURBS 库。通常，与您的问题相关的操作集是：点评估、结插入、拆分、也许 仰角 。
为了概括起见，我将描述三种可能的解决方案。
按节分开
假设您的输入 NURBS 曲线是非有理数（无权重 = 单位权重），并且它们的阶数不能超过生成的贝塞尔曲线的最大允许阶数。那么样条的每一个跨度就是一条多项式曲线，所以可以提取为贝塞尔曲线。
根据您使用的库，算法的描述可能会有所不同。以下是可能的变体：
- 如果有将NURBS曲线分割成Bezier曲线的函数，直接调用即可。
- 假设有一个函数可以在给定参数下将一条曲线分成两条子曲线。然后在任何内部结中分割曲线（即不等于 min/max 结）。对每条子曲线执行相同操作，直到没有内部节点，这意味着所有曲线都是贝塞尔曲线。
- 任何 NURBS 库都必须具有结插入功能。对于多重性小于 D（度）的每个结 Ki，调用参数 = Ki 的结插入。您可以按任何顺序插入不同的结。该库还可以包含 "multiple knot insertion"，它允许将所有插入组合到一个调用中。最后，min/max个节点必须有多重度D+1，所有内部节点必须有多重度D。此时控制点完全描述了你需要的贝塞尔曲线：控制点[0..D]定义了第0贝塞尔曲线，[D..2D]定义第1贝塞尔曲线，...，[q D .. (q+1) D]控制点定义第q贝塞尔曲线。
如果您输入的 NURBS 曲线的阶数低于所需的贝塞尔曲线阶数，您还可以为原始 NURBS 曲线或生成的贝塞尔曲线调用阶数提升。说到ID2D1GeometrySink，它接受所有阶数<= 3的贝塞尔曲线（线性贝塞尔曲线只是一条线段），所以没有必要。
如果您的 NURBS 曲线可能具有不可接受的高阶数，或者可能是有理数，那么您必须使用三次样条（更硬更快）或折线（更简单但更慢）来逼近曲线。
保证折线近似
这是一个相当简单的递归算法，它构建 NURBS 曲线的折线近似，保证误差 <= MaxErr。
- 从曲线的第一个控制点到最后一个控制点画一条线段。
- 检查是否所有控制点都在离线段的 MaxErr 距离内。
- 如果是，则将线段添加到输出。
- 否则，将中间的曲线分割成两条子曲线，递归逼近。
要实现它，需要NURBS曲线分割操作（可以通过节点插入实现）。
启发式折线近似
如果手边没有 NURBS 库，执行节点插入可能会很痛苦。这就是为什么我描述了另一种解决方案，它仅使用 NURBS 曲线的点评估。您可以通过 de Boor 算法或定义（参见 basis functions and NURBS curve 定义）
来实现点评估该算法是递归的，它接受原始曲线上的参数区间作为输入。
- 计算参数区间的起点和终点。
- 通过它们画一条线段。
- 评估参数区间内曲线上的一些点。
- 检查这些内部点是否在线段的 MaxErr 距离内。
- 如果是，则将线段添加到输出。
- 否则，将参数区间分成两半，并递归调用它们的逼近。
此算法是自适应的，在极少数情况下，它在实践中会产生错误的近似值。检查点可以在参数区间内统一选择。为了获得更高的可靠性，最好还对落在参数区间内的输入曲线的所有节点处的曲线进行评估。
第三方库
如果您不打算经常使用 NURBS，我建议使用 tinyspline 库。它在设计上非常小，没有依赖性，并且有 MIT 许可证。另外，好像在积极开发中，有什么问题可以和作者沟通。
看来第一种解法已经够开题了，下面是用tinyspline将NURBS拆分成Bezier曲线的代码：
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <math.h>
#include "tinysplinecpp.h"
#include "debugging.h"
int main() {
//create B-spline curve and set its data
TsBSpline nurbs(3, 2, 10, TS_NONE);
float knotsData[] = {0.0f, 0.0f, 0.0f, 0.0f, 0.3f, 0.3f, 0.5f, 0.7f, 0.7f, 0.7f, 1.0f, 1.0f, 1.0f, 1.0f};
for (int i = 0; i < nurbs.nKnots(); i++)
nurbs.knots()[i] = knotsData[i];
for (int i = 0; i < nurbs.nCtrlp(); i++) {
nurbs.ctrlp()[2*i+0] = 0.0f + i;
float x = 1.0f - i / float(nurbs.nCtrlp());
nurbs.ctrlp()[2*i+1] = x * x * x;
}
ts_bspline_print(nurbs.data());
//insert knots into B-spline so that it becomes a sequence of bezier curves
TsBSpline beziers = nurbs;
beziers.toBeziers();
ts_bspline_print(beziers.data());
//check that the library does not fail us
for (int i = 0; i < 10000; i++) {
float t = float(rand()) / RAND_MAX;
float *pRes1 = nurbs(t).result();
float *pRes2 = beziers(t).result();
float diff = hypotf(pRes1[0] - pRes2[0], pRes1[1] - pRes2[1]);
if (diff >= 1e-6f)
printf("Bad eval at %f: err = %f (%f;%f) vs (%f;%f)\n", t, diff, pRes1[0], pRes1[1], pRes2[0], pRes2[1]);
}
//extract bezier curves
assert(beziers.nCtrlp() % nurbs.order() == 0);
int n = beziers.nCtrlp() / nurbs.order();
int sz = nurbs.order() * 2; //floats per bezier
for (int i = 0; i < n; i++) {
float *begin = beziers.ctrlp() + sz * i;
float *end = beziers.ctrlp() + sz * (i + 1);
//[begin..end) contains control points of i-th bezier curve
}
return 0;
}
最后的注释
上面的大部分文本假定您的 NURBS 曲线是 clamped，这意味着最小和最大节点具有多重性 D+1。有时也使用未固定的 NURBS 曲线。如果你遇到一个，你可能还需要使用库的适当功能来限制它。上面使用的 tinyspline 的 toBeziers 方法会自动夹紧 NURBS，您不需要手动夹紧它。
我使用此示例代码将基数样条转换为三次贝塞尔曲线块列表：http://www.codeproject.com/Articles/31859/Draw-a-Smooth-Curve-through-a-Set-of-D-Points-wit
它是为 WPF 编写的，但由于 WPF 和 Direct2D 的区别仅在于它们的编程模型（声明式与命令式），因此它很容易转换为 Direct2D。