intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Đồ họa máy tính - Chương 3: Một số thuật toán đồ họa cơ bản

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST
Báo xấu
349
lượt xem 29
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Một số thuật toán đồ họa cơ bản I. Vẽ đoạn thẳng Xét đoạn thẳng y = m.x +b có hệ số góc 00. Làm sao để vẽ đoạn thẳng nối (x1,y1) (x2,y2) trong khi ta chỉ có thể ra lệnh cho màn hình vẽ từng điểm ảnh (kiểư như PutPixel của TP)? Làm sao vẽ đoạn thẳng nối 2 điểm này

Chủ đề:

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

Lưu

Nội dung Text: Đồ họa máy tính - Chương 3: Một số thuật toán đồ họa cơ bản

  1. Đồ họa máy tính - Khoa CNTT - ĐHSPHN Chương III: Một số thuật toán đồ họa cơ bản I. Vẽ đoạn thẳng Xét đoạn thẳng y = m.x +b có hệ số góc 0
  2. Đồ họa máy tính - Khoa CNTT - ĐHSPHN 1. Thuật toán DDA vẽ đoạn thẳng Việc quyết định chọn yi+1 là yi hay yi+1 dựa vào phương trình của đoạn thẳng thực. (xi+1, round(y)) y (xi , yi) (xi+1, y) Ta sẽ tính tọa độ của điểm y = m (xi +1) + b thuộc về đoạn thẳng thực, sau đó chọn điểm nào gần với nó nhất trong 2 điểm, nghĩa là yi+1 = round(y) = round(m.xi+1 +b) Như vậy sẽ tốn 1 phép nhân và 1 phép cộng số thực. Để cải thiện tốc độ, người ta dùng cách sau để khử phép nhân. Nhận xét rằng: yi = m.xi + b yi+1 = m.xi+1 +b ⇒ yi+1 = yi + m Begin Lưu đồ thuật toán DDA m:=dy/dx ; x:=x1; y:=y1; putpixel(x,round(y)); No x < x2 ? End Yes x:=x+1; y:=y+m; PutPixel(x,round(y)); Ví dụ: Cho A(12,20) và B(22,27), ta có m=0.7 http://www.ebook.edu.vn 40
  3. Đồ họa máy tính - Khoa CNTT - ĐHSPHN i xi yi y 0 12 20 20 1 13 21 20.7 2 14 21 21.4 3 15 22 22.1 4 16 23 22.8 5 17 24 23.5 6 18 24 24.2 7 19 25 24.9 8 20 26 25.6 9 21 26 26.3 10 22 27 27 Thuật toán DDA vẽ đoạn thẳng { Vẽ đoạn thẳng trong trường hợp 0
  4. Đồ họa máy tính - Khoa CNTT - ĐHSPHN 2. Thuật toán Bresenham vẽ đoạn thẳng (xi+1,y) yi+1 P d2 y d1 yi S xi+1 xi Trong hình vẽ (xi+1,y) là điểm thuộc đoạn thẳng thực, ta có: y = m(xi+1) + b. Giả sử ở bước i ta đã xác định được điểm (xi,yi). Đặt d1 = y – y1 ; d2 = (yi +1) - y ; Việc chọn điểm tiếp theo (xi+1, yi+1) là S hay P tùy thuộc vào việc d1 lớn hơn hay nhỏ hơn d2, nói cách khác là phụ thuộc vào dấu của (d1 – d2) • Nếu d1 – d2 0, ta sẽ chọn P, tức là yi+1 = yi+1 Đặt pi = dx (d1 – d2). Thay d1 = y – y1 ; d2 = (yi +1) – y vào ta có pi = dx (2y - 2yi -1) Thay y = mxi+b = dy(xi+1)/dx + b vào ta có pi = 2dx [dy(xi+1)/dx +b] – 2yidx –dx = 2xidy – 2yidx +C với C = 2dy + (2b-1)dx là hằng số. Ta nhận xét rằng, nếu tại bước thứ i ta xác định được dấu của pi thì sẽ xác định được điểm cần tô ở bước i+1. Làm sao để tính giá trị của pi ? ta dùng phương pháp “lũy tiến” như sau. Ta có: pi+1 –pi = (2xi+1dy – 2yi+1dx +C) - (2xidy – 2yidx +C) = 2dy -2dx(yi+1 – yi) • Nếu pi0 thì điểm được chọn là P, tức là yi+1 = yi+1 ⇒ pi+1 = pi +2dy -2dx Cuối cùng, giá trị p0 được tính từ điểm ảnh đầu tiên (x0, y0) theo công thức sau p0 = 2x0dy – 2y0dx + c Thay giá trị của c vào, chú ý rằng điểm đầu (x0, y0) cũng thuộc đoạn thẳng thực nên y0 = mx0 + b = x0dy/dx + b, suy ra p0 = 2dy -dx tóm lại là: http://www.ebook.edu.vn 42
  5. Đồ họa máy tính - Khoa CNTT - ĐHSPHN p0 p2 y1 ... p1 y0 y2 ... Ví dụ: Cho A(12,20) và B(22,27), ta có dx = 22 – 12 = 10 ; dy = 27 – 20 = 7; c1 = 2dy = 14 ; c2 = 2(dy-dx) = -6; p0 = 2Dy – dx = 4 i xi yi pi 0 12 20 4 1 13 21 -2 2 14 21 12 3 15 22 6 4 16 23 0 5 17 24 -6 6 18 24 8 7 19 25 2 8 20 26 -4 9 21 26 10 10 22 27 4 http://www.ebook.edu.vn 43
  6. Đồ họa máy tính - Khoa CNTT - ĐHSPHN Lưu đồ thuật toán Begin Bresenham p:=2dy - dx ; c1=2dy; c2=2(dy-dx); x:=x1; y:=y1 ; putpixel(x,y); No x < x2 ? End Yes No p
  7. Đồ họa máy tính - Khoa CNTT - ĐHSPHN dx:=x2-x1; dy:=y2-y1; p:=2*dy - dx; c1:=2*dy; c2:=2*(dy-dx); x:=x1; y:=y1; putpixel(x,y,white); for i:=x1 to x2 do begin if p
  8. Đồ họa máy tính - Khoa CNTT - ĐHSPHN • Nếu pi >0 tức là O nằm phía dưới đường thẳng ⇒ ta chọn P Làm sao để tính pi ? tương tự như thuật toán Bresenham, ta cũng dùng phương pháp “lũy tiến”, dùng giá trị ở bước trước pi để tính giá trị ở bước tiếp theo pi+1 Ta có: pi+1 – pi =2F(xi+1 +1,yi+1 +1/2) - 2F(xi +1,yi +1/2) = 2[A(xi+1+1)+B(yi+1+1/2)+C] - 2[A(xi+1)+B(yi+1/2)+C] = 2dy – 2dx(yi+1 – yi) Như vậy • Nếu pi 0 thì ta chọn yi+1 = yi+1 , do đó pi+1 = pi +2dy – 2dx Cuối cùng, giá trị đầu p0 được tính như sau: nhận xét rằng điểm đầu (x0, y0) thuộc đoạn thẳng thực tức là Ax0 + By0 +C = 0 p0 = 2F(x0+1,y0+1/2) = 2[A(x0+1)+B(y0+1/2)+C] = 2(Ax0 + By0 +C) + 2A +B = 2A+B = 2dy –dx II Vẽ đường tròn Thuật toán MidPoint A (-x, y) (x,y) B (-y, x) (y,x) (-y, -x) (y, -x) (-x, -y) (x, -y) Đầu tiên ta nhận xét rằng, do tính đối xứng của đường tròn nên ta chỉ cần vẽ được cung AB là cung 1/8 đường tròn, sau đó lấy đối xứng qua các trục và các đường phân giác ta sẽ có cả đường tròn. Chẳng hạn như ở hình vẽ trên nếu xác định được điểm (x,y), lấy đối xứng qua đường phân giác của góc phần tư thứ nhất ta thu được điểm (y,x), lấy đối xứng qua trục hoành ta thu được 2 điểm (y,-x) và (x,-y) ... Nếu ta chia thành 16,32 ... phần thì việc xác định tọa độ 15,31... điểm đối xứng còn lại sẽ rất khó. Còn nếu chia thành 4 hay 2 phần thì số điểm lân cận cần phải loại trừ có thể nhiều hơn 2 điểm. http://www.ebook.edu.vn 46
  9. Đồ họa máy tính - Khoa CNTT - ĐHSPHN yi S Q(xi+1,y) yi-1 P M: điểm giữa xi xi+1 Gọi R là bán kính đường tròn, ta xuất phát từ điểm A (0,R) để vẽ cung AB. Nhìn hình vẽ ta thấy, nếu (xi, yi) là điểm ảnh đã vẽ được ở bước thứ i thì điểm ảnh (xi+1, yi+1) ở bước tiếp theo chỉ có thể là S hoặc P, tức là • xi+1 = xi + 1 • yi+1 ∈ {yi, yi-1} Giống như thuật toán vẽ đoạn thẳng, ý tưởng chính để lựa chọn giữa S và P ở đây là căn cứ vào vị trí tương đối của điểm giữa M của SP với đường tròn. Nếu M nằm bên trong đường tròn như hình vẽ thì ta sẽ chọn S vì nó gần điểm thực Q hơn so với P. Ngược lại nếu M nằm ngoài đường tròn thì P sẽ được chọn. Đặt F(x,y) = x2 + y2 – R2 , các định lý toán học cho ta biết rằng • F(x,y) 0 nếu điểm (x,y) nằm ngoài đường tròn Đặt pi = F(M) = F(xi+1,yi – ½) ta có • Nếu pi
  10. Đồ họa máy tính - Khoa CNTT - ĐHSPHN Lưu đồ thuật toán Begin MidPoint vẽ đường tròn p:=5/4 -R; x:=0; y:=R ; PutPixel8(x,y); No x
  11. Đồ họa máy tính - Khoa CNTT - ĐHSPHN mau:=random(GetMaxColor); {Vẽ đường tròn MidPoint màu ngẫu nhiên } x:=0; y:=R; PutPixel8(x,y,mau); p:=1-R; while (x
  12. Đồ họa máy tính - Khoa CNTT - ĐHSPHN 1001 1000 1010 D C E ymax B 0001 F J L 0000 A K’ 0010 J’ K I’ ymin 0101 0100 0110 I xmin xmax Cách làm: đầu tiên ta nhận xét rằng một điểm P(x,y) nằm trong cửa sổ (được nhìn thấy) khi và chỉ khi thỏa mãn đồng thời 2 điều kiện xmax ≥ x ≥ xmin ymax ≥ y ≥ ymin Ngược lại, nếu một trong 2 điều kiện bị vi phạm thì P nằm ngoài cửa sổ và sẽ không được hiển thị. Các đoạn thẳng chỉ có thể thuộc một trong những trường hợp sau: • Hoàn toàn nằm trong cửa sổ, ví dụ như AB, khi đó cả 2 đầu mút đều nằm bên trong cửa sổ • Hoàn toàn nằm ngoài cửa sổ (bị che toàn phần), ví dụ như CD, EF • Chỉ một phần nằm trong cửa sổ và được hiển thị, ví dụ như KL và IJ Đầu tiên, thuật toán Cohen – Sutherland dùng 4 đường thẳng chứa cạnh cửa sổ chia mặt phẳng thành 9 phần. Mỗi điểm A(x,y) thuộc mặt phẳng sẽ được gán mã 4 bit abcd theo cách sau: • a=1 ⇔ y > ymax : A nằm phía trên cửa sổ • b=1 ⇔ y < ymin : A nằm phía dưới cửa sổ • c=1 ⇔ x > xmax : A nằm phía phải cửa sổ • d=1 ⇔ x < xmin : A nằm phía trái cửa sổ Khi đó, ta nhận xét rằng: • đoạn thẳng sẽ hoàn toàn nằm trong cửa sổ nếu cả 2 đầu mút đều bằng 0000 • đoạn thẳng sẽ hoàn toàn nằm ngoài cửa sổ nếu kết quả phép AND của 2 đầu mút khác 0000 Thực vậy, nhận xét đầu là hiển nhiên. Để minh họa cho nhận xét 2, xét đoạn thẳng EF: E = 1010, F = 0010 ⇒ (E) AND (F) = (1010) and (0010) = 0010 ≠ 0 bit thứ 3 của cả 2 đầu mút E và F đều bằng 1, chứng tỏ chúng đều nằm bên phải cửa sổ, do đó cả đoạn thẳng dĩ nhiên cũng nằm bên phải cửa sổ và sẽ không được hiển thị. Vấn đề còn lại là, nếu kết quả phép AND hai đầu mút bằng 0000, khi đó thuật toán sẽ tìm giao của đoạn thẳng với các biên của cửa sổ và xét từng phần của nó. Ta ký hiệu 4 đường thẳng chứa cạnh cửa sổ là: http://www.ebook.edu.vn 50
  13. Đồ họa máy tính - Khoa CNTT - ĐHSPHN • đường 1: y = ymax • đường 2: y = ymin • đường 3: x = xmax • đường 4: x = xmin Khi đó nhìn vào mã của 2 đầu mút ta sẽ biết ngay đoạn thẳng đó cắt cạnh nào của cửa sổ. Ví dụ: 4 3 ymax 1 0001 J L 0010 K’ J’ K I’ ymin 2 0100 I xmin xmax Xét đoạn IJ • Mã của I = 0100, bít thứ 2 =1 nên chắc chắn nó sẽ cắt đường 2 • Mã của J = 0001, bít thứ 4 =1 nên chắc chắn nó sẽ cắt đường 4 Xét đoạn KL • Mã của L = 0100, bít thứ 3 =1 nên chắc chắn nó sẽ cắt đường 3 Việc xác định tọa độ giao điểm là rất đơn giản vì ta đã biết rõ 2 đầu mút. Sau khi chia đoạn thẳng thành các đoạn, ta lặp lại thuật toán với mỗi đoạn chia cho đến khi kết thúc. Ví dụ ta xét đoạn IJ • Bước 1: kết quả phép and bằng 0 nhưng 2 đầu mút khác 0: tìm giao điểm với biên I’ • Bước 2: loại đoạn II’ • Bước 3: xét đoạn JI’ : tìm giao điểm J’ • Bước 4: loại đoạn JJ’. Kết thúc với đoạn I’J’ được hiển thị 2. Thuật toán Sutherland - Hodgman Bài toán: ta cần cắt 1 đa giác bất kỳ Y vào trong cửa sổ là một đa giác lồi X. Cách làm: Ta sẽ duyệt lần lượt các cạnh của X, với mỗi cạnh đó ta lại xét lần lượt cạnh của Y. Kết quả sau khi xén với cạnh thứ i (của cửa sổ X) sẽ được dùng để xén với cạnh tiếp theo i+1 của X. Quy tắc là: http://www.ebook.edu.vn 51
  14. Đồ họa máy tính - Khoa CNTT - ĐHSPHN • nếu cạnh đang xét của Y đi từ trong cửa sổ ra ngoài (Pi-1 ở trong, Pi ở ngoài) thì chỉ giữ lại giao điểm I của Pi-1 Pi với cạnh đang xét của X. • nếu cạnh đang xét đi từ ngoài vào trong (tức là Pi-1 ở ngoài, Pi ở trong): giữ lại giao điểm I và Pi • trường hợp cạnh ở ngoài hoàn toàn: loại bỏ • trường hợp cạnh ở trong hoàn toàn: giữ lại Pi . V C A P Q B R H G J D E I U T M K F Ví dụ Đầu tiên ta xét cạnh UV của cửa sổ cắt là tam giác UVT. Cạnh đang xét (theo chiều vecto) Hướng đi Quyết định giữ lại AB (xét với UV) Từ ngoài vào trong P,B BC (xét với VT) Trong ra ngoài Q CD Ngoài vào trong R,D DE Hoàn toàn nằm trong E EK (xét với TU) Trong ra ngoài M KF Hoàn toàn nằm ngoài Loại hết FG Ngoài vào trong I,G GH (xét với UV) Trong ra ngoài J HA Hoàn toàn nằm ngoài Loại hết Ta thu được đa giác (theo thứ tự): P,B,Q,R,D,E,M,I,G,J như hình vẽ Đoạn mã giả (pseudocode) sau minh họa cho thuật toán trên. t:=1 for i:=1 to n do {Đa giác cửa sổ X có n cạnh} for j:=1 to m do {Đa giác bị cắt Y có m cạnh } k:=j+1; {Xét cạnh XjXj+1 của đa giác cửa sổ X} if k>n then k:=1 ; if (Xj ở trong) then http://www.ebook.edu.vn 52
  15. Đồ họa máy tính - Khoa CNTT - ĐHSPHN begin if (Xk ở trong) then Yt := Yk else Yt := giao điểm của XjXk với cạnh i của X t:=t+1; end else if (Xk ở trong ) then begin Yt := giao điểm; t:=t+1; Yt := Xk ; t:=t+1; end; Vấn đề: cho tọa độ 1 điểm, làm sao biết điểm đó ở trong/ngoài đa giác lồi X ? Bổ đề: nếu điểm đó nằm bên phải 1 cạnh nào đó của đa giác lồi X theo chiều dương thì nó nằm ngoài X. Nếu nó nằm bên trái tất cả các cạnh thì nó nằm bên trong X B(x2,y2) P(x,y) chiều dương bên phải A(x1,y1) bên trái Bổ đề: cho vector AB và điểm P(x,y), P nằm bên trái vector AB (như hình vẽ) nếu và chỉ nếu (x2 – x1)(y – y1) – (y2 – y1)(x – x1) >0 Ta công nhận, không chứng minh bổ đề toán này. Vấn đề: cho tọa độ tập đỉnh của đa giác lồi X dưới dạng 1 danh sách có thứ tự (nghĩa là nếu biết 1 đỉnh thì ta luôn biết 2 đỉnh kề của nó), làm sao xếp chúng lại “theo chiều dương” ? Cách làm: Chọn đỉnh có hoành độ nhỏ nhất, ký hiệu là A như hình vẽ. Gọi 2 đỉnh kề nó là B,C trong đó xB < xC. Thứ tự theo chiều dương sẽ là BAC. Sau đó ta chỉ việc đi tới đỉnh tiếp theo C ... Thật vậy, ta có thể thấy rõ khi nhìn hình vẽ. Chỉ có 3 trường hợp: • B,C nằm ở 2 phía của đường thẳng x = xA • B,C cùng nằm bên phải đường thẳng đó • B,C cùng nằm bên trái http://www.ebook.edu.vn 53
  16. Đồ họa máy tính - Khoa CNTT - ĐHSPHN B C C C B B A A A 2. Clipping một đoạn thẳng vào đường tròn A A D d d B C O O A B B (a) (b) (c) Gọi d là khoảng cách từ tâm O tới đoạn thẳng AB. • Nếu d > bán kính r ⇒ clip(AB) = ∅ • Nếu d = bán kính r ⇒ clip(AB) = {điểm tiếp xúc} • Nếu d < bán kính r, ta chia thành 3 trường hợp o Cả A,B đều nằm trong đường tròn: clip(AB) = AB o Một trong hai điểm (giả sử là A) nằm ngoài đường tròn. Gọi C là giao của AB với đường tròn ta có clip(AB) = BC o Cả 2 cùng nằm ngoài đường tròn, xét dấu: Nếu (xA-xC) (xB-xC) 0 thì clip(AB)=∅ (trường hợp (b)) IV. Tô màu vùng khép kín Cho một vùng khép kín được giới hạn bởi một đường biên đồng màu. Vấn đề đặt ra là tô màu cho miền trong của vùng đó. Có 2 phương pháp chính: tô theo dòng quét (scan line fill) và tô dựa theo đường biên (boundary fill). 1. Thuật toán tô màu theo đường biên (Boundary algorithm) Cách tô này yêu cầu phải biết trước tọa độ một điểm (điểm “gieo”) nằm bên trong vùng cần tô. Bắt đầu từ điểm đó ta sẽ tô “loang” dần ra các vùng xung quanh bằng việc đọc màu của các điểm lân cận để kiểm tra xem chúng đã được tô màu hay chưa. Nếu đã được tô, http://www.ebook.edu.vn 54
  17. Đồ họa máy tính - Khoa CNTT - ĐHSPHN hoặc màu của điểm lân cận là màu của biên thì dừng lại và xét điểm khác, nếu không thì tô điểm lân cận đó. Có vài phương pháp khác nhau để xác định lân cận như: loại 4 điểm, loại 8 điểm Lân cận 4 điểm Lân cận 8 điểm Procedure BFill ( x,y,c,B:integer) {(x,y) điểm đang xét, c: màu tô, B: màu đường biên } Var t: integer; Begin t:=GetPixel(x,y); if (t B) and (tc) then { putpixel(x,y,c); BFill(x-1,y,c,B); BFill(x+1,y,c,B); BFill(x,y-1,c,B); BFill(x,y+1,c,B); } Cách làm như trên có nhược điểm là khi gọi đệ quy cho 4 điểm lân cận không xét tới việc chúng đã được kiểm tra ở các bước trước hay chưa. Cần có cải tiến để không xét lại những điểm đã được kiểm tra rồi. 2. Thuật toán tô màu dựa theo dòng quét (Scan-line algorithm) Giả sử dùng cần tô là một đa giác N đỉnh {Pi =(xi,yi)} i=1..N Ta sử dụng 1 dòng quét song song với trục Ox đi từ đỉnh trên cùng (Ymax) đến đỉnh dưới cùng (Ymin) của vùng cần tô. Với mỗi giá trị y = yi, dòng quét cắt các đường biên của vùng cần tô tạo thành các đoạn thẳng. Ta tô màu các điểm nằm giữa hai đầu mút của các đoạn thẳng đó. http://www.ebook.edu.vn 55
  18. Đồ họa máy tính - Khoa CNTT - ĐHSPHN Ymax Ymin Các bước: - Xác định Ymax, Ymin của đa giác cần tô - Với mỗi dòng quét y = yi (Ymin ≤ yi ≤ Ymax), xác định hoành độ giao điểm với các cạnh của đa giác - Sắp xếp chúng theo thứ tự tăng dần thành các cặp (x0, x1) ... - Tô các đoạn (x0, x1), (x2, x3), (x4, x5) ... Tuy nhiên, có một ngoại lệ là khi dòng quét đi qua đỉnh P của đa giác. Khi đó ta phải chia thành 2 trường hợp: - Nếu 2 cạnh kề của P có hướng ngược nhau, một cạnh đi lên một cạnh đi xuống thì trong danh sách giao điểm ta sẽ tính là 2 giao điểm có tọa độ trùng nhau ở đỉnh P. Nghĩa là xi = xi+1 = xP - Nếu 2 cạnh kề của P cùng hướng nhau, cả hai cùng đi lên hoặc đi xuống thì P chỉ được tính là 1 giao điểm. 1 4 2,3 2 3 1 http://www.ebook.edu.vn 56
ADSENSE

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.

 

Đồng bộ tài khoản
2=>2