liveBook · Manning

Bézier subdivision

As explained in Advanced Algorithms and Data Structures

Bézier subdivision is a technique that recursively splits Bézier curves into smaller curve sections for geometric analysis.

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

How Advanced Algorithms and Data Structures covers it

How deep it goes
Explains convex-hull filtering, recursive halving, and error-based termination, while deferring Bézier clipping details.
Examples
Uses quadratic, cubic, quartic, and generic curves, including a first-iteration cubic subdivision diagram.
What it assumes
Assumes Bézier curves and control points, while defining convex hulls as smallest containing convex sets.
What you can do after
Apply it to test curve intersections through hull overlap, recursive subdivision, and bounded segment approximation.
How it connects
Connects Bézier curves with convex hulls, line-segment intersection, Bézier clipping, and interval subdivision.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.