Kü thuËt §å ho¹ m¸y tÝnh
78
MÆt C¸c ®Ønh
1 1 2 3 4
2 5 6 7 8
3 1 2 6 5
4 2 3 7 6
5 3 4 8 7
6 4 1 5 8
VÏ h×nh lËp ph−¬ng theo m« h×nh trªn
Bµi tËp : BiÓu diÔn c¸c khèi ®a diÖn ®Òu vµ viÕt ch−¬ng tr×nh minh ho¹ :
1. Tø diÖn ®Òu
2. Khèi lËp ph−¬ng
3. B¸t diÖn ®Òu (8 mÆt, mçi mÆt lµ mét tam gi¸c ®Òu, 1 ®Ønh kÒ 4 mÆt)
4. NhÞ thËp diÖn ®Òu (20 mÆt, mçi mÆt lµ mét tam gi¸c ®Òu, 1 ®Ønh kÒ 5 mÆt)
5. ThËp nhÞ diÖn ®Òu (12 mÆt, mçi mÆt lµ mét ngò gi¸c ®Òu, 1 ®Ønh kÒ 3 mÆt)
6. BiÓu diÔn h×nh l¨ng trô vµ viÕt ch−¬ng tr×nh minh ho¹
$14. X¸c ®Þnh ®−êng khuÊt mÆt khuÊt
§Ó cã thÓ t¹o ra ¶nh næi trong kh«ng gian 3 chiÒu ng−êi ta ph¶i bá ®i c¸c mÆt khuÊt
®−êng khuÊt hoÆc dùa vµo mµu s¾c ®Ó t¹o nªn ®é s¸ng tèi kh¸c nhau, ®iÒu nµy dÉn
®Õn bµi to¸n x¸c ®Þnh mÆt khuÊt ®−êng khuÊt trong kü thuËt ®å ho¹
1. X¸c ®Þnh phÝa tr−íc phÝa sau cña mét mÆt
Gi¶ sö cho mét vËt thÓ trong kh«ng gian 3D ®−îc giíi h¹n bëi c¸c mÆt lµ c¸c ®a gi¸c
Mét mÆt giíi h¹n cïng vËt thÓ lµ phÇn giíi h¹n cña mÆt ph¼ng chøa ®a gi¸c ®ã gi¶
sö mÆt ph¼ng cã ph−¬ng tr×nh:
Kü thuËt §å ho¹ m¸y tÝnh
79
ax+by+cz+d=0 (*)
MÆt ph¼ng (*) chia kh«ng gian thµnh hai phÇn. Chóng ta quy −íc tÊt c¶ c¸c ®iÓm
(x,y,z) mµ ax+by+cz+d <0 lµ phÝa sau cña mÆt vµ tËp c¸c ®iÓm (x,y,z) mµ
ax+by+cz+d ≥0 lµ phÇn phÝa tr−íc cña mÆt
Víi c¸c quy ®Þnh trªn th× vËt thÓ lµ tËp hîp tÊt c¶ c¸c ®iÓm thuéc phÇn phÝa sau cña
tÊt c¶ c¸c mÆt t¹o nªn vËt thÓ
Tõ ®©y ta còng suy ra nh÷ng ®iÓm n»m vÒ phÝa sau cña tÊt c¶ c¸c mÆt t¹o nªn phÇn
bªn trong vËt thÓ, phÇn cßn l¹i cña kh«ng gian lµ phÇn bªn ngoµi vËt thÓ, suy ra
ng−êi quan s¸t cã thÓ nh×n thÊy vËt thÓ khi ng−êi ®ã ë phÝa ngoµi vËt thÓ
Gi¶ sö vËt thÓ 3D ®−îc cho bëi danh s¸ch c¸c mÆt vµ mçi mÆt lµ danh s¸ch c¸c c¹nh
hoÆc c¸c ®Ønh. Mçi mÆt lµ mét ®a gi¸c låi. Ta gi¶ sö c¸c c¹nh ®−îc ®¸nh sè theo
chiÒu ng−îc chiÒu kim ®ång hå.
Gäi
ρ
n lµ vÐct¬ ph¸p tuyÕn cña mÆt ABCD ng−îc víi h−íng nh×n tõ bªn ngoµi
Gi¶ sö ng−êi quan s¸t ë vÞ trÝ Ex y z
EEE
(,,) nh×n vµo vËt thÓ. LÊy mét ®iÓm P bÊt
kú trªn mÆt Si cña vËt thÓ khi ®ã vect¬ ep
ρ
t¹o nªn h−íng nh×n cña ng−êi quan s¸t
®èi víi mÆt Si
E
DC
b
n
a
B
A
Kü thuËt §å ho¹ m¸y tÝnh
80
n
E
P
n
a
b
XÐt tÝch c¸c h−íng ep n ep n n ep
ρ
ρ
ρ
ρ
ρ
.cos(,)= khi ®ã nÕu ep n
ρ
ρ
.
<
⇒0 gãc
(, )
ρ
ρ
nep O
<90 th× mÆt Si chøa ®iÓm P bÞ che khuÊt khi ®ã c¸c c¹nh t¹o nªn mÆt bÞ
che khuÊt kh«ng nh×n thÊy, nã t¹o nªn c¸c ®−êng khuÊt. Ng−îc l¹i nÕu
(, )
ρρ
nep O
≥90 th× ng−êi quan s¸t nh×n thÊy mÆt Si vµ do ®ã c¸c c¹nh t¹o nªn mÆt Si
kh«ng bÞ che khuÊt
Chó ý:
1. Chóng ta chó ý r»ng nÕu mÆt ph¼ng song song víi h−íng nh×n th× h×nh ¶nh cña
mÆt trªn mÆt ph¼ng chiÕu lµ mét ®o¹n th¼ng
2. ViÖc x¸c ®Þnh c¸c ®−êng khuÊt mÆt khuÊt dùa theo nguyªn t¾c trªn ®èi víi c¸c vËt
thÓ cã h×nh d¹ng tuú ý lµ rÊt phøc t¹p v× c¸c c¹nh cã thÓ bÞ che khuÊt mét phÇn do
c¸c mÆt kh¸c mµ kh«ng ph¶i bÞ che khuÊt toµn bé. Nguyªn t¾c trªn chØ thÝch hîp víi
c¸c vËt thÓ ®¬n gi¶n
α
P
E
O
n
A
C
B
Kü thuËt §å ho¹ m¸y tÝnh
81
2. ThuËt to¸n m« t¶ vËt thÓ theo ®é s©u
(Depth buffer Method)
B©y giê chóng ta kh¶o s¸t mét thuËt to¸n kh¸c - gäi lµ thuËt to¸n m« t¶ vËt thÓ theo
®é s©u, ý t−ëng cña thuËt to¸n rÊt ®¬n gi¶n lµ dùa vµo kho¶ng c¸ch gi÷a mçi ®iÓm
trªn vËt thÓ víi vÞ trÝ ng−êi quan s¸t ®Ó t« mµu s¸ng tèi kh¸c nhau
¦u ®iÓm cña ph−¬ng ph¸p nµy lµ vËt thÓ cã thÓ cã h×nh d¹ng bÊt kú kh«ng nhÊt thiÕt
lµ ®a diÖn, dÔ øng dông, dÔ hiÓu
Bµi to¸n nh− sau :
Gi¶ sö cho vËt thÓ V ®−îc giíi h¹n bëi c¸c mÆt S1,S2...... Sm, c¸c ®iÓm (i,j) thuéc
mÆt Sk cña vËt thÓ ®−îc t« bëi mµu f(k,i,j) (k=1,m) (®Ó ®¬n gi¶n ta cã thÓ gi¶ thiÕt
c¸c ®iÓm cña mçi mÆt Sk ®−îc t« cïng mét mµu fk). Gi¶ sö ng−êi quan s¸t ë vÞ trÝ
Ex y z
EEE
(
,,) vµ nh×n vËt thÓ theo h−íng OZ
S1
S2
Z
Y
O
X
ThuËt to¸n m« t¶ vËt thÓ theo ®é s©u ®−îc thÓ hiÖn nh− sau:
Ta sö dông hai m¶ng : mét m¶ng gäi lµ m¶ng depth(i,j) dïng ®Ó chøa ®é s©u theo
h−íng OZ cña ®iÓm (i,j) nµo ®ã, m¶ng thø hai lµ m¶ng cã tªn gäi color(i,j) dïng ®Ó
chøa mµu cÇn t« cña ®iÓm (i,j)
ThuËt to¸n:
1. Víi mçi ®iÓm (i,j) thuéc h×nh ch÷ nhËt bao vËt thÓ ta ®Æt
Kü thuËt §å ho¹ m¸y tÝnh
82
depth(i,j):=0; color(i,j):=<mµu nÒn>
2. For (mçi ®iÓm (i,j) thuéc h×nh ch÷ nhËt bao vËt thÓ) Do
Begin
For k:=1 To m Do
Begin
If (®iÓm (i,j) thuéc mÆt Sk) Then
Begin
TÝnh ®é s©u cña ®iÓm (i,j) thuéc Sk : z:=(-aki-bkj-dk)/ck
If (z<depth(i,j)) Then
Begin
depth(i,j):=z; color(i,j):=f(k,i,j);
End;
End;
End;
End;
3. Víi mçi ®iÓm (i,j) thuéc h×nh ch÷ nhËt bao vËt thÓ
vÏ ®iÓm (i,j) b»ng mµu color(i,j);
4. KÕt thóc
¦u ®iÓm cña thuËt to¸n nµy nh− trªn ®· nªu ®¬n gi¶n, dÔ ¸p dông cho mäi ®èi
t−îng. NhiÒu lóc nã cßn cã −u ®iÓm lín h¬n lµ víi vËt thÓ phøc t¹p, sè mÆt t¨ng lªn
sè phÐp tÝnh kh«ng t¨ng. Nh−îc ®iÓm lín nhÊt lµ kÝch th−íc cña 2 m¶ng t¨ng nhanh
khi ®é ph©n gi¶i cña mµn h×nh t¨ng
Chó ý: NÕu c¸c mÆt cña vËt thÓ lµ c¸c ®a gi¸c nghÜa lµ mét phÇn cña mÆt ph¼ng:
ax+by+cz+d=0
khi ®ã viÖc tÝnh ®é s©u z ®−îc tÝnh theo c«ng thøc:
z
x
b
y
d
c
kkk
k
=
−
−
−
3. ThuËt to¸n x¸c ®Þnh vËt thÓ theo ®−êng quÐt
Ph−¬ng ph¸p nμy cßn cã tªn gäi lμ thuËt to¸n scan-line
ý t−ëng cña thuËt to¸n nh− sau: