CS 184: COMPUTER GRAPHICS

QUESTIONS OF THE DAY:

RE:  A#1:  What is the probability that two students draw exactly the same polygon in their windows ?

A simpler question: How many different triangles can you draw in the plane ?
( How many separate 1-variable "sliders" would you have to provide to cover all cases ? )
( How many different variables would you have to randomize in a test generator ? )
This is called the "Degrees Of Freedom" (DOF) of such a system.

With this definition: How many DOFs are there for:
1.)  all equilateral triangles in the plane ?
2.)  all rectilinear bricks in 3D space ?
3.)  all circles in the plane ?
4.)  all infinitely long lines in 2D ?

Where do such questions come up in the field of computer graphics (CAD, Robotics ...) ?

PREVIOUS < - - - - > CS 184 HOME < - - - - > CURRENT < - - - - > NEXT

NOTE: Discussion Section #3 (Tue 10-11am) has been dropped.

Lecture #5 -- Wed 2/4/2009.

Polygon Rasterization -- the nitty gritty details.

Crucial Concepts from Last Lecture:

Linear interpolation is a key operation not just for clipping, but also for morphing, for shading, and for the efficient calculation of splines and subdivision surfaces.

Sweeping Scan-line Approach:  One polygon at a time:

Datastructures:
    -- Scene Graph -- Display List -- Edge Table -- Active Edge List.
Preprocessing:
    -- Bucket-sort (in y) all polygon edges into the Edge Table. Process the scan-line buckets from bottom to top.
    -- Inserting edges into scan-line buckets (details)
Scan-line Processing:
    -- For the current swath of pixels update the Active Edge List of all edges that cross the current scan line.
    -- Details of scan-line processing on active edge list
    -- Turn on pixesl that have their sampling points on active inside spans.
        (For convenience we chose the pixel sampling point to be the lower left corner, thus avoiding to have to add/subtract 0.5 all the time.)

Linear interpolation is a key operation! We use it to efficiently update the position (and color and z-value) of the polygon edges in the scan-line algorithm,
-- and then again to efficiently calculate the values needed at each pixel location. Specifically:
Gouraud Shading (= linear (color, brightness) interpolation between vertices)
Z-buffer Algorithm (to find the "top" visible polygon; calculate height incrementally along scan line)
Linear Interpolation in Scan-Line Algorithm

Polygons can also be processing all psimultaneously:
Extra Notes on Sweep-Line-Based Hidden Feature Elimination

The devil is in the details !

Dealing with possible coincidences needs all the attention (and produces most of the bugs).
Here is a more detailed description of a sweeping scan-line algorithm.

New Graphics Concepts in A#2:

Picking

Find what is under the cursor!  Like target shooting in a CG game:  How do you know what, if anything, you hit with your blaster ??
A#2: Test each polygon vertex whether it is "close enough" to the mouse!

Abstractions, LODs, Bounding Boxes

It is useful to have some simple Bounds around objects and groups in a scene, they can serve as:
-- conservative (pessimistic) size estimates (e.g. for culling) to reduce the amount of computation that needs to be done n(e.g., clipping, rendering collision detection...)
-- crude abstractions ("place-holders", "imposters") for displaying that piece of the scene hierarchy at lower LOD (level-of-detail).
Such bounds should be easy to construct and easy to use.

Axis-Aligned Bounding Boxes (AABB):
a rectangle with diagonal corners (xmin,ymin), (xmax, ymax).
These AABB's have some inefficiencies: e.g., around a diagonal needle.
Also, with every (rotated) use in a hierarchy, the AABB may grow.

Alternatives to Bounding Boxes:
Optimally oriented bounding boxes (OOBB):  are more efficient but more difficult to determine.
Bounding circles or spheres: have rotation-independent size, but are not so easy to find either.
Convex hulls: can be constructed efficiently, but may have many vertices, --> loss of efficiency.

Hierarchy, transformations, and bounding boxes will important components in Assignment #3.

2D Transforms (Introduction):  Viewport Mapping

Transformations are a key element of computer graphics !

The Various Coordinate Systems in the Classical Rendering Pipeline:
World to screen transforms - Overview   (This is valid in some form for all rendering environments).
And what it does to a world of triangles.

In assignment A#2 you are asked to make the display window scalable (e.g., by dragging one of its corners).
But you don't want your carefully designed fantasy polygon to be distorted -- just scaled uniformly to the largest sixe that fits into the current window.
Thus you have to determine what is the largest rectangle with the aspect ratio of your original drawing window (= square) that fits into the given window.

Conceptually we calculate two transformation steps:  Window (your original 2D sceene) ==> NDC (normalized Device coordinates) ==> Viewport (area on display).
If we were to just scale the x- and y-directions individually, so that the content of window completely fills viewport, we might get affine distortions, if the aspect ratios of window and viewport are different.
To avoid such distortion, we choose the smaller of the two scale factors and apply it uniformly to both axes.

Matrix Representation of Translations; Homogeneous Coordinates

Transformations are conveniently described and applied with the use of matrices. This yields a powerful formalism exists for combining the effects of several transformations.
(You should  brush up on: Matrix multiplication;  Rotation Matrices; -- if you are a liitle rusty, go back to your linear algebra text!)

Now we also want to do Translation with Matrices. This is not straight-forward since translation is not a "linear operation"!
Linear transforms: {T(aX + B) = a T(X) + b } always leave origin in place; T(0) = 0.
--> We use a clever hack via homogeneous coordinates:
Homogenizing = introduce an extra component: w :  (x, y) ==>  (wx, wy, w)
We can recover the  regular cartesian coordinates by a division with w  (w<>0);
this corresponds to a cut of the homogeneous line with the w=1 plane.
Matrix operation is still linear in d+1 dimension (origin stays in place),
but we are only interested in (hyper-)plane  w=1,
Show the basic translation matrix, demonstrate that it works. Show all 2D transforms for use with homogeneous column vectors.
Distinguish: Rigid-body transforms  (rotate and translate) and  Affine transforms  (scaling and shear).

Issues arising from use of homogeneous coordinates:

Efficiency ?: -- Number of arithmetic operations may increase!
Yields ease of composition: -- No need to separate out the translation part.
Abstraction from Implementation: however it is done -- hide it from user !  (e.g., row vectors versus column vectors).
 

DOF: Degrees of Freedom -- another important, general concept!

Suppose, you want to make a randomized generator that produces line segments to test your line-clipping algorithm.
All possible line segments should have a chance of being generated.
How many variables need to be randomized ?
Or, if you want to make an interactive generator applet, -- how many individual (one-parameter) sliders would you need ?
Or, if you wanted to sample a given "world" with all possible camera "windows", -- How many parameters does this require ?
-- Or how many DOFs does this have ?

Similarly, how many DOFs are there for the specification of all possible ...

How could each of these systems be implemented practically with the minimum number of sliders indicated by the DOFs?

Reading Assignments:

Study: ( i.e., try to understand fully, so that you can answer questions on an exam): 
Shirley, 2nd Ed: Ch 2.10; Ch 6.1, 6.3.

Programming Assignments 1 and 2:

Both must be done individually.
Assignment #1 is due (electronically submitted) before Thursday 2/5, 11:00pm.
Assignment #2 is due (electronically submitted) before Thursday 2/12, 11:00pm.

I strongly recommend that you should be done with your assignments by Wednesday,
so that you can then focus on the new one and pay attention to what I might say in class about it.
The "extension" to Thursday should only be seen as an emergency measure.

PREVIOUS < - - - - > CS 184 HOME < - - - - > CURRENT < - - - - > NEXT
Page Editor: Carlo H. Séquin