Bài giảng Đồ họa máy tính - Chương 2: Các phép biến đổi cơ sở

Nội dung text: Bài giảng Đồ họa máy tính - Chương 2: Các phép biến đổi cơ sở

1. TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP KHOA CÔNG NGHỆ THÔNG TIN BÀI GIẢNG MÔN ĐỒ HỌA MÁY TÍNH Số ĐVHT: 2 1
2. Néi dung m«n häc Chương 1: Tổng quan về đồ họa máy tính Chương 2: Các phép biến đổi cơ sở Chương 3: Hiển thị các đối tượng đồ họa Chương 4: Một số kỹ thuật đồ họa nâng cao
3. CH¬NG 2: C¸c phÐp biÕn ®æi c¬ së I. Giới thiệu 1.1 Giới thiệu 1.2 Các hệ tọa độ II. Các thuật toán vẽ đường thẳng, đường tròn III. Các phép biến đổi của đối tượng hai chiều IV. Kết hợp các phép biến đổi V. Một số tính chất của phép biến đổi affine VI. Một số phép biến đổi khác 3
4. CHƯƠNG II: CÁCGiíi PHÉP thiÖu BIẾN ĐỔI CƠ SỞ Bất kỳ ảnh nào cũng được cấu trúc từ tập các đối tượng đơn giản hơn.
5. CHƯƠNG II: CÁCGiíi PHÉP thiÖu BIẾN ĐỔI CƠ SỞ Với các ảnh phát sinh từ đồ họa máy tính, hình dạng và màu sắc của mỗi đối tượng có thể được mô tả riêng biệt bằng 2 mô hình: + Dãy các pixel (mô hình dựa trên mẫu số hóa), đối tượng được xây dựng từ tập các pixel. + Tập các đối tượng hình học cơ sở ( mô hình dựa trên đặc trưng hình học). Mỗi đối tượng đồ họa cơ sở được mô tả thông qua dữ liệu về tọa độ và các thuộc tính của nó.
6. CHƯƠNG II: CÁCI.Giíi GIỚI PHÉP thiÖu THIỆU BIẾN ĐỔI CƠ SỞ - Đối tượng đồ họa cơ sở đơn giản nhất là điểm và đoạn thẳng, đường tròn, các đường conics, mặt bậc hai, các vùng tô đa giác, chuỗi kí tự, - Các công cụ lập trình đồ họa cung cấp: o Các hàm mô tả một ảnh dưới dạng các đối tượng đồ họa cơ sở o Các hàm kết hợp tập các đối tượng cơ sở để tạo thành đối tượng có cấu trúc phức tạp hơn. Chương này sẽ khảo sát các thuật toán hiển thị các đối tượng đồ họa cơ sở cho các thiết bị hiển thị dạng điểm.
7. CHƯƠNG II:I. CÁC GIỚIGiíi PHÉP THIỆUthiÖu BIẾN ĐỔI CƠ SỞ Các thuật toán thực hiện quá trình chuyển đổi các đối tượng đồ họa cơ sở được mô tả trong hệ tọa độ thực về dãy các pixel có tọa độ nguyên của thiết bị hiển thị.
8. CHƯƠNG II:I. CÁC GIỚIGiíi PHÉP THIỆUthiÖu BIẾN ĐỔI CƠ SỞ Có hai yêu cầu đặt ra cho các thuật toán là : 1, Điểm nguyên xấp xỉ đối tượng tốt nhất: Do: Đối tượng được mô tả trong hệ tọa độ thực là liên tục, còn đối tượng trong hệ tọa độ thiết bị là rời rạc Nên: Đối tượng được hiển thị trên hệ tọa độ thiết bị phải “giống nhất“ với đối tượng trong hệ tọa độ thế giới thực. 2, Tối ưu hóa về mặt tốc độ: Do: Các đối tượng đồ họa cơ sở là thành phần chính cấu trúc nên các đối tượng phức tạp, Nên: Các thuật toán hiển thị chúng cần phải được tối ưu hóa về mặt tốc độ.
9. CHƯƠNG II: C¸cCÁCI. GIỚI HÖ PHÉP täa THIỆU BIẾN®é ĐỔI CƠ SỞ - Hệ tọa độ thế giới thực: Hệ tọa độ thế giới thực mô tả các đối tượng thế giới thực. Thường dùng hệ tọa độ Descartes. Các điểm trong hệ được mô tả bởi một cặp tọa độ (x, y), trong đó x, y R. Do vậy, các điểm trong hệ tọa độ thực được định nghĩa liên tục.
10. CHƯƠNG II:I. C¸cCÁC I.GIỚI GIỚI HÖ PHÉP THIỆU täa THIỆU BIẾN®é ĐỔI CƠ SỞ - Hệ tọa độ thiết bị: Hệ tọa độ thiết bị mô tả các đối tượng trong một thiết bị xuất cụ thể nào đó: máy in, màn hình, Đặc điểm của hệ tọa độ thiết bị: + Mỗi điểm được mô tả bởi một cặp tọa độ (x, y), trong đó x, y N. Do vậy các điểm rời rạc nhau . + x, y bị giới hạn trong một khoảng nào đó và tùy theo từng loại thiết bị.
11. CHƯƠNG II: C¸cCÁCI. GIỚI HÖ PHÉP täa THIỆU BIẾN®é ĐỔI CƠ SỞ - Hệ tọa độ thiết bị chuẩn: ✓ Hệ tọa độ trên các thiết bị khác nhau là khác nhau nên một hình ảnh hiển thị trên thiết bị này là chính xác nhưng có thể là không chính xác khi hiển thị trên thiết bị khác. ✓ Hệ tọa độ thiết bị chuẩn đại diện chung cho tất cả các thiết bị để mô tả các hình ảnh mà không phụ thuộc vào thiết bị hiển thị nào
12. CH¬NG 2: C¸c phÐp biÕn ®æi c¬ së I. Giới thiệu II. Các thuật toán vẽ đường thẳng, đường tròn 2.1 Các đối tượng đồ họa cơ sở 2.2 Các thuật toán vẽ đường thẳng 2.3 Thuật toán Midpoint vẽ đường tròn III. Các phép biến đổi của đối tượng hai chiều IV. Kết hợp các phép biến đổi V. Một số tính chất của phép biến đổi affine VI. Một số phép biến đổi khác 12
13. CHƯƠNGII. CÁCC¸c THUẬT II: ®èi CÁCI. t GIỚI îngTOÁN PHÉP ®åTHIỆU VẼ häa BIẾN ĐIỂM, c¬ ĐỔI së ĐƯỜNG CƠ SỞ + Điểm: Điểm là thành phần cơ sở được định nghĩa trong một hệ tọa độ. Đối với hệ tọa độ hai chiều mỗi điểm được xác định bởi cặp tọa độ (x, y). Ngoài thông tin về tọa độ, điểm còn có thuộc tính là màu sắc. Thủ tục vẽ một điểm (x,y) với mầu c: Putpixel(x,y,c)
14. CHƯƠNGII. CÁCC¸c THUẬT II: ®èi CÁCI. t GIỚI îngTOÁN PHÉP ®åTHIỆU VẼ häa BIẾN ĐIỂM, c¬ ĐỔI së ĐƯỜNG CƠ SỞ + Đoạn thẳng: Được xác định bởi: Màu sắc, độ rộng nét vẽ, kiểu nét vẽ của đoạn thẳng ( nét liền, nét đứt, chấm gạch ) Một đường thẳng được xác định nếu biết hai điểm thuộc nó (x1, y1) và (x2, y2): Ta có: y = mx + b, trong đó:
15. CHƯƠNGII. CÁCC¸c THUẬT II: ®èi CÁCI. t GIỚI îngTOÁN PHÉP ®åTHIỆU VẼ häa BIẾN ĐIỂM, c¬ ĐỔI së ĐƯỜNG CƠ SỞ + Đường gấp khúc: Tập các đoạn thẳng nối với nhau một cách tuần tự, điểm giao của hai đoạn thẳng được gọi là đỉnh. Các đường gấp khúc được xác định qua danh sách các đỉnh, mỗi đỉnh được cho bởi các cặp tọa độ. + Đa giác: Là một đường gấp khúc có điểm đầu và điểm cuối trùng nhau.
16. CHƯƠNGII. CÁCC¸c THUẬT II: ®èi CÁCI. t GIỚI îngTOÁN PHÉP ®åTHIỆU VẼ häa BIẾN ĐIỂM, c¬ ĐỔI së ĐƯỜNG CƠ SỞ + Vùng tô: Gồm đường biên (là một đường khép kín) và vùng bên trong. Xác định bởi: Thuộc tính của đường biên: là các thuộc tính như thuộc tính của đoạn thẳng. Thuộc tính của vùng bên trong: bao gồm màu tô và mẫu tô. + Kí tự, chuỗi kí tự: xác định bởi: Màu sắc của các kí tự, Font chữ, kích thước, khoảng cách giữa các kí tự, sự canh chỉnh (gióng lề), hướng hiển thị tuần tự của các kí tự.
17. II C¸c tt vÏ ®êng th¼ng, ®êng trßn 2.1 Các đối tượng đồ họa cơ sở 2.2 Các thuật toán vẽ đường thẳng 2.2.1 Mở đầu 2.2.2 Thuật toán DDA 2.2.3 Thuật toán Bresenham 2.2.4 Thuật toán Midpoint 2.3 Thuật toán Midpoint vẽ đường tròn 17
18. II. CÁC THUẬT TOÁNmë ®Çu VẼ ĐIỂM, ĐƯỜNG Gọi (xi,yi), i= 0,1, là tọa độ các điểm nguyên sau khi xấp xỉ yi các điểm thực, và là các điểm sẽ được hiển thị trên màn hình. (x ,y ) là điểm đen trên hình vẽ i i xi Nếu bước i xác định được (xi,yi ) Thì bước thứ i+1 xác định được (xi+1,yi+1) (xi+1,yi+1) là một trong tám điểm được đánh số từ 1 đến 8.
19. II. CÁC THUẬT TOÁNmë ®Çu VẼ ĐIỂM, ĐƯỜNG Xét đoạn thẳng có hệ số góc 0≤ m ≤1 và Dx >0 . y yi 0 ≤ m ≤ 1 x xi
20. II. CÁC THUẬT TOÁNmë ®Çu VẼ ĐIỂM, ĐƯỜNG Xét đoạn thẳng có hệ số góc 0 ≤ m ≤ 1 và Dx >0 . Nếu (xi,yi) là điểm đã xác định được ở bước thứ i Thì điểm cần chọn (xi+1,yi+1) ở bước thứ (i+1) sẽ là một trong hai trường hợp như hình vẽ. Như vậy : xi+1 = xi +1, yi+1 { yi, yi + 1 }
21. Thuật toán DDA (Digital Differential Analyzer) Ý tưởng: Dựa vào phương trình y = mx + b để chọn yi+1 là yi hay yi+1. t Tính tọa độ điểm Q(xi+1,y i+1) thuộc đoạn thẳng thực: Từ pt của đoạn thẳng ta có: t y i+1= mxi+1 + b t y i+1 = yi + m t yi+1 là giá trị sau khi làm tròn y i+1 : yi+1 t = round(y i+1) Do vậy: yi+1= round(yi + m)
22. Thuật toán DDA (Digital Differential Analyzer) Như vậy: Nếu bước thứ i ta vẽ được điểm (xi,yi) Thì bước thứ i+1 ta vẽ được điểm (xi+1,yi+1) Trong đó: xi+1 = xi +1, yi+1= round(yi + m)
23. Thuật toán DDA Begin m = Dy/Dx; x = x1; Giải thuật: y = y1; Putpixel(x, y, c); Sai x ≤ x2 Đúng x = x + 1; y = y + m; Putpixel(x,round(y),c); End
24. ThuậtII. CÁC toán THUẬT DDA (Digital TOÁN Differential VẼ ĐIỂM, Analyzer) ĐƯỜNG Nhận xét: t - Việc sử dụng công thức y i+1 = yi + m đã khử được phép nhân trên số thực. - Còn bị hạn chế về mặt tốc độ do vẫn còn phép toán cộng số thực và làm tròn.
25. b, Thuật toán BresenhamThuật toán Bresenham Ý tưởng: Thuật toán đưa ra cách chọn yi+1 là yi hay yi+1 theo hướng hạn chế tối đa các phép toán trên số thực. Gọi Q(xi+1,y) ϵ đường thẳng thực, ta có: y = mxi+1 + b . = m(xi+1) + b . Đặt: d1 = y – yi , d2 = (yi + 1) – y
26. b, Thuật toán BresenhamThuật toán Bresenham Xét pi = Dx (d1 – d2 ) = Dx ( 2y - 2yi – 1) → pi = Dx ( 2 ( m ( xi + 1) + b) - 2yi – 1) do m = Dy/Dx → Pi = 2xiDy – 2yiDx + c với c = 2Dy + (2b - 1)Dx Ta tính:
27. b, Thuật toán BresenhamThuật toán Bresenham Việc chọn điểm (xi+1,yi+1) là 1 hay 2 phụ thuộc vào dấu của biểu thức d1 – d2 hay dấu của pi, ta có: Nếu d1 – d2 <0 hay pi < 0 chọn 1 yi+1 = yi pi+1 = pi +2Dy Nếu d1 – d2 ≥ 0 hay pi ≥ 0 chọn 2 yi+1 = yi + 1 pi+1 = pi +2Dy – 2Dx Tính: P0 = 2x0Dy – 2y0Dx + c Do y0 = mx0+ b p0 = 2Dy - Dx
28. Thuật toán Bresenham Begin p = 2Dy-Dx C1 = 2Dy; C2 = 2(Dy-Dx) x=x1; y = y1 Putpixel(x, y, c); Giải thuật: Sai x ≤ x2 Đúng Sai p < 0 p = p + C2; Đúng y = y + 1; p = p + C1; x = x+1; Putpixel(x, y, c); End
29. b, ThuậtThuật toán toán Bresenham BresenhamThuật toán Bresenham Nhận xét: - Thuật toán Bresenham chỉ làm việc trên số nguyên - Các thao tác trên số nguyên chỉ là phép cộng Làm tăng tốc độ đáng kể so với thuật toán DDA.
30. c,b, ThuậtThuật toántoán MidpointBresenhamThuật toán Midpoint Ý tưởng: TT chọn yi+1 là yi+1 hay yi bằng cách so sánh vị trí tương đối giữa trung điểm M(xi +1, yi + ½) của 1 và 2 với đường thẳng thực. Từ pt đoạn thẳng y = mx + b xDy – yDx + c = 0 Đặt F(x,y) = xDy – yDx +c Đặt pi = 2F(M)=2F(xi +1, yi + ½) pi = 2(xi+1)Dy - 2(yi+1/2)Dx + 2c Ta tính: p – p i+1 i = 2 ( xi+1 – xi)Dy – 2 ( yi+1 – yi)Dx
31. c,b, ThuậtThuật toántoán MidpointBresenhamThuật toán Midpoint Nhận xét rằng: - Nếu F(M) < 0 M nằm phía trên của đoạn thẳng Vậy điểm cần vẽ tại bước thứ i+1 là 1 → yi+1 = yi - Ngược lại, chọn 2 → yi+1 = yi + 1 Vậy, nếu biết được dấu của pi ( là dấu của F(M) tại bước thứ i thì ta có thể xác định được điểm cần vẽ tại bước thứ i+1.
32. c,b, ThuậtThuật toántoán MidpointBresenhamThuật toán Midpoint Ta có: pi+1 – pi = 2Dy – 2 ( yi+1 – yi)Dx Như vậy: Nếu pi < 0 pi+1 = pi + 2Dy Nếu pi ≥ 0 pi+1 = pi + 2Dy - 2Dx Tính: p0= 2F(x0 + 1, y0+1/2) = 2(x0+1)Dy – 2( y0+1/2)Dx +2 c = 2(x0Dy - y0Dx + c) + 2Dy – Dx p0 = 2Dy – Dx Nhận xét: Thuật toán Midpoint cho kết quả tương tự thuật toán Bresenham.
33. II. C¸c tt vÏ ®êng th¼ng, ®êng trßn 2.1 Các đối tượng đồ họa cơ sở 2.2 Các thuật toán vẽ đường thẳng 2.3 Thuật toán Midpoint vẽ đường tròn 33
34. c,b, ThuậtThuật toántoánThuật MidpointBresenham toán Midpoint vẽ đường tròn d, Thuật toán vẽ đường tròn Midpoint Nhận xét: Do tính đối xứng của đường tròn nên ta chỉ cần khảo sát trên 1/8 đường tròn, sau đó lấy đối xứng. Giả sử P(x,y) là một điểm bất kỳ trên cung được khảo sát (cung tô màu xám). Các vị trí đối xứng với P qua các trục tọa độ và các đường phân giác là (±x, ±y) và (±y, ±x).
35. c,b, ThuậtThuật toántoán MidpointBresenham d,c,b, Thuật ThuậtThuật toán toántoánThuật vẽ MidpointBresenham đường toánThuật Midpoint tròn toán Midpoint Midpoint vẽ đường tròn d, Thuật toán vẽ đường tròn Midpoint Chọn điểm bắt đầu vẽ là điểm (0,R) Nếu (xi,yi) là điểm nguyên được vẽ ở bước thứ i Thì ở bước thứ (i+1) có thể chọn S(xi+1,yi) hoặc P(xi+1, yi – 1). Vậy: xi+1 = xi+1 yi+1 {yi-1, yi} Đặt F(x,y) = x2+ y2 – R2 , ta có :
36. c,b, ThuậtThuật toántoán MidpointBresenham d,c,b, Thuật ThuậtThuật toán toántoánThuật vẽ MidpointBresenham toánThuậtđường Midpoint toán tròn Midpoint Midpoint vẽ đường tròn d, Thuật toán vẽ đường tròn Midpoint Đặt F(x,y) = x2+ y2 – R2 , ta có : Xét pi= F(Midpoint) = F(xi + 1, yi - 1/2) . Ta có: - Nếu pi < 0, điểm Midpoint nằm trong đường tròn vậy điểm cần vẽ tại bước thứ i+1 là S → yi+1 = yi - Nếu pi ≥ 0, chọn P → yi+1 = yi -1
37. d,c,b,c,b, ThuậtThuật ThuậtThuật toántoán Thuật toántoán MidpointvẽBresenham MidpointBresenham toán Thuậtđường Midpoint toán tròn Midpoint Midpoint vẽ đường tròn Vì pi= F(xi +1, yi – 1/2) Ta có: pi+1 – pi = F(xi+1 +1, yi+1 – 1/2) – F(xi +1, yi – 1/2) 2 2 2 2 2 2 = [ ( xi+1+1) + (yi+1 – 1/2) - R ] –[(xi+1) + (yi-1/2) – R ] 2 2 = 2xi + 3 + (y i+1 – y i) –( yi+1 – yi) Nếu pi < 0 thì pi+1 = pi + 2xi + 3 Nếu pi ≥ 0 thì pi+1 = pi + 2xi – 2yi + 5 Tính p0 ứng với điểm ban đầu (0, R), ta có: p0= F(0 +1, R – 1/2) = 5/4 – R
38. Thuật toánThuật Midpoint toán Midpoint Begin vẽ đường tròn p = 5/4 - R X = 0; y = R; Putpixel(x, y, c); Giải thuật: Sai x ≤ y Đúng Sai p < 0 Đúng p = p+2(x-y)+5; y = y - 1; p = p + 2*x+3; x = x+1; Putpixel(x, y, c); End
39. II. C¸c tt vÏ ®êng th¼ng, ®êng trßn Bài tập: 1. Trình bày các thuật toán vẽ đường thẳng trong trường hợp m>1 2. Tìm các điểm phát sinh khi vẽ đường thẳng bằng thuật toán DDA trong trường hợp 0 1 3. Tìm các điểm phát sinh khi vẽ đường thẳng bằng thuật toán Bresenham và Midpoint trong trường hợp 0 1 4. Tìm các điểm phát sinh khi vẽ đường tròn bằng thuật toán Midpoint