Bezier Clipping Is Quadratically Convergent

Authors

Christian Schulz

Year

2009

Journal Paper

Algorithm

Bezier Clipping

Source

Computer Aided Geometric Design

Identifiers

DOI 10.1016/j.cagd.2007.12.006

Abstract¶

In 1990 Sederberg et al. introduced Bézier clipping as a new method to determine the intersections of two Bézier curves in the plane. The method utilizes the convex hull property of Bézier curves. In experiments a quadratic convergence rate was observed at transversal intersections, the equivalent of simple roots of functions, but no formal proof for this has been provided. In this paper we formally prove the quadratic convergence rate. Bézier clipping bounds one of the curves by a region along a line. We also discuss the usefulness of arbitrary lines for creating these so called 'fat lines', leading to two general classes of fat lines which both give quadratic convergence.

Summary¶

Proves quadratic convergence properties for Bezier clipping under appropriate conditions. The result supports the use of Bezier clipping as a reliable geometric root-finding and intersection primitive in computer graphics and CAD.