Last TimeTodaySweep Fill AlgorithmsSpansAlgorithmUpdating EdgesWhen are Edges Relevant (1)When are Edges Relevant (2)When are Edges Relevant (3)Sweep Fill DetailsEdge TableActive Edge List (shown just before filling each row)Slide 13Active Edge ListCommentsDodging Floating Point (for integer endpoints)Anti-AliasingPre-Filtered PrimitivesPost-Filtering (Supersampling)Where We StandVisibilityVisibility IssuesPainters Algorithm (Image Precision)The Z-buffer (1) (Image Precision)The Z-buffer (2)Z-Buffer and Transparency03/07/02(c) 2002 University of Wisconsin, CS559Last Time•Line drawing•An intro to polygon filling03/07/02(c) 2002 University of Wisconsin, CS559Today•Polygon Fill•Some methods for hidden surface removal•Homework 4 is online–It’s due two days before the midterm, but we will grade it in time and it’s useful study material•Midterm info03/07/02(c) 2002 University of Wisconsin, CS559Sweep Fill Algorithms•Algorithmic issues:–Reduce to filling many spans–Which edges define the span of pixels to fill?–How do you update these edges when moving from span to span?–What happens when you cross a vertex?03/07/02(c) 2002 University of Wisconsin, CS559Spans•Process - fill the bottom horizontal span of pixels; move up and keep filling •Have xmin, xmax for each span•Define:–floor(x): largest integer < x–ceiling(x): smallest integer >=x•Fill from ceiling(xmin) up to floor(xmax)•Consistent with convention03/07/02(c) 2002 University of Wisconsin, CS559Algorithm•For each row in the polygon:–Throw away irrelevant edges–Obtain newly relevant edges–Fill span–Update current edges•Issues:–How do we update existing edges?–When is an edge relevant/irrelevant?•All can be resolved by referring to our convention about what polygon pixel belongs to03/07/02(c) 2002 University of Wisconsin, CS559Updating Edges•Each edge is a line of the form:•Next row is:•So, each current edge can have it’s x position updated by adding a constant stored with the edge•Other values may also be updated, such as depth or color informationcmyxcmxy or mxcmyxii)1(103/07/02(c) 2002 University of Wisconsin, CS559When are Edges Relevant (1)•Use figures and convention to determine when edge is irrelevant–For y<ymin and y>=ymax of edge•Similarly, edge is relevant when y>=ymin and y<ymax of edge•What about horizontal edges?–m’ is infinite03/07/02(c) 2002 University of Wisconsin, CS559When are Edges Relevant (2)12343,41,31,2Convex polygon:Always only two edges active03/07/02(c) 2002 University of Wisconsin, CS559When are Edges Relevant (3)1,3Horizontal edges?12344?2?03/07/02(c) 2002 University of Wisconsin, CS559Sweep Fill Details•Maintain a list of active edges in case there are multiple spans of pixels - known as Active Edge List.•For each edge on the list, must know: x-value, maximum y value of edge, m’–Maybe also depth, color…•Keep all edges in a table, indexed by minimum y value - Edge Table•For row = min to row=max–AEL=append(AEL, ET(row));–remove edges whose ymax=row–sort AEL by x-value–fill spans–update each edge in AEL03/07/02(c) 2002 University of Wisconsin, CS5591234561 2 3 4 5 6Row:6543212 0 5 6 0 64 0 56 0 6xmin1/mymaxEdge Table5 0 603/07/02(c) 2002 University of Wisconsin, CS5592 0 5 6 0 62 0 5 6 0 62 0 5 6 0 62 0 5 4 0 55 0 6 6 0 66 0 6x1/mymaxActive Edge List (shown just before filling each row)1234561 2 3 4 5 65 0 6 6 0 603/07/02(c) 2002 University of Wisconsin, CS5591234561 2 3 4 5 6Row:654321 2 1 5 6 -1 56 0 6xmin1/mymaxEdge Table03/07/02(c) 2002 University of Wisconsin, CS5591234561 2 3 4 5 6Row:654321 2 1 5 6 -1 53 1 5 5 -1 54 1 5 4 -1 53 -1 5 5 1 56 0 6x1/mymaxActive Edge List03/07/02(c) 2002 University of Wisconsin, CS559Comments•Sort is quite fast, because AEL is usually almost in order–Use bubble sort or insertion sort•OpenGL limits to convex polygons, meaning two and only two elements in AEL at any time, and no sorting •Can generate memory addresses (for pixel writes) efficiently•Does not require floating point - next slide03/07/02(c) 2002 University of Wisconsin, CS559Dodging Floating Point(for integer endpoints)•For edge, m=x/y, which is a rational number•View x as xi+xn/y, with xn<y. Store xi and xn•Then x->x+m’ is given by:–xn=xn+x–if (xn>=y) { xi=xi+1; xn=xn- y }•Advantages:–no floating point–can tell if x is an integer or not, and get floor(x) and ceiling(x) easily, for the span endpoints03/07/02(c) 2002 University of Wisconsin, CS559Anti-Aliasing•Recall: We can’t sample and then accurately reconstruct an image that is not band-limited–Infinite Nyquist frequency–Attempting to sample sharp edges gives “jaggies”, or stair-step lines•Solution: Band-limit by filtering (pre-filtering)–What sort of filter will give a band-limited result?•But when doing computer rendering, we don’t have the original continuous function03/07/02(c) 2002 University of Wisconsin, CS559Pre-Filtered Primitives•We can simulate filtering by rendering “thick” primitives, with , and compositing•Expensive, and requires the ability to do compositing•Hardware method: Keep sub-pixel masks tracking coverageIdeal1/62/31/6Filter=1/6=2/3=1/6 over=1/6=2/3=1/6Pre-Filtered and composited03/07/02(c) 2002 University of Wisconsin, CS559Post-Filtering (Supersampling)•Sample at a higher resolution than required for display, and filter image down•Two basic approaches:–Generate extra samples and filter the result (traditional super-sampling)–Generate multiple (say 4) images, each with the image plane slightly offset. Then average the images•Requires general perspective transformations•Can be done in OpenGL using the accumulation buffer•Issues of which samples to take, and how to average them•Method used in most current hardware–Note that anti-aliasing costs 4x regular rendering for 2x2 box filtering03/07/02(c) 2002 University of Wisconsin, CS559Where We Stand•At this point we know how to:–Convert points from local to window coordinates–Clip polygons and lines to the view volume–Determine which pixels are covered by any given line or polygon–Anti-alias•Next thing:–Determine which polygon is in front03/07/02(c) 2002 University of Wisconsin, CS559Visibility•Given a set of polygons, which is visible at each pixel? (in front, etc.). Also called hidden surface
View Full Document
Unlocking...