Hidden Surface Removal

Visible Surface
 Invisible Primitives

▪Why might a polygon be invisible?

○Polygon outside the field of view
○Polygon is backfacing
○Polygon is occluded by object(s) nearer the viewpoint

▪For efficiency reasons, we want to avoid spending work on

polygons outside field of view or backfacing

▪For efficiency and correctness reasons, we need to know

when polygons are occluded
 HSR algo classes
▪Three classes of algorithms
○“Conservative” visibility testing: only trivial reject – does not give final answer!
▪e.g., back-face culling, canonical view volume clipping, spatial subdivision
▪have to feed results to algorithms mentioned below

○Image precision – resolve visibility at discrete points in image

▪sample model, then resolve visibility – i.e., figure out which objects it makes sense to
compare with
▪e.g., ray tracing, or Z-buffer and scan-line algo.

○Object precision – resolve for all possible view directions from a given eye
point
▪irrespective of view direction or sampling density
▪resolve visibility exactly, then sample the results
▪e.g., 3-D depth sort, BSP trees
Image Precision
Object Precision
 Outline

1.Back- Face Culling

2.z- Buffer (Depth- Buffer)
3.Depth- Sort
4.BSP- Tree
5.Scanline Algorithm
Back Face Culling
Removing Back Faces
 Back-Face Culling

▪On the surface of a closed manifold, polygons whose

normals point away from the camera are always
occluded:
Plane Normal . (Point on plane - COP) > 0 -----→ Backface
 Back-Face Culling

▪On the surface of a closed manifold,

polygons whose normals point away from
the camera are always occluded:
 Back-Face Culling - Problems

▪On the surface of a closed manifold,

polygons whose normals point away from
the camera are always occluded:

Note: backface culling

alone doesn’t solve the
hidden-surface
problem!
 Back-Face Culling - Problems

▪one polyhedron may obscure another

 Back-Face Culling - Advantages

▪On average, approximately one-half of a

polyhedron’s polygons are back-facing.
▪Back-Face culling halves the number of
polygons to be considered for each pixel in
an image precision algorithm.
 Plane-Half Space interpretation

○A plane can be defined by a normal N and any point, P0, on the plane:
▪plane satisfied by NxPx + NyPy + NzPz+ D= 0
▪rewrite as (N • P) + D = 0
▪pick another point, P; then we can say N •(P – P0) = 0
▪notice that –N •P0 is constant; let’s call it D
▪solve for D using any point on the plane.

○Plane divides all points into two half-spaces

▪(N • P) + D = 0, P is on plane
▪(N • P) + D > 0, P is in positive half-space
▪(N • P) + D < 0, P is in negative half-space

○Polygon faces away for eye points in negative half-space

▪if (N • Eye) + D < 0, discard
 Occlusion

▪For most interesting scenes, some polygons will

overlap:

▪To render the correct image, we need to determine

which polygons occlude which
Painters Algorithm
 Painter’s Algorithm

▪Simple approach: render the polygons from back to

front, “painting over” previous polygons:

○Draw blue, then green, then pink

▪Will this work in general?
 Painter’s Algorithm: Problems

▪Intersecting polygons present a problem

▪Even non-intersecting polygons can form a cycle with no
valid visibility order:
 Z-Buffer – Image Precision

○Requires two “buffers”

Intensity Buffer
—our familiar RGB pixel buffer
—initialized to background color
Depth (“Z”) Buffer
—depth of scene at each pixel
—initialized to far depth

○Polygons are scan-converted in arbitrary order. When pixels

overlap, use Z-buffer to decide which polygon “gets” that pixel
 Z-Buffer

Algorithm:
▪Initialize:
○Each z- buffer cell ⇐ Max z value
○Each frame buffer cell ⇐ background color
▪For each polygon:
○Compute z( x, y), polygon depth at the pixel (x, y)
○If z( x, y) < z buffer value at pixel (x, y) then
▪z buffer( x, y) ⇐ z( x, y)
▪pixel( x, y) ⇐ color of polygon at (x, y)
 Z-Buffer

255 255 255 255 255 255 127

255 127
255 127 127 127 127
127 127
1 127 127 127 127 127 255
2
7
255 255 255 255 255 255 255
127 255
127 127 127 127 127
127 127 127 127 127 127 255 255

255 255 255 255 255

+255 255 255
= 127 127 127 127 127 255 255 255
127 127 127 127 127

255 255 255 255 255 255 255 255 127 127 127 127 255 255 255 255
127 127 127 127

255 255 255 255 255 255 255 255 127 127 127 255 255 255 255 255
127 127 127
127 127 127 127 127 127 127 255 127 127 127 127 127 127 127 255
255 255 255 255 255 255 255 255 127 127 255 255 255 255 255 255

127 127
127
255 127
255 127
255 127
255 127
255 127
255 255
255 255
255 127
127 127
255 127
255 127
255 127
255 127
255 255
255 255
255

127
255 127
255 127
255 127
255 127
255
+255 255
127 255 = 127
255 127
255 127
255 127
255 127
255 255 255 255

127 127 127 127 255 255 255 255 63 127 127 127 255 255 255 255
63

127 127 127 255 255 255 255 255 63 63 127 255 255 255 255 255
Above: example using
63 integer
63Z-buffer with near = 0, far = 255
127 127 255 255 255 255 255 255 63 63 63 255 255 255 255 255

63 63 63
127 255 255 255 255 255 255 255 63 63 63 63 255 255 255 255

255 255 255 255 255 255 63

255 63
255 63 63 63 63 63 63 63 255 255 255

63 63 63 63 63
 Computing Z values

▪How do we compute it efficiently?

 Computing Z values
▪How do we compute it efficiently?
○Answer is simple: do it incrementally!
○Remember scan conversion/polygon filling? As we move along Y-axis,
track x position where each edge intersects scan-line
○do same thing for z coordinate using “remainder” calculations with y-z
slope

○Once we have za and zb for each edge, can incrementally calculate zp

as we scan. Did something similar with calculating color per pixel...
(Gouraud shading)
 Z-Buffer: Advantages

○Simplicity lends itself well to hardware implementations:

FAST
▪used by all graphics cards
○Polygons do not have to be compared in any particular
order: no presorting in z necessary, big gain!
○Only consider one polygon at a time
○Z-buffer can be stored with an image; allows you to correctly
composite multiple images (easy!) without having to merge
models (hard!)
○Can be used for non-polygonal surfaces
 Z-Buffer: Disadvantages

○A pixel may be drawn many times

○High amount of memory required
○Lower precision for higher depth
 Binary Space Partioning (BSP) Tree

▪Provides spatial subdivision and draw order

▪Split space with any line (2D) or plane (3D)

▪Divide and conquer:

○to display any polygon correctly, display all polygons on “far” (relative to viewpoint)
side of polygon, then that polygon, then all polygons on polygon’s “near” side

▪Trades off view-independent preprocessing step (extra time and

space) for low run-time overhead each time view changes
 BSP Tree

▪Perform view-independent step once each time scene changes:

▪recursively subdivide environment into a hierarchy of half-spaces by dividing polygons in
a half-space by the plane of a selected polygon
▪build a BSP tree representing this hierarchy
▪each selected polygon is the root of a sub-tree
▪An example:

Initial
Scene
 BSP Tree

Step-1: Choose any polygon (e.g., polygon 3) and subdivide

others
by its plane, splitting polygons when necessary
 BSP Tree

Step-2: Process front sub-tree

recursively
 BSP Tree

Step-3: Process back sub-tree

recursively
 BSP Tree

An alternative BSP tree with polygon 5 at the root

 BSP Tree

▪Painter’s Algorithm with BSP Trees

○Each face has form Ax + By + Cz + D
○Plug in coordinates and determine
▪Positive: front side
▪Zero: on plane
▪Negative: back side
○Back-to-front: postorder traversal, farther child first
○Front-to-back: inorder traversal, near child first
○Do backface culling with same sign test
○Clip against visible portion of space (portals)
 Pseudo code for Building BSP Tree

▪Pseudocode for Building BSP Tree

typedef struct {
polygon root;
BSP_tree *backChild, *frontChild;
} BSP_tree;
BSP_tree *BSP_makeTree(polygon *polylist)
polygon root, *backList, *frontList, p, backPart, frontPart;
if (polyList == NULL) return NULL;
else
root = BSP_selectAndRemovePoly( &polyList );
backList = frontList = NULL;
for (each remaining polygon p in polylist)
if (polygon p in front of root)
BSP_addToLkist(p, &frontList);
else if (polygon p in back of root)
BSP_addToLkist(p, &backList);
else
BSP_splitPoly( p, root, &fronPart, &backPart);
BSP_addToList(frontPart, &frontList);
BSP_addToList(backPart, &backList);
return BSP_combineTree(BSP_makeTree(frontList), root,
BSP_makeTree(backList)
 Pseudo code for Building BSP Tree

void BSP_displayTree(BSP_tree *tree) {

if (tree != NULL) {
if (viewer is in front of tree->root) {
/*Display back child, root, and front child */
BSP_displayTree(tree->backChild);
displayPolygon(tree->root);
BSP_displayTree(tree->frontChild);
} else {
/*Display front child, root, and back child */
BSP_displayTree(tree->frontChild);
displayPolygon(tree->root);
BSP_displayTree(tree->backChild);
}
}
}
 xm Scan-Line Algorithm
▪Image precision algorithm
▪Renders scene scan line by scan line
▪Maintain various lists
○Edge Table
○Active Edge Table
○Polygon Table
○Active Polygon Table
 Scan-Line Algorithm

○Edge Table (ET) (for non-horizontal edge)

▪Sorted into buckets based on each edge’s smaller y-
coordinate
▪Within buckets are ordered by increasing x-coordinate of
their lower end point.
Δx=Δy/m
xat ymin ymax Δy=1
Δx ID

–Polygon Table (PT)

in-
ID Plane eqn. Shading Info
out
 Scan-Line Algorithm

○Active Edge Table (AET)

▪Stores the list of edges intersecting current scanline
in increasing order of current x-coordinate

ymax xA Δx

–Active Polygon Table (APT)

✴At each x-scan value this table contains the list
of polygons whose in-out flag is set to true
 Scan-Line Algorithm
y
B E
γ+
2γ+
1 γ
D C
β
F
α

A x
AET contents
Scan line Entries
α AB AC
β AB AC FD FE
γ, γ+1 AB DE CB FE
γ+2 AB CB DE FE
 Scan-Line Algorithm
▪Initialization
○Initialize the AEL to empty
○Initialize each screen pixel to bk-color
○Set y to the first nonempty cell value in edge
table
 Scan-Line Algorithm
▪For each scan line y do
○AEL ← AEL∪ Edges from ET that are in current scanline
○sort AEL in order of increasing xA
○For each edge e (except last one) in AEL do
▪invert in-out flag of the polygon that contains e
▪Update APL
▪Determine polygon p in APL with smallest z value at (e.xA, y)
▪The pixels from e upto next edge in AEL are set to the color of p
○AEL ← AEL⎯ Edges from ET with ymax = y
○for each edge e in AEL do e.xA = e.xA + e.Δx
○Sort AEL on xA
 Depth-Sort Algorithm

▪Initially sort by smallest (farthest) Z

 Depth-Sort Algorithm
▪How to find overlapping polygons?
○examine the z-extents
▪Checking (to test whether polygon P obscures
polygon Q):
1.Are the x-extents of P and Q disjoint?
2.Are the y-extents of P and Q disjoint?
3.Is P entirely on the opposite side of Q’s plane from the eye?
4.Is Q entirely on the same side of P’s plane as the eye?
5.Are the projections of P and Q on the screen are disjoint?
 Depth-Sort Algorithm

▪If answers to all of the above is NO, we assume that P

actually obscure Q. Therefore test whether Q can be scan
converted before P.
3'. Is Q entirely on the opposite side of P’s plane from the eye?
4'. Is P entirely on the same side of Q’s plane as the eye?
▪If the answers are NO, then split.
▪Consider the fllowing case:

▪So do not try steps 3' and 4‘.

 Depth-Sort Algorithm

▪Advantages:
○Fast enough for simple scenes
○Fairly intuitive

▪Disadvantages
○Slow for even moderately complex scenes
○Hard to implement and debug
○Lots of special cases
 Ref.

▪FV: 15.2.4, 15.4, 15.5.1, 15.5.2, 15.6