计算三次贝塞尔曲线的边界框 [英] Calculating the bounding box of cubic bezier curve

问题描述

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

I am trying to find an algorithm to calculate the bounding box of a given cubic bezier curve. The curve is in 3D space.

除了在曲线上采样点并计算这些点的边界框之外，是否有数学方法可以做到这一点?

Is there a mathematic way to do this except of sampling points on the curve and calculating the bounding box of these points?

推荐答案

大部分内容在 一种找到封闭贝塞尔曲线边界框的算法? 除了这里我们有三次贝塞尔曲线，而那里他们处理的是二次贝塞尔曲线.

Most of this is addressed in An algorithm to find bounding box of closed bezier curves? except here we have cubic Beziers and there they were dealing with quadratic Bezier curves.

本质上，您需要获取每个坐标函数的导数.如果 x 坐标由

Essentially you need to take the derivatives of each of the coordinate functions. If the x-coord is given by

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 你可以使用二次公式

this is a quadratic which we can write at a t^2 + b t + c. We want to solve dx/dt = 0 which you can do using the quadratic formula

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

解决这个问题将给出两个解决方案 t0，t1，比如说，没有解决方案，或者在极少数情况下只有一个解决方案.我们只对 0 <= t <= 1 的解决方案感兴趣.您将拥有最多四个候选点，两个端点和两个解决方案.找出其中哪些给出极值点很简单.

Solving this will either gives two solutions t0, t1 say, no solutions or in rare case just one solution. We are only interest in solutions with 0 <= t <= 1. You will have a maximum of four candidate points, the two end points and the two solutions. Its a simple matter to find which of these give the extreme points.

您可以对每个坐标重复相同的过程，然后得到边界框.

You can repeat the same process for each coordinate and then get the bounding box.

我已经把这个用于 2D 案例的 js fiddle http://jsfiddle.net/SalixAlba/QQnvm/4/

I've put this for the 2D case in a js fiddle http://jsfiddle.net/SalixAlba/QQnvm/4/

这篇关于计算三次贝塞尔曲线的边界框的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！