javascript - 如何计算避开物体的贝塞尔曲线控制点？

Question

具体来说，我正在使用 javascript 在画布上工作。

基本上，我的对象有我想避免的边界，但仍然用贝塞尔曲线环绕。但是，我什至不确定从哪里开始编写一个可以移动控制点以避免碰撞的算法。

问题在下图中，即使你不熟悉乐谱，问题应该还是很清楚的。曲线的点是红点

此外，我可以访问每个音符的边界框，其中包括词干。

所以自然地，必须在边界框和曲线之间检测到碰撞（这里有一些方向会很好，但我一直在浏览，发现有很多关于这方面的信息）。但是在检测到碰撞后会发生什么？计算控制点位置以使某些东西看起来更像：

Answer 1

贝塞尔方法

最初，这个问题是一个广泛的问题 - 甚至对于 SO 来说甚至可能是广泛的，因为需要考虑许多不同的场景以制定“适合所有人的解决方案”。它本身就是一个完整的项目。因此，我将为您提供可以构建的解决方案的基础- 它不是一个完整的解决方案（但接近一个..）。我在最后添加了一些补充建议。

此解决方案的基本步骤是：

将音符分为两组，左部分和右部分。

然后，控制点基于从第一个（结束）点的最大角度和到该组中任何其他音符的​​距离，以及最后一个结束点到第二组中任何点的距离。

然后将两组得到的角度加倍（最大 90°）并用作计算控制点的基础（基本上是点旋转）。可以使用张力值进一步修剪距离。

角度、加倍、距离、张力和填充偏移将允许微调以获得最佳的整体结果。可能存在需要额外条件检查的特殊情况，但这超出了本文的范围（它不是一个完整的密钥就绪解决方案，但为进一步工作提供了良好的基础）。

该过程的几个快照：

示例中的主要代码分为两部分，两个循环解析每一半以找到最大角度和距离。这可以组合成一个循环，除了从左到中的迭代器之外，还有第二个迭代器从右到中，但为了简单起见并更好地理解发生了什么，我将它们分成两个循环（并引入了一个错误在下半场 - 请注意。我将把它留作练习）：

var dist1 = 0,  // final distance and angles for the control points
    dist2 = 0,
    a1 = 0,
    a2 = 0;

// get min angle from the half first points
for(i = 2; i < len * 0.5 - 2; i += 2) {

    var dx = notes[i  ] - notes[0],      // diff between end point and
        dy = notes[i+1] - notes[1],      // current point.
        dist = Math.sqrt(dx*dx + dy*dy), // get distance
        a = Math.atan2(dy, dx);          // get angle

    if (a < a1) {                        // if less (neg) then update finals
        a1 = a;
        dist1 = dist;
    }
}

if (a1 < -0.5 * Math.PI) a1 = -0.5 * Math.PI;      // limit to 90 deg.

下半场也是如此，但在这里我们翻转角度，以便通过比较当前点与终点而不是终点与当前点来比较它们更容易处理。循环完成后，我们将其翻转 180°：

// get min angle from the half last points
for(i = len * 0.5; i < len - 2; i += 2) {

    var dx = notes[len-2] - notes[i],
        dy = notes[len-1] - notes[i+1],
        dist = Math.sqrt(dx*dx + dy*dy),
        a = Math.atan2(dy, dx);

    if (a > a2) {
        a2 = a;
        if (dist2 < dist) dist2 = dist;            //bug here*
    }
}

a2 -= Math.PI;                                     // flip 180 deg.
if (a2 > -0.5 * Math.PI) a2 = -0.5 * Math.PI;      // limit to 90 deg.

（错误是即使距离较短的点具有更大的角度，也会使用最长的距离 - 我现在就让它成为一个例子。它可以通过反转迭代来修复。）。

我发现效果很好的关系是地板和点之间的角度差乘以 2：

var da1 = Math.abs(a1);                            // get angle diff
var da2 = a2 < 0 ? Math.PI + a2 : Math.abs(a2);

a1 -= da1*2;                                       // double the diff
a2 += da2*2;

现在我们可以简单地计算控制点并使用张力值来微调结果：

var t = 0.8,                                       // tension
    cp1x = notes[0]     + dist1 * t * Math.cos(a1),
    cp1y = notes[1]     + dist1 * t * Math.sin(a1),
    cp2x = notes[len-2] + dist2 * t * Math.cos(a2),
    cp2y = notes[len-1] + dist2 * t * Math.sin(a2);

瞧：

ctx.moveTo(notes[0], notes[1]);
ctx.bezierCurveTo(cp1x, cp1y, cp2x, cp2y, notes[len-2], notes[len-1]);
ctx.stroke();

添加锥形效果

要创建在视觉上更令人愉悦的曲线，只需执行以下操作即可添加锥形：

在添加第一条贝塞尔曲线后，不要在路径上抚摸，而是用轻微的角度偏移调整控制点。然后通过添加另一条从右到左的贝塞尔曲线来继续路径，最后填充它（fill()将隐式关闭路径）：

// first path from left to right
ctx.beginPath();
ctx.moveTo(notes[0], notes[1]);                    // start point
ctx.bezierCurveTo(cp1x, cp1y, cp2x, cp2y, notes[len-2], notes[len-1]);

// taper going from right to left
var taper = 0.15;                                  // angle offset
cp1x = notes[0] + dist1*t*Math.cos(a1-taper);
cp1y = notes[1] + dist1*t*Math.sin(a1-taper);
cp2x = notes[len-2] + dist2*t*Math.cos(a2+taper);
cp2y = notes[len-1] + dist2*t*Math.sin(a2+taper);

// note the order of the control points
ctx.bezierCurveTo(cp2x, cp2y, cp1x, cp1y, notes[0], notes[1]);
ctx.fill();                                        // close and fill

最终结果（带有伪音符 - 张力 = 0.7，填充 = 10）

小提琴

建议改进：

• 如果两组的距离都很大，或者角度很陡，它们可能会被用作减少张力（距离）或增加张力（角度）的总和。
• 优势/面积因素可能会影响距离。表示最高部分在哪里移动的优势（它是在左侧还是右侧更多，并相应地影响每一侧的张力）。这本身可能/可能就足够了，但需要进行测试。
• 锥角偏移也应该与距离的总和有关系。在某些情况下，线条交叉并且看起来不太好。锥形可以用解析贝塞尔点的手动方法（手动实现）替换，并根据数组位置在原始点和返回路径的点之间添加距离。

希望这可以帮助！

Answer 2

基数样条和过滤方法

如果您愿意使用非贝塞尔方法，那么以下可以给出音符上方的近似曲线。

该解决方案包括 4 个步骤：

1. 收集音符/词根的顶部
2. 过滤掉路径中的“低谷”
3. 过滤掉同一斜率上的点
4. 生成基数样条曲线

这是一个原型解决方案，所以我没有针对所有可能的组合对其进行测试。但它应该为您提供一个良好的起点和继续前进的基础。

第一步很简单，收集代表音符顶部的点 - 对于演示，我使用以下点收集，它略微代表您在帖子中拥有的图像。它们按 x、y 顺序排列：

var notes = [60,40, 100,35, 140,30, 180,25, 220,45, 260,25, 300,25, 340,45];

这将表示如下：

然后我创建了一个简单的多通道算法，可以过滤掉同一斜率上的倾角和点。该算法的步骤如下：

• 当有anotherPass（真）时，它将继续，或者直到最初设置的最大通行数
• 只要skip未设置标志，该点就会被复制到另一个数组
• 然后它将当前点与下一个点进行比较，看它是否有下坡
• 如果是，它将下一个点与以下点进行比较，看看它是否有上坡
• 如果是这样，则认为是下降并skip设置了标志，因此不会复制下一个点（当前中间点）
• 下一个过滤器将比较当前点和下一个点之间的斜率，以及下一个点和下一个点之间的斜率。
• 如果它们相同skip，则设置标志。
• 如果它必须设置一个skip标志，它也会设置一个anotherPass标志。
• 如果没有过滤（或达到最大通过）点，则循环将结束

核心功能如下：

while(anotherPass && max) {
    
    skip = anotherPass = false;
    
    for(i = 0; i < notes.length - 2; i += 2) {
    
        if (!skip) curve.push(notes[i], notes[i+1]);
        skip = false;
        
        // if this to next points goes downward
        // AND the next and the following up we have a dip
        if (notes[i+3] >= notes[i+1] && notes[i+5] <= notes[i+3]) {
            skip = anotherPass = true;
        }
        
        // if slope from this to next point = 
        // slope from next and following skip
        else if (notes[i+2] - notes[i] === notes[i+4] - notes[i+2] &&
            notes[i+3] - notes[i+1] === notes[i+5] - notes[i+3]) {
            skip = anotherPass = true;
        }
    }
    curve.push(notes[notes.length-2], notes[notes.length-1]);
    max--;

    if (anotherPass && max) {
        notes = curve;
        curve = [];
    }
}

第一次通过的结果将是在偏移 y 轴上的所有点之后 - 请注意，浸渍音符被忽略：

在运行所有必要的传递之后，最终点数组将表示为：

剩下的唯一步骤是平滑曲线。为此，我使用了自己的基数样条实现（在麻省理工学院获得许可，可以在此处找到），它采用带有 x、y 点的数组并根据张力值添加插值点对其进行平滑处理。

它不会产生完美的曲线，但结果是：

小提琴

有一些方法可以改善我没有提到的视觉效果，但如果你觉得有必要，我会留给你去做。其中可能包括：

• 找到点的中心并根据角度增加偏移量，使其在顶部弧度更大
• 平滑曲线的端点有时会略微卷曲 - 这可以通过在第一个点正下方以及末端添加一个初始点来解决。这将迫使曲线具有更好看的开始/结束。
• 您可以通过在另一个数组上使用此列表中的第一个点但在弧的顶部有一个非常小的偏移量来绘制双曲线以产生锥形效果（薄的开始/结束，中间较厚），然后将其渲染在顶部.

该算法是为这个答案创建的，所以它显然没有经过适当的测试。可能会有特殊情况和组合将其扔掉，但我认为这是一个好的开始。

已知弱点：

• 它假设每个茎之间的距离对于斜率检测是相同的。如果组内的距离发生变化，则需要将其替换为基于因素的比较。
• 它将斜率与精确值进行比较，如果使用浮点值可能会失败。与 epsilon/公差进行比较