Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20CSC 480 / 580Computer GraphicsK. KirbyScan Conversion FillingScan-converting Lines :Line: y=mx + b (m= slope, b= intercept)bm1xAxB// What's WRONG with this?for ( int x= xA ; x <= xB ; ++x ){int y= round( m*x + b ) ;pixel( x, y ) ;}Scan-converting Lines: Getting the API right.xAxBvoid line( int xA, int yA, int xB, int yB );yAyBABxyx= xB  xA y= yB  yA DefineScan-converting Lines - Toward the Bresenham AlgorithmSpecial case: 0 < m < 1, x > 0 xx+1y+1y??At each step:x++ ;if ( – > +) y++ ;–+Let p = x ( – – + ). Then:At each step:x++ ;if ( p > 0 ) y++ ;update p ; “true line”imagine pixel centersat grid verticesCan we do this with simple all-int arithmetic? Yes!The Bresenham Algorithmvoid line( int xA, int yA, int xB, int yB )// Special case: shallow increasing slope.{ const int DX= xB - xA ; const int DY= yB - yA ; const int DP_FLAT= 2*DY ; const int DP_JUMP= DP_FLAT - 2*DX ; assert( 0 < DY && DY < DX ) ; int x= xA ; int y= yA ; int p= 2*DY - DX ; pix( xA, yA ) ; while ( x < xB ) { x++ ; if ( p > 0 ) { ++y ; p+= DP_JUMP ; } else p+= DP_FLAT ; pix( x, y ) ; }}initial values(derived in class)Scan-converting CirclesFor derivation:“Without loss of generality,”assume center is (0,0)void circle( int ixCenter, int iyCenter, int r ) ;rScan-converting Circles - 28-fold symmetrym > 1x++if ( p > 0 ) y-- ;Scan-converting Circles - 3??xk xk + 1yk yk - 1MFrom step k to step k+1Scan-converting Circles - 4??0 1rr - 1MStep 0.Stack-based Pixel Filling By Runs - 1seedStack-based Pixel Filling By Runs - 2Fill the scan lineStack-based Pixel Filling By Runs - 3Pushseeds for the next step rightmost left pixels, above & belowTrapezoid Filling – 1yloyhiTrapezoid Filling – 2yloyhifor ( int iy=iyLo ; iy <= iyHi ; ++iy ){ fillRow( ixLeft, ixRight, iy ) ; ixLeft += ???? ; ixRight += ???? ;}for ( int iy=iyLo ; iy <= iyHi ; ++iy ){ fillRow( ixLeft, ixRight, iy ) ; ixLeft += ???? ; ixRight += ???? ;}yxLxRPolygon Filling - 1yminymaxyPolygon Filling - 2a b c defghab cde fg h active edge list (AEL)yminymaxy 700300ix= 700 YHI = 300 INVSLOPE = -0.9 gPolygon Filling - 3class Edge// An edge record for the AEL in a filled-polygon function.{ public: // Constructors Edge( const CPoint& ptA, const CPoint& ptB ) : _x( min( ptA.x, ptB.x ) ) , _INVSLOPE( (double)( ptB.x - ptA.x ) / ( ptB.y - ptA.y ) ) , _YHI( max( ptA.y, ptB.y ) ) {} // Constant fields const int _YHI ; // the upper y coordinate of the edge const double _INVSLOPE ; // the inverse of the slope (= 1/m) // Inspectors int ix() const { return round( _x ) ; } bool operator<( const Edge& e ) const { return _x < e._x ; } // Mutators void update() { _x += _INVSLOPE ; return *this ; } private: // Variable fields double _x ;} ;class Edge// An edge record for the AEL in a filled-polygon function.{ public: // Constructors Edge( const CPoint& ptA, const CPoint& ptB ) : _x( min( ptA.x, ptB.x ) ) , _INVSLOPE( (double)( ptB.x - ptA.x ) / ( ptB.y - ptA.y ) ) , _YHI( max( ptA.y, ptB.y ) ) {} // Constant fields const int _YHI ; // the upper y coordinate of the edge const double _INVSLOPE ; // the inverse of the slope (= 1/m) // Inspectors int ix() const { return round( _x ) ; } bool operator<( const Edge& e ) const { return _x < e._x ; } // Mutators void update() { _x += _INVSLOPE ; return *this ; } private: // Variable fields double _x ;} ;Polygon Filling – 4 int main()// A quick demo of Edge and list<Edge>.{ list<Edge> ael ; // Put 3 edges on the list and sort it. ael.push_back( Edge( CPoint(10,10), CPoint(40,50) ) ) ; ael.push_back( Edge( CPoint(20,30), CPoint(25,70) ) ) ; ael.push_back( Edge( CPoint(40,10), CPoint(35,90) ) ) ; ael.sort() ; // Walk down the list and update its edges. for ( list<Edge>::iterator it= ael.begin() ; it != ael.end() ; ++it ) { cout << *it ; it->update() ; cout << ", after 1 update: " << *it << endl ; } return 0 ;}int main()// A quick demo of Edge and list<Edge>.{ list<Edge> ael ; // Put 3 edges on the list and sort it. ael.push_back( Edge( CPoint(10,10), CPoint(40,50) ) ) ; ael.push_back( Edge( CPoint(20,30), CPoint(25,70) ) ) ; ael.push_back( Edge( CPoint(40,10), CPoint(35,90) ) ) ; ael.sort() ; // Walk down the list and update its edges. for ( list<Edge>::iterator it= ael.begin() ; it != ael.end() ; ++it ) { cout << *it ; it->update() ; cout << ", after 1 update: " << *it << endl ; } return 0 ;}#include <list>Z-Buffering for each polygon for each scanline for each pixel in scanline update depth at pixel if pixel depth < buffered depth write to screen & depth buffersTwo buffers - screen buffer (color) - depth bufferZ-Buffering [n^, d] x += xz += ______xderive