Fast Automatic Knot Placement Method for Accurate B-spline Curve Fitting. (November 2020) - Yeh, Raine; Nashed, Youssef S.G.; Peterka, Tom; Tricoche, Xavier
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.