使用Direct2D绘制样条线

Question

我有样条曲线的数据

• 学位
• 结
• 控制点
• 适合点

我需要使用绘制这条曲线Direct2D.目前我正在使用ID2D1GeometrySink接口绘制几何图形,但似乎它没有实现可能的AddSpline方法.

有没有办法通过Direct2D？绘制样条？即使是DirectX可以在Direct2D应用程序中使用的实现也没问题.

Answer 1

除非您已经有基本NURBS操作的工作代码,或者您是NURBS专家,否则我建议您使用一些NURBS库.通常,与您的问题相关的一组操作包括:点评估,结点插入,拆分以及可能的度数提升.

为了一般性,我将描述三种可能的解决方案.

按结点分开

假设您的输入NURBS曲线是非理性的(没有权重=单位权重),并且它们的度数不能超过所得贝塞尔曲线的最大允许程度.然后样条曲线的每个跨度都是多项式曲线,因此可以将其提取为贝塞尔曲线.

根据您使用的库,算法的描述可能不同.以下是可能的变体:

1. 如果有将NURBS曲线分割为Bezier曲线的功能,只需调用它即可.
2. 假设在给定参数处存在将曲线分成两个子曲线的函数.然后将曲线分成任何内部结(即不等于最小/最大结).对每个子曲线执行相同操作,直到没有内部结,这意味着所有曲线都是贝塞尔曲线.
3. 任何NURBS库都必须具有结插入功能.对于具有小于D(度)的多重性的每个结Ki,使用param = Ki调用结点插入.您可以按任何顺序插入不同的结.该库还可以包含"多个结插入",它允许将所有插入组合成一个调用.最后,最小/最大结必须具有多重性D + 1,所有内部结必须具有多重性D.此时控制点完全描述您需要的贝塞尔曲线:控制点[0..D]定义0- Bezier,[D..2D]定义第1个Bezier,......,[q D ..(q + 1)D]控制点定义第q个Bezier.

如果您的输入NURBS曲线的程度低于所需的贝塞尔曲线的程度,您还可以为原始NURBS曲线或生成的贝塞尔曲线调用度数高程.说到ID2D1GeometrySink,它接受程度<= 3的所有贝塞尔曲线(线性贝塞尔曲线只是一个线段),因此没有必要.

如果您的NURBS曲线可能具有不可接受的高度,或者可能是合理的,那么您必须使用三次样条(更硬和更快)或使用折线(更简单但更慢)来近似曲线.

保证折线近似

这是一个相当简单的递归算法,它建立了NURBS曲线的折线近似,保证误差<= MaxErr.

1. 从曲线的第一个控制点到最后一个控制点绘制线段.
2. 检查所有控制点是否在距离段的MaxErr距离内.
3. 如果是,则将线段添加到输出.
4. 否则,将中间的曲线分成两个子曲线,并递归逼近它们.

要实现它,您需要NURBS曲线分割操作(可以通过结插入实现).

启发式折线近似

如果手边没有NURBS库,实现结点插入可能会导致很多痛苦.这就是为什么我描述了一个仅使用NURBS曲线的点评估的解决方案.您可以通过de Boor算法或定义(参见基函数和NURBS曲线定义)实现点评估

该算法是递归的,它接受原始曲线上的参数区间作为输入.

1. 评估参数区间的起点和终点.
2. 通过它们绘制线段.
3. 评估参数区间内曲线上的一些点.
4. 检查这些内部点是否在线段的MaxErr距离内.
5. 如果是,则将线段添加到输出.
6. 否则,将参数区间分成两半,并递归调用它们的近似值.

该算法具有自适应性,在极少数情况下可以在实际中产生不良近似.可以在参数区间内统一选择检查点.为了获得更高的可靠性,最好还要评估输入曲线在参数区间内的所有节点的曲线.

第三方库

如果您不打算与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曲线被钳制,这意味着最小和最大结具有多重性D + 1.有时也使用未钳位的NURBS曲线.如果您遇到一个,您可能还需要使用库的适当功能来夹紧它.上面使用的来自tinyspline的Beziers的方法自动夹住NURBS,你不需要手动夹紧它.