CS-460/560, Assignment # 3
CS-560 students must do all parts (A, B, C, and D)
CS-460 students must do parts A, B, and C
Due Date 3-2-2010


Part A

In this part of the assignment you are to write a VC++ MFC program that
displays a pattern of straight lines on the window client area using three
line-drawing algorithms: your implementation of Bresenham, your
implementation of DDA (both discussed in class), and the CDC GDI line-
drawing functions MoveTo() and LineTo(). In each case the pattern is to
be a sunburst which occupies the entire window client area. Each sunburst 
pattern should appear as follows: lines drawn from the center of the 
window client area to every fifth pixel in the top and bottom rows of the 
window client area and lines from the center of thewindow client area to 
every fifth pixel in the left-most and right-most columns of the window 
client area. (This will include all four Bresenham cases.) The figure 
below shows what the pattern should look like.


Each new line-drawing algorithm could be triggered by a menu item or by keyboard keys. For each new algorithm, the lines should be drawn in a different color. 
In each case, you should use the function GetTickCount() before and after
the pattern is displayed so that you can determine the number of milliseconds
that each algorithm took. In each case the result should be displayed.
(This could be done by using TextOut() or by putting up a MessageBox. Either
way you will probably need to use the function sprintf() or wsprintf() to
format the number of milliseconds into a text string. See the online help.)
If the computer you are using is so fast that the amount of time is less than
5 milliseconds, you should draw the pattern several times (perhaps many times)
and measure the amount of time from just before the first iteration of
drawing the pattern until just after the last iteration.

Part B

In this part of the assignment you are to draw the same pattern of lines
drawn in Part A using OpenGL under Windows. Bresenham's algorithm, the DDA
algorithm, and the OpenGL GL_LINES line-drawing fucntion should be compared.

For both the Bresenham and "DDA" lines, you will be specifying 
vertices using calls to glVertex(x,y) inside a glBegin(GL_POINTS)/glEnd() 
block to plot points. You might think of using code like this:

glBegin(GL_POINTS);
//loop to determine endpoint coordinates (x1,y1), (x2,y2) of each new line
     {Bresnham(x1,y1,x2,y2)} or {DDA(x1,y1,x2,y2)};
glEnd();

In this pseudocode Bresenham(...) and DDA(...) are helper functions 
that would be called for each iteration of the loop. You would put code in 
these functions to compute and plot the pixels on each line drawn. In each, 
the vertex plotting primitive will be glVertex2i(x,y). (This will replace 
the SetPixel(...) function that I used in the notes.)

To plot the OpenGL lines, you should use a GL_Begin(GL_LINES)/GL_End() 
block, inside of which you will again have a loop to determine the endpoint
coordinates of each new line; but now, for each, you will make a pair of 
calls to glVertex2i(x,y), where each (x,y) will be an endpoint coordinate of 
each line in the pattern.

You have two options in this part of this assignment: either use the OpenGL 
GLUT approach or the OpenGL "wgl" approach. The advantage of the "wgl" 
approach is that you can use Windows functions such as TextOut(...) or 
MessageBox(...) to draw text. You can also easily incorporate menu items for 
the user to select the desired line-drawing algorithm. In addition you could 
use the function GetTickCount() before and after the pattern is displayed to
determine the number of milliseconds that each algorithm took. If the computer 
you are using is so fast that the amount of time is less than 5 milliseconds 
(which it undoubtedly will be), you should draw the pattern several times 
(perhaps hundreds of times) and measure the amount of time from just before 
the first iteration of drawing the pattern until just after the last iteration. 

Also, if you use the "wgl" approach, you should set things up so that the 
viewing area is a rectangular box whose x-y dimension is approximately the 
size of the window's client area. You can, for example, use the OpenGL 
function glOrtho(-w,w,-h,h,-100,100) after OpenGL is initialized (in response 
to WM_CREATE). Here w is half the width of the window and h half its height. 
You could just use some number like 400 for the width and height or perhaps 
call GetClientRect() to get the size of the window's client area.

If you decide to use the GLUT approach, your code will be much shorter and 
simpler. But you won't have any of the Windows GDI and menu support. 
Furthermore, to determine the times, you could use the function _ftime(...) 
before and after drawing the pattern. This takes a pointer to a _timeb 
time-buffer structure. One of the members of that structure is millitm, the 
time in milliseconds. You could have code like the following to determine time 
intervals:

   struct _timeb timebuffer;
   unsigned short millitm1, millitm2;  // start and end times in milliseconds
   _ftime(&timebuffer);              // get time in milliseconds before drawing
   millitm1 = timebuffer.millitm;
   // display the line pattern (probably many times)
   _ftime(&timebuffer);              // get time in milliseconds after drawing
   millitm2 = timebuffer.millitm;
   
The elapsed time in milliseconds will then be millitm2-millitm1. If you do this,
you will need to have the following #include at the top of your program:

   #include <sys/timeb.h>

In addition, if you are using the GLUT approach, as in previous assignments you 
might set up a world coordinate "window" with something like the following: 
gluOrtho2D(-w,w,-h,h), where w and h are the logical width and height of the 
"window". This will give you a world coordinate system origin that will map to
the center of the client area of the display window.


Part C

In this part of the assignment you are to write a VC++ MFC program (or add 
to the program in Part A) that displays two patterns of ellipses on the
window's client area using the Midpoint Ellipse algorithm discussed in
class. The first pattern is a set of at least 50 concentric ellipses
centered on the center of your window's client area. The second pattern is
a set of at least 50 ellipses whose centers are located on a diagonal line
that goes from the window's upper lefthand corner to its lower righthand
corner. Each new ellipse should be larger than its predecessor. The figures
below show the desired patterns. As in Part A, the triggering of each
pattern can be done in response to menu items or to keyboard presses. The
program should not call the GDI Ellipse() function.


Part D -- Only required for CS-560 students

In this part of the assignment you are to derive and implement a "midpoint 
cubic curve drawing algorithm" which should scan convert and plot a simple
cubic function efficiently by using the same approach discussed in class
for the midpoint ellipse algorithm. The equation to be scan converted is: 
                                3 
                       y = c * x

In this equation, c is a parameter that determines the shape of the cubic
curve. (For a 600 X 400 pixel window, values of c between 0.000001 and 
0.000025 work well.) Once you have devised your algorithm, you should use it 
to display at least 50 cubic curves, each with a different value of c. The
display should show the cubic curves on both sides of the origin--which
means you will have to make a simple coordinate system transformation
(e.g., x --> x+300, y --> y+200 for a 600 X 400 pixel window). A display
like that shown in the following figure is what is desired.


You should also include in the program a "brute force" cubic curve drawing algorithm that plots the same pattern of cubic curves in some other color by direct calculation instead of incrementally. (If your algorithms are correct, the the patterns of cubic curves should look the same--except for color.)
For Part D, in addition to submitting the program, you should also submit
your derivation of the midpoint algorithm. You can turn in the derivation
on paper in class (or put it in the CS-560 drop drawer in the filing cabinet
outside the CS office) or include some sort of a text file (or pdf) of the
derivation with the email you send to the TA.

In parts A, C, and D of this assignment, the non-GDI algorithms will make  as many calls as necessary to the GDI function SetPixel().