The transverse row sequence in the extrusion invariance of Loop subdivision obeys
In the convention , the centered univariate subdivision mask is
The even coefficients sum to one and the odd coefficients sum to one; the whole binary mask sums to two. Its generating expression is , identifying the Cardinal cubic B-spline refinement rule. Its limit is for the centered unit-grid cubic basis . The curve across rows is this cubic B-spline; extrusion generates the whole limit surface. The along-extrusion direction itself has constant height, so its profile is a straight line rather than an additional nonconstant cubic curve.
Choose one grid-edge vector as the extrusion direction and an independent edge vector . Label grid points , so extruded height data have , independent of . The Loop subdivision stencils are affine-exact in the coordinates, so the refined horizontal grid has spacing one-half and the same row structure.
At an old vertex, two neighbors lie in its own row, two in the row above and two in the row below. Its refined height is therefore
A new vertex on an edge parallel to has both endpoints in row and its opposite vertices in rows , giving exactly the same value . A new vertex on either of the other edge directions has endpoints in rows ; its two opposite vertices are also one in each of these rows. Its height is
Every refined vertex in a given row consequently has the same height. Induction proves this at every refinement level. The piecewise planar interpolating mesh is also constant along between rows, since adjacent rows have constant heights and form parallel straight lines. Taking its convergent limit preserves this invariance. Thus
where the points lie in the domain. The limit subdivision surface is an extrusion of the univariate limit curve. This is a statement about functional data on the regular grid, not about an arbitrary spatial mesh with extraordinary vertices or independently imposed boundary stencils.
The supplied subdivision mask describes the regular, valence-six triangular grid. Its coefficients split into four parity classes after binary refinement: one class for old vertices and three classes for the three edge directions. For an old vertex with cyclic neighbors , the even stencil is
For an edge with endpoints and opposite vertices in its two incident triangles, the new odd vertex is
Rotating this edge stencil supplies the other two odd parity classes. All stencil weights sum to one, giving affine invariance; their first moments place an affine regular grid at the old positions and edge midpoints. Apply the same weights separately to . Boundary edges and extraordinary vertices need additional rules, which are not specified by this uniform mask. The subsequent arguments concern the regular interior grid and compatible extruded boundary treatment.
A practical family consists of constant-distance parallel surfaces and smooth variable normal offsets
Constants cover wall thickness, cutter radius and clearance. A scalar B-spline or piecewise polynomial displacement field permits thickness variation, local bumps and smooth blending; compact support makes local edits economical. Use the base parameterization or compatible data on its subdivision hierarchy so that evaluating the displacement and its derivatives requires only a small local stencil. Choose displacement size and gradients to avoid unintended folds, and trim global self-intersections where the physical application requires an envelope. A constant displacement smaller than the local curvature radii prevents the corresponding local focal singularities, although global clearance still needs a separate check.
When remaining within a polynomial or rational representation is more useful than prescribing an exact distance, a related practical form is with a low-degree scalar field . Its displacement is normal but has magnitude , so it is not a constant-distance parallel surface. For polynomial and , it stays polynomial; for rational input it stays rational. More general low-degree vector displacement fields similarly preserve efficient evaluation, while relinquishing the normal-offset condition. These forms make explicit the tradeoff between an exact metric offset, which involves normalization, and an easily represented deformation. Simple scalar normal-displacement fields are useful and directly evaluable; algebraic displacement fields are useful when representation closure is required.
Treat the subdivision surface as an evaluable limit together with its refinement hierarchy. At a requested location , evaluate the limit position and two independent limit tangent vectors, then set
On regular regions, local spline patches supply position and derivative evaluations. Near extraordinary vertices, use the actual subdivision rule and its limit-position and tangent evaluation machinery, or a convergent local refinement with controlled position and normal vector errors. If a tangent pair degenerates, the regular offset evaluator is not defined there; a crease requires separate one-sided offsets and an explicitly chosen join.
For polygonal interrogation, subdivide the base mesh adaptively. At every new sample, evaluate the base limit and its limit normal vector, and displace that sample by . Connect these samples with the inherited connectivity, refining until flatness and normal-variation bounds meet the desired tolerance. If the position error is and unit-normal error is , the offset-position error is at most , in addition to the interpolation error between samples. A variable normal offset can be sampled at the same locations, with its approximation error included as well. The result retains the base subdivision hierarchy for locating points and refining patches.
Displacing the original control vertices along estimated vertex normals and applying the original subdivision mask just once does not, in general, give the exact surface offset. If is one linear refinement step, then , while displacing the refined base gives ; normalization and the normal calculation are nonlinear, so in general. Thus the exact offset is an interrogation wrapper around the base limit, and a conventional subdivision control mesh for it is a fitted approximation requiring refinement or error control. Refine and interrogate the base limit, then offset its evaluated points; do not assume offsetting commutes with subdivision.
For a regular parametric surface , form , and define the offset evaluator
It is already a parametric surface with the same parameter domain, even if its coordinates no longer belong to the original polynomial or rational patch family. Point interrogation requires evaluations of and one normalization. For tangent or normal vector interrogation, differentiate the evaluator. For example,
and similarly for . The offset normal vector is the normalized cross product wherever it is nonzero. These derivatives also support intersection, projection and curvature calculations by the usual methods for parametric surfaces. For a variable normal offset, add and to the corresponding tangent derivatives.
With shape operator , the constant-distance offset differential is . Along a principal direction its factor is , where is a principal curvature. Consequently regular interrogation fails at ; on regular pieces the offset principal curvatures are with the continued normal orientation. Global self-intersections can occur even when both local factors are nonzero. Evaluate and differentiate the base surface and its normalized normal; an exact conversion back to the original patch type is unnecessary.
A parallel surface at signed distance from a design surface describes a constant-thickness skin, shell, coating or clearance envelope. A particularly important application is machining with a spherical cutter of radius : when the cutter touches without penetration, its center lies at , where is the outward unit normal vector. Thus a tool-center path can be computed on the surface offset rather than on the desired contact surface. Positive and negative surface offsets also model material addition and removal, and pairs of offsets describe the two faces of a thin manufactured wall. Offsets convert contact, thickness and clearance specifications into geometric surfaces which can be interrogated.
The construction is initially local. Where the offset develops self-intersections or reaches a curvature radius, not every point of the raw parallel surface is a usable physical boundary. Tool paths and solid envelopes may require trimming those pieces and checking global collisions.
Use unit knot spacing and the centered Cardinal cubic B-spline convention , where is supported on . On the span , with , the active control points are , and their B-spline weights are
For , take , . The weights and their derivatives are
The PDF has and , so the point and tangent vector are
Thus, under this centered convention,
The original PDF specifies neither the knot origin nor its indexing relative to . If instead the convention associates span with , the identical local weights multiply at the requested parameter, giving
These are parameter translations of the same uniform construction, rather than contradictory evaluations with the same knots. A specified knot convention is necessary to select the numerical pair uniquely; changing the knot spacing would also rescale the derivative.
The Cox-de Boor recurrence and De Boor's algorithm handle nonuniform knots and repeated knots without converting the whole curve. With a tabulated recurrence they require arithmetic after locating the span and use only local control points; a naive recursive basis evaluation wastes work by recomputing the same terms. De Boor's algorithm evaluates the vector directly using affine combinations. Inside the span these are convex combinations, which makes the geometric construction transparent and avoids the cancellation that can occur in a power-basis representation. Basis evaluation is especially useful when the same knots and parameter are shared by many coordinate functions or many curves, since the weights can be reused.
Precomputed power coefficients followed by Horner's method need only arithmetic per coordinate and are attractive for many evaluations within an unchanged span, particularly for fixed-degree uniform B-splines. Coefficient construction has an initial cost, control-point edits require updates to affected spans, and poor scaling of high-degree power coefficients can damage accuracy. Rescaling each span to helps. Bézier curve extraction has a similar initial conversion cost; De Casteljau's algorithm then gives stable local evaluation, subdivision, a convex hull bound and geometric flatness tests useful for rendering and intersection.
Subdivision is convenient when an entire polygonal approximation is wanted: refine only where needed and reuse the hierarchy. It is less economical for a single prescribed parameter and requires a geometric error bound before its approximate point can replace exact evaluation. Span lookup itself costs for sorted arbitrary knots, constant work for a uniform interior span, or amortized constant work for an ordered sequence of sample parameters. Use de Boor for robust general knots, shared basis weights for batches, and precomputed local polynomials or Bézier pieces for repeated interrogation.
Write a degree- B-spline as and locate its spline knot span. There are several equivalent exact evaluation methods.
Evaluate the at most nonzero basis functions by the Cox-de Boor recurrence, then form their weighted sum of control points. Alternatively apply De Boor's algorithm directly to the active control points. In a span , initialize and repeatedly interpolate:
for and . The last point is ; zero knot intervals are handled by the standard limiting convention or an appropriate neighboring nonempty span.
A third method precomputes the local polynomial coefficients on each span and evaluates them by Horner's method. For a uniform cubic B-spline, a fixed four-by-four basis matrix gives these coefficients. A fourth method uses knot insertion to express the relevant span as a Bézier curve, followed by De Casteljau's algorithm. Both interpolation algorithms also split the curve at the requested parameter. Repeated subdivision supplies arbitrarily accurate polygonal evaluation, although a finite subdivision mesh is generally an approximation rather than the exact requested point. Basis summation, de Boor interpolation, local polynomial evaluation and Bézier extraction are equivalent exact representations.
Store a bounding volume hierarchy for each object, using axis-aligned bounding boxes or tighter enclosing volumes. A leaf contains one triangle or a small group; every internal node encloses all its descendants. Start with the two roots. If their bounding volumes are disjoint, discard that pair. Otherwise descend into children of one or both nodes, usually splitting the larger node, until overlapping leaf pairs are reached. Apply the exact triangle-triangle intersection algorithm only at these leaves, and stop at the first hit if only a yes/no answer is required. The pruning is sound because disjoint enclosing volumes imply disjoint enclosed triangles.
A balanced bounding volume hierarchy typically takes work to construct and storage. It can be reused for repeated queries and refitted when vertex positions move; a rigid transformation can also be handled in a common coordinate frame. Spatial grids or octrees provide another broad-phase strategy: place triangles in every cell they meet and test only pairs from common cells, suppressing duplicates. A box test is especially valuable because the small randomly distributed triangles almost always fail it.
For of order , the naive method has about candidate pairs. Hierarchical pruning replaces this by the number of overlapping node pairs and actual candidate leaf pairs. No universal subquadratic worst-case bound follows: interpenetrating or very poorly separated meshes can still generate candidates. If “intersection of objects” means overlap of solid volumes rather than intersection of their boundaries, add a point-in-solid containment test when no surface intersections are found; one closed object can lie wholly inside the other. Use spatial enclosure to prune pairs before exact triangle tests.
Count scalar additions, subtractions, multiplications and divisions for the specific triangle-triangle intersection algorithm above; comparisons and index selection are separate. Computing one plane normal vector uses two vector differences, costing six subtractions, and one cross product, costing six multiplications and three subtractions. The three vertex-to-plane evaluations use nine further coordinate subtractions and three dot products, each with three multiplications and two additions. The first rejection test therefore costs
For randomly located triangles of characteristic size in a box of size , a second triangle straddles the first triangle's plane only when its position is in a slab of relative thickness . Consequently the first plane test rejects almost every pair: the expected arithmetic count for this implementation is , with the constant in the remainder determined by the subsequent branches. This is an average count, rather than the assertion that every input needs 39 operations.
For a generic surviving noncoplanar pair, the symmetric plane test costs another 39 operations, the cross product costs nine, and each of the four slice endpoints needs five scalar operations in the selected coordinate: one subtraction and division for the interpolation fraction, then one subtraction, multiplication and addition for the coordinate. Thus this branch uses
A fully executed coplanar test can use six planar edge directions. Each needs two subtractions to form its perpendicular and six two-dimensional dot products, costing operations. Including both plane tests and the parallelism cross product gives an upper count before any early exit. Contact and degeneracy can shorten or change these counts. Precomputed normal vectors or a preliminary axis-aligned bounding box test also change the answer: the latter uses only comparisons after its coordinate extrema are available. The relevant small-triangle average is 39 operations for the specified plane-first implementation; a generic complete test uses 107.
Let the triangles have vertices and . Work initially with nonzero-area triangles. A triangle-triangle intersection algorithm begins with the unnormalized normal vector and the three signed plane evaluations . If all are strictly positive, or all strictly negative, the second triangle lies strictly on one side of the first one's plane, so the triangles are disjoint. Otherwise compute and and apply the symmetric rejection test. Strict inequalities are important: contact on a vertex or edge counts as intersection.
If the planes are not parallel, put . Each triangle meets the other one's plane in an empty set, a point or a line segment. Its endpoints are obtained from zero-valued vertices and the edges whose endpoint plane evaluations have opposite signs. For example, an edge contributes
All these points lie on the common line of the two planes. Choose a coordinate for which and form the coordinate intervals , of the two slices. This coordinate is one-to-one along the common line, so the exact final test is
Only that coordinate of each slice endpoint needs to be evaluated; no full three-dimensional line parameterization is necessary.
Parallel planes which have survived the strict plane tests are coplanar. Drop the coordinate corresponding to the largest component of and test the two projected planar triangles. For each edge of either projected triangle, project both vertex sets onto the perpendicular direction. A strictly disjoint pair of projection intervals certifies separation. If none of the six edge directions separates them, the planar convex sets overlap: a separating line for two disjoint convex polygons can be chosen parallel to an edge of one of them. This includes containment and boundary contact.
A zero normal vector signifies a degenerate triangle; reduce its convex hull to a point or its extreme line segment and use point containment or segment intersection instead. For floating-point input, reliable sign predicates and scale-aware error bounds are preferable to treating a tiny signed distance as an arbitrary exact zero. Plane rejection followed by interval overlap, with a planar test for coplanar input, determines all nondegenerate cases.
Use the standard nonnegative partition-normalized B-splines ; their sum is at most one, and is exactly one for the complete clamped basis on . The printed question introduces only in its last matrix formula without defining it. The intended normalization is the unit-integral normalization of a B-spline:
For supports wholly inside the interval, . The positivity and partition convention, sometimes called normalization, should not be confused with individually rescaling every spline to have maximum exactly one.
The characterization in part 1(a) gives the normal equations for the orthogonal projection:
Dividing each equation by yields
This is the mixed-normalization spline Gram matrix. It need not be symmetric, but with and . The ordinary Gram matrix is positive definite because the splines are linearly independent, so is invertible and .
Since each is nonnegative and has integral one,
The induced matrix operator norm is the maximum absolute row sum, so
Finally, nonnegativity and the subpartition of unity for B-splines give
Taking the supremum over and then over proves the maximum-norm bound for spline projection:
The formulas also establish linearity and boundedness of the projection on continuous inputs. Its range is exactly the finite-dimensional spline space , since it fixes every spline in that space. Thus, when the splines are continuous, it is an operator with range ; it is not onto all of as the printed wording says. For example, cannot belong to a fixed finite-degree spline space because it is not a polynomial on any nonempty knot interval. The missing normalization and this range correction are needed for a precise reading of the result.
The first Jackson theorem for periodic approximation states that an absolute constant exists such that, for every continuous -periodic function and integer , there is a trigonometric polynomial of degree at most satisfying
Apply it to the continuous periodic function , which is even. Replace the approximant by its even part
Since , the triangle inequality gives . This symmetrization cancels all sine terms, so . The Chebyshev polynomials satisfy and have degree ; the latter follows inductively from , and . Therefore
is an algebraic polynomial of degree at most , and . Because cosine maps onto , the supremum norms agree exactly:
Finally, the definition of the best error, periodic Jackson approximation, and part (a) give the successive bounds
Thus
Neither the constant nor the choice of approximation space depends on . The cosine substitution for polynomial approximation and even symmetrization are what preserve the required degree bound.
For a function on an interval, the modulus of continuity is , with the pair restricted to that interval. For a periodic function the equivalent definition is . The mean value theorem and give
Both cosine values lie in . Hence for ,
Taking the supremum proves
If the periodic modulus of continuity is defined using circular distance instead, choose lifts at that shortest distance and apply the same argument. The cosine substitution for polynomial approximation therefore does not enlarge this modulus.
For each , choose the best uniform approximation . If its error is nonzero, take its alternating extrema. The intermediate value theorem supplies a point strictly between the th and st extrema such that , for . These points are distinct. The polynomial interpolation problem at them has a unique solution of degree at most , so its solution is exactly . This constructs the interpolation nodes from best uniform approximation.
If , then itself belongs to the polynomial space, and any distinct nodes give the same conclusion. In either case, take or the arbitrary nodes just described. Then
The Weierstrass approximation theorem gives ; alternatively, the bound derived in part 4(b), combined with uniform continuity, gives this convergence directly. Therefore
The nodes may depend on and on . The conclusion does not assert a universal sequence of interpolation grids working for every continuous target.
A nontrivial example is , the Chebyshev polynomial characterized by . Its supremum norm is one. At the points , , its values alternate between and ; reversing their order gives increasing nodes with the same alternation.
The zero polynomial therefore satisfies the Chebyshev alternation theorem for degree at most , so . Since the smaller polynomial space is contained in the larger one, ; the zero polynomial is feasible in the smaller space as well, giving the reverse inequality. Hence
A constant function would also give equality with both errors zero, but this example shows that equality can occur at a positive approximation error.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact