Fast Automatic Knot Placement Method for Accurate B-spline Curve Fitting. (November 2020)

• Record Type: Journal Article
• Authors: Yeh, Raine; Nashed, Youssef S.G.; Peterka, Tom; Tricoche, Xavier
• Is Part Of: Computer aided design. Volume 128(2020)
• Publication Date: 2020-11
• Subjects: B-spline curve fitting -- Knot placement -- Knot optimization -- Smooth approximation; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2020.102905
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: The choice of knot vector has immense influence on the resulting accuracy of a B-spline approximation of a curve. However, despite the significance of this problem and the various solutions that were proposed in the literature, optimizing the number and placement of knots remains a difficult task. This paper presents a novel method for the approximation of a curve by a B-spline of arbitrary order, which automatically determines a knot vector that achieves high approximation quality. At the core of our approach is a feature function that characterizes the amount and spatial distribution of geometric details in the input curve by estimating its derivatives. Knots are then selected in such a way as to evenly distribute the feature contents across their intervals. A comparison to the state of the art for a wide variety of curves shows that our method is faster and achieves more accurate reconstruction results, while typically reducing the number of necessary knots. Graphical abstract: Highlights: We automatically compute a set of knots that enable low error approximation for smooth datasets. Our algorithm is fast, run-time scaling linearly with the input data size. We can give a good estimate of the number of knots needed for a given error threshold.