计算三次贝塞尔曲线的边界框 [英] 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.

我已将其用于JS小提琴中的2D情况 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屋！