Assignment 3 - Clipping Algorithms

CS4961 - Computer Graphics

Due February 26, 2001, 10:45 AM

NOTICE: NEW DUE DATE

Overview

This project builds on your previous project to implement line and polygon clipping. You will need to use your Bresenham line drawer to do this project.

Project Requirements

The following are requirements for the project. Both parts must be implemented for full credit.

Part 1: Line Clipping

The user should be able to specify the start and end points of a line using the mouse.
Allow the user to specify a clipping rectangle. The user should be able to do this either numerically or by mouse clicks (your choice). The user should be able to toggle this rectangle so that it is visible or hidden. (Only the border needs to be drawn when visible.) The clipping rectangle should be drawn in a color other than the default line color.
Allow the user to toggle line clipping. That is, when turned on, the line should be clipped to the clipping rectangle. When off, the entire line should be drawn (or at least as much of the line as can be fit on the screen). You should use the Cohen-Sutherland Line-Clipping algorithm (section 3.12.3).

Part 2: Polygon Clipping

The user should be able to construct a polygon of an arbitrary number of vertices. The user will do this with mouse clicks on the screen in the order the vertices appear. When finished, you must connect these vertices into a continuous polygon. You may assume the user will never assign vertices in such a way that edges cross. Oly the polygon's border needs to be drawn.
Allow the user to specify a clipping rectangle. The user should be able to do this either numerically or by mouse clicks (your choice). The user should be able to toggle this rectangle so that it is visible or hidden. (Only the border needs to be drawn when visible.) The clipping rectangle should be drawn in a color other than the default polygon color.
Allow the user to toggle polygon clipping. That is, when turned on, the polygon should be clipped to the clipping rectangle. When off, the entire polygon should be drawn. When clipped, all fragments of the polygon in the clipping window should have a continuous border - there should be no gaps. You should use the Sutherland-Hodgeman Polygon-Clipping algorithm (section 3.14.1).
Bonus (up to 6 points): Make the polygon solid in the above routines. For polygon filling, you may assume the polygon contains no slivers. (See section 3.6)

In both parts, the user should be able to change the clipping window without changing the line or polygon. The user must also be able to change the line/polygon without changing the clipping window. It is not necessary to draw lines and polygons at the same time.

When clipping, only points inside the clipping rectangle should be drawn. Do not draw points on or outside the rectangle. Again, GL and GLUT both contain functions that will draw lines and/or polygons and will perform clipping of these object. Again, YOU MAY NOT USE THEM. In all cases, drawing to the screen must be accomplished by specifying each pixel to draw.

In addition to the above requirements, include:

A way to clear the screen.
Documentation - Briefly explain what your program does and how to operate it. In addition, describe all data structures, major functions, and the program's flow of control.
User interface - The program should be controlled by user events and display to the screen. Any input from or output to the console window will not be considered for grading purposes.

Turn in all your code and documentation using submit (on CS machines) or handin on CADE machines. Your code will be tested using whatever environment you turn it in on (CS or CADE). Your code should be written in C/C++ and compile using gcc/g++. The project folder for submit and handin is named clipping. (submit cs4961 clipping file1 file2...)

Additional Notes

This section contains any additional notes regarding this project either due to questions raised by students or discoveries of my own. I will send messages to the class mailing list announcing any notes or clarifications, but this will contain a digest of all such info. These notes will never change what is required in the project, but may clarify some formerly ambiguous points and so should be checked semi-regularly.

On CS Suns, GLUI causes the line initfuncCalled = -7676776 to be printed to the screen whenever the drawing window is reset. Aside from being annoying, this has no other detrimental effects and may be ignored.
> In the homework handout, it specifies that we need to be able to draw
> polygons with an arbitrary number of vertices.
> This says to me that we need some sort of dynamic
> data structure to store all those points. Is that correct?
Yes. You should use dynamic allocation to store the points. You will lose design points on the project if you statically define your point structures. The exact nature of your data structure is up to you, but it should be described in your documentation.
> Also, I remember studying the difference between convex polygons and
> non-convex polygons. Are we supposed to only draw convex, or do we need
> to worry about non-convex ones as well?
You will need to draw and clip both concave and convex polygons. The Sutherland-Hodgman algorithm can handle both cases.
> When you turn the clip boundary on, do you only want to clip the next
> object drawn? Or do you want to clip whatever is in the window at the
> time? And conversely, do you want to redisplay the original line when
> the clip is turned off?
What is drawn on the screen should always be appropriate for the current state. If clipping is turned off, whatever object is on the screen should be drawn in its original, un-clipped form. Likewise, when clipping is turned on, whatever is on the screen should be displayed clipped. The changes should be immediate.
> the question is can the rectangle drawn by user be out of screen, ie if
> the screen size is 512x512, can the rectangle size be 500x700 etc?
You may constrain the clipping rectangle so that it is only within the screen.
I talked to several people and there seems to be a couple misunderstandings about the assignment. (Sorry about that.)
First, the screen should always reflect the state of the control panel. If clipping is turned on then everything on the screen needs to be clipped. If clipping is off then everything on the screen should be shown completely.
This said, I don't require much at any given time. There only needs to be one line at a time - new lines can replace the old lines. A new clipping rectangle can replace the old one. Etc. This is intended so you don't need to keep track of more than one clipping rectangle/object (line or polygon) at a time. If you have more than one of each item displayed at any given moment, then every item must behave according to the control panel. (I.e. if you choose to have several lines and a polygon on the screen at one time, all must clip or unclip as specified in the control panel.) You are responsible for what is on the screen.
Due to several factors, project 3 will now not be due until Monday, Feb. 26. Have a great long weekend.
Some students have pointed out that, since you know the clipping body is a rectangle, one part of the Sutherland-Hodgeman algoithm can be simplified. Given how... particular... I was about implementing the Bresenham algorithm precisely, I want to announce that it is perfectly fine if you simplify the inside/outside determiniation given that the clipping area is an upright rectangle.
In order that those who used the more general method don't feel slighted, you can earn extra credit if your program can clip polygons to arbitrary convex polygons. (You will need to implement some way that I can create an arbitrary clipping polygon to get credit for this.)
You must clip the polygons correctly. This means taking care of the degeneracies. If clipping would produce multiple polygons, you must draw multiple, unconnected polygons. I will be checking for this.
> When polygon clipping was discussed in class Rich spoke about the
> degenerate polygons that should become two separate polygons when
> clipped but with the algorithm a line still connects the two. (in fact,
> this was the example used in the slides.) My question... are our
> programs supposed to handle these degenerates and create 2 separate
> polygons, or are the lines connecting them ok?