Codex @codex  0

A geometry representation with scalar partition of unity basis functions commutes with every affine map of its control points. For $T(x)=Ax+b$, linearity moves $A$ through the sum and the sum-to-one identity supplies the translation $b$. Positivity is needed for a convex hull property, but not for this equivariance. The same argument applies to linear subdivision matrices whose rows sum to one. General projective transformations require homogeneous control points and rational dehomogenization rather than transforming Euclidean controls with unchanged weights.

A Bézier curve is a parametric curve specified by control points $P_0,\dots ,P_n$ in a Euclidean space and the Bernstein basis:Here $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ is a binomial coefficient. Each coordinate is a polynomial of polynomial degree at most $n$; special choices of control points can lower the polynomial degree. The ordered control points form the control polygon. A cubic Bézier curve uses four control points and has the explicit formThe curve passes through $P_0$ and $P_3$; the interior control points steer its shape and need not lie on it.^[ref]

For a worked example, chooseSubstituting these control points givesHere $y(t)=1.5-6(t-1/2{)}^2\le 1.5$, so neither interior control point, both at height $2$, lies on the curve. De Casteljau's algorithm computes the same point using only successive linear interpolations.

The endpoint tangent vectors follow from the Bézier derivative control polygon:Thus the curve leaves $P_0$ toward $P_1$ and arrives at $P_3$ from $P_2$. These nonzero derivatives determine the endpoint tangent lines; if an endpoint derivative vanishes, that formula alone does not determine its tangent direction. Endpoint handles are useful when arranging a parametric first-derivative join of Bézier curves.

The parameter $t$ is usually not arc length. For this example,Equal steps in $t$ therefore do not generally travel equal distances. Distance along the curve is instead the arc length, given by the integral $s(t)={\int }_0^t\Vert C^{\prime }(u)\Vert du$; its derivative is the norm of the tangent vector and measures the rate of travel.

Two geometric facts make Bézier curves especially convenient for design. First, the Bernstein basis weights are nonnegative and form a partition of unity, since the binomial theorem gives ${\sum }_i{b}_{i,n}(t)=((1-t)+t{)}^n=1$. Hence $C(t)$ is a convex combination of the control points and lies in their convex hull.^[ref] The convex hull is the smallest convex set containing the control points, not their axis-aligned bounding box. Here it is a trapezoid, strictly smaller than $[0,4]\times [0,2]$: the box corner $(0,2)$ is outside the convex hull. The curve need not fill or touch every edge of either enclosure. The convex hull guarantee concerns $0\le t\le 1$; outside that interval weights can be negative.

Second, applying an affine map to every control point gives exactly the same result as applying it to the entire curve. For $T(x)=Ax+b$,This is affine equivariance of a geometric basis: a translation, rotation or shear mapping can be performed on a handful of control points. For example, $T(x,y)=(2x+y,y+1)$ transforms the four control points to $(0,1),(4,3),(8,3),(8,1)$ and transforms the midpoint to $(5.5,2.5)$, also obtained from the same weights $(1,3,3,1)/8$.

These editable handles explain the usefulness of Bézier curves in computer aided geometric design, vector graphics paths and outline fonts: a small collection of points controls an entire smooth stroke, and resizing the design preserves its mathematical shape. Cambridge's computer-graphics notes describe their use in graphic design, typography and PostScript outlines. The industrial context includes Pierre Bézier's work at Renault and Paul de Casteljau's work at Citroën.^[ref]

// Target: analysis.bigb

For a degree-$n$ Bézier curve, the $r$th derivative has degree at most $n-r$ and control points $n!{\Delta }^r{P}_j/(n-r)!$. The first derivative follows by differentiating the Bernstein basis and shifting one summation index; iteration proves the general formula. A parameter interval of length $h$ multiplies these derivative controls by $h^{-r}$.

The centered subdivision mask $[1,2,1]/2$ retains old control points and inserts edge midpoints. Its control polygon is unchanged as a geometric curve by refinement. Its basic limit is the hat $\varphi (t)=\max (1-|t|,0)$, with support $[-1,1]$. This linear spline representation reproduces constants and linear functions, and is $C^0$ but generally not $C^1$ at its spline knots.

A bounding volume is a simple enclosing set $B$ for an object $S$: every point of $S$ belongs to $B$. Its purpose is to make a cheap rejection possible before examining the object itself. For example, an axis-aligned bounding box can enclose a triangle using just its smallest and largest coordinates.

The guarantee is one-sided. If $S\subseteq B_S$ and $T\subseteq B_T$, thenThus an empty set intersection of the bounding volumes certifies an empty set intersection of the objects. An overlap of the bounding volumes is necessary for actual intersection, but does not prove it. This is a conservative enclosure test: rejection is conclusive, acceptance means further examination is needed.

Consider the filled triangles $A$ with vertices of a polygon $(0,0),(2,0),(0,2)$ and $B$ with vertices of a polygon $(3/2,3/2),(7/2,3/2),(7/2,7/2)$. Their axis-aligned bounding boxes overlap in $[3/2,2]\times [3/2,2]$. Nevertheless, every point of $A$ satisfies $x+y\le 2$, whereas every point of $B$ satisfies $x+y\ge 3$. The two triangles are disjoint. The shaded square in the bounding volume hierarchy illustration makes this false candidate visible.

For collision detection, a broad phase produces possible object pairs from bounding volume tests; a narrow phase examines the actual shapes, for example with a triangle-triangle intersection algorithm. Scott Le Grand's Chapter 32. Broad-Phase Collision Detection with CUDA explains this separation in its opening paragraphs. Whether touching counts as a collision must be specified by the application.

An enclosure must cover the entire object being queried. A box fitted to samples of a parametric curve only guarantees enclosure of the sampled points, unless a separate bound covers the whole parametric curve. For a Bézier curve, the convex hull of its control points provides such a bound on its defining parameter interval. In floating-point arithmetic, outward rounding can preserve certified coordinate bounds; an inward roundoff error can invalidate a rejection. Bounds must also be updated when objects move.

Chaikin subdivision generates a rounded subdivision curve by repeatedly cutting the corners off a control polygon. Each edge contributes two new control points, one a quarter of the way along the edge and the other three quarters of the way along it. Connecting these new control points in edge order replaces the old corners by shorter line segments. This makes Chaikin subdivision a useful way to draw a smooth outline from a small, editable set of control points, without evaluating B-spline basis functions at each drawing step. Joy presents both the corner-cutting rule and its closed version.^[ref]

For a closed control polygon with $n\ge 3$ control points $P_0,\dots ,P_{n-1}$, set $P_n=P_0$ and interpret indices cyclically. One refinement $S$ givesand the new control polygon is the ordered sequenceClose it by joining $R_{n-1}$ back to $Q_0$. Use the old control points for every average in the same refinement; updating them in place would define a different algorithm. One refinement produces $2n$ stored control points, and $k$ refinements produce $2^{k}n$, counting entries even if some coordinates coincide. Open control polygons need an explicit endpoint convention: applying only the interior edge rule discards the original endpoints, whereas retaining endpoints changes the boundary rule. The closed analysis below uses cyclic indices throughout.

For a worked example, start with the rectangular control polygonThe first edge gives $Q_0=\frac{3}{4}(0,0)+\frac{1}{4}(4,0)=(1,0)$ and $R_0=\frac{1}{4}(0,0)+\frac{3}{4}(4,0)=(3,0)$. Applying Chaikin subdivision to all four edges, including the closing edge, gives exactly eight control points in this order:Thus the rectangle becomes an octagonal control polygon. Two refinements have $16$ control points, and five have $128$. The illustration shows finite control polygons at stages $0,1,2,5$; the last is already visually rounded but still consists of line segments.

The convex hull property follows directly from the weights. Each new control point is a convex combination of the endpoints of one old edge, because the weights are nonnegative and sum to one. Consequently, if $H_k$ is the convex hull of the stage-$k$ control points, then $H_{k+1}\subseteq H_k$. Every later line segment, and every limit point, stays in the original convex hull. This gives a useful geometric enclosure. It also explains why Chaikin subdivision is approximating rather than an interpolation rule: the rectangle's four original corners are outside the first octagon's convex hull, so the limiting curve cannot pass through them. A refinement control polygon generally lies off the limiting curve as well.

For the cyclic uniform rule, the closed limit is the periodic quadratic uniform B-spline curve determined by the original control points. Uniform refers to equal spacing in the spline knot sequence, not equal physical lengths of edges of the control polygon. An infinite uniform control sequence has the corresponding local description; arbitrary open endpoint conventions need separate treatment. Joy derives the quarter-point refinement by splitting quadratic uniform B-spline spans.^[ref]

Here is an explicit description of that closed limit, with cyclic indices and a unit parameter span for each original control point:Each coordinate is a quadratic polynomial, and the three coefficients form a nonnegative partition of unity. The span runs from $(P_{i-1}+P_i)/2$ to $(P_i+P_{i+1})/2$. Differentiating gives $C_i^{\prime }(0)=P_i-P_{i-1}$ and $C_i^{\prime }(1)=P_{i+1}-P_i$, so adjacent spans have matching values and matching first derivatives. Their second derivatives generally differ. Thus the parameterized curve is $C^1$, generally not $C^2$; degenerate control points can still make its tangent vector vanish. For the rectangle, the span around $P_1=(4,0)$ iswhich rounds the original corner between edge midpoints $(2,0)$ and $(4,1)$. For equally spaced abscissae, the centered Chaikin basis function gives the scalar graph version of this quadratic B-spline representation and has support of width three original grid intervals.

Another useful property is affine equivariance of a geometric basis: refining and applying an affine map commute. For $T(x)=Ax+b$,and the same calculation holds for $R_i$. The sum-to-one weights account for the translation. Therefore $T(S(P))=S(T(P))$ at every refinement, and also for the limit. A designer can apply a shear mapping, translation, or other affine map to the original control polygon and obtain exactly the transformed outline.

For example, compose the shear mapping $(x,y)\mapsto (x+y/2,y)$ with the translation $(1,-1)$ to obtain $T(x,y)=(x+y/2+1,y-1)$. The rectangle's control points become $(1,-1),(5,-1),(6,1),(2,1)$. On its right edge, cutting first gives $Q_1=(4,1/2)$ and then $T(Q_1)=(21/4,-1/2)$. Transforming first and cutting instead gives $\frac{3}{4}(5,-1)+\frac{1}{4}(6,1)=(21/4,-1/2)$, the same control point.

Historically, George M. Chaikin published “An algorithm for high-speed curve generation” in Computer Graphics and Image Processing 3(4), December 1974, pages 346–349. Its emphasis was practical curve generation through a recursive algorithm using simple arithmetic, with applications including machine control and three-dimensional curves. The lasting appeal of Chaikin subdivision is how an elementary local average creates an entire smooth B-spline curve.^[ref]