[Math] How to clip Bézier curves using Casteljau’s algorithm

bezier-curveparametric

I am attempting to approximate intersections of Bézier curves using iterative clipping.

This common method is described here and here.

It basically works like this:

  1. Find bounding lines outside one curve.

  2. Clip the other curve to these lines.

  3. Alternate and repeat.

There are some extra cases to handle (multiple intersections), but that's the idea.

I get stuck on step (2). In a one sentence explanation, both sources say to use de Casteljau's algorithm to clip the curve $P$ to between $t_1$ and $t_2$.

Bézier clipping is completed by subdividing $P$ twice using the de Casteljau algorithm, such that
portions of $P$ over parameter values $t < 0.25$ and $t > 0.75$ are removed.

I understand how to use de Casteljau's to split a curve on a single $t$ value, but not multiple.

How is this intended to work?

Best Answer

Lets call the original curve $C1$, and suppose we want to clip it to the parameter interval $[0.25, 0.75]$. We do this by applying de Casteljau splitting twice.

First, split $C1$ at $t=0.75$. Keep the "left" portion (the one corresponding to $[0,0.75]$) and throw away the right portion. Call the resulting curve $C2$.

Now we want to split $C2$. The split has to happen at the point $P$ that corresponds to $t=0.25$ on the original curve $C1$. The only subtlety is that the point $P$ corresponds to $t=\tfrac13$ on the curve $C2$, because $0.25 = \tfrac13*0.75$. So, split $C2$ at $t=\tfrac13$, and keep the right-hand portion, $C3$. The curve $C3$ is the one you want.