Bài giảng đồ họa : Các thuật toán tô màu part 2

Chia sẻ: poseidon07

y Min : giá trị tung độ nhỏ nhất trong 2 đỉnh của cạnh. xInter sec t : hoành độ giao điểm của cạnh với dòng quét hiện hành. DxPerScan : giá trị 1/m (m là hệ số góc của cạnh). deltaY : khoảng cách từ dòng quét hiện hành tới đỉnh

Nội dung Text: Bài giảng đồ họa : Các thuật toán tô màu part 2

ÑOÀ HOÏA MAÙY TÍNH


Ñeà xuaát caáu truùc döõ lieäu cuûa moät caïnh (EDGE)


deltaY


y=k

xIntersect


yMin



y Min : giaù trò tung ñoä nhoû nhaát trong 2 ñænh cuûa

caïnh.

xInter sec t : hoaønh ñoä giao ñieåm cuûa caïnh vôùi doøng

queùt hieän haønh.

DxPerScan : giaù trò 1/m (m laø heä soá goùc cuûa caïnh).


deltaY : khoaûng caùch töø doøng queùt hieän haønh tôùi ñænh

k > yMax
y Max .Luùc naøy ñieàu kieän trôû thaønh
deltaY ≤ 0 .

• Giaù trò xInter sec t ñöôïc khôûi gaùn ban ñaàu laø hoaønh ñoä
cuûa ñænh coù tung ñoä laø y Min , vaø giaù trò deltaY ñöôïc
khôûi gaùn ban ñaàu laø y Max − y Min + 1 .




Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 5/16
ÑOÀ HOÏA MAÙY TÍNH



Giaûi quyeát tröôøng hôïp doøng queùt ñi qua ñænh
• Tính moät giao ñieåm neáu chieàu cuûa hai caïnh keà cuûa
ñænh ñoù coù xu höôùng taêng hay giaûm.

• Tính hai giao ñieåm neáu chieàu cuûa hai caïnh keà cuûa
ñænh ñoù coù xu höôùng thay ñoåi, nghóa laø taêng-giaûm
hay giaûm-taêng.

Pi+1 Pi-1
Pi Pi-1
Pi Pi+1
Pi Pi+1

Pi-1 Pi+1 Pi-1 Pi

(a) (b)




• Khi caøi ñaët ñeå khoûi phaûi xeùt ñieàu kieän naøy cho phöùc
taïp, khi xaây döïng döõ lieäu cho moãi caïnh tröôùc khi ñöa
vaøo ET, ngöôøi ta seõ xöû lí caùc caïnh coù ñænh tính hai
giao ñieåm baèng caùch loaïi ñi moät pixel treân cuøng cuûa
moät trong hai caïnh.

Pi+1 Pi+1 Pi-1 Pi-1



y=k y=k
y=k-1 Pi y=k-1 Pi
Pi* Pi*



Pi-1 Pi-1 Pi+1 Pi+1




Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 6/16
ÑOÀ HOÏA MAÙY TÍNH



Minh hoïa thuaät toaùn
Top
F
C



D E

yG* =yG+1
G yG

yB
B
yB* =yB-1
yH*=yH+1
I H yH



Bottom
A



• Ban ñaàu :

♦ ET : AB*, AI, H*G, BC, G*F, DC, EF. (loaïi IH vaø DE)

♦ AET : NULL.

• Khi doøng queùt ñaït y=yA

♦ ET : H*G, BC, G*F, DC, EF. (chuyeån AB*, AI sang AET)

♦ AET : AB*, AI.

• Khi doøng queùt ñaït y=yH*

♦ ET : BC, G*F, DC, EF. (chuyeån H*G sang AET)

♦ AET : AB*, H*G. (loaïi AI vì khoâng coøn caét doøng queùt)



Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 7/16
ÑOÀ HOÏA MAÙY TÍNH


• Khi doøng queùt ñaït y=yB

♦ ET : G*F, DC, EF. (chuyeån BC sang AET)

♦ AET : BC, H*G. (loaïi AB*, saép xeáp laïi H*G vaø BC)

• Khi doøng queùt ñaït y=yG*

♦ ET : DC, EF. (chuyeån G*F sang AET)

♦ AET : BC, G*F. (loaïi H*G vì khoâng coøn caét doøng queùt)

• Khi doøng queùt ñaït y=yD

♦ ET : NULL. (chuyeån DC, EF sang AET)

♦ AET : BC, DC, EF, G*F. (saép xeáp laïi BC, GF*, DC, EF)

• Khi doøng queùt ñaït y=yC+1

♦ ET : NULL.

♦ AET : EF, G*F. (loaïi BC, DC vì khoâng coøn caét doøng queùt)

• Khi doøng queùt ñaït y=yF+1

♦ ET : NULL.

♦ AET : NULL. (loaïi EF, G*F vì khoâng coøn caét doøng queùt).

• Thuaät toaùn döøng taïi ñaây.




Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 8/16
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản