Typical curve with G1 constraints for curve completion

Chuan He, Gang Zhao, Aizeng Wang, Fei Hou, Zhanchuan Cai, Shaolin Li

Abstract

Filling gaps in curves while maintaining smoothness is a fundamental problem in computer-aided design (CAD) and computer vision. This paper proposes using "typical curves"—a subset of Bézier curves with monotonic curvature—for G1 curve completion. This approach provides a NURBS-compatible, computationally efficient alternative to the traditional Euler spiral. We introduce the Angle Sign Change (ASC) condition to guarantee solution existence and describe an optimization algorithm that adjusts curve degree to meet boundary conditions.

Introduction

In CAD and computer vision, the process of connecting two points with a smooth transition that matches specific directions (tangents) at the endpoints is known as G1 interpolation. While humans intuitively complete shapes—such as the edges of an occluded square—formalizing this for computers is mathematically challenging.

The "gold standard" for aesthetically pleasing curves is the Euler spiral, characterized by a linear change in curvature. However, Euler spirals are defined by transcendental functions, making them computationally expensive and incompatible with Non-Uniform Rational B-Splines (NURBS), the industry standard for CAD software. Standard polynomial curves like Bézier curves are NURBS-compatible but often suffer from "wiggles" or non-monotonic curvature, which engineering standards define as "unfair."

Methods: The Typical Curve Framework

The authors address these issues by leveraging Typical Curves, a specific subset of planar Bézier curves. The defining characteristic of a typical curve is that its control edges follow a geometric progression: each edge is a scaled and rotated version of the previous one ($V_i = s \cdot R_\theta \cdot V_{i-1}$). This structure inherently guarantees monotonic curvature, meaning the curvature only increases or decreases without oscillating.

Mathematical Framework and ASC Condition

The G1 interpolation problem is converted into a system of nonlinear equations. A key contribution is the Angle Sign Change (ASC) condition, a sufficient condition that allows the system to check before calculation whether a valid typical curve solution exists for a given set of boundary constraints.

The G1 interpolation problem involves transforming endpoint positions and tangents into a canonical coordinate system to solve for the curve parameters.

The authors use an interior point method to solve for the scale factor ($s$) and the length of the initial control edge ($\|V_0\|$). The algorithm iteratively increases the degree of the curve ($k$) until a solution satisfying the monotonicity constraints is found.

Evaluation and Results

The algorithm was evaluated using synthetic geometric constraints and visual completion tasks. It successfully completes complex curves with sharp tangent angles, producing smooth, "C-shaped" transitions that appear natural to the human eye.

The Kanizsa Triangle serves as a benchmark for visual completion, demonstrating the algorithm's ability to reconstruct occluded boundaries.

Practical applications were demonstrated through real-world image proxies, such as completing the occluded boundaries of a banana or overlapping leaves. Computational results show that the algorithm finds precise values for the scale factor $s$ and rotation angle $\theta$, typically requiring degrees ranging from $k=5$ to $k=20$ for highly curved completions.

Discussion and Future Work

By restricting the search space to typical curves, the method ensures "fairness" through monotonicity while maintaining NURBS compatibility. This allows the output to be integrated directly into modern CAD environments without the approximation errors associated with Euler spirals.

Currently, the method is limited to "C-shaped" curves without inflection points and is restricted to 2D planes. Future work aims to extend this framework to 3D curves and G2 (curvature) continuity, which is essential for high-end manufacturing like automotive body design.

Summary updated

Abstract

This paper presents a novel algorithm for planar G1 interpolation using typical curves with monotonic curvature. The G1 interpolation problem is converted into a system of nonlinear equations and sufficient conditions are provided to check whether there is a solution. The proposed algorithm was applied to a curve completion task. The main advantages of the proposed method are its simple construction, compatibility with NURBS, and monotonic curvature.
BibTeX
@article{he2021typical,
  author = {Chuan He and Gang Zhao and Aizeng Wang and Fei Hou and Zhanchuan Cai and Shaolin Li},
  title = {{Typical curve with G1 constraints for curve completion}},
  journal = {Vis. Comput. Ind. Biomed. Art},
  year = {2021},
  doi = {10.1186/s42492-021-00095-9},
}
Figure