Course: Computer Graphics (tvf GC,;)

Homework #: 1 (SOLUTION)
Assigned on: 8th May 2006
Due on: 25th May 2006 (Quiz in class)
Question # 1: Solve these questions from the exercise given at the end of chapter 2: 2-4, 2-5, 2-
6,2-8,2-9,2-10,2-11,2-12,2-13.

2-4
For 12 bits/Dixel
1. 640X480 ~ X 12 bits/~ = 3686400 bits =460800 bytes =O.46MB.
2. 1280X1024 pixel X 12 bitsl~ = 15728640 bits = 1966080 bytes = 1.96MB.
3. 2560X2048 pixel X 12 bitsl~ =
62914560 bits =7864320 bytes =7.86MB.
For 24 bits/Dixel
1. 640X480 ~X24 bits/~= 7372800 bits = 921600 bytes = 0.92MB.
=
2. 1280X1024 pixel X 24 bits/pixel 31457280 bits =3932160 bytes =3.93MB
3. 2560X2048 ~ = =
X 24 bitsJfH*e' 125829120 bits 15728640 bytes 15.72MB =
2-5
=
8"X10"converted into pixels 8X100X10X100 800 X 1000 =
8OOX10OOpixel X 6 bits/pi}(el =4800000 bits =600000 bytes 0.6MB =
2~ .
Transfer of bits per second = 105 bits
For a frame buffer sized 640X480 with 12 bits/pixel
640X480~X 12bits1~
10 bitslsec = 36.86sec
For a frame buffersized 1280X1024with24 bits/pixel
1280X1024~X24bit61~
10 bitslsec
= 314.57sec = 5.24min
2-8
Resolution: 640X480, refresh rate: 60Hz
Pixels/second =640X48OX60 = 18432000
Time to access one pixel =1/18432000 =5.4X10.8sec
Resolution: 1280X1024,refresh rate: 60Hz
Pixels/second=1280X1024X60=78643200
Time to access one pixel= 1/78643200 = 1.27X1 o-B see
2.9 .
Radius of a pixel = R &Area of the pixel = 1T~
As the aspect ratio is 1, so
=
1280X1024X1T~ 12X9.6
=
R2 2.79X10'5"
=
R 5.28X10-3.,
= =
Diameter RX2 10.56X10-3..
2-10
Refresh rate =60 frames/sec &total number of pixels in one sec = 1280X1024X60 =78643200
Time to refresh one pixel = 1/78643200 = 1.27X10-8sec
Time to refresh one row = 1280X1.27X10-8 =1.627X10.5sec
2-11

~:~~ } ON PfrGr~ ~
Question # 2: If the image has a height of 2 inches and aspect. ration of 1.5, what is its width?

Aspect ratio =width/height? 1.5 =widthl2 ? width = 1.5X2 = 3

1
Question # 3: If we want to resize a 1024X768 image to one that is 640 pixels wide with the
same aspect ratio, what would be the height of the resized image?

Considering 1024[Width(W1)] and 768{Height(H1)]. As the aspect ratio is the same so:
=
W11H1 =W2IH2 -7 1024/768 640/H2 -7 H2 = (640X768)/1024 -7 H2 = 480

Question # 4: Sometimes the pixel at the upper left comer of an image is considered to be at the
origin of the pixel coordinate system (a left-handed system). How to convert the coordinates of a
pixel at (X,y)in this coordinate system into its coordinates (x', y') in the Iower-teft-corner-as-origin
coordinate system (a right handed system)?

Where m is the number of pixels in the y-direction, (x', y') =(x, y-m-1).
Question # 5: A run-length encoded message is 8(9)4{1)5(3). What will be the de-coded
message?

8(9)4(1)5(3)= 8888888884555

Question # 6: In the class, we constructed the lineDDAalgorithm in which the tine was drawn
from left to right. Write a similar lineDDA algorithm in which line processing and drawing is done
from rightto left.

Question # 7: We studied the bresenham's tine drawingalgorithmfor a < m < 1. Modify the
algorithm, so that the algorithmalso draws lines witharbitraryslopes. Also writethe pseudo code
for the whole algorithm {take a look at [Hearn & Baker, pg 92D.

Question # 8: In class we discussed the derivation of a circle in the 90°-45° octant. Derive and
corne up with the algorithmfor a circle in the 0°-45° octant Show all steps of the derivation and
the algorithm.

Question # 9: Consider the end-points of the following lines: (25, 14) & (30, 20), (1, 6) & (6, 1),
=
(2,1) & (2,G), (20, 10) & (25, 15). Draw these lines, using the following algorithms: y m.x + b,
lineDDA, Generalized bresenham's line drawingalgorithmdeveloped in question 7.

Question # 10: When 8-way symmetry is used to obtain a full circle from pixel coordinates
generated from 0° to 45°, or from goo to 45° octant, certain pixels are set twice or plotted twice.
This phenomenon is caned as [Link] overstrike occurs? Is overstrike harmful
besides wasting time?

See Figure on the right. Overstrike occurs at the 8 points shown on the
figureat righti.e. (O,r) and (r, 0) and all the points plottedw.r.t these by
symmetry.

No, overstrike is not harmful besides wasting time.

Question # 11: When 4-way symmetry is used to obtain a full ellipse from pixel coordinates
generated for the first quadrant, does overstrike occur? Where?

Just like the circle but at the 4 locations with coordinates (O,rx)and (a, ry) and their symmetrical
positions.

Question # 12: How can we eliminate overstrike?

2
 Can be eliminated by checking each pixel before writing to it. Ifthe pixel has already been written
to, no pixel is written.

Question # 13: The coordinates of the vertices of a polygon are shown in the followingfigure. (a)
Write the initialedge list of the polygon and (b) fillthe shape using the scan-line polygon fill
algorithm.
10
E6
9 V
I- - - 1I5

S E614 .
- Vf - V7 V4 ...
4

. 1v3
6 E7 E3
.
E8 . E2
x 11m
oJ ---- --
Edge ymin ymax E1
3 V1 V
E2 5 7 9 0
E8 5 7 2 0 1
E4 7 9 8 0 1
E6 7 9 4 0 -
1 1 3 oJ 5 6 S 9 10
Scan line 5: Fills the line from updated point
(2, 5) to (9, 5), again updates the table as
follows: removed from the edge list. The table is now
Edge ymin ymax x 11m u dated as:
E2 6 7 9 0 Ed e min max x 11m
E8 6 7 2 0 E4 8 9 8 0
E4 7 9 8 0 E6 8 9 4 0
E6 7 9 4 0 Scan line 8: Fills the line from updated point
Scan line 6: Fills the line from updated point (4, 8) to (8, 8), again updates the table as
(2, 6) to (9, 6), again updates the table as follows:
follows: Ed e min max x 11m
Edge ymin ymax x 11m E4 9 9 8 0
E2 7 7 9 0 E6 9 9 4 0
E8 7 7 2 0 Scan line 9: Fills the line from updated point
E4 7 9 8 0 (4, 9) to (8, 9). As ymin = ymax for E4 and
E6 7 9 4 0 E6, they now become de-active and are
Scan line 7: Fills the line from updated point removed from the edge list. The Edge list is
(2, 7) to (9, 7). As ymin =ymax for E2 and now empty and the algorithm termionates for
E8, they now become de-active and are this polygon.

Question # 14: Write a recursive pseudo code procedure to implement the boundary-fill algorithm in its
basic form, using the 8-connected definition for region pixels.

void boundaryFil18(int x, int y, int fill, int boundary)

Int current = getPixel(x, y);

If ((current != bo~ndary) && (current != fill»
{
setColor (fill) ;
setPixel(x, y);

BoundaryFil18 (x + 1, y, fill, boundary);

BoundaryFil18 (x - 1, y, fill, boundary);
BoundaryFil18 (x, y + 1, fill, boundary);

3
 BoundaryFil18 (x, y - 1, fill, boundary);
BoundaryFil18 (x + 1, y + 1, fill, boundary);
BoundaryFil18 (x + 1, y - 1, fill, boundary);
BoundaryFill8 (x - 1, y + 1, fill, boundary);
BoundaryFil18 (x - 1, y - 1, fill, boundary);

Question # 15: Write a recursive pseudo code procedure to implementthe flood-fillalgorithm in its basic
form, using the 8-connected definitionfor region pixels.

void floodFill8(int x, int y, int fill, int oldColor)

If (getPixel(x, y) == oldColor)
{
setColor(fill);
setPixel(x, Y)i

floodFill8 (x + 1, y, fill, oldColor);

floodFill8 (x - 1, y, fill, oldColor);
floodFill8 (x, y + 1, fill, oldColor);
floodFill8 (x, y - 1, fill, oldColor)i
floodFi1l8 (x + 1, y + 1, fill, oldColor);
floodFi1l8 (x + 1, y - 1, fill, oldColor);
floodFi1l8 (x - 1, y + 1, fill, oldColor)i
floodFi1l8 (x - 1, y - 1, fill, oldColor)i

Question # 16: (a) Findthe matrixthat represent a rotation by 30° counter-clockwiseabout the origin(b)
What are the new coordinates of the point P(2, -4) after the rotation.
Question # 17: Perform a 45° clockwise rotationof a triangle A(O,0), 8(1, 1), C(5, 2) (a) about the origin
and (b) about a fixed point(-1, -1).
Question # 18: Solve these questions from the exercise given at the end of chapter 5: 5-6, 5-7, 5-8, 5-9,
5-10,5-11,5-12,5-13, fi H. 5--15.

-
-

QUESTION:tt= 16Lb)

f<3D· P
-*"
'I').. .n/2. 0 *"1-
/ -'h o\rl
00' ,

-
-- J3 + 2-
4
1- 2J3 I
 QU€STIDN l:fl£\) W5,. = f3-/2 , V[Link] {i/2-

-.[if').. 0 0 1
R-t . Ob \ rJ.
0
1i/2-
0
Ii/ ).. 0
0 I
I 2- . '::
1 I {\
, r o.[i
I' 0
I) T"'IA.-k.
":f..{i/:;.
$hI
l-o ;j
[Link].T-'.Ob 2.) R.o"'Ak.-
3) Tro..t-\.h, C4.4-t. b II t.k

D 1 0 I S
Io 0
,
-I
- t \ \J2./z.
Ii".. -(i/2-
6/z. 0
0
1

0 l' D t 2.
. _, _ J
::. \ (.[2.-t)fJJ2.-')
?t/2.(Ii -I)
1/£.J2. _I)

o 0 \ II 0 0 1
\1 0 0 I 1 "
\ L I I I
c ~lJG~TIDN 1F ,8 tr;j~oMe.l:ric... ;d~~. .
;)-b ~ L9'1+ &2,.)::: ~e-, ~9-). - 5l¥\9',.$U1
i-L
(1\) ((L&,). R (&2-);;' ~ l &;1-). R(&, ) sin (9', t 6').): ~ 9-,SL¥\9-:L+
s~9-, <.&!>
&2-
LH~ ::
c.e:9', ~~&,
~U'\ 90,
- ~~,
° ~9-:a.
0 ,s(..VU9-:3,.
-~~&-1- 0 -
~ 9-1.0 -
t8~'l..8~&2.-~ifl&I~;'I8>, -c.cS9'.si,'\&",.

\ o l> J1\ 0 0' 1 r

- I~, ~&)._SlY\
9',~~ &-2,- ~ &,s~9-2.- ~Wv9-,~ 9'L 0
~Wv&,~" -t~9-IS~,. -~~, ~~1.+ t.6-S9-,
W!>E1-2,.
0
o 0 I
-- ~Le-, +9'2.) - ~~(8-c t9-z) 0 14~~.J.~ +rl'a°V\.O~
~~l9-I-\-9':a.) ~ t9',+(};z..) D ~ ..4~~
o o I1

- !.~9-r0
~t9-1 0
D \1

-s.~e-c ~~f}2-- CM&,S,~2- 0

-S<M,&, s~).
o--t:LM&-l (.(%l9-J- 0'

-- ~t&l + 9',..) _ SWvL9-c 1- &-2.) 0

U}S (So, f t9-).) 0

~lG-1 +9-,)
o I
D

A~ LH& =- R H-S
5
\..k.Y\c.L 1>ro\J e.J .
~_b r
[Z) S,. ~).. =- S)... ':>,

LH-S::: 51y.. 0 O 52.~ D 0 51)(.52." 0

[ oo &1'1
0
0
]l
10
0 521
D
0::
I] [
0
0
5,'1. S].'f
0

~ rt
f;-":f-
--

~W) g~~ ~'f. == g'l ~ ==- .

. ProV'f- ~ G. ~ ~ R. S 'ttrY ~ &~£t
5~
-SS~& 0
L-H-~:::. \~ 0 0 ~e- _S~~ 0
D ~ 0 s~€Y ~tr 0 ;: bS~e-- ~~9' 0
o 0 I l\ t) 0 \ \ 0 0
,
L&Sf} - VY\I& D f, D
RW =- \ vW&-- tiH. 0 0 S D :: s. .s &- 0
D 0 I 0 0 D1 lS& 0 -S$o 01
(

LrtS RB-<;, [Link]

6
. Wv cJ. I G..f< t IZ.S'tj)
5 V\.lM _ rV1
 1 C t){l S.x 0 ?Lc.(I-<;)()
- S~e--
D I t~
~&
SWvEf ~ g, 'f
Ji-c.{t-~e-)+at.s~e-
c, (t -~ 8') _ ')(.c.5 ~
l 0 t;1 'f ~ ( 1 - t; 'I )
001 \ l DOl J 0 0 1

S)£ ~& _ ~'/ ~vwe- ?Lc.(I-s'Y.~&) + ~~ Sy s ~~

~ ,I 0 t;>(
o ( t'f S'f ~~ 5.'{ ~& 'J~ (( - 5'( ~&) - 'X.,~S't. S vvv&
00\ \\ ,0 0 J

-;:. ~)( LB-'>.fT' - ~y ~WvfF '}l.(. (\ - ~I})

S,:: -I- '/ c- ~'I $~ -t b< .fA~.QA

)
l s,/ $ ~
o
Si
0
UJ.-!,fF ~ (. (I _ ~'f eM &) - )<.c- $" ~ INvI)- -t t i
(
\I H ~D
-- -

~J R(~D) ~ l: -i ~1 R~~~ ~~D ~~ ~1

fZ(~D).ReJ
-\ O ' 0 O
- D I O w~[Link] ~,~[Link]
. 1x = \ D 0 0 -\ - l0 t D 0 to ~ovv
~ o 0 , Il0 0'
()
} 0 , ~ [Link](
~({;' -~,)
D -\ 0 -l 0 0
~-\O t<.lqo) ~ RRJ :::
\ 0 0 -1ft 0 I 0
~o 0 ,1 l 0 0 I1

D -l 0 -I Dol r0 -I
(Z (q D).
R
~ i:::
::.
-' 0

l o
1
0
0 0
I \l 0 0 ,
0
0
10\ \ 0

W ~ ch ~[Link] -t,o
vVvt~ - ~~)
 o -, 0 0 I 0::'
o 0 I o 0 ( 0 -I D

W~ . , 0 0 I
. Lh 9lAAN~ to ~rot;~ o...b~ -UJ..
UYtr-C<LWvoJ.i /5Y;r I~ 1)-= ,gO. [ws /80 = ~I ~ ~ Igo ",0)=

,_\~ ~~ OLbuvJ; [Link] ~ ~ w1~

~~
I) Tl"'llN\.t..toXe.~
'/:: rV\. 'f, -\ b
to fht- lrf i r
Lo..AIv b..e.- r.~...(Yt,uf;
iJ
~
tYaN\J..I()..k:.e..
M.
~ _(.QO'fdi"a.!c.

~ D\. b' i~ 'I" i V\.W eLp t .

\tAtXcri I

J.) RotQ..t;e, tv ~r" [Link] t Vv-e, '/. - o...'t~ i..:-<- . R-o \;o-D- ~
~ Le- ff .\WU:;' .(-tAJ.- ~ t'\I'\..OJu v<J1..J.h -t ~ 1<..~x LA
~) ~cX' tJA1VV ~ x.. o-x i;..
4) R--otetli b~t-K
~) \ r()..N'.h\~ b~U::.
' D 0
')TY'~\~ ~l)( 1)h.u1, D I - b1
l o D I

:2.) R-o\7~ ~')( ~ uxo-- a...vu! ~~e-I 5.0 ~"'1

~ lfoJ,u.V..cM.: (~1o ~ ~)
I~ ~ ~~~ we ~'LA fr..\tAL ~ (rYl)
.'NV= r~ /rwvv = tevvvfY (Jrw\.&- :: 5.w,&-/tM&-)

vv\, -:: S lM.J & ~ / 9'

l4Wv% .IW.- 1Ar; FD~ ;~~ $i", ~+ ~z.B- =-J - (I)

!!,u,.br,\1 ~ ~ \I 6\) !:, [Link]- =- rVU.t9~ 8-

liM> l. & t
VV\1.. [Link]>). &: I

~2-f} =- (11" m).):::- I 8

~2..e--;;:. 1/(I+m2-)
I ~ e.-;:. I /./ , + N12- 7
 NOCA1

(;~h' ~
~~{}I rvt t
v~
~~8' =-
15' ~
I
()- ~ s~ 1m
.. '2 l-
~ Wv 2...f} -t W1 S iN\. f)- .:::. ,
W)'2-

~ ~ 2.. ~ -t tv') 2.~ ~ 2..8-- =- rYJ2- I -~'Jtt ;1-

~;:;:;;;). 0
Gwtl-9- Lf-fm2.):: m2..
'Y{f.t';1, ~;t;;. 0
~~l. 9-';:: mJ. /( 11" VV\1..) D 0

~ ~~&-- ==- W\ /[ l-tm2- ~

o
3) R~~ .vuJMi< r o -l
o V ~]
4-) fZot~ bo..~

5") T('~l~ bavk:

~ ~ ~Uj~ 6)) lYllNv\.tvr lV\.oJ-t~ w1LL

1 .It I . R;)\ . R ·T -I
s- ,~ K e1 . Ref. : \t0 \ 1"" 0
a - 1 0 -' 0 0
-1 ~::.')( 1 ~ 0 0 -\ 0 0 = 0 -
~ ")C 1

00,00 It I1 [ 001
J ()
1

\NvWctv v" ~~v~ -w 011\£; rot~ ~()1.A..t ~

~ d..Wva;t.t, 6Y L-F ,3- e-:: ('30. (ux 180::. -I ) S 1M" 180 :: 0)
GU~~T(DN "#" .~)
a-II ru.,oLul-t~ 6)) YY\~ Y\"XI'Y\ (rYI~U\.¥\~/n pi1CeU~

y-~ U h, I"o.1L r f().Ml'.U> I ~0

ltuYi ~ rdf-o..c:- *~ ~ ll'U'ti,uJ reLro..cL tVCf' .
\otCAl r~(UL ~ piftCM'V\L :: (M-l)th01 tt"e.r.

d.-Id-. ruo~ 1:2.80x ID2-t I ~h.., ro::Lt 60 tI~

l~ :: ('J-t ~ £WJ;l {Vif == roo fH . I

p~_~ \!~ vW..JIAL~~o.. (rY\-IHhov +ivu- .

-= \010)( (f-l~ + (OOtts = 1123 X Sfts
~ ~6 IS'"f~ (5'( {.~ I( W1&.

1-\~ As ~ ~ 1.4 ~ /[Link], IN-e (jMA ~

~:1A l,O\,otArS l~~ ~) .

£,\~ ~ fr~ ~ :::: $'1'2..-1< ~11-:: 2& X 28 ::: 21t.

~~ lo~ Wv~1r~~'
~ I~ (j).JA ~~ ib 6'A.t ~ 2-14 U> (,0 lM"S tA.t' ~

?O~ ~ ~.

10
 -~U6STIDN # 8

~
1M,~
dLr~,,~
~~ 00_ 0
~
D ttlLV\.t.
~ J..h,
~
~
ctr-o.M~
DttD..ht I

u.W..t ~tr~r-t ~ ~ ~~ a-~xiA

cwJv pll)/.e.t. P ~i hcYv 01).. LGL1UAJ.M-G Ol I I It. /.11 ~ I<
t>a {"V\clWva k ~J--po~ ~ x-tV:u"o 7<k_1 1<.1(-1 XK

~ -IW.- pixet i). pLotUd o-X (~, aK)~ ~ ~6YW-to

pivt }W., V\h,(t p~e11 ~ ~ 1:0 um.6i d.u- 0.- pmM.x
~~ ~ ("t.K, ~K-I"I) CLv\d. ()I."_I' Mkt,) 0<.AAtl -/W.-
ux-elL ~ chlYV\ V, ~ [Link] M

R. =. f urtle, ('J<.K- 112. , ~Ktl):: (')(1< - '12.) 1+ (tl" T I) 1_ 11-'-0

~ pI£. <0 (XI<' ~)<:-tl) ~ ~.[Link] GUA<:l ~

PI<-» 0 ('4-" ~K.-tl) wU1 ~ silicJ-d 0
NOw fuv ~ V\Ur lx~
P\(.ot\:: [Link] (~-I-I/2.' ~K.-tlt I)
n ~ ~ ~

rKtl " (~_I - '/1.) -\- (~\t.-tl-t \")

2. '2.
- A, 1-

PM I =-lrtt<-I-'h) t~~I<.-t\)tl J -Iv

?Kt I - PI£. =. l (t.t<-I -Ih) t [(~K t I). -t IJ

~ - ,.: J - i - 112.)\ {~kt",)l-~I
(xI<-

Pil-t1- .PI<.=- 0-K_.-11:1.)1.-t (~~ '+ I -t 2.(jl:.t I) -;t - (xI<-- '/2.)2.- (a,0'l) '"+ y
Rtl - PI<- = (-)("\:-1 - 11:1Ytit 2.( j 1'0 t I) - (I<". - 1/2. ) >-
PK-t\ - PI<. = 1<.:_1 t t a( ~ I<--t
X - ")(.."-1 I) - x.; - X -t?L"
PKtl
- Pit-::' ()l.K~1 -?l;) - ?LI<) -t ,;U d
- ()I."_I I< -t I) + I

PKt I " PI<. t (l<.:> x.:) - (1<-"-1- ?tt<) t ~L ~I<-t I ) + I 11

No to, )(, K_\ taNv h.~ M-o \[Link]
 jb Pi<. <0 ,~ 'X.K_1 = 14

PK-t I ~ Pr, 1" (~-?C4') - Cit:.-~I'.) + d-1QI<. -t I) + I

P~-tl;;' PK. + '?-(dk. -t I) + I

PIL-tI ;;. PK- t .;( ~ k.~ I -t I

~ PK., 0 , ~ 1<-\(_1 =- -I?<.k

PIt-t, =- PIL t [(?tf<. -I ) '- 1<.:J - (?f!1<.- I -'11<.) -t d./M K t I) + I

p!(-t I =- PIl- + ~+ \ - ;A)( K - *'.( ) + I + ,;U ~ K t I) + I

Pitt I =- PIl- + I- ~?tl< +I+ ;;t a I<-tI +I

rIt -t \ ;;. r -a
\(. ')tK ;- I + a ~ IL-t I ;- I

PM! :: - d-(J<.K-1) + .l~I<.-t1 t

PI<. I

P1<.tt ~ p~ - a?L!(_I -t ;;t ~ ~-t, t I

~I>vl~ I ~ ~ !-\.AL P lU" ~ po UL\A- ~ CA1 UA 10..kef

bo w. ~~ ~ vo.J..w., (1", 0 )
o 2 L).
'0: (0- \/')..) t (Ot\)-Iv

. f. =- '/ + 1/ 4 - 'Y+ I -K
P. :: ~/'t - ""
Po~ I-Jv

12
 ~~#VVVV
CD Jrv?!.At f'~ Y ~ UAAtex- (It", de.).
C0 ObtOvVW ~ iWst: po~ (1<.01jo) =- (Y, 0) .

~ ~ ro =I-Jv

@ ~t~~ K= 0 I oJj Wif1j ~K p~i ~J pifF"rvv+t4

W>t:
~ ~ PI<- <D) plot (f(J<.'tlKtl) cwJ
f\(t l =- P~ + ~~ K.+' T I

-> ~ PK 70 } pLot ('X.K_1, ~\(.tl) ~

PK-t I =- ?\l. - ~')lI<_1 t ~~IUI -t I
~ Dtt~ ~~t pO~ ~.fht- ~ o~
oct~ ~ plot ~. _ .

[> ~ pw <.1 1'0 J).; [Link] ~ "1t D4~

'1-= Ilt~" wvJ-- ~=- d -I:~c- .

ID ~ hLV ~ ~ 0:'- ')(. '16 ~O-~.