Incremental algorithms for the design of triangular -based spline surfaces

Spline surfaces consisting of triangular patches have a number of advantages over their rectangular counterparts, such as the ability to handle surfaces of arbitrary topology. Designing and interpolating triangular-based spline surfaces has been a research interest in the field of CAGD for some years. Algorithms for designing triangular splines with local flexibility was left by Ramshaw [Ram87] as an open problem in 1987. Although many approaches have been proposed in the years since, none could quite achieve the elegance and flexibility of the algorithms for designing rectangular splines surfaces. The difficulty with triangular spline surfaces is that unlike tensor-product surfaces, the familiar B-spline curve framework does not carry over. We present a new de Boor-like algorithm to design triangular C1-splines based on general triangulations of the parameter plane. Through careful analysis of the continuity constraints based on polar forms, we discovered a way of choosing strategic control points, so that the remaining control points are computed using a simple propagation scheme. Due to its local nature, the algorithm can be easily made incremental. The algorithm operates in linear time and handles holes and sharp corners easily. Preliminary results also suggest that the algorithm can be extended to C2-splines. Due to the amount of freedom our algorithm leaves around the vertex regions, it is readily extendable to handle interpolation. However, fairing methods are needed to improve the resulting surface quality. We have also extended our algorithm to handle closed surfaces based on triangulated polyhedra. Parametric data fitting is achieved through G1 triangular surfaces. We provide a new rigorous definition of a piecewise polynomial surface based on a triangulated polyhedron. We also define a new kind of geometric continuity associated with such a polynomial surface, the AGk-continuity