Description

CIS 636 Prologue to PC Design CG Nuts and bolts 2 of 8: Rasterization and 2-D Cutting William H. Hsu Division of Processing and Data Sciences, KSU KSOL course pages: http://snipurl.com/1y5gc Course site: http://www.kddresearch.org/Courses/CIS636

Transcripts

CIS 636 Introduction to Computer Graphics CG Basics 2 of 8: Rasterization and 2-D Clipping William H. Hsu Department of Computing and Information Sciences, KSU KSOL course pages: http://snipurl.com/1y5gc Course site: http://www.kddresearch.org/Courses/CIS636 Instructor landing page: http://www.cis.ksu.edu/~bhsu Readings: Sections 2.4 â 2.6 , Eberly 2 e â see http://snurl.com/1ye72 Chapter 3, Foley, J. D., VanDam, A., Feiner, S. K., & Hughes, J. F. (1991). PC Graphics, Principles and Practice, Second Edition in C. NeHe instructional exercises: http://nehe.gamedev.net (#2: polygons, 21: lines, 26: cutting) CIS 636/736: (Introduction to) Computer Graphics

Lecture Outline Scan Conversion of Lines Naã¯ve calculation Midpoint calculation ( otherwise known as Bresenhamâs) Method of forward contrasts Scan Conversion of Polygons Scan line interjection Why itâs critical: premise of shading/texturing, z-buffering Scan Conversion of Circles and Ellipses Aliasing and Antialiasing Basic issue characterized Approaches CIS 636/736: (Introduction to) Computer Graphics

Online Recorded Lectures for CIS 636 Introduction to Computer Graphics Project Topics for CIS 636 Computer Graphics Basics (8) 1. Numerical Foundations â Week 2. Rasterizing and 2-D Clipping â Week 3. OpenGL Primer 1 of 3 â Week 3 4. Nitty gritty Introduction to 3-D Viewing â Week 4 5. OpenGL Primer 2 of 3 â Week 5 6. Polygon Rendering â Week 6 7. OpenGL Primer 3 of 3 â Week 8. Obvious Surface Determination â Week 9 Recommended Background Reading for CIS 636 Shared Lectures with CIS 736 ( Computer Graphics ) Regular in-class addresses (35) and labs (7) Guidelines for paper surveys â Week 7 Preparing term venture presentations, demos for design â Week 11 CIS 636/736: (Introduction to) Computer Graphics

Scan Converting Lines Line Drawing Draw a line on a raster screen between two focuses Whatâs amiss with the issue\'s announcement? it doesnât say anything in regards to which focuses are permitted as endpoints it doesnât give an unmistakable intending to âdrawâ it doesnât say what constitutes a âlineâ in the raster world it doesnât say how to gauge the achievement of a proposed calculation Problem Statement Given two focuses P and Q in the plane, both with whole number directions, figure out which pixels on a raster screen ought to be on keeping in mind the end goal to make a photo of a unit-width line fragment beginning at P and completion at Q Adapted from slides Â© 2005 A. VanDam, Brown University. Reused with consent. CIS 636/736: (Introduction to) Computer Graphics

Finding the following pixel Special case: Horizontal Line: Draw pixel P and addition the x direction esteem by one to get the following pixel. Vertical Line: Draw pixel P and addition the y direction esteem by one to get the following pixel. Flawless Diagonal Line: Draw pixel P and addition both the x and the y coordinate by one to get the following pixel. What would it be advisable for us to do in the general case? Increase the x coordinate by 1 and pick the point nearest to the line. Be that as it may, how would we gauge âclosestâ? Adjusted from slides Â© 2005 A. VanDam, Brown University. Reused with consent. CIS 636/736: (Introduction to) Computer Graphics

Vertical Distance Why would we be able to utilize the vertical separation as a measure of which point is closer? since the vertical separation is relative to the real separation how would we demonstrate this? with compatible triangles By comparable triangles we can see that the genuine separations to the line (in blue) are straightforwardly corresponding to the vertical separations to the line (in dark) for every point Therefore, the point with the littler vertical separation to the line is the nearest to the line ( x 1 , y 1 ) ( x 2 , y 2 ) Adapted from slides Â© 2005 A. VanDam, Brown University. Reused with authorization. CIS 636/736: (Introduction to) Computer Graphics

Strategy 1: Incremental Algorithm [1] The Basic Algorithm Find the mathematical statement of the line that join the two focuses P and Q Starting with the furthest left point P , increase x i by 1 to figure y i = mx i + B where m = slant, B = y capture Intensify the pixel at ( x i , Round( y i )) where Round ( y i ) = Floor (0.5 + y i ) The Incremental Algorithm: Each cycle obliges a drifting point duplication in this manner, alter the calculation. y i+ 1 = mx i+ 1 + B = m ( x i + ï x ) + B = y i + m ï x If ï x = 1 , then y i+ 1 = y i + m At every stride, we make incremental computations taking into account the former stride to locate the following y worth Adapted from slides Â© 2005 A. VanDam, Brown University. Reused with authorization. CIS 636/736: (Introduction to) Computer Graphics

Strategy 1: Incremental Algorithm [2] Adapted from slides Â© 2005 A. VanDam, Brown University. Reused with authorization. CIS 636/736: (Introduction to) Computer Graphics

Example Code/Incremental Line Algorithm/Assumes â1 <= m <= 1, x0 < x1 void Line(int x0, int y0, int x1, int y1, int esteem) { int x; float y; float dy = y1 â y0; float dx = x1 â x0; float m = dy/dx; y = y0; for (x = x0; x < x1; x++) { WritePixel(x, Round(y), esteem); y = y + m; } } Adapted from slides Â© 2005 A. VanDam, Brown University. Reused with authorization. CIS 636/736: (Introduction to) Computer Graphics

Problems with Incremental Algorithm void Line(int x0, int y0, int x1, int y1, int esteem) { int x; float y; float dy = y1 â y0; float dx = x1 â x0; float m = dy/dx; y = y0; for (x = x0; x < x1; x++) { WritePixel(x, Round(y), value); y = y + m; } } Rounding sets aside time Since slant is fragmentary, need exceptional case for vertical lines Adapted from slides Â© 2005 A. VanDam, Brown University. Reused with authorization. CIS 636/736: (Introduction to) Computer Graphics

Strategy 2: Midpoint Line Algorithm [1] Assume lineâs incline is shallow and positive (0 < slant < 1); different inclines can be taken care of by suitable reflections about key tomahawks Call lower left endpoint ( x 0 , y 0 ) and upper right endpoint ( x 1 , y 1 ) Assume we have quite recently chosen pixel P at ( x p , y p ) Next, must pick between pixel to right (E pixel) one right and one up (NE pixel) Let Q be convergence purpose of line being sweep changed over with network line x = x p +1 Adapted from slides Â© 2005 A. VanDam, Brown University. Reused with authorization. CIS 636/736: (Introduction to) Computer Graphics

Strategy 2: Midpoint Line Algorithm [2] NE pixel Q Midpoint M E pixel Previous pixel Choices for current pixel Choices for next pixel Adapted from slides Â© 2005 A. VanDam, Brown University. Reused with authorization. CIS 636/736: (Introduction to) Computer Graphics

Strategy 2: Midpoint Line Algorithm [3] The line goes in the middle of E and NE The point that is closer to the convergence point Q must be picked Observe on which side of the line the midpoint M lies: E is closer to the line if the midpoint M lies over the line, i.e., the line crosses the base half NE is closer to the line if the midpoint M lies beneath the line, i.e., the line crosses the top a large portion of The mistake, the vertical separation between the picked pixel and the real line, is dependably â¤ Â½ The calculation picks NE as the following pixel for the line demonstrated Now, figure out how to ascertain on which side of the line the midpoint untruths Adapted from slides Â© 2005 A. VanDam, Brown University. Reused with authorization. CIS 636/736: (Introduction to) Computer Graphics

The Line mathematical statement as a capacity f(x) : y = f(x) = m*x + B = dy/dx*x + B Line comparison as an understood capacity: F ( x, y ) = a*x + b*y + c = 0 for coefficients a , b , c , where a , b â 0 from above, y*dx = dy*x + B*dx so a = dy , b = - dx , c = B*dx , a > 0 for y 0 < y 1 Properties (evidence by case investigation): F ( x m , y m ) = 0 when any point M is hanging in the balance F ( x m , y m ) < 0 when any point M is over the line F ( x m , y m ) > 0 when any point M is beneath the line Our choice will be founded on the capacity\'s estimation at the midpoint M at ( x p + 1, y p + Â½) Adapted from slides Â© 2005 A. VanDam, Brown University. Reused with authorization. CIS 636/736: (Introduction to) Computer Graphics

Decision Variable Decision Variable d : We just need the indication of F ( x p + 1, y p + Â½) to see where the line untruths, and afterward pick the closest pixel d = F ( x p + 1, y p + Â½) -if d > 0 pick pixel NE -if d < 0 pick pixel E -if d = 0 pick either one reliably How would we incrementally upgrade d ? On the premise of picking E or NE, make sense of the area of M for the following network line, and the comparing estimation of d = F(M) for that framework line Adapted from slides Â© 2005 A. VanDam, Brown University. Reused with authorization. CIS 636/736: (Introduction to) Computer Graphics

E Pixel Chosen M is augmented by one stage in the x heading d new = F ( x p + 2, y p + Â½) = a ( x p + 2) + b ( y p + Â½) + c d old = a ( x p + 1) + b ( y p + Â½) + c Subtract d old from d new to get the incremental distinction ï E d new = d old + a ï E = a = dy Gives estimation of choice variable at next step incrementally without registering F(M) straightforwardly d new = d old + ï E = d old + dy ï E can be considered as the adjustment or overhaul element to take d old to d new It is alluded to as the forward contrast Adapted from slides Â© 2005 A. VanDam, Bro