1Greg HumphreysCS445: Intro GraphicsUniversity of Virginia, Fall 2004Hidden Surface Removal(or, visibility)Visibility algorithms[Sutherland ‘74]Visible Surface Determination• Problem: Given a set of 3D objects and a viewingspecification, determine which lines or surfaces arevisible• This is called visible surface(line) determination, orhidden surface(line) removal• Two general approaches: Image precision Object precisionImage Precision HSRfor each pixel in the imagedetermine the closest object pierced bythe ray through the pixeldraw the pixel in the appropriate color• Brute force approach: For each pixel, examine all n objects, find which is closest• O(np) where p = #pixels• Needs to be redone if the image is resizedObject Precision HSRfor each object in the worlddetermine the parts of the object thatare unobscured by other partsof it or other objectsdraw those parts in the appropriate colorBrute force approach:For each object, examine all n objectsO(n2)n << p, so this seems good…But each computation much more expensiveTends to be slower in practiceCoherence• Slowly varying object properties: coherence Object, Face, Edge, Scanline, Area, Depth, Frame• Exploit coherence whenever possible Reuse calculations Complex math simple differences2Perspective Transformations• Depth comparisons are typically performed after theperspective transformation• Since we’re looking down the z axis, two points arenow on the same ray if x1=x2 and y1=y2• The perspective transformation preserves Relative depth Straight lines PlanesExtents• An object’s screen extent is an axis aligned rectangleBounding Volumes• Can be used to trivially reject objects If bounding volumes don’t intersect, objects don’t either If bounding volumes do intersect, more work is required• Bounding volumes don’t have to be rectangular;spheres are common as well• How “good” is a particular bounding volume?Back-face detectionQ: How do we test for back-facing polygons?A: Dot product of the normal and view directions.A2: Negative ‘z’ coordinate of normal in eye spaceback-facingpolygonQ: When does this method break down?A: Object not closed. What about interreflections?2D Backface ExampleRed edges are not drawnBlue edges are drawnViewing directionHierarchical Objects• Objects that can neatly be divided into hierarchieshave implicit extents and object coherence• If two hierarchical objects fail to intersect, no need totest their childrenBuildingFloor 1 Floor 2 Floor 3 Floor 4Room 1 Room 2 Room 33Visible Line Determination• Most VLD algorithms operate in object space• Input: description of a 3D scene• Output: a list of visible line segments ready fordisplayRobert’s Algorithm• Assume convex polyhedra• Perform backface culling• Test each remaining edge against all other polyhedra Use extent testing to trivially reject most polyhedra Each polyhedron either completely obscures the line, orsplits it into 1 or 2 lines• Use linear programming to figure out where a rayfrom the eye to the line in question grazes eachpolyhedronAppel’s Algorithm• Relax the assumption about convex polyhedra• Define quantitative invisibility (QI) of a point # of front-facing polygons that obscure ot• When a line passes behind a front facing polygon, itsQI is increased by one, and when it passes out it isdecreased by one0121010Contour Lines• contour line: An edge shared between a front and back facing polygon The unshared edge of a front facing polygon• QI changes when lines pass behind a contour edge• Intersect the contour edge with the triangle formedby the endpoints of the line and the view pointThe Z Buffer Algorithm• Image precision hidden surface removal algorithm• Very simple to implement• Use an additional buffer to hold depth values: Render primitives in arbitrary order Record their depths in the depth buffer If the depth of a pixel about to be drawn is greater thanwhat’s already there, throw it awayZ Buffer Example0 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 05 5 5 5 5 5 55 5 5 5 5 55 5 5 5 55 5 5 55 5 55 5500 00 0 00 0 0 00 0 0 0 00 0 0 0 0 00 0 0 0 0 0 00 0 0 0 0 0 0 05 5 5 5 5 5 55 5 5 5 5 55 5 5 5 55 5 5 55 5 55 55+=00 00 0 00 0 0 00 0 0 0 00 0 0 0 0 00 0 0 0 0 0 00 0 0 0 0 0 0 05 5 5 5 5 5 55 5 5 5 5 55 5 5 5 55 5 5 55 5 55 5534 35 4 36 5 4 37 6 5 4 38 7 6 5 4 300 00 0 00 0 0 03 0 0 0 05 4 3 0 0 07 6 5 4 3 0 00 0 0 0 0 0 0 05 5 5 5 5 5 55 5 5 5 5 55 5 5 5 55 5 5 56 5 57 68+=4Why Is Z So Popular?• Advantages Simple to implement in hardware» One more interpolator» Chunk of memory» One more comparison Supports non-polygonal primitives Unlimited scene complexity Depth values can be saved for later use, or other uses• Disadvantages Extra memory and bandwidth Waste time drawing hidden objects Z precision errors lead to depth aliasingList Priority Algorithms• List priority algorithms define a visibility ordering forobjects, ensuring that a correct picture will result ifthe objects are drawn in this order• If no objects overlap in z, just sort on z• Even if they overlap, we may still be able to sort on z• Problems for cyclical objects:Depth Sorting• The Depth Sort algorithm performs three conceptualsteps: Sort all polygons according to the smallest (farthest) zcoordinate of each Resolve any overlapping z extent ambiguities, splittingpolygons if necessary Scan convert each polygon in order of ascending z (backto front)• If we ignore the second step, this is called thepainter’s algorithmResolving Depth Ambiguities• Call P the polygon at the end of the list, and Q thepolygon about to be added behind P• 5 questions, in order of complexity: Do the polygons’ x extents not overlap? Do the polygons’ y extents not overlap? Is P entirely on the opposite side of Q’s plane from theviewpoint? Is Q entirely on the same side of P’s plane from theviewpoint? Do the projections of the two polygons onto the (x,y) planenot overlap?These Five Questions…• If the answer to any of these five questions is true, Pdoes not obscure Q, and we can proceed• If they all fail, assume for the moment that Pobscures Q, and see if P and Q need to be swapped Ask questions 3 and 4 again, in the other order• If either of these new tests succeeds, we put Q at thehead of the list, and
View Full Document
Unlocking...