Solution

Course: Homework #: Assigned on: Due on:

Computer Graphics (tvf GC,;) 1 (SOLUTION) 8th May 2006 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, 26,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. = 15728640 bits = 1966080 bytes = 1.96MB. 2. 1280X1024 pixel X 12 bitsl~ 62914560 bits =7864320 bytes =7.86MB. 3. 2560X2048 pixel X 12 bitsl~ 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 X 24 bitsJfH*e' 125829120 bits 15728640 bytes 15.72MB 3. 2560X2048 ~ 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~ = 314.57sec = 5.24min 10 bitslsec

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 Time to refresh one pixel = 1/78643200 = 1.27X10-8sec Time to refresh one row = 1280X1.27X10-8 =1.627X10.5sec 2-11

}

~:~~

ON

= 1280X1024X60 =78643200

~

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 averstriJce.Identifywhere 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

S

-

E614

-

Vf

6

ymax 7 7 9 9

x 9 2 8 4

(2, 5) to (9, 5), again updates the table as follows:

ymin ymax x 11m 7 6 9 0 6 7 2 0 7 9 8 0 7 9 4 0 Scan line 6: Fills the line from updated point Edge E2 E8 E4 E6

(2, 6) to (9, 6), again updates the table as follows:

11m 0 0 0 0 Scan line 7: Fills the line from updated point (2, 7) to (9, 7). As ymin =ymax for E2 and

Edge ymin ymax 7 E2 7 7 E8 7 E4 7 9 7 E6 9

x 9 2 8 4

E8, they now become de-active and are

V7

3

1I5

.

4

...

. 1v3

E3

.

---- --

oJ

11m 0 0 0 0 Scan line 5: Fills the line from updated point ymin 5 5 7 7

V4

E7 E8

Edge E2 E8 E4 E6

I-

- -

E1

V1

. E2 V

1 1 1

1

3

oJ

5

6

-

S 9 10

removed from the edge list. The table is now u dated as: Ed e min max x 11m E4 8 9 8 0 E6 8 9 4 0 Scan line 8: Fills the line from updated point (4, 8) to (8, 8), again updates the table as follows: Ed e min max x 11m E4 9 9 8 0 E6 9 9 4 0 Scan line 9: Fills the line from updated point (4, 9) to (8, 9). As ymin = ymax for E4 and E6, they now become de-active and are removed from the edge list. The Edge list is now empty and the algorithm termionates for 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, If ((current != bo~ndary) {

y); && (current

!= fill»

setColor (fill) ; setPixel(x, y);

BoundaryFil18 BoundaryFil18 BoundaryFil18

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

3

BoundaryFil18 BoundaryFil18 BoundaryFil18 BoundaryFill8 BoundaryFil18

-

(x, y

1, fill, boundary);

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

(x - 1, y + 1, fill, boundary); (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 floodFill8 floodFill8 floodFill8 floodFi1l8 floodFi1l8 floodFi1l8 floodFi1l8

(x + 1, (x - 1, (x, y + (x, y (x + 1, (x + 1,

y, fill, oldColor); y, fill, oldColor); 1, fill, oldColor); 1, fill, oldColor)i y + 1, fill, oldColor); y

-

1,

fill,

oldColor);

(x - 1, y + 1, fill, oldColor)i (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-

1- 2J3

I

4

QU€STIDN

W5,.

l:fl£\)

\ rJ.

R-t . Ob

= f3-/2 , V14:::

-.[if').. 0

0

Ii/ ).. 0

0

1i/20

0

1

r

I 2- . ':: 1 I {\ ,

I

o.[i

0

-I - t \ \J2./z. Ii"..

-(i/26/z.

o 0

\ II 0

0

Io

c

;)-b

,

~lJG~TIDN

D 1

0

0 1

0 l' \1 0

I) T"'IA.-k.

S

.

D t 2.

0

I

1

-

~ l &;1-). R(&, )

° ~9-:a. J1\ 0

c.e:9', ~~&, ~U'\ 90,

\

~~,

o

_,

L

_ J

I

?t/2.(Ii -I) 1/£.J2. _I)

I

I

L9'1+ &2,.)::: ~e-,

0

l>

0 ~ 9-1.0 -

-~~&-1-

,s(..VU9-:3,.

~Wv&,~" -t~9-IS~,. o

0'

1

-~~,

t8~'l..8~&2.-~ifl&I~;'I8>,

0

~~l9-I-\-9':a.)

D

o

t9',+(};z..)

o

-c.cS9'.si,'\&",.

r 9'L

0

14~~.J.~

~

I1

+rl'a°V\.O~

..4~~

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

0 \1

-s.~e-c ~~f}2--S<M,&, s~).

--

+ 9',..)

~t&l

~lG-1 +9-,)

_ SWvL9-c 1- &-2.)

0

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

0

D

A~

o

CM&,S,~2-

0

o--t:LM&-l (.(%l9-J- 0'

I

LH& =- R H-S

5 \..k.Y\c.L

1>ro\J e.J .

<.&!> &2-

~~1.+ t.6-S9-, W!>E1-2,. 0 0 I

~Le-, +9'2.) - ~~(8-c t9-z) ~

.

~9-). - 5l¥\9',.$U1 i-L

sin (9', t 6').): ~ 9-,SL¥\9-:L+ s~9-,

- I~, ~&)._SlY\ 9',~~ &-2,- ~ &,s~9-2.- ~Wv9-,~

--

;j

tr;j~oMe.l:ric... ;d~~. ~

LH~ ::

l-o

::. \ (.[2.-t)fJJ2.-')

\

"

1F ,8

(1\) ((L&,). R (&2-);;'

$hI

0

2.) R.o"'Ak.3) Tro..t-\.h, C4.4-t. b II t.k

I

0

":f..{i/:;.

I'

T.Rr.T-'.Ob 1

{i/2-

~_b

[Z)

r

S,. ~).. =- S)... ':>, 51y..

LH-S:::

[ oo

0

O

&1'1

0

52.~

0 ]l 10

0

D

0

521

0::

D

I]

51)(.52."

0

0

5,'1. S].'f

[

0

0

rt

~

f;-":f--

g~~

~W) .

ProV'f-

L-H-~:::.

~

G. ~

\~

0

=-

\

~

s~€Y

0

o

0

I

vW&-D

l\

==-

_S~~ ~tr

t)

.

~

5~ &~£t

0

0 ;:

0

\

bS~e--

\

-SS~&

0

~~9'

0

0

0

, D

f,

tiH.

0

0

0

I

VY\I&

LrtS

. Wv

5

g'l ~

R. S 'ttrY

~e-

~

-

==

0

D

L&Sf}

RW

~'f.

D

S

D

0

D1

0

RB-<;,

cJ.

::

s.

lS& 0

.s

-S$o

&-

0 ( 01

P.yD I

V\.lM _

G..f<

t IZ.S'tj) rV1

6

1 C t){l

D I t~ \

001

o

0

t;>(

(

t'f

00\ -;:.

l

SWvEf

~)(

-~

8') _ ')(.c.5

_ ~'/ ~vwe-

~&

~

l: -i

~

0

D

+ ~~ Sy s

,

D

W

~

l

Il

0

0 0

~ i:::

-\

0

~o

1

o

R~~~

0

D

0

O ()

0'

,1

0

0

~~

0

-I

\l 0

I

ch ~LA.OJ

vVvt~ - ~~)

-

}

-

0

-t,o

l 0

)

\I

H

~D -- -

D

I

O

w~t.Lv ~,~u.oJ

l0

D

0

to ~ovv

0

t

, ~ VVla.tin( ~({;' -~,)

0

0

0

I

0

0

Dol ,

.fA~.QA

~1

~~

:::

-1ft

0

~~D

-l

RRJ

0

-l

)

t; 'I

- 'X.,~S't. S vvv&

(( - 5'( ~&)

(

0

0

\

-

1

1

S,::

'

\

-\

-

O

o

~

(

~I}) -I- '/ c- ~'I $~ -t b< (I _ ~'f eM &) - )<.c- $" ~ INvI)- -t t i

(\

~1

-\

~

R

0

'f ~

J

~ (.

UJ.-!,fF

1x =

t<.lqo)

'}l.(.

0

fZ(~D).ReJ

.

'J~

?Lc.(I-<;)()

t;1

0

Si

R(~D)

l

0

0

?Lc.(I-s'Y.~&)

5.'{ ~&

- ~y ~WvfF

LB-'>.fT'

(Z (q D).

(t

c,

S.x

J

\\ ,0

l

~-\O

g, 'f

S'f ~~

s,/ $ ~ o

~J

~

Ji-c.{t-~e-)+at.s~e-

DOl S)£

,I

~

- S~e--

~&

0 I1

r0

-'

::.

0

10\

\

-I 0

0

-,

o o

W~

.

. Lh

/5Y;r

0::'

o

0

(

~rot;~ 1)-= ,gO. [ws

I~

'/::

b

rV\. 'f, -\

/80

~ ~)

\tAtXcri

Le- ff

~cX'

-I

D

0

0

I

lrf

i

~I

~

r

iJ

-UJ..

~

Igo ",0) =

w1~

~

Lo..AIv b..e.- r.~...(Yt,uf;

to fht-

=

~

M. ~ _(.QO'fdi"a.!c.

tYaN\J..I()..k:.e..

b' i~ 'I" i V\.W eLp t . J.) RotQ..t;e, tv ~r" v0i.fk t Vv-e, '/. - o...'t~ D\.

0

o...b~

~

OLbuvJ; c.wv

I) Tl"'llN\.t..toXe.~

~

I

I

to

9lAAN~

~~

~~

0

0

,

UYtr-C
,_\~

0

I

.\WU:;' .(-tAJ.- ~ tJA1VV

~

t'\I'\..OJu

i..:-<- . R-o \;o-D-

v<J1..J.h -t ~

~

1<..~x LA

x.. o-x i;..

4) R--otetli b~t-K ~) \ r()..N'.h\~

b~U::.

D

'

')TY'~\~

:2.)

~l)(

R-o\7~

~ I~

1)h.u1,

lfoJ,u.V..cM.: (~1o

~

/

vv\, -:: S lM.J & ~

l4Wv% !!,u,.br,\1

.IW.- 1Ar;

~

we

/rwvv

D

-

b1 I

5.0

~"'1

~)

~'LA

= tevvvfY

~

fr..\tAL (Jrw\.&-

::

(rYl)

5.w,&-/tM&-)

9'

;~~

FD~

~ VV\1.. liM> l. & t

6\)

\I

~2-f}

I

o

~

~~~

.'NV= r~

D

uxo-- a...vu! ~~e-I

~

~')(

l

0

c.lY>). =-

&:

!:, w.ve-

I

~

=- rVU.t9~

-

=-J

8-

I

(11" m).):::-

~2..e--;;:.

$i", ~+ ~z.B-

I

1/(I+m2-) e.-;:.

I /./ , + N12- 7

8

(I)

NOCA1

~ ~~{}I rvt t

v~

(;~h'

..

~~8'

-t W1

()- ~

s~

1m

l-

'2

~ Wv 2...f}

=-

15' ~ I

S iN\.

f)-

.:::. ,

W)'2-

~

~

2..

~

Gwtl-9-

-t tv') 2.~

9-';::

~ ~~&--

4-) fZot~

.vuJMi<

r

W\

m2..

/(

I ~;:;:;;;).

0

'Y{f.t';1, ~;t;;.

0

D

11" VV\1..)

/[ l-tm2-

o o -l o V

bavk:

~Uj~

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

1 .It I . R;)\

0

~

bo..~

5") T('~l~

~ ~

mJ.

==-

-~'Jtt ;1-

2..8-- =- rYJ2-

Lf-fm2.)::

~~l.

3) R~~

~

. R ·T -I

w1LL

~]

s- ,~

.

K e1 -1 ~::.')(

Ref. 1

\t0 \

:

~

~

")C

0 0

1""

0

1

00,00

\NvWctv ~

~~v~

v"

d..Wva;t.t, 6Y

GU~~T(DN

a-II

~

6))

::

\!~ (f-l~

?O~

()

J

001

1

~

~()1.A..t 180 ::

0)

pi1CeU~

reLro..cL tVCf' . (M-l)th01

::

~h..,

I

tt"e.r.

ro::Lt 60 tI~

roo fH .

=

I

(rY\-IHhov +ivu-

.

1123 X Sfts

1.4 ~

l~~

~

lo~

~

0

{.~ I( W1&.

~

(j).JA

==

+ (OOtts

~ fr~

~ I~

ll'U'ti,uJ

piftCM'V\L

(5'(

As ~

~~

[

-

0

180::. -I ) S 1M"

vW..JIAL~~o..

~:1A l,O\,otArS

£,\~

*~ ~

('J-t ~ £WJ;l {Vif

~6 IS'"f~

1-\~

0 = I1

Y\"XI'Y\ (rYI~U\.¥\~/n

1:2.80x ID2-t

-= \010)( ~

YY\~

rdf-o..c:-

p~_~

0

0

r f().Ml'.U> I ~0

d.-Id-. ruo~

l~

,3- e-:: ('30. (ux

r~(UL ~

\otCAl

0

.~)

"#"

U h, I"o.1L

ltuYi

It

-'

1

-w 011\£; rot~

L-F

ru.,oLul-t~

y-~

-

a -\

~~

/Pw.el,

~) ::::

IN-e (jMA ~

. $'1'2..-1<

~11-::

2& X 28

:::

21t.

Wv~1r~~' ib 6'A.t

~ 2-14

U> (,0 lM"S

tA.t'

~

~.

10

-~U6STIDN #

8

~ dLr~,,~ 1M,~ ~~ 00_

~

~

0

D ttlLV\.t.

~tr~r-t

cwJv

pll)/.e.t. P ~i hcYv

~

k

pivt

~

pI£.

('4-"

NOw fuv ~

~

PK-t\

-

-

No to,

silicJ-d

=

(~_I

-

l

(t.t<-I

~

(-)("\:-1 1<.:_1

2.

0<.AAtl -/W.-

GUA<:l

T I)

~

1_ 11-'-0

0

~

- A,

2.(

j

1'0

t I)

X - ")(.."-1 t a( ~ I<--t

taNv

1-

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

(~~ '+ I -t 2.(jl:.t I) -;t - (xI<-- '/2.)2.- (a,0'l)

- 11:1Ytit t

'2.

~

- (I<". I)

h.~

1/2.

) >-

- x.; - X -t?L"

- ()I."_I - ?LI<) -t ,;U d

t (l<.:> x.:)

)(, K_\

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

-Ih) t [(~K t I). -t IJ

()l.K~1 -?l;)

PI<.

pmM.x

~K.-tlt I)

~

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

PKtl - Pit-::' PKt I "

~.su.eLkcl

PM I

PI<.

Mkt,)

- '12.) 1+ (tl"

(')(1<

"

PI<- =

~6YW-to

V\Ur lx~

Pil-t1- .PI<.=- 0-K_.-11:1.)1.-t Rtl

~Ktl)::

rKtl

=.

7
1:0 um.6i d.u- 0.-

~K.-tl) wU1 ~

n

PI£.

It. /.11 ~ I<

I

w.icL M

P\(.ot\:: 1uA.cU (~-I-I/2.'

-

x-tV:u"o

~

~

('J<.K- 112. ,

(XI<' ~)<:-tl)

PI<-» 0

?Kt I

~

I

("t.K, ~K-I"I) CLv\d. ()I."_I'

f urtle,

<0

a-~xiA

01).. LGL1UAJ.M-G Ol

chlYV\ V,

R. =.

I

i). pLotUd o-X (~, aK)~ ~

~ ~

ux-elL

DttD..ht

~~

}W., V\h,(t p~e11 ~

~~

ctr-o.M~

~

~J--po~

pixet

-IW.-

J..h,

~ ~

u.W..t

t>a {"V\clWva

~

I<

-t I) + I

- (1<-"-1- ?tt<) t ~L ~I<-t I ) + I M-o

\Ia.tu.eA

11

'"+

y

jb PK-t I

Pi<.

Pr, 1"

~

PIL t

PIt-t, =p!(-t I

=-

,

;;.

PM!

:: ~

~I>vl~

~

[(?tf<.

1<-\(_1

-I ) '- 1<.:J

~+

PIl- +

PIl-

=-

rIt -t \

+ I-

r -a \(.

\

-

~?tl<

;A)( K

a ~ IL-t

P.

::

~/'t

I) + I

+I

I

po

UL\A-

~

CA1 UA 10..kef

L).

\/')..) t (Ot\)-Iv

(0=- '/ +

t I) + I

;- I

!-\.AL P lU" ~ 2

f.

K

vo.J..w., (1", 0 )

o

Po~

I

- d-(J<.K-1) + .l~I<.-t1 t p~ - a?L!(_I -t ;;t ~ ~-t, t I ~

?<.k

;;t a I<-tI

PI<.

I ~

'0:

-I - (?f!1<.- I -'11<.) -t d./M =-

- *'.( ) + I + ,;U ~ K t

+I+

;- I +

')tK

bo w. ~~ ~

.

+ d-1QI<. -t I) + I

~ k.~ I -t I

.;(

PK., 0

P1<.tt

- Cit:.-~I'.)

(~-?C4')

PK- t

;;.

~

Pitt I

14

=

'X.K_1

PK. + '?-(dk. -t I) + I

P~-tl;;' PIL-tI

,~

<0

1/

4 - 'Y+

I

-K

- ""

I-Jv

12

~~#VVVV CD Jrv?!.At

C0 ObtOvVW ~

~ @

iWst:

~

K= 0

W>t: ~

~

-> ~

oct~ [> ~

}

pLot

~

K.+'

~~t ~

~K p~i

~J

pifF"rvv+t4

plot

T I

('X.K_1, ~\(.tl)

- ~')lI<_1 t

~~IUI

hLV ~

~

-t I

pO~

~.

~.fht-

~

o~ .

"1t D4~

wvJ-- ~=- d -I:~c- .

~

~

_

pw <.1 1'0 J).; lu.hwl '1-= Ilt~"

ID

Wif1j

+ ~~

P~

=-

PK 70

Dtt~

(1<.01jo) =- (Y, 0) .

plot (f(J<.'tlKtl) cwJ

PK-t I =- ?\l.

~

po~

oJj

I

PI<-
f\(t l

UAAtex- (It", de.).

=I-Jv

ro

~t~~

~

Y

f'~

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