/***********************************************************************/ /* */ /* NAME : Terry Fleury PROGRAM : mp1 */ /* NET ID : cs318ta1 COURSE : CS318 - Fall 1999 */ /* DUE DATE : September 24, 1999 */ /* PURPOSE : In this MP, we implement the midpoint line drawing */ /* algorithm for arbitrary lines. The user enters two */ /* endpoints with the mouse. These two endpoints are */ /* drawn in Green and Red (first point, second point), */ /* and the line is drawn between them in white. For */ /* 1-unit grad students, the user can type 0-9 on the */ /* keyboard for different lengths of dashed lines. */ /* INPUT : Left Mouse Button - designates first and second */ /* endpoints of the line. */ /* 0-9 - changes the line to a dashed line with equal */ /* line segments/spaces making up the dashed line. */ /* (For 1-unit grad students only.) */ /* "q" - quit program */ /* */ /***********************************************************************/ #include #include #include #include /*************************/ /* FUNCTION PROTOTYPES */ /*************************/ void Initialize(void); void SetCameraPosition(void); void UpdateDisplay(void); void DrawLinePoint(int,int,int); void DrawLine(void); void MouseButtonPressed(int,int,int,int); void KeyPressed(unsigned char,int,int); void ReshapeWindow(int,int); void QuitProgram(void); void PrintUsage(void); /**********************/ /* GLOBAL VARIABLES */ /**********************/ int WinWidth = 600; /* Width of the main window */ int WinHeight = 600; /* Height of the main window */ int DashedLine = 0; /* Spacing for dashed line - 0 = solid */ int PointsEntered = 0; /* Number of endpoints entered so far */ int EndPoints[2][2]; /* Array to hold two endpoints of the line */ /***********************************************************************/ /* Initialize is called at program invocation and sets up the main */ /* window. */ /***********************************************************************/ void Initialize(void) { /* Initialize the window and color mode */ glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB); glutInitWindowSize(WinWidth,WinHeight); glutCreateWindow("CS318 MP1 - Solution"); glClearColor(0.0,0.0,0.0,0.0); /* Background is black */ SetCameraPosition(); } /***********************************************************************/ /* SetCameraPosition is called by several procedures to move the */ /* camera to the correct viewing position, and then set GL_MODELVIEW */ /* to allow drawing of objects on the screen. */ /***********************************************************************/ void SetCameraPosition(void) { /* Set the viewing transformation */ glMatrixMode(GL_PROJECTION); glLoadIdentity(); gluOrtho2D(0.0,(GLdouble)WinWidth+1.0,(GLdouble)WinHeight+1.0,0.0); glMatrixMode(GL_MODELVIEW); } /***********************************************************************/ /* UpdateDisplay is called by the main event loop to refresh the */ /* contents of the display and to show the squares. */ /***********************************************************************/ void UpdateDisplay(void) { glClear(GL_COLOR_BUFFER_BIT); /* Clear the main window */ DrawLine(); glFlush(); /* Flush all output to the main window */ } /***********************************************************************/ /* DrawLinePoint is called by DrawLine to draw a single point for */ /* the line. I made this a separate procedure so that I could easily */ /* draw lines with vertices swapped, if necessary. This function */ /* takes an (x,y) point and a boolean if they should be swapped. */ /***********************************************************************/ void DrawLinePoint(int x, int y, int swapped) { if (swapped) glVertex2i(y,x); else glVertex2i(x,y); } /***********************************************************************/ /* DrawLine is called by UpdateDisplay to draw the endpoints and the */ /* line on the screen. It draws the first endpoint in green, the */ /* second endpoint in red, and the line in white. The endpoints are */ /* slightly bigger to make them more visible. This procedure uses */ /* the midpoint line algorithm to draw the line. It also uses the */ /* value of DashedLine to draw a dashed line if DashedLine > 0. */ /***********************************************************************/ void DrawLine(void) { int x, y; /* The current (x,y) point to be plotted */ int xend, yend; /* The second endpoint of the line */ int dx, dy; /* The difference between the two endpoints */ int stepx, stepy; /* These will be +1 or -1 depending on the line */ int p; /* The decision parameter */ int str, diag; /* The straight/diagonal increments for p */ int swapped; /* Do we plot (x,y) or (y,x)? */ int DashCounter; /* Count number of pixels to dash on/off */ int LineOn; /* Toggles when DashCounter reaches DashedLine */ if (PointsEntered > 0) { /* Draw the first big endpoint of the line */ glColor3f(0.0,1.0,0.0); /* Drawing Color is Green */ glPointSize(3.0); /* Make a big endpoint */ glBegin(GL_POINTS); glVertex2i(EndPoints[0][0],EndPoints[0][1]); glEnd(); } if (PointsEntered > 1) { /* Draw the second big endpoint of the line */ glColor3f(1.0,0.0,0.0); /* Drawing Color is Red */ glPointSize(3.0); /* Make a big endpoint */ glBegin(GL_POINTS); glVertex2i(EndPoints[1][0],EndPoints[1][1]); glEnd(); /* Draw the line between the two endpoints */ glColor3f(1.0,1.0,1.0); /* Drawing Color is White */ glPointSize(1.0); /* Make a thin line */ LineOn = 1; /* Start with the (dashed) lines on */ DashCounter = 1; /* Reset the counter for dashed lines */ if (abs(EndPoints[1][1] - EndPoints[0][1]) <= abs(EndPoints[1][0] - EndPoints[0][0])) { /* -1 <= Slope <= 1 */ swapped = 0; /* Don't swap x & y values */ x = EndPoints[0][0]; y = EndPoints[0][1]; xend = EndPoints[1][0]; yend = EndPoints[1][1]; } else { /* Slope < -1 OR Slope > 1 */ /* This part of the code requires some explanation. In order */ /* to keep code duplication to a minimum, I have "swapped" */ /* x & y values for the case of "up & down" lines. This way */ /* I can use the same equations below for different lines. */ /* I set "swapped" to 1, and then plot (y,x) instead. */ swapped = 1; /* Swap x & y values */ x = EndPoints[0][1]; y = EndPoints[0][0]; xend = EndPoints[1][1]; yend = EndPoints[1][0]; } /* Start drawing Points for the line */ glBegin(GL_POINTS); /* Plot the first point of the line */ DrawLinePoint(x,y,swapped); /* Calculate the direction for drawing the line */ dx = xend - x; dy = yend - y; if (dx < 0) stepx = -1; else stepx = 1; if (dy < 0) stepy = -1; else stepy = 1; /* Calculate the decision parameter and straight/diagonal values */ p = (2 * dy * stepx) - (dx * stepy); str = 2 * dy * stepx; diag = 2 * (dy * stepx - dx * stepy); /* Plot points until we reach the second endpoint */ while (x != xend) { x += stepx; if (((p < 0) && ((stepx + stepy) != 0)) || ((p >= 0) && ((stepx + stepy) == 0))) p += str; else { p += diag; y += stepy; } /* If drawing dashes, check to see if we toggle on/off drawing */ if (DashCounter == DashedLine) { LineOn = !LineOn; DashCounter = 1; /* Reset Counter */ } else if (DashedLine > 0) DashCounter++; /* Increment Counter */ if (LineOn) DrawLinePoint(x,y,swapped); } /* Plot the last point of the line */ if (LineOn) DrawLinePoint(xend,yend,swapped); /* All done drawing points for the line */ glEnd(); } } /***********************************************************************/ /* MouseButtonPressed is the callback function for when the Left */ /* Mouse Button has been pressed. It extracts the (x,y) position of */ /* the mouse. If the number of points entered thus far does not */ /* equal 1 (ie. 0 or 2), then we set the first endpoint. Otherwise, */ /* we have already entered the first endpoint, and we set the second */ /* endpoint of the line, updating PointsEntered as necessary. */ /***********************************************************************/ void MouseButtonPressed(int Button, int State, int X, int Y) { if ((State == GLUT_DOWN) && (Button == GLUT_LEFT_BUTTON)) { /* Check to see if either no endpoints or two endpoints are defined. */ if (PointsEntered != 1) { EndPoints[0][0] = X; EndPoints[0][1] = Y; PointsEntered = 1; } else /* The first endpoint has been entered. Set the second endpoint. */ { EndPoints[1][0] = X; EndPoints[1][1] = Y; PointsEntered = 2; } glutPostRedisplay(); } } /***********************************************************************/ /* KeyPressed is called when a key is press on the keyboard. If a */ /* 'q' is pressed (lower or upper case), the program exits. If a */ /* number is pressed, DashedLine is set to that value. DashedLine */ /* is the number of "pixels" for the spaces and dashes of the line. */ /* A setting of zero means to draw a solid line. At the start of */ /* the program, DashedLine is initialized to 0. */ /***********************************************************************/ void KeyPressed(unsigned char Key, int X, int Y) { if (toupper(Key) == 'Q') QuitProgram(); else if (isdigit(Key)) { DashedLine = Key - '0'; glutPostRedisplay(); } } /***********************************************************************/ /* ReshapeWindow is called if the main window needs to be resized. */ /***********************************************************************/ void ReshapeWindow(int Width, int Height) { WinWidth = Width; /* Update the global WinWidth/WinHeight variables */ WinHeight = Height; SetCameraPosition(); /* Update the camera view to be full screen */ glViewport(0,0,WinWidth,WinHeight); } /***********************************************************************/ /* QuitProgram is called to exit gracefully. */ /***********************************************************************/ void QuitProgram(void) { exit(0); } /***********************************************************************/ /* PrintUsage is called at program startup to print out a short */ /* help message on how to use the program. */ /***********************************************************************/ void PrintUsage(void) { printf("CS318 - MP1 - Midpoint Line Algorithm\n"); printf("INPUTS:\n"); printf("Left Mouse Button - Enter Endpoints for Line\n"); printf("'0' - '9' - Change line dash width (1-unit grads)\n"); printf("'q' or 'Q' - Quit Program\n"); fflush(NULL); /* Make sure output shows up */ } /**************************/ /* BEGIN MAIN PROGRAM */ /**************************/ int main(int argc, char** argv) { glutInit(&argc,argv); PrintUsage(); Initialize(); /* Set up main window and variables */ /* Set the Mouse / Keyboard / Reshape / Display callbacks */ glutKeyboardFunc(KeyPressed); glutMouseFunc(MouseButtonPressed); glutReshapeFunc(ReshapeWindow); glutDisplayFunc(UpdateDisplay); glutMainLoop(); return 0; /* Required by ANSI C */ } /**************************/ /* END MAIN PROGRAM */ /**************************/ /************************************************************************ Midpoint Line Algorithm Derivation ---------------------------------- The equation of any line is y = (dy/dx) * x + B, where dy/dx is the slope and B is the y-intercept. We can also write the equation of a line in its implicit form as F(x,y) = ax + by + c. We start by putting the first equaion above in the implicit form. Move the y over to the right side of the '=', and multiply everything by dx to get F(x,y) = dy*x - dx*y + dx*B. Compare this with the second equation above, and we can see that a=dy, b=-dx, and c=dx*B. The basic idea behind the midpoint line algorithm is to use the implicit form of the line equation in conjunction with a "midpoint" to determine the next pixel to be painted. Let's first consider the case where 0 < m < 1, and the first endpoint is left-most. For this case, we will always increment x by 1 at each step. What we need to figure out is whether to increment y or not at each step. Let's assume that we have already plotted a point at (i,j). We must decide whether to plot (i+1,j) or (i+1,j+1). (Since the first endpoint is left-most, we increment x in the positive direction. Since the slope is between 0 and 1, we increment y in the positive direction.) The midpoint between these two "next" points is at (i+1,j+0.5). We would like to find out if this "midpoint" is above or below the line we are trying to draw. Why? If the midpoint is below the line, then the line is above the midpoint, and we want to plot (i+1,j+1). If the midpoint is above the line, then the line is below the midpoint and we want to plot (i+1,j). These are our only two choices. (If the midpoint is "on" the line, we don't care which point we plot, as long as we are consistent.) To determine where the midpoint is in relation to the line, let's plug that point into our line equation and see what we get. From the equation of our line, we know that if F(x,y) is zero, then (x,y) lies on the line. If F(x,y) is positive, then (x,y) is below the line. If F(x,y) is negative, then (x,y) is above the line. (If you don't believe me, try the line F(x,y) = x - 2y, which has a slope of 0.5 and a y-intercept of 0. (2,1) is on the line, and F(2,1) = 0. (2,4) is above the line, and F(2,4) = -6. (4,0) is below the line, and F(4,0) = 4.) Plugging in (i+1,j+0.5), we get F(i+1,j+0.5) = dy*(i+1) - dx*(j+0.5) + dx*B. Multiply to get dy*i + dy - dx*j - 0.5*dx + dx*B. Rearranging terms, we get dy*i - dx*j + dx*B + dy - 0.5*dx. Notice the first three terms of this equation: dy*i - dx*j + dx*B. This is simply F(i,j). Now, look at the rest of the equation: dy - 0.5*dx, and look back at the first paragraph. This is actually a + 0.5*b! Now, let's call F(x,y) our decision parameter "p". To find the initial decision parameter, let's plug in F(x0+1,y0+0.5), where x0,y0 is the left- most endpoint. We know from above that if a point lies on the line, then F(x,y) equals zero. Since (x0,y0) lies on the line, F(x0,y0) equals zero. Figuring out F(x0+1,y0+0.5) we get F(x0,y0) + dy - 0.5*dx. Let's multiply this by 2 so we get rid of the 0.5 term. This is okay since we only care about the SIGN of the function. This gives us our intial decision parameter of p = 2*dy - dx. Next, we need to figure out how to update this decision parameter based on which of the two pixels we chose. We assume that we had some decision parameter already. Call this p_old. First, let's assume we picked (i+1,j). Our NEXT decision parameter is going to look at the next midpoint which is (i+2,j+0.5). Plugging this into F(x,y), we get p_new = dy*(i+2) - dx*(j+0.5) + dx*B. But, p_old = dy(i*1) - dx*(j + 0.5) + dx*B. So we end up with p_new = p_old + dy. Since we multiplied F by 2 above, we need to do the same here to get p_new = p_old + 2*dy. Second, let's assume we picked (i+1,j+1). Our NEXT decision parameter is going to look at the next midpoint which is (i+2,j+1.5). Plug this into F(x,y) to get p_new = dy*(i+2) - dx*(j+1.5) + dx*B. Looking at p_old again, we see that p_new = p_old + dy - dx. Again, multiply F by 2 to get p_new = p_old + 2*dy - 2*dx. Now, we have everything we need. Let's summarize: Left-most Endpoint = (x0,y0) Right-most Endpoint = (x1,y1) dy = y1 - y0 dx = x1 - x0 Initial decision parameter p = 2*dy - dx If we pick (i+1,j), update p = p + 2*dy If we pick (i+1,j+1), update p = p + 2*dy - 2*dx Okay, now let's try to generalize this. Let's look at the four cases where |m| < 1. We just saw the first one above, but let's look at -1 < m < 0, and the first endpoint is left-most. We still increment x in the positive direction, but now we increment y in the negative direction. Assuming we already plotted the point (i,j), we must decide whether to plot the point (i+1,j) or the point (i+1,j-1). So, our midpoint is now (i+1,j-0.5). Plugging that into our F(x,y) equation, we get dy*(i+1) - dx(j-0.5) + dx*B. Multiplying and rearranging, we get dy*i - dx*j +dx*B + dy + 0.5*dx. The first three terms are again F(i,j) and we multiply F by 2 to get rid of the 0.5 term. If we plug in (x0,y0) again, we will get an initial decision parameter of 2*dy + dx. Also, we need to figure out our "update p" values. If we picked (i+1,j), the next midpoint is going to be (i+2,j-0.5), and we will get F(i+2,j-0.5) = F(i+1,j-0.5) + dy, or p_new = p_old + 2*dy (since we need to multiply F by 2 as above). If we picked (i+1,j-1), the next midpoint is going to be (i+2,j-1.5), and we will get F(i+2,j-1.5) = F(i+1,j-0.5) + dy + dx, or p_new = p_old + 2*dy +2*dx (again multiplying F by 2). Do this again for the case where 0 < m < 1, first point right-most, and -1 < m < 0, first point right-most, and we can build the following table: 1st Point Slope StepX StepY Initial p (x+stepx,y) (x+stepx,y+stepy) ---------- ----- ----- ----- --------- ----------- ----------------- left-most 0= 0) && ((stepx + stepy) == 0))) For the 4 cases where |m| > 1, the easiest thing to do is to "swap" the x and y values of the endpoints, calculate everything as before, and plot the point (y,x). Alternatively, we could duplicate all of the code and change x's to y's and vice-versa, resulting in two while loops. ************************************************************************/