CIS 636 Prologue to PC Design.


78 views
Uploaded on:
Category: Food / Beverages
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
Slide 1

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

Slide 2

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

Slide 3

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

Slide 4

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

Slide 5

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

Slide 6

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

Slide 7

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

Slide 8

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

Slide 9

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

Slide 10

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

Slide 11

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

Slide 12

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

Slide 13

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

Slide 14

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

Slide 15

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

Slide 16

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

Recommended
View more...