Raycasting

1. use rays to sample the viewing area - generally a grid of samples corresponding to the centers of pixels
2. for each ray:
• shoot the ray at each object in the scene; if the ray hits and it's the closest hit so far, keep it
• shade according to the closest object the ray hit
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:

• easy to implement, to understand
• free clipping - you're only shooting rays inside the view frustum
• easy to extend to new objects - only need a ray-object intersect test
• flexible quality - do more work and you get a better picture
• highly parallelizable

• O(nxy)
• linear in the # of objects
• very resolution-dependent
• in the technical language, slow.

many, many optimizations!

runtime:
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
coherence:
    "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.

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.

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