The Research Of The Bounds On The Deviation Between Curves And The Corresponding Control Polygons

The technology of bounding box plays an important role in the applied area of CG, CAGD and computer animation. With the popular application of this technology, especially in the aspects of computing the intersection of two curves and two surfaces, the intersection between beam and curves and surfaces, the requirement of lessening bounding box is becoming more and more urgent. Based on the study of the bounds on the deviation between curves and surfaces and the corresponding control polygons and nets, a new algorithm is presented to reduce the bounds on the deviation between the former curves and the corresponding control polygons.In this paper conception and current research of bounding box is firstly introduced, and necessity of the research about the bounds on the deviation between curves and surfaces and the corresponding control polygons and nets is pointed out.In the second chapter brief introduction about the development and basic conceptions of curves and surfaces is presented. Meanwhile, it is illustrated that characteristic of curves and surfaces is one of the important foundations in the research of the bounds on the deviation between curves and surfaces and the corresponding control polygons and nets.In chapter 3, briefly introduce the concepts of the differences and the vector norms. Then we introduce that the maximal distance between a Bezier segment and its control polygon is bounded in terms of the differences of the control point sequence and a constant that depends only on the degree of the polynomial. The constants derived here for various norms and orders of differences are the smallest possible. We present the bounds on the deviation between univariate polynomials, tensor product polynomials, univariate splines, and tensor product splines and the corresponding control polygons and nets. The bounds on the Lp-norm are given in terms of the maximal absolute second differences of the control point sequence.In chapter 4, we analyze the differences of the bound by using the maximal absolute second difference of the control point sequence and the corresponding constant. Thebound in terms of the maximal absolute second difference of the control points is a sharp upper bound for the Hausdorff distance between the control polygon and the curve segment, and it is optimal in most case. In the case of the bounds on the deviation between cubic Bezier curves and the corresponding control polygons, we analyse the effects of the bounds by different norm and the shape of curve. The comparison of magnitude of bounds as to different norm was given if the control points fixed. The selection of appropriate norm space was also provided to minimize the bounds between the curves and the corresponding control polygons according to diverse curve shape. At last, on the basis of the L--norm space a new algorithm is presented, that creates new compacter bounds than the old ones, the conclusion is also illustrated.