CE7453: Bezier Techniques

10 minute read

Published: June 22, 2024

This post summarizes key concepts of Bezier techniques covered in CE7453, based on the lecture notes “03-BeizerTechniques”.

Key Concepts

Bezier curves and surfaces are parametric representations used extensively in computer graphics, CAD systems, and geometric modeling. They provide intuitive control over curve shapes through control points.

Historical Context

Bezier curves were developed independently by Pierre Bézier (at Renault) and Paul de Casteljau (at Citroën) in the 1960s for automotive design. The mathematical foundation, however, dates back to the Bernstein polynomials developed in the early 20th century.

Real-world Applications

Vehicle Design: Automobile body shapes and aerodynamic profiles
Font Design: TrueType and PostScript font outlines
Animation: Smooth motion paths and transitions
CAD/CAM: Industrial part design and manufacturing
Computer Graphics: Representing curves and surfaces in rendering

Bezier Curves

1. Mathematical Foundation

Definition: A Bezier curve of degree n is defined by n+1 control points
Bernstein Basis: The mathematical foundation of Bezier curves
- B_i,n(t) = (n choose i) tⁱ (1-t)^n-i
Parametric Equation: P(t) = Σ_i=0ⁿ P_i B_i,n(t), t ∈ [0,1]

Bernstein Polynomials Derivation

The Bernstein basis polynomials of degree n are:

B_i,n(t) = (n choose i) tⁱ (1-t)^n-i for i = 0, 1, …, n

Where (n choose i) is the binomial coefficient:

(n choose i) = n! / (i! × (n-i)!)

Common Bezier Curve Forms

Linear Bezier Curve (n=1, 2 control points):
- P(t) = (1-t)P₀ + tP₁
- Simple linear interpolation between two points
Quadratic Bezier Curve (n=2, 3 control points):
- P(t) = (1-t)²P₀ + 2(1-t)tP₁ + t²P₂
- Creates a parabolic arc
Cubic Bezier Curve (n=3, 4 control points):
- P(t) = (1-t)³P₀ + 3(1-t)²tP₁ + 3(1-t)t²P₂ + t³P₃
- Most commonly used form, offering good balance between flexibility and computational efficiency

Worked Example: Cubic Bezier Curve

Given control points in 2D:

P₀ = (0, 0)
P₁ = (1, 3)
P₂ = (3, 3)
P₃ = (4, 0)

Let’s compute points on the curve for t = 0, 0.25, 0.5, 0.75, 1:

t	(1-t)³	3(1-t)²t	3(1-t)t²	t³	P(t)
0	1	0	0	0	(0, 0)
0.25	0.422	0.422	0.141	0.016	(1.31, 2.34)
0.5	0.125	0.375	0.375	0.125	(2.5, 2.25)
0.75	0.016	0.141	0.422	0.422	(3.44, 1.22)
1	0	0	0	1	(4, 0)

This creates a smooth curve that starts at P₀, is pulled toward P₁ and P₂, and ends at P₃.

2. Properties

Endpoint Interpolation: Curve passes through first and last control points
Convex Hull: Entire curve lies within convex hull of control points
Affine Invariance: Transforming control points transforms curve predictably
Variation Diminishing: Curve doesn’t oscillate more than control polygon
Differentiability: C^∞ continuous within segments

Mathematical Proof of Properties

Endpoint Interpolation:

At t=0: P(0) = B_0,n(0)P₀ + … + B_n,n(0)P_n = P₀
- Because B_0,n(0) = 1 and B_i,n(0) = 0 for i > 0
At t=1: P(1) = B_0,n(1)P₀ + … + B_n,n(1)P_n = P_n
- Because B_n,n(1) = 1 and B_i,n(1) = 0 for i < n

Convex Hull Property:

Since Bernstein polynomials are non-negative and sum to 1 (partition of unity), the Bezier curve is a convex combination of its control points.

Derivatives of Bezier Curves

The derivative of a Bezier curve of degree n is:

P’(t) = n Σ_i=0^n-1 (P_i+1 - P_i) B_i,n-1(t)

For a cubic Bezier curve: P’(t) = 3[(P₁ - P₀)(1-t)² + (P₂ - P₁)2(1-t)t + (P₃ - P₂)t²]

The second derivative is: P’‘(t) = n(n-1) Σ_i=0^n-2 (P_i+2 - 2P_i+1 + P_i) B_i,n-2(t)

3. De Casteljau Algorithm

Purpose: Efficient and numerically stable way to evaluate Bezier curves
Process: Recursive linear interpolation between control points
Advantages:
- Geometrically intuitive
- Allows curve subdivision at any parameter value
- Numerically stable

Step-by-step De Casteljau Algorithm

Start with n+1 control points: P₀, P₁, …, P_n
For r from 1 to n:
- For i from 0 to n-r:
  - P_i^r = (1-t)P_i^r-1 + tP_i+1^r-1
P₀ⁿ is the point on the curve at parameter t

Worked Example: De Casteljau Algorithm

For a cubic Bezier curve with control points P₀, P₁, P₂, P₃, let’s evaluate at t = 0.5:

First level (r = 1):

P₀¹ = (1-0.5)P₀ + 0.5P₁ = 0.5P₀ + 0.5P₁
P₁¹ = (1-0.5)P₁ + 0.5P₂ = 0.5P₁ + 0.5P₂
P₂¹ = (1-0.5)P₂ + 0.5P₃ = 0.5P₂ + 0.5P₃

Second level (r = 2):

P₀² = (1-0.5)P₀¹ + 0.5P₁¹ = 0.5(0.5P₀ + 0.5P₁) + 0.5(0.5P₁ + 0.5P₂) = 0.25P₀ + 0.5P₁ + 0.25P₂
P₁² = (1-0.5)P₁¹ + 0.5P₂¹ = 0.5(0.5P₁ + 0.5P₂) + 0.5(0.5P₂ + 0.5P₃) = 0.25P₁ + 0.5P₂ + 0.25P₃

Third level (r = 3):

P₀³ = (1-0.5)P₀² + 0.5P₁² = 0.5(0.25P₀ + 0.5P₁ + 0.25P₂) + 0.5(0.25P₁ + 0.5P₂ + 0.25P₃) = 0.125P₀ + 0.375P₁ + 0.375P₂ + 0.125P₃

This gives us P(0.5) = 0.125P₀ + 0.375P₁ + 0.375P₂ + 0.125P₃, which matches the cubic Bernstein polynomial evaluation.

Python Implementation for De Casteljau

import numpy as np

def de_casteljau(control_points, t):
    """
    Evaluate a Bezier curve at parameter t using De Casteljau algorithm.
    
    Parameters:
    - control_points: List of control points (can be 2D or 3D)
    - t: Parameter value in range [0, 1]
    
    Returns:
    - Point on the Bezier curve at parameter t
    """
    points = np.copy(control_points)
    n = len(points) - 1  # Degree of the curve
    
    for r in range(1, n + 1):
        for i in range(n - r + 1):
            points[i] = (1 - t) * points[i] + t * points[i + 1]
    
    return points[0]  # Final point is P₀ⁿ

Curve Subdivision

One powerful application of the De Casteljau algorithm is curve subdivision. At parameter t, the algorithm computes intermediate points that can be used to represent two new Bezier curves of the same degree, together forming the original curve.

For a cubic curve at t = 0.5, the subdivided control points are:

Left half: [P₀, P₀¹, P₀², P₀³]
Right half: [P₀³, P₁², P₂¹, P₃]

This subdivision property is useful for rendering, intersection calculations, and adaptive approximation of Bezier curves.

Bezier Surfaces

Construction: Tensor product of Bezier curves
Control Net: Array of control points that define the surface
Equation: P(u,v) = Σ_i=0ⁿ Σ_j=0^m P_i,j B_i,n(u) B_j,m(v)

Tensor Product Construction

A Bezier surface is created by taking a bidirectional net of control points P_i,j and applying the Bernstein basis in both parametric directions (u and v).

For a bicubic Bezier surface (n=3, m=3), we have a 4×4 grid of 16 control points and:

P(u,v) = Σ_i=0³ Σ_j=0³ P_i,j B_i,3(u) B_j,3(v)

Evaluating Bezier Surfaces

Bezier surfaces can be evaluated using a bivariate extension of the De Casteljau algorithm:

Apply the De Casteljau algorithm to each row of control points using parameter u
Apply the De Casteljau algorithm to the resulting points using parameter v

Alternatively:

Apply the De Casteljau algorithm to each column of control points using parameter v
Apply the De Casteljau algorithm to the resulting points using parameter u

Either approach yields the same result due to the tensor product structure.

Python Implementation for Bezier Surface Evaluation

def bezier_surface(control_points, u, v):
    """
    Evaluate a Bezier surface at parameters (u, v).
    
    Parameters:
    - control_points: 2D array of control points
    - u, v: Parameter values in range [0, 1]
    
    Returns:
    - Point on the Bezier surface at (u, v)
    """
    # First pass: evaluate along rows (u parameter)
    row_points = []
    for row in control_points:
        point = de_casteljau(row, u)
        row_points.append(point)
    
    # Second pass: evaluate along result (v parameter)
    return de_casteljau(row_points, v)

Practical Applications

1. Curve Design

Path Design: Creating smooth trajectories for animation or motion planning
Font Design: Representing letter outlines in digital typography
Boundary Representation: Defining object boundaries in modeling

2. Surface Design

Product Design: Creating smooth surfaces for industrial design
Character Modeling: Defining smooth surfaces for animation characters
Architectural Design: Creating complex curved structures

Interactive Design Tools

Modern design software uses Bezier curves and surfaces as fundamental building blocks:

Adobe Illustrator/Photoshop: Pen tool creates Bezier paths
Blender/Maya: Curve and surface tools based on Bezier formulations
AutoCAD/SolidWorks: Curve and surface design tools

Rendering Bezier Curves

While Bezier curves are defined mathematically as continuous functions, for rendering purposes they are typically approximated using line segments or other primitives.

The common approach is:

Evaluate the curve at a set of parameter values: t = 0, Δt, 2Δt, …, 1
Connect the resulting points with line segments

More sophisticated approaches include:

Adaptive subdivision based on curvature
Conversion to other primitive types supported by graphics hardware

Limitations and Solutions

Local Control: Lack of local control with pure Bezier curves
- Solution: Use piecewise Bezier curves
Degree Elevation: Increasing the degree of a curve without changing its shape
Degree Reduction: Approximating a high-degree curve with a lower-degree one

Piecewise Bezier Curves

To achieve local control, multiple Bezier curve segments can be joined together. For smoothness, continuity conditions must be enforced at join points:

C⁰ continuity: Endpoint of one segment equals the start point of the next
C¹ continuity: First derivatives are equal at join points
C² continuity: Second derivatives are equal at join points

For cubic Bezier curves with control points [P_i,0, P_i,1, P_i,2, P_i,3] and [P_i+1,0, P_i+1,1, P_i+1,2, P_i+1,3]:

C⁰ continuity: P_i,3 = P_i+1,0
C¹ continuity: P_i,3 - P_i,2 = α(P_i+1,1 - P_i+1,0), where α > 0
C² continuity: Additional constraints on control points

Degree Elevation

Degree elevation allows representing a Bezier curve of degree n as a Bezier curve of degree n+1 without changing its shape. The new control points are:

P_i’= (i/(n+1))P_i-1 + (1-i/(n+1))P_i for i = 0, 1, …, n+1

Where P_-1 and P_n+1 are defined as P₀ and P_n respectively.

Example: Elevating a Quadratic to Cubic

For a quadratic Bezier curve with control points [P₀, P₁, P₂], the elevated cubic control points are:

P₀’ = P₀
P₁’ = (1/3)P₀ + (2/3)P₁
P₂’ = (2/3)P₁ + (1/3)P₂
P₃’ = P₂

Exam Focus Areas

Bernstein Basis: Understanding and evaluating the basis functions
De Casteljau Algorithm: Implementation and geometric interpretation
Curve Properties: Understanding and applying the key properties
Curve Manipulation: Degree elevation, subdivision, joining curves
Surface Construction: Building and evaluating Bezier surfaces

Common Exam Questions

Analytical: Derive the Bernstein basis functions for degree n
Computational: Evaluate a Bezier curve at a specific parameter value
Geometric: Describe the effect of moving control points
Algorithmic: Trace through the De Casteljau algorithm steps
Application: Design a piecewise Bezier curve with specific continuity

Practice Problems

Implement the De Casteljau algorithm for a cubic Bezier curve
Find the derivative of a Bezier curve and evaluate it at a specific parameter
Perform degree elevation on a quadratic Bezier curve
Create a C¹ continuous piecewise Bezier curve from given control points

Challenge Problem

Design a piecewise cubic Bezier curve that passes through the points (0,0), (2,3), (5,1), and (7,4) with C¹ continuity, and derive the necessary control points.

Original lecture notes are available at: /files/CE7453/CE7453/03-BeizerTechniques-4slides1page(1).pdf

Share on

Twitter Facebook LinkedIn

Liao Chang