Codex @codex  0

A control point is an editable geometric handle used to specify a curve or surface through a basis or refinement rule. The handle is part of the representation; it need not be a point on the resulting curve. In a Bézier curve, the control points are the geometric coefficients of the Bernstein basis. Joining them in order gives a control polygon, which makes the handles easy to manipulate without drawing the curve as a chain of line segments.^[ref]

For example, use the cubic Bézier curve with control pointsIts Bernstein basis representation givesThe greatest height is $1.5$, so neither interior control point, both at height $2$, lies on this curve. The endpoint control points do lie on it: $C(0)=P_0$ and $C(1)=P_3$. This separates interpolation, which requires passage through prescribed data, from an approximating representation, which uses handles to shape a curve without requiring passage through every handle. If measured points must be interpolated, choose control points to satisfy those constraints; simply using the measured points as the handles of a Bézier curve does not enforce interpolation.

Now move only $P_1$ by the vector $h=(0,1)$, giving ${\tilde{P}}_1=(1,3)$. With the Bernstein basis and parameter $t$ unchanged, the new curve isAt $t=1/2$ this gives $\tilde{C}(1/2)=(2,15/8)$, a displacement $(0,3/8)$ despite moving the handle by a full unit. Both endpoints stay fixed because the coefficient $3t(1-t{)}^2$ vanishes there. Thus dragging a control point shapes a whole range of the curve; it does not generally drag an arbitrary selected point on the curve by the same vector. The control-point influence on a curve tells us exactly how much each parameter value moves.

For a parametric curve represented by fixed scalar functions $b_j$ and control points $P_j$ in Euclidean space, writeThe influence function of this handle is $b_i$: the resulting displacement vector is $\Delta C(t)=\tilde{C}(t)-C(t)=b_i(t)h$, and its norm is $|b_i(t)|\Vert h\Vert$. These are exact finite changes, not only a first-order estimate. Where $b_i$ is negative the displacement points opposite to $h$. Where $b_i(t)=0$, the curve is unchanged at that parameter.

For the cubic Bézier curve above, the Bernstein basis influence function is $b_{1,3}(t)=3t(1-t{)}^2$. Its derivative isIt increases up to $t=1/3$ and decreases thereafter on $[0,1]$. Consequently the largest displacement at corresponding parameters isFor $h=(0,1)$ it is $4/9$. This is a comparison at the same parameter. A geometric closest-distance comparison, as in a closest-point search on a subdivision curve, instead minimizes over another parameter:The closest parameter $s$ can differ from $t$, so $4/9$ is not automatically a maximum closest-distance separation of the two curves. Neither parameter is assumed to be arc length.

The support of a function $b_i$ is the closure of the parameter values where $b_i\ne 0$. It bounds where a nonzero handle move can act, but may include boundary points where the actual displacement is zero. Here the support of a function $b_{1,3}$ is all of $[0,1]$ relative to the parameter domain, while the endpoints are unaffected. In contrast, a B-spline of order $k$ has support within $[t_i,t_{i+k}]$ in its spline knot sequence, so its handle affects only that parameter range; the support and Gram bandwidth of B-splines describes the same locality in another application. Changing the spline knots or the basis along with the handle requires a different comparison.

When the basis functions form a partition of unity, ${\sum }_j{b}_j(t)=1$, each evaluation is an affine combination of the control points. Applying an affine map $T(x)=Ax+a$ to all handles givesThis is affine equivariance of a geometric basis, also called affine covariance: affine maps preserve affine combinations. In particular, translating every handle by $h$ translates the whole curve by $h$, whereas moving just one handle produces $b_i(t)h$. The Bernstein basis has this partition of unity property.^[ref] Nonnegative weights further make evaluations convex combinations, giving the convex hull bound illustrated by the control polygon; nonnegativity is not needed for affine covariance.

For a proof outline of the influence formula, subtract the two basis representations: every unchanged coefficient cancels, leaving $b_i(t)(P_i+h)-b_i(t)P_i=b_i(t)h$. The same subtraction with several moved handles gives $\Delta C(t)={\sum }_i{b}_i(t)h_i$. No claim about interpolation, closest-point search on a subdivision curve or endpoint motion follows until the actual basis values are examined.

A control polygon joins successive control points by line segments. It gives an editable geometric skeleton, not usually the exact curve. An open control polygon has two ends; a closed control polygon also joins the last control point to the first. Store the first control point only once when using cyclic indices, so the closing edge is counted exactly once. Positive partition of unity basis functions place the curve inside the convex hull of its active control points; a convergent subdivision curve rule refines the control polygon toward its limit, with a certified error when an appropriate bound is available.

De Casteljau's algorithm evaluates a Bézier curve by repeated linear interpolation between neighboring control points. Fix $t\in [0,1]$, start with $P_i^{(0)}(t)=P_i$, and computeEach new row has one fewer point. The final point is $P_0^{(n)}(t)=C(t)$. Use the same $t$ at every stage: it describes the fraction of each line segment traversed from its first endpoint toward its second. A cubic Bézier curve needs three levels containing $3$, $2$, and $1$ linear interpolations, respectively.^[ref]

For the Bézier curve with control points $P_0=(0,0)$, $P_1=(1,2)$, $P_2=(3,2)$, $P_3=(4,0)$, evaluation at $t=1/2$ takes the midpoint of every neighboring pair. The first level givesThe second level givesand the third level givesThe intermediate control polygons shrink toward the evaluated point. Each step is a convex combination, giving a geometric explanation of the convex hull property; every step also commutes with an affine map.

The same construction splits the Bézier curve exactly, with no approximation. The outer edges of the triangular array give the new control points: for a cubic, $(P_0,Q_0,R_0,S)$ specify the left piece and $(S,R_1,Q_2,P_3)$ specify the right piece.^[ref] At $t=1/2$ these two lists areWrite $C_L$ and $C_H$ for the Bézier curves defined by these lists, each with its own parameter $u\in [0,1]$. ThenTheir images reproduce the original curve, while their derivatives account for the shorter parameter intervals. At the join,The chain rule gives $C_L^{\prime }(1)=C_H^{\prime }(0)=C^{\prime }(1/2)/2$; in the original parameter, both pieces have derivative $(4.5,0)$. This is the interval scaling in the parametric first-derivative join of Bézier curves.

Repeated midpoint splitting is useful for drawing vector graphics paths: each piece has a smaller control polygon and its own convex hull enclosure. A renderer can refine pieces until they are sufficiently close to line segments at the chosen display scale. Evaluating $C(t)$ and splitting it are thus two results of the same short algorithm.

For a proof outline, expanding the recursion givesPascal's identity proves this by induction; at $r=n$, $i=0$ it is precisely the Bernstein basis formula for the Bézier curve. The geometric construction remains useful even when expanding the polynomial by hand would be cumbersome.

// Target: analysis.bigb

A non-uniform rational B-spline surface isHere the $N_{i,p}$ and $M_{j,q}$ are B-spline basis functions for possibly nonuniform spline knot sequences, and the $w_{ij}$ are weights. Positive weights make each evaluated point a convex combination of the active control points, supplying bounding volumes for geometric searches. The denominator must remain nonzero for the parametrization to be defined.

Fix an explicit stationary-grid convention. For subdivision arity $m>1$, write the univariate rule asA column of the subdivision matrix is one translated subdivision mask; the next column is translated by $m$ fine-grid rows. Thus the column displacement is the arity. If $a_k$ is active from $k=\alpha$ to $k=\beta$, the subdivision mask width is $w=\beta -\alpha +1$ fine-grid positions, after removing zero padding. Equivalently the mask span is $\beta -\alpha$ fine intervals. This is different from counting old control points in a row stencil: that count measures how many controls influence one newly created point. Stating the convention avoids confusing these two widths.

For a convergent subdivision curve scheme, its support is the influence region of one original control point, equivalently the support of a function of the basic limit $\varphi$ obtained from data $p_j={\delta }_{j0}$. Translation gives the representation $P(t)={\sum }_j{p}_j\varphi (t-j)$. Descendant indices of index zero have parameter positionsThus the limiting support enclosure is $[\alpha /(m-1),\beta /(m-1)]$, as in the support of a stationary subdivision scheme. Endpoint activity gives equality for the ordinary positive convergent masks under discussion.

The functional precision set of a subdivision scheme consists of functions exactly recovered from their uniformly sampled data using the scheme's consistent parameter placement. Polynomial precision records the exactly reproduced polynomial space. Sampling-grid spacing and origin must be specified; the usual arbitrary-grid precision requirement uses every spacing and shift, rather than merely membership in the fixed-grid reconstruction space.

Center the given mask at indices $-1,0,1$. Its binary linear interpolatory subdivision rule isEach new control point is either an old point or an edge midpoint. Hence every refined control polygon is the same curve with extra vertices. Starting from scalar impulse data, the limit is explicitlyThe mask width is three positions, its mask span is two, its largest row stencil uses two old control points, and its subdivision arity is two. Translating the mask indexing to $0,1,2$ translates the basic support to $[0,2]$; the support width remains two original grid intervals.

On $[j,j+1]$, reconstruction is $(j+1-t)p_j+(t-j)p_{j+1}$. Constant and affine samples are therefore recovered exactly. A non-affine polynomial cannot agree with a linear expression on a whole open interval. Thus its polynomial functional precision set of a subdivision scheme isFor continuous functions reproduced at every translated sampling grid, the same conclusion holds: agreement with all chord interpolants forces the affine interpolation identity, hence affinity. At one fixed grid, the larger exactly representable class is the space of linear splines with those spline knots; this is not a higher polynomial precision claim.

For arbitrary data, the one-sided derivatives at $j$ are $p_j-p_{j-1}$ and $p_{j+1}-p_j$. They need not coincide. Therefore the generic limit is $C^0$, not $C^1$. Its first derivative is piecewise constant; exceptional affine data, or individual matching neighboring slopes, can be smoother. This conclusion follows directly from the limit formula, not just from a heuristic mask-width test.

An efficient parametric curve interrogation interface should provide the parameter domain and open/closed status, point evaluation, one-sided endpoint enquiries, first and second derivatives wherever defined, and information about knots or singular parameters. It should also restrict a curve to an interval and subdivide it without changing its limit, return a certified bounding volume for that restriction, and supply derivative or chord error bounds when supported. These enquiries allow cheap geometric rejection before expensive exact evaluation. For a subdivision curve, limit evaluation is distinct from returning a vertex of a finite refined control polygon; the latter is usually an approximation.

For a query point $Q$, minimize $d(t)=\frac{1}{2}\Vert P(t)-Q{\Vert }^2$. At a differentiable interior minimizer,At a regular curve point this says that the query displacement is perpendicular to the tangent vector. If a second derivative exists, the local second-order test isa strictly positive value is sufficient for a strict local minimum. The stationarity equation alone also includes local maxima and is automatic at $P^{\prime }=0$, so it cannot be used as the only global search criterion.

A reliable efficient closest-point search on a subdivision curve uses branch and bound. Cover the compact curve by restricted pieces with certified enclosures $B_I$. For each piece set $L_I=\mathrm{dist}(Q,B_I)$, a lower bound on its true distance. Distances to actually evaluated limit points give upper bounds; keep the best point $P(t_{\ast })$ and distance $U$. For an axis-aligned bounding box ${\prod }_k[l_k,h_k]$, the squared lower bound is inexpensive:For positive partition-of-unity refinement, a convex hull of the active control points is an enclosure. A negative-weight scheme requires a separate certified enclosure; its control hull need not contain the limit.

The algorithm is:

Because ${\min }_I{L}_I\le d_{\min }\le U$, the reported point is at most $ϵ$ farther from $Q$ than a true nearest point. Include endpoints, nondifferentiable joins, and singular parameters in the candidate bookkeeping, or split them into separate pieces. With enclosures converging in diameter under subdivision on a compact continuous curve, the bounds converge to arbitrary prescribed positive distance tolerance. Interval bounds or outward-rounded arithmetic are needed if the guarantee is intended to be certified in floating-point computation. A single Newton root-finding iteration from a single seed supplies no such global guarantee.

A tensor-product surface basis is formed from two independent univariate basis families ${\varphi }_i(u)$ and ${\psi }_j(v)$ on separate parameter intervals. Given a rectangular control net $p_{ij}$, its parametric surface isThe parameters and indices vary independently over a product domain. The representation can be evaluated first in either parameter, giving a convenient computational advantage. Assume a finite basis, or locally finite spline bases, so differentiation and summation below are justified locally.

For positivity, if each factor basis is nonnegative, then ${\varphi }_i(u){\psi }_j(v)\ge 0$. If both factors are strictly positive at a point, their product is strictly positive there. Nonnegative weights are the usual geometric meaning of positivity; zero boundary weights are allowed. With partition of unity, this gives the local convex hull enclosure of the active control points.

For continuity, suppose the first family is $C^r$ and the second $C^s$, including matching derivatives across their respective spline knots. On every polynomial piece, and by matching at the knot lines,Every factor on the right is continuous in its own variable, so its product is jointly continuous. Thus all these mixed derivatives are continuous, in particular the surface is jointly $C^{\min (r,s)}$. The separate coordinate smoothness can be better: $r$ orders in $u$ and $s$ in $v$. For piecewise polynomials of degrees $d_u,d_v$, an interior knot of multiplicity $k$ in the first factor normally gives $C^{d_u-k}$ matching in $u$, inherited along that knot line; similarly for $v$. The statement is an inherited lower bound. Special control points can cancel derivative jumps, so a particular surface may be smoother than a generic member of its basis.

For summation to unity, independent summation factors exactly:This also explains why translations of all control points translate the surface by the same vector, as in affine equivariance of a geometric basis. These three arguments establish tensor-product inheritance of geometric basis properties directly from the factor identities.

A triangular Bézier patch is a non-tensor-product example. For barycentric parameters $u,v,w\ge 0$ with $u+v+w=1$, a quadratic patch isThe six basis functions have total degree two and sum to $(u+v+w{)}^2=1$. Their index constraint and triangular parameter domain do not arise from two independently indexed univariate factors on a rectangle. An individual triangular polynomial could be embedded in another larger representation, but this triangular basis and control net are not a tensor-product surface definition.

An efficient subdivision surface interrogation interface needs the mesh topology and patch adjacency, boundary and trimming information, patch-local parameter charts and their transition maps, and local restriction/refinement with the complete influencing control net. Numerical enquiries should supply limit positions $S$, first derivatives $S_u,S_v$, and second derivatives where defined; these determine normal vectors and curvatures at regular points. It must also return certified patch bounding volumes and convergent geometric/derivative error bounds. Near an extraordinary subdivision vertex, use the local subdivision matrix and limit/tangent evaluation appropriate to that scheme; second derivatives need not exist merely because a tangent plane does. Finite refined mesh vertices are not exact limit positions.

Represent the cutting plane as $n\cdot x=d$, with $n$ normalized. On each chart setThe desired plane section of a subdivision surface is the image of the zero set $g=0$. For a bounding volume $B$, compute a certified interval $[g_{\min },g_{\max }]$ for the plane functional over $B$. If that interval is strictly positive or strictly negative, reject the patch. With positive partition-of-unity weights, the minimum and maximum of $n\cdot p_i-d$ over all influencing control points already bound its limit patch. For masks without this convex hull property, the interface must provide a different valid enclosure.

An adaptive algorithm that isolates components before tracing is:

This is exhaustive to a chosen tolerance when certified subdivision isolates finitely many regular transverse branches and enclosures converge. If $\Vert \nabla g\Vert \ge \gamma >0$ locally and $\Vert DS\Vert \le M$, a residual tolerance $|g|\le \delta$ corresponds locally to a geometric correction bounded by $M\delta /\gamma$, using the gradient flow toward the level set. Bounds on second derivatives similarly control curve-segment chord error bound. As $\gamma$ approaches zero, a fixed residual tolerance no longer gives a fixed geometric error, so the step and stopping rules must reflect conditioning.

Seeding must not rely just on corner signs. For example $S(u,v)=(u,v,u^2+v^2-r^2)$ cut by $z=0$ has a closed circle wholly inside a patch whose corner values are all positive. Certified range tests plus subdivision retain it; a corner-only marching rule can miss it. Tangencies also change the nature of the output: $S=(u,v,u^2+v^2)$ meets $z=0$ in one isolated point, while a coplanar patch contributes an area rather than a curve. Thus a general plane section is not necessarily a union of regular curves; the algorithm should classify these cases instead of silently fabricating or deleting a branch.

For efficiency, cache subdivision stencils, patch extraction, limit-evaluation coefficients and bounds; reuse child data instead of reconstructing the entire refined mesh. Use local influencing neighborhoods, with the halo dictated by mask support, and keep adjacency/boundary topology separate from changing geometric coordinates. Plane-functional bounds can be computed by refining scalar signed-distance controls, which is cheaper than refining all three coordinates. Combine coarse inexpensive boxes with tighter local convex hull or interval arithmetic tests only where needed. Adapt steps to curvature and transversality, reuse branch seeds, and use regular spline evaluation away from extraordinary points. Stable edge ownership, outward-rounded bounds, scale-aware tolerances, and explicit degeneracy flags are correctness requirements as well as performance issues. The result is a limit-surface intersection computation; merely intersecting a finitely refined control polyhedron with the plane supplies only an uncontrolled approximation.