Last TimeTodayVisibility RecapZ-Buffer and TransparencyOpenGL Depth BufferThe A-buffer (Image Precision)The A-buffer (2)Area SubdivisionWarnock’s Area Subdivision (Image Precision)Warnock’s AlgorithmBSP-Trees (Object Precision)BSP-Tree ExampleBuilding BSP-TreesBuilding ExampleBuilding Example (Done)BSP-Tree RenderingUsing a BSP-TreeRendering ExampleBSP-Tree Rendering (2)Exact VisibilityCells and PortalsCell-Portal Example (1)Cell and Portal VisibilityCell-Portal Example (2)Cell-Portal Example (3)Cell-Portal Example (4)Cell-Portal Example (5)Cell-Portal Example (6)Cell-Portal OperationsCell-Portal PropertiesProject 2 IntroProject 2 (2)Project 2 (3)Where We Stand11/02/04 © University of Wisconsin, CS559 Fall 2004Last Time•Filling polygons•Anti-aliasing•Visibility–Painter’s algorithm–Z-Buffer11/02/04 © University of Wisconsin, CS559 Fall 2004Today•Hidden Surface Removal–More Z-buffer–A-buffer–BSP Tree algorithms•Project 211/02/04 © University of Wisconsin, CS559 Fall 2004Visibility 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 polygon11/02/04 © University of Wisconsin, CS559 Fall 2004Z-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 onePartially transparentOpaqueOpaque1st2nd3rdFront1st or 2nd1st or 2ndMust recall this color and depth3rd: Need depth of 1st and 2nd11/02/04 © University of Wisconsin, CS559 Fall 2004OpenGL 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 buffer11/02/04 © University of Wisconsin, CS559 Fall 2004The 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 polygons11/02/04 © University of Wisconsin, CS559 Fall 2004The A-buffer (2)•Algorithm: Rendering pass–At each pixel, traverse buffer using polygon colors and coverage masks to composite:•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 toolsover=11/02/04 © University of Wisconsin, CS559 Fall 2004Area 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 region2. no surfaces project to the region3. only one surface is completely inside the region, overlaps the region, or surrounds the region11/02/04 © University of Wisconsin, CS559 Fall 2004Warnock’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 slow11/02/04 © University of Wisconsin, CS559 Fall 2004Warnock’s Algorithm•Regions labeled with case used to classify them:1) One polygon in front2) Empty3) One polygon inside, surrounding or intersecting•Small regions not labeled•Note it’s a rendering algorithm and a HSR algorithm at the same time–Assuming you can draw squares2 2 22222223333 33333333333311 11111/02/04 © University of Wisconsin, CS559 Fall 2004BSP-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 algorithm11/02/04 © University of Wisconsin, CS559 Fall 2004BSP-Tree ExampleACB2413ABC3 2 4 1---+++11/02/04 © University of Wisconsin, CS559 Fall 2004Building 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 tree11/02/04 © University of Wisconsin, CS559 Fall 2004Building Example•We will build a BSP tree, in 2D, for a 3 room building–Ignoring doors•Splitting edge order is shown–“Back” side of edge is side with the number123 45611/02/04 © University of Wisconsin, CS559 Fall 2004Building Example (Done)123b 4b5a61-+4a3a2-+5b3a+3b+4a6+5b4b5a+11/02/04 © University of Wisconsin, CS559 Fall 2004BSP-Tree Rendering•Observation: Things on the opposite side of a splitting plane from the viewpoint cannot obscure things on the same side as the
View Full Document
Unlocking...