0
\$\begingroup\$

I am using the code from the question Adding functionality to make individual anchor points of bezier continuous or non-continuous to create bezier curves (I added a line renderer).

How can I find the center of the curve for multiple cubic Bézier segments, where the centre of a bounding box is the centre of the curve (as in the image below)?

enter image description here

\$\endgroup\$
4
  • \$\begingroup\$ @TenOutOfTen Is this the sort of bounding box you're looking for? If so, let me know & I'll write it up an answer based on the linked content. And regarding the comment on curve type, if you are actually using cubic segments & not higher order curves, please edit your question to reflect that. Seconding guess people attempting to answer is likely to just cause additional confusion. \$\endgroup\$
    – Pikalek
    Oct 22, 2018 at 22:44
  • \$\begingroup\$ @Pikalek I Just edited the question. Yes, the bounding box you linked is what I am looking for. \$\endgroup\$ Oct 23, 2018 at 7:48
  • \$\begingroup\$ Okay - it'll take me at least a couple days before I devote time to writing up the full answer. If you happen to work it out before that & want to post the solution yourself, feel free to do so! \$\endgroup\$
    – Pikalek
    Oct 23, 2018 at 18:20
  • \$\begingroup\$ @Pikalek okay for now I'll give it a try. If I haven't posted the solution, that means I haven't been able to solve it :) \$\endgroup\$ Oct 24, 2018 at 17:56

1 Answer 1

1
\$\begingroup\$

You mentioned that you had a line renderer. If possible, the easiest way to find the bounds would be to track the min & max values for X & Y while rendering. If that's not possible, here's how to calculate the bounds after the fact.

The type of boundary box you're looking for is often called an axis aligned boundary box (AABB) because its sides are parallel (aligned) to the X & Y axis. This simplifies things because given multiple AABBs, we can an AABB that contains all the others by taking the min & max of their respective bounds. Thus, if we can find the AABB for each cubic Bézier segment, we can find the final answer.

Here's the overview of how to calculate an AABB for a cubic Bézier curve:

  • Find the extremities (the x & y roots).
  • Find all t values for roots.
  • Discard any t values lower than 0 or higher than 1,because Bézier curves only use the interval [0,1].
  • Track the lowest and highest results found when plugging the roots into the cubic Bézier equation: the lowest value is the lower bound, and the highest value is the upper bound for the bounding box we want to construct.

The derivative of a cubic curve is a quadratic curve, so we can find the roots Bézier curve means we can apply the quadratic formula. If p1 is the start, p2 is the first control point, p3 is the second control point and p4 is the end, we can solve for t as shown below. Note, because of the ± there may be more than one value for t generated. $$\begin{align}t&={-b\pm\sqrt{b^2-4ac} \over 2a} \\ a &= 3(-p_1+3p_2-3p_3+p_4) \\ b &= 6(p_1-2p_2+p_3) \\ c &= 3(p_2-p_1) \end{align} $$ Note that since your p values have both an X & Y component, you'll essentially run through the equations above twice: once for X & again for Y. Also, you will need to add some code that guards against division by zero.

Discard any t values that are less than 0 or greater than 1. Then take the remaining values, along with 0 & 1, and plug them into the formula for a cubic Bézier: $$f(t) = p_1(1-t)^3 + 3p_2t(1-t)^2 + 3p_3t^2(1-t) + p_4t^3$$

As you plug the t values in, check the results & save the smallest and largest X & Y values. Repeating the process for each curve will give you the min & max values for an AABB that encloses all of the curves examined.

To verify your answers during debugging, step through the cubic Bézier equation with some small value for t, for instance, t = 0.001. While this won't give you the exact roots, the results should be close enough to double check your work. You probably want to avoid this in your final code because it's not as accurate or efficient as solving for the roots.

Regarding your additional question on rotation: you can rotate the curve(s) around a point by rotating all of the start, end & control points around the point.

My main reference for this answer was Pomax's Primer on Bézier Curves, which I strongly recommend. You might also find this question on SO useful.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Similar article iquilezles.org/www/articles/bezierbbox/bezierbbox.htm \$\endgroup\$
    – Bálint
    Oct 26, 2018 at 6:18
  • \$\begingroup\$ @Bálint Nice! I like that your link also included the matrix representation. Pomax covers that as well, but there's so much material covered, it's sometimes hard to pick the correct trees out of the forest so to speak. I hadn't considered calculating a loose bounding box, but it makes sense that you could do so using just the Bézier points. Might have to see if I can use that as a first pass filter for something I was working on. Thanks! \$\endgroup\$
    – Pikalek
    Oct 26, 2018 at 13:34
  • \$\begingroup\$ @Pikalek I am yet to try your solution. I just separated the question, I realised the second part needed to be a question on it's own \$\endgroup\$ Oct 27, 2018 at 14:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .