The Research And Implement Of Symmetrical Eight-Step Line-Generating Algorithm And Bezier Curves Degree Reduction Algorithm

The line is the basic element in generating graphics. So line drawing is a fundamental task for raster graphics. The line scan conversion generating algorithm is a very important and fundamenatal algorithm in Computer Graphics (CG) and Computer Aided Design (CAD), Visualization in Scientific Computing (VISC), Virtual Reality and Computer Animation.The efficiency of generating graphics and showing graphics is affected directly by the performance of the line generating algorithm. Therefore, accelerating the speed of the traditional line drawing algorithm has important actual significance. Industrila circle and CAGD academic circles are interested in Bézier curve and Bézier surface,because they are one of the most common use curve and surface in geometry model. Considering the time complexity of algorithm, the degree of Bézier curve and Bézier surface must be reduced when generating curve and surface.So, to study the degree reduction transform of curve is also impantant.Both line generating algorithm and Bézier curve degree reduction algorithm are analysed and studied in this paper.About the line generating algorithm, we present a new line drawing algorithm named eight-step incremental generation of lines by analyzing the relationship between generation models of line and the linear slope. The algorithm can draws four pixels on the same time, and it can draw eight pixels as well considering the symmetry of line generation. As only addition, subtraction and left shift operation of integer are used in this algorithm, the speed has been improved greatly, and it is easy to be implemented by hardware. Compare with the Bresenham algorithm, the Eight-step algorithm can save 70% decision times and 75% iterative times. So the speed of generating lines of the Eight-step algorithm is almost 3 times of that of the Bresenham algorithm.By using the geometric attributes and degree escalation formula of Bézier curve, the adaptive algorithm to reduce a biquadratic Bézier curve to piecewise quadratic Bézier curves which based on curve subdivision points is present. Both the error calculation of degree reduction and the adopted process while unsmooth occur on the division points are discussed, too. By the research of degree reduction formula of Bézier curve , the adaptive algorithm to reduce a biquadratic Bézier curve to quadratic Bézier curves acquires improvement. In addition of being the same as traditional algorithm of degree reduction, this algorithm not only owes the feature of geometric visualization, but also need not to calculate the left degree reduction nor right degree reduction.This algorithm has such advantages as computation simple and high stability.