1Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Implementation IEd AngelProfessor of Computer Science,Electrical and ComputerEngineering, and Media ArtsUniversity of New Mexico2Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Objectives• Introduce basic implementation strategies• Clipping• Scan conversion3Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Overview• At end of the geometric pipeline, verticeshave been assembled into primitives• Must clip out primitives that are outsidethe view frustum- Algorithms based on representing primitives bylists of vertices• Must find which pixels can be affected byeach primitive- Fragment generation- Rasterization or scan conversion4Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Required Tasks• Clipping• Rasterization or scan conversion• Transformations• Some tasks deferred until fragementprocessing- Hidden surface removal- Antialiasing5Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Rasterization Meta Algorithms• Consider two approaches to rendering ascene with opaque objects• For every pixel, determine which object thatprojects on the pixel is closest to the viewerand compute the shade of this pixel- Ray tracing paradigm• For every object, determine which pixels itcovers and shade these pixels- Pipeline approach- Must keep track of depths6Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Clipping• 2D against clipping window• 3D against clipping volume• Easy for line segments polygons• Hard for curves and text- Convert to lines and polygons first7Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Clipping 2D Line Segments• Brute force approach: computeintersections with all sides of clippingwindow- Inefficient: one division per intersection8Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Cohen-Sutherland Algorithm• Idea: eliminate as many cases as possiblewithout computing intersections• Start with four lines that determine thesides of the clipping windowx = xmaxx = xminy = ymaxy = ymin9Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005The Cases• Case 1: both endpoints of line segment inside allfour lines- Draw (accept) line segment as is• Case 2: both endpoints outside all lines and onsame side of a line- Discard (reject) the line segmentx = xmaxx = xminy = ymaxy = ymin10Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005The Cases• Case 3: One endpoint inside, one outside- Must do at least one intersection• Case 4: Both outside- May have part inside- Must do at least one intersectionx = xmaxx = xminy = ymax11Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Defining Outcodes• For each endpoint, define an outcode• Outcodes divide space into 9 regions• Computation of outcode requires at most4 subtractionsb0b1b2b3b0 = 1 if y > ymax, 0 otherwiseb1 = 1 if y < ymin, 0 otherwiseb2 = 1 if x > xmax, 0 otherwiseb3 = 1 if x < xmin, 0 otherwise12Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Using Outcodes• Consider the 5 cases below• AB: outcode(A) = outcode(B) = 0- Accept line segment13Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Using Outcodes• CD: outcode (C) = 0, outcode(D) ≠ 0- Compute intersection- Location of 1 in outcode(D) determines whichedge to intersect with- Note if there were a segment from A to a pointin a region with 2 ones in outcode, we mighthave to do two interesections14Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Using Outcodes• EF: outcode(E) logically ANDed withoutcode(F) (bitwise) ≠ 0- Both outcodes have a 1 bit in the same place- Line segment is outside of corresponding sideof clipping window- reject15Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Using Outcodes• GH and IJ: same outcodes, neither zerobut logical AND yields zero• Shorten line segment by intersecting withone of sides of window• Compute outcode of intersection (newendpoint of shortened line segment)• Reexecute algorithm16Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Efficiency• In many applications, the clipping windowis small relative to the size of the entiredata base- Most line segments are outside one or moreside of the window and can be eliminatedbased on their outcodes• Inefficiency when code has to bereexecuted for line segments that must beshortened in more than one step17Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Cohen Sutherland in 3D• Use 6-bit outcodes• When needed, clip line segment against planes18Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Liang-Barsky Clipping• Consider the parametric form of a line segment• We can distinguish between the cases by looking at theordering of the values of α where the line determined bythe line segment crosses the lines that determine thewindowp(α) = (1-α)p1+ αp2 1 ≥ α ≥ 0p1p219Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Liang-Barsky Clipping• In (a): α4 > α3 > α2 > α1- Intersect right, top, left, bottom: shorten• In (b): α4 > α2 > α3 > α1- Intersect right, left, top, bottom: reject20Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Advantages• Can accept/reject as easily as withCohen-Sutherland• Using values of α, we do not have to usealgorithm recursively as with C-S• Extends to 3D21Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Clipping and Normalization• General clipping in 3D requiresintersection of line segments againstarbitrary plane• Example: oblique view22Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Plane-Line Intersections)()(121ppnppnao!•!•=23Angel: Interactive Computer Graphics 4E © Addison-Wesley 2005Normalized Formbefore normalization after normalizationNormalization is part of viewing (pre clipping)but after normalization, we clip against sides ofright parallelepipedTypical intersection calculation now requires onlya floating point subtraction, e.g. is x > xmax ?top