The process of filling the interior region of a polygon is known as polygon scan conversion. Whereas the standard approach requires two data structures, a sorting procedure and is device-dependent [1], the critical points method described herein is easy to implement, uses less space and is fast [2]. Assume the polygon has no intersecting edges and that its vertices are represented by two cyclic arrays X and Y. The scan conversion algorithm begins with the Build_CR( ) procedure which determines the set CR of critical points of the polygon. A critical point is a vertex whose y coordinate is either a local minimum or is a representative of a set of consecutive vertices that together form a local minimum. After Build_CR( ), the active edge list (AEL) is initialised to empty. From every critical point whose y value is less than scanline S, each of the two polygon edges ascending from it is followed until either edge turns down before reaching S or it passes S. If the edge turns down, it is deleted from the AEL, otherwise a new element is inserted into the AEL. Each AEL element contains The entire algorithm for the critical points method is shown below, as pseudocode, where c is the number of critical points and CR is an array of critical points. It is assumed that procedures Insert( ) and Delete( ) are available for the AEL and that Paint( ) is available for drawing horizontal lines between alternate pairs of AEL elements. [2] Gordon, D., M.A. Peterson, and R.A. Reynolds, ‘Fast Polygon Scan Conversion with Medical Applications,’ IEEE Computer Graphics and Applications, 14(6):20-27, November 1994 [2] Catmull, E., and A.R. Smith, ‘3-D Transformations of Images in Scanline Order,’ Computer Graphics, SIGGRAPH 1980 Proceedings, 279-285 Mapping a set of parameters onto a surface of a three dimensional scene enhances the realism of the image. Parameters include surface normal vectors, transparency, specularity, and illumination [1]. The most widely known and applied surface parameter is colour. Mapping of this sort is known as texture mapping. For scenes viewed with perspective projections, proper foreshortening of texture images is achieved through projective mapping: a projection of one plane through a point onto another plane. The source and destination points are expressed in terms of homogenous coordinates, a system used extensively in projective geometry. A point in destination space is represented by the homogenous vector pd = (x’, y’, w) where w is an arbitrary nonzero number. To recover the actual coordinates we simply divide by the homogenous component as in (x, y) = (x’/w, y’/w). A point in source space is denoted by ps = (u’, v’, q). computing homogeneous texture coordinates The transformation of ps to pd, known as forward projective mapping, is easily written in homogenous matrix notation: where i = 1 without loss of generality. Given texture coordinates (u, v) the screen coordinates are found by computing an optimisation Moreton and Heckbert realised a far more efficient alternative than computing the homogeneous texture coordinates as described above [3]. Moreton observed that a given parameter p suitable for linear interpolation across a polygon, in screen space, can be found by dividing the parameter by screen w, linearly interpolating p / w, and dividing the quantity p / w by 1 / w at each pixel to recover the desired parameter. The algorithm can be generalised as such [3] parameter interpolation If the polygon is a triangle, interpolation of texture parameters can be accomplished as follows. In three dimensional space, a parameter p varies linearly across a triangle such that [2] Heckbert, P.S., Fundamentals of Texture Mapping and Image Warping, UCB/CSD 89/516, Computer Science Division, University of California at Berkeley, 19-20, June 1989 [3] Heckbert, P.S., and H.P. Moreton, Interpolation for Polygon Texture Mapping and Shading, Department of Electrical Engineering and Computer Science, University of California at Berkeley, 1991 [4] Maillot, J., H. Yahia, and A. Verroust, ‘Interactive Texture Mapping,’ Computer Graphics, SIGGRAPH 1993 Proceedings, 27-34 [5] Litwinowicz, P., and G. Miller, ‘Efficient Techniques for Interactive Texture Placement,’ Computer Graphics, SIGGRAPH 1994 Proceedings, 119-122 Source.