CMSC 341 Asymptotic Analysis Application Example Visibility AA Example Visibility The problem Given a geometric model list of polygons and a view specification generate the image which represents that scene viewed in that way Many ways to approach the problem 9 13 2007 Ivan Sutherland A Characterization of Ten Hidden Surface Algorithms 1974 More approaches in the decades since UMBC CMSC 341 AA Example 2 1 Painter s Algorithm Approach Sort polygons Draw polygons in order furthest to closest 9 13 2007 UMBC CMSC 341 AA Example 3 Painter s Algorithm Given List of Polygons P1 P2 Pn Array of Intensity x y Begin Sort polygon list on minimum z largest z first For each polygon P in selected list do For each pixel x y that intersects P do Intensity x y intensity of P at x y Display Intensity array 9 13 2007 UMBC CMSC 341 AA Example 4 2 Z buffer Approach Draw polygons in arbitrary order store depth At each pixel overwrite if new pgon closer Pgon 1 1 5 7 7 5 1 7 5 9 13 2007 UMBC CMSC 341 AA Example 5 Zbuffer Example 1 Pgon 1 1 5 7 7 5 1 7 5 9 13 2007 UMBC CMSC 341 AA Example 6 3 Zbuffer Example 2 Pgon 3 5 9 10 5 9 10 9 9 3 9 9 9 13 2007 UMBC CMSC 341 AA Example 7 Zbuffer Example 3 Pgon 2 6 3 2 3 8 7 3 3 9 13 2007 UMBC CMSC 341 AA Example 8 4 Zbuffer Example 4 9 13 2007 UMBC CMSC 341 AA Example 9 Zbuffer Algorithm Given List of Polygons P1 P2 Pn Array of Intensity x y Array z buffer x y initialized to infinity Begin For each polygon P in selected list do For each pixel x y that intersects P do Calculate z depth of P at x y If z depth z buffer x y then Intensity x y intensity of P at x y z buffer x y z depth Display Intensity array 9 13 2007 UMBC CMSC 341 AA Example 10 5 Scanline Algorithm Approach Consider one row of image scanline at a time Identify coherent runs in scanline 9 13 2007 UMBC CMSC 341 AA Example 11 Scanline Algorithm Given List of Polygons P1 P2 Pn Array of Intensity x y Begin Sort pgons into sorted surface table SST on y Initialize y and active surface table AST Repeat until AST and SST empty identify spans for this scanline sorted on x for each span determine visible element based on z fill pixel intensities with values from element update AST y remove exhausted edges update x intercepts resort AST on x add entering pgons Display Intensity array 9 13 2007 UMBC CMSC 341 AA Example 12 6 Ray Casting Approach Project sight rays from eye point through pixel into scene Draw thing found at first intersection of each pixel 9 13 2007 UMBC CMSC 341 AA Example 13 Ray Casting Algorithm 1 Given List of Polygons P1 P2 Pn Array of Intensity x y Begin For each pixel x y form a ray R in object space through the camera position C and the pixel x y Intensity x y trace R Display array Intensity 9 13 2007 UMBC CMSC 341 AA Example 14 7 Ray Casting Algorithm 2 Intensity trace Ray for each polygon P in the scene Calculate the intersection of P and R If R hit no pgon return background intensity Else Find pgon P with closest intersection Calculate intensity I at intersection point Return I 9 13 2007 UMBC CMSC 341 AA Example 15 Visibility Algorithm Taxonomy Basic design choice 9 13 2007 Object space organize by pgon Image space organize by pixel UMBC CMSC 341 AA Example 16 8 Visibility Algorithm Taxonomy Also consider continuous output 9 13 2007 UMBC CMSC 341 AA Example 17 Visibility Algorithm Taxonomy 9 13 2007 UMBC CMSC 341 AA Example 18 9 Reviewing the Code 9 13 2007 UMBC CMSC 341 AA Example 19 Painter s Algorithm Given List of Polygons P1 P2 Pn Array of Intensity x y Begin Sort polygon list on minimum z largest z first For each polygon P in selected list do For each pixel x y that intersects P do Intensity x y intensity of P at x y Display Intensity array 9 13 2007 UMBC CMSC 341 AA Example 20 10 Zbuffer Algorithm Given List of Polygons P1 P2 Pn Array of Intensity x y Array z buffer x y initialized to infinity Begin For each polygon P in selected list do For each pixel x y that intersects P do Calculate z depth of P at x y If z depth z buffer x y then Intensity x y intensity of P at x y z buffer x y z depth Display Intensity array 9 13 2007 UMBC CMSC 341 AA Example 21 Scanline Algorithm Given List of Polygons P1 P2 Pn Array of Intensity x y Begin Sort pgons into sorted surface table SST on y Initialize y and active surface table AST Repeat until AST and SST empty identify spans for this scanline sorted on x for each span determine visible element based on z fill pixel intensities with values from element update AST y remove exhausted edges update x intercepts resort AST on x add entering pgons Display Intensity array 9 13 2007 UMBC CMSC 341 AA Example 22 11 Ray Casting Algorithm 1 Given List of Polygons P1 P2 Pn Array of Intensity x y Begin For each pixel x y form a ray R in object space through the camera position C and the pixel x y Intensity x y trace R Display array Intensity 9 13 2007 UMBC CMSC 341 AA Example 23 Looking at Performance Approach TIme Space Painter s Z buffer Scanline Raycast 9 13 2007 UMBC CMSC 341 AA Example 24 12 9 13 2007 UMBC CMSC 341 AA Example 25 13
View Full Document
Unlocking...