Hidden Surface Elimination

​

Instructor: Christopher Rasmussen (cer@cis.udel.edu)

​

​

April 12, 2022 ❖ Lecture 16

Outline

• Midterms
• HW #3 due tonight
• Culling non-visible surfaces
• Viewing volume: Clipping
• Backfacing polys
• Occlusion: Z-buffering, painter's algorithms

​

• Marschner: 8.1.3-8.1.6, 8.2-8.2.3, 8.4, 12.4

Clipping: Basic issues

• Testing which side of a clip plane a point is on
• Which side of a line in 2-D
• How to trim primitives that span VV border
• Find the intersection of a line segment and a clip plane

​

from E. Angel

Cohen-Sutherland 2-D line clipping (not in textbook)

• Idea: Consider rectangle (the “viewing area” (VA)) as intersection of 4 half-planes defined by sides

VA

x_min

x_max

y_max

y_min

adapted from F. Pfenning

y < y_max

y > y_min

x > x_min

x < x_max

= ∩

Cohen-Sutherland clipping: Outcodes

• Test a line endpoint p = (x, y) against each of 4 half-planes and record whether it is outside the half-plane or not (T or F)
• These four T/F bits are p’s outcode o(p)

​

from Hill

Cohen-Sutherland clipping

• Outcodes partition plane around the viewing area
• Trivial line clipping cases
• Accept line (p₁, p₂): Both endpoints are inside the rectangle
• In terms of outcodes, this means o(p₁) = FFFF and o(p₂) = FFFF
• Reject line: Both endpoints outside rectangle on same side
• This means both points’ outcodes have a T at the same bit position—e.g., o(p₁) = FTTF and o(p₂) = FFTF

​

from Hill

Cohen-Sutherland clipping

• Tougher cases are what’s left

​

​

​

​

​

​

• Basic idea: Subdivide non-trivial lines by sequentially removing (aka clipping) portions outside rectangle edge lines until what’s left is trivial
• Arbitrary order: Left, right, bottom, top

adapted from E. Angel

Cohen-Sutherland: Algorithm

Computing the intersection point

• What is c = (c_x, c_y)?

​

adapted from Hill

Computing the intersection point

• What is c = (c_x, c_y)?
• Obviously, in this case c_x = x_max and c_y = a_y - d

​

adapted from Hill

Computing the intersection point

• What is c = (c_x, c_y)?
• Obviously, in this case c_x = x_max and c_y = a_y - d
• Noting that e = a_x - x_max and by similar triangles e/Δx = d/Δy , we can compute d = e Δy/Δx and obtain c_y

​

adapted from Hill

Computing the intersection point

• What is c = (c_x, c_y)?
• Obviously, in this case c_x = x_max and c_y = a_y - d
• Noting that e = a_x - x_max and by similar triangles e/Δx = d/Δy , we can compute d = e Δy/Δx and obtain c_y
• A similar approach works for the other clip lines

adapted from Hill

Line clipping: Notes

• C-S’s recursive clipping (up to 4 passes) is not optimal
• E.g., Liang-Barsky method can be faster
• C-S generalizable to 3-D (CVV)
• Instead of 4 half-planes there are 6 half-spaces (3-D volumes)
• Outcode has 6 bits (two more for near and far Z clip planes)

from E. Angel

from Hill

Clipping Triangles

• Four cases for the whole triangle:

​

​

​

​

​

​

​

​

Keep complete triangle

Throw away complete triangle

Keep triangular portion inside

Split quadrilateral portion inside into 2 triangles

Hidden Surfaces: Why care?

• Hidden surfaces are objects inside the viewing volume that should not be seen
• Occlusion: Closer (opaque) objects along same viewing ray obscure more distant ones
• Reasons to remove
• Efficiency: As with clipping, avoid wasting work on invisible objects
• Correctness: The image will look wrong if we don’t model occlusion properly
• Clarity: useful for wireframes

​

from Angel

Wireframe Hidden Line Removal

Backface Culling

• Basic idea: We don’t have to draw polygons on solid objects that face away from the viewer, since front-facing polygons will occlude them
• A back-facing polygon’s normal forms an acute angle with the view vector

​

​

from

Hill

n

Backface Culling on wireframe

from geometricalgebra.org

Polygon normals

• Let polygon vertices v₀, v₁, v₂,..., v_{n - 1} be in counterclockwise order and co-planar
• Calculate normal with cross product:

n = (v₁ - v₀) x (v_{n - 1} - v₀)

• Normalize to unit vector with n/|n|

v₀

v₁

v₂

v₃

v₄

Polygon normals

• Let polygon vertices v₀, v₁, v₂,..., v_{n - 1} be in counterclockwise order and co-planar
• Calculate normal with cross product:

n = (v₁ - v₀) x (v_{n - 1} - v₀)

• Normalize to unit vector with n/|n|

v₀

v₁

v₂

v₃

v₄

Backface culling: Test

• Polygon with normal n is back-facing relative to view direction vector v (camera Z-axis) if n ⋅ v > 0 (because that means angle is less than 90 degrees)
• Can also just use point on polygon p to define

v = p – eye in world coordinates

​

​

​

Backface culling: Test

• Polygon with normal n is back-facing relative to view direction vector v (camera Z-axis) if n ⋅ v > 0 (because that means angle is less than 90 degrees)
• Can also just use point on polygon p to define

v = p – eye in world coordinates

• Available in OpenGL with glEnable(GL_CULL_FACE) and glCullFace(GL_BACK)

​

​

n

Depth tests for HSE

• Backface culling depends only on orientation
• Depth comparisons
• Per "object"?
• Per primitive?
• Per fragment?
• Do we have to do sorting of some kind?

​

​

courtesy of Brent Haley

Z-buffering

• A per-pixel hidden surface elimination technique
• Maintain an image-sized buffer of the nearest depth drawn at each pixel so far
• Only draw a pixel if it’s closer than what’s been rendered already

​

from Hill

Z-buffer: Example

courtesy of DAM Entertainment

Color buffer

Depth buffer

Z-buffer: another example

courtesy of Brent Haley

Z-buffering

• A per-pixel hidden surface elimination technique
• Maintain an image-sized buffer of the nearest depth drawn at each pixel so far
• Only draw a pixel if it’s closer than what’s been rendered already

​

from Hill

Is this sorting?

Z-buffer: Implementation

• Key implementation detail: It is generally unnecessary to independently calculate the depth of each pixel
• Instead, calculate depths of polygon vertices and linearly interpolate depth across pixels in between during rasterization (GPU does this for us)
• E.g., for triangles/quadrilaterals:
• Interpolate vertex depths along edges to get z_left, z_right for a scanline
• Initialize z = z_left, increment along scanline by Δ z = (z_right - z_left) / (x_right - x_left)
• Two stages --> bilinear interpolation

Bilinear interpolation for DEPTH

Z-buffer precision

• Store depth before perspective division or after?
• If before, constant precision over range of depths
• E.g., 8 bits with near/far clip plane difference of 10 meters = ~4 cm depth resolution
• If after (most common), nonlinear function of depth providing more precision closer to viewer
• Z fighting: Objects closer to each other than minimum z discrimination mean interpenetration/improper display is possible
• Example: piece of paper on a desk top
• Minimize with high-precision Z buffer, pushing near clip plane out as far as possible, and/or polygon offset (depth biasing)

Z fighting example

Z fighting example

video courtesy of Udacity

Z-buffering: Notes

• Pros
• Interpolation of pixel values from vertex values is easy to do and a key idea in graphics
• Nearly constant overhead
• Expensive for simple scenes but good for complex ones
• Cons
• Relatively late in pipeline
• Extra storage
• Precision of depth buffer limits accuracy of object depth ordering for large scale scenes (i.e., nearest to farthest objects)
• No perfect scheme for handling translucent objects

Z-buffering in OpenGL

• Parametrize depth buffer by setting GLFW_DEPTH_BITS window hint (default is 24)
• Enable per-pixel depth testing with glEnable(GL_DEPTH_TEST)
• Clear depth buffer by setting GL_DEPTH_BUFFER_BIT in glClear()

​

E.g., in HW #2 multiearth main.cpp

​

Painter’s algorithm

Draw primitives

from back to

front to avoid

need for depth

comparisons

Painter’s algorithm

• Idea: Sort primitives by minimum depth, then rasterize from furthest to nearest
• When there are depth overlaps, do more tests of bounding areas, etc. to see if one actually occludes the other

​

from Angel

• Cyclical overlaps and interpenetration can be a problem