CS318 - Fall 1999
Machine Problem 3

Assigned:: October 8, 1999
Due Date:: October 22, 1999, 10:00am

Description

For this MP, you will be implementing the Nicholl-Lee-Nicholl Line Clipping Algorithm. Your program will take input from the mouse for the endpoints of up to 20 lines, and the two corners which define a rectangular clipping region.

Since you will be implementing your own clipping algorithm, you may not use the built-in OpenGL clipping function glClipPlane. That wouldn't be very interesting, now would it?

Goals

Upon completion of this MP, you should be able to do the following things:

Understand the various line and polygon clipping algorithms presented in the book; and
Understand how to implement the Nicholl-Lee-Nicholl line clipping algorithm.

Preparation

Read the Textbook

Read Chapter 6 in the required text for this class - ``Computer Graphics, 2nd Edition'' by Hearn & Baker. It discusses the various clipping algorithms and basic concepts you will need for this MP.

Figure Out the Input Routines

For this MP, you will need to use the mouse buttons. Their functionality is described below. You can use the code from previous MPs to get mouse coordinates. Get your program working with just entering the lines and the clipping rectangle, and worry about doing the actual clipping later.

Your Assignment

You are to write a program that allows the user to enter up to a maximum of twenty (20) line segments on the screen. This means that you can enter a maximum of forty (40) endpoints. In addition, the user can enter two (opposite) corners of a rectangular clipping region. Your program must then clip all of the lines to the boundaries of the input clipping rectangle using the Nicholl-Lee-Nicholl line clipping algorithm. You must implement the following inputs to the mouse and the keyboard.

Left Mouse Button - Enter Line Segment Endpoints

The Left Mouse Button allows you to enter endpoints for your line segments. Observe the following instructions when drawing the endpoints and the connecting line segments.

When you enter the first endpoint of a line with the mouse, draw that endpoint in GREEN (glColor3f(0.0,1.0,0.0)) with a point size of 3.0. When you enter the second endpoint with the mouse, draw the connecting line segment in GREEN with a line width of 1.0, but do not draw the endpoints as large points. Just draw the line itself. (Basically, you will draw a large endpoint for the last coordinate input if the number of endpoints entered thus far is odd.)

You can continue to enter endpoints with the Left Mouse Button in this manner. As an example, assume we have entered two endpoints as above and have drawn the connecting line segment. When you click the left mouse button a third time, the original line segment remains, and you will have another green endpoint on the screen. Clicking the mouse a fourth time will give you two line segments (but no large endpoints). You can continue the process for up to forty (40) endpoints, which gives you a maximum of twenty (20) line segments. Once you reach this maximum, simply ignore any other attempts to add more endpoints.

Once you start entering a new line segment by designating the first endpoint of that line segment, do not allow the user to enter any points for the clipping rectangle. See the description for the Right Mouse Button below.

Type the <Backspace> Key - Clear the Line Segments

When you type the Backspace key, the screen is cleared of all line segments. All line segments (and possibly a single endpoint) are removed from the screen, but the clipping rectangle (if any) remains. You can type the <Backspace> key at any time. For example, if you have entered the first endpoint of a line, and you type the <Backspace> key, all line segments are removed from the screen. The next click of the Left Mouse Button would enter the first endpoint of a line.

Note that typing the <Backspace> key has no effect on the clipping rectangle. Only the line segments are cleared.

Right Mouse Button - Enter Clipping Rectangle Corners

The Right Mouse Button is used to enter the two corners of the clipping rectangle. (Any rectangle can be defined by two opposite corners.) Each button press adds one corner to the clipping rectangle. The two corners can be entered in any order. Follow these conventions when drawing the clipping rectangle:

Draw the lines of the clipping rectangle in BLUE (glColor3f(0.0,0.0,1.0)) with a line width of 1.0.
While entering the two corners, draw the first corner entered as a POINT (glBegin(GL_POINTS)) with a point size of 3.0.
When the second corner has been entered, draw the rectangle defined by the two points as an outline (ie. draw only the edges). Note that you cannot use glRect since this draws a filled rectangle. Also, do not draw a POINT for the first corner (or any corner for that matter).

Once the two corners have been entered, you are free to swap their values as you see fit. This is useful if you always want one corner to contain X and Y values that are less than another corner's. That way, you can force one corner to contain (xmin,ymin) and another corner to contain (xmax,ymax) of the clipping rectangle. This will come in handy when trying to determine which edge is which.

If only one corner of the clipping rectangle has been entered, do not allow the user to enter endpoints for lines. The user can enter line segments only if 0 or 2 corners of the clipping rectangle have been entered.

Similarly, if one endpoint of a line has been entered (awaiting the second endpoint to define the line), do not allow the user to enter corners for the clipping rectangle. The user can enter corners of the clipping rectangle only if an even number of line endpoints have been entered.

Once the two corners of the clipping rectangle have been entered, you can then allow the user to enter more endpoints for line segments. You can also enter a new clipping rectangle by clicking with the Right Mouse Button again. The old clipping rectangle disappears and you start all over entering the two corners. This means that you should have a maximum of one clipping rectangle on the screen at any time.

Type the Letter ``Q'' - Quit the Program

When you type the letter ``q'' or ``Q'', the program should exit.

Performing the Clipping

Once you have entered both corners of the clipping rectangle, apply the Nicholl-Lee-Nicholl line clipping algorithm to all line segments to obtain ``clipped line segments''. Follow these conventions when drawing the ``clipped line segments'':

Draw the ``clipped lines'' in RED (glColor3f(1.0,0.0,0.0)) with a line width of 1.0.
Draw in this order: original line segments (and possibly a single endpoint) first, clipping rectangle second, and ``clipped lines'' last.

You must clip your lines using the method described on pp.233-235 of the textbook. However, you can handle each of the 9 cases (actually 13 since each corner has 2 cases) separately if you want. Do do not have to use the generalization suggested (ie. rotating points so that they fall into one of the three cases shown).

Restrictions

This section lists restrictions that are placed on your program. Please read this section carefully, or you may lose points by implementing something incorrectly.

You may not use glClipPlane.
You may not use glViewport to ``simulate'' a clipping region.

Hints / Sample Code

Remember that screen coordinates make x values increase from left to right (as expected) and y values increase from top to bottom (opposite of what is expected).
Be sure to prevent the user from entering corners of the clipping rectangle while entering endpoints for lines, and vice versa. Simply keep a global variable for the number of line endpoints entered so far, and a global variable for the number of corners of the clipping rectangle entered. You will need these variables in your ``update display'' routine to decide if you should draw the lines and endpoints, the clipping rectangle, and the ``clipped lines''.
Don't draw any ``clipped lines'' if the user is entering clipping rectangle corners. Wait until the clipping rectangle is completely entered.
Once both corners of the clipping rectangle have been entered, make the first corner hold (xmin,ymin) and the second corner hold (xmax,ymax). This will help you in your clipping routine.
When drawing your clipping rectangle, use glBegin(GL_LINE_LOOP). If you know that the first corner is (xmin,ymin), you can easily figure out the four corners that make up the clipping rectangle and use glVertex with the four corners. For example:
```
      glBegin(GL_LINE_LOOP);
        glVertex2i(xmin,ymin);
        glVertex2i(xmin,ymax);
        glVertex2i(xmax,ymax);
        glVertex2i(xmax,ymin);
      glEnd();
```
When you draw your ``clipped lines'', they will not exactly cover the original lines since the new endpoints of the ``clipped lines'' will be integer values, but the intersection of the original lines and the clipping rectangle may have been floating point values. Don't worry about this since it is bound to happen.

One Unit Grad / Honors Students

Those graduate students enrolled for 1 unit of credit, and undergrad students registered for honors credit, must also implement the following additional functionality.

For this MP, you will be concerned about user interface design techniques. In particular, you will implement rubberbanding for feedback when the user enters line segments and the clipping rectangle.

Type the Spacebar - Toggle Rubberbanding

When your program first starts, it should be in the ``non-rubberband'' mode where screen updates occur only upon mouse clicks. When you hit the Spacebar, you toggle the rubberband mode on and off. When your program is in ``rubberband'' mode, the screen is updated also when your mouse cursor moves.

Let's say that you are in rubberband mode and you are inputting line segments. You select the first endpoint by clicking with the Left Mouse Button. Then, as the mouse cursor moves around the screen, a line is drawn from this first endpoint to the current cursor location. When you click with the Left Mouse Button again, the resulting line segment is drawn, and you are done. See Figure 8-10 in your textbook for an illustration.

Again, let's say you are in rubberband mode and you are inputting the clipping rectangle. You select the first corner by clicking with the Right Mouse Button. Then, as the mouse cursor moves around the screen, a rectangle is drawn from the first corner to the ``opposite'' corner as defined by the current cursor location. When you click with the Right Mouse Button again, the clipping rectangle is drawn, and you are done. See Figure 8-11 in your textbook for an illustration.

Hints and Tips

Getting your program to handle rubberbanding is not as simple as it might seem at first. There are many issues that you will have to deal with in implementing rubberbanding. Below are some tips on getting it to work correctly. You should also try out the demonstration program provided on the class web page to see some of the tricky issues.

You might want to use double-buffering to reduce screen flicker. To do this, you will need to do two things. First, when you initialize your window, you will need to tell GLUT that you want to use a double-buffered window, instead of a single-buffered window. You will probably have something like glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB) in your window initialization routine. Second, when you enable double-buffering, GLUT automatically draws to the ``hidden'' buffer. So, you need to change any calls of the form glFlush() to glutSwapBuffers(). (This will automatically do a glFlush for you.)
You will need to monitor mouse movements when you have entered the first endpoint of a line or the first corner of the clipping rectangle. There are two calls in GLUT to do this: glutMotionFunc() and glutPassiveMotionFunc(). The first handles mouse movement when one or more mouse buttons are held down, and the second handles mouse movement when no mouse buttons are pressed. You might want to write one general function to handle mouse movement, and then have both of these GLUT event handlers use that general function when you are in rubberband mode. You can effectively turn off the monitoring of mouse movements by passing NULL as the parameter to these two GLUT functions.
Pay close attention to what happens when the user presses the spacebar during a rubberband drawing. If you are currently in rubberband mode and just about to select the second endpoint of a line segment when the user presses the spacebar, then the rubberbanding should go away and you will be left with the first endpoint. On the other hand, if you are currently not in rubberband mode and just about to select the second endpoint of a line segment when the user presses the spacebar, then a rubberband line will appear between the first endpoint and the current mouse location.
You need to decide whether a point is selected on a mouse press or on a mouse release. This will affect the functionality of your rubberbanding if the user keeps the mouse pressed for a long period of time. I chose to designate a coordinate on a mouse button press. Try the demonstration program to see what I mean.

Hand-In Procedures

For this and future MPs, we will be using the electronic handin program. Once you have completed your program, logon or telnet to one of the Sun Sparc machines (``handin'' does not work on the WindowsNT machines) and hand in your source code by typing ``handin cs318 mp3 mp3.c''. (For more information on handing in your code, consult the class web page at http://www-courses.cs.uiuc.edu/~cs318/handin.html.) This will send your program to the class directory for grading.

Do not submit your executable program. Also, put all your source code in one file. You must hand in your source code file before 10:00am of the due date, as handin will not accept late assignments. Make sure your name, login, MP#, and date appear at the top of your code listing. See the class web page for a sample file header.

If your program does not run as required, you will be given at most 50% of the total points for the MP. You are responsible for making sure your program compiles on the WindowsNT machines using the makewin batch file.

Late assignments will not be accepted. If you are having problems beyond your control, you must let a TA know at least 24 hours before the due date to arrange for a possible extension. There will be no exceptions!