DOC PREVIEW
UVA CS 445 - Hidden Surface Removal

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Greg HumphreysCS445: Intro GraphicsUniversity of Virginia, Fall 2003Hidden Surface Removal(or, visibility)Greg HumphreysUniversity of VirginiaCS 445, Fall 2003Visibility algorithms[Sutherland ‘74]Visible Surface Determination• Problem: Given a set of 3D objects and a viewing specification, determine which lines or surfaces are visible• This is called visible surface(line) determination, or hidden surface(line) removal• Two general approaches:D Image precision D Object precisionImage Precision HSRfor each pixel in the imagedetermine the closest object pierced by the ray through the pixeldraw the pixel in the appropriate color• Brute force approach:D For each pixel, examine all n objects, find which is closest•O(np) where p = #pixels • Needs to be redone if the image is resized2Object Precision HSRfor each object in the worlddetermine the parts of the object that are unobscured by other parts of it or other objectsdraw those parts in the appropriate color• Brute force approach:D For each object, examine all n objects•O(n2) • n << p, so this seems good…• But each computation much more expensive• Tends to be slower in practiceCoherence• Slowly varying object properties: coherenceD Object, Face, Edge, Scanline, Area, Depth, Frame• Exploit coherence whenever possibleD Reuse calculationsD Complex math Æ simple differencesPerspective Transformations• Depth comparisons are typically performed after the perspective transformation• Since we’re looking down the z axis, two points are now on the same ray if x1=x2and y1=y2• The perspective transformation preservesD Relative depthD Straight linesD PlanesExtents• An object’s screen extent is an axis aligned rectangle3Bounding Volumes• Can be used to trivially reject objectsD If bounding volumes don’t intersect, objects don’t eitherD 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 hierarchies have implicit extents and object coherence• If two hierarchical objects fail to intersect, no need to test their childrenBuildingFloor 1 Floor 2 Floor 3 Floor 4Room 1 Room 2 Room 34Visible Line Determination• Most VLD algorithms operate in object space• Input: description of a 3D scene• Output: a list of visible line segments ready for displayRobert’s Algorithm• Assume convex polyhedra• Perform backface culling• Test each remaining edge against all other polyhedraD Use extent testing to trivially reject most polyhedraD Each polyhedron either completely obscures the line, or splits it into 1 or 2 lines• Use linear programming to figure out where a ray from the eye to the line in question grazes each polyhedronAppel’s Algorithm• Relax the assumption about convex polyhedra• Define quantitative invisibility (QI) of a pointD # of front-facing polygons that obscure ot• When a line passes behind a front facing polygon, its QI is increased by one, and when it passes out it is decreased by one0121010Contour Lines• contour line:D An edge shared between a front and back facing polygonD The unshared edge of a front facing polygon• QI changes when lines pass behind a contour edge• Intersect the contour edge with the triangle formed by the endpoints of the line and the view point5The Z Buffer Algorithm• Image precision hidden surface removal algorithm • Very simple to implement• Use an additional buffer to hold depth values:D Render primitives in arbitrary orderD Record their depths in the depth bufferD If the depth of a pixel about to be drawn is greater than what’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+=Why Is Z So Popular?• AdvantagesD Simple to implement in hardware» One more interpolator» Chunk of memory» One more comparisonD Supports non-polygonal primitivesD Unlimited scene complexityD Depth values can be saved for later use, or other uses• DisadvantagesD Extra memory and bandwidthD Waste time drawing hidden objectsD Z precision errors lead to depth aliasingList Priority Algorithms• List priority algorithms define a visibility ordering for objects, ensuring that a correct picture will result if the 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:6Depth Sorting• The Depth Sort algorithm performs three conceptual steps:D Sort all polygons according to the smallest (farthest) zcoordinate of eachD Resolve any overlapping z extent ambiguities, splitting polygons if necessaryD Scan convert each polygon in order of ascending z (back to front)• If we ignore the second step, this is called the painter’s algorithmResolving Depth Ambiguities• Call P the polygon at the end of the list, and Q the polygon about to be added behind P• 5 questions, in order of complexity:D Do the polygons’ x extents not overlap?D Do the polygons’ y extents not overlap?D Is P entirely on the opposite side of Q’s plane from the viewpoint?D Is Q entirely on the same side of P’s plane from the viewpoint?D Do the projections of the two polygons onto the (x,y) plane not 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 swappedD Ask questions 3 and 4 again, in the other order• If either of these new tests succeeds,


View Full Document

UVA CS 445 - Hidden Surface Removal

Documents in this Course
Lighting

Lighting

49 pages

Color

Color

20 pages

Clipping

Clipping

10 pages

Shadows

Shadows

95 pages

Color

Color

37 pages

Radiosity

Radiosity

49 pages

Clipping

Clipping

59 pages

Assign 3

Assign 3

28 pages

Splines

Splines

17 pages

Color

Color

17 pages

Load more
Download Hidden Surface Removal
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Hidden Surface Removal and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Hidden Surface Removal 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?