We study several algorithms for deleting hidden surfaces of objects, including
1) Normal-vector face culling -- and the necessity to compute surface normal vectors
2) The depth (Z) buffer technique -- and the equation of a plane
3) Ray tracing -- and how to tell if a ray hits a sphere
It stands to reason that we don't want to draw faces that are "facing away from us." By definition, we always enumerate the vertices of a polygon in counterclockwise order as seen from its intended front side. We also are always looking down the positive Z axis (at least in our left handed viewing system.). Thus, only polygons whose normal has a negative Z value, should be scan converted.
So, how do we calculate that normal? Take a sequence of three vertices (call them A, B, C) and construct two vectors P=AB and Q=BC. Now, P x Q is N and that's a surface normal.
Face culling is not sufficient to prevent jumbled pictures in general; but if you are drawing a single convex solid (e. g. a cube) which you know to be in front of its background scene, it will suffice.
For quiz purposes, think about each of the relevant words: single, convex, jumbled picture. What do you think a jumbled picture might look like?
Now that RAM is cheap, the logical thing to do is simply to assign to each pixel both a color (8 or 24 bit, usually) and a depth (16 or 32 bit, usually.) How can we rapidly compute the depth of every pixel? We have to do this in the scan conversion process, in some highly efficient manner.
Well, we need to know the equation of the plane containing the polygon. From this, if we know the x and y of a point (which we obviously know when we're scan converting it) we can compute the point's z.
Consider the classic equation for a plane:
ax + by + cz + d = 0If we temporarily let d=0, we can see that this defines a set of points that includes the origin. That is, (x, y, z)=(0,0,0) is one solution of the equation.
If we let a=b=c=1 and d=-10, we realize that the points (10,0,0), (0,10,0) and (0,0,10) are on the plane. So in some skewed sense, d must measure the distance of the plane from the origin.
If we think of N= (a,b,c) as a vector and P=(x,y,z) as another vector, then we see that we can write the equation of the plane through the origin as N.P=0. Now P is any point in the plane (or equivalently, a vector from the origin to the corresponding point. So, N sounds very much like it's a vector perpendicular to all possible values of P (the dot product of two perpendicular vectors is zero, remember?)
Aha, we just figured out a definition of the plane, based on the normal vector. But what is d? Let's study a helpful case, by making a plane parallel to the (x,y) plane at z=10. How would we do that? The equation would have to be
z = 10or, more formally,
ax+by+cz = -d z = -(ax+by+d)/cPutting in the data. So, as we scan across a polygon and paint it into our image, we just compute the z of every pixel and put the z value into the z buffer for that pixel. When we paint the next polygon, we compute z FIRST, and see if it's larger than what's already there. If so, that pixel is beyond something we've already painted, so don't bother coloring it.
Making it efficient. Just like in line-scan conversion, we don't want to have to do a bunch of floating arithmetic for every pixel. Instead of really computing z from x and y by the above equation, we observe a couple of things and compute y "incrementally" - changing it as needed, rather than figuring from scratch.
1) The constant term -d/c can be added once at the beginning of the scan line.
2) y is constant through a whole scan line, so we can add -(by)/c once per line, and forget about it.
2) x changes by 1 with every step across the line, so we can just add (-a/c) when we increment x.
On top of this, we actually use an integer technique for managing rational numbers (as we mentioned for line scan conversion) and so we wind up being able to compute the z buffer for only a few integer operations per pixel.
One of the basic problems with polygon based methods is that they don't treat curved surfaces very nicely, when it comes to light and reflection. (Yes, I know we haven't studied that yet.) As CPUs got faster, people began to try to emulate physics more closely and get away from slavery to polygons. Ray tracing means following a beam of light wherever it may go, testing along the way to see what it hits.
In fact, we trace BACKWARDS from the viewpoint toward light sources, because otherwise we'd trace millions of rays that would never be seen.
So, to trace rays, we need a way to test if a ray hits an object. We will skip the more complex problems of deciding if a ray hits a polygon, and just work on the simple problem of collision testing with spheres.
In this picture, the observer is at point P and a sphere of radius r is centered at point C. Call the vector from P to C by the name S = PC, and call the ray of light we're studying, R. Now the question is, does R hit the sphere or not?
That is, can we compute the distance d, and compare it to r?
A1 Your task is
to use what you know about vectors, dot and cross product, to
find an efficient way to answer this question. Hint: The SIN of
an angle is the ratio of the length of the opposite side of the
triangle (away from the angle), to the length of the hypotenuse.
Most folks are dimly aware that we have actually got four different sensory systems in our eyes: rods for dim light and fast motion, and three flavors of cones for red, green and blue bright light and relatively slow motion. How can this work?
A spectral color (true physical color, of a single wavelengh of light) that is halfway between the maximal sensitivities of two cone systems stimulates them equally, allowing the brain to deduce the spectral color. However, the brain can be fooled by a mixture of two spectral colors into perceiving one that's not there.
This also opens the possibility of non-spectral colors such as brown and purple. These must consist of a mixture of non-adjacent spectral colors, because they result from the stimulation of multiple cone systems in ways that would be impossible by a single spectral color.
Surface Properties will be expressed in ways that are based on the surface reflection lighting model in use. In general we can have almost independent properties for each of the primary colors, and compute the net light coming off the surface as the sum of three computations, one for each primary color. We multiply the amount of primary red by the computed reflectance for red, etc.
The Computer Graphics Problem with Light. We only see light when it hits something; so our principal problem is deciding how to render an object in relation to a light source. It has become conventional to talk about three different kinds of light sources, although they are crude approximations to reality and are entangled with the properties of the surfaces reflecting the light.
We factor light in this way because there are convenient mathematical models for each kind of reflection.
There is a large range of possible techniques; here are some way-points.
Flat Shading applies the same color to an entire polygon. We often use a cosine law (called the Lambertian law for diffuse reflection) to compute the brightness, such as b = I * (N.L) where N is the surface normal, L is the vector pointing from the center of the polygon to the light source, and I is the incoming light's intensity. Note that this illumination doesn't seem to care which way it is to the viewer, only to the light source. It corresponds to "flat" (not glossy) paint, and matte surfaces.
Gouraud Shading computes a flat shading brightness at each corner of the (usually triangular) polygon. At these vertices, an "average normal" vector is used, by averaging the normals of all the polygons that meet at that vertex. The vertex brightness (a scalar value) is then computed for each vertex. Gouraud then uses bilinear interpolation to compute a linear average of the vertex brightnesses, at each point on the surface. The interpolation is almost identical to the z-buffer interpolation technique, because we're once again adding a constant amount per change in y and x, as we work across the surface.
Gouraud shading can be used with the Lambertian model, or with more realistic models such as Phong's reflectance model. In that model, specular light is allowed for, by computing a reflected ray R (see Assignment 2 below.) The cosine of the angle between the viewing direction and R is raised to some power n, for n between 1 and several hundred. Higher powers produce smaller, sharper highlights.
Phong Shading uses a classier idea. The vertex normal vectors are averaged at each point on the surface (like producing a porcupine of vectors.) This is more work than averaging the scalar vertex brightness values. We then apply the cosine law, for simple Phong shading. If we want , we could use Phong's reflectance model too.
Ray Tracing. We already looked at the propagation model. To draw an image, you have to cast a ray from the viewpoint through each pixel in the screen, and see what it hits, and bring that brightness info back to the screen. It's easily rendered parallel because rays are essentially independent.
A2 If we are tracing a ray L which hits a surface at point P, another ray R is produced which has the property that its angle with the normal N is equal and opposite to that between L and N. Given the numerical values for L, P and N, show how to compute R. (Remember, Michael's first law of computer graphics is: when in doubt, play with the Cross Product!)
Radiosity is the ultimate (so far) form of illumination modeling. The entire model space (e. g. interior of a room) is cut up into small zones, each of which is regarded as a source of light as well as a destination for light. Actual lights are assigned a specific brightness, and then a large set of equations are solved for the "steady state" in which everyone's output contributes to everyone's input. The degree of coupling between any two patches is represented by a form factor, finding out the form factors is the hardest part of the computation.
Often progressive refinement is used. In this technique,
instead of explicitly solving the set of simultaneous linear equations
(a slow operation if you have thousands of patches, thus thousands
of equations), we just "let some light loose in the room"
and substitute into the equations. After one pass, the light won't
be right but we draw the scene anyway, then take another pass.
This "relaxation" technique converges toward the correct
solution of the equations, but you can quit early if you don't
like the picture that's emerging. This often happens.
Let's see, now. We have to give you a QUIZ next week on Monday.
Wonder how we'll do that!? HINT: Study these notes, and the notes
from CAP5725's first three weeks. (Don't worry about the OpenGL
material.)