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

Question

具体来说,我正在使用javascript在canvas中工作.

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

问题出现在下图中,即使您不熟悉音乐符号,问题仍然应该是相当清楚的.曲线的点是红点

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

所以很自然地,必须在边界框和曲线之间检测到碰撞(这里的某个方向会很好,但我一直在浏览并看到有相当数量的信息).但是在检测到碰撞后会发生什么？计算控制点位置以制作看起来更像的东西会发生什么:

Answer 1

贝齐尔的方法

最初的问题是一个广泛的问题 - 甚至可能更广泛的问题,因为有许多不同的情景需要考虑制定"一个适合所有人的解决方案".这是一个完整的项目.因此,我将提供一个可以构建的解决方案的基础 - 它不是一个完整的解决方案(但接近一个......).我在最后添加了一些关于添加的建议.

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

将笔记分为两组,左侧和右侧.

然后,控制点基于从第一个(结束)点到该组中任何其他音符的​​最大角度,以及到第二个组中任何点的最后一个结束点.

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

角度,倍增,距离,张力和填充偏移将允许微调以获得最佳的总体结果.可能存在需要额外条件检查的特殊情况,但这不在此范围内(它不是完整的密钥就绪解决方案,但为进一步工作提供了良好的基础).

来自该流程的几个快照:

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

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.

(错误是即使较短的距离点具有更大的角度,也会使用最长的距离 - 我现在将其视为一个例子.它可以通过反转迭代来修复.).

我发现的关系很好,是地板和点之间的角度差两倍:

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();

增加逐渐减少的效果

要创建曲线,可以通过以下操作简单地添加逐渐变细的渐变:

在添加第一条贝塞尔曲线之后,不是抚摸路径,而是以微小的角度偏移调整控制点.然后通过添加另一条从右到左的Bezier曲线继续路径,最后填充它(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)

小提琴

建议的改进:

• 如果两组的距离都很大,或者角度很陡,它们可能会被用作减少张力(距离)或增加它(角度)的总和.
• 优势/面积因素可能会影响距离.优势表示最高的部件在哪里移位(它是否位于左侧或右侧,并相应地影响每侧的张力).这可能/可能足够自己但需要进行测试.
• 锥角偏移也应与距离之和有关.在某些情况下,线条交叉并且看起来不那么好.可以用解析Bezier点(手动实现)的手动方法替换锥度,并根据阵列位置在原始点和返回路径的点之间添加距离.

希望这可以帮助!

Answer 2

红衣主教样条和过滤方法

如果您打开使用非Bezier方法,则以下可以在音符杆上方给出近似曲线.

该解决方案包括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轴上的所有点之后 - 注意忽略倾斜音符:

在完成所有必要的传递之后,最终的点数组将表示为:

剩下的唯一步骤是使曲线平滑.为此,我使用了我自己的基数样条实现(在MIT下许可,可以在这里找到),它采用x,y点和平滑的数组,它根据张力值添加插值点.

它不会产生完美的曲线,但结果将是:

小提琴

有一些方法可以改善我没有解决过的视觉效果,但如果您觉得有必要,我会留给您做.其中可能是:

• 找到点的中心并根据角度增加偏移量,使其在顶部更加圆弧
• 平滑曲线的终点有时会略微卷曲 - 这可以通过在第一个点的正下方和末尾添加一个初始点来修复.这将迫使曲线具有更好的开始/结束.
• 您可以绘制双曲线以通过在另一个阵列上使用此列表中的第一个点但在弧顶部具有非常小的偏移来进行锥形效果(较薄的开始/结束,在中间较厚),然后将其渲染到顶部.

这个算法是为这个答案创建的ad-hook,所以它显然没有经过适当的测试.可能会有特殊情况和组合将其抛弃,但我认为这是一个良好的开端.

已知的弱点:

• 它假设每个杆之间的距离对于斜率检测是相同的.如果距离在组内变化,则需要用基于因子的比较来替换.
• 它将斜率与精确值进行比较,如果使用浮点值,则可能会失败.与epsilon /容差比较