Bézier subdivision recursively splits curves and uses their convex hulls to reduce intersection testing to smaller curve sections. section 15.4.4
An intersection test proceeds as follows:
- Construct the convex hull around each curve using its endpoints and control points. section 15.4.4
- Discard curve pairs whose convex hulls do not overlap. section 15.4.4
- Split overlapping curves in half and repeat the overlap comparison for their smaller sections. section 15.4.4
- Stop when no hulls overlap or sections are small enough to approximate with line segments within the allowed error. section 15.4.4
Quadratic and cubic curves
The method applies to quadratic, cubic, quartic, and generic Bézier curves; segment intersection testing finishes the sufficiently small cases. section 15.4.4
Figure 15.24 The Bézier subdivision method in action (first iteration). The points shown are the actual control points of cubic curves. This method can obviously also be applied to quadratic, quartic, or generic curves.
Shows the first subdivision iteration on cubic curves and illustrates how control points define the tested sections. section 15.4.4
