Techniques for modeling a high-quality B-spline curves by S-polygons in a float format

This article proposes a technique for the geometrically stable modeling of high-degree B-spline curves based on S-polygon in a float format, which will allow the accurate positioning of the end points of curves and the direction of the tangent vectors. The method of shape approximation is described with the purpose of providing geometrical proximity between the original and approximating curve. The content of the notion of a "harmonious, regular form" of B-spline curve’s S-polygon in a float format is revealed as a factor in achieving a high-quality of fit for the generated curve. The expediency of the shape modeling method based on S-polygon in a float format at the end portions of the curve for quality control of curve modeling and editing is substantiated. The results of a comparative test are presented, demonstrating the superlative efficacy of using the Mineur-Farin configuration for constructing constant and monotone curvature curves based on an S-polygon in a float format. The findings presented in this article confirm that it is preferable to employ the principle of "constructing a control polygon of a harmonious form (or the Mineur-Farin configuration) of a parametric polynomial" to a B-spline curve’s S-polygon in a float format, and not to a B-polygon of the Bézier curve. Recommendations are given for prospective studies in the field of applying the technique of constructing a high-quality B-spline curves to the approximation of log-aesthetic curves, Ziatdinov’s superspirals, etc. The authors of the article developed a technique for constructing smooth connections of B-spline curves with ensuring a high order of smoothness of the composite curve. The proposed techniques are implemented in the FairCurveModeler program as a plug-in to engineering CAD systems.

Mineur et al. [1] and Farin [2] proposed a method for constructing Bézier curves with a monotone change in curvature, based on the construction of the Bézier polygon (also known as B-polygon) with a monotonic change in the control polygon legs at fixed angles between the legs. The error in this method was recently demonstrated [18], although this fact was known a decade ago to one of our Japanese colleagues, Norimasa Yoshida.

In this paper, the aforementioned method adapts to the construction of B-spline curves with monotone curvature and the application of the S-polygon with the Mineur-Farin configuration. A technique for modeling a curve with an S-polygon in a float format is proposed, which allows for the precise positioning of the end points of the curve and the direction of the tangents. More detailed equivalence parameters for the two curves, such as the similarity of the m-level curvature and the similarity of the m-level curvature of torsion, are introduced. In addition, a method for approximating analytic curves with the equivalence of curvature and curvature of torsion to the mth level is proposed.

Modern CAD systems use a method of modeling class A curves using S-polygons of high-degree NURBS curves. To model closed curves, the S-polygon is used in a float format, and the closed format of the S-polygon is used for non-closed curves. Based on the configuration of the S-polygon in a float format, the quality of the modeled curve is easily judged. The harmonious, regular form of the S-polygon in a float format of the B-spline curve allows us to ensure high quality in the generated curve (hereinafter in this article we will clarify the concept of harmony of the S-polygon shape). Using a closed S-polygon is dictated by the need for precise positioning of the end points of the curve and the directions of the tangent vectors at the end points. The end portions of the closed S-polygon coincide with the initial portions of the B-polygons of the end segments of the curve, which allows precise positioning of the end points and directions of the tangent vectors at these points. However, using an S-polygon in a closed format causes instability in the curve modeling at the end portions of the curve.

The Cox-de Boor algorithm [4, 5] using the format of the representation of the B-spline curve with an S-polygon in a float format is numerically stable, since it uses a sequence of operations dividing the segment into a given ratio. In addition, the operations of calculating points and differential characteristics of the curve are uniform on any segment. Obviously, for the best approximation of the circular arc, the segment of the B-spline curve of the vertex of the S-polygon in a float format must be uniformly chosen on the circle. We construct an S-polygon in a float format of a segment of a B-spline of the ninth degree along the vertices of a regular dodecagon inscribed in a circle with a radius of R = 10. The point of the largest deviation of the evolute of the curve from the center (0, 0) of the circle is the point with the coordinates (0.000000015321, 0.000000057206).

Transformations of the control polygon formats of B-spline curves and Bézier splines are performed using BS and SB algorithms [6-8]. In [9] NBS and NSB algorithms of transformations for rational splines are proposed. SB (NSB) algorithms for the transition from the format of the S-polygon B-spline to the format of the generalized B-polygon of the Bézier spline are stable, since they contain only operations of dividing the segments into a given ratio. BS (NBS) algorithms are less stable, so they contain extrapolation operations of a segment in a given ratio. The algorithms for converting S-polygon formats of multi-segment splines partially contain the operations of BS (NBS) and SB (NSB) algorithms.

Fig. 1 shows the segment of the B-spline curve of the ninth degree associated with the S-polygon in a float format and the closed S-polygon coinciding with the B-polygon of the Bézier curve of the ninth degree.

The vertices of the closed S-polygon (i.e., the B-polygon) do not lie on the circle. The legs of the S-polygon do not have the same length (the lengths of the legs are 0.518838, 0.519949, 0.520746, 0.521227, 0.521387, ...). The angles between the legs are also not equal: in radians they are 0.0653566, 0.0654361, 0.0654898, 0.0655169, ...). At the same time, it is this configuration that provides a high-precision approximation of the circular arc with an accuracy of 5.92221×10-8. 

In modern CAD systems for modeling class A curves, B-splines with S-polygons in closed format are used. It is impossible to draw a closed S-polygon with the same configuration as in Fig. 2 to approximate a circular arc with the same level of accuracy. The difficulty of ensuring proper quality at the end portions is emphasized in the guidelines for modeling class A curves in CAD systems.

An S-polygon in a float format of a B-spline curve of degree m can be used for quality control of modeling and for editing a curve [10].

Differential characteristics of the spline are determined by the divided differences of the S-polygon in a float format [5, 11]. A harmonious, regular form of an S-polygon in a float format of a B-spline curve of degree m must satisfy the second order isogeometry and regularity of an S-polygon of order m-1 [9]. Such a configuration of an S-polygon can be achieved by providing the required law of variation of the discrete approximation of the tangent vectors and curvature [9], as computed from the central divided differences of the S-polygon of the first and second order. More stringent requirements to the harmonicity of the polyline configuration can be introduced if one takes into account the condition that portions of a modeled or approximated curve with a monotone change in curvature are determined by segments of a polygonal line with a monotonous variation of the discrete curvature, as, for example, segments of a polygonal line with a Mineur-Farin configuration.

Modeling and editing of the high-degree B-spline curve at the end portions of the curve by means of a closed S-polygon is extremely unstable. Even simple rounding of the coordinates of a closed S-polygon’s vertices can cause distortion of the shape. For example, let the arc of a B-spline curve of the ninth degree be given by a convex S-polygon in a float format (see Figure 1), built on the vertices of a dodecagon inscribed in a circle of radius R = 10. Rounding the coordinates of the second vertex of the closed S-polygon (see Fig. 1) from the value (-1.807034341228000, 8.748581800695999) to the value (-1.807, 8.748) causes a significant change in the shape of the curve and an unpredictable change in the shape of the S-polygon in a float format. The vertices of the original S-polygon (-7.071, -7.071), (-9.659, -2.588), (-9.659, 2.588), etc. have changed to (-83.972, 1295.780), (-8.274, -26.046), (-9.832, 5.520), and so on. The error of circular arc approximation increases from 5.92221×10-8 to a value of 3.06354×10-1.

It is the stability of shaping with an S-polygon in a float format at the end portions of the curve that makes this method preferable.

The uncertainty of positioning the end points of the curve and the values ​​of the tangent vectors is eliminated by employing a technique which consists of the following steps:

1. Construct the S-polygon of a curve in a float format of the proper shape.

2. Control the positions of the end points and the tangent directions when formatting the closed S-polygon.

3. Define the position difference vector (the vector determined by the difference of the actual end point versus the desired end point) and the difference angle of the direction (the angle between the actual tangent direction and the required one).

4. Switch the current formatting to that of S-polygon in a float format.

5. Eliminate misalignment in the position of the end points, requiring translation of the m terminal vertices of the S-polygon by the magnitude of the difference vector in the direction of decreasing the error value.

6. Eliminate the difference in the direction of the tangent vectors, requiring rotation of m end vertices of the S-polygon by the amount of the difference angle in the direction of decreasing the difference value.

7. Edit the changed configuration of the S-polygon in a float format until it reaches a harmonious, regular shape. Repeat the position control on the closed S-polygon and edit the S-polygon in a float format until a harmonious, regular form of the S-polygon in a float format and the accuracy of the closed S-polygon position are obtained.

[1] Mineur, Y., Lichah, T., Castelain, J.M., Giaume, H. A shape controlled fitting method for Bézier curves. Computer Aided Geometric Design 15 (9), 1998, pp. 879-891.

[2] Farin, G. Class A Bézier curves. Computer Aided Geometric Design, 23, 2006, pp. 573-581.

[3] Welters, H.J, Farin, G. Geometric curve approximation. Computer Aided Geometric Design, 14, 1997, pp. 499-513.

[4] Cox M. G. The numerical evaluation of B-splines, Journal of the Institute of Mathematics and its Applications, 10, 1972, pp. 134-149.

[5] De Boor, C., et al. A practical guide to splines. Vol. 27. New York: Springer-Verlag, 1978.

[6] Boehm, W. Cubic B-spline curves and surfaces in computer-aided geometric design. Computing, 19, 1977, pp. 29-34.

[7] Sabloniere, P. Spline and Bézier polygons associated with a polynomial spline curve. Computer-Aided Design, 10 (4), 1978, pp. 257-261.

[8] Prautzsch, H., Boehm, W., Paluszny, M. Bézier and B-spline techniques. Springer, 2002, 190 p.

[9] Muftejev, V.G., Romanyuk, A.N., Mardanov, A.R., Farkhutdinov, I.M. Geometrically stable modeling of NURBS curves and surfaces of arbitrary degrees. Applied Geometry, 11, pp. 19-77.

[10] Muftejev, V.G., Mardanov, A.R., Romanyuk, A.N., Turta, V.G., Farkhutdinov, I.M. Program of isogeometric modeling of high-quality curves. Web-application for CAD systems. Proceedings of the international scientific and technical internet-conference on computer graphics and image recognition. Vinnytsa, Ukraine. 2012. pp. 127-139.

[11] Golovanov, N.N. Geometric modeling. Moscow, Fizmatlit, 2002 (in Russian).

[12] Ziatdinov, R., Muftejev, V.G. On a class of plane curves with equal curvatures of the n-th level. In Systems of design, technological preparation of production and management of the life cycle of an industrial product (CAD/CAM/PDM - 2017). Institute of Control Problems, Russian Academy of Sciences. p.133.

[13] Yoshida, N., Saito, T. Interactive aesthetic curve segments. The Visual Computer, 22 (9-11), 2006, pp. 896-905.

[14] Miura, K.T. A general equation of log-aesthetic curves and its self-affinity. Journal of the Japan Society for Precision Engineering, 72 (7), 2006, pp. 857-861.

[15] Ziatdinov, R. Family of superspirals with completely monotonic curvature given in terms of Gauss hypergeometric function. Computer Aided Geometric Design, 29 (7), 2012, pp. 510-518.

[16] Muftejev, V.G., Ziatdinov, R. Functionality and aesthetics of curves in industrial design: a multi-criteria approach to assessing the quality of shapes in CAD systems of the future. Vestnik Mashinostroyeniya, Issue 7, 23-27, 2018 (in Russian).

[17] FairCurveModeler app for AutoCAD v. 2019 https://apps.autodesk.com/ACD/en/Detail/Index?id=4526969846340104233&appLang=en&os=Win32_64&mode=preview&autostart=True&loginRequired=True

[18] Wang, A., Zhao, G. Counter examples of “Class A Bézier curves”. Computer Aided Geometric Design, 61, 2018, pp. 6-8.