Last Time Line drawing An intro to polygon filling 03 07 02 c 2002 University of Wisconsin CS559 Today 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 info 03 07 02 c 2002 University of Wisconsin CS559 Sweep Fill Algorithms Algorithmic issues 03 07 02 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 c 2002 University of Wisconsin CS559 Spans 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 convention 03 07 02 c 2002 University of Wisconsin CS559 Algorithm 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 to 03 07 02 c 2002 University of Wisconsin CS559 Updating Edges Each edge is a line of the form y mx c or x ym c Next row is xi 1 y 1 m c xi m 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 information 03 07 02 c 2002 University of Wisconsin CS559 When 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 infinite 03 07 02 c 2002 University of Wisconsin CS559 When are Edges Relevant 2 Convex polygon Always only two edges active 2 1 2 1 1 3 3 3 4 03 07 02 4 c 2002 University of Wisconsin CS559 When are Edges Relevant 3 Horizontal edges 2 1 1 3 4 03 07 02 2 3 4 c 2002 University of Wisconsin CS559 Sweep 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 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 AEL Maybe also depth color Keep all edges in a table indexed by minimum y value Edge Table 03 07 02 c 2002 University of Wisconsin CS559 Edge Table 6 5 4 3 2 Row 6 5 4 1 2 3 4 5 0 5 5 0 6 2 0 5 6 0 6 3 2 1 1 4 6 6 xmin 03 07 02 c 2002 University of Wisconsin CS559 0 6 1 m ymax Active Edge List shown just before filling each row 6 1 2 3 4 5 5 5 0 6 6 0 6 4 2 0 5 4 0 5 3 2 0 5 6 0 6 2 2 0 5 6 0 6 1 2 0 5 6 0 6 6 6 x 03 07 02 5 0 6 1 m c 2002 University of Wisconsin CS559 ymax 0 6 6 0 6 Edge Table Row 6 5 6 5 4 4 3 2 3 2 1 2 1 5 6 1 5 1 6 1 2 03 07 02 3 4 5 6 xmin c 2002 University of Wisconsin CS559 0 6 1 m ymax Active Edge List Row 6 6 5 5 4 3 1 5 5 1 5 3 4 1 5 4 1 5 2 3 1 5 5 1 5 1 2 1 5 6 1 5 4 3 2 1 1 2 3 4 5 6 6 x 03 07 02 c 2002 University of Wisconsin CS559 0 6 1 m ymax Comments 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 slide 03 07 02 c 2002 University of Wisconsin CS559 Dodging 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 endpoints 03 07 02 c 2002 University of Wisconsin CS559 Anti 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 function 03 07 02 c 2002 University of Wisconsin CS559 Pre 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 coverage Filter 1 6 2 3 1 6 Ideal 03 07 02 1 6 2 3 1 6 over 1 6 2 3 1 6 Pre Filtered and composited c 2002 University of Wisconsin CS559 Post 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 filtering 03 07 02 c 2002 University of Wisconsin CS559 Where 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 front 03 07 02 c 2002 University of Wisconsin CS559 Visibility Given a set of polygons which is visible at each pixel in front etc Also called hidden surface removal Very large number of different algorithms known Two main classes Object precision computations that decompose polygons in world to solve Image precision computations at the pixel level All the spaces in the viewing pipeline maintain depth so we can work …
View Full Document
Unlocking...