代写CSE 328 OGRAMMING ASSIGNMENT

CSE 328 PROGRAMMING ASSIGNMENT TWO

The primary objective of this programming assignment is to practice the basic key operations on

planar triangles and polygons pertinent to 2D computer graphics techniques. In this programming

assignment, you could rely on OpenGL drawing commands to draw points/pixels (GL POINTS),

lines (GL LINE STRIP), and wireframe polygons (GL LINE LOOP). Please note that you are not

allowed to use the solid-filling polygon rasterization mode (GL FILL). Since GL FILL is OpenGL’s

default polygon rasterization mode, you must override it manually with GL POINT or GL LINE in

your program. Again, you are required to use OpenGL in the core-profile mode (modern OpenGL).

Deprecated functions in immediate mode (legacy OpenGL) are not permitted.

The key 2D operations of our current interest include: (1) The drawing of polygons and the scan

conversion of their interior pixels so that they will have a solid appearance; (2) The display of polygons

including both convex and concave ones (please note that the concave cases are in the BONUS part);

(3) The application of various standard 2D transformations and manipulations to simple polygons; (4)

The basic clipping operations; (5) The morphing of one simple polygon to another one.

Before you continue, please review the course materials and the handout documents carefully. If

you have difficulties understanding the materials, you could refer to the original textbook Computer

Graphics with OpenGL Fourth Edition.

Please refer to the TA Help Page for general requirements, and take note that all deadlines are

strictly enforced. To prevent late submissions caused by network issues, avoid submitting at the last

minute! Please also note that your credits for this programming assignment will be scaled by 50%

(i.e., from 200 + 60 to 100 + 30) on Brightspace to match the overall grading schemes.

1 Creation (40 points)

The major concern of this part is the creation and scan-conversion of 2D polygonal primitives, as well

as edge-edge self-intersection detection.

These features require you to mathematically understand the process to compute the intersection

of one line segment and another. If you are having difficulties understanding these concepts, you are

strongly recommended to go back to the lecture slides and the attached materials.

Please also note that, in the base part of this assignment, all polygons are guaranteed to be convex,

i.e., you do not have to consider concave polygons. The handling of concave polygons is left for the

BONUS part.

1.1 Simple Case (20 points)

Draw a triangle and scan-convert all of its interior pixels so that the triangle will have solid shading.

Then, extend the drawing capability to display a quadrangle and a pentagon.

You are required to implement the scanline polygon fill algorithm. Other algorithms (like the

flood-fill algorithm) are not permitted. The program should support the display of multiple polygons

at the same time. For simplicity, we assume that the user will switch to other parts and then switch

back to this part before adding the second, third, ... polygon. For this part, you are only required to

consider the simple convex polygons, i.e., you don’t need to handle edge-edge self-intersection and

concave cases.

1

The user will press key 1 to enter this part. The user will left-click the mouse to add vertices and

right-click the mouse to add the last vertex and finalize the polygon. After each left click, you should

display a wireframe polygon by connecting all added vertices with line segments. After the last right

click, the polygon should be scan-converted into a solid one.

To provide users with a better experience, within the creation mode and modification mode, the

vertices of the polygon should be displayed as highlighted by calling glPointSize(9.0f). In all

other modes, the vertices should not be highlighted.

1.2 General N-gons (20 points)

Extend the previous part to the scan-conversion of general any-sized polygons (i.e., n-gons). For this

part and all the subsequent parts, you must test the simpleness of the input polygon by checking

whether any two edges intersect with each other besides their endpoints. You should print out a

warning message whenever the user makes a polygon complex (i.e., not simple). When the user

leaves the creation mode (part 1) or the modification mode (part 2), all complex polygons created in

these modes should be deleted.

We have explained different ways to detect edge-edge self-intersections in our lectures extensively,

and you are free to use different methods and techniques to provide the correct detection. You are not

required to use the methods discussed in our lectures, but you should ensure that your implementation

works correctly and robustly and can handle all different cases without any problem!

2 Deformation (20 points)

Implement the polygon modification feature. Please note that your program should always repeat the

already-implemented functionalities whenever and wherever you deform the polygon, i.e., redrawing

the newly deformed polygons, detecting and discarding the complex polygons, re-filling the interior,

etc. When the user leaves the creation mode (part 1) or the modification mode (part 2), all complex

polygons created in these modes should be deleted.

The user will press key 2 to enter this part. The user will left-click the mouse to select the nearest

vertex (from one of the multiple polygons added in previous parts) and drag the mouse to move it to

a new location. If there are multiple nearest vertices, you may select a random one. You do not need

to implement the move animation, i.e., no visual output is required when dragging. But, when you

release the left mouse button, the vertex should be at the new location, and the polygon should be

re-filled.

Again, for this question, all polygons are guaranteed to be convex, i.e., you do not have to consider

concave polygons. The handling of concave polygons is left for the BONUS part.

3 Geometric Transformations (49 points)

Implement the following fundamental 2D geometric transformations on polygons created in previous

parts. The user will press key 3 to enter this part and left-click the mouse to select a polygon. For

simplicity, a polygon is selected as long as the click-point is inside its bounding box. If the mouse

click involves multiple candidate polygons, you may select a random one. As feedback, you should

display the bounding box of the selected polygon. Furthermore, the user should be able to unselect

all polygons by right-clicking the mouse.

2

Once again, to provide users with a better experience, in the transformation mode, the vertices

of the bounding box should be displayed as highlighted. In all other modes (where a bounding box

should be displayed), the vertices should not be highlighted.

The following transformations will be applied to the selected polygon. Again, a transformation

animation is not required, but the polygon should be transformed and re-filled after you have done

mouse input. And again, for this question, all polygons are guaranteed to be convex.

3.1 Translation (7 points)

Translate the selected polygon by dragging the vertices of its bounding box while pressing the T key.

The translation vector is the same as the displacement vector of the bounding box’s top-right corner.

3.2 Rotation (7 points)

Rotate the selected polygon with regard to its centroid by scrolling the mouse’s middle button.

Scrolling up means counter-clockwise rotation, and scrolling down means clockwise rotation. You

should follow the standard graphics pipeline: First, you translate the rotation center to the origin.

Next, you rotate the polygon with regard to the origin. Finally, you translate the rotation center back

to its original position.

3.3 Scale (7 points)

Scale the selected polygon by dragging the vertices of its bounding box. The drag will deform the

bounding box while keeping its bottom-left corner unchanged. The scaled polygon should fit its new

bounding box.

3.4 Shear (7 points)

Shear the selected polygon by dragging the vertices of its bounding box while pressing the CTRL key.

Denote t = (tx, ty) as the displacement vector of the bounding box’s top-right corner, w as the width

of the viewport, and h as the height of the viewport. The shear vector is defined as:

s = (sx, sy) =

(

tx

w

,

ty

h

)

.

3.5 Reflection (21 points)

Reflect the selected polygon with respect to:

• (7 points) Line x = c;

• (7 points) Line x− y = 0;

• (7 points) An arbitrary line y = ax+ b.

The parameters c, a, and b are to be loaded dynamically from the configuration file. The configuration

file pa2/etc/parameters.txt contains two lines. The first line contains one

integer t which could take one of the following three values:

• t = 1. In this case, reflect w.r.t. line x = c;

3

• t = 2. In this case, reflect w.r.t. line x− y = 0;

• t = 3. In this case, reflect w.r.t. line y = ax+ b.

The second line contains three space-separated floating point numbers, separately denoting c, a, and

b. (Depending on the value of t, some or all of these values may be redundant.)

The user will click the middle button of the mouse to reflect the selected polygon. The user could

press the R key to show or hide the reflection line (note that, a line has infinite length, and thus should

pass through the whole viewport!) The user should also be able to update the parameters at run time.

As a concrete example, the user should be able to:

1. Press the R key to show the reflection line l1;

2. Click the middle button to reflect the selected polygon w.r.t. l1;

3. Press R to hide l1;

4. Modify the configuration file so that it represents another line l2;

5. Press R again to show l2;

6. Click the middle button again to reflect the polygon w.r.t. l2.

4 Clipping (36 points)

Implement the clipping operation on convex polygons (concave polygons are left for the BONUS

part).

Please note that you must implement the clipping operation as-is. That is, you first determine the

new vertex list of the clipped polygon with the Sutherland-Hodgman polygon clipping algorithm, and

then re-rasterize the polygon. Tiny differences in implementation details are acceptable; however, it is

considered unacceptable to apply brute-force methods like “rasterize the whole polygon and traverse

all its interior pixels to decide which pixels to keep/discard”.

The user will press key 4 to enter this part. The user will then select a polygon-to-clip as in part

3. Then, the user has the following two options:

4.1 Line Clipping (9 points)

The user will first left-click and then right-click the mouse to specify the start pointA and the endpoint

B of a line. You should display a preview of the clipping line as the user moves the mouse after the

left click. When the user right-clicks the mouse, the right side of vector AB should be clipped. Then,

all existing clipping primitives are removed, and the user should be able to specify the next clipping

primitive.

4.2 Window Clipping (27 points)

The user should be able to clip the selected polygon with another simple convex polygon (clipping

window). For simplicity, the clipping window is guaranteed to be simple and convex, and contains no

more than 5 edges (i.e., no more complicated than a pentagon). After a target polygon is selected, the

user would specify the clipping window as follows:

1. Left-click the mouse to specify the first vertex;

2. Press and hold the B key to claim that he or she is to add more vertices;

3. Use a sequence of left clicks to add more vertices;

4

4. Release the B key, and right-click the mouse to claim that the clipping window is finalized.

Your program should display a preview of the clipping window during the process above. After the

right click, the exterior side of the clipping window should be clipped. Then, all existing clipping

primitives are removed, and the user should be able to specify the next clipping primitive.

5 Decoration (25 points)

Your program should support the following three display modes: (1) WIREFRAME mode, which is

self-explanatory; (2) SOLID mode, which fills the interior pixels of our polygons; (3) DECORATION

mode, where you could decorate your polygons with any meaningful line art, textures, or images

toward visual richness.

The user should be able to switch between these display modes by pressing the D key. The default

display mode should be the WIREFRAME mode. Please note that the decoration functionality should

be available for the entire program (i.e., in all parts.)

6 Morphing (30 points)

Figure 1: Illustration for a 2D morphing example (i.e., continuously changing from the source polygon

to the target polygon.

Polygon morphing is to transform one polygon Ps (where s denotes the source) into another

polygon Pd (where d denotes the destination). Your program should handle the task of 2D polygon

morphing, which has been explained in the lecture (please also refer to Figure 1). You could set up

your own correspondence rules. For simplicity, you could assume that the two polygons have the

same number of vertices (the minimum complexity is highlighted in Figure 1).

The user will press key 6 to enter this part. The user will first select a polygon as Ps. Ps should

have its bounding box highlighted. The user will then left-click another polygon as Pd. If Pd’s

number of vertices differs from that of Ps, you should unselect all polygons and print out an error

message. Otherwise, you should also unselect all polygons and play the morphing animation. After

the animation, you should restore the morphed polygon to its original status.

5

Again, for this question, all polygons are guaranteed to be convex, i.e., you do not have to consider

concave polygons. The handling of concave polygons is left for the BONUS part.

7 BONUS (80 points)

7.1 Concave Polygons (20 points)

Extend all of the functionalities mentioned above to support concave polygons. Note: For the clipping

feature, you should support both line clipping and window clipping. The guarantees on clipping

windows (i.e., being simple and convex, containing no more than 5 edges) remain unchanged.

Please note that, you must implement the Weiler-Atherton algorithm as-is. It is acceptable if there

are tiny differences in your implementation; however, it is considered unacceptable to apply brute-

force methods like “rasterize the whole polygon and traverse all its interior pixels to decide which

pixels to keep/discard”.

7.2 Concave Clipping Window (20 points)

Extend your clipping functionality even further to handle both concave target polygons and concave

clipping windows. That is, the clipping window is only guaranteed to be simple. It could be either

convex or concave, and it could have an arbitrary number of edges. As a concrete example, you should

be able to clip one polygon with another polygon, both of these polygons could be either convex or

concave, and the selected polygon may be clipped apart (into multiple residues).

Again, you must implement the Weiler-Atherton algorithm as-is. It is acceptable if there are

tiny differences in your implementation; however, it is considered unacceptable to apply brute-force

methods like “rasterize the whole polygon and traverse all its interior pixels to decide which pixels to

keep/discard”.

7.3 Non-linear Morphing (40 points)

Try to implement at least one non-linear interpolation method for the polygon morphing part. The

minimum complexity is detailed in our lectures. Please be specific about what non-linear method(s)

you are employing, and explain why you choose such methods.