Evaluation of Gauss-Legendre curves

1. Problem Statement

Gauss-Legendre (GL) curves are a class of polynomial parametric curves introduced recently in Computer-Aided Geometric Design (CAGD). Unlike Bézier curves, GL curves exhibit superior shape control properties, closely following their control polygons even at high degrees. However, their practical application has been hindered by the lack of efficient evaluation algorithms.

The core challenges identified are:

• Complex Definition: GL curves are defined via integrals of Legendre polynomials involving their roots (zeros), making direct evaluation computationally expensive and numerically unstable.
• Lack of Algorithms: Previous literature defined the curves but did not provide methods for their efficient point-wise or multipoint evaluation.
• Computational Cost: Naive evaluation methods are too slow for real-time rendering or high-degree applications, where $n$ (degree) and $M$ (number of evaluation points) can be large.

2. Methodology

The authors propose a two-stage methodology to solve the evaluation problem:

1. Derivation of New Representations: They transform the definition of GL polynomials ($F^n_i$) from integral forms into algebraic expansions using specific polynomial bases.
2. Algorithmic Implementation: They utilize these new representations to design recursive and multipoint evaluation algorithms with optimized computational complexity.

A. New Polynomial Representations

The paper derives representations for GL polynomials in three distinct bases:

• Shifted Power Basis: Expanding $F^n_i(t)$ in terms of $(t+1)^k$. The authors derive recurrence relations for the coefficients $b^{(i)}_k$ to express the integral of the Legendre polynomial divided by $(x-\tau_i)$.
• Legendre Basis: Using the Christoffel–Darboux formula, they express $F^n_i(t)$ as a linear combination of standard Legendre polynomials $P_k(t)$.
• Symmetric Jacobi Basis: They derive expansions involving derivatives of Legendre polynomials (which are related to symmetric Jacobi polynomials $P^{(1)}_k$). This representation is highlighted as particularly suitable for numerical stability.

B. Evaluation Algorithms

Based on these representations, the authors propose two main evaluation strategies:

1. Single-Point Evaluation:

   • Approach 1 (Shifted Power): Uses Horner's scheme on the power basis expansion.
   • Approach 2 (Jacobi/Legendre): Uses the Clenshaw algorithm, a stable recursive method for evaluating orthogonal polynomial series.
   • Symmetry Optimization: Both approaches exploit the symmetry property $F^n_i(-t) = -F^n_{n-i}(t)$ to reduce the number of calculations by roughly half.
   • Complexity: $O(n^2 + dn)$ for a curve of degree $n$ in $d$ dimensions.

2. Multipoint Evaluation:

   • The authors observe that for rendering, $M$ (number of points) is typically much larger than $n$.
   • Strategy: Precompute the coefficients of the GL curve in the chosen basis (e.g., converting the control points $W_i$ into basis coefficients $q_k$ or $s_k$). This precomputation takes $O(n^2)$.
   • Evaluation: Evaluate the resulting polynomial at $M$ points using Horner's scheme or Clenshaw's algorithm. This takes $O(Mn)$.
   • Total Complexity: $O(Mn + n^2)$, which simplifies to $O(Mn)$ when $M \gg n$. This is a significant improvement over the naive $O(Mn^2)$ approach.

3. Key Contributions

• New Algebraic Forms: The paper provides the first explicit expansions of GL polynomials and their derivatives in shifted power, Legendre, and symmetric Jacobi bases.
• Efficient Algorithms:
  • Proposed $O(n^2 + dn)$ algorithms for single-point evaluation.
  • Proposed $O(Mn + dn^2)$ algorithms for multipoint evaluation, making high-degree GL curve rendering feasible.
• Numerical Stability Analysis: The authors rigorously tested the numerical behavior of different bases. They identified that while the Shifted Power basis is the fastest computationally, it suffers from severe numerical instability (loss of precision) for degrees $n \gtrsim 20$ due to large alternating coefficients.
• Optimal Basis Selection: They demonstrate that the Symmetric Jacobi and Legendre bases offer a superior trade-off, maintaining high numerical stability even for high degrees ($n=100$) while retaining near-optimal speed.

4. Results

The authors conducted numerical experiments using Python (NumPy/SciPy) to validate their methods:

• Accuracy: For degrees up to 50, the Symmetric Jacobi and Legendre basis methods produced results identical to direct integral evaluation (within double precision limits). The Shifted Power basis diverged significantly for $n > 20$.
• Performance (Speed):
  • Shifted Power: Fastest but unstable for high $n$.
  • Symmetric Jacobi vs. Legendre: Both are highly efficient. For $n=100$, the Jacobi method took ~57 seconds to evaluate 5000 points on 100 curves, whereas the direct integral method exceeded time limits.
  • Comparison: The proposed methods are orders of magnitude faster than direct integration (e.g., for $n=50$, Jacobi took ~27s vs. ~7450s for direct integration).
• Scalability: The multipoint evaluation strategy successfully handled high-degree curves ($n=100$) with linear scaling relative to the number of evaluation points.

5. Significance

This work bridges the gap between the theoretical properties of Gauss-Legendre curves and their practical application in CAGD and computer graphics.

• Enabling High-Degree Curves: By providing stable, fast evaluation algorithms, the paper makes it feasible to use GL curves for high-degree modeling, where Bézier curves typically fail to maintain shape fidelity.
• Real-Time Rendering: The $O(Mn)$ multipoint evaluation complexity allows for the real-time rendering of GL curves, which was previously computationally prohibitive.
• Foundation for Future Work: The authors note that these representations lay the groundwork for future research into converting between Bernstein and Gauss-Legendre bases and constructing dual bases, which are crucial for approximation theory and surface fitting.

In conclusion, the paper transforms Gauss-Legendre curves from a theoretical curiosity into a practical tool for geometric modeling by solving the critical bottleneck of efficient and stable evaluation.