Projection of curves on B-spline surfaces using quadratic reparameterization

Yi-Jun Yang, Wei Zeng, Hui Zhang, Jun‐Hai Yong, Jean‐Claude PaulGraphical 2010 · DOI

TL;DR

This paper introduces a novel method for projecting curves onto B-spline surfaces, ensuring the projected curves lie exactly on the surface. By employing quadratic reparameterization and approximating curves with hyperbolae, the algorithm significantly reduces the number of subdivisions needed compared to previous methods, while maintaining desirable continuity properties and computational efficiency.

What Problem Does This Paper Address?

In computer-aided design (CAD) and manufacturing, curves lying on free-form surfaces are crucial for tasks like surface blending, intersection, and tool path generation. Ideally, these curves should lie precisely on the surface to avoid gaps and ensure geometric integrity. Existing methods often fall into two categories: computing exact curves, which can be computationally expensive and numerically unstable due to high degrees, or approximating curves. While approximation methods reduce complexity, many fail to guarantee that the projected curves lie entirely on the surface. This can lead to gaps between surfaces, which is problematic for applications like surface blending where new surfaces connect existing ones along these curves. The paper aims to bridge this gap by providing an efficient approximation method that guarantees curves lie on the surface and possess good continuity.

Methods

The core of the paper's contribution lies in its "hyperbola approximation method" combined with "quadratic reparameterization."

  1. Bézier Surface Decomposition: The B-spline surface is first divided into Bézier patches using knot insertion.
  2. Domain Curve Approximation: The curve, initially defined in the parameter domain of the surface, is approximated by hyperbolic curves. This is a key departure from previous "polyline approximation" methods.
  3. Quadratic Reparameterization: Instead of simple linear transformations, the paper uses quadratic reparameterization of Bézier surfaces. This introduces additional free parameters, allowing for more flexible transformations of the parameter lines. Crucially, this reparameterization can transform hyperbolic curves in the original parameter domain into simpler line segments (iso-parameter curves) in the reparameterized domain.
  4. Subdivision Control: The domain curve is subdivided iteratively. This subdivision is driven by two criteria:
  5. Hausdorff Distance: The distance between the projected hyperbolic curve and the original curve is kept below a user-specified tolerance ($\epsilon_D$).
  6. Continuity ($\epsilon_r$-G¹): The tangent discrepancy between adjacent projected curves is controlled by an angle tolerance ($\epsilon_r$). This ensures smooth transitions between curve segments.
  7. Projection: The approximated hyperbolic curves from the original parameter domain are then mapped onto the Bézier surface using the iso-parameter curves of the quadratically reparameterized surface.

The paper also provides explicit derivations for the coefficients of quadratically reparameterized Bézier surfaces, extending previous work.

Datasets

Not discussed in the paper. The paper focuses on algorithmic development and demonstrates its method with synthetic examples and standard geometric models (a face, an ear).

Key Insights and Ideas

  • Hyperbolae as Approximators: Using hyperbolic curves to approximate domain curves is more effective than simple polylines, especially when combined with reparameterization. This allows for better approximation with fewer segments.
  • Quadratic Reparameterization is Key: The introduction of quadratic reparameterization is a significant advancement. It provides the flexibility to transform complex domain curves (like hyperbolae) into simpler forms in a new parameter space, which can then be easily mapped back to the surface. This is crucial for ensuring the projected curves lie on the surface.
  • Reduced Subdivisions: The combination of hyperbola approximation and quadratic reparameterization leads to a substantial reduction in the number of subdivisions required to meet distance and angle tolerances, compared to polyline methods. This directly translates to simpler and more efficient representations.
  • Guaranteed Surface Adherence: The method explicitly ensures that the projected curves lie on the B-spline surface, a critical requirement for many CAD applications that was not consistently met by prior approximation techniques.

Key Results

  • Reduced Subdivisions: Tables 1, 2, 3, 4, and 5 consistently show that the hyperbola approximation method requires significantly fewer segments (subdivisions) than the polyline approximation method for comparable distance and angle tolerances. For instance, in Table 1, for a distance tolerance of $1 \times 10^{-5}$, the hyperbola method uses 230 segments, while the polyline method uses 2118.
  • Comparable or Better Performance: The number of subdivisions is comparable to or better than degree reduction methods, while guaranteeing curves lie on the surface, which degree reduction methods do not always achieve.
  • Computational Efficiency: The processor time for the hyperbola approximation method is comparable to degree reduction methods and is efficient enough for real-time CAD applications.
  • ε-G¹ Continuity: The algorithm successfully generates $\epsilon$-G¹ continuous curves, which is sufficient for many practical applications.

Limitations and Future Work

  • Computational Cost of Reparameterization: While the final projected curves are simpler, the quadratic reparameterization step itself can be computationally intensive, though the paper claims it's comparable to other methods.
  • Generalization to Higher-Order Continuity: The paper focuses on $\epsilon$-G¹ continuity. Future work could explore achieving higher-order continuity (e.g., G²).
  • Handling Complex Surface Geometries: While demonstrated on standard surfaces, exploring the method's robustness on highly complex or degenerate B-spline surfaces could be beneficial.
  • Interactive Control: While tolerances are user-specified, more intuitive interactive tools for guiding the approximation process could be explored.

Summary updated

BibTeX
@inproceedings{yang2010projection,
  author = {Yi-Jun Yang and Wei Zeng and Hui Zhang and Jun‐Hai Yong and Jean‐Claude Paul},
  title = {{Projection of curves on B-spline surfaces using quadratic reparameterization}},
  booktitle = {Graphical},
  year = {2010},
  doi = {10.1016/j.gmod.2010.08.001},
}
Figure