VisibilityLast timeToday’s topicsVisibility computationsClasses of visibility algorithmsHidden surface removalPainter’s algorithmCookie cutter approachCookie cutter approachArea subdivisionBSP treesConstructing BSP treesConstructing BSP treesConstructing BSP treesConstructing BSP treesConstructing BSP treesConstructing BSP treesConstructing BSP treesConstructing BSP treesRendering with BSP treesRendering with BSP treesBSP treesBSP tree exampleDepth bufferDepth bufferWhat gets stored in a depth-buffer?Computing "Z"Linear yet nonlinear?Interpolating ZMonotonic Z valuesRay castingNext time3/07/071VisibilityComputer GraphicsCOMP 770 (236)Spring 2007Instructor: Brandon Lloyd3/07/072Last time■ Advanced OpenGL features3/07/073Today’s topics■ Visibility in general■ Hidden surface removal° painter’s algorithm° priority lists° area subdivision° depth-buffer° ray casting3/07/074Visibility computations■ Fundamental question: Between which parts of a scene does there exist an unobstructed path■ Types of visiblity computations° hidden surface removal - compute the parts of the scene the eye can see° visibility culling- quickly reject parts of the scene that can’t be seen- back-face culling, view frustum culling, occlusion culling° global visibility - precomputed PVS- line-of-sight- sound propogation- path planning and robotics3/07/075Classes of visibility algorithms■ Point visibility° compute parts of the scene visible at a point■ Region visibility° region visiblity – compute parts of the scene visible at any point in a region■ Object precision° compute parts of an object that are visible° operates directly on the geometry■ Image precision° compute which pixel is visible° discretized representation of geometry3/07/076Hidden surface removal■ Many different algorithms■ All algorithms involve sorting in some wayImages courtesy of Cornell University3/07/077Painter’s algorithm■ Render objects back to front■ Advantages:° Simplicity■ Problems:° How to sort?° Interpenetrating objects° Cycles° Overdrawzx3/07/078Cookie cutter approach■ Clip polygons against each other until depth order can be determined° clip from the eye’s point of view■ Weiler-Atherton° Clip against closest polygon in z-order, creating a list of fragments inside and outside the polygon° Recurse on inside list, then outside list3/07/079Cookie cutter approach■ Advantages° Little over draw° Exact visibility■ Disadvantages° Robustness problems° Complexity3/07/0710Area subdivision■ Main idea° Divide and conquer. Recursively subdivide region until it becomes an easy case■ Stopping criteria° empty region° no intersections or cycles° pixel level – compute polygon depths at pixel center and pick closest° Warnock subdivision3/07/0711BSP trees■ Observation° Objects on the same side of a plane as the eye cannot be occluded by objects on the opposite side of the plane■ Constructing a Binary SpacePartition (BSP) tree° Use a plane from a polygon in the scene as the dividing plane° Partition objects into the positiveor negative half-space° Split objects that straddle° Recurse on each half-space until thereis a single polygon in each half-spaceeye3/07/0712Constructing BSP trees014233/07/0713Constructing BSP trees02f1432b01, 2f 2b, 3, 43/07/0714Constructing BSP trees02f14012b, 3, 42f32b3/07/0715Constructing BSP trees02f14012f2b, 3, 42b33/07/0716Constructing BSP trees02f143f01 2b2f3f 3b,42b3b3/07/0717Constructing BSP trees02f143f01 2b2f 3f3b,42b3b3/07/0718Constructing BSP trees02f143f01 2b2f 3f 3b42b3b3/07/0719Constructing BSP trees02f143f01 2b2f 3f 3b42b3b3/07/0720Rendering with BSP trees■ Algorithm° Start at root node° Recurse on child node that does not contain the eye° Render polygon used for partitioning° Recurse on child node that does contain the eye01 2b2f 3f 3b402f143f2b3b31265473/07/0721Rendering with BSP trees■ Rendering with a BSP tree° Start at root node° Recurse on child node that does not contain the eye° Render polygon used for partitioning° Recurse on child node that does contain the eye01 2b2f 3f 3b402f143f2b3b56742313/07/0722BSP trees■ BSP tree built offline° good for static scenes with moving viewpoint■ Order of planes matters° Finding the optimal order is expensive° Good heuristic: test 5 or 6 planes and choose the candidate thatproduces the least number of splits■ Can be used for things other than visibility° Collision detection° Model representation° CSG operations3/07/0723BSP tree exampleBSP trees used in Doomhttp://pauillac.inria.fr/~levy//bsp/3/07/0724Depth bufferAlgorithm:Maintain current closest surface at each pixelRendering Loop:set depth of all pixels to ZMAXforeach primitive in scene foreach pixel in primitivecompute zprimat pixelif (zprim< depthpixel)thenpixel = object colordepthpixel= zprimendifendforendfor3/07/0725Depth buffer■ Advantages:° Simple° Can process one primitive at a time in any order° Can easily composite one image + depth with another image+depth° Spatial coherence- incremental evaluation in loops- good memory coherence■ Disadvantages:° Visibility coupled to sampling (can cause aliasing artifacts)° Requires a lot of storage° Lots of overdraw° Read/Modify/Write is hard to make fast° Quantization artifacts° Transparency is hard to handle (has to be done in strict back-to-front order)3/07/0726What gets stored in a depth-buffer?Recall the projection matrix was augmented to include a mapping for z values. There are two important considerations. 1. The mapping is from 3D (Affine) to 3D (Projective) 2. The mapping is linear (in general, planes map to planes) ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡′′′−⋅⋅−−+−+−−⋅−+−−⋅1zyx0100000000wzwywxwnearfarnearfar2nearfarnearfarbottomtop)bottomtop(bottomtopnear2leftright)leftright(leftrightnear23/07/0727Computing "Z"We get the following expression for z' from our projection matrixThis mapping of z values is non-linear:)nearfar(znearfar2)nearfar(zz−⋅⋅⋅−+⋅=′1-13/07/0728Linear yet nonlinear?■ What does it mean for the projection mapping to preserve planes and lines, yet, have a non-linear mapping of z values? How can this be? ■ Consider these examples. As the parameter tis varied from 0 to 1, what geometric object is described?■Linearity of the spaceis preserved, but linearity of the parameterizationis not.■ So, suppose