zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Đồ họa - Thiết kế - Flash

Bài giảng đồ họa : Các thuật toán xén điểm, đoạn thẳng part 2

Chia sẻ: Ashfjshd Askfaj | Ngày: | Loại File: PDF | Số trang:5

Báo xấu

67
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Như vậy việc tìm đoạn giao thực chất là tìm nghiệm của hệ bất phương trình này. Có hai khả năng xảy ra đó là : ♦ Hệ bất phương trình vô nghiệm, nghĩa là đường thẳng không có phần giao với cửa sổ nên sẽ bị loại bỏ. ♦ Hệ bất phương trình có nghiệm, lúc này tập nghiệm sẽ là các giá trị t thỏa t ∈ [t1 , t2 ] ⊆ [0,1] .

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng đồ họa : Các thuật toán xén điểm, đoạn thẳng part 2

ÑOÀ HOÏA MAÙY TÍNH p1 = − Dx, q1 = x1 − x min p2 = Dx, q2 = x max − x1 • Ñaët p3 = − Dy, q3 = y1 − y min p4 = Dy, q4 = y max − y1 • Luùc naøy ta vieát heä phöông trình treân döôùi daïng :  pk t ≤ qk , k = 1,2,3,4  0 ≤ t ≤ 1 • Nhö vaäy vieäc tìm ñoaïn giao thöïc chaát laø tìm nghieäm cuûa heä baát phöông trình naøy. Coù hai khaû naêng xaûy ra ñoù laø : ♦ Heä baát phöông trình voâ nghieäm, nghóa laø ñöôøng thaúng khoâng coù phaàn giao vôùi cöûa soå neân seõ bò loaïi boû. ♦ Heä baát phöông trình coù nghieäm, luùc naøy taäp nghieäm seõ laø caùc giaù trò t thoûa t ∈ [t1 , t2 ] ⊆ [0,1] . • Ta xeùt caùc tröôøng hôïp : ♦ Neáu ∃ k ∈ {1,2,3,4} : ( pk = 0) ∧ (qk < 0) thì roõ raøng baát phöông trình öùng vôùi k treân laø voâ nghieäm, do ñoù heä voâ nghieäm. ♦ Neáu ∀ k ∈ {1,2,3,4} : ( pk ≠ 0) ∨ (qk ≥ 0) thì vôùi caùc baát phöông trình maø öùng vôùi pk = 0 laø caùc baát phöông trình hieån nhieân, luùc naøy heä baát phöông trình caàn giaûi töông ñöông vôùi heä baát phöông trình coù pk ≠ 0. ♦ Vôùi caùc baát phöông trình p k t ≤ q k maø p k < 0 , ta coù t ≥ qk / pk . p k > 0 , ta coù ♦ Vôùi caùc baát phöông trình p k t ≤ qk maø t ≤ qk / pk . Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn xeùn hình 7/11
ÑOÀ HOÏA MAÙY TÍNH • Vaäy nghieäm cuûa heä baát phöông trình laø [t1 , t2 ] vôùi :   qk  , pk < 0 U {0}) t1 = max(  pk     qk   , p k > 0 U {1}) t2 = min(  pk   t ≤ t 1 2   Neáu heä treân coù nghieäm thì ñoaïn giao Q1 Q2 seõ laø • Q1 ( x1 + t1 Dx, y1 + t1 Dy), Q2 ( x1 + t2 Dx, y1 + t2 Dy) . • Neáu xeùt thuaät toaùn naøy ôû khía caïnh hình hoïc ta coù : ♦ Tröôøng hôïp ∃ k ∈ {1,2,3,4} : ( pk = 0) ∧ (qk < 0) töông öùng vôùi tröôøng hôïp ñoaïn thaúng caàn xeùt song song vôùi moät trong caùc bieân cuûa cöûa soå ( p k = 0 ) vaø naèm ngoaøi cöûa soå ( q k < 0 ) neân seõ bò loaïi boû sau khi xeùn. ♦ Vôùi p k ≠ 0 , giaù trò t = rk = q k / p k seõ töông öùng vôùi giao ñieåm cuûa ñoaïn thaúng vôùi bieân k keùo daøi cuûa cöûa soå. Tröôøng hôïp p k < 0 , keùo daøi caùc bieân cöûa soå vaø ñoaïn thaúng veà voâ cöïc, ta coù ñöôøng thaúng ñang xeùt seõ coù höôùng ñi töø beân ngoaøi vaøo beân trong cöûa soå. Neáu pk > 0 , ñöôøng thaúng seõ coù höôùng ñi töø beân trong cöûa soå ñi ra. Do ñoù hai ñaàu muùt cuûa ñoaïn giao seõ öùng vôùi caùc giaù trò t1 , t2 ñöôïc tính nhö sau : Giaù trò t1 chính laø giaù trò lôùn nhaát cuûa caùc rk = q k / p k maø p k < 0 (ñöôøng thaúng ñi töø ngoaøi vaøo trong cöûa soå) vaø 0; giaù trò t2 chính laø giaù trò nhoû nhaát cuûa caùc rk = qk / pk maø p k > 0 (ñöôøng thaúng ñi töø trong cöûa soå ñi ra) vaø 1. Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn xeùn hình 8/11
ÑOÀ HOÏA MAÙY TÍNH Thuaät toaùn xeùn ña giaùc Sutherland - Hodgemand Daãn nhaäp • Chuùng ta coù theå hieäu chænh caùc thuaät toaùn xeùn ñoaïn thaúng ñeå xeùn ña giaùc baèng caùch xem ña giaùc nhö laø moät taäp caùc ñoaïn thaúng lieân tieáp noái vôùi nhau. Tuy nhieân, keát quaû sau khi xeùn nhieàu khi laïi laø taäp caùc ñoaïn thaúng rôøi nhau. • Ñieàu chuùng ta mong muoán ôû ñaây ñoù laø keát quaû sau khi xeùn phaûi laø moät caùc ña giaùc ñeå sau naøy coù theå chuyeån thaønh caùc vuøng toâ. (a) (b) (c) Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn xeùn hình 9/11
ÑOÀ HOÏA MAÙY TÍNH Thuaät toaùn Sutherland - Hodgeman • Thuaät toaùn naøy seõ tieán haønh xeùn ña giaùc laàn löôït vôùi caùc bieân cöûa soå. Ñaàu tieân, ña giaùc seõ ñöôïc xeùn doïc theo bieân traùi cuûa cöûa soå, keát quaû sau böôùc naøy seõ ñöôïc duøng ñeå xeùn tieáp bieân phaûi, roài cöù töông töï nhö vaäy cho caùc bieân treân, döôùi. Sau khi xeùn heát vôùi boán bieân cuûa cöûa soå, ta ñöôïc keát quaû cuoái cuøng. • Vôùi moãi laàn xeùn ña giaùc doïc theo moät bieân naøo ñoù cuûa cöûa soå, neáu goïi Vi , Vi+1 laø hai ñænh keà caïnh Vi Vi+1 , ta coù 4 tröôøng hôïp coù theå xaûy ra khi xeùt töøng caëp ñænh cuûa ña giaùc ban ñaàu vôùi bieân cuûa cöûa soå nhö sau: ♦ Neáu Vi naèm ngoaøi, Vi +1 naèm trong, ta löu giao ñieåm I cuûa Vi Vi +1 vôùi bieân cuûa cöûa soå vaø Vi+1 . ♦ Neáu caû Vi , Vi +1 ñeàu naèm trong, ta seõ löu caû Vi , Vi +1 . Vi vaø I. ♦ Neáu Vi naèm trong, Vi+1 naèm ngoaøi, ta seõ löu ♦ Neáu caû Vi , Vi +1 ñeàu naèm ngoaøi, ta khoâng löu gì caû. Vi I Vi+1 Vi Vi+1 Vi Vi+1 I Vi+1 Vi (i) (ii) (iii) (iv) Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn xeùn hình 10/11
ÑOÀ HOÏA MAÙY TÍNH Caøi ñaët haøm xeùn ña giaùc theo moät caïnh cuûa cöûa soå void ClipEdge(POINT *pIn, int N, POINT *pOut, int &Cnt, int Edge, RECT rWin) { int FlagPrevPt = FALSE; Cnt = 0; POINT pPrev; pPrev = pIn[0]; if(Inside(pPrev, Edge, rWin)) // Save point { pOut[Cnt] = pPrev; Cnt++; FlagPrevPt = TRUE; } for(int i=1; i

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.