Computer aided geometric design

Computer aided geometric design studies computational representations, evaluation and manipulation of curves and regular surfaces, especially using splines and subdivision surfaces.

// Target: geometry-and-topology.bigb

A boundary representation specifies a solid through its oriented bounding faces and their edge and vertex of a polyhedron incidence. Supporting planes and coordinates supply geometry; face loops and adjacency supply topology. A valid closed manifold model requires compatible orientation, two incident faces per edge and a single local fan at each vertex of a polyhedron, together with an embedded boundary.

A mesh representation with two oppositely directed records per ordinary edge. Each record stores its origin vertex of a polyhedron, incident face, next face-boundary record and opposite record; previous records are often cached. The opposite record's origin gives the destination. This usage differs from a dangling half-edge of a graph.

An edge record stores endpoint vertices of a polyhedron, its two incident faces, and predecessor and successor edges for each face. These four boundary-neighbour references are the wings. Face and vertex of a polyhedron records also carry entry references for traversal. Local edits must preserve all reciprocal incidence references and orientations.

Joined pieces have order-$k$ parametric continuity when their positions and one-sided derivatives through order $k$ agree in the actual common parameter. Changing parameter-interval lengths changes the required derivative scale by the chain rule. For regular curves, parametric continuity implies the corresponding geometric continuity.

Joined regular parametric curves have order-$k$ geometric continuity when their local images admit compatible orientation-preserving regular parameter choices with matching derivatives through order $k$. At order one the nonzero one-sided tangent vectors must be positive scalar multiples. At order two the oriented bending must also match: equality of unsigned curvature alone does not suffice if the curves bend to opposite sides.

A fillet rounds a corner or edge by inserting a tangent transition. In a planar circular construction, intersect normal lines through the prescribed tangent points to find the circle centre. Choosing the retained side and local clipping region is part of the design: intersecting the entire original solid with the fillet disk generally removes unrelated geometry. Tangent joining need not make curvature continuous.

Constructive solid geometry describes a solid by combining primitive regions with Boolean set union, set intersection and difference. With primitive defining functions nonpositive inside, minimum implements union and maximum implements intersection. These formulas encode membership rather than signed distance functions. Solid modellers often regularize Boolean operations to remove isolated lower-dimensional remnants.

A rooted tree whose leaves describe primitive regions and whose internal nodes describe Boolean operations. A half-space leaf can hold an implicit equation and an inside-sign convention. Evaluate membership from the leaves toward the root; interval arithmetic can propagate conservative inside/outside bounds over a box instead of a single point.

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.

For overlapping solid bodies, the penetration depth is the smallest translation needed to remove interior overlap, with orientation fixed. It is distance from the origin to the complement of the translational collision region. Define signed separation as positive ordinary separation for disjoint bodies, zero for contact, and $-\delta$ for interior overlap. Translation-space branch and bound can bracket it using certified intersection/containment queries. This convention handles crossing and complete containment; merely negating unsigned boundary distance does not.

A basis with the displayed identities reproduces affine functions from their values at the precision sites ${\xi }_j$. For two such bases, the tensor-product precision sites are $({\xi }_j,{\eta }_k)$: summation independently recovers $u$ and $v$. Affine images of this site grid therefore produce exact planar parameterizations, independent of the chosen control-grid representation.

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 mesh connecting a surface's control points according to the representation's indexing topology. A tensor-product surface basis gives a rectangular index grid and quadrilateral cells, even when its points in space are neither planar nor rectangular. The drawn mesh is a geometric skeleton, not generally the exact limit surface or an enclosing solid. Positive partition of unity coefficients give a convex hull bound on the relevant controls.

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.

If $g$ is gravitational acceleration and $a$ is the camera's acceleration, the locally felt upward vector is $U=a-g$. Choose the travel unit vector $X$, set $W=U-(U\cdot X)X$, and, when $W\ne 0$, take $Z=W/\Vert W\Vert$ and $Y=Z\times X$. These form an orthonormal basis with $U$ in the $XZ$ plane. If $U$ is parallel to $X$, the condition leaves the roll angle free even when $U\ne 0$; transport a previous transverse axis or choose a well-conditioned coordinate axis and project it into $X^{\perp }$.

A subdivision curve is the limit of repeated refinement of a control polygon, when that limit exists. Each finite stage still consists of line segments; the limiting curve can have a continuous derivative. Linear stationary rules, which use the same fixed weighted averages at every stage, can be studied through their subdivision masks and often represent splines. An interpolation rule retains the old control points, as in binary linear interpolatory subdivision; an approximating rule such as Chaikin subdivision generally moves away from them. Increasing the number of control points alone does not prove convergence or smoothness.

// Target: analysis.bigb

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.

The functional precision set of a subdivision scheme consists of functions exactly reproduced by refining their uniform samples with the scheme's consistent parameter placement. Polynomial precision usually specifies the reproduced polynomial space. If exactness is required for every grid spacing and shift, the binary midpoint-interpolation scheme has precision exactly the affine functions. At one fixed grid, its entire reconstruction range is the space of continuous piecewise linear functions on that grid; this larger range should not be confused with polynomial precision or arbitrary-grid reproduction.

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]

This centered quadratic cardinal B-spline weights each original control ordinate at its uniformly spaced abscissa. Its translates sum to one. It and its first derivative match at half-integer knots, while the second derivative can jump. The limit graph is ${\sum }_i{y}_i\beta ((x-x_i)/h)$; one ordinate influences exactly three original intervals. Refinement of a quadratic adds $a{h}^2/4$ in the limit, yielding this basis by extending each three-point neighborhood quadratically.

For uniformly spaced abscissae, quarter and three-quarter averages applied to constant or affine samples leave the same polynomial. For $P(x)=a{x}^2+bx+c$ on spacing $h$, both new subgrids lie on $P(x)+3a{h}^2/16$. For degree $n\ge 3$, their candidate polynomial formulas differ with leading term $(h^3/32)P^{\prime \prime \prime }$, which has a nonzero highest-degree coefficient. Thus preservation of polynomial degree for arbitrary sufficiently long data sequences holds exactly for degrees zero, one and two, despite quadratic values changing.

Under $P_i^{\ell +1}={\sum }_j{M}_{i-aj}{P}_j^{\ell }$, the descendants of control index zero lie at $a^{\ell -1}{j}_1+\cdots +j_{\ell }$, where each $j_k$ is in the mask support. Dividing by the refined parameter scale $a^{\ell }$ gives a limiting influence enclosure with the displayed endpoints. For a mask supported on $[-w,w]$ its width is $2w/(a-1)$ when the endpoints are active and a nonzero compactly supported basic limit exists. To prove exactness, the largest active mask term is the only surviving term near the right endpoint of the refinement equation, forcing $\beta =(\beta +j_{\max })/a$; the analogous left-end argument completes the result. Mask padding should be removed, and a nonconvergent rule has no limit support.

A useful subdivision curve interface provides parameter ranges, endpoint and limit evaluation, derivatives, subdivision into equivalent restricted pieces, a certified bounding volume, and a certified error relative to a chord. Positive subdivision masks often give a convex hull bound. Masks with negative coefficients need a separate enclosing bound; their control-point hull need not enclose the limit curve.

At a regular differentiable interior nearest point of a parametric curve, the displacement from the query point is perpendicular to the tangent vector. A branch and bound search uses distances to certified enclosing bounding volumes as lower bounds, and evaluated limit points as upper bounds. Refine the most promising restricted pieces until the upper bound differs from the global lower bound by the chosen distance tolerance. Safeguarded Newton root-finding iteration accelerates local candidates, but endpoints, nonregular points, ties and other stationary branches must not be omitted.

For a point light at $L$, the shadow of a curve point is the first surface intersection on its ray beyond that point. Certified patch bounds and subdivision isolate intersections; regular hits are corrected with a three-variable Newton method solve. Differentiating the displayed equation gives $[S_u,S_v,-(C-L)](u^{\prime },v^{\prime },{\lambda }^{\prime }{)}^T=\lambda C^{\prime }$, a predictor for continuation along the shadow. Surface boundaries and grazing rays require clipping and reseeding; every visible component must be isolated, rather than assumed detectable from a fixed sample of the casting curve.

For an oriented plane function $\ell$, certified extrema over a bounding volume allow a subdivision curve piece to be rejected when $\max \ell <0$, or wholly retained when $\min \ell \ge 0$. Otherwise subdivide. At an explicitly chosen rendering tolerance, a sufficiently flat, sufficiently short piece can be replaced by its clipped chord. This is an approximation, not a proof of exact crossing topology. Exact treatment of tangent contacts and small excursions requires root isolation of $\ell (C(t))$ and splitting into sign-constant intervals, when the curve representation supports such isolation.

A subdivision surface is the limit of repeated mesh refinement and vertex averaging. Exact interrogation evaluates this limit and, where defined, its tangent vectors and normal vectors; a finite refined control mesh is generally only an approximation to the limit.

// Target: analysis.bigb

Lateral artifacts of a subdivision surface are unwanted variations along an intended straight extrusion: input cross-sections identical along a lattice direction acquire ripples in that direction under refinement. For a stationary arity-$m$ lattice rule $a_{i,j}$, extrusion along the first lattice coordinate is preserved exactly when ${\sum }_{i\equiv r(\mathrm{mod}m)}{a}_{i,j}$ is independent of the residue $r$ for every transverse offset $j$. Then summing along each row gives a single associated univariate subdivision mask. This direction-specific criterion does not promise invariance under every possible oblique extrusion.

If a triangular-lattice subdivision mask has the displayed residue-sum equality, refining data $p_{i,j}=q_j$ gives $p_{I,J}^{\prime }={\sum }_k{b}_{J-3k}{q}_k$, independent of $I$. If affine coordinates reproduce their parameter positions, a geometrically straight extrusion is preserved. Rotationally symmetric masks give the corresponding property in all three lattice-edge directions. A boundary curve compatible with this extrusion uses the collapsed mask $b$, not just the central row of the two-dimensional mask.

Mid-edge subdivision replaces each mesh edge by its midpoint, joins successive midpoints around every old face, and joins successive midpoints around every old vertex. For an interior manifold mesh, each new vertex has valence four. Each geometric update is a convex combination, so every refined control point remains in the convex hull of the original control mesh. The regular limit is associated with the quadratic four-direction box spline.

The descendant of a face with cyclic vertices $p_0,\dots ,p_{n-1}$ has vertices $p_i^{\prime }=(p_i+p_{i+1})/2$. Their arithmetic mean is unchanged. On the cyclic Fourier basis, a mode of frequency $j$ is multiplied by $(1+e^{2\pi ij/n})/2$. Every nonconstant mode has modulus less than one, so the descendant face shrinks to the original vertex centroid. This puts that centroid on the subdivision limit, without requiring the original face to be planar.

Interrogation of a subdivision limit needs patch/topology navigation, refinement, limit evaluation and derivatives where they exist, with certified bounds and geometric error estimates. On regular patches one may use the corresponding spline representation. At extraordinary subdivision vertices, local subdivision matrices determine limit positions and tangents under the scheme's smoothness conditions. A normal vector may exist even when second derivatives and Gaussian curvature do not; finite refined polygons are approximations rather than exact limit queries.

A robust intersection search applies branch and bound to pairs of subdivision surface patches. Certified bounding volumes reject disjoint pairs, and refinement reduces unresolved pairs. Limit evaluation, tangent data and controlled approximation bounds produce and correct local intersection arcs, then patch adjacency joins them. Bounds must enclose the limit, not merely the current mesh. Flat polygon intersections are approximations and can miss tiny components or tangencies unless the associated geometric and transversality conditions are verified.

A plane section of a subdivision surface is a zero set of the plane functional evaluated on the limit parametric surface. Certified patch bounding volumes reject sign-definite patches. On a regular transverse section, $\nabla g\ne 0$ and the parameter tangent is $(-g_v,g_u)$; predictor-corrector continuation method traces a branch after every component has been isolated. Closed loops, tangencies, coplanar patches and extraordinary-vertex neighborhoods require more than corner-sign tests. Degenerate sections can contain isolated points or two-dimensional portions rather than only regular curves.

For disjoint compact bodies, the minimum occurs on their boundaries. Patch bounding volumes give certified lower bounds and evaluated limit-point pairs give upper bounds. A branch and bound search refines promising patch pairs until the global bounds differ by the tolerance. Boundary distance alone cannot detect containment; touching, crossing or nested solid bodies have ordinary set distance zero. Negative overlap values require an additional convention such as translational penetration depth.

An extraordinary subdivision vertex has a valence different from that of the regular refinement lattice. Regular box spline calculations do not alone establish smoothness at this vertex. The finite local subdivision matrix, its eigenvalues, and the associated characteristic map of a subdivision surface determine convergence and tangent behavior.

The characteristic map of a subdivision surface is the planar limit map obtained from the two independent tangent eigenvectors of its local subdivision matrix. In the usual stationary setting, a simple constant eigenvalue one, a semisimple double subdominant eigenvalue $0<\lambda <1$, strictly smaller other eigenvalues, and a regular injective characteristic map establish the standard $C^1$ tangent-plane behavior for nondegenerate data. The eigenvalue inequalities alone do not exclude a folded or singular characteristic map. For an alternating scheme these tests must use a full period of refinement.

A regular quincunx subdivision step replaces a square lattice by the union of its old vertices and face centres. In lattice indices one may useThus two steps give ordinary binary refinement. If $A(z,w)$ is the one-step subdivision mask symbol, the two-step symbol is $A(z,w)A(zw,z/w)$. The two lattice parity classes separately determine the old-vertex and face-vertex stencils; their coefficient sums must each be one to reproduce constants.

On a regular triangular grid, Loop subdivision retains an old vertex with weight $10/16$ and adds its six neighbors with weight $1/16$ each. A new edge vertex has weights $3/8$ on the endpoints and $1/8$ on the two opposite vertices. Extraordinary vertices require valence-dependent rules.

// Target: analysis.bigb

For the three unit-grid edge vectors $v_1,v_2,v_3$ and a multivariate polynomial $f$ of total degree at most three, sampled regular-grid Loop subdivision generates the graph of $f+\frac{1}{12}{\sum }_{r=1}^3(v_r\cdot \nabla {)}^{2}f$. Thus affine polynomials are reproduced exactly and all polynomials through degree three retain their degree. Fourth-degree data constant along one edge direction reduce to a Cardinal cubic B-spline, whose limit need not be a polynomial.

On an infinite regular triangular grid, height data constant along one edge direction remain constant along that direction under Loop subdivision. Across rows the induced rule is $g_{2j}^{\prime }=(g_{j-1}+6g_j+g_{j+1})/8$, $g_{2j+1}^{\prime }=(g_j+g_{j+1})/2$, the centered Cardinal cubic B-spline rule.

// Target: analysis.bigb

A stationary binary subdivision mask $a$ specifies a refinement operator $q_j={\sum }_i{a}_{j-2i}{p}_i$. Indices may be vectors for a surface. Coefficients restricted to a parity class give the stencil for one type of refined vertex.

// Target: analysis.bigb

For a stationary univariate refinement $S_{ij}=a_{i-mj}$, the subdivision mask width counts fine-grid positions from the first to the last active entry in a column, including any internal zeros. Consecutive columns are translates by $m$ rows, the subdivision arity. The number of old control points used by a particular new point is instead the size of its row stencil; it need not equal the mask width. A span convention counts $w-1$ fine intervals, so numerical width claims should specify the convention.

The subdivision arity is the integer factor $a>1$ by which a stationary refinement shrinks parameter-grid intervals: control index $i$ has coordinate $i/a^{\ell }$ after $\ell$ levels. It is distinct from the mask width and from the number of neighbors in a stencil.

For backward differences $\Delta P_i=P_i-P_{i-1}$, a scalar stationary arity-$a$ subdivision mask has symbol $M(z)={\sum }_i{M}_i{z}^i$. The identity $(1-z)M(z)=B(z)(1-z^a)$ gives the displayed intertwining whenever the quotient is a finite Laurent polynomial. Iterating supplies higher-difference masks. The coefficients $a^{r\ell }{\Delta }^r{P}_i^{\ell }$ are candidate $r$th-derivative controls. A convergent derivative scheme, proved by contraction of its first differences, establishes corresponding smoothness of the original limit under the standard consistent parameterization.

Finite local subdivision matrices for the scaled difference scheme track derivative variations in nested parameter intervals. A product-norm bound below one proves uniform contraction for every interval and therefore gives a lower bound on derivative continuity. A product eigenvalue of modulus at least one is an obstruction when its mode is reachable from the data and visible in the limit: generic data excite it, so the corresponding derivative differences fail to vanish. Harmless polynomial or unobservable modes must be removed before applying such an upper bound. Borderline smoothness needs direct analysis, not rounding a numerical exponent. Stability and convergence of the underlying scheme must be checked rather than inferred from mask width.

A local subdivision matrix maps the control points in a refinement-invariant neighborhood to the refined neighborhood. Row sums one express constant reproduction. Its constant eigenvector has eigenvalue one; remaining eigenvalues govern decay of shape modes. Near an extraordinary subdivision vertex, tangent modes and a characteristic map of a subdivision surface are needed to test geometric smoothness, beyond simple convergence.

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

A weighted quadratic Bézier curve with positive middle weight $w$ retains endpoint interpolation and endpoint tangent directions while changing the bulge. For a circular arc of angle $\theta$ less than $180^{\circ }$, choose endpoints on the circle, their tangent intersection as the middle control point, and $w=\cos (\theta /2)$. Unlike an ordinary nonconstant polynomial Bézier curve, this rational representation can describe a circular arc exactly.

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}$.

Two adjacent Bézier curves of degrees $n,m$ and interval lengths $h,k$ have a $C^1$ join precisely when their endpoint positions and their derivatives in the common parameter agree. Parallel endpoint polygon edges alone give tangent-direction agreement; their scaled vectors must be equal for parametric first-derivative continuity.

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 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.

A conservative enclosure test may retain disjoint objects as candidates, but must never reject a true set intersection. Increasing an enclosure can add candidates while preserving this implication.