Visibility

Visibility algorithms are needed to determine which objects in the scene are obscured by other objects. They are typically classified into two groups:

• image-space algorithms
• operate on display primitives. e.g., pixels, scan-lines
• visibility resolved to the precision of the display
• e.g.: z-buffer, Watkin's, ray-tracing
• object-space algorithms
• BSP: binary-space partitions
• variations on painter's algorithm
• worst case: creation of O(N²) primitives from N original primitives

The Z-buffer

Summary of Z-buffer algorithm:

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
    }
  }
}

• commonly used
• memory intensive
• hardware implementation common
• handles polygon interpenetration
• jaggies!

Scan-converting Z

   0 = A x + B y + C z + D,

   z = ( - A x - B y - D ) /C.

   z' = ( - A (x+1) - B y - D ) /C.

   z' = z - A/C.

   x' = x + 1/m.

   z' = z - (A/m + B )/C.

Bilinear interpolation

• equivalent to the above method, without having to solve for plane equation
• incrementally interpolates any type of quantity between known values at the vertices
• colours -- Gouraud shading
• texture coordinates
• surface normals

The A-Buffer

• antialiased, area-averaged, accumulation buffer
• z-buffer: only one visible surface per pixel
• A-buffer: linked list of surfaces

The data for each surface includes:

• RGB
• Z
• alpha
• area coverage percentage
• other surface parameters

BSP trees

• binary space partition
• object space, produces back-to-front ordering
• preprocess scene the scene once to build BSP tree
• traversal of BSP tree is view dependent

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)
   }
}

Depth-sorting Algorithms

• sort polygons by z
• resolve ambiguities where z-extents overlap
• scan-convert polygons in back-to-front order

• bounding rectangles do not overlap in xy-plane
• A is completely behind C
• C is completely in front of A
• projections on xy-plane do not overlap

Scan-line algorithms

• modify scan-conversion to handle multiple polygons
• priority according to Z
• resolve visibility one scanline at a time
• less memory

for each scanline (row) in image
  for each pixel in scanline
    determine closest object
    calculate pixel colour, draw pixel
  end
end  

Ray Tracing

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

• rays cast through image pixels
• solves visibility, some global illumination
• requires efficient intersection tests

O(mnN): m x n pixels, N objects

Hosted by Graphics & Media Lab http://graphics.cs.msu.su

mailto: Laboratory