CODEWITHSUNDEEP
beziersplineafter-effectscubic
Tomas Sinkunas
Tomas Sinkunas

Reputation: 11

Subdivide multi segmented Cubic Bezier spline

First of let me apologies for a bad English and probably not very straight forward question, as I am not really sure how to call it.

I have a multi segmented Cubic Bezier curve In After Effects, it is is defined by 5 vertices with IN & OUT tangents. My task is to subdivide it into N small linear chunks in Java Script.

EDIT submited more info. Given a multi segmented Cubic Bezier spline defined by 5 points with In & Out tangents, I need to get a linear representation of it. Where N is number of linear segments, defined by user.

Cubic Bezier Spline:

Segment1: P0, P0out, P1in, P1;
Segment2: P1, P1out, P2in, P2;
Segment3: P2, P2out, P3in, P3;
Segment4: P3, P3out, P4in, P4;

Expected output:

N = 1: linear spline with 2 anchors representing entire shape;
N = 2: linear spline with 3 anchors representing entire shape;
N = 3: linear spline with 4 anchors representing entire shape;
N = 4: linear spline with 5 anchors representing entire shape;
...
N = 8: linear spline with 9 anchors representing entire shape;

distance(L0,L1) = distance(L1,L2) = distance(L2,L3) = ... = distance(L-n, Ln)

In example image I use 4-segmented spline, where segment length is equal to one another - this is just easier to draw to explain my task. But in real project those segments will not be equal, and there will be more then 4 segments total.

I have looked at de Casteljau method, but as I can understand, it works with one segment spline. My math skills are dusty, so I am not really sure if I can use de Casteljau in my example.

Upvotes: 1

Views: 1271

Answers (2)

Mike 'Pomax' Kamermans
Mike 'Pomax' Kamermans

Reputation: 53538

This is conceptually straight forward, although it might involve quite a bit of code for reasons explained a little later on. What you're trying to do is flatten a (cubic) poly-Bezier, so let's start with that:

Individual cubic Bezier curves are generated by four points: a start point, a control point that determines the tangent at the start point, an end point, and a control point that determines the tangent at the end point. The curve, then, is a plot of the cubic Bezier function:

Bx(t) = p1.x × (1-t)³ + 2 × p2.x × (1-t)² × t + 2 × p3.x × (1-t) × t² + p4.x × t³
By(t) = p1.y × (1-t)³ + 2 × p2.y × (1-t)² × t + 2 × p3.y × (1-t) × t² + p4.y × t³

A single Bezier curve is plotted over the interval t=[0,1], so a poly-Bezier of N segments is plotted over a total interval N × [0,1].

First, the simple case: simple flattening. Bezier curves are non-linear curves and so let's first not bother to enforce "same length for each of the line segments". Given an N-segment poly-Bezier:

S = number of segments we want
points = empty list
for (s = 0):(s = S):(step = S/N):
  v = s * step
  segmentid = floor(v)
  segment = polycurve.segments[segmentid] 
  t = v % 1
  points.push(
    segment.pointAt(t)
  )

We now have all the points we need, and we just connect them with lines. Done.

However, Bezier curves are non-linear curves, so flattening in this way does not yield equidistant segments in the slightest. If we want to do that, we need to work with distance along the curve rather than t values. 

S = number of segments we want
points = empty list
for (s = 0):(s = S):(step = S/N):
  v = s * step
  segmentid = floor(v)
  segment = polycurve.segments[segmentid]
  distanceRatio = v % 1
  t = segment.getTforDistanceRatio(distanceRatio)
  points.push(
    segment.pointAt(t)
  )

This will work exactly as you want, but getTforDistanceRatio is the hard part, because what we're doing here is reparameterizing the curve for distance, rather than time, and that is a very hard mathematical problem (for which no general symbolic solution exists). The cheapest way to do this is using a Lookup Table (LUT), which is explained in the link above, for "distance along the curve".

Upvotes: 1

fang
fang

Reputation: 3623

The de Casteljau method is used to compute a point on the Bezier curve and also obtain the control points for the two subdivided curves in the process. So, yes you should be able to use de Cateljau method to evaluate as many points as you want on a Bezier curve if you know the control points.

From the picture you show and the fact that your "cubic Bezier spline" takes in/out tangents as input, I think your spline is actually "cubic Hermite spline", in which each segment is indeed a cubic Bezier curve. You can convert each segment of your spline to a cubic Bezier curve, then use de Cateljau method to evaluate as many points as you want, then connect these points by straight lines.

Upvotes: 0

Related Questions