CS-460/560, Assignment # 3In this part of the assignment you are to write a VC++ MFC program that

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

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 BIn 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 theBresenham 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 theOpenGL 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 CIn 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.

In this part of the assignment you are to derive and implement a "midpoint

Part D -- Only required for CS-560 students

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().