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

9
具体来说,我正在使用JavaScript中的Canvas工作。
基本上,我有一些对象,它们具有要避免但仍然被贝塞尔曲线包围的边界。 但是,我甚至不知道从哪里开始编写算法以移动控制点以避免碰撞。
问题在下面的图像中,即使您不熟悉音乐符号,问题也应该相当明显。 曲线的点是红点。
此外,我可以访问每个音符的边界框,其中包括茎。
因此,必须在边界框和曲线之间检测到碰撞(在这里提供一些方向会很好,但我一直在浏览并看到有大量关于此的信息)。 但是,在检测到碰撞后会发生什么? 必须发生什么才能计算控制点位置以使其看起来更像:

你是在说自动将曲线放在音符上面吗?问题在于有无限多的解决方案,其中曲线在音符上方。我可以看到一种非自动化的解决方案,即手动将代表控制点的红点移动到正确位置。 - markE
我不是在寻找非自动化的解决方案,只需要至少能近似最佳位置的东西。 - Cyril Silverman
2个回答

9

Bezier方法

最初这个问题是一个广泛的问题 - 甚至对于SO来说也可能过于广泛,因为有许多不同的情况需要考虑以制定“一种适合所有情况的解决方案”。这本身就是一个完整的项目。因此,我将提供一个基础解决方案,您可以在此基础上构建 - 它不是一个完整的解决方案(但接近于一个解决方案..)。我在末尾添加了一些建议。

此解决方案的基本步骤如下:

将笔记分组为左侧部分和右侧部分。

然后,控制点基于第一个(结束)点的最大角度和该组其他任何笔记的距离,以及最后一个结束点到第二组中的任何点的距离。

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

角度、加倍、距离、张力和边距偏移量将允许微调以获得最佳的整体结果。可能会有一些特殊情况需要额外的条件检查,但这超出了此处覆盖的范围(它不会是一个完整的键准备解决方案,但提供了一个良好的基础,可进一步工作)。

过程中的几个快照:

image2

image3

示例中的主要代码分为两个部分,两个循环解析每半部分以查找最大角度和距离。这可以合并为单个循环,并引入第二个迭代器从右到中间进行迭代,除了从左到中间的迭代器外,但为了简单起见并更好地理解发生了什么,我将其拆分为两个循环(并在第二半部分引入了一个错误 - 请注意,我将其留作练习)。

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.

(这个 bug 是使用了最长距离,即使一个角度更大的点有较短的距离 - 我现在将其保留作为示例。可以通过反转迭代来修复它。)

我发现有效的关系是地板和点之间的角度差乘以二:

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)

taper

FIDDLE

建议改进:

  • 如果两组距离很远或者角度很陡峭,它们可能可以用作总和来减少张力(距离)或增加张力(角度)。
  • 支配/面积因素可能会影响距离。支配表示最高部分偏移的位置(它是否更多地位于左侧或右侧,并相应地影响每一侧的张力)。这可能已经足够了,但需要测试。
  • 锥度角偏移量也应与距离总和有关系。在某些情况下,线条交叉并不好看。可以用手动方法解析贝塞尔点(手动实现),并根据数组位置添加原始点和返回路径点之间的距离。

希望这可以帮到你!


2
+1 不错的方法!将目标分成左右两部分很适合使用影响曲线左右部分的三次贝塞尔控制点。是的...非常好! - markE
3
太棒了!再次感谢您提供非常详尽并且解释得非常清楚的解决方案。 - Cyril Silverman

6

Cardinal样条和滤波方法

如果您愿意使用非Bezier方法,则以下方法可以给出一个大致的曲线,覆盖在音符干杆上方。

此解决方案包括4个步骤:

  1. 收集音符/干杆顶部的点
  2. 过滤路径中的“低谷”
  3. 过滤掉同一斜率的点
  4. 生成一个Cardinal样条曲线

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

第一步很容易,收集代表音符干杆顶部的点 - 对于演示,我使用以下点集,它略微表示您在帖子中的图像。它们按x,y顺序排列:

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

这将被表示为:

image1

然后我创建了一个简单的多通道算法,过滤掉相同斜率上的凹点和凸点。算法的步骤如下:

  • 只要有anotherPass(true),它就会继续,或者直到最初设置的最大通过数
  • 只要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轴上的偏移都被处理掉了,注意这个下沉的音符被忽略了: image2 经过所有必要的处理后,最终的点数组如下图所示: image3 唯一剩下的步骤就是使曲线平滑。为此,我使用了我自己实现的基数样条(在MIT下获得许可,并且可以在此处找到),它接受一个包含x、y点的数组,并根据张力值添加插值点来平滑它。
它不会生成完美的曲线,但从这个结果中可以看出: image6 FIDDLE 有些方法可以改进视觉效果,但我将把它留给你去完成,如果你认为需要的话。其中可能包括:
- 查找点的中心并根据角度增加偏移量,以便在顶部形成更弯曲的弧线。 - 平滑曲线的端点有时会卷曲-这可以通过在第一个点的正下方添加一个初始点以及在末尾处添加一个点来解决。这将强制曲线有更好的起始/结束外观。 - 你可以绘制双曲线,通过使用此列表中的第一个点在另一个数组上进行微小偏移的方式来产生锥形效果(从顶部变窄/末端变宽),然后在上面渲染它。
该算法是为了回答而创建的,因此显然没有经过适当的测试。可能存在特殊情况和组合使其失效,但我认为这是一个好的开始。
已知缺点:
- 它假定斜率检测时每个茎之间的距离相同。如果距离在一组内变化,则需要使用基于比较的因子来替换它。 - 它将斜率与精确值进行比较,如果使用浮点值可能会失败。应该使用epsilon/公差进行比较。

非常感谢您的详细回复!使用fiddle玩耍,它确实运行得非常好。一些更加刺耳的组合可能会使其有些失调,但我相信通过一些修改可以解决这个问题。如果我找不到贝塞尔曲线的解决方案,那么这可能是我要走的路线。但是,对于这种用例,贝塞尔曲线绝对可以创建最美观的曲线,所以我仍然想追求它。 - Cyril Silverman

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接