Last Time Filling polygons Anti aliasing Visibility Painter s algorithm Z Buffer 11 02 04 University of Wisconsin CS559 Fall 2004 Today Hidden Surface Removal More Z buffer A buffer BSP Tree algorithms Project 2 11 02 04 University of Wisconsin CS559 Fall 2004 Visibility Recap You are given a set of polygons to draw and you need to figure out which one is visible at every pixel Issues include Efficiency it is slow to overwrite pixels or scan convert things that cannot be seen Accuracy answer should be right and behave well when the viewpoint moves Complexity object precision visibility may generate many small pieces of polygon 11 02 04 University of Wisconsin CS559 Fall 2004 Z Buffer and Transparency Say you want to render transparent surfaces alpha not 1 with a z buffer Must render in back to front order Otherwise would have to store at least the first opaque polygon behind transparent one Front Partially transparent 3rd Opaque 2nd Opaque 1st 1st or 2nd 3rd Need depth of 1st and 2nd 1st or 2nd Must recall this color and depth 11 02 04 University of Wisconsin CS559 Fall 2004 OpenGL Depth Buffer OpenGL defines a depth buffer as its visibility algorithm The enable depth testing glEnable GL DEPTH TEST To clear the depth buffer glClear GL DEPTH BUFFER BIT To clear color and depth glClear GL COLOR BUFFER BIT GL DEPTH BUFFER BIT The number of bits used for the depth values can be specified windowing system dependent and hardware may impose limits based on available memory The comparison function can be specified glDepthFunc Sometimes want to draw furthest thing or equal to depth in buffer 11 02 04 University of Wisconsin CS559 Fall 2004 The A buffer Image Precision Handles transparent surfaces and filter anti aliasing At each pixel maintain a pointer to a list of polygons sorted by depth and a sub pixel coverage mask for each polygon Coverage mask Matrix of bits saying which parts of the pixel are covered Algorithm Drawing pass do not directly display the result if polygon is opaque and covers pixel insert into list removing all polygons farther away if polygon is transparent or only partially covers pixel insert into list but don t remove farther polygons 11 02 04 University of Wisconsin CS559 Fall 2004 The A buffer 2 Algorithm Rendering pass At each pixel traverse buffer using polygon colors and coverage masks to composite over Advantage Can do more than Z buffer Coverage mask idea can be used in other visibility algorithms Disadvantages Not in hardware and slow in software Still at heart a z buffer Over rendering and depth quantization problems But used in high quality rendering tools 11 02 04 University of Wisconsin CS559 Fall 2004 Area Subdivision Exploits area coherence Small areas of an image are likely to be covered by only one polygon The practical truth of this assertion varies over the years it s currently going from mostly false to more true Three easy cases for determining what s in front in a given region 1 a polygon is completely in front of everything else in that region 2 no surfaces project to the region 3 only one surface is completely inside the region overlaps the region or surrounds the region 11 02 04 University of Wisconsin CS559 Fall 2004 Warnock s Area Subdivision Image Precision Start with whole image If one of the easy cases is satisfied previous slide draw what s in front Otherwise subdivide the region and recurse If region is single pixel choose surface with smallest depth Advantages No over rendering Anti aliases well just recurse deeper to get sub pixel information Disadvantage Tests are quite complex and slow 11 02 04 University of Wisconsin CS559 Fall 2004 Warnock s Algorithm 2 3 3 2 3 3 2 1 3 1 1 1 1 3 3 3 3 2 3 3 3 3 Regions labeled with case used to classify them 1 One polygon in front 2 Empty 3 One polygon inside surrounding or intersecting 3 3 3 2 Small regions not labeled Note it s a rendering algorithm and a HSR algorithm at the same time 2 11 02 04 2 2 2 University of Wisconsin CS559 Fall 2004 Assuming you can draw squares BSP Trees Object Precision Construct a binary space partition tree Tree gives a rendering order A list priority algorithm Tree splits 3D world with planes The world is broken into convex cells Each cell is the intersection of all the half spaces of splitting planes on tree path to the cell Also used to model the shape of objects and in other visibility algorithms BSP visibility in games does not necessarily refer to this algorithm 11 02 04 University of Wisconsin CS559 Fall 2004 BSP Tree Example A C 4 A 3 C B B 1 3 2 11 02 04 University of Wisconsin CS559 Fall 2004 2 4 1 Building BSP Trees Choose polygon arbitrary Split its cell using plane on which polygon lies May have to chop polygons in two Clipping Continue until each cell contains only one polygon fragment Splitting planes could be chosen in other ways but there is no efficient optimal algorithm for building BSP trees Optimal means minimum number of polygon fragments in a balanced tree 11 02 04 University of Wisconsin CS559 Fall 2004 Building Example We will build a BSP tree in 2D for a 3 room building 5 Ignoring doors Splitting edge order is shown Back side of edge is side with the number 2 3 4 1 6 11 02 04 University of Wisconsin CS559 Fall 2004 Building Example Done 1 5b 5a 2 3a 4a 3b 6 3b 2 4b 4b 5b 5a 1 3a 6 11 02 04 University of Wisconsin CS559 Fall 2004 4a BSP Tree Rendering Observation Things on the opposite side of a splitting plane from the viewpoint cannot obscure things on the same side as the viewpoint Rendering algorithm is recursive descent of the BSP Tree At each node for back to front rendering Recurse down the side of the sub tree that does not contain the viewpoint Test viewpoint against the split plane to decide which tree Draw the polygon in the splitting plane Paint over whatever has already been drawn Recurse down the side of the tree containing the viewpoint 11 02 04 University of Wisconsin CS559 Fall 2004 Using a BSP Tree Observation Things on the opposite side of a splitting plane from the viewpoint cannot obscure things on the same side as the viewpoint Split plane A statement about rays a ray must hit something on this side of the split plane before it hits the split plane and before it hits anything on the back side NOT a statement about distance things on the far side of the plane can be closer than things on the near side Gives a relative ordering of the polygons not absolute in terms of depth or any other quantity 11 02 04 University
View Full Document
Unlocking...