1CMSC 341Asymptotic AnalysisApplication Example: Visibility9/13/2007 UMBC CMSC 341 AA Example 2AA Example: Visibility The problem: Given a geometric model (list ofpolygons) and a view specification, generate theimage which represents that scene viewed inthat way Many ways to approach the problem Ivan Sutherland, A Characterization of Ten HiddenSurface Algorithms, 1974 More approaches in the decades since29/13/2007 UMBC CMSC 341 AA Example 3Painter’s Algorithm Approach Sort polygons Draw polygons in order: furthest to closest9/13/2007 UMBC CMSC 341 AA Example 4Painter’s Algorithm Given List of Polygons {P1, P2, … , Pn} Array of Intensity [x, y]BeginSort polygon list on minimum z (largest z first)For each polygon P in selected list doFor each pixel (x,y) that intersects P doIntensity [x,y] = intensity of P at (x,y)Display Intensity array39/13/2007 UMBC CMSC 341 AA Example 5Z-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 6Zbuffer Example (1) Pgon: (1,1,5), (7,7,5), (1,7,5)49/13/2007 UMBC CMSC 341 AA Example 7Zbuffer Example (2) Pgon: (3,5,9), (10, 5, 9), (10,9,9), (3,9,9)9/13/2007 UMBC CMSC 341 AA Example 8Zbuffer Example (3) Pgon: (2,6,3), (2,3,8), (7,3,3)59/13/2007 UMBC CMSC 341 AA Example 9Zbuffer Example (4)9/13/2007 UMBC CMSC 341 AA Example 10Zbuffer Algorithm Given List of Polygons {P1, P2, … , Pn} Array of Intensity [x, y] Array z-buffer [x,y], initialized to +infinityBeginFor each polygon P in selected list doFor each pixel (x,y) that intersects P doCalculate z-depth of P at (x,y)If z-depth < z-buffer[x,y] thenIntensity [x,y] = intensity of P at (x,y)z-buffer[x,y] = z-depthDisplay Intensity array69/13/2007 UMBC CMSC 341 AA Example 11Scanline Algorithm Approach Consider one row of image (scanline) at a time Identify coherent runs in scanline9/13/2007 UMBC CMSC 341 AA Example 12Scanline Algorithm Given List of Polygons {P1, P2, … , Pn} Array of Intensity [x, y]BeginSort pgons into sorted surface table (SST) on yInitialize y and active surface table (AST)Repeat until AST and SST emptyidentify spans for this scanline (sorted on x)for each spandetermine visible element (based on z)fill pixel intensities with values from elementupdate AST: y++remove exhausted edgesupdate x interceptsresort AST on xadd entering pgonsDisplay Intensity array79/13/2007 UMBC CMSC 341 AA Example 13Ray Casting Approach Project sight rays from eye point through pixel intoscene Draw thing found at first intersection of each pixel9/13/2007 UMBC CMSC 341 AA Example 14Ray Casting Algorithm (1) Given List of Polygons {P1, P2, … , Pn} Array of Intensity [x, y]BeginFor each pixel (x,y) {form a ray R in object space through the cameraposition C and the pixel (x,y)Intensity [x,y] = trace(R)}Display array Intensity89/13/2007 UMBC CMSC 341 AA Example 15Ray Casting Algorithm (2)Intensity trace(Ray) {for each polygon P in the sceneCalculate the intersection of P and RIf ( R hit no pgon)return (background intensity)Else {Find pgon P with closest intersectionCalculate intensity I at intersection pointReturn (I)}9/13/2007 UMBC CMSC 341 AA Example 16Visibility Algorithm Taxonomy Basic design choice Object space: organize by pgon Image space: organize by pixel99/13/2007 UMBC CMSC 341 AA Example 17Visibility Algorithm Taxonomy Also considercontinuous output9/13/2007 UMBC CMSC 341 AA Example 18Visibility Algorithm Taxonomy109/13/2007 UMBC CMSC 341 AA Example 19Reviewing the Code9/13/2007 UMBC CMSC 341 AA Example 20Painter’s Algorithm Given List of Polygons {P1, P2, … , Pn} Array of Intensity [x, y]BeginSort polygon list on minimum z (largest z first)For each polygon P in selected list doFor each pixel (x,y) that intersects P doIntensity [x,y] = intensity of P at (x,y)Display Intensity array119/13/2007 UMBC CMSC 341 AA Example 21Zbuffer Algorithm Given List of Polygons {P1, P2, … , Pn} Array of Intensity [x, y] Array z-buffer [x,y], initialized to +infinityBeginFor each polygon P in selected list doFor each pixel (x,y) that intersects P doCalculate z-depth of P at (x,y)If z-depth < z-buffer[x,y] thenIntensity [x,y] = intensity of P at (x,y)z-buffer[x,y] = z-depthDisplay Intensity array9/13/2007 UMBC CMSC 341 AA Example 22Scanline Algorithm Given List of Polygons {P1, P2, … , Pn} Array of Intensity [x, y]BeginSort pgons into sorted surface table (SST) on yInitialize y and active surface table (AST)Repeat until AST and SST emptyidentify spans for this scanline (sorted on x)for each spandetermine visible element (based on z)fill pixel intensities with values from elementupdate AST: y++remove exhausted edgesupdate x interceptsresort AST on xadd entering pgonsDisplay Intensity array129/13/2007 UMBC CMSC 341 AA Example 23Ray Casting Algorithm (1) Given List of Polygons {P1, P2, … , Pn} Array of Intensity [x, y]BeginFor each pixel (x,y) {form a ray R in object space through the cameraposition C and the pixel (x,y)Intensity [x,y] = trace(R)}Display array Intensity9/13/2007 UMBC CMSC 341 AA Example 24Looking at PerformanceRaycastScanlineZ-bufferPainter’s ApproachTIme Space139/13/2007 UMBC CMSC 341 AA Example
View Full Document
Unlocking...