The Bezier Clipping Algorithm ¶

Contents¶

• a. Introduction
• b. Prerequisites
• 1. Overview of the bezier clipping algorithm
  • 1.1 Intersections of bezier curves
  • 1.2 Fatline of a bezier curve
  • 1.3 Finding intersections using fatline
  • 1.4 The clipping process in detail
  • 1.5 Multiple intersections
  • 1.6 The complete algorithm
• 2. The run-time behaviour of the bezier clipping algorithm
  • 2.1 Generating test data
  • 2.2 Rate of convergence
  • 2.3 Effect of parameters
• 3. Conclusions

Introduction¶

Bezier clipping or fatline clipping is a fast and efficient algorithm to find intersections between two bezier curves. Paper.js contains a javascript implementation of the bezier clipping algorithm based on the paper published by Sederberg T., Nishita T. (http://nishitalab.org/user/nis/cdrom/cad/CAGD90Curve.pdf). The implementation currently assumes cubic bezier curves.

This post attempts to explain the algorithm and its run time characteristics and behaviour. Especially what our implementation of the algorithm does and what it does not.

Prerequisites ¶

If you want to run this notebook locally; I would highly recommend it.

Along with all the usual stuff —IPython, Numpy, matplotlib, you would need the following.

Copy bezclip_manual.py into the same folder as this Ipython notebook.

(STATUTORY WARNING: code contains nonidiomatic, javascript-like python).

The file bezclip_manual.py is a direct translation of paper.js implementation of bezier clipping into python from javascript.This javascript $\leftrightarrow$ python change should not affect the behaviour of the algorithm discussed below in any significant way. The running time, memory used etc. might change however. The file also contains some not-so-interesting matplotlib code used to draw stuff.

Import the things we need.

Some configuration options.

1 Overview of the bezier clipping algorithm [TOP]

For the purpose of explanation we have to make some basic assumptions. Also I am assuming you are familiar with how bezier curves are defined and their basic properties.

1. When we talk about curves, it means specifically a $3^{rd}$ degree bezier curve (cubic bezier curve) expressed in parametric form.
2. A curve is defined by 4 control points or control vertices $(P_0, P_1, P_2, P_3)$
3. Then the explicit mathematical equation for curve $B$

$$\begin{equation} \tag{1} {\bf B(t)} = \sum_{i=0}^{3} \underbrace{{3 \choose i}}_{\text{binomial c.}} (1-t)^{(3-i)}.t^i.\underbrace{P_i}_{\text{CVs}} \end{equation}\ ~~~~~~|\ t = [0, 1]$$

4. $t$ is called the curve time parameter. For the curve above, $t$ varies between 0 and 1 inclusive.
5. The baseline of a curve, denoted by $\bf L$ is just the line connecting the start and end points of the curve.

1.1 Intersections of bezier curves [TOP]

We can largely group all possible intersections between two bezier curves A and B, into the following.

1. Crossings – The intersections between A and B are well spaced w.r.t. the error limit ($\epsilon$) chosen in the intersection finding algorithm.
2. Tangential intersections – Either A and B come very close to ($<\epsilon$) each other and then diverge, or A and B has a pair of intersections which are very close to each other ($\simeq\epsilon$)

The original bezier clipping algorithm, as detailed by Sederberg et. al. handles only crossings, though they extend the algorithm by introducing various concepts such as Focus of a curve. In this notebook, an intersection means a crossing, we are not going to deal with tangential intersections now.

1.2 Fatline of a bezier curve [TOP]

Fatline is just a wide line that completely contains the curve, it is represented by two lines parallel to the curve's baseline $\bf L$ of the curve, at distances $\bf d_{min}$ and $\bf d_{max}$ on either side of $L$.

Using the above method we can draw a fatline around a bezier curve.

1.3 Finding intersections using fatline [TOP]

Let's try and overlap two fatlines. Obviously, the intersection point will be contained within the intersection of both fatlines.

Let's say we pick Curve A and discard the parts of curve that is not within Curve B's fatline. Now we are left with a much smaller Curve A'. We use the fatline of this new curve to clip Curve B. We can narrow down on the intersection point by alternatively clipping the remnants of Curve A with the remnants of Curve B. We can stop once we have clipped both curves to nearly a small point.

NOTE: It might take a bit more time to render the following piece of code, since it renders all steps of the clipping process

The plots above shows how the algorithm recursively converges to the intersections.

The algorithm always converges to the intersections between two curves, if there are any; also note that the algorithm manages to narrow down on the actual intersection point quite rapidly, and the speed at which it narrows it down accelerates as we are closer to the actual intersection point.

In other words, the algorithm is globally convergent; and on average bezier clipping algorithm converges quadratically. We will examine these properties of the algorithm later in detail.

1.4 The clipping process in detail [TOP]

If we look closely at one of the clipping steps, the clipping is not really exact. In the plot below, Curve B is being clipped by the fatline of Curve A, and parts of curve B extends quite a bit from both sides of the fatline. If we clip enough curves, we can determine that the algorithm always underestimates the possible clip. This has one advantage that we always leave some room for error, and we will not miss the intersection point because of loss of precision doing arithmetic on small IEEE floating point numbers.

Let's consider the plot above, Curve $A$'s fatline is clipping Curve $B$. Fatline is a much simpler representation than the actual bezier curve. It is just two parallel lines at $(d_{min},\ d_{max})$ from the baseline ${\bf L}~of~curve~{\bf A}$. And we need a simpler representation for curve $\bf B$ as well.

For $B$, we would apply a simple transformation into something called a non-parametric bezier curve.

The plot on the right shows the non-parametric version of Curve $B$ (the dark blue curve on the left plot). It shows the distance of curve $\bf B$ from the fatline base $\bf L$ vs. the bezier time parameter $\bf t_i$. Note that the control points of the non-parametric curve are placed at equally spaced intervals on t, where t = [0, 1]. The non-parametric curve is just a mapping between the distance from a given line ($L$) and the curve time parameter of a bezier curve – for derivations see the paper mentioned in the introduction.

Now we can just clip this distance curve or non-parametric curve at $d_{min}$ and $d_{max}$* and look at the corresponding parameter $t_i$ on the x-axis of the second plot and keep parts of $B$ at $(t_{min} < t < t_{max})$.

But there is a small issue with this idea. The non-parametric curve is still a bezier curve, and it is expensive and difficult to calculate the intersection between a line and the non-parametric curve. If we recursively execute such an expensive operation, the algorithm might turn out to be the slowest in it's class.

We can use the convex-hull property of a bezier curve to make clipping much simpler and faster. We would just clip away parts of convex-hull of the non-parametric curve that lies above the horizontal line $y=d_{min}$ and the parts below $y=d_{max})$. Then we can choose $t_{min}$ and $t_{max}$ as the minimum and maximum values along the x-axis ($t_i$) corresponding to the clipped convex-hull. Convex-hull only contains straight lines and this is much easier to deal with.

A suitably low value $\epsilon$ is chosen, so that if $t_{diff}$ on both curves is less than that value, the algorithm stops clipping and returns the average of $t_{min}$ and $t_{max}$ as the intersection between A and B. In paperjs $\epsilon$ is defined as $1 \times 10 ^{-5}$.

This method can be optimised further to speed it up, such as generating convex-hulls faster since we already have some information about the nature of the non-parametric curve (control points equally spaced about the x-axis, only 4 points in case of cubic curves etc.).

In the plot above, you can rotate the fatline and notice how the algorithm behaves when the angle between the fatline and the curve changes.

*Also you may have noticed the relationship between the clipped bezier overhangs from the fatline edges (on the left plot) and the distance from the clipping points on the convex-hull (red markers on the right plot) and the nearest point on the non-parametric curve along $d_{min}$ or $d_{max}$.

1.5 Multiple intersections [TOP]

Like many subdivision algorithms, bezier clipping converges to one intersection at a time. If there are multiple intersections, the fatline would fail to clip away the curve effectively.

The way we handle this is to check if there is no significant reduction in $(t_{diff} = t_{max} - t_{min})$ between successive clipping operation, subdivide one of the curves in half and proceed with the algorithm. Sederberg et. al. recommends a reduction by at least 20% ($\Delta_t < 0.8$).

The value 0.8 was selected based on testing and various performance tradeoffs. Any value reasonably within the range (0.1, 0.9) may work with the algorithm, however if the value is too small, say <= 0.5, the algorithm will eagerly subdivide cases where it doesn't need to; or if this value is too high (> 0.85), the algorithm will try to recurse more without much success until, $\Delta t$ becomes more than this value and then subdivide.

1.6 The complete algorithm [TOP]

method clipBezier(A :curve, B: curve):

1. Compute the fatline for ${\bf A}$ $(L, d_{min}, d_{max})$
2. Compute the distance $d_i$ of control points of ${\bf B}$ from the fatline base
3. Create a non-parametric curve from the distances $d_i$ obtained above
4. Clip the convex-hull of the non-parametric curve, calculate $t_{min}$ and $t_{max}$
   1. If either the entire convex-hull is above $d_{max}$ or below $d_{min}$, the curves do not intersect
5. Let ${\bf B^\prime} \leftarrow B(t_{min}, t_{max})$ ; part of $B$ roughly contained by the fatline
6. If $(t_{max}-t_{min}) < errorEpsilon$:
   1. add $(t_{max}-t_{min})/2$ to the list of intersections
   2. Return
7. Else if $\Delta t_{current} > 0.8\ and\ \Delta t_{previous} > 0.8$:
   1. $parts \leftarrow subdivide(longest\ of\ (A, B^\prime))$; let $X$ be the shortest of $A, B^\prime$
   2. clipBezier($parts[0]$, $X$)
   3. clipBezier($parts[1]$, $X$)
8. Else:
   1. clipBezier($B^\prime$, $A$)

2 The run-time behaviour of the bezier clipping algorithm [TOP]

2.1 Generating test data [TOP]

A set of around 600 test cases are included in bezclip_manual.py file, since generating this test data may take some time (especially for number of intersections > 4).

The test data has the following distribution.

Please note that this distribution of test data is not representative of what the algorithm might encounter in real world, where I believe, a significant majority of the cases have 1 or 2 intersections between them.

One caveat of using randomly generated test cases is that, the curvature variations within the curve is often not wild enough to produce curve pairs intersecting at more than 6 or 7 locations. In order to asses the behaviour of the algorithm for different inputs, included below are some hand-rolled test cases, with number of intersections ranging from $1~to~9$. As you may remember, the maximum possible number of intersections between two cubic bezier curves is 9.

2.2 Rate of convergence [TOP]

To compare the performance, let's look at the amortised rate of convergence of the algorithm.

The bezier clipping algorithm converges to $L$ with a rate of convergence $\bf q$ if, there exists a number $\mu ~|~ \mu \in (0, 1)$ such that,

$$\begin{equation} \tag{2} \lim_{x\rightarrow\infty} {\frac {|x_{k+1}-L|}{|x_k-L|^q}} = \mu \end{equation}$$

Here we use $t_{diff}$, which should ideally converge to 0 at an intersection, so $L = 0$.

Reduce the results and plot them.

Try changing the plot for number of intersections between 1 and 7. The average rate of convergence per depth is around 2 is all cases from depth > ~10. Below is a plot of all test cases overlaid.

On average the clipping algorithm manages to narrow down on an intersection at the rate of 2 orders of magnitude of precision for each level of recursive call. The clipping algorithm performs dramatically better after the first few clips; mostly because during initial clips the algorithm spends some time subdividing the curves.

The algorithm has quadratic convergence on a single intersection. In the absence of subdivision, on average, the difference between the estimate and actual intersection value is squared after each successive clip. In practice, the step of subdividing curves reduces the rate of convergence by a little; as you can see in the plot above, the resultant rate of convergence is approximately 1.6 which is still superlinear.

2.3 Effect of parameters [TOP]

The bezier clipping algorithm has 2 parameters that may affect how the algorithm converges to intersections.

1. The $\bf t_{limit}$ — decides when to assume there may be multiple intersections and subdivide the curve.
2. A $\bf recursion_{max}$ parameter — The algorithm abandons the search for intersections if it reaches this maximum recursion depth.

The $recursion_{max}$ can be a suitably large value. Usually the algorithm will find all intersections within a depth of 30.

3. Conclusions [TOP]

I hope this gives a fair introduction to the bezier clipping algorithm. Checkout the implementation in javascript at https://github.com/paperjs/paper.js/. Please send pull-requests or file issues at the repository.

Thank you.

$/Hari$