2
$\begingroup$

If I want to draw a cubic bezier curve, I need to sample points on it and draw the resulting poly lines. One could sample the curve using De Casteljau algorithm and incrementing $t$ from 0 to 1 with a given interval. However depending on the length of the curve or how far away the control points are from each other, one might want to choose bigger or smaller sampling interval. Is there a good metric to calculate a satisfactory sampling interval? Would the the length of the poly lines formed by the control points of the bezier curve be considered a good metric? Or the length of the curve itself?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Consider computing the rate of curvature of the curve. (there are lots of sources for this on the net) Where it is flat use less samples, where it is more curved subdivide and check the curvature again. Another approach is to do arc fitting which is described here: pomax.github.io/bezierinfo/#arcapproximation $\endgroup$
    – pmw1234
    Commented Jul 18, 2022 at 10:48
  • $\begingroup$ @pmw1234 Thanks I'll have to read through the arc approximation method but computing the rate of the curvature sounds like a great idea! However I wonder would you sample the rate (or I guess the first derivative) at specific intervals for t or how would you do it? $\endgroup$
    – Lenny White
    Commented Jul 19, 2022 at 3:30
  • $\begingroup$ Here is a video that explains the issues really well, about half way through she covers curvature, and curve length is covered at the end: youtube.com/watch?v=aVwxzDHniEw $\endgroup$
    – pmw1234
    Commented Jul 19, 2022 at 10:34
  • $\begingroup$ Also note how the evenly spaced t values tend to "bunch up" where acceleration is high, this means that a nicely subdivided t interval might be "good enough" to capture the curve. If anything the areas on the curve that are flat may tend to have too few points. $\endgroup$
    – pmw1234
    Commented Jul 19, 2022 at 10:37
  • $\begingroup$ Also note that the curvature rate $\kappa$ formula is slightly different for 2d and 3d. $\endgroup$
    – pmw1234
    Commented Jul 19, 2022 at 10:39

1 Answer 1

Reset to default
2
$\begingroup$

IIRC, Watt and Watt's "Advanced Animation and Rendering Techniques" (Chapter 3) has an interesting discussion on this (which I think is summarising the work of Clark https://dl.acm.org/doi/10.1145/965103.807440 ... but only the first page seems to be there :-( )

UPDATE: There is some text from Watt and Watt describing Clark's method available here:

If that's not to your taste, you could try the following: Take the Cubic Bezier cage - shown in green - with the curve in purple:

Bezier (Possibly not 100% accurate)

If you do a do a mid-point subdivision of the curve, you can measure the (squared) distance (red) from the centre of the straight line (blue) joining the original end points to the mid point of your curve. If this exceeds a threshold (some number of pixels), recurse, else stop.

I seem to recall that the difference between the straight-line approx and the curve drops by a factor of 4 (or was it 8??) with each subdivision, so it converges quite rapidly.

The maths to subdivide the 4 control points of any Cubic Bezier into 2 smaller Beziers is quite simple .. but I'd need to go and look it up ...

Update 2: See here for splitting a Bezier in 'twain'

Though, thinking about it, I'd say you might need to go one more step to account for this type of starting case:

enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the suggestion! Can I ask if this technique you explained is used or documented anywhere? $\endgroup$
    – Lenny White
    Commented Jul 19, 2022 at 3:31
  • $\begingroup$ Well, I think the description in Watt and Watt (archive.org/details/…) of Clark's work might have a more direct approach in terms of how to compute an estimate of how much displacement there is between a line segment and a (subdivided) curve. OOH I've found an link. Will update the text above $\endgroup$
    – Simon F
    Commented Jul 19, 2022 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.