计算三次贝塞尔曲线的边界框

Question

我试图找到一个算法来计算给定的三次贝塞尔曲线的边界框.曲线在3D空间中.

除了曲线上的采样点和计算这些点的边界框之外,是否有一种数学方法可以做到这一点？

Answer 1

大多数这是在一个算法中解决,以找到闭合贝塞尔曲线的边界框？除了这里我们有立方贝塞尔曲线,他们在那里处理二次贝塞尔曲线.

基本上你需要采用每个坐标函数的导数.如果x-coord由.给出

x = A (1-t)^3 +3 B t (1-t)^2 + 3 C t^2 (1-t) + D t^3

区别于t.

dx/dt =  3 (B - A) (1-t)^2 + 6 (C - B) (1-t) t + 3 (D - C) t^2
      =  [3 (D - C) - 6 (C - B) + 3 (B - A)] t^2
       + [ -6 (B - A) - 6 (C - B)] t
       + 3 (B - A) 
      =  (3 D - 9 C + 9 B - 3 A) t^2 + (6 A - 12 B + 6 C) t + 3 (B - A)

这是我们可以写的二次方a t^2 + b t + c.我们想dx/dt = 0用二次公式解决你可以做的事情

- b +/- sqrt(b^2-4 a c)
-----------------------
        2 a

解决这个问题要么提供两个解决方案t0,t1说,没有解决方案,或者在极少数情况下只有一个解决方案.我们只对0 <= t <= 1的解决方案感兴趣.您将有最多四个候选点,两个端点和两个解决方案.找到这些中的哪些极端点是一件简单的事情.

您可以为每个坐标重复相同的过程,然后获取边界框.

我把这个用于js小提琴中的2D案例http://jsfiddle.net/SalixAlba/QQnvm/4/

Answer 2

查找三次贝塞尔曲线(或任何度数的B样条曲线)的边界框通常通过查找曲线控制多边形的边界框来完成.由于曲线始终由其控制多边形限定,因此通过控制多边形获得的边界框保证包围曲线.您还可以对曲线执行结点插入,并使控制多边形变得更接近曲线本身.所以,通用算法将如下所示:

1)从控制多边形中找到当前B样条曲线的边界框(表示为BBox1).
2)在B样条曲线中的每个贝塞尔曲线段的中间参数处插入结.
3)找到新B样条曲线的边界框(表示为BBox2).
4)将BBox2与BBox1进行比较.如果BBox2与BBox1几乎相同,我们就完成了.如果BBox2比BBox1小得多,重复步骤2到4直到收敛.

Answer 3

本文解释了详细信息，并且还有一个现场 html5 演示：
计算/计算三次贝塞尔曲线的边界框

我在 Snap.svg 中找到了一个 javascript 来计算：这里
看到 bezierBBox 和 curveDim 函数。

我重写了 2 个 javascript 函数，用于三次贝塞尔曲线和二次贝塞尔曲线。

//For cubic bezier.
//(x0,y0) is start point; (x1,y1),(x2,y2) is control points; (x3,y3) is end point.
function cubicBezierMinMax(x0, y0, x1, y1, x2, y2, x3, y3) {
    var tArr = [], xArr = [x0, x3], yArr = [y0, y3],
        a, b, c, t, t1, t2, b2ac, sqrt_b2ac;
    for (var i = 0; i < 2; ++i) {
        if (i == 0) {
            b = 6 * x0 - 12 * x1 + 6 * x2;
            a = -3 * x0 + 9 * x1 - 9 * x2 + 3 * x3;
            c = 3 * x1 - 3 * x0;
        } else {
            b = 6 * y0 - 12 * y1 + 6 * y2;
            a = -3 * y0 + 9 * y1 - 9 * y2 + 3 * y3;
            c = 3 * y1 - 3 * y0;
        }
        if (Math.abs(a) < 1e-12) {
            if (Math.abs(b) < 1e-12) {
                continue;
            }
            t = -c / b;
            if (0 < t && t < 1) {
                tArr.push(t);
            }
            continue;
        }
        b2ac = b * b - 4 * c * a;
        if (b2ac < 0) {
            if (Math.abs(b2ac) < 1e-12) {
                t = -b / (2 * a);
                if (0 < t && t < 1) {
                    tArr.push(t);
                }
            }
            continue;
        }
        sqrt_b2ac = Math.sqrt(b2ac);
        t1 = (-b + sqrt_b2ac) / (2 * a);
        if (0 < t1 && t1 < 1) {
            tArr.push(t1);
        }
        t2 = (-b - sqrt_b2ac) / (2 * a);
        if (0 < t2 && t2 < 1) {
            tArr.push(t2);
        }
    }

    var j = tArr.length, mt;
    while (j--) {
        t = tArr[j];
        mt = 1 - t;
        xArr[j] = (mt * mt * mt * x0) + (3 * mt * mt * t * x1) + (3 * mt * t * t * x2) + (t * t * t * x3);
        yArr[j] = (mt * mt * mt * y0) + (3 * mt * mt * t * y1) + (3 * mt * t * t * y2) + (t * t * t * y3);
    }

    return {
        min: {x: Math.min.apply(0, xArr), y: Math.min.apply(0, yArr)},
        max: {x: Math.max.apply(0, xArr), y: Math.max.apply(0, yArr)}
    };
}


//For quadratic bezier.
//(x0,y0) is start point; (x1,y1) is control points; (x2,y2) is end point.
function quadraticBezierMinMax(x0, y0, x1, y1, x2, y2) {
    var xArr = [x0, x2], yArr = [y0, y2], a, b, c, t;
    for (var i = 0; i < 2; ++i) {
        a = i == 0 ? x0 - 2 * x1 + x2 : y0 - 2 * y1 + y2;
        b = i == 0 ? -2 * x0 + 2 * x1 : -2 * y0 + 2 * y1;
        c = i == 0 ? x0 : y0;
        if (Math.abs(a) > 1e-12) {
            t = -b / (2 * a);
            if (0 < t && t < 1) {
                [xArr, yArr][i].push(a * t * t + b * t + c);
            }
        }
    }
    return {
        min: {x: Math.min.apply(0, xArr), y: Math.min.apply(0, yArr)},
        max: {x: Math.max.apply(0, xArr), y: Math.max.apply(0, yArr)}
    };
}