如何在不进行昂贵的预计算的情况下以恒定速度沿着贝塞尔曲线移动

Question

请原谅我的代码示例太长，但我不知道如何用更少的代码正确解释我的问题：

let c = document.querySelector("canvas");
let ctx = c.getContext("2d");
class BezierCurve {
constructor(x1, y1, cpX, cpY, x2, y2) {
this.f = 0;
this.x1 = x1;
this.y1 = y1;
this.cpX = cpX;
this.cpY = cpY;
this.x2 = x2;
this.y2 = y2;
this.pointCache = this.calcPoints();
}
calcX(t) { return (1 - t) * (1 - t) * this.x1 + 2 * (1 - t) * t * this.cpX + t * t * this.x2; }
calcY(t) { return (1 - t) * (1 - t) * this.y1 + 2 * (1 - t) * t * this.cpY + t * t * this.y2; }
calcPoints() {
const step = 0.001, segments = [];

for (let i = 0; i <= 1 - step; i += step) {
let dx = this.calcX(i) - this.calcX(i + step);
let dy = this.calcY(i) - this.calcY(i + step);

segments.push(Math.sqrt(dx * dx + dy * dy));
}

const len = segments.reduce((a, c) => a + c, 0);
let result = [], l = 0, co = 0;

for (let i = 0; i < segments.length; i++) {
l += segments[i];
co += step;
result.push({ t: l / len, co });
}

return result;
}
draw() {
ctx.beginPath();
ctx.moveTo(this.x1, this.y1);
ctx.quadraticCurveTo(this.cpX, this.cpY, this.x2, this.y2);
ctx.stroke();
}
tick(amount = 0.001) {
this.f = this.f < 1 ? this.f + amount : 0;
}
}
function drawCircle(x, y, r) {
ctx.beginPath();
ctx.arc(x, y, r, 0, 2 * Math.PI);
ctx.fill();
}
let a = new BezierCurve(25, 25, 80, 250, 100, 50);
let b = new BezierCurve(225, 25, 280, 250, 300, 50);
function draw(curve, fraction) {
let x = curve.calcX(fraction);
let y = curve.calcY(fraction);
curve.draw();
drawCircle(x, y, 5);
curve.tick();
}
// Inefficient but using this instead of binary search just to save space in code example
function findClosestNumInArray(arr, goal) {
return arr.reduce((prev, cur) => Math.abs(cur.t - goal) < Math.abs(prev.t - goal) ? cur : prev);
}
function drawLoop(elapsed) {  
c.width = 600;
c.height = 600;

draw(a, a.f);
let closest = findClosestNumInArray(b.pointCache, b.f).co;
draw(b, closest);
requestAnimationFrame(drawLoop);
}
drawLoop(0);

<canvas></canvas>

好吧，来解释一下发生了什么：如果你点击Run code snippet，你会看到有两条曲线，我称之为a(左一条(和b(右一条(。

你可能会注意到，沿着a的曲线移动的点开始得很快，然后在曲线周围变慢，然后再次加速。这是尽管分数部分在每帧增加一个常数0.001。

另一方面，b的点在整个迭代过程中以恒定速度移动。这是因为对于b，我使用了为曲线预先计算的pointCache映射。该函数CCD_ 8生成映射使得输入分数分量CCD_；适当的"；沿着曲线CCD_ 10的实际百分比。

无论如何，这一切都是有效的，但我的问题是预计算calcPoints是昂贵的，并且引用查找表来查找百分比沿线的实际小数部分是不精确的，并且需要大量的内存使用。我想知道是否有更好的方法。

我正在寻找一种方法来做curve.calcX(0.5)和这样的事情，实际上沿着曲线获得50%的分数。因为目前现有的等式并不能做到这一点，我不得不做这个代价高昂的变通方法。

Answer 1

我们可以尝试修改您的方法以提高效率。这仍然不是你所希望的确切解决方案，但它可能会奏效。

我们可以使用细分的思想，而不是在参数值相差0.001的情况下重复评估Bézier曲线(在这种情况下，您不重复使用上一步的计算(。你知道德的算法吗？它不仅在给定参数t下评估贝塞尔曲线，还为您提供了将曲线细分为两条的方法：一条贝塞尔曲线等于区间[0，t]上的原始曲线，另一条等于区间[t-，1]上的原始曲线。它们的控制多边形是比原始控制多边形更好的曲线近似。

因此，您将按照以下步骤进行：

1. 使用De Casteljau的算法在t=0.5处细分曲线
2. 使用De Casteljau的算法在t=0.25处细分第一段
3. 使用De Casteljau的算法在t=0.75处细分第二段
4. 以相同的方式递归进行，直到达到规定的深度。这取决于您想要达到的精度

这些线段的控制多边形将是原始Bézier曲线的(分段线性(近似值。使用它们来预计算参数，就像您迄今为止所做的那样；或者直接绘制该近似值而不是将CCD_ 13与原始曲线一起使用。生成此近似值应该比您的过程快得多。

您可以在Prautzsch、Boehm和Paluszny的第3.3、3.4和3.5节中阅读更多关于这个想法的内容：Bézier和B样条曲线技术。它们还提供了该过程收敛到原始曲线的速度的估计。

Answer 2

不完全确定这会起作用，但你知道绘制贝塞尔点的Horner方案吗？

/***************************************************************************
//
//   This routine plots out a bezier curve, with multiple calls to hornbez()
//
//***************************************************************************
function bezierCalculate(context, NumberOfDots, color, dotSize) {
// This routine uses Horner's Scheme to draw entire Bezier Line...
for (var t = 0.0; t < 1.0001; t = t + 1.0 / NumberOfDots) {
xTemp = hornbez(numberOfControlPoints - 1, "x", t);
yTemp = hornbez(numberOfControlPoints - 1, "y", t);
drawDot(context, xTemp, yTemp, dotSize, color);
}
}
//***************************************************************************
//
//   This routine uses  Horner's scheme to compute one coordinate
//   value of a  Bezier curve. Has to be called
//   for each coordinate  (x,y, and/or z) of a control polygon.
//   See Farin, pg 59,60.  Note:  This technique is also called
//   "nested multiplication".
//   Input:   degree: degree of curve.
//            coeff:  array with coefficients of curve.
//            t:      parameter value.
//            Output: coordinate value.
//
//***************************************************************************
function hornbez(degree, xORy, t) {
var i;
var n_choose_i; /* shouldn't be too large! */
var fact, t1, aux;
t1 = 1 - t;
fact = 1;
n_choose_i = 1;
var aux = FrameControlPt[0][xORy] * t1;
/* starting the evaluation loop */
for (i = 1; i < degree; i++) {
fact = fact * t;
n_choose_i = n_choose_i * (degree - i + 1) / i; /* always int! */
aux = (aux + fact * n_choose_i * FrameControlPt[i][xORy]) * t1;
}
aux = aux + fact * t * FrameControlPt[degree][xORy];
return aux;
}

不确定你要去哪里，但这里有一篇我不久前写的文章。。。关于Bezier iframe的内容，请参阅。。。我隐含的问题？贝塞尔曲线适合你吗？