Solution to Assignment 7

Problem 1: (xmin, ymin) = (50, 50); (xmax, ymax) = (150, 100)
Recall that:

b0 = 1 if y > ymax (and zero otherwise)
b1 = 1 if y < ymin
b2 = 1 if x > xmax
b3 = 1 if x < xmin

Case 1: if o0 = o1 = 0 we render the entire line.

Case 2: if o0 = 0 and o1 != 0 (or vice versa) we must clip

Case 3: if o0 & o1 != 0 discard the entire line

Case 4: if o0 & o1 = 0 we may or may not have to clip, depending on intersections.

a) P0 = (25, 75), outcode o0 = 0001; P1 = (30, 125), outcode o1 = 1001

Because o0 & o1 = 0001 is not zero, the line is discarded.

b) P0 = (100, 70), outcode o0 = 0000; P1 = (125, 120), outcode o1 = 1000

o0 & o1 = 0; o0 = 0, o1 != 0; Therefore we need to clip.

delta_y / delta_x = (y1 - y0) / (x1 - x0) =(120 - 70) / (125 - 100) = 2

Intersection at top border (ymax = 100):
(ymax - y0) / (x - x0) = (100 - 70) / (x - 100) = 2
y = 100, x = 115

Values of x and y at clipped point: (115, 100)

c) P0 = (100, 25), o0 = 0100; P1 = (175, 75), o1 = 0010

o0 & o1 = 0, we must compute intersections to determine whether clipping is needed.

Intersections are computed as for part b.

Intersection with lower border (y = 50) occurs at x = 137.5,
i.e. (x, y) = (137.5, 50)

Intersection with right border (x = 150) occurs at y = 58.33,
i.e. (x, y) = (150, 58.33)

These intersections are within the boundary of the clipping rectangle, so we must clip.

Problem 2: Liang-Barsky clipping.

We use the same clipping boundaries as in problem 1.

P1 = (30, 80); P2 = (90, 110)

Parametric representations:

x = x1 + alpha(x2 - x1); x = 30 + alpha(60)
y = y1 + alpha(y2 - y1); y = 80 + alpha(30)

Border	k	pk	qk	alpha_k
Left	1	-60	-20	1/3
Right	2	60	120	2
Bottom	3	-30	30	-1
Top	4	30	20	2/3

Negative pk's: p1 and p3.
Maximum of alpha1, alpha3 or 0 is alpha1 = 1/3.
u1 = 1/3

Positive pk's: p2 and p4.
Minimum of alpha2, alpha4 or 1 is alpha4 = 2/3.
u2 = 2/3

u1 < u2 so we must clip at alpha = u1 and alpha = u2.

(x, y) values at alpha = u1 = 1/3:

x = 30 + alpha(60) = 30 + (1/3)(60) = 50
y = 80 + alpha(30) = 80 + (1/3)(30) = 90

(x, y) values at alpha = u2 = 2/3:

x = 30 + (2/3)(60) = 70
y = 80 + (2/3)(30) = 100

Therefore we clip at (50, 90) and (70, 100)

Problem 3: Line drawing

a) Use DDA algorithm to draw a line between
(x1, y1) = (2, 3); (xf, yf) = (9, 8)

Slope of line = delta_y/delta_x = (8 - 3)/(9 - 2) = 5/7

First point: x = 2, y = 3

Second point: x = 3, y = 3+5/7; Plot (3, 4)

Third point: x = 4, y = 3 + 10/7 = 4 + 3/7; Plot (4, 4)

Fourth point: x = 5, y = 4 + 8/7 = 5 + 1/7; Plot (5, 5)

Fifth point: x = 6, y = 5 + 6/7; Plot (6, 6)

Sixth point: x = 7, y = 5 + 11/7 = 6 + 4/7; Plot (7, 7)

Seventh point: x = 8, y = 6 + 9/7 = 7 + 2/7; Plot (8, 7)

Eigth point: x = 9, y = 7 + 7/7 = 8; Plot (9, 8)

b) Use the Liang-Barsky algorithm to draw a line between
(x1, y1) = (2, 3), (xf, yf) = (8, 7)

First, compute values:
delta_x = 6, delta_y = 4, 2*delta_y = 8; 2*delta_y - 2*delta_x = -4;
p1 = 2*delta_y - delta_x = 2

First, Plot (x1, y1) = (2, 3)

At each step, if pk < 0, then

plot the next point at xk+1, yk;
p(k+1) = pk + 2*delta_y = pk + 8

If pk > 0 then

plot the next point at xk+1, yk+1
p(k+1) = pk + 2*delta_y - 2*delta_x = pk - 4.

k	(xk, yk)	pk	(x(k+1), y(k+1))	p(k+1)
1	(2, 3)	2	(3, 4)	-2
2	(3, 4)	-2	(4, 4)	6
3	(4, 4)	6	(5, 5)	2
4	(5, 5)	2	(6, 6)	-2
5	(6, 6)	-2	(7, 6)	6
6	(7, 6)	6	(8, 7)	2

Therefore, we plot pixels at:
(2, 3), (3, 4), (4, 4), (5, 5), (6, 6), (7, 6), (8, 7)

Home | | Syllabus | | Assignments | | Documentation

Constance Royden--croyden@mathcs.holycross.edu
Computer Science 384
Date Created: August 17, 1999
Last Modified: December 12, 2003
Page Expires: August 17, 2004