CS480 Solutions to Homework Assignment 3

1. At a sufficient viewing distance, the eye ``blurs'' the contribution of the individual pixels in an mx m pixel pattern. Each pattern's perceived intensity is directly related to the sum of its individual pixel intensities. Thus the equation for the number of intensities that can be represented by mx m pixel patterns, where each pixel has w bits is:

Note that this equation is the total number of pixels () times the total number of possible non-zero intensities per pixel plus one additional (the case where all pixels are zero).

2. Assume that we have a closed, convex polygonal shape where all polygon normals point outward. Under these conditions, a point is inside a shape only when the point lies in the negative half-space for all the polygons that define the shape. We can determine whether a point is in the negative half space for a particular polygon by plugging the point into the polygon's plane equation. The algorithm for determining whether or not a point is inside the shape is simply:

 
for each polygon in the object

		 if Ax + By + Cz + D > 0

		 		 return OUTSIDE;

return INSIDE;

This algorithm will not work for concave objects. This is because it is based on half-spaces. This is demonstrated for the prismatic polygonal shape shown below.

Even though the point P is inside the polygonal object, it is classified as ``outside'' the shape. This is because it lies in the positive half-space, which is defined by a face and it's outward pointing normal.

3. We are given three constraints expressed in terms of the three control points for a quadratic Bézier curve: , , and . We put these constraints into the quadratic Bézier geometry matrix:

Each constraint corresponds with an equation:

where is the quadratic Bézier basis matrix.

These three constraint equations can be rewritten in matrix form:

For this equation to be satisfied, must be the inverse of the matrix:

Expanding the product in gives the curve in terms of blending functions:

The resulting blending functions are Bernstein polynomials

In general, a Bézier curve of degree n will have n+1 control points, and thus n+1 blending functions. Blending functions for a Bézier curve of degree n take the form:

4. One possible interface for selecting the right level in the hierarchy lets the user navigate up and down using keyboard input. By using the U-key, the user could move up the hierarchy, by using the D-key, the user could move down. As feedback, the interface would display the resulting selection as highlighted. The user would hit the return key when the desired level in the hierarchy was selected. The following is pseudo code for the algorithm:

 
if hierarchy depth < 2

   return( top of structure )

level = bottom of hierarchy

done = FALSE

set up keyboard input

create a structure for highlighting the current selection

do

       wait for keyboard input

       if upward motion requested and not at top of hierarchy

              move up a level

       if downward motion requested and not at bottom of hierarchy

              move down a level

       else if carriage return

              done = TRUE

       if changed level in heirarchy

              highlight the new selection

while( not done )

delete highlight structure

return( selected level )

Assume that we have already made a call to SPH_pickCorrelate (as in example 7.1 in the text). This routine returns the PHIGS structure path in pickInfo: starting with the top (root) downwards, the structure contains information about the pick level (how many levels deep the path goes in the PHIGS structure hierarchy) and the structureID at each level. Here is a code fragment from a routine that would allow the user to select the desired level in the hierarchy.

 
if(pickInfo.picklevel < 2)
       return(pickInfo.picklevel);

done = FALSE;
level = pickInfo.picklevel;

SPH_setInputMode(KEYBOARD,EVENT);
SPH_setKeyboardProcessingMode(RAW);
SHP_openStructure(HIGHLIGHT_STRUCTURE);
SPH_setInteriorColor(HIGHLIGHT_COLOR);
SPH_executeStructure(pickInfo.path[level].structureID);
SPH_closeStructure();
SPH_postRoot(HIGHLIGHT_STRUCTURE,viewIndex);

do {
       whichdev = SPH_waitEvent(INDEFINITE);
       if(whichdev==KEYBOARD){
              SPH_getKeyboard(key,KEYMEASURE_SIZE);
              increment = 0;
              if((key[0]=='u'  key[0]=='U')  level> 1)
                     increment = -1;

              else if((key[0]=='d'  key[0]=='D') level < pickInfo.pick_level)
                     increment = 1;

              else if(key[0] == '')
                     done = TRUE;

              if(increment) {
                     level += increment;
                     SPH_openStructure(HIGHLIGHT_STRUCTURE);
                     SPH_setElementPointer(1);
                     SPH_deleteElement();
                     SPH_executeStructure(pickInfo.path[level].structureID);
                     SPH_closeStructure();
                     SPH_postRoot(HIGHLIGHT_STRUCTURE,viewIndex);
                     }
              }
       } while(done == FALSE);

SPH_postRoot(pickInfo.path[1].structureID,viewIndex);

return(level);

}