[Angel p388-389; Foley p649-651]
Visibility is the problem of determining which objects, or parts of objects, are visible to the eye as opposed to being obscured by other objects. Visibility algorithms are typically classified into two groups:
[Angel p391-393; Foley p668-672]
for all i,j { Depth[i,j] = MAX_DEPTH Image[i,j] = BACKGROUND_COLOUR } for all polygons P { for all pixels in P { if (Z_pixel < Depth[i,j]) { Image[i,j] = C_pixel Depth[i,j] = Z_pixel } } }
Characteristics of the z-buffer algorithm:
When does the z-buffer perform poorly?
Scan conversion proceeds much like the 2D case, only now appropriate Z-values must be generated. In order to determine z = f(x,y), we begin with the plane equation of the polygon in device coordinates as given by
0 = A x + B y + C z + D,
We can solve for z as
z = ( - A x - B y - D ) /C.
The value of z at the adjacent pixel (x+1, y) is
z' = ( - A (x+1) - B y - D ) /C.
or
z' = z - A/C.
Generating z-values when travelling across a scanline is thus simple once the z-value is known at the left edge of the polygon. This can also be calculated in an incremental fashion, knowing that
x' = x + 1/m.
The new left edge of the polygon is (x+1/m, y+1) and we can determine the difference in z as being
z' = z - (A/m + B )/C.
The data for each surface includes:
[Angel p466-468; Foley p675-680]
BSPtree *BSPmaketree(polygon list) {
choose a polygon as the tree root
for all other polygons
if polygon is in front, add to front list
if polygon is behind, add to behind list
else split polygon and add one part to each list
BSPtree = BSPcombinetree(BSPmaketree(front list),
root,
BSPmaketree(behind list) )
}
DrawTree(BSPtree) {
if (eye is in front of root) {
DrawTree(BSPtree->behind)
DrawPoly(BSPtree->root)
DrawPoly(BSPtree->front)
} else {
DrawTree(BSPtree->front)
DrawPoly(BSPtree->root)
DrawTree(BSPtree->behind)
}
}
[Angel p393-396; Foley p672-675]
Ambiguities can be resolved in several ways.
|
If these fail, exchange the order of the surfaces and repeat. If this still fails, the polygons can be intersected to split one of the polygons if necessary. In the worst case, the algorithm can generate O(n^2) new polygons.
[Angel p396; Foley p680-684]
for each scanline (row) in image for each pixel in scanline determine closest object calculate pixel colour, draw pixel end end
[Angel p596-605; Foley p701-712]
for each pixel on screen determine ray from eye through pixel find closest intersection of ray with an object cast off reflected and refracted ray, recursively calculate pixel colour, draw pixel end