naive implementation:
  1. use rays to sample the viewing area - generally a grid of samples corresponding to the centers of pixels
  2. for each ray:
  3. interpolate between the color values to create a continuous image
  4. raytrace: shoot more rays for better shading (to detect shadows, reflections, refraction)

Why it's everybody's favorite:

Why it's the underdog:  
use: first step in high-quality shading; topic in graphics classes
pre-processing: none
coherence: none
scene footprint: total
memory footprint: an object and a ray at a time
overdraw: total; occluded objects are treated no differently from non-occluded, except that they're never shaded.
clipping: not an issue
transparent objects: yes

many, many optimizations!

Spatial Subdivision (Glassner, 1984)
preprocessing: build the k-d tree

figure out the cell of the eyept
for each ray {
    fire the ray at all the objects in this cell
    if it hits, we're done
    if it misses, go to the next cell

use: when most of the objects are occluded or clipped
    "world-space" coherence - the world can be sampled into discrete spaces
    object coherence - objects can be placed into an area of space
scene footprint: minimal; only the cells (and their objects) that each ray goes through, which is generally a tight superset of all visible objects.
memory footprint: requires a cell, its objects, and a ray at a time
overdraw: all the objects that miss the ray along the way, or are occluded in the final cell.

Area Subdivision
Use Warnock area subdivision
When you've subdivided down to 1x1 case, you've got some list of incident objects.
Shoot a ray at each of those objects to determine the closest one.

use: scenes with low depth complexity
coherence: image-space; objects that are separable in x and y are not compared.
scene footprint: total
memory footprint: list of objects for a given subfrustum
overdraw: invisible objects are only considered for the pixels they would show up in, if they weren't occluded.

Spatial + Area Subdivision, aka Frustum Casting (Teller, Alex 98)
Rather than doing k-d tree traversal and object-ray intersect tests a ray at a time, do them for a frustum of rays at a time.


operating unit: polyhedron created by the intersection of a frustum with a k-d cell that we term the current cell of the frustum

Try to do operations (intersect, k-d tree traverse) for all rays passing through that polyhedron
Maintain a queue of work to be done in the form of these frustum/cell combinations.

start case: queue contains only the view frustum, associated with the cell of the eye point

invariant 1: the corner and all interior rays of the frustum pass through its current cell.
invariant 2: none of the rays inside the frustum intersect any objects before those in the current cell
        intuitively, the frustum from the eye point up to the current cell is completely empty space.

for each frustum f on the queue {
                c = frustum's current cell
                get the list of objects from c that are also inside f
                    (win: objects tested against groups of rays at a time)
                if there are no such objects,
                        consider the 4 corner rays of the frustum
                        we know each ray passes through the current cell, and on to somewhere else
                        figure out where those 4 corners go
                        if all corners go to the same cell,
                            set the frustum location to the next cell, and repeat the process
                                (win: only had to do 4 cell traversals instead of one for each ray)

                otherwise, if the corners go into different cells or if there are objects inside both f and c,
                           subdivide into 4 subfrusta, a la Warnock. Their cell location == our own.
                           Place them on the queue to be done
                                (win: objects divided in screen space or we're able to sample the k-d tree to maintain the largest possible frustum size)

use: real-time walkthrus of large scenes
pre-processing: create the k-d tree
coherence: object, image-space, world-space
scene footprint: all objects in visible cells
memory footprint: frustum and current cell's incidence list
overdraw: occluded/clipped objects in visible cells