Introduction

When working with vector graphics, 3D modeling, or computer-aided geometric design, piecewise-cubic Bezier paths are widely used due to their simplicity and smoothness. A Bezier path composed of piecewise-cubic segments provides a flexible and efficient way to represent complex curves. However, adjusting these paths by inserting new points can be challenging. This article walks through the algorithm for inserting points into a piecewise-cubic Bezier path, using the De Casteljau subdivision method to maintain continuity and precision.

Understanding Cubic Bezier Curves

Before exploring the insertion algorithm, it is essential to understand a cubic Bezier curve, defined by four control points: $P_0$, $P_1$, $P_2$, and $P_3$. The parametric equation for a cubic Bezier curve is:

$$B(t) = (1-t)^3 P_0 + 3(1-t)^2 t P_1 + 3(1-t) t^2 P_2 + t^3 P_3, \quad t \in [0,1]$$

This equation creates a smooth curve from $P_0$ to $P_3$, controlled by intermediate points $P_1$ and $P_2$ that shape the tangent directions at the endpoints.

Why Insert Points?

Inserting new points into a Bezier path may be necessary for several reasons:

1. Increasing Path Detail: Adding points allows for finer, more detailed rendering of the curve.
2. Path Modification: Helps adjust the curve shape without rebuilding the entire path.
3. Collision Detection: Allows algorithms to work on a set of smaller segments rather than one large curve.
4. Animation Precision: Refines paths used for animations, ensuring precise movement along the curve.

Algorithm for Insertion

Overview

1. Determine the Segment: Identify which segment of the Bezier path contains the insertion point.
2. Subdivide with De Casteljau: Split the segment into two sub-curves at the parameter value $t$.
3. Create New Control Points: Calculate the control points for both new segments.
4. Preserve Continuity: Ensure that the new segments connect smoothly to maintain the curve's continuity.

Step 1: Determine the Segment

Given a set of piecewise-cubic Bezier segments, determine which segment contains the parameter value $t$ where the new point must be inserted. This step involves iterating over the segments and finding the one whose parametric interval contains $t$.

Step 2: Subdivide Using De Casteljau

The De Casteljau algorithm is the standard tool for splitting a cubic Bezier curve at parameter $t$. Given the original control points $P_0, P_1, P_2, P_3$, compute intermediate points through successive linear interpolation:

First level:

• $Q_0 = (1-t) P_0 + t P_1$
• $Q_1 = (1-t) P_1 + t P_2$
• $Q_2 = (1-t) P_2 + t P_3$

Second level:

• $R_0 = (1-t) Q_0 + t Q_1$
• $R_1 = (1-t) Q_1 + t Q_2$

Third level (the point on the curve):

• $S = (1-t) R_0 + t R_1$

The point $S$ is the new insertion point, lying exactly on the original curve at parameter $t$.

Step 3: Create New Control Points

The two new Bezier segments are defined by:

• First segment: $[P_0, Q_0, R_0, S]$
• Second segment: $[S, R_1, Q_2, P_3]$

Both segments together trace exactly the same curve as the original segment. No approximation is involved. This is one of the key strengths of De Casteljau subdivision.

Step 4: Preserve Continuity

The subdivision naturally preserves $C^1$ continuity at the split point $S$ because the tangent vectors from both sides match. To ensure $G^1$ continuity across the entire path, verify that the last control point of the first new segment and the first control point of the second new segment are the same point (they are, by construction). If the original path had $C^2$ continuity at segment boundaries, check that the new control point arrangement does not break that property.

Worked Example

Consider a Bezier curve with control points $P_0 = (0, 0)$, $P_1 = (1, 2)$, $P_2 = (3, 2)$, $P_3 = (4, 0)$. We want to split at $t = 0.5$.

First level:

• $Q_0 = 0.5 \cdot (0,0) + 0.5 \cdot (1,2) = (0.5, 1)$
• $Q_1 = 0.5 \cdot (1,2) + 0.5 \cdot (3,2) = (2, 2)$
• $Q_2 = 0.5 \cdot (3,2) + 0.5 \cdot (4,0) = (3.5, 1)$

Second level:

• $R_0 = 0.5 \cdot (0.5, 1) + 0.5 \cdot (2, 2) = (1.25, 1.5)$
• $R_1 = 0.5 \cdot (2, 2) + 0.5 \cdot (3.5, 1) = (2.75, 1.5)$

Third level:

• $S = 0.5 \cdot (1.25, 1.5) + 0.5 \cdot (2.75, 1.5) = (2, 1.5)$

The two resulting segments are:

• Segment 1: $[(0, 0),\; (0.5, 1),\; (1.25, 1.5),\; (2, 1.5)]$
• Segment 2: $[(2, 1.5),\; (2.75, 1.5),\; (3.5, 1),\; (4, 0)]$

Together, these two curves reproduce the original curve exactly.

Summary

Common Pitfalls

• Choosing $t = 0$ or $t = 1$ produces a degenerate split where one segment has zero length. Guard against this in code.
• When inserting into a multi-segment path, make sure to remap the global parameter to the local segment parameter before applying De Casteljau.
• Floating-point precision can drift over many successive subdivisions. If you need high accuracy after many splits, consider using rational arithmetic or interval methods.

Understanding this technique is crucial for anyone working in computer graphics or geometric modeling. Through precise subdivision, seamless animations, detailed curve editing, and robust collision detection all become possible.