Codex @codex  0

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]

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.

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 solid body transform is a rigid transformation: it preserves distances within the object. In three-dimensional coordinates it has the form $T(x)=Rx+b$, with translation $b\in {\mathbb{R}}^3$ and an orthogonal matrix $R$. For a proper physical rotation, the coefficient constraints areEquivalently the columns of $R$ are an orthonormal basis with positive orientation. A reflection also preserves distance but has $\det R=-1$ and is excluded when “solid-body motion” means a rotation and translation. There are three rotational and three translational degrees of freedom, not twelve independent matrix coefficients.

Computationally use the homogeneous coordinates representationThe last row is $(0,0,0,1)$; matrix multiplication composes transforms. Alternatively store a unit quaternion together with $b$, maintaining its unit norm. A transpose gives the rotational inverse: $T^{-1}(y)=R^T(y-b)$.

Write the cubic Bézier curve as $P(t)={\sum }_{i=0}^3{B}_i^3(t)p_i$, where $B_i^3(t)=\left(\genfrac{}{}{0ex}{}{3}{i}\right)(1-t{)}^{3-i}{t}^i$. The binomial theorem gives ${\sum }_i{B}_i^3(t)=1$. Transforming the controls producesThis proves pointwise equivariance, including the original parameter values; it is stronger than a statement that the two curves merely have the same shape.

Orthogonality was not used in the calculation. The identical proof applies to every affine map $T(x)=Ax+b$, including scales, shears and even singular affine maps. It applies to every representation $P(u)={\sum }_i{\varphi }_i(u)p_i$ with scalar, control-independent partition of unity basis functions: Bézier curves of every degree, B-splines, surfaces built on a tensor-product surface basis, triangular Bézier patches, and more general linear control-point representations. Positivity is not needed for affine equivariance of a geometric basis. For linear stationary subdivision matrices with row sums one, each refinement step commutes with the affine transformation; taking a convergent limit proves the corresponding assertion for subdivision curves and subdivision surfaces. Rules with geometry-dependent nonlinear weights require separate equivariance tests and are not covered automatically.

The affine class is the largest class that preserves every such Euclidean-control construction with unchanged basis weights, under the usual continuity assumption. In fact the degree-one case would forcefor all $x,y$ and $0\le t\le 1$. This segment identity, followed by continuity, forces $T$ to be affine. Nonlinear transforms such as perspective division generally fail it.

There is a further extension when the representation itself is enlarged: apply a projective transformation linearly to homogeneous controls $(w_i{p}_i,w_i)$, then dehomogenize the weighted sum. The transformed objects are rational Bézier curves or non-uniform rational B-splines, with transformed weights as well as transformed Euclidean controls. This works wherever the new denominator is nonzero. It does not assert projective invariance of ordinary polynomial Bézier curves with their old weights.

A parametric curve interrogation interface first supplies the parameter domain and the point $C(t)$. At regular parameters, it also supplies $C^{\prime }(t)$ and, when needed, higher derivatives. The unit tangent vector, speed and curvature are then obtained fromin three dimensions. The formulas require $C^{\prime }\ne 0$; a Frenet normal additionally requires nonzero curvature. A practical interface can restrict the curve to a parameter interval, provide endpoints, and give a certified bounding volume or a derivative-range bound. Arc length, closest-point and intersection queries are higher-level operations built from these elementary enquiries rather than consequences of point evaluation alone.

For a plane $n\cdot x=d$ with $n\ne 0$, defineThis reduces certified curve-plane intersection to scalar root isolation. A subdivision curve can expose the parametric enquiries by evaluating its limit at a parameter address: refine the corresponding piece until its certified positional enclosure reaches the requested accuracy, or use its exact local spline representation. Derivative evaluation similarly needs the derivative refinement rule and its error bound. A finite control vertex is not automatically a point of the limit curve.

One reliable algorithm is range-based isolation followed by safeguarded Newton iteration:

For a transverse root, the derivative is nonzero nearby, so sufficiently fine intervals have monotone $F$ and the sign bracket isolates it. Bisection provides a global error bound; near a simple root Newton iteration gives quadratic convergence. Good enclosures discard most of the curve before expensive limit evaluation, and the method does not require a specific subdivision mask.

The weaknesses are equally important. Near tangency $F^{\prime }$ is small and Newton steps are ill-conditioned; same-sign endpoints may conceal a tangent root or two crossings. An arc lying in the plane has infinitely many intersections and should be returned as an interval, not a point. Finite-precision evaluations require error enclosures before a sign is certified. For an arbitrary smooth point-evaluation oracle, no finite sampling scheme can certify all intersections: a smooth bump between sampled parameters can create extra crossings without changing any sampled values or derivatives. With finitely many isolated transverse intersections and convergent certified enclosures, the algorithm terminates to any prescribed tolerance. For tangencies it either uses stronger representation tests or reports unresolved possible-contact intervals, rather than silently omitting them.

A norm estimate controls the worst possible refined differences for every choice of the initial controls. Submultiplicativity turns a length-$p$ contraction into a bound for arbitrary long products, so it proves a certain number of continuous derivatives. Its absolute values can lose cancellations; failure of the estimate is inconclusive. It therefore gives a lower bound on smoothness.

Conversely, an observable eigenmode of a repeated local product exhibits a particular sequence of shrinking neighborhoods with inadequate decay. General-position controls have a nonzero coefficient in that mode, so greater derivative continuity is impossible. Special symmetric or polynomial data may suppress the bad mode; this is why the general-position qualification matters. The obstruction gives an upper bound on smoothness, while failure to find an obstruction proves nothing. A lower bound on spectral growth becomes an upper bound on smoothness because large surviving differences correspond to rough behavior.

For example, the binary Cardinal cubic B-spline subdivision mask has symbol $M(z)=(1+z{)}^4/8$, up to an irrelevant index shift. At derivative order $r=2$, the first-difference subdivision mask is $B_2=(1+z)/2$, whose maximum parity sum is $1/2$: the limit is at least $C^2$. At $r=3$, $B_3=1$, and the surviving difference mode does not decay. For generic controls the third derivative is piecewise constant with nonzero jumps, so the subdivision curve is not $C^3$. Here the lower and upper tests determine the exact integer continuity, but they need not coincide for an arbitrary subdivision mask. Stability, sum rules and borderline modes must be handled explicitly before interpreting any numerical estimate as a continuity level.

Fix the indexing conventionwhere the subdivision arity $a>1$ is an integer. A change of the initial control $P_0^0$ can influence only indices $i=j_1$ after one step, where $M_{j_1}\ne 0$. After $\ell$ steps the possible descendant indices areLet $j_{\min },j_{\max }$ be the smallest and largest active subdivision mask indices. Dividing by $a^{\ell }$ gives the enclosureTherefore the support of a stationary subdivision scheme, in initial control-grid units, is enclosed byFor the stated symmetric subdivision mask with active extremes $-w,w$, the width is $2w/(a-1)$. For a nonzero compactly supported basic limit function $\varphi$, this is an exact endpoint calculation: its refinement equation is $\varphi (x)={\sum }_j{M}_j\varphi (ax-j)$. If $\beta$ is its right support endpoint, only the largest active subdivision mask index can contribute sufficiently close to the rightmost point of this sum; all smaller indices have argument beyond $\beta$. Hence $\beta =(\beta +j_{\max })/a$, giving $\beta =j_{\max }/(a-1)$. The left endpoint follows in the same way. This argument also excludes cancellation at an extreme for signed subdivision masks. The support for initial control $P_k$ is translated by $k$. If the nominal subdivision mask was padded by zero coefficients, use its actual extremes; and a limiting subdivision curve has to exist before its support is meaningful. This calculation describes the entire possible influence region, rather than the width of a single refinement stencil on its finer grid.

Let the point light be at $L$. For a subdivision curve point $C(t)$, its projected shadow lies on the ray beyond the subdivision curve:The shadow is the first intersection of that ray with the receiving subdivision surface after the subdivision curve point. Thus solveand retain the smallest admissible $\lambda$. This is the defining equation for shadow tracing for a subdivision curve.

First organize the subdivision surface patches into a bounding volume hierarchy. For a restricted subdivision curve interval, rays through its enclosing volume define an enclosing ray cone from $L$; subdivision surface bounds that do not meet this cone can be rejected. Refine surviving subdivision curve intervals and subdivision surface patches. For a fixed $t$, isolate all possible ray intersections using those bounds, then correct each regular candidate with the Jacobian matrix for the Newton methodThe scalar triple product shows that $J$ is invertible exactly when $n\cdot (C(t)-L)\ne 0$. Enforce the patch domain and $\lambda >1$ throughout correction, and choose the smallest valid $\lambda$. Bounds or validated root isolation, rather than a fixed list of subdivision curve samples, are needed if every shadow component is to be found.

Once a regular intersection is known, follow it as $t$ changes. Differentiating $F=0$ gives a useful predictor:Take a small predictor step in $(u,v,\lambda )$ and apply a Newton method correction at the new subdivision curve parameter. Move through patch adjacency with its chart transition; shrink steps when derivatives or error estimates change rapidly. Subdivide further and test a geometric curve-to-chord bound to approximate the resulting shadow trace to a chosen tolerance.

Surface-boundary crossings terminate or clip a trace. If a ray has no admissible subdivision surface intersection, that subdivision curve parameter contributes no shadow on $S$. At grazing contact the Jacobian is singular, so use interval subdivision and root isolation to detect the event and seed any outgoing branches. If several intersections are possible, recheck which is first; facing the light locally is helpful but is not a proof of global uniqueness. Open-curve endpoints and closed-curve seams must also be accounted for. With a compact represented geometry, transversal intersections and validated subdivision bounds, this algorithm traces every visible component; a purely sampled implementation gives only a tolerance-dependent approximation and cannot certify arbitrary tiny missed components.

For a directional light, replace the ray by $C(t)+\lambda d$ for a fixed propagation vector $d$ and $\lambda >0$. The intersection equation becomes $S-C-\lambda d=0$, with Jacobian $[S_u,S_v,-d]$ and continuation right-hand side $C^{\prime }(t)$. The same enquiries and event handling apply.

A subdivision curve should support subdivision curve interrogation rather than merely supply successively larger control polygons. Its interface should provide the parameter interval, orientation and open/closed status; endpoint and limit-point evaluation to a prescribed accuracy; and tangent vector or derivative evaluation where defined. It should be possible to split a parameter interval, commonly at its midpoint, into equivalent restricted curve definitions while retaining all neighboring controls needed by the refinement rule.

For geometric algorithms, request a certified bounding volume for each restricted curve, such as a convex hull or an axis-aligned bounding box, and the minimum and maximum of a plane's linear function over that bound. Request also a certified flatness bound: the maximum distance of the restricted limit curve from its endpoint chord, together with its spatial extent. These allow safe rejection, adaptive drawing and accuracy control. A positive, constant-reproducing subdivision mask often makes a control-point convex hull a valid bound. With negative mask coefficients this must be proved separately or replaced by a padded bound; it cannot simply be assumed.

Further useful enquiries include roots of a scalar function along the curve, closest-point searches, arc length, and inversion of an arc-length parametrization. They can be implemented through evaluation, differentiation, certified bounds and recursive subdivision. Evaluation, restriction, enclosure and error bounds are the essential primitives needed for reliable clipping and rendering; an unqualified control-polygon approximation is insufficient.

Orient the plane relative to the eye. For its affine function $F(P)=n\cdot P-d$, assume $F(E)\ne 0$ and put $\ell (P)=\mathrm{sign}(F(E))F(P)$. The desired closed half-space is $\ell \ge 0$. If the eye is on the plane, the notion of its side is undefined and a side convention must be supplied.

Apply recursive half-space clipping of a subdivision curve to each initial curve piece. Obtain a certified bounding volume $K$, and calculate $l={\min }_K\ell$, $h={\max }_K\ell$. For a control-point convex hull, these extrema occur at its vertices, so this test is inexpensive. If $h<0$, discard the piece. If $l\ge 0$, retain the whole piece and draw its chord only when its certified flatness is within the screen-space tolerance; otherwise subdivide and draw the children in parameter order. If $l<0\le h$, subdivide and repeat the classification.

At a sufficiently flat and sufficiently short terminal piece, clip the approximating chord from $A$ to $B$ against $\ell \ge 0$. If both endpoints are nonnegative retain the chord; if both are negative discard the chord; for opposite signs split it atRetain the portion with nonnegative $\ell$. Handle an endpoint exactly on the plane without dividing by zero, and retain a coplanar chord under the closed-half-space convention. The recursion yields an ordered polyline rather than connecting endpoints of disconnected retained pieces.

Crucially, do not reject an unresolved whole curve merely because its endpoints have negative signs: it can cross the plane twice and have a visible interior excursion. The preceding terminal chord rule is a rendering approximation at an explicitly chosen spatial tolerance. A flatness bound and a diameter bound make any missed leaf-sized excursion spatially small; they do not prove exact crossing topology, especially for a near-tangent contact or an unfavorable projection. Use the actual viewing projection to enforce a screen-space tolerance, with special handling near a perspective singularity.

If exact clipping intervals are required for a spline representation, isolate all roots of $\ell (C(t))$, split at them and classify each intervening interval. Bernstein basis coefficient bounds, derivative bounds and recursive subdivision can isolate roots on polynomial spans, including even-multiplicity tangencies. Treat identically coplanar spans separately. For a general subdivision curve, keep unresolved straddling pieces flagged or refine to the chosen tolerance instead of claiming that a finite endpoint-sign test is exact. Certified half-space rejection combined with adaptive subdivision is the recursive drawing algorithm; exact boundary topology needs additional root isolation.

Use the limit subdivision surface and limit subdivision curve, rather than treating their initial control meshes as the reflecting geometry. Build adaptive refinement hierarchies for both. Each surface cell supplies a limit-position evaluator, local tangent vectors and a normal vector; each curve interval supplies a limit-position evaluator and tangent. Regular regions may be evaluated as local splines, while extraordinary neighborhoods require the evaluation machinery of the specified subdivision rules. A piecewise smooth surface is handled patch by patch, with explicit boundary or crease joins.

A useful initial polygonal construction refines the surface to small triangles and the source curve to small line segments. For a candidate mirror triangle in a plane $n\cdot (X-X_0)=0$, reflect the eye across that plane:For a source edge $Y(t)=(1-t)Y_0+t{Y}_1$, a physical reflection point is the plane intersection of the line $E^{\ast }Y(t)$:Keep only $0\le t\le 1$, $0<\lambda <1$, points inside the mirror triangle, and eye/source points on the appropriate reflecting side. Unfolding the reflected path across the mirror proves the specular reflection condition. As $Y$ moves along a straight edge, $X$ lies on the intersection of the mirror plane with the plane through $E^{\ast },Y_0,Y_1$, so the retained locus is a straight segment, a point or the empty set. Plane and triangle clipping computes its endpoints. If these defining points are collinear, or a denominator vanishes, use the corresponding limiting geometric case rather than a generic plane formula. A bounding volume hierarchy accelerates candidate search where geometric bounds exclude pairs; refined facet segments provide seeds and approximate connectivity.

To obtain the reflection curve of the actual limits, correct these seeds. In a local surface chart write $S(u,v)$, and on a source interval write $C(t)$. SetThe exact limit reflection locus is $F=0$ together with the front-side conditions. For a two-sided mirror, orient $n$ locally so that $b\cdot n>0$ and require $a\cdot n>0$; for a one-sided mirror use its prescribed orientation and discard the wrong side. At grazing incidence this orientation condition ceases to be strict and the case needs separate handling. Unlike the eye-facing assumption in the parametric question, no global orientation condition is supplied here.

Apply a continuation method: at a rank-two root of $DF$, predict in a nullspace tangent direction and correct by the Newton method on a transverse section. Map corrected parameters to $S(u,v)$, crossing patch and curve-interval boundaries through their hierarchy adjacency. Trace all branches, recognizing closed components and endpoints. Supplement facet seeds by recursive searches of the surface-cell/source-interval product, with interval arithmetic or other certified enclosures of $F$; otherwise a small loop absent from the initial polygonal approximation could be missed. Split singular neighborhoods where the Jacobian matrix loses rank, and test the open source-to-mirror and mirror-to-eye segments for occlusion when selecting actually visible components.

Allocate a geometric error budget to limit evaluation, root correction and polygonal chords. For example, require combined position-evaluation and corrected-root error at most $ϵ/2$ and, on every regular arc, require the chord error bound $M(\Delta s{)}^2/8\le ϵ/2$. Use subdivision position and normal bounds for evaluations: a tiny position error alone is insufficient, since a wrong normal vector changes the reflected ray. Away from singularities an inverse transverse Jacobian matrix bound converts reflection residual into parameter error and a bound on $DS$ converts this to space error. Refine until these bounds hold, or use validated enclosures of entire arcs and their distances to the chords.

Near a caustic the inverse bound can become large, so the hierarchy must refine more strongly or isolate the singular branch geometry. Mesh flatness alone does not certify a reflection tolerance. With regular convergent evaluators and finite resolvable components, the resulting ordered vertices and chords satisfyThe problem supplies no particular subdivision rules or smoothness guarantees, so this construction specifies what their evaluators and bounds must provide; an arbitrary nonsmooth or degenerate limit need not have an ordinary finite reflection curve. Refine for seeds, enforce reflection on the actual limit geometry, then refine the traced arcs to the required spatial tolerance.

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.