Parametric Cubic Curves, Splines, Bezier & Polygon Surfaces
Open in the Padhaiko app4.1 Introduction to Parametric Cubic Curves, Splines and Bezier Curves
Curve modeling is central to computer-aided design (CAD), animation path synthesis, font glyph generation, and geometric modeling. Curves can be described in three distinct mathematical representations:
- Explicit Representation (): Cannot represent closed curves (circles), multi-valued geometries, or vertical tangents ().
- Implicit Representation (): Can represent closed curves, but determining whether a point lies on the curve is easier than generating an ordered sequence of points to render along the curve.
- Parametric Representation ( for ): Each spatial coordinate is expressed as an explicit function of an independent parameter .
Parametric Cubic Curve Segment
A parametric cubic curve segment in 3D space is defined over parameter interval by:
where are algebraic coefficient vectors.
Why Cubic Polynomials ()?
In computer graphics, cubic polynomials are universally preferred for curve and spline modeling for several reasons:
- Flexibility: Degree 3 is the lowest degree polynomial that can form non-planar space curves (curves that twist through 3D space) and can support inflection points (points where curvature changes sign).
- Boundary Control: A cubic polynomial provides four degrees of freedom (four coefficients), allowing the curve to satisfy four boundary conditions: two endpoint positions and two endpoint tangent vectors.
- Continuity across Joints: Provides sufficient degrees of freedom to join piecewise segments with (tangent vector) or (curvature) continuity.
- Computational Stability: Higher-degree polynomials (degree ) are computationally expensive and prone to Runge's phenomenon—unwanted, wild oscillations between control points.
Continuity Conditions: Parametric vs. Geometric Continuity
Complex curves are modeled by joining low-degree piecewise polynomial segments end-to-end. The smoothness of the connection between two adjacent curve segments and (where ) is quantified by continuity conditions:
1. Parametric Continuity ()
Parametric continuity requires matching the derivatives of the parametric functions with respect to parameter at the joint:
- Continuity (Positional): The segments touch at the joint:
- Continuity (First Derivative / Tangent Vector): The first derivative vectors match in both direction and magnitude:
- Continuity (Second Derivative / Curvature Vector): The second derivative vectors match:
2. Geometric Continuity ()
Geometric continuity relaxes parametric constraints by requiring smoothness of the curve's geometric trace in space, independent of parameterization:
- Continuity: Identical to ; endpoints coincide ().
- Continuity: Tangent vectors at the joint point in the same direction, but may differ in magnitude:
- Continuity: Centers of curvature and radii of curvature match at the joint, ensuring smooth visual transition without requiring identical second derivative vectors.
| Continuity Order | Parametric Requirement () | Geometric Requirement () | Visual Effect |
|---|---|---|---|
| Order 0 | Continuous path; sharp corner or kink permitted. | ||
| Order 1 | (equal magnitude & direction) | (same direction) | Smooth tangent transition; no sharp corner. |
| Order 2 | Curvature center and radius match | Seamless curvature; no abrupt acceleration change. |
Cubic Hermite Spline Curves
A cubic Hermite curve segment is an interpolating spline defined by specifying two endpoint positions and two endpoint tangent vectors.
Derivation of Hermite Blending Functions
Let a cubic curve satisfy the four boundary conditions:
- Starting position:
- Ending position:
- Starting tangent vector:
- Ending tangent vector:
Differentiating with respect to :
Evaluating at and :
Substituting into and grouping by geometric constraints:
Cubic Hermite Curve Formulation
The cubic Hermite curve is given by:
where the four Hermite blending functions are:
In matrix form:
Notice that for all , satisfying partition of unity for the positional terms.
Bezier Curves
While Hermite curves require specifying abstract tangent vectors , the French engineer Pierre Bézier introduced a representation controlled entirely by intuitive geometric control points.
Bezier Curve
A Bezier curve of degree is defined by control points as a weighted linear combination:
where are the Bernstein polynomials:
Cubic Bezier Curves ()
For a cubic Bezier curve, four control points are specified ():
Cubic Bezier Curve Matrix Formulation
In matrix form, a cubic Bezier curve is:
Fundamental Properties of Bezier Curves
- Endpoint Interpolation:
The curve always passes directly through the first and last control points.
- Endpoint Tangent Property: Differentiating the Bernstein basis at and :
For , and . The tangent vector at an endpoint is parallel to the adjacent polygon segment.
- Convex Hull Property: Because Bernstein polynomials are non-negative ( for ) and sum to unity (), every point is a convex combination of the control points. Therefore, the entire Bezier curve lies completely within the convex hull of its control polygon.
- Affine Invariance: Applying an affine transformation (translation, scaling, rotation) to the control points transforms the curve identically:
- Variation Diminishing Property: Any straight line crosses the Bezier curve at most as many times as it crosses the control polygon. This ensures that the curve does not oscillate more than its defining polygon.
De Casteljau's Algorithm
De Casteljau's algorithm provides a numerically stable, geometric construction of Bezier curves via recursive linear interpolation:
de Casteljau's Recursive Algorithm
Let be the control points of a degree- Bezier curve. To evaluate the curve at parameter :
- Initialize level :
- For recursion level :
- The curve point at parameter is given by the single point at level :
Comparison with Splines
- Natural Cubic Splines: Interpolating splines with continuous second derivatives () across all knots. However, modifying a single control point alters the entire curve globally, making them less suitable for interactive shape editing.
- B-Spline Curves: Solve the global dependency problem by utilizing local polynomial basis functions defined over knot vectors, ensuring that moving one control point modifies only nearby local segments.
- NURBS (Non-Uniform Rational B-Splines): Generalized rational B-splines that can represent free-form curves as well as standard conic sections (circles, ellipses, parabolas) exactly.
4.2 Surface Modeling: Polygon Surfaces, Tables and Orientation
In 3D computer graphics, 3D solids and curved boundaries are predominantly modeled using polygon mesh surfaces (boundary representations / B-rep). A polygon mesh approximates a surface as a collection of planar polygonal facets (typically triangles or quadrilaterals) sharing common edges and vertices.
Polygon Data Tables (Three-Table Hierarchy)
To store and manipulate polygon mesh geometry efficiently without redundancy, standard graphics databases organize the mesh into a three-level relational hierarchy:
- Vertex Table: Contains spatial coordinates for each distinct vertex in the model.
- Edge Table: Contains pointers to the two endpoint vertices of each edge, along with pointers to the polygon faces that share this edge.
- Polygon / Face Table: Contains ordered pointers to the edges (or vertices) that form the perimeter of each polygon face.
| Table | Identifier | Components / Pointers | Notes |
|---|---|---|---|
| Vertex Table | Base vertex 1 Base vertex 2 Base vertex 3 Apex vertex | ||
| Edge Table | Base edge Base edge Base edge Slanted edge 1 Slanted edge 2 Slanted edge 3 | ||
| Polygon Table | Base face Front face Right face Left face |
Why the Three-Table Design is Used
- Elimination of Coordinate Duplication: Each vertex coordinate is stored exactly once in memory. In a typical closed manifold mesh, each vertex is shared by 4 to 6 polygons; storing coordinates directly within polygons would waste substantial memory.
- Topological Consistency: Shared edges are explicitly tracked. This allows edge-drawing (wireframes) to draw each edge exactly once.
- Efficient Shading and Normal Averaging: When computing smooth surface normals for Gouraud or Phong shading, adjacent faces sharing a vertex or edge can be identified immediately.
Plane Equation of a Polygon Face
Every planar polygon facet lies in a plane described by the standard linear equation:
where represents the normal vector perpendicular to the plane, and determines the plane's offset from the origin.
Given three non-collinear vertices , , and listed in counterclockwise order around the face:
The normal vector is obtained from the vector cross product:
Solving for by substituting vertex :
The unit surface normal vector is:
Surface Normal and Spatial Orientation: Inside-Outside Test
The spatial orientation of a polygon face is defined by the direction of its surface normal vector .
In computer graphics, the right-hand rule establishes the outward orientation convention:
- Vertices are ordered counterclockwise when viewed from the outside looking at the exterior (front) face of the solid.
- This ordering ensures that the cross product points directly outward, toward the exterior of the solid object.
Surface Normal and Inside-Outside Spatial Test
For a planar polygon facet with outward normal and plane equation , any arbitrary point in 3D space can be classified relative to the surface by evaluating the plane function:
- Inside the surface (interior half-space):
The point lies behind the plane, in the direction opposite to the outward normal .
- On the surface:
The point lies directly on the polygon plane.
- Outside the surface (exterior half-space):
The point lies in front of the plane, in the direction of the outward normal .
This spatial test forms the foundational mathematical check for back-face detection, polygon clipping, ray-surface intersection testing, and solid modeling point-containment algorithms.
Worked Examples
Evaluation of a Cubic Bezier Curve Point and Tangent
A cubic Bezier curve is defined by four control points:
- Compute the coordinates of the curve point at parameter value using the Bernstein basis polynomials.
- Confirm the result using de Casteljau's recursive linear interpolation algorithm.
Evaluating Bernstein Polynomials at : For degree and :
Computing Curve Point Coordinates: Evaluating and :
Thus, .
Confirming via de Casteljau's Algorithm: Using at each recursion stage:
- Level 0 (Control Points):
- Level 1:
- Level 2:
- Level 3:
Both methods yield precisely .
- Using Bernstein basis: .
- De Casteljau's algorithm confirms .
Hermite Cubic Curve Blending and Point Calculation
A cubic Hermite curve segment is specified by endpoints and tangent vectors:
- Determine the parametric equation of the curve .
- Calculate the coordinates of the midpoint of the curve at parameter .
Evaluating Hermite Blending Functions at :
Computing Parametric Coordinate Equations: The general Hermite formulation gives:
Substituting the boundary values:
Evaluating Coordinates at : Substituting :
The curve reaches point at parameter .
- Parametric curve equations: and .
- Midpoint coordinates at : .
Polygon Surface Plane Equation, Normal Vector and Inside-Outside Test
A triangular polygon facet on the boundary of a 3D solid has counterclockwise vertices:
- Determine the coefficients of the plane equation .
- Compute the unit outward surface normal vector .
- Determine whether point and point lie inside or outside the surface.
Computing Edge Vectors and Normal Vector: Forming vectors along the polygon edges:
Evaluating the outward surface normal :
Thus, .
Finding Plane Constant and Unit Normal: Substituting vertex :
The plane equation is:
Computing the magnitude of the normal :
The unit outward normal vector is:
Executing the Inside-Outside Test: Evaluating :
- For point :
Because , point lies inside the surface.
- For point :
Because , point lies outside the surface.
- Plane equation: (or ).
- Unit outward normal: .
- Classification: is inside (); is outside ().
Exercises
Curves and Surface Modeling Exercises
Define a spline curve. Distinguish between parametric continuity () and geometric continuity () at the joint between two curve segments.
Definition of a Spline Curve: In computer graphics, a spline curve is a piecewise polynomial curve constructed by joining multiple low-degree polynomial segments (typically cubic) end-to-end at boundary points called knots, subject to specified continuity conditions across the joints. Piecewise low-degree segments prevent unwanted polynomial oscillations while allowing local shape modification.
Comparison of Continuity Orders:
- Positional Continuity ( and ): Both require that the end of the first segment coincides spatially with the start of the second segment ().
- First-Order Continuity ( vs. ): continuity requires that the first derivative vectors match in both direction and magnitude (). continuity requires only that the tangent vectors point in the same direction ( for ), allowing different speeds of parameter traversal.
- Second-Order Continuity ( vs. ): requires identical second derivative vectors (). requires that the center of curvature and radius of curvature match continuously across the joint, providing smooth visual curvature without imposing equal acceleration.
A spline curve is a composite curve composed of piecewise polynomial segments joined with specified smoothness. continuity requires equality of parametric derivatives up to order , while continuity requires only geometric alignment of tangents and curvature, independent of parameterization.
A cubic Bezier curve is defined by four control points:
Calculate the coordinates of the point on the curve at parameter .
Evaluating Bernstein Polynomials at : For and :
Computing Point Coordinates: Evaluating :
Evaluating :
The coordinates of the curve point at are:
Derive the four cubic Hermite blending functions from the endpoint boundary conditions.
Setting Up Boundary Conditions: A cubic parametric curve is given by for . Its derivative is . The boundary conditions are:
Solving for Polynomial Coefficients: From the first and third equations: and . Substituting into the second and fourth equations:
Multiplying the first equation by and subtracting from the second:
Substituting back:
Grouping by Boundary Vectors: Substituting into :
Grouping terms multiplying :
The four cubic Hermite blending functions are:
State and prove the convex hull property and the endpoint tangent property of a Bezier curve of degree .
Proof of the Convex Hull Property: A Bezier curve of degree is defined by for , where .
- Non-negativity: For any , and , and binomial coefficient . Thus, for all .
- Partition of Unity: By the Binomial Theorem:
Because the blending weights are non-negative and sum strictly to , every point is a convex combination of control points . Therefore, the curve lies entirely inside the convex hull of its control polygon.
Proof of the Endpoint Tangent Property: Differentiating the general Bezier curve equation with respect to :
Evaluating at starting endpoint : Since and for :
Evaluating at ending endpoint : Since and all other basis functions vanish:
Thus, the tangent vector at each endpoint is collinear with the adjacent edge of the control polygon.
- Convex Hull Property: Holds because and for all .
- Endpoint Tangents: and , proving the tangent vectors are directly proportional to the boundary control edges.
Describe the three-table polygon representation (vertex table, edge table, polygon table) used in geometric surface modeling. Explain three principal advantages of this data structure over storing explicit coordinates per polygon.
Structure of the Three Tables:
- Vertex Table: Stores vertex identifiers alongside their 3D coordinates .
- Edge Table: Stores edge identifiers with pointers to their start and end vertex keys, plus pointers to adjacent polygon faces sharing the edge.
- Polygon / Face Table: Stores polygon identifiers with ordered lists of edge identifiers (or vertex identifiers) outlining the boundary of each facet.
Three Principal Advantages:
- Zero Coordinate Redundancy: Vertices shared by multiple adjacent facets are stored exactly once in memory, drastically reducing the storage footprint of large meshes.
- Efficient Edge Traversal and Rendering: Wireframe rendering algorithms can iterate directly over the Edge Table, drawing each edge exactly once without redrawing shared boundaries between polygons.
- Topology and Normal Sharing: Determining neighboring faces sharing a common edge or vertex is an lookup, allowing fast surface normal averaging for smooth shading (Gouraud/Phong) and silhouette edge detection for shadow volumes.
The three-table representation splits mesh data into Vertex, Edge, and Polygon tables. Advantages:
- Eliminates coordinate duplication.
- Draws each wireframe edge exactly once.
- Provides immediate adjacency information for normal averaging and lighting.
A planar triangular face on the boundary of a solid has counterclockwise vertices:
- Find the plane equation coefficients for .
- Determine the unit outward normal vector .
- Determine whether point lies inside or outside the surface.
Computing Normal Vector via Vector Cross Product: Forming boundary vectors from :
Taking the cross product :
Thus, .
Evaluating Constant and Unit Normal: Substituting vertex :
The plane equation is:
Computing the magnitude of normal vector :
The unit outward normal vector is:
Evaluating the Inside-Outside Test for : Evaluating the plane function :
Because , point lies in front of the plane in the exterior half-space (outside the surface).
- Plane equation: .
- Unit outward normal: .
- Point lies outside the surface ().