Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 56 (Computer-aided Geometric Design)

Work in three-dimensional projective space, with four homogeneous coordinates indexed $0,1,2,3$. Let $A$ and $B$ be independent representatives of two points. The Plücker coordinates of their line areThis antisymmetric matrix has rank two and is defined only up to a nonzero scalar. Replacing the pair by another basis of the same two-dimensional subspace multiplies $L$ by the determinant of that basis change. Its six independent entries satisfy $L^{01}{L}^{23}-L^{02}{L}^{13}+L^{03}{L}^{12}=0$, since the exterior product $(A\wedge B)\wedge (A\wedge B)$ vanishes.

To describe the same line as an intersection of planes, choose a volume orientation with ${\epsilon }_{0123}=1$ and define the dual Plücker coordinates byThe independent components pair asConversely, $L^{ij}=\frac{1}{2}{\epsilon }^{ijkl}{L}_{kl}$ with the matching volume convention. The lower-index form annihilates both defining points: $L_{ij}{A}^j=L_{ij}{B}^j=0$. Its columns span the pencil of planes containing their line. This dualization uses the volume form, not a Euclidean metric for raising and lowering indices. Two-index point and plane representations are dual in projective dimension three; in higher dimensions the corresponding dual exterior form has a different degree.

For a general plane covector $F_i$, contract the upper-index form:This is a linear combination of $A,B$, so it is on the line, and $F_i{P}^i=0$ by antisymmetry, so it is on the plane. Provided the resulting vector is nonzero, its homogeneous coordinates give the unique intersection, including intersections at infinity. If $F(A)=F(B)=0$, the whole line lies in the plane and the zero result correctly indicates that there is no unique intersection. These are the line-plane incidence in Plücker coordinates operations used in the subparts.

The $j$th coordinate plane has equation $X^j=0$, hence covector $F_i={\delta }_{ij}$. The line-plane incidence in Plücker coordinates formula reduces toThus the $j$th column of the upper-index Plücker coordinates contains the intersection point's homogeneous coordinates, up to projective scaling. Its $j$th entry vanishes as required. If that column is zero, both defining points have coordinate $j$ zero and the entire line is contained in the coordinate plane; there is no distinguished intersection point. Reading rows instead changes only the irrelevant overall sign.

Let $E_j$ denote the $j$th coordinate point. The plane through the given line and $E_j$ has covectorIndeed, the lower-index Plücker coordinates annihilate both line-defining points, while $F_i^{(j)}{E}_j^i=L_{jj}=0$. The $j$th column therefore lists this plane's coefficients. In the affine chart $X^0\ne 0$, the points $E_1,E_2,E_3$ lie at infinity and represent the three coordinate axis directions; a plane containing $E_j$ is parallel to that axis direction. If $E_j$ already lies on the line, the column is zero and infinitely many planes through the line contain that direction. This is the dual of the containment degeneracy in the coordinate-plane intersection.

An invertible $4\times 4$ matrix $M$, modulo scalar multiples, acts linearly on homogeneous coordinates. In an affine chart its projective transformation has the formwhere the denominator must be nonzero for a finite image. The important nested groups are Euclidean motions, Euclidean similarities, invertible affine maps, and general projective transformations. Their defining preserved structures become progressively weaker.

A Euclidean motion has $x^{\prime }=Rx+b$ with $R^{T}R=I$. It preserves all distances and angles, hence lengths, areas and volumes. Proper motions have $\det R=1$ and preserve orientation as well; allowing reflections preserves unsigned measurements but can reverse signed ones. A Euclidean similarity has $x^{\prime }=sRx+b$ with $s>0$. It preserves angles and all ratios of lengths; lengths, areas and volumes scale by $s,s^2,s^3$. Thus rigid shape is preserved up to one overall scale.

An invertible affine map has $c=0$ and preserves the plane at infinity. It preserves incidence, parallelism, collinear ratios, affine combinations, and ratios of volumes. Absolute volume scales by $|\det A|$; the volume-preserving affine subgroup has $|\det A|=1$. Lengths and angles are not affine invariants. A general projective transformation preserves incidence, collinearity, concurrence, tangency, and the cross-ratio of four collinear points, but can move the plane at infinity. The cross-ratio, rather than a three-point affine ratio, survives arbitrary projective changes. For a homogeneous quadric hypersurface $X^{T}QX=0$, its transformed matrix is $M^{-T}Q{M}^{-1}$, so its rank and projective degeneracy are preserved.

For surface classes, rather than a fixed numerical radius or curvature, the consequences are:

For example, the affine stretch $(x,y,z)\mapsto (2x,y,z)$ changes a unit sphere to $x^{\prime 2}/4+y^{\prime 2}+z^{\prime 2}=1$ and a unit circular cylinder to $x^{\prime 2}/4+y^{\prime 2}=1$. A general conical surface written $P+tD(s)$ transforms affinely into $T(P)+tAD(s)$, so every generator still passes through a finite apex. A nonsingular elliptic paraboloid or hyperbolic paraboloid has quadratic part of rank two and a nonzero linear component in its null direction. An invertible affine map preserves that rank, inertia and nonzero null-direction coupling, so translation and linear coordinate changes again put it in elliptic or hyperbolic paraboloid form.

Under a genuinely projective change, these Euclidean classifications depend on which plane is designated as infinity. For the map $(x,y,z)\mapsto (x,y,z)/(1+\alpha z)$, a circular cylinder $x^2+y^2=1$ becomesa cone whose apex is finite. The inverse map sends that apex to infinity and produces the cylinder. Thus a cone is projectively invariant as a family of concurrent generators if an ideal apex is allowed, but finite-apex cones and cylinders are not separately invariant. Likewise a projective image of a sphere or either type of paraboloid remains a nonsingular quadric hypersurface, but need not retain its affine or metric type. The distinction between general cones and circular cones matters: circularity is a metric property and is not preserved by arbitrary affine changes.

Write $N_{i,d}$ for the partition-of-unity-normalized degree-$d$ B-spline, supported on $[t_i,t_{i+d+1}]$. Assume $d\ge 1$. First take distinct knots; endpoint repetitions will be interpreted as confluent limits. For fixed parameter $t$, let $f_t(\tau )=(\tau -t{)}_{+}^d$, and formwhere the brackets denote a divided difference in the knot variable $\tau$. This representation follows from the defining properties, rather than assuming a derivative recurrence. If $t<t_i$, $f_t$ is a degree-$d$ polynomial in all its knot arguments and its order-$(d+1)$ divided difference is zero. If $t>t_{i+d+1}$, every truncated-power term is zero. Between knots it is a degree-$d$ polynomial with $d-1$ continuous derivatives. Those support and smoothness conditions determine a one-dimensional spline space: there are $d+1$ spans, the continuity conditions leave $2d+1$ coefficients, and vanishing through order $d-1$ at both support ends imposes $2d$ conditions.

The remaining scalar is fixed by the prescribed integral. Put $a=t_i$, $b=t_{i+d+1}$. Integrating the truncated power first givesThe order-$(d+1)$ divided difference of this polynomial is its leading coefficient $1/(d+1)$, so the proposed $N_{i,d}$ has integral $(b-a)/(d+1)$, exactly the specified normalization.

Now differentiate with respect to $t$ and apply the final recursion for a divided difference:In terms of normalized lower-degree B-splines, this is the B-spline differentiation formulaA zero denominator corresponds to a collapsed-support basis term and contributes zero. Repeated knots follow by coalescing distinct knots; at knots where the classical derivative is discontinuous, read the formula on each open span or one-sided. The stated maximal interior continuity corresponds to simple interior knots, while the clamped endpoint repetitions do not affect the interior argument.

Let the control-point abscissae be the Greville abscissaeCollect the coefficient of $N_{i,d-1}$ after differentiating:The difference of the two consecutive knot averages telescopes toso every noncollapsed coefficient is one. The lower-degree basis on the endpoint-trimmed knot vector has partition of unity; equivalently the outer lower-degree basis functions on the original vector have collapsed support. Therefore $X^{\prime }(t)=1$ on the parameter interval. With $d+1$ repeated left endpoint knots at $a$, the clamped basis has $N_{0,d}(a)=1$, all other values zero, and ${\xi }_0=a$. Thus $X(a)=a$ fixes the constant of integration. Continuity and endpoint limits now giveThis is linear precision at Greville abscissae. It requires neither equal knot spacing nor a restriction on the other control-point coordinates; those determine the remaining coordinates of the parametric curve.

The basic parametric surface interrogation enquiries provide the parameter domain and patch adjacency; evaluation of $S(u,v)$; first derivatives $S_u,S_v$; and, for curvature or error-controlled stepping, second derivatives $S_{uu},S_{uv},S_{vv}$. Useful search enquiries also supply conservative bounding volumes over parameter rectangles, subdivision or restriction of a patch, and regularity/singularity information. A local inverse or closest-point enquiry can help seed a search but does not replace global component isolation.

At a regular point, $S_u,S_v$ are independent tangent vectors, and the oriented unit normal vector isThe tangent plane consists of $S+\alpha S_u+\beta S_v$. If the cross product is zero, this chart does not define a normal; use a regular alternative chart or treat a true singularity separately.

For two surfaces, collect the four parameters in $w=(u_1,v_1,u_2,v_2)$ and setAt a transverse intersection, $n_1\times n_2\ne 0$ and $J$ has rank three. Hence the implicit function theorem makes $F=0$ locally a curve. Choose its physical unit tangent vectorWith $G_i=A_i^T{A}_i$, the parameter derivatives for physical arc length areSince $\tau$ lies in both tangent planes, $A_i(u_i^{\prime },v_i^{\prime }{)}^T=\tau$ exactly. Thus these two pairs form a vector $d$ in the kernel of $J$.

A practical transversal intersection of two parametric surfaces algorithm is:

with Newton method. The final equation intersects the curve with the plane through $X_p$ perpendicular to the predicted tangent. Its Jacobian row is $[{\tau }^T{A}_1,0,0]$; together with $J$ it is nonsingular at a sufficiently nearby transverse point. This removes the otherwise free along-curve parameter in the three coincidence equations.

A finite tolerance supplies a polygonal or fitted-curve approximation; regularity and certified bounds determine its accuracy. Parallel normals, singular charts, branch contacts and coincident patches require separate handling: their intersection may be a singular curve, an isolated point or a two-dimensional region. The transverse marching equations must not be used to claim a unique curve in those cases.

A subdivision surface enquiry acts on the limit surface, not just on the current control mesh. The basic subdivision surface interrogation operations are: enumerate initial patches and their topological adjacency; subdivide a patch into covering children with inherited boundary links; return conservative bounding volumes; estimate approximation error and, where available, normal variation; and evaluate limit positions and first derivatives or tangent data. Boundaries, creases and extraordinary subdivision vertices need explicit rules. Nonnegative convex subdivision weights can supply a local control-hull enclosure, but a scheme with negative weights needs another proved enclosure; an arbitrary control-mesh box is not automatically a bound on the limit.

The intersection of subdivision limit surfaces can be computed by a paired recursive search. Start with every relevant pair of root patches $(A,B)$, along with their domains and adjacency identifiers:

A termination criterion specifies geometric error and conditioning, not merely a fixed refinement depth. For isolated regular transverse components, shrinking limit enclosures and normal/error bounds permit reliable curve approximation. Candidate boxes cannot be discarded merely because no coarse edge has crossed another surface: a complete small closed component can lie in the interior. Tangency, coincident limit patches, creases and poorly conditioned extraordinary-point neighborhoods need special tests or must be reported as unresolved degenerate configurations. The intersection is that of the two subdivision limits; intersecting a finite refined mesh without error control only gives an approximation.

Orient the boundary cyclically as $B_0,B_1,\dots ,B_{m-1},B_m=B_0$, and orient every fan triangle consistently as $(P,B_i,B_{i+1})$. Its vector area isChoose the sign convention in which a triangle with positive normal component along the unit vector $V$ has positive projected area. Then the total signed, or algebraic, projected area isThis is a signed sum, so overlaps and oppositely oriented pieces cancel. Expand the cross product:The sum of $B_i-B_{i+1}$ is zero around the closed polygon. ConsequentlyThis vector area of a polygonal boundary depends only on the oriented boundary, not on $P$, and does not require that the polygon be planar. Translating the boundary adds telescoping terms too, so the formula is independent of the choice of spatial origin. It is the polygonal instance of the vector area boundary integral $\frac{1}{2}\oint B\times dB$.

For $\mathbf{A}\ne 0$, the Cauchy-Schwarz inequality gives $A(V)\le |\mathbf{A}|$ because $|V|=1$. HenceThe opposite direction gives the minimum $-|\mathbf{A}|$; either direction maximizes the absolute algebraic area. Zero algebraic area occurs exactly for unit directions satisfying $V\cdot \mathbf{A}=0$, a great circle of directions perpendicular to the area vector. If $\mathbf{A}=0$, every direction gives zero and every direction is a maximizer, even though the sum of unsigned triangle areas may be positive. Reversing the initial orientation reverses every signed result consistently.