Research On Some Basic Algorithms Of Computer Graphics

This paper researches the basic algorithms of Computer Graphics including the algorithms of an efficient algorithm for polygon clipping and pixel-level algorithm for generating Archimedes and ivolute curve.Polygon clipping is more often used than line clipping in practice, so it is the main subject in clipping research now. This paper presents an efficient algorithm for polygon clipping which processes general polygons. Firstly, singly linked lists are used as the data structure of this algorithm rather than doubly linked lists or trees as other algorithms use, so less memory space and running time are required. Secondly, the relationship between the entry and exit points on the two polygons is found and argumentation, which, with the reasonable operations on the lists, reduces the times that the lists are traversed and allows the polygon to be input clockwise or counterclockwise. Lastly, a new efficient technique for finding and computing intersection points is presented. As we know that finding and computing of intersection points is a main procedure, it makes the speed of the algorithm more higher. At the end of this paper, the new algorithm is compared with the existing algorithms and the result shows that it uses less memory space and has higher speed than others. This algorithm can be used to calculate not only intersection (clipping) but also set-theoretic differences and union of two polygons.With the widely use of raster display, pixel-level algorithm becomes a research hotspot of basic algorithms of Computer Graphics now. Since pixel-level contrapose pixel coordinate, trigonometric function must be used to translate polar coordinates to pixel coordinate when the curve is described by polar coordinate. So research is very little on algorithms for generating this sort of curve by now. This paper develops iterative formula of sine and cosine function in document[40], and presents new pixel-level algorithms forgenerating Archimedes and involute curves which are widely used in engineering. In each iteration, no trigonometric function is used and only two multiplications are required. By taking the advantage of symmetry, only the points in one octant are need to be generated. Furthermore, the error is no more than 2/2 pixel unit.