›
›

Tài liệu Kỹ thuật đồ hoạ

pdf 199 trang vanle 2740
Download
Bạn đang xem 20 trang mẫu của tài liệu "Tài liệu Kỹ thuật đồ hoạ", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdftai_lieu_ky_thuat_do_hoa.pdf

Nội dung text: Tài liệu Kỹ thuật đồ hoạ

  1. LỜI NÓI ĐẦU Đồ hoạ máy tính (Computer Graphics) là một lĩnh vực lý thú và có nhiều ứng dụng trong thực tế, nó góp phần làm cho giao tiếp giữa con người và máy tính trở nên thân thiện hơn. Giao diện kiểu văn bản (text) đã được thay thế hoàn toàn bằng giao diện đồ hoạ. Tuy nhiên, việc dạy và học kỹ thuật đồ họa thì không đơn giản do chủ đề này có nhiều phức tạp. Kỹ thuật đồ họa liên quan đến tin học và toán học bởi vì hầu hết các giải thuật vẽ, tô cùng các phép biến hình đều được xây dựng dựa trên nền tảng của hình học không gian hai chiều và ba chiều. Hiện nay, Kỹ thuật đồ họa là một môn học được giảng dạy cho sinh viên chuyên ngành Công Nghệ Thông Tin. Trong cuốn giáo trình này, tôi muốn mang lại cho bạn đọc các cơ sở lý thuyết về đồ hoạ máy tính từ đơn giản nhất như các thuật toán vẽ đường thẳng, đường tròn, đa giác, ký tự Tiếp đến các kỹ thuật xén tỉa, các phép biến đổi đồ hoạ trong không gian 2D và 3D Chúng ta lần lượt làm quen với thế giới màu sắc thông qua các hệ màu: RGB, CMYK, HSV Phức tạp hơn nữa là các phép chiếu, các phương pháp xây dựng đường cong và mặt cong cho đối tượng. Cuối chúng ta tìm hiểu về ánh sáng và hình học fractal. Giáo trình gồm chín chương, trong đó chương một giúp bạn đọc có cái nhìn tổng quan về kỹ thuật đồ hoạ từ trước đến giờ cùng định hướng tương lai cho lĩnh vực này. Các chương tiếp theo, mỗi chương sẽ là một vấn đề từ đơn giản đến phức tạp về cơ sở nền tảng cho ngành kỹ thuật đồ hoạ. Cuối mỗi chương đều có phần bài tập để kiểm tra lại kiến thức vừa đọc được. Bài tập gồm hai dạng: dạng tính toán và dạng lập trình, đối với dạng lập trình bạn có thể viết bằng C/C++ hay BC thậm chí bằng VB đều được. Cuối cùng là phần phụ lục gồm các hướng dẫn làm bài tập lập trình, ngôn ngữ hay dùng ở đây là C/C++ hay BC. Bố cục rõ ràng, hình ảnh phong phú, đa dạng. Tôi hy vọng rằng giáo trình là một bộ tham khảo đầy đủ các thông tin hữu ích và có tính thực tiễn cao cho môn kỹ thuật đồ hoạ. Trong quá trình biên soạn mặc dù đã cố gắng hết sức nhưng vẫn không tránh khỏi những sai sót, rất mong nhậnPTIT được sự đóng góp chân thành từ quý bạn đọc. Xin chân thành cám ơn. Tác giả
  2. Mục lục MỤC LỤC LỜI NÓI ĐẦU 1 MỤC LỤC 2 CHƯƠNG 1: TỔNG QUAN VỀ KỸ THUẬT ĐỒ HOẠ 7 1.1. CÁC KHÁI NIỆM TỔNG QUAN CỦA KỸ THUẬT ĐỒ HOẠ MÁY TÍNH (COMPUTER GRAPHICS) 7 1.1.1. L ịch sử phát triển 7 1.1.2. Kỹ thuật đồ họa vi tính. 8 1.2. CÁC KỸ THUẬT ĐỒ HOẠ 8 1.2.1. Kỹ thuật đồ hoạ điểm (Sample based-Graphics) 8 1.2.2. Kỹ thuật đồ hoạ vector 9 1.2.3. Phân loại của đồ hoạ máy tính 10 1.2.4. Các ứng dụng tiêu biểu của kỹ thuật đồ họa 11 1.2.5. Các chuẩn giao diện của hệ đồ hoạ 13 1.3. PHẦN CỨNG ĐỒ HOẠ (GRAPHICS HARDWARE) 13 1.3.1. Các thành phần phần cứng của hệ đồ hoạ tương tác 13 1.3.2. Máy in 14 1.3.3. Màn hình CRT 14 1.3.4. Màn hình tinh thể lỏng (Liquid Crystal Display – LCD) 16 Tóm tắt chương: 17 Bài tập: 18 CHƯƠNG 2: CÁC GIẢI THUẬT SINH THỰC THỂ CƠ SỞ 19 2.1. CÁC HỆ THỐNG TOẠ ĐỘ TRONG ĐỒ HOẠ 19 2.1.1. Hệ toạ độ thực (WCS – World Coordinate System) 19 2.1.2. Hệ toạ độ thiết bị (DCS – Device Coordinate System) 19 2.1.3. toạ độ thiết bị PTITchuẩn (NDCS – Normalized Device Coordinate System) 20 2.2. ĐIỂM VÀ ĐOẠN THẲNG 20 2.2.1. Điểm 20 2.2.2. Đoạn thẳng 20 2.3. CÁC GIẢI THUẬT XÂY DỰNG THỰC THỂ CƠ SỞ 21 2.3.1. Giải thuật vẽ đoạn thẳng thông thường 21 2.3.2. Giải thuật Bresenham 22 2.3.3. Giải thuật trung điểm-Midpoint 23 2.3.3. Giải thuật sinh đường tròn (Scan Converting Circles)(Bresenham) 25 2.3.5. Giải thuật sinh đường tròn Midpoint 28 2.3.6. Giải thuật sinh đường ellipse 30 2.3.7. Giải thuật sinh ký tự 33 2.3.8. Giải thuật sinh đa giác (Polygon) 34 2
  3. Mục lục Tóm tắt chương: 39 Bài tập: 39 CHƯƠNG 3: CÁC PHÉP BIẾN ĐỔI ĐỒ HOẠ 41 3.1. CÁC PHÉP BIẾN ĐỔI HÌNH HỌC HAI CHIỀU 41 3.1.1. Phép biến đổi Affine (Affine Transformations) 41 3.1.2. Các phép biến đổi đối tượng 41 3.2. TỌA ĐỘ ĐỒNG NHẤT VÀ CÁC PHÉP BIẾN ĐỔI 45 3.2.1. Toạ độ đồng nhất 45 3.2.2. Phép biến đổi với toạ độ đồng nhất 46 3.2.3. Cài đặt c/c++ cho phép quay tam giác quanh 1 điểm (xq,yq): 47 3.3. CÁC PHÉP BIẾN ĐỔI HÌNH HỌC BA CHIỀU 48 3.3.1.Biểu diễn điểm trong không gian 3 chiều 48 3.3.2. Phép tịnh tiến 48 3.3.3. Phép tỉ lệ 48 3.3.4. Phép biến dạng 49 3.3.5. Phép lấy đối xứng 49 3.3.6. Phép quay 3 chiều 49 3.3.7. Cài đặt bằng c/c++ như sau: 53 Tóm tắt: 54 Bài tập: 54 CHƯƠNG 4: CÁC GIẢI THUẬT ĐỒ HOẠ CƠ SỞ 57 4.1. MÔ HÌNH CHUYỂN ĐỔI GIỮA BA HỆ THỐNG TOẠ ĐỘ 57 4.1.1. Mô hình chuyển đổi 57 4.1.2. Phép ánh xạ từ cửa sổ vào khung nhìn 57 4.2. CÁC GIẢI THUẬT XÉN TIẢ (CLIPPING) 59 4.2.1. Khái niệm 59 4.2.2. Clipping điểmPTIT 59 4.2.3. Xén tỉa đoạn thẳng 59 4.2.4. Giải thuật xén tỉa đa giác (Sutherland Hodgman) 66 Tóm tắt chương: 70 Bài tập: 70 CHƯƠNG 5: PHÉP CHIẾU –PROJECTION 71 5.1. KHÁI NIỆM CHUNG 71 5.1.1.Nguyên lý về 3D (three-Dimension) 71 5.1.2. Đặc điểm của kỹ thuật đồ hoạ 3D 71 5.1.3.Các phương pháp hiển thị 3D 71 5.2.PHÉP CHIẾU 72 5.3. PHÉP CHIẾU SONG SONG (Parallel Projections ) 74 3
  4. Mục lục 5.3.1.Phép chiếu trực giao (Orthographic projection) 74 5.3.2. Phép chiếu trục luợng (Axonometric) 75 5.3.3. Phép chiếu xiên - Oblique 78 5.4. PHÉP CHIẾU PHỐI CẢNH (Perspective Projection) 79 5.4.1. Phép chiếu phối cảnh một tâm chiếu 80 5.4.2. Phép chiếu phối cảnh hai tâm chiếu 81 5.4.3. Phép chiếu phối cảnh ba tâm chiếu 83 Tóm tắt chương: 83 Bài tập: 83 CHƯƠNG 6: MÀU SẮC TRONG ĐỒ HOẠ 85 6.1. ÁNH SÁNG VÀ MÀU SẮC (light and color) 85 6.1.1. Quan niệm về ánh sáng 85 6.1.2. Yếu tố vật lý 85 6.1.3. Cảm nhận màu sắc của con người (Physiology - Sinh lý - Human Vision) 87 6.1.4. Các đặc trưng cơ bản của ánh sáng 89 6.2. ÁNH SÁNG ĐƠN SẮC 89 6.2.1. Cường độ sáng và cách tính 90 6.2.2. Phép hiệu chỉnh gama 90 6.2.3. Xấp xỉ bán tông - halftone 91 6.2.4. Ma trận Dither và phép lấy xấp xỉ bán tông 93 6.3. CÁC HỆ MÀU TRONG MÀN HÌNH ĐỒ HỌA 93 6.3.1. Mô hình màu RGB (Red, Green, Blue - đỏ, lục, lam) 94 6.3.2. Mô hình màu CMY (Cyan, Magenta, Yellow - xanh tím, Đỏ tươi, vàng) 94 6.3.3. Mô hình màu YIQ 95 3.4. Mô hình màu HSV (Hue, Saturation,Value) - Mỹ thuật 96 6.3.5. Biểu đồ màu CIE (1931 – Commission Internationale de l’Eclairage) 97 6.4. CHUYỂN ĐỔI GIỮAPTIT CÁC HỆ MÀU 100 6.4.1. Chuyển đổi HSV - RGB 100 6.4.2. Chuyển đổi RGB sang XYZ 101 Tóm tắt: 102 Bài tập: 102 CHƯƠNG 7: ĐƯỜNG CONG VÀ MẶT CONG TRONG 3D 104 7.1. ĐƯỜNG CONG - CURVE 104 7.1.1. Điểm biểu diễn đường cong (curve represents points ) 104 7.1.2. Đường cong đa thức bậc ba tham biến 104 7.1.3. Đường cong Hermite 105 7.1.4. Đường cong Bezier 106 7.1.5. Đường cong B-spline 108 4
  5. Mục lục 7.2. MÔ HÌNH BỀ MẶT (Surface) VÀ CÁC PHƯƠNG PHÁP XÂY DỰNG 114 7.2.1. Các khái niệm cơ bản 114 7.2.2. Biểu diễn mảnh tứ giác 115 7.2.3. Mô hình hoá các mặt cong (Surface Patches) 117 7. 117 7.2.4. Mặt từ các đường cong 120 Tóm tắt: 125 Bài tập: 125 CHƯƠNG 8: ÁNH SÁNG 127 8.1. GIỚI THIỆU 127 8.1.1. Mục tiêu chính trong đồ họa máy tính 127 8.1.2. Các giải pháp trong đồ họa máy tính 127 8.2. CÁC KỸ THUẬT CHIẾU SÁNG TRONG ĐỒ HỌA MÁY TÍNH 129 8.2.1. Đánh giá về cường độ ánh sáng 129 8.2.2. Cường độ ánh sáng 130 8.2.3. Những thuộc tính bao quanh của vật chất 131 8.2.4. Thuộc tính khuếch tán của vật chất 132 8.2.5. Sự tương tác bề mặt/ánh sáng 133 8.2.6. Sự khúc xạ và sự truyền sáng 134 8.3. CÁC CÔNG NGHỆ 134 8.3.1. Raytracing 134 8.3.2. Radiosity 138 8.3.3. Photon Mapping 143 8.4. SỰ SO SÁNH GIỮA CÁC KỸ THUẬT (COMPARISON OF TECHNIQUES) 147 8.4.1. Raytracing 148 8.4.2. Radiosity 148 8.4.3. Photon mappingPTIT 148 Tóm tắt: 149 CHƯƠNG 9: HÌNH HỌC FRACTAL 150 9.1. SỰ RA ĐỜI VÀ CÁC ỨNG DỤNG CỦA HÌNH HỌC PHÂN HÌNH 150 9.1.1. Sự ra đời của lý thuyết hình học phân hình 150 9.1.2. Các ứng dụng tổng quát của hình học phân hình 151 9.2. MỘT SỐ KỸ THUẬT CÀI ĐẶT HÌNH HỌC PHÂN HÌNH 151 9.2.1 Họ đường VONKOCK 151 9.2.2. Đường SIERPINSKI 154 9.3. CÂY FRACTAL 155 9.3.1. CÁC CÂY THỰC TẾ: 155 9.3.2. BIỂN DIỄN TOÁN HỌC CỦA CÂY: 156 5
  6. Mục lục 9.4. TẬP MANDELBROT 159 9.4.1. Đặt vấn đề 159 9.4.2. CÔNG THỨC TOÁN HỌC 159 9.4.3. THUẬT TOÁN THỂ HIỆN TẬP MANDELBROT 160 9.5. TẬP JULIA 161 9.5.1. Đặt vấn đề: 161 9.5.2. Công thức toán học: 161 9.5.3. Thuật toán thể hiện tập Julia 161 9.6. HỌ CÁC ĐƯỜNG CONG PHOENIX 163 Bài tập 165 Chương 10: OpenGL 166 10.1. Giới thiệu về OpenGL 166 10.1.1. Khái niệm 166 10.1.2. Cài đặt OpenGL trong Visual C++ 166 10.2. Các thành phần cơ bản của OpenGL 166 10.2.1. Chương trình đầu tiên 166 10.2.2. Vẽ hình trong Window 167 10.2.3. Khung nhìn 168 10.3. Vẽ các đối tượng hình học cơ bản trong OpenGL 169 10.3.1. Vẽ điểm, đường và đa giác (point, line and polygon) 169 10.4. Phép biến đổi điểm nhìn và biến đổi mô hình (Viewing and Modeling transformations) 173 10.4.1. Phép biến đổi điểm nhìn 173 10.4.2. Phép biến đổi mô hình 173 10.4.3. kết hợp các phép biến đổi 174 10.5. Phép chiếu phối cảnh và phép chiếu trực giao (Perspective and Orthographic Projection) PTIT 174 10.5.1. Phép chiếu phối cảnh 174 10.5.2. Phép chiếu trực giao 175 PHỤ LỤC 177 1. Yêu cầu 177 2. Khởi tạo và đóng chế độ đồ hoạ 177 3. Các hàm cơ bản 178 3.1. Bảng màu của màn hình đồ hoạ. 178 3.2. Điểm 179 3.3. Đường 179 3.4. Hình chữ nhật 179 3.5. Hình tròn 179 3.6. Đa giác 180 6
  7. Mục lục 3.7. Văn bản 180 3.8. Cửa sổ (viewport) 181 3.9. Tạo hình ảnh chuyển động 181 Các code chương trình ví dụ cho bài tập lập trình 183 Bài 1: quay đối tượng 183 Bài 2: xén tỉa 190 Bài 3: Phép chiếu 191 TÀI LIỆU THAM KHẢO 185 PTIT 7
  8. Chương 1: Tổng quan về kỹ thuật đồ hoạ CHƯƠNG 1: TỔNG QUAN VỀ KỸ THUẬT ĐỒ HOẠ 1.1. CÁC KHÁI NIỆM TỔNG QUAN CỦA KỸ THUẬT ĐỒ HOẠ MÁY TÍNH (COMPUTER GRAPHICS) 1.1.1. L ịch sử phát triển Lịch sử của đồ họa máy tính là vào thập niên 1960 được đánh dấu bởi dự án SketchPad được phát triển tại Học viện Công nghệ Massachusetts (MIT) bởi Ivan Sutherland. Các thành tựu thu được đã được báo cáo tại hội nghị Fall Joint Computer và đây cũng chính là sự kiện lần đầu tiên người ta có thể tạo mới, hiển thị và thay đổi được dữ liệu hình ảnh trực tiếp trên màn hình máy tính trong thời gian thực. Hệ thống Sketchpad này được dùng để thiết kế hệ thống mạch điện và bao gồm những thành phần sau: . CRT màn hình . Bút sáng và một bàn phím bao gồm các phím chức năng . Máy tính chứa chương trình xử lý các thông tin Với hệ thống này, người sử dụng có thể vẽ trực tiếp các sơ đồ mạch điện lên màn hình thông qua bút sáng, chương trình sẽ phân tích và tính toán các thông số cần thiết của mạch điện do người dùng vẽ nên. Cũng trong năm 1960 này, William Fetter nhà khoa học người Mỹ. Ông đang nghiên cứu xây dựng mô hình buồng lái máy bay cho hãng Boeing của Mỹ. Ông dựa trên hình ảnh ba chiều của mô hình người phi công trong buồng lái của máy bay để xây dựng nên một mô hình tối ưu cho buồng lái máy bay. Phương pháp này cho phép các nhà thiết kế quan sát một cách trực quan vị trí của người lái trong khoang. Ông đặt tên cho phương pháp này là đồ hoạ máy tính (Computer Graphics) . Màn hình là thiết bị thông dụng nhất trong hệ đồ hoạ, các thao tác của hầu hết các màn hình đều dựa trên thiết kế ống tia âm cực CRT (Cathode ray tube). Kỹ thuật đồ họa được liên tục hoàn thiện vào thập niên 1970 với sự xuất hiện của các chuẩn đồ họa làm tăng cường khả năng giao tiếp và tái sử dụng của phần mềm cũng như các thư viện đồ họa. PTIT Sự phát triển vượt bậc của công nghệ vi điện tử và phần cứng máy tính vào thập niên 1980 làm xuất hiện hàng loạt các vỉ mạch hỗ trợ cho việc truy xuất đồ họa đi cùng với sự giảm giá đáng kể của máy tính cá nhân làm đồ họa ngày càng đi sâu vào cuộc sống thực tế. Những năm 1980 có raster graphics (đồ hoạ điểm). Bắt đầu chuẩn đồ hoạ ví dụ như: GKS(Graphics Kernel System): European effort (kết quả của châu âu), Becomes ISO 2D standard. Thập niên 90 phát triển đặc biệt về phần cứng, thiết bị hình học đồ hoạ Silicon. Xuất hiện các chuẩn công nghiệp: PHIGS (Programmers Hierarchical Interactive Graphics Standard) xác định các phương pháp chuẩn cho các mô hình thời gian thực và lập trình hướng đối tượng. Giao diện người máy Human-Computer Interface (HCI). 7
  9. Chương 1: Tổng quan về kỹ thuật đồ hoạ Ngày nay xuất hiện ảnh hiện thực, cạc đồ hoạ cho máy tính (Graphics cards for PCs), game boxes và game players. Công nghiệp phim ảnh nhờ vào đồ hoạ máy tính (Computer graphics becoming routine in movie industry), Maya (thế giới vật chất tri giác được) . 1.1.2. Kỹ thuật đồ họa vi tính. Đồ họa máy tính là một lĩnh vực của khoa học máy tính nghiên cứu về cơ sở toán học, các thuật toán cũng như các kỹ thuật để cho phép tạo, hiển thị và điều khiển hình ảnh trên màn hình máy tính. Đồ họa máy tính có liên quan ít nhiều đến một số lĩnh vực như đại số, hình học giải tích, hình học họa hình, quang học, và kỹ thuật máy tính, đặc biệt là chế tạo phần cứng (các loại màn hình, các thiết bị xuất, nhập, các vỉ mạch đồ họa ). Theo nghĩa rộng hơn, đồ họa máy tính là phương pháp và công nghệ dùng trong việc chuyển đổi qua lại giữa dữ liệu và hình ảnh trên màn hình bằng máy tính. Đồ họa máy tính hay kỹ thuật đồ họa máy tính còn được hiểu dưới dạng phương pháp và kỹ thuật tạo hình ảnh từ các mô hình toán học mô tả các đối tượng hay dữ liệu lấy được từ các đối tượng trong thực tế. 1.2. CÁC KỸ THUẬT ĐỒ HOẠ 1.2.1. Kỹ thuật đồ hoạ điểm (Sample based-Graphics) . Các mô hình, hình ảnh của các đối tượng được hiển thị thông qua từng pixel (từng mẫu rời rạc) . Đặc điểm:Có thể thay đổi thuộc tính của từng điểm ảnh rời rạc o Xoá đi từng pixel của mô hình và hình ảnh các đối tượng. o Các mô hình hình ảnh được hiển thị như một lưới điểm (grid) các pixel rời rạc, o Từng pixel đều có vị trí xác định, được hiển thị với một giá trị rời rạc (số nguyên) các thông số hiển thị (màu sắc hoặc độ sáng) . Tập hợp tất cả các pixel của grid cho chúng ta mô hình, hình ảnh đối tượng mà chúng ta muốn hiển thị.PTIT Hình 1.1 Ảnh đồ hoạ điểm Phương pháp để tạo ra các pixel . Phương pháp dùng phần mềm để vẽ trực tiếp từng pixel một. . Dựa trên các lý thuyết mô phỏng (lý thuyết Fractal, v.v) để xây dựng nên hình ảnh mô phỏng của sự vật. 8
  10. Chương 1: Tổng quan về kỹ thuật đồ hoạ . Phương pháp rời rạc hoá (số hoá) hình ảnh thực của đối tượng. . Có thể sửa đổi (image editing) hoặc xử lý (image processing) mảng các pixel thu được theo những phương pháp khác nhau để thu được hình ảnh đặc trưng của đối tượng. 1.2.2. Kỹ thuật đồ hoạ vector Mô hình Các tham đồ họa số tô trát Tô trát Thiết bị ra Hình 1.2 Mô hình đồ hoạ vector . Mô hình hình học (geometrical model) của đối tượng . Xác định các thuộc tính của mô hình hình học này, . Quá trình tô trát (rendering) để hiển thị từng điểm của mô hình, hình ảnh thực của đối tượng Ví dụ về hình ảnh đồ hoạ Vector Wireframe Model Skeletal Model Muscle Model PTIT Skin Model Hair Model Render and Touch up Hình 1.3 Ví dụ về đồ hoạ vector Có thể định nghĩa đồ hoạ vector: Đồ hoạ vector = geometrical model + rendering 9
  11. Chương 1: Tổng quan về kỹ thuật đồ hoạ So sánh giữa Raster và Vector Graphics Đồ hoạ điểm(Raster Graphics) Đồ hoạ vector(Vector Graphics) - Hình ảnh và mô hình của các vật thể được - Không thay đổi thuộc tính của từng điểm biểu diễn bởi tập hợp các điểm của lưới (grid) trực tiếp - Thay đổi thuộc tính của các pixel => thay - Xử lý với từng thành phần hình học cơ sở đổi từng phần và từng vùng của hình ảnh. của nó và thực hiện quá trình tô trát và hiển thị - Copy được các pixel từ một hình ảnh này lại. sang hình ảnh khác. - Quan sát hình ảnh và mô hình của hình ảnh và sự vật ở nhiều góc độ khác nhau bằng cách thay đổi điểm nhìn và góc nhìn. 1.2.3. Phân loại của đồ hoạ máy tính Phân loại theo các lĩnh vực của đồ hoạ máy tính CAD/CAM System Kiến tạo đồ đồ hoạ minh hoạ hoạ Đồ hoạ hoạt hình và nghệ thuật Kỹ thuật đồ hoạ Xử lý ảnh Xử lý đồ hoạ Kỹ thuật nhận dạng Kỹ thuật phân tích và tạo ảnh Phân loại theo hệ toạ độ Kỹ thuật đồ hoạ 2 chiều Kỹ thuật đồ hoạ PTITKỹ thuật đồ hoạ 3 chiều . Kỹ thuật đồ hoạ hai chiều: là kỹ thuật đồ hoạ máy tính sử dụng hệ toạ độ hai chiều (hệ toạ độ phẳng), sử dụng rất nhiều trong kỹ thuật xử lý bản đồ, đồ thị. . Kỹ thuật đồ hoạ ba chiều: là kỹ thuật đồ hoạ máy tính sử dụng hệ toạ độ ba chiều, đòi hỏi rất nhiều tính toán và phức tạp hơn nhiều so với kỹ thuật đồ hoạ hai chiều. Các lĩnh vực của đồ hoạ máy tính: Kỹ thuật xử lý ảnh (Computer Imaging): sau quá trình xử lý ảnh cho ta ảnh số của đối tượng. Trong quá trình xử lý ảnh sử dụng rất nhiều các kỹ thuật phức tạp: kỹ thuật khôi phục ảnh, kỹ thuật làm nổi ảnh, kỹ thuật xác định biên ảnh. Kỹ thuật nhận dạng (Pattern Recognition): từ những ảnh mẫu có sẵn ta phân loại theo cấu trúc, hoặc theo các tiêu trí được xác định từ trước và bằng các thuật toán chọn lọc để có thể phân tích hay tổng hợp ảnh đã cho thành một tập hợp các ảnh gốc, các ảnh gốc 10
  12. Chương 1: Tổng quan về kỹ thuật đồ hoạ này được lưu trong một thư viện và căn cứ vào thư viện này ta xây dựng được các thuật giải phân tích và tổ hợp ảnh. Kỹ thuật tổng hợp ảnh (Image Synthesis): là lĩnh vực xây dựng mô hình và hình ảnh của các vật thể dựa trên các đối tượng và mối quan hệ giữa chúng. Các hệ CAD/CAM (Computer Aided Design/Computer Aided Manufacture System): kỹ thuật đồ hoạ tập hợp các công cụ, các kỹ thuật trợ giúp cho thiết kế các chi tiết và các hệ thống khác nhau: hệ thống cơ, hệ thống điện, hệ thống điện tử . Đồ hoạ trình bày (Presentation Graphics): gồm các công cụ giúp hiển thị các số liệu thí nghiệm một cách trực quan, dựa trên các mẫu đồ thị hoặc các thuật toán có sẵn. Đồ hoạ hoạt hình và nghệ thuật: bao gồm các công cụ giúp cho các hoạ sĩ, các nhà thiết kế phim hoạt hình chuyên nghiệp làm các kỹ xảo hoạt hình, vẽ tranh Ví dụ: phần mềm 3D Studio, 3D Animation, 3D Studio Max. 1.2.4. Các ứng dụng tiêu biểu của kỹ thuật đồ họa Đồ hoạ máy tính là một trong những lĩnh vực lý thú nhất và phát triển nhanh nhất của tin học. Ngay từ khi xuất hiện nó đã có sức lôi cuốn mãnh liệt, cuốn hút rất nhiều người ở nhiều lĩnh vực khác nhau như khoa học, nghệ thuật, kinh doanh, quản lý Tính hấp dẫn của nó có thể được minh hoạ rất trực quan thông qua các ứng dụng của nó. . Xây dựng giao diện người dùng (User Interface) Giao diện đồ hoạ thực sự là cuộc cách mạng mang lại sự thuận tiện và thoải mái cho người dùng ứng dụng. Giao diện WYSIWYG và WIMP đang được đa số người dùng ưu thích nhờ tính thân thiện, dễ sử dụng của nó. . Tạo các biểu đồ trong thương mại, khoa học, kỹ thuật Các ứng dụng này thường được dùng để tóm lược các dữ liệu về tài chính, thống kê, kinh tế, khoa học, toán học giúp cho nghiên cứu, quản lý một cách có hiệu quả. . Tự động hoá văn phòng và chế bản điện tử . Thiết kế với sự trợ giúp của máy tính (CAD_CAM) . Lĩnh vực giải trí, nghệPTIT thuật và mô phỏng . Điều khiển các quá trình sản xuất (Process Control) . Lĩnh vực bản đồ (Cartography) . Giáo dục và đào tạo 11
  13. Chương 1: Tổng quan về kỹ thuật đồ hoạ Một số ví dụ của ứng dụng kỹ thuật đồ hoạ: Hình 1.4 Các ứng dụng của kỹ thuật đồ hoạ PTIT Hình 1.5 Hệ ứng dụng CAD - CAM 12
  14. Chương 1: Tổng quan về kỹ thuật đồ hoạ 1.2.5. Các chuẩn giao diện của hệ đồ hoạ Mục tiêu căn bản của các chuẩn cho phần mềm đồ hoạ là đảm bảo tính tương thích. Khi các công cụ được thiết kế với hàm đồ hoạ chuẩn, phần mềm có thể được di chuyển một cách dễ dàng từ hệ phần cứng này sang hệ phần cứng khác và được dùng trong nhiều cài đặt và ứng dụng khác nhau. GKS (Graphics Kernel System): chuẩn xác định các hàm đồ hoạ chuẩn, được thiết kế như một tập hợp các công cụ đồ hoạ hai chiều và ba chiều. GKS Functional Description, ANSI X3.124 - 1985.GKS - 3D Functional Description, ISO Doc #8805:1988. CGI (Computer Graphics Interface System): hệ chuẩn cho các phương pháp giao tiếp với các thiết bị ngoại vi. CGM (Computer Graphics Metafile): xác định các chuẩn cho việc lưu trữ và chuyển đổi hình ảnh. VRML (Virtual Reality Modeling Language): ngôn ngữ thực tại ảo, một hướng phát triển trong công nghệ hiển thị được đề xuất bởi hãng Silicon Graphics, sau đó đã được chuẩn hóa như một chuẩn công nghiệp. PHIGS (Programmers Hierarchical Interactive Graphics Standard): xác định các phương pháp chuẩn cho các mô hình thời gian thực và lập trình hướng đối tượng. PHIGS Functional Description, ANSI X3.144 - 1985.+ Functional Description, 1988, 1992. OPENGL thư viện đồ họa của hãng Silicon Graphics, được xây dựng theo đúng chuẩn của một hệ đồ họa năm 1993. DIRECTX thư viện đồ hoạ của hãng Microsoft, Direct X/Direct3D 1997 1.3. PHẦN CỨNG ĐỒ HOẠ (GRAPHICS HARDWARE) 1.3.1. Các thành phần phần cứng của hệ đồ hoạ tương tác CPU:thực hiện các chương trình ứng dụng. Bộ xử lý hiển thị (DisplayPTIT Processor): thực hiện công việc hiển thị dữ liệu đồ hoạ. Bộ nhớ hệ thống (System Memory): chứa các chương trình và dữ liệu đang thực hiện. Gói phần mềm đồ hoạ (Graphics Package): cung cấp các hàm đồ hoạ cho chương trình ứng dụng Phần mềm ứng dụng (Application Program): phần mềm đồ hoạ ứng dụng. Bộ đệm ( Frame buffer): có nhiệm vụ chứa các hình ảnh hiển thị. Bộ điều khiển màn hình (Video Controller): điều khiển màn hình, chuyển dữ liệu dạng số ở frame buffer thành các điểm sáng trên màn hình. 13
  15. Chương 1: Tổng quan về kỹ thuật đồ hoạ Hình 1.6 Các thành phần cứng của hệ đồ hoạ tương tác 1.3.2. Máy in Dot size: đường kính của một điểm in bé nhất mà máy in có thể in được Addressability: khả năng địa chỉ hoá các điểm in có thể có trên một đơn vị độ dài (dot per inch) Dot size Point per inch 8 - 20/ 100 inch 200, 600 5/1000 inch 1500 Máy vẽ 6,15/1000 inch 1000, 2000 1.3.3. Màn hình CRT Một chùm các tia điện tử (tia âm cực) phát ra từ một súng điện tử, vượt qua cuộn lái tia dẫn đến vị trí xác định trên màn hình được phủ một lớp phosphor. Tại mỗi vị trí tương tác với tia điện tử hạt phosphor sẽ phát lên một chấm sáng nhỏ. Nhưng chấm sáng sẽ mờ dần rất nhanh nên cần có cách nào nó duy trì ảnh trên màn hình. Một trong các cách là: lặp đi lặp lại nhiều lần việc vẽ lại ảnh thật nhanh bằng cách hướng cácPTIT tia điện tử trở lại ví trí cũ. Gọi là làm tươi (refresh CRT). Số lượng tối đa các điểm có thể hiển thị trên một CRT được gọi là độ phân giải (Resolution). Hay độ phân giải là số lượng các điểm có thể được vẽ theo chiều ngang và chiều dọc (được xem như tổng số điểm theo mỗi hướng) của màn hình. Kích thước vật lý của màn hình đồ hoạ được tính từ độ dài của đường chéo màn hình. Thường dao động từ 12-27 inch, hoặc lớn hơn. Thuộc tính khác của màn hình là tỷ số phương (aspect ratio). Nó là tỷ lệ của các điểm dọc và các điểm ngang cần để phát sinh các đoạn thẳng có độ dài đơn vị theo cả hai hướng trên màn hình. Màn hình có tỷ số phương khác một, thì hình vuông hiển thị trên đó thành hình chữ nhật còn hình tròn thành hình ellipse. 14
  16. Chương 1: Tổng quan về kỹ thuật đồ hoạ NEC Hybrid Hitachi EDP Standard Dot-trio SONY Trinitron Mask CRT Hình 1.7 Công nghệ màn hình CRT Màn hình dạng điểm (Raster Display): thường gặp nhất trong số các dạng màn hình sử dụng CRT trên công nghệ truyền hình. Mỗi điểm trên màn hình được gọi là pixel. Các thông tin về ảnh hiển thị trên màn hình được lưu trữ trong một vùng bộ nhớ gọi là vùng đệm làm tươi (Refresh buffer) hay là vùng đệm khung (Frame Buffer). Vùng lưu trữ tập các giá trị cường độ sáng củaPTIT toàn bộ các điểm trên màn hình và luôn tồn tại một cách song ánh giữa mỗi điểm trên màn hình và mỗi phần tử trong vùng này. Để tạo ra hình ảnh đen trắng, đơn giản chỉ cần lưu thông tin của mỗi Pixel là một bít (0,1) (xem hình 1.8). Trong trường hợp ảnh nhiều màu thì cần nhiều bít hơn, nếu thông tin mỗi pixel được lưu bằng b bít thì ta có thể có 2b giá trị màu phân biệt cho pixel đó. 15
  17. Chương 1: Tổng quan về kỹ thuật đồ hoạ Ví dụ mô hình đồ hoạ điểm ngôi nhà và ngôi sao. Interface to host computer (interaction data) (Display commands) Display Keyboard processo Data input 00000000000000 r 00000000000100 0000 CRT 00000000000000 00000000000100 Bitmap refresh buffer (the 1’s are0000 accentuated for contrast)00000000000000 00000000011111 0000 00000000011000Hình 1.8 Song ánh giữa vùng đệm khung và màn hình 00000111111111 Trong các màn hình màu, người ta định nghĩa tập các màu làm việc trong một bảng 1111 tra (LookUp Table00000000111100 - LUT). Mỗi phần tử của LUT được định nghĩa một bộ ba giá trị (RGB) mô tả một màu00000000011111 nào đó. Khi cần sử dụng một màu, ta chỉ cần chỉ định số thứ tự (index) tương ứng của0000 màu đó trong LUT, số phần tử trong bảng LUT chính là số màu có 00000011111111 thể được hiển thị cùng00000000000100 một lúc trên màn hình. 0000 X: 0 ¸ Xmax2 màu/ 1 bit 640 x 480 x 16 Video RAM = 2MB 00001111111111 Y: 0 ¸ Ymax16 màu/1100 4 bit0000000100 ;256 màu/ 8bit 1024 x 1024 x 24 Video RAM = 24MB 16 24 0000 2 màu/ 16 bit ; 2 màu/ 24 bit 00111111111111 Việc làm tươi11110000000000 trên màn hình dạng này được thực hiện ở tốc độ 60 - 80 khung/giây. 0000 Đôi khi tốc độ làm 00011111111111tươi còn được biểu diễn bằng đơn vị Hertz (Hz - số chu kỳ trên/giây), trong đó một chu 11100000000000 kỳ tương ứng với một khung (frame). Vậy tốc độ làm tươi 60 khung/giây đơn giản0000 là 60 Hz. Khi đạt đến cuối mỗi dòng quét, tia điện tử quay trở lại 00011111111111 bên trái của màn hình để bắt đầu dòng quét kế tiếp. Việc quay trở về bên trái màn hình sau 11100000000000 khi làm tươi mỗi dòng0000 quét được gọi là tia hồi ngang (Horizontal retrace). Và tới cuối mỗi 00011111111111PTIT frame, tia điện tử (tia hồi dọc - Vertical retrace) quay trở lại góc bên trái của màn hình để chuẩn bị bắt đầu frame11100000000000 kế tiếp. 0000 00000000000000 00000000000000 0000 Hình 1.9 Quét mành và quét dòng của màn hình CRT 1.3.4. Màn hình tinh thể lỏng (Liquid Crystal Display – LCD) Dựa vào công nghệ truyền ánh sáng qua điện cực mà đặt giữa là cuộn dây xoắn. Khi chưa có từ trường (chưa có dòng điện) ở cuộn dây thì ánh sáng truyền thẳng, khi có từ trường thì ánh sáng truyền đổi chiều. 16
  18. Chương 1: Tổng quan về kỹ thuật đồ hoạ Hình 1.10 Công nghệ truyền ánh sáng trong màn hình tinh thể lỏng CRT Displays (màn hình CRT) Advantages (ưu điểm) Disadvantages (nhược điểm) Đáp ứng nhanh (có độ phân giải cao) Lớn và nặng (typ. 70x70 cm, 15 kg) Màu sắc đa dạng (Có độ sâu và rộng) Tiêu tốn nguồn điện cao (typ. 140W) Màu sắc bão hoà và tự nhiên Có hại cho sức khoẻ vì trường điện từ và từ tính Công nghệ không quá đắt và hoàn thiện Màn hình nhấp nháy (at 50-80 Hz) Góc nhìn rộng, tương phản và độ sáng cao Hình hay bị méo tại 4 góc LCD Displays (màn hình tinh thể lỏng) Advantages (ưu điểm) Disadvantages (nhược điểm) Hình dáng nhỏ, trọng lượng nhẹ (approx 1/6 of Giá thành cao (presently 3x CRT) CRT, typ. 1/5 of CRT) PTIT Góc nhìn hẹp hơn (typ. +/- 50 degrees) Tiêu tốn nguồn thấp (typ. 1/4 of CRT) độ tương phản thấp (typ. 1:100) Màn hình phẳng tuyệt đối nên không méo tại độ chói (độ ngời) thấp hơn (typ. 200 cd/m2) các góc Màu sắc đều, ảnh sinh động Không bị hiệu ứng điện từ trường Có thể màn hình vừa lớn vừa rộng (>20 inch) Tóm tắt chương: Sự ra đời của đồ hoạ máy tính thực sự là cuộc cách mạng trong giao tiếp giữa người dùng và máy tính. Với lượng thông tin trực quan, đa dạng và phong phú được truyền tải qua hình ảnh. Các ứng dụng đồ hoạ máy tính đã lôi cuốn nhiều người nhờ tính thân thiện, dễ dùng, kích thích khả năng sáng tạo và tăng đáng kể hiệu suất làm việc. 17
  19. Chương 1: Tổng quan về kỹ thuật đồ hoạ Đồ hoạ máy tính ngày nay được được ứng dụng rất rộng rãi trong nhiều lĩnh vực khoa học, kỹ thuật, nghệ thuật, kinh doanh, quản lý Các ứng dụng đồ hoạ rất đa dạng, phong phú và phát triển liên tục không ngừng. Ngày nay, hầu như không có chương trình ứng dụng nào mà không sử dụng kỹ thuật đồ hoạ để làm tăng tính hấp dẫn cho mình. Một hệ thống đồ hoạ bao giờ cũng gồm hai phần chính đó là phần cứng và phần mềm. Phần cứng bao gồm các thiết bị hiển thị (thiết bị xuất) và các thiết bị nhập. Tiêu biểu nhất là màn hình, có hai loại màn hình thông dụng là CRT và LCD. Bài tập: 1. Cấu tạo và nguyên lý hoạt động của màn hình dạng điểm. Nêu các khái niệm vùng đệm khung, độ phân giải, tỷ số phương của màn hình loại này? 2. Ý nghĩa và hoạt động của bảng tra LUT? 3. Tính Video Ram của các màn hình lần lượt có độ phân giải là 640x480, 1024x768, 1280x1024 mà có mỗi pixel được mô tả lần lượt là 8bít, 12 bit, 24 bit. 4. Nếu chúng ta dùng các giá trị 12bit cho mỗi pixel trong một bảng tham chiếu lookup table, có bao nhiêu hạng mục mà lookup table có được? 5. Tại sao phải chuẩn hoá các phần mềm đồ hoạ? Liệt kê các chuẩn hóa đó. PTIT 18
  20. Chương 2: Các giải thuật sinh thực thể cơ sở CHƯƠNG 2: CÁC GIẢI THUẬT SINH THỰC THỂ CƠ SỞ 2.1. CÁC HỆ THỐNG TOẠ ĐỘ TRONG ĐỒ HOẠ Trong lĩnh vực kỹ thuật đồ họa, chúng ta phải hiểu được rằng thực chất của đồ họa là làm thế nào để có thể mô tả và biến đổi được các đối tượng trong thế giới thực trên máy tính. Bởi vì, các đối tượng trong thế giới thực được mô tả bằng tọa độ thực. Trong khi đó, hệ tọa độ thiết bị lại sử dụng hệ tọa độ nguyên để hiển thị các hình ảnh. Đây chính là vấn đề cơ bản cần giải quyết. Ngoài ra, còn có một khó khăn khác nữa là với các thiết bị khác nhau thì có các định nghĩa khác nhau. Do đó, cần có một phương pháp chuyển đổi tương ứng giữa các hệ tọa độ và đối tượng phải được định nghĩa bởi các thành phần đơn giản như thế nào để có thể mô tả gần đúng với hình ảnh thực bên ngoài. Hai mô hình cơ bản của ứng dụng đồ họa là dựa trên mẫu số hóa và dựa trên đặc trưng hình học. Trong ứng dụng đồ họa dựa trên mẫu số hóa thì các đối tượng đồ họa được tạo ra bởi lưới các pixel rời rạc. Các pixel này có thể đuợc tạo ra bằng các chương trình vẽ, máy quét, Các pixel này mô tả tọa độ xác định vị trí và giá trị mẫu. Thuận lợi của ứng dụng này là dể dàng thay đổi ảnh bằng cách thay đổi màu sắc hay vị trí của các pixel, hoặc di chuyển vùng ảnh từ nơi này sang nơi khác. Tuy nhiên, điều bất lợi là không thể xem xét đối tượng từ các góc nhìn khác nhau. Ứng dụng đồ họa dựa trên đặc trưng hình học bao gồm các đối tượng đồ họa cơ sở như đoạn thẳng, đa giác, Chúng được lưu trữ bằng các mô hình và các thuộc tính. Ví dụ : đoạn thẳng được mô hình bằng hai điểm đầu và cuối, có thuộc tính như màu sắc, độ dày. Người sử dụng không thao tác trực tiếp trên các pixel mà thao tác trên các thành phần hình học của đối tượng. 2.1.1. Hệ toạ độ thực (WCS – World Coordinate System) Một trong những hệ tọa độ thực thường được dùng để mô tả các đối tượng trong thế giới thực là hệ tọa độ Descartes. Với hệ tọa độ này, mỗi điểm P được biểu diễn bằng một cặp tọa độ P(xp,yp,zp) với xp, yp,zp R PTIT Hình 2.1 Hệ tọa độ thực. Ox,Oy, Oz là trục toạ độ xp ,yp,zp : toạ độ của P 2.1.2. Hệ toạ độ thiết bị (DCS – Device Coordinate System) Hệ tọa độ thiết bị (device coordinates) được dùng cho một thiết bị xuất cụ thể nào đó, ví dụ như máy in, màn hình, Trong hệ tọa độ thiết bị thì các điểm cũng được mô tả bởi cặp 19
  21. Chương 2: Các giải thuật sinh thực thể cơ sở tọa độ (x,y). Tuy nhiên, khác với hệ tọa độ thực là x, y N. Điều này có nghĩa là các điểm trong hệ tọa độ thực được định nghĩa liên tục, còn các điểm trong hệ tọa độ thiết bị là rời rạc. Ngoài ra, các tọa độ x, y của hệ tọa độ thiết bị chỉ biểu diễn được trong một giới hạn nào đó của N. Ví dụ : Độ phân giải của màn hình trong chế độ đồ họa là 640x480. Khi đó, x (0,639) và y (0,479) (xem hình 2.2). Hình 2.2 Hệ tọa độ trên màn hình 2.1.3. toạ độ thiết bị chuẩn (NDCS – Normalized Device Coordinate System) Do cách định nghĩa các hệ tọa độ thiết bị khác nhau nên một hình ảnh hiển thị được trên thiết bị này là chính xác thì chưa chắc hiển thị chính xác trên thiết bị khác. Người ta xây dựng một hệ tọa độ thiết bị chuẩn đại diện chung cho tất cả các thiết bị để có thể mô tả các hình ảnh mà không phụ thuộc vào bất kỳ thiết bị nào. Trong hệ tọa độ chuẩn, các tọa độ x, y sẽ được gán các giá trị trong đoạn từ [0,1]. Như vậy, vùng không gian của hệ tọa độ chuẩn chính là hình vuông đơn vị có góc trái dưới (0, 0) và góc phải trên là (1, 1). Quá trình mô tả các đối tượng thực như sau (xem hình 2.3): Hình 2.3 Hệ tọa độ trên màn hình. 2.2. ĐIỂM VÀ ĐOẠN THPTITẲNG 2.2.1. Điểm Trong hệ toạ độ hai chiều (mặt phẳng) thì điểm được biểu diễn P(x,y), ngoài ra nó còn có tính chất màu sắc. Ví dụ để vẽ một điểm ta có hàm putpixel(x,y,color). 2.2.2. Đoạn thẳng . Biểu diễn tường minh: y = f(x) Một đoạn thẳng được xác định nếu biết 2 điểm thuộc nó. Phương trình đoạn thẳng đi qua 2 điểm P (x1,y1) và Q(x2,y2) như sau: 20
  22. Chương 2: Các giải thuật sinh thực thể cơ sở (y-y1)/( x-x1) = ( y2-y1)/( x2-x1) Q(x2 , y2) (y-y1)(x2-x1)=(x-x1)(y2-y1) (x2-x1)y=(y2-y1)x + y1(x2-x1) - x1(y2-y1) y = ((y2-y1)/(x2-x1))x + y1 - ((y2-y1)/(x2-x1))x1 P(x , y ) y = kx + b 1 1 k = (y2-y1)/(x2-x1) Độ dốc hay hệ số góc của đường b = y1- kx1 Đoạn chắn trên trục y b y = k x (tức là khi x thay đổi thì y thay đổi theo) Hình 2.4 Vẽ đoạn thẳng PQ . Biểu diễn không tường minh: ax+by+c=0 Ta có : (y2-y1)x - (x2-x1)y + (x2-x1)y1 - (y2-y1)x1 = 0 (y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0 hay ax + by + c = 0 Trong đó a = (y2-y1), b = -(x2-x1 ) và c = x2y1 - x1y2 . Biểu diễn thông qua tham số: P(u) = P1 + u(P2 - P1) có u [0,1] x(u) = x1 + u( x2 - x1 ) y (u)= y1 + u( y2 - y1 ) 2.3. CÁC GIẢI THUẬT XÂY DỰNG THỰC THỂ CƠ SỞ 2.3.1. Giải thuật vẽ đoạn thẳng thông thường Nguyên lý chung: cho một thành phần toạ độ x hay y biến đổi theo từng đơn vị và tính độ nguyên còn lại sao cho gần với toạ độ thực nhất. y y Ta có y 2 1 x x y x x 1 1 2 1 PTIT Cho x thay đổi tìm y, trong bài này cho x1 thay đổi tiến tới x2 ta chọn đơn vị nhỏ nhất của màn hình x=1. Giải thuật thông thường: void dline(int x1,int y1, int x2,int y2, int color) { float y; int x; for (x=x1; x<=x2; x++) { y = y1 + (x-x1)*(y2-y1)/(x2-x1) ; putpixel(x, Round(y), color ); } } 21
  23. Chương 2: Các giải thuật sinh thực thể cơ sở 2.3.2. Giải thuật Bresenham 1960 Bresenham thuộc IBM tìm ra các điểm gần với đường thẳng dựa trên độ phân giải hữu hạn. Giải thuật này loại bỏ được các phép toán chia và phép toán làm tròn như ta đã thấy trong giải thuật trên. Xét đoạn thẳng với 0 yi+1 = yi - Ngược lại d1 > d2 => yi+1 = yi +1 Đặt D = d1 - d2= 2k(xi + 1) - 2yi + 2b - 1 Có k= y/ x và đặt Pi = xD = x (d1 - d2) Pi = x(2 y/ x(xi +1)- 2yi +2b-1) = 2 yxi +2 y -2 xyi + 2b x - x Ta tính bước tiếp: Pi+1 = 2 yxi+1 +2 y -2 xyi+1 + 2b x - x Pi+1 - Pi = -2 x(yi+1 -yi) + 2 y(xi+1 -xi) Có xi+1 =xi+1 nên: Pi+1 - Pi = - 2 x(yPTITi+1 -yi) + 2 y = 2 y - 2 x(yi+1 -yi) Nếu Pi 0 thì yi+1 = yi +1 Pi+1 = Pi + 2 y - 2 x Tính giá trị đầu: P1? P1 = x(d1 - d2) = x(2 y/ x(x1 +1)- 2y1 +2b-1) = 2 yx1 +2 y -2 xy1 + 2b x - x Có y1=kx1 + b = y/ x x1 +b P1 = 2 yx1 +2 y -2 x(( y/ x)x1 +b) + 2b x - x = 2 yx1 +2 y -2 yx1 - 2b x + 2b x - x P1 = 2 y - x 22
  24. Chương 2: Các giải thuật sinh thực thể cơ sở void Bre_line(int x1, int y1, int x2, int y2, int c){ B¾t ®Çu int x, y, dx, dy,p; y = y1; x = x1x=x1;y=y1; ; y = y1; dx = x2 - x1; dx = x2dx=x2 - x1; -x1; dy = y2 - y1; dy = y2 - y1; P = dx -dy=y2 2dy; -y1; p = 2*dy - dx; p=2dy-dx ; for (x=x1; x 0 else { Pp= = Pp+2dy - 2dy +- 2dx2dx p+=2*(dy-dx);//p=p+2dy-2dx x = x + 1 yes y++; } p=p+2dyP = P - 2dy y = y + 1 } } yes x 1 -1 =0) { if(p =0) { p+=2*dy-2*dx; p+=2*dy-2*dx; p+=2*dy+2*dx; p+=-2*dy-2*dx; y++; x++; y ; x ; } else } else } else } else p+=2*dy; p+=-2*dx; p+=2*dy; p+=-2*dx; 2.3.3. Giải thuật trung điểm-MidpointPTIT Jack Bresenham 1965/Pitteway 1967, áp dụng cho việc sinh các đường thẳng và đường tròn 1985. Xét trung điểm của đoạn AB (M) Nếu M ở trên đoạn thẳng AB thì chọn B còn M ở dưới đoạn thẳng AB chọn A Công thức đơn giản hơn, tạo được các điểm tương tự như với Bresenham d = f(xi + 1, yi + 1/2) là trung điểm của đoạn AB 23
  25. Chương 2: Các giải thuật sinh thực thể cơ sở d 0 A A B Hình 2.7 Mô tả giải thuật Midpoint So sánh hay kiểm tra M sẽ được thay bằng việc xét giá trị d. . d > 0 điểm B được chọn khi đó yi+1 = yi . d 0) thì M sẽ tăng theo x di+1=f(xi+2,yi+1/2) = a(xi+2) +b(yi +1/2) +c di+1 - di = a Hay di+1 = di + dy Tính d1 ? d1 = f(x1+1,yPTIT1+1/2) = a(x1+1) +b(y1 +1/2) +c = ax1 +by1 +c +a +1/2 b = f(x1,y1) +a +b/2 Có (x1,y1) là điểm bắt đầu, nằm trên đoạn thẳng nên f(x1,y1) = 0 Vậy d1 = a+ b/2 = dy - dx/2 24
  26. Chương 2: Các giải thuật sinh thực thể cơ sở /* Thuat toan Midpoint de ve B¾t ®Çu doan thang (0<k<1) */ void Mid_line(int x1, int y1, int x2, int y2, int c) x = x1 ; y = y1; { int x, y, dx, dy,d; dx = x2 - x1; y = y1; dy = y2 - y1; dx = x2 - x1; d = dy - dx/2; dy = y2 - y1; d= dy - dx/2; Putpixel (x ,y); for (x=x1; x<=x2; x++) { putpixel(x, y, c); No if (d <= 0) d <= 0 d = d + dy; d = d + dy - dx x = x + 1 else { yes y ++; d = d + dy y = y + 1 d = d + dy - dx; } } yes x < x2 } no KÕt thóc Hình 2.8 Sơ đồ khối giải thuật Midpiont cho đoạn thẳng 2.3.3. Giải thuật sinh đường tròn (Scan Converting Circles)(Bresenham) . Phương trình đường tròn đi qua tâm có toạ độ (xc,yc) là: 2 2 2 (x - xc) + (y - yc) = r Hình tròn là hình đối xứng tám cách PTIT Hình 2.9 Hình tròn đối xứng 8 phần Để đơn giản ta xét tâm trùng gốc 0 thì phương trình đơn giản : x2 + y2 = r2 Ta xét các điểm tạo ra từ góc phần tư thứ 2: từ 900 đến 450 , thực hiện theo hướng +x, -y 25
  27. Chương 2: Các giải thuật sinh thực thể cơ sở Hình 2.10 Mô tả giải thuật Bresenham Giả sử bắt đầu xi vậy xi+1 = xi +1 2 2 2 y = r - (xi +1) 2 2 2 2 2 d1 = yi - y = yi - r - (xi +1) 2 2 2 2 2 d2 = y - (yi - 1) = r - (xi +1) - (yi - 1) 2 2 2 2 pi = d1 - d2 = 2(xi +1 ) + yi + (yi - 1) -2r Xét: pi =0 (d1>=d2) chọn điểm nằm trong đường tròn yi+1 = yi +1 2 2 2 pi = 2(xi +1 ) + 2yi - 2yi 1 - 2r 2 2 2 pi+1 = 2(xi +2 ) + 2yi+1 - 2yi+1 + 1 - 2r 2 2 pi+1 = pi + 4xi +6 + 2yi+1 - 2yi - 2yi+1 + 2yi 2 2 pi+1 = pi + 4xi +6 + 2(yi+1 - yi )- 2(yi+1 - yi ) . Nếu pi =0 hay yi+1 = yi -1 pi+1 = pi + 4xi +6 - 4yi + 2 + 2 pi+1 = pi + 4(xi - yi ) + 10 . Tính P1 ? khi đó ứng với x1=0 và y1 =r 2 2 2 2 p1 = 2(x1 +1) + y1 + (y1 - 1) -2r = 2 + r2 + (r-1)2PTIT - 2r2= 3 - 2r Giải thuật là: 26
  28. Chương 2: Các giải thuật sinh thực thể cơ sở void Bre_circle(int xc, int yc, Bắt đầu int Radius, int color) { int x, y, p; X=0; y=r; x = 0; p=3-2r; y = Radius; p = 3 - 2 * Radius; Putpixel(x,y,c); while (x #include #define pc(xc,yc,x,y) { putpixel(xc + x, ycPTIT + y, color); putpixel(xc - x, yc - y, color); putpixel(xc -y, yc +x, color); putpixel(xc +y, yc -x, color); } void Bresenham_Circle(int xc, int yc, int Radius, int color){ int x, y, p; x = 0; y = Radius; p = 3 - 2 * Radius; pc(xc,yc, Radius,0); //ve 4 diem dac biet while (x < y){ if (d < 0) p += 4 * x + 6; else{ p += 4 * (x-y) + 10; 27
  29. Chương 2: Các giải thuật sinh thực thể cơ sở y ; } x++; pc(xc,yc, x,y); pc(xc,yc, y,x); } pc(xc,yc, y,y); // ve 4 diem phan giac x=y } void main(){ int gr_drive = DETECT, gr_mode; initgraph(&gr_drive, &gr_mode, ""); Bresenham_Circle(getmaxx() / 2, getmaxy() / 2, 150, 4); getch(); closegraph(); } 2.3.5. Giải thuật sinh đường tròn Midpoint Phương trình đường tròn không tường minh: f(x,y) = x2+y2-R2 =0 Hình 2.12 Mô tả giải thuật Midpoint Nếu f(x,y) = 0 thì nằm trên đường tròn f(x,y) > 0 thì nằm bên ngoài đường tròn f(x,y) = 0 chọn B thì điểm kế cận sẽ dịch chuyển theo x 1 đơn vị, theo y -1 đơn vị di+1 = f(xi +2, yi -3/2) 28
  30. Chương 2: Các giải thuật sinh thực thể cơ sở 2 2 2 = (xi +2) + (yi - 3/2) - r di+1 - di = 2xi - 2yi +5 di+1 = di + 2xi - 2yi +5 Tính d1? tại điểm (0, r) 2 2 2 d1 =f(1,r-1/2)= 1 + (r-1/2) - r d1 = 5/4 -r Thuật toán như sau: void Mid_circle(int xc, int yc, Bắt đầu int Radius, int color) { int x, y, d; X=0; y=r; d=1-r; x = 0; y = Radius; d = 1- Radius; while (x <= y){ Putpixel(x,y,c); putpixel(xc + x, yc + y, color); if (d< 0) d +=2 * x + 3; X++ else{ d<0 d += 2 * (x-y) + 5; y ; d=d+2x-2y+5 } d=d+2x+3; x++; } y } X<r End Hình 2.13 Sơ đồ khối giải thuậtPTIT Midpiont vẽ đường tròn void Midpoint_Circle(int xc, int yc, int Radius, int color){ int x, y, d; x = 0; y = Radius; d = 5 / 4 - Radius; while (x <= y) { putpixel(xc + x, yc + y, color); putpixel(xc - x, yc + y, color); putpixel(xc + x, yc - y, color); putpixel(xc - x, yc - y, color); putpixel(xc + y, yc + x, color); putpixel(xc - y, yc + x, color); putpixel(xc + y, yc - x, color); putpixel(xc - y, yc - x, color); if (d < 0) 29
  31. Chương 2: Các giải thuật sinh thực thể cơ sở d += 2 * x + 3; else { d += 2 * (x-y) + 5; y ; } x++; }} 2.3.6. Giải thuật sinh đường ellipse Tính đối xứng được thực hiện trên 4 cách F( x , y ) b2 x 2 a 2 y 2 a 2 b 2 0 A M tiep tuyen = -1 B gradient B C M i Hình 2.14 Mô tả giải thuật sinh đường ellipse Vector  với tiếp tuyến gradient =1 Ta có tiếp tuyến với cung tròn (độ dốc) = -1= dy/dx = - fx/fy Trong đó fx=2b2x đạo hàm riêng phần của f(x,y) với x Và fy=2a2y đạo hàm riêng phần của f(x,y) với y Giả sử ta chỉ xét trên góc phần tư thứ nhất: giả sử ta chia cung từ (0,b) đến (a,0) tại Q, có độ dốc -1 Trên phần 1: x thay đổi thì y thay đổi theo Trên phần 2: y thay đổi thì x thay đổi theo Xét trên phần 1: Bắt đầu từ (0,b), bước thứ i (xi,yi) chọn tiếp A(xi+1, yi) PTIT B(xi+1,yi-1) Tham số quyết định: 2 2 2 2 2 2 Pi = f(xi+1,yi-1/2) = b (xi+1) + a (yi-1/2) -a b 2 2 2 2 2 2 Pi+1 = f(xi+1+1,yi+1-1/2) = b (xi+1+1) + a (yi+1-1/2) -a b 2 2 2 2 2 2 Pi+1 - Pi = b ((xi+1+1) - (xi+1) )+ a ((yi+1-1/2) - (yi-1/2) ) 2 2 2 2 2 Pi+1 = Pi + 2b xi+1+ b + a ((yi+1-1/2) - (yi-1/2) ) . Nếu Pi <0 chọn A xi+1=xi+1 yi+1=yi 2 2 2 2 Pi+1 = Pi + 2b xi(xi+1) +b = Pi + 2b xi +3b 2 Hay Pi+1 = Pi + b (2xi +3) 30
  32. Chương 2: Các giải thuật sinh thực thể cơ sở . Nếu Pi >=0 chọn B xi+1=xi+1 yi+1=yi -1 2 2 2 2 2 Pi+1 = Pi + 2b xi(xi+1) +b + a ((yi-1 -1/2) - (yi-1/2) ) 2 2 2 = Pi + 2b xi +3b +a (-3yi +9/4 +yi -1/4) 2 2 2 = Pi + 2b xi +3b +a (-2yi +2) 2 2 Hay Pi+1 = Pi + b (2xi +3) + a (-2yi +2) . Tính P1? tại (0,b) 2 2 2 2 2 P1 = f(x1+1,y1-1/2) = b + a (b-1/2) -a b 2 2 2 P1 = b - a b +a /4 Xét trên phần 2: Ta lấy toạ dộ của Pixel sau cùng trong phần 1 của đường cong để tính giá trị ban đầu cho phần 2. Giả sử pixel (xk,yk) vừa chuyển quét cuối cùng của phần 1 nhập vào bước j cho phần 2 (xj,yj). Pixel kế tiếp có thể là: C(xj,yj-1) D(xj+1, yj-1) Tham số quyết định: 2 2 2 2 2 2 qj = f(xj+1/2,yj-1) = b (xj+1/2) + a (yj-1) -a b 2 2 2 2 2 2 qj+1 = f(xj+1+1/2,yj+1-1) = b (xj+1+1/2) + a (yj+1-1) -a b 2 2 2 2 2 2 qj+1 - qj = b ((xj+1+1/2) - (xj+1/2) )+ a ((yj+1-1) - (yj-1) ) 2 2 2 2 2 qj+1 = qj + b ((xj+1+1/2) - (xj+1/2) )+ a - 2a yj+1 . Nếu qj =0 chọn C yj+1=yj -1 xj+1= xj 2 2 qj+1 = qj + a - 2a (yj-1) 2 Hay qj+1 = qj + a (3 - 2yj ) . Tính q1? 2 2 2 2 2 2 q1 = f(xk+1/2,yk -1) = b (xk+1/2) + a (yk-1) -a b 31
  33. Chương 2: Các giải thuật sinh thực thể cơ sở Câu hỏi: lúc lấy đối xứng 4 cách để tìm 1 Ellipse hoàn chỉnh từ các toạ độ pixel được tạo ra với cung phần tư thứ 1. Có hiện tượng overstrike xảy ra hay không? Trả lời: hiện tượng overstrike xảy ra tại: (0,b); (0,-b); (a,0); (-a,0) Thuật toán #include #include #define ROUND(a) ((long)(a+0.5)) void plot(int xc, int yc, int x, int y, int color){ putpixel(xc+x, yc+y, color); putpixel(xc-x, yc+y, color); putpixel(xc+x, yc-y, color); putpixel(xc-x, yc-y, color); } void Mid_ellipse(int xc, int yc, int a, int b, int color){ long x, y, fx, fy, a2, b2, p; x = 0; y = b; a2 = a * a; //a2 b2 = b * b; // b2 fx = 0; fy = 2 * a2 * y; // 2a2y plot(xc, yc, x,y, color); p = ROUND(b2-(a2*b)+(0.25*a)); // p=b2 - a2b + a2/4 while (fx 0){ y ; fy -= 2*a2; // 2a2 if (p>=0) p+=a2*(3 - 2*y); //p =p + a2(3-2y) else{ x++; fx += 2*b2; // 2b2 p += b2*(2*x+2) + a2*(-2*y +3); //p=p + b2(2x +2) +a2(-2y +3) } plot(xc, yc, x, y, color); } } 32
  34. Chương 2: Các giải thuật sinh thực thể cơ sở void main(){ int gr_drive = DETECT, gr_mode; initgraph(&gr_drive, &gr_mode, ""); Mid_Ellipse(getmaxx() / 2, getmaxy() / 2, 150, 80, 4); getch(); closegraph(); } 2.3.7. Giải thuật sinh ký tự Trong màn hình text, truy xuất các ký tự trên màn hình được hỗ trợ bởi phần cứng. Các ký tự được lưu trữ trong bộ nhớ ROM, dưới dạng bitmap hay các ma trận ảnh. Phần cứng sẽ đưa ký tự lên màn hình tại ví trí xác định, tính toán cuốn trang và xuống dòng. Trong đồ hoạ: . Vector: định nghĩa các ký tự theo những đường cong mềm bao ngoài của chúng, tốn kém về mặt tính toán. Ưu nhược điểm: - phức tạp (tính toán phương trình) - lưu trữ gọn nhẹ - các phép biến đổi dựa vào công thức biến đổi Hình 2.15 Ký tự vector - Kích thước phụ thuộc vào môi trường (không có kích thước cố định) . Bitmap: định nghĩa mỗi ký tự với 1 font chữ cho trước là 1 ảnh bitmap hình chữ nhật nhỏ. - Đơn giản trong việc sinh ký tự (copypixel) - Lưu trữ lớn - Các phép biến đổi(I,B,U, scale) đòi hỏi lưu trữ thêm - Kích thước không đổi Hình 2.16 Ký tự bitmapPTIT . bitmap: sử dụng hàm copypixel (copy điểm ảnh) được lưu trữ trong bộ nhớ cố định - Fontcache, đưa vào bộ nhớ đệm hiển thị. Mỗi 1 ký tự như 1 ma trận 2 chiều của các điểm ảnh - mặt nạ. Hàm_sinh_ki_tu (mask) {xmax, ymax, xmin, ymin //các giới hạn của mặt nạ xo, yo //điểm gốc trên bộ đệm hiển thị for (i=ymin;i 0) copypixel ((mask(i,j), pixel(xo+j, yo+i)); } 33
  35. Chương 2: Các giải thuật sinh thực thể cơ sở Ký tự fontcache bitmap đơn giản của SRGP lưu trữ các ký tự theo chuỗi liên tiếp nhau trong bộ nhớ. Nhưng độ rộng các ký tự khác nhau, truy nhập các fontcache thông qua bản ghi về cấu trúc cho từng kí tự. Cấu trúc font chữ typedef struct { int leftx; int width; } Charlocation; //Vị trí của text struct { int CacheId; int Height; // Độ rộng chữ int CharSpace; // Khoảng cách giữa các ký tự Charlocation Table [128]; //bảng chữ cái } fontcache; . Ký tự vector Xây dựng theo phương pháp định nghĩa các ký tự bởi đường cong mềm bao ngoài của chúng dễ dàng thay đổi kích thước của kí tự cũng như nội suy ra các dạng của kí tự. Hoàn toàn độc lập với thiết bị. . Tối ưu nhất: lưu trữ font dưới dạng đường bao. Khi các chương trình ứng dụng sử dụng là bitmap tương ứng với chúng. 2.3.8. Giải thuật sinh đa giác (Polygon) a. Thuật giải vẽ đường bao đa giác Việc biểu diễn đa giác thông qua: . Tập các đoạn thẳng . Tập các điểm thuộc đa giác Các loại đa giác: PTIT Tam giác lồi lõm tự cắt miền Hình 2.17 Các loại đa giác Đa giác lồi: là đa giác có đường thẳng nối bất ký 2 điểm bên trong nào của đa giác đều nằm trọn trong đa giác. Đa giác không lồi là đa giác lõm. Các đường thẳng bao đa giác - cạnh của đa giác. Các điểm giao của cạnh - đỉnh của đa giác. Thông tin cần thiết để xác định đa giác: . Số cạnh . Toạ độ các đỉnh của đa giác Giải thuật: Polygon (arrayx, arrayy,n) 34
  36. Chương 2: Các giải thuật sinh thực thể cơ sở { if (n #include PTIT void FloodFill (int x, int y, int in_color, int new_color){ if (getpixel(x, y) == in_color){ putpixel(x, y, new_color); FloodFill(x-1, y, in_color, new_color); FloodFill(x+1, y, in_color, new_color); FloodFill(x, y-1, in_color, new_color); FloodFill(x, y+1, in_color, new_color); }} void main(){ int gr_drive = DETECT, gr_mode; initgraph(&gr_drive, &gr_mode, ""); circle(getmaxx() / 2, getmaxy() / 2, 15); FloodFill(getmaxx() / 2, getmaxy() / 2, 0, 4); getch(); closegraph();} 35
  37. Chương 2: Các giải thuật sinh thực thể cơ sở . Giải thuật dòng quét (scanline) cho việc tô màu vùng Giải thuật dựa trên ý tưởng sử dụng một đường quét trên trục y của màn hình đi từ ymax đến ymin của vùng cần được tô màu. Với mỗi giá trị y = yi đường thẳng quét cắt các đường biên của vùng cần tô tạo ra đoạn thẳng y = yi với x [xmin, xmax]. Trên đoạn thẳng đó chúng ta tô màu các điểm tương ứng đi từ xmin đến xmax có các điểm tô (xi, yi) y = yi. . Đơn giản nhất ví dụ tô màu hình chữ nhật: void scanline_rectg(x1,y1,x2,y2,c){ int i,j; for(i=y1; i>=y2; i ) for(j=x1; j<= x2;j++) putpixel(i,j,c); } . Phép tô màu 1 đa giác bất kỳ sẽ phức tập hơn rất nhiều so với hình chữ nhật Giả sử vùng tô được cho bởi 1 đa giác n đỉnh: pi (xi,yi), i=0,1, ,n-1. Đa giác này có thể là đa giác lồi, đa giác lõm hay đa giác tự cắt Các bước tóm tắt chính của thuật toán: . Tìm ytop, ybottom lần lượt là giá trị lớn nhất, nhỏ nhất của tập các tung độ của các đỉnh của đa giác đã cho. ytop = max{yi,(xi,yi) P}, ybottom = min{yi,(xi,yi) P}. . Ứng với mỗi dòng quét y=k, với k thay đổi từ ybottom đến ytop lặp: o Tìm tất cả các hoành độ giao điểm của dòng quét y=k với các cạnh của đa giác o Sắp xếp các hoành độ giao điểm theo thứ tự tăng dần: xo,x1, o Tô màu các đoạn thẳng trên đường thẳng y=k lần lượt được giới hạn bởi các cặp (xo,x1), (x2,x3), , (x2k,x2k+1). Chúng ta sẽ gặp 1 số vấn đề sau: . Ứng với mỗi dòngPTIT quét không phải lúc nào tất cả các cạnh của đa giác cũng tham gia cắt dòng quét. Do đó để cải thiện tốc độ cần phải có một cách nào đó để hạn chế được số cạnh cần tìm giao điểm ứng với mỗi dòng quét. y yqmax yq yq yqmin x Hình 2.19 Giải thuật scanline cho một đa giác bất kỳ 36
  38. Chương 2: Các giải thuật sinh thực thể cơ sở . Nếu số giao điểm tìm được giữa các cạnh đa giác và dòng quét là lẻ (điều này chỉ xảy ra khi dòng quét sẽ đi qua các đỉnh của đa giác) khi đó ta sẽ tính số điểm là 2 thì có thể tô không chính xác. Ngoài ra, việc tìm giao điểm của dòng quét với các cạnh nằm ngang là trường hợp đặt biệt Để giải quyết các vấn đề trên ta có các phương pháp sau: . Danh sách các cạnh kích hoạt (AET - Active Edge Table) Mỗi cạnh của đa giác được xây dựng từ 2 đỉnh kề nhau Pi(xi,yi) và Pi+1(xi+1,yi+1) gồm các thông tin sau: ymin: giá trị nhỏ nhất trong 2 đỉnh của cạnh xIntersect: hoành độ giao điểm của cạnh với dòng quét hiện đang xét 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 ymax Danh sách các cạnh kích hoạt AET: danh sách này dùng để lưu các tập cạnh của đa giác có thể cắt ứng với dòng quét hiện hành và tập các điểm giao tương ứng. Nó có một số đặc điểm: Các cạnh trong danh sách được sắp xếp theo thứ tự tăng dần của các hoành độ giao điểm để có thể tô màu các đoạn giao một cách dễ dàng. Thay đổi ứng với mỗi dòng quét đang xét, do đó danh sách này sẽ được cập nhật liên tục trong quá trình thực hiện thuật toán. Đầu tiên ta có danh dách chứa toàn bộ các cạnh của đa giác gọi là ET (Edge Table) được sắp xếp theo thứ tự tăng dần của ymin, rồi sau mỗi lần dòng quét thay đổi sẽ di chuyển các cạnh trong ET thoả điều kiện sang AET. Một dòng quét y=k chỉ cắt 1 cạnh của đa giác khi và chỉ khi k>=ymin và y>0. Chính vì vậy mà với các tổ chức của ET (sắp theo thứ tự tăng dần của ymin) điều kiện để chuyển các cạnh từ ET sang AET sẽ là k>=ymin; và điều kiện để loại một cạnh ra khỏi AET là y<=0 . Công thức tìm giao điểm nhanh Nếu gọi xk,xk+1 lần lượtPTIT là các hoành độ giao điểm của một cạnh nào đó với các dòng quét y=k và y=k+1 ta có: xk+1 - xk = 1/m ((k+1) - k) = 1/m hay xk+1 = xk + 1/m Như vậy nếu lưu hoành độ giao điểm ứng với dòng quét trước lại, cùng với hệ số góc của cạnh, ta xác định được hoành độ giao điểm ứng với dòng quét kế tiếp theo công thức trên. Nên thông tin của cạnh có 2 biến: DxPerScan , xIntersect. . Trường hợp dòng quét đi ngang qua một đỉnh: Tính 1 giao điểm nếu chiều của 2 cạnh kề của đỉnh đó có xu hướng tăng hay giảm Tính 2 giao điểm nếu chiều của 2 cạnh kề của đỉnh đó có xu hướng thay đổi, nghĩa là tăng-giảm hay giảm-tăng. 37
  39. Chương 2: Các giải thuật sinh thực thể cơ sở Pi-1 Pi+1 Pi+1 Pi-1 Pi Pi Pi Pi+1 Pi Pi-1 Pi+1 Pi-1 A B Hình 2.20 Qui tắc tính: một giao điểm (A) và hai giao điểm (B) PTIT Hình 2.21 lưu đồ thuật toán scan - line . Giải thuật tô vùng kín theo mẫu (Pattern filling)  object (ảnh mẫu) A[m,n] Vấn đề: xác định điểm ở mẫu và nhiều điểm tương ứng với chúng trên màn hình. Phương pháp 1: Tìm điểm neo ở đầu trái nhất hàng đầu tiên của đa giác. 38
  40. Chương 2: Các giải thuật sinh thực thể cơ sở Nhược điểm: không có điểm định vị trí phân biệt một cách rõ ràng cho mẫu tô trong một đa giác bất kỳ. Phương pháp 2: sử dụng cho SRGP Lấy điểm neo ở gốc toạ độ, giả sử ta coi cả màn hình được lát bởi màu tô các thực thể là các đường biên cho các vùng tô, vậy nếu ngoài các thực thể các màu tô không được phép thể hiện. y y neo neo x x Hình 2.22 Phương pháp lấy điểm neo Tóm tắt chương: Để có thể hiển thị các đối tượng đồ hoạ trên thiết bị hiển thị dạng điểm mà điển hình là màn hình, cần phải có một quá trình chuyển các mô tả hình học của các đối tượng này trong hệ toạ độ thế giới thực về dãy các pixel tương ứng gần với chúng nhất trên toạ độ thiết bị. Quá trình này còn được gọi là quá trình chuyển đổi bằng dòng quét. Yêu cầu quan trọng nhất đối với quá trình này ngoài việc phải cho kết quả xấp xỉ tốt nhất còn phải cho tốc độ tối ưu. Ba cách tiếp cận để vẽ đoạn thẳng gồm thuật toán DDA, thuật toán Bresenham, thuật toán Midpiont đều tập trung vào việc đưa ra cách chọn một trong hai điểm nguyên kế tiếp khi đã biết điểm nguyên ở bước trước. Thuật toán DDA đơn giản chỉ dùng thao tác làm tròn nên phải dùng các phép toán trên số thực, trong khi đó thuật toán Bresenham và Midpiont đưa ra cách chọn phức tạp hơn nhưng cho kết quả tốt hơn. Tương tự dùng hai giải thuật Bresenham và MidpiontPTIT để vẽ đường tròn và ellpise và một số đường cong khác. Các thuật toán tô màu vùng gồm thuật toán loang (đệ qui) hay thuật toán dòng quét. Có thể tô cùng một màu hay tô theo mẫu. Bài tập: 1. Chỉ định các vị trí mành nào sẽ được chọn bởi thuật toán Bresenham lúc chuyển quét một đường thẳng từ toạ độ pixel (1,1) sang toạ độ pixel (8,5). 2. Dùng giải thuật Bresenham viết hàm sinh đoạn thẳng (xét tất cả các trường hợp của hệ số góc). 3. Dùng giải thuật Midpiont viết hàm sinh đoạn thẳng (xét tất cả các trường hợp của hệ số góc). 39
  41. Chương 2: Các giải thuật sinh thực thể cơ sở 4. Dùng giải thuật Midpiont viết hàm sinh đường tròn (toạ độ tâm (xc,yc) và bán kính r). 5. Dùng giải thuật Midpiont viết hàm sinh đường ellipse (toạ độ tâm (xc,yc) và bán kính rx và ry ). 6. Từ hàm vẽ đường thẳng thiết kế và cài đặt hàm vẽ các hình sau: hình chữ nhật, đa giác, ngôi nhà 7. Viết giải thuật tìm giao điểm hai đoạn thẳng. 8. Viết chương trình tô màu Floodfill (sử dụng đệ qui với 4-connected). 9. Đưa ra lưu đồ thuật toán tô màu theo dòng quét.Viết thuật toán tô màu scan-line. PTIT 40
  42. Chương 3: Các phép biến đổi đồ hoạ CHƯƠNG 3: CÁC PHÉP BIẾN ĐỔI ĐỒ HOẠ 3.1. CÁC PHÉP BIẾN ĐỔI HÌNH HỌC HAI CHIỀU 3.1.1. Phép biến đổi Affine (Affine Transformations) Phép biến đổi Affine là phép biến đổi tuyến tính tọa độ điểm đặc trưng của đối tượng thành tập tương ứng các điểm mới để tạo ra các hiệu ứng cho toàn đối tượng. Ví dụ: phép biến đổi tọa độ với chỉ 2 điểm đầu cuối của đoạn thẳng tạo thành 2 điểm mới mà khi nối chúng với nhau tạo thành đoạn thẳng mới. Các điểm nằm trên đoạn thẳng sẽ có kết quả là điểm nằm trên đoạn thẳng mới với cùng phép biến đổi thông qua phép nội suy. 3.1.2. Các phép biến đổi đối tượng Các đối tượng phẳng trong đồ hoạ 2 chiều mô tả tập các điểm phẳng. Điểm trong đồ hoạ 2 chiều biểu diễn thông qua toạ độ, viết dưới dạng ma trận gọi là vectơ vị trí. Có 2 dạng biểu diễn: Một hàng và 2 cột: x y x Hai hàng và 1 cột: y Trong giáo trình chúng ta chọn biểu diễn điểm là ma trận hàng (một hàng và 2 cột). Tập các điểm được lưu trữ trong máy tính sẽ được viết dưới dạng ma trận vị trí của chúng. Chúng có thể là đường thẳng, đường cong, ảnh thật dễ dàng kiểm soát các đối tượng thông qua các phép biến đổi chúng, thực chất các phép biến đổi đồ hoạ này được mô tả dưới dạng các ma trận. 3.1.2.1. Phép biến đổi vị trí Giả sử ta có điểm P = [ x y ] trong mặt phẳng với [x y] là vectơ vị trí của P, kí hiệu là [P]. Gọi ma trận T là ma trận biến đổi sẽ có dạng: a b T PTIT c d y P’ P x Hình 3.1 Phép biến đổi vị trí Ta có điểm P sau phép biến đổi thành P’ có giá trị [x’ y’]. Thực thi phép biến đổi đúng trên 1 điểm ảnh sẽ đúng với toàn bộ đối tượng. 41
  43. Chương 3: Các phép biến đổi đồ hoạ a b ' ' X *T x y*  ax cy bx dy  x y  c d Hay ta có: x’ = ax + cy y’ = bx + dy Xét ma trận biến đổi T:  Phép bất biến: Khi đó: a = d =1 và b = c = 0 và ma trận cho phép bất biến là: 1 0 T 0 1 1 0 X *T x y* x y x' y' 0 1 Vậy x’=x và y = y’ hay là P’ = P chứng tỏ bất biến qua phép biến đổi.  Phép biến đổi tỷ lệ (scaling): . Nếu d=1 và b = c = 0 thì ma trận biến đổi là: a 0 T 0 1 x’ = ax y’ = y a 0 X *T x y*  ax y x' y' 0 1 P’ dịch chuyển theo trục x với tỷ lệ a xác định. . Nếu b = c =0 thì ma trận biến đổi là: a 0 T 0 d a 0 X *T x y*PTIT ax dy x' y' 0 d Hay tổng quát hơn gọi Sx, Sy lần lượt là tỷ lệ theo trục x và trục y, thì ma trận tỷ lệ sẽ là: Sx 0 T 0 Sy Khi Sx , Sy >1 gọi là phép phóng to Khi Sx, Sy <1 gọi là phép thu nhỏ . Các trường hợp đặc biệt: 42
  44. Chương 3: Các phép biến đổi đồ hoạ Sy= -1 Sx=Sy=-1 Sx=-1 P P P’ P P’ P’ Đối xứng qua y Đối xứng qua x Đối xứng qua gốc toạ độ Hình 3.2 Các phép đối xứng trên 2D  Phép biến dạng Khi a = d = 1 thì toạ độ của P’ phụ thuộc vào thay đổi của b và c . Xét c = 0 1 b X *T x y* x bx y x' y' 0 1 P’ y’=bx+y P bx Hình 3.3 Phép biến dạng theo trục oy Có P’ không thay đổi giá trị toạ độ x, còn y’ thay đổi phụ thuộc vào cả b và x . Xét b = 0 1 0 X*T x y* x cy y x' y' c 1 PTIT cy x’=x+cy P P’ Hình 3.4 Phép biến dạng theo trục ox Chú ý: điểm gốc toạ độ P[0 0] bất biến với mọi phép biến đổi  Phép quay Có >0 ngược chiều kim đồng hồ 43
  45. Chương 3: Các phép biến đổi đồ hoạ Hình 3.5 Phép quay trên 2D Ta có: P[x y]= [rcos rsin] P’[x’ y’] = [rcos( +) rsin( +)] P’[x’ y’] = [r(cos cos - sin sin)r(cos sin + sin cos)] = [(xcos - ysin )(xsin + ycos )] Vậy: x’ = xcos - ysin y’ = xsin + ycos Ta có: [X’]= [X]* [T] = [(xcos - ysin ) (xsin + ycos )] Vậy T tổng quát khi quay đối tượng quanh gốc toạ độ 1 góc bất kỳ là: cos sin T sin cos 3.1.2.2. Phép biến đổi tổng hợp Phương pháp biến đổi sử dụng phép nhân ma trận với toạ độ điểm thông qua các vectơ vị trí thật sự hiệu quả và đem lại công cụ mạnh về đồ hoạ cho người sử dụng. Nhưng thực tế các thao tác thường cần không chỉ một mà nhiều phép biến đổi khác nhau. Ta có phép hoán vị khi nhân ma trận là khôngPTIT thực hiện nhưng khả năng tổ hợp các phép nhân lại cho phép tạo ra một ma trận biến đổi duy nhất. Làm giảm bớt đáng kể khối lượng tính toán trong quá trình biến đổi, làm tăng tốc các chương trình ứng dụng và tạo điều kiện cho việc quản lý các biến đổi trong ứng dụng. Giả sử ta có P với [X] = [x y], có hai phép biến đổi [T1] quay quanh gốc toạ độ 900: 0 1 T1 1 0 Và [T2] lấy đối xứng P qua gốc toạ độ: 1 0 T 2 0 1 Ta có: 44
  46. Chương 3: Các phép biến đổi đồ hoạ 0 1 X ' X *T1 x y*  y x 1 0 1 0 X" X '*T 2  y x* y x 0 1 Giả sử [T3] là ma trận tổng hợp [T1] và [T2] 0 1 X * X *T3 x y* y x 1 0 Kết luận: biến đổi qua nhiều ma trận thành phần sẽ tương đương với phép biến đổi qua ma trận tổng hợp từ các phép biến đổi đó. 3.2. TỌA ĐỘ ĐỒNG NHẤT VÀ CÁC PHÉP BIẾN ĐỔI 3.2.1. Toạ độ đồng nhất Ta xét phép tịnh tiến: x’= x + dx y’ = y + dy Vậy P’ = P + [T] dx T  dy Vậy phép biến đổi tổng hợp: P’’=P’*[T’] + [T’’] = (P + [T]) [T’] + [T’’] Rõ ràng không thể biểu diễn thông qua ma trận tổng hợp 2 chiều 2x2 được. Phép tịnh tiến đưa ra ma trận biến đổi tổng hợp là không thể. Thế nào là phương pháp biểu diễn toạ độ đồng nhất ? là phương pháp biểu diễn mở rộng thông qua toạ độ đồng nhất của các vectơ vị trí không đồng nhất [x y] là ứng dụng của phép biến đổi hình học mà ở đó toạ độ điểm được mô tả dưới ma trận [x* y* h] với x=x*/h, y=y*/h có h là một sốPTIT thực tuỳ ý. Vậy một vectơ vị trí [xy] bất kỳ trên mặt phẳng xoy bằng tập vô số các điểm đồng nhất [hx hyh]. Ví dụ: [2 5] sẽ biểu diễn bằng [4102], [6153] đơn giản nhất là [251]. Vậy toạ độ đồng nhất của vectơ vị trí [X]= [ x y 1]. Khi đó ma trận biến đổi sẽ là 3x3: a b 0 T  c d 0 dx dy 1 a b 0 P' P.T  x y 1* c d 0 dx dy 1 x’=ax + cy +dx 45
  47. Chương 3: Các phép biến đổi đồ hoạ y’=bx + dy + dy [X’]= [x’ y’1] Trong đó dx, dy là khoảng tịnh tiến theo trục x và y. 3.2.2. Phép biến đổi với toạ độ đồng nhất a b 0 [T] c d 0 m n 1 Ma trận biến đổi đồng nhất  Phép tịnh tiến Có a=d=1 và b=c=0 1 0 0 T  0 1 0 m n 1 1 0 0 [x' y' 1] [x y 1] 0 1 0 [x m y n 1] m n 1 Chú ý: trong mặt phẳng toạ độ, mọi điểm kể cả gốc toạ độ đều có thể biến đổi. Phép biến đổi tổng hợp của hai phép tịnh tiến theo khoảng [m1 n1] và [m2n2] bằng phép biến đổi duy nhất một khoảng có giá trị bằng tổng của hai phép biến đổi [m1+m2n1+n2]. Thật vậy: 1 0 0 1 0 0 1 0 0 T1*T 2 0 1 0 * 0 1 0 0 1 0 m1 n1 1 m2 n2 1 m1 m2 n1 n2 1  Phép tỷ lệ PTIT Tương tự ma` trận tỷ lệ: Sx 0 0 Sx 0 0 Ts 0 Sy 0   [x' y' 1] [x y 1] 0 Sy 0 [x.Sx y.Sy 1] 0 0 1 0 0 1 Chú ý: Phép biến đổi tổng hợp của hai phép tỷ lệ Sx1, Sx2 và Sy1,Sy2 bằng phép biến đổi duy nhất có tỷ lệ là tích hai phép biến đổi trên Sx1*Sx2, Sy1*Sy2. Cài đặt c/c++ cho phép tỷ lệ đoạn thẳng toạ độ từ (x1,y1) đến (x2,y2): x11=int(x1*1.1); x22=int(x2*0.9); y11=int(y1*1.1); y22=int(y2*0.9);  Phép quay 46
  48. Chương 3: Các phép biến đổi đồ hoạ y ( x’, y’ )  ( x, y )    x Hình 3.6 Phép quay cos sin 0 [x' y' 1] [x y 1] sin cos 0 0 0 1 (xcos ysin ) (xsin ycos ) 1 Chú ý: Phép biến đổi tổng hợp của hai phép quay 1 và 2 là Cài đặt c/c++ cho phép quay tam giác quanh gốc toạ độ : void quay(int &x,int &y,float tamgiac(x1,y1,x2,y2,x3,y3,4); goc){ quay(x1,y1,goc); goc=goc*3.14/180; quay(x2,y2,goc); int t=x; quay(x3,y3,goc); x=x*cos(goc)-y*sin(goc); tamgiac(x1,y1,x2,y2,x3,y3,mau); y=t*sin(goc)+y*cos(goc); } 3.2.3. Cài đặt c/c++ cho phép quayPTIT tam giác quanh 1 điểm (xq,yq): #define RADS 0.017453293 void Quay(int x1,int y1, int x2, int y2, int x3, int y3,int xq, int yq,float goc ){ float x11,y11,x22,y22,x33,y33; float anpha = RADS *goc; x11=int(x1*cos(anpha)-y1*sin(anpha)+(1-cos(anpha))*xq + sin(anpha)*yq); y11=int(x1*sin(anpha)+y1*cos(anpha)-sin(anpha)*xq+(1 - cos(anpha))*yq); x22=int(x2*cos(anpha)-y2*sin(anpha)+(1-cos(anpha))*xq + sin(anpha)*yq); y22=int(x2*sin(anpha)+y2*cos(anpha)-sin(anpha)*xq+(1-cos(anpha))*yq); x33=int(x3*cos(anpha)-y3*sin(anpha)+(1-cos(anpha))*xq + sin(anpha)*yq); y33=int(x3*sin(anpha)+y3*cos(anpha)-sin(anpha)*xq+(1 - cos(anpha))*yq); tamgiac(x11,y11,x22,y22,x33,y33,12); } 47
  49. Chương 3: Các phép biến đổi đồ hoạ 3.3. CÁC PHÉP BIẾN ĐỔI HÌNH HỌC BA CHIỀU Các phép biến đổi chuyển vị - translation, tỉ lệ-scaling và quay-rotation sử dụng trong không gian 2D đều có thể mở rộng trong không gian 3D. 3.3.1.Biểu diễn điểm trong không gian 3 chiều [x* y* z* h] hay[x*/h y*/hz*/h 1] Viết gọn hơn:[x y z 1] Ma trận biến đổi tổng quát trong không gian 3D với tọa độ đồng nhất (4x4) a b c p a b c 0 d e f q d e f 0 [T] Hay T g i j r g i h 0 l m n s dx dy dz 1 3.3.2. Phép tịnh tiến Đây là phép biến đổi đơn giản nhất, mở rộng từ phép biến đổi trong không gian 2D ta có: 1 0 0 0 0 1 0 0 [ T(dx,dy,dz)] 0 0 1 0 dx dy dz 1 [X'] = [ X ] . [ T(dx,dy,dz) ] [ x' y' z' 1 ] = [ x y z 1 ].[ T(dx,dy,dz) ] = [ x+dx y+dy z+dz 1 ] Hình 3.7 Phép tình tiến trên 3D 3.3.3. Phép tỉ lệ Tương tự trong 2D ta có phép tỉPTIT lệ trong 3D là : Sx 0 0 0 0 Sy 0 0 Ts 0 0 Sz 0 0 0 0 1 Ta có Sx,Sy và Sz là các hệ số tỉ lệ trên các trục toạ độ [X’] = [X] . [T(Sx,Sy,Sz) ] Sx 0 0 0 0 Sy 0 0 [x ' y' z' 1] [x y z 1] 0 0 Sz 0 Hình 3.8 Phép tỷ lệ trên 3D 0 0 0 1 = [x.Sxy.Sy z.Sz 1] 48
  50. Chương 3: Các phép biến đổi đồ hoạ 3.3.4. Phép biến dạng . Ta có tất cả các phần tử nằm trên đường chéo chính bằng 1 . Các phần tử chiếu và tịnh tiến bằng 0 [X’] = [X] . [Tsh] 1 b c 0 d 1 f 0 [x' y' z' 1] [x y z 1] g i 1 0 0 0 0 1 [x yd gz bx y iz cx fy z 1] Hình 3.9 Các phép biến dạng trên 3D 3.3.5. Phép lấy đối xứng Đối xứng qua trục ox Đối xứng qua mặt xoy Đối xứng qua gốc O 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 Mox Mxoy Mo 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 3.3.6. Phép quay 3 chiều 3.3.6.1. Quay quanh các trụcPTIT toạ độ Đơn giản nhất là phép quay quanh các trục toạ độ ox,oy và oz với góc dương: Hình 3.10 Xác định góc quay dương trên 3 trục toạ độ Khi này phép quay lại đưa về phép quay không gian 2D quanh gốc toạ độ . Quay quanh trục oz: 49
  51. Chương 3: Các phép biến đổi đồ hoạ ' cos sin 0 0 x xcos ysin ' sin cos 0 0 y xsin ycos [Tz] ' 0 0 1 0 z z 0 0 0 1 Hình 3.11 Quay quanh trục oz . Quay quanh trục ox: ' x x 1 0 0 0 ' y ycos zsin 0 cos sin 0 ' [Tx] z ysin zcos 0 sin cos 0 0 0 0 1 Hình 3.12 quay quanh trục ox . Quay quanh trục oy: x' xcos zsin cos 0 sin 0 y ' y 0 1 0 0 ' [Ty] z xsin zcos sin 0 cos 0 PTIT 0 0 0 1 Hình 3.13 quay quanh trục oy Ghi chú: phép quay trong không gian 3D sử dụng phép nhân ma trận biến đổi không có khả năng hoán vị các ma trận. 3.3.6.2. Quay quanh một trục bất kỳ song song với các trục tọa độ . Đầu tiên chuyển dịch đối tượng cho đến khi toạ độ địa phương của đối tượng trùng với trục toạ độ mà trục địa phương song song. Quay đối tương xung quanh trục của nó (chính là trục toạ độ) . Đưa đối tượng về toạ độ trước khi dịch chuyển ta có ma trận tổng hợp là: [T //] = [Ttt-].[T ].[Ttt+] 50
  52. Chương 3: Các phép biến đổi đồ hoạ Ví dụ: quay đối tượng xung quanh một trục // với trục z với khoảng dịch chuyển là x,y và gốc quay là . Giải: T // z  Ttt .T .Ttt  1 0 0 0 cos sin 0 0 1 0 0 0 0 1 0 0 sin cos 0 0 0 1 0 0 . . 0 0 1 0 0 0 1 0 0 0 1 0 x y 0 1 0 0 0 1 x y 0 1 cos sin 0 0 1 0 0 0 sin cos 0 0 0 1 0 0 . 0 0 0 0 0 0 1 0 ( xcos ysin ) ( xsin ycos ) 0 1 x y 0 1 cos sin 0 0 sin cos 0 0 0 0 1 0 x(1 cos ) ysin y(1 cos ) xsin ) 0 1 3.3.6.3. Quay đối tương quanh một trục bất kỳ  Xét bài toán sau, hãy tìm ma trận biến đổi để đưa một trục bất kỳ có hướng: V=ax + by + cz về trùng với trục oz theo chiều dương. Ta thực hiện các bước như sau: . Quay V quanh trục y một góc (- ) sao cho nằm trên mặt phẳng (y, z) được V1 . Quay V1 quanh trục x một góc  sao cho PTITtrùng với trục z được V2 Hình 3.14 Quay đối tượng quanh một trục bất kỳ đi qua tâm 51
  53. Chương 3: Các phép biến đổi đồ hoạ Bước 1: y b V a x c V’ z a Hình 3.15 Quay V=ax+by+cz quanh trục oy Ta tính ? Chiếu V trên mặt phẳng (x,z) được V’. Ta có: a sin a 2 c2 c cos a 2 c2 c a cos 0 sin( ) 0 0 0 a 2 c2 a 2 c2 0 1 0 0 T 0 1 0 0  y  a c sin( ) 0 cos 0 0 0 a 2 c 2 a 2 c2 0 0 0 1 0 0 0 1 2 2 Vectơ: V1(0,b, a c y Bước 2: b V1 PTITV a  x c V a 2 z Hình 3.16 Quay vector V1 quanh trục ox b sin  a2 b2 c2 a2 c2 cos  a2 b2 c2 52
  54. Chương 3: Các phép biến đổi đồ hoạ 1 0 0 0 1 0 0 0 a 2 c2 b 0 0 0 cos  sin  0 a 2 b2 c 2 a 2 b2 c2 T  x 0 sin  cos  0 b a 2 c2 0 0 0 0 0 1 a 2 b2 c2 a 2 b2 c2 0 0 0 1 Vậy [Tv] = [T- y]. [Tx] Nếu đưa ngược lại ta được: 1 1 Tv  T y .Tx  T x .T y   Cho trục quay L (vectơ V = ax + by + cz) và một điểm P nằm trên trục L. Hãy tìm ma trận biến đổi quay đối tượng xung quanh trục L một góc . Giải: Ta thực hiện như sau: 1. Tịnh tiến P về gốc tọa độ. 2. Chuyển trục L về trùng với trục OZ 3. Quay đối tượng xung quanh trục OZ một góc . 4. Thực hiện ngược lại 2,1 Vậy: 1 T ,L  Ttt .Tv .T ,Z .Tv .Ttt  3.3.7. Cài đặt bằng c/c++ như sau: . Đổi 3D sang 2D #define RADS 0.017453293 struct point{ int x,y,z; } point Diem3d(int &x, int &y, int &z) { point p; p.x = int(getmaxx()/2+PTIT y - x*cos(RADS*45)); p.y = int(getmaxy()/2 - z + x*cos(RADS*45)); return p; } . Quay quanh các trục toạ độ point quay(int x,int y,int z,float goc,int truc){ point p; if (truc==1){ //Quay quanh OX p.y=y*cos(RADS*goc)-z*sin(RADS*goc); p.z=y*sin(RADS*goc)+z*cos(RADS*goc); p.x=x; } if (truc==2){ //Quay quanh OY p.x=x*cos(RADS*goc)+z*sin(RADS*goc); p.z=-x*sin(RADS*goc)+z*cos(RADS*goc); p.y=y; 53
  55. Chương 3: Các phép biến đổi đồ hoạ } if (truc==3){ p.x=x*cos(RADS*goc)-y*sin(RADS*goc); p.y=x*sin(RADS*goc)+y*cos(RADS*goc); p.z=z; } return p; } Tóm tắt: Các phép biến đổi hình học cho phép dễ dàng thao tác trên các đối tượng đã được tạo ra. Chúng làm thay đổi mô tả về toạ độ của các đối tượng, từ đó đối tượng sẽ được thay đổi về hướng, kích thước và hình dạng. Các phép biến đổi hình học cơ sở bao gồm tịnh tiến, quay và biến đổi tỷ lệ. Ngoài ra một số phép biến đổi khác cũng thường được áp dụng đó là phép đối xứng và biến dạng. Các phép biến đổi hình học 2D đều được biểu diễn dưới dạng ma trận đồng nhất 3x3 để tiện cho việc thực hiện các thao tác kết hợp giữa chúng. Trong hệ toạ độ đồng nhất, toạ độ của một điểm được mô tả bởi một vector dòng bao gồm ba giá trị, hai giá trị đầu tương ứng với toạ độ Descartes của điểm đó, và giá trị thứ ba là 1. Với cách biểu diễn này, ma trận của phép biến đổi có được từ sự kết hợp của các phép biến đổi cơ sở sẽ bằng tích của các ma trận của các phép biến đổi thành phần. Phép biến đổi hình học 3D là sự mở rộng của phép biến đổi 2D. Tương tự nó cũng có các phép: tịnh tiến, tỷ lệ, biến dạng và quay. Phức tạp nhất là phép quay, nên chúng ta khảo sát lần lượt từ đơn giản đến phức tạp: quay đối tượng quanh các trục toạ độ, quanh 1 trục song song với trục toạ độ, quanh 1 trục bất kỳ Do khảo sát các phép biến đổi affine với biểu diễn dạng ma trận đồng nhất (4x4 với 3D) nên công việc khá đơn giản và nhất quán. Lưu ý phép tịnh tiến và quay có chung thuộc tính là: sau khi biến đổi hình dạng và kích thước của đối tượng không thay đổi mà chúng chỉ bị thay đổi vị trí và định hướng trong không gian. PTIT Bài tập: 1. a. Hãy tìm ma trận biểu thị phép quay một đối tượng một góc 600 quanh gốc toạ độ. b. Tìm toạ độ mới của P(-3,3) sau khi thực hiện phép quay trên? 2. a. Hãy viết dạng tổng quát của ma trận điều chỉnh tỷ lệ tương ứng với một điểm cố định Q(a,b)? b. Phóng lớn tứ giác có các đỉnh A(0,0), B(1,3), C(4,2) và D(3,1) lên hai lần kích thước ban đầu của nó trong khi vẫn giữ điểm D(3,1)? 3. 54
  56. Chương 3: Các phép biến đổi đồ hoạ a. Mô tả phép biến đổi nhằm quay 1 đối tượng một góc xung quanh một tâm cố định Q(a,b)? b. Thực hiện phép quay tam giác ABC có A(0,0), B(1,1) và C(4,2) một góc 450 xung quanh điểm (-1, -1)? 4. Cho ABC có các toạ độ đỉnh là A(2,2), B(3,1) và C(4,3). Xác định ma trận biến đổi affine biến đổi tam giác này thành A’B’C’ biết ảnh A’(4,3), B’(4,5) và C’(7,3). 5. a. hãy tìm một ma trận dành cho phép phản chiếu đối xứng gương xung quanh một đường thẳng G với độ dốc m và tung độ gốc (0,g)? y P’ G g P 0 x b. Tạo phản xạ đối xứng gương đa giác mà đỉnh của nó: A(-1,0), B(0,-2), C(1,0) và D(0,2) xung quanh đường G trong các trường hợp sau: i. x=2 ii. y=3 iii. y=2x+3 6. Cho hình chóp ABCD có các toạ độ A(0,0,0), B(1,0,0), C(0,1,0) và D(0,0,1). Quay hình chóp quanh đường L (v=x+y+z) đi qua điểm C một góc 450. Tìm toạ độ hình chóp mới. 7. a. Hãy tìm phép biến đổi dành cho phép đối xứng gương tương ứng với một mặt phẳng đã choPTIT (có vector pháp tuyến M, trên đó có một điểm P). y Q Q’ M x z b. Áp dụng tìm ma trận cho phép đối xứng gương với mặt phẳng đi qua gốc toạ độ và vector pháp tuyến có hướng M=x+y+z. 8. Viết chương trình với đối tượng (đường thẳng, tam giác, tứ giác ) trong mặt phẳng 2D a. Dịch chuyển (dùng các phím dịch chuyển) 55
  57. Chương 3: Các phép biến đổi đồ hoạ b. Phóng lớn, thu nhỏ (dùng phím dịch chuyển hay gõ vào từ bàn phím) c. Quay với góc quay được gõ vào từ bàn phím (góc gõ vào được tính bằng độ) 9. Viết chương trình với đối tượng (hình kim cương, hình lập phương ) trong 3D a. Dịch chuyển b. Phóng lớn, thu nhỏ c. Quay một góc PTIT 56
  58. Chương 4: Các giải thuật đồ hoạ cơ sở CHƯƠNG 4: CÁC GIẢI THUẬT ĐỒ HOẠ CƠ SỞ 4.1. MÔ HÌNH CHUYỂN ĐỔI GIỮA BA HỆ THỐNG TOẠ ĐỘ 4.1.1. Mô hình chuyển đổi Hệ tọa độ Descartes là dễ thích ứng cho các chương trình ứng dụng để miêu tả các hình ảnh (picture) trên hệ tọa độ thế giới thực (World Coordinate System). Các hình ảnh được định nghĩa trên hệ tọa độ thế giới thực này sau đó được hệ đồ họa vẽ lên các hệ tọa độ thiết bị (Device Coordinate). Điển hình, một vùng đồ họa cho phép người sử dụng xác định vùng nào của hình ảnh sẽ được hiển thị và bạn muốn đặt nó ở nơi nào trên hệ tọa độ thiết bị. Một vùng đơn lẻ hoặc vài vùng của hình ảnh có thể được chọn. Những vùng này có thể được đặt ở những vị trí tách biệt, hoặc một vùng có thể được chèn vào một vùng lớn hơn. Quá trình biến đổi này liên quan đến những thao tác như tịnh tiến, biến đổi tỷ lệ vùng được chọn và xóa bỏ những phần bên ngoài vùng được chọn. Hình 4.1 WCS Hình 4.2 NDCS Normalized Hình 4.3 DCS World Coordinate System Device Coordinate System Device Coordinate System . Qui trình để chuyển đổi các đối tượng trong WCS sang NDCS được gọi là phép ánh xạ cửa sổ sang khung nhìn hay phép biến đổi chuẩn hoá (Window to Viewport mapping or Normalization Transformation) . Qui trình có thể áp các toạ độ thiết bị hiển thị chuẩn hoá sang các thiết bị rời rạc được gọi là phép biến đổi trạm làm việc (Workstation Transformation) 4.1.2. Phép ánh xạ từ cửa sổ vàoPTIT khung nhìn Hình 4.4 Đối tượng trong cửa sổ Hình 4.5 Đối tượng tại khung nhìn . Một cửa sổ (window) được chỉ định bởi bốn toạ độ thực (WCS): Xwmin, Xwmax, Ywmin, Ywmax 57
  59. Chương 4: Các giải thuật đồ hoạ cơ sở . Một khung nhìn (viewport) được mô tả bởi bốn toạ độ thiết bị chuẩn hoá (NDCS): Xvmin, Xvmax, Yvmin, Yvmax Mục đích của phép ánh xạ này là chuyển đổi các toạ độ thực (Xw,Yw) của một điểm tuỳ ý sang thiết bị chuẩn hoá tương ứng (Xv,Yv). Để giữ lại khoảng cách của điểm trong khung nhìn bằng với khoảng cách của điểm trong cửa sổ, với yêu cầu: xv xv max xw xwmin xv max xv min xwmax xwmin yv yv max yw ywmin yv max yv min ywmax ywmin Ta có: (xv max xv min ) xv (xw xwmin ) xv max (xwmax xwmin ) (yvmax yvmin ) yv (yw ywmin ) yvmax (ywmax ywmin ) Ta có tám giá trị ở trên để xác định cửa sổ và khung nhìn đều là hằng số. Vậy chúng ta hoàn toàn tính được (Xv,Yv) từ (Xw, Yw) qua phép biến đổi: [XvYv1] = [XwYw 1]. [T] [T] = [Ttt-]. [Ts] . [Ttt] . Ma trận tịnh tiến theo window: 1 0 0 T 0 1 0  tt  xw yw 1 . Ma trận chuyển đổi tỷ lệ window vào viewport là: x x v max v min 0 0 x x wmax wminPTIT yv max yv min T s  0 0 ywmax ywmin 0 0 1 . Ma trận tịnh tiến theo toạ độ viewport: 1 0 0 T 0 1 0  tt  xv yv 1 Vậy ma trận biến đổi từ cửa sổ vào khung nhìn: 58
  60. Chương 4: Các giải thuật đồ hoạ cơ sở xv max xv min 0 0 x x wmax wmin y y T 0 v max v min 0   ywmax ywmin x x y y v max v min v max v min xv min xwmin . yv min ywmin . 1 xwmax xwmin ywmax ywmin 4.2. CÁC GIẢI THUẬT XÉN TIẢ (CLIPPING) 4.2.1. Khái niệm Xén tỉa là tiến trình xác định các điểm của một đối tượng nằm trong hay ngoài cửa sổ hiển thị. Nằm trong được hiển thị, nằm ngoài loại bỏ. Việc loại từng điểm ảnh của đối tượng thường chậm nhất là khi đối tượng mà phần lớn nằm ngoài cửa sổ hiển thị. 4.2.2. Clipping điểm Giả sử (x,y) là toạ độ của một điểm, vậy điểm đó được hiển thị khi thoả mãn: Xmin xmaxy1,y2 > ymax x1,x2 < xminy1,y2 < ymin . Xén tỉa: đoạn thẳng cần xén tỉa Việc cài đặt giải thuật chia làm hai bước: Bước 1 : Gán mã vùng 4-bit cho mỗi điểm cuối của đoạn thẳng 59
  61. Chương 4: Các giải thuật đồ hoạ cơ sở Hình 4.6 Mặt phẳng mã trong các trường hợp clipping đoạn thẳng Mã vùng được xác định theo 9 vùng của mặt phẳng mà các điểm cuối nằm vào đó. Một bít được cài đặt true (1) hoặc false (0). Bít 1: điểm cuối ở bên trên cửa sổ = sign(y-ymax) Bít 2: điểm cuối ở bên dưới cửa sổ = sign(ymin-y) Bít 3: điểm cuối ở bên phải cửa sổ = sign(x-xmax) Bít 4: điểm cuối ở bên trái cửa sổ = sign(xmin-x) Qui ước sign(a) = 1 nếu a dương = 0 nếu a âm Bước 2 :Quá trình kiểm tra vị trí của đoạn thẳng so với cửa sổ. Tất cả điểm đầu và điểm cuối của đoạn thẳng đã có mã. Giải thuật như sau : Bước 1 :Nếu mã của P1 hoặc P2 đều = 0000 thì toàn bộ đoạn thẳng thuộc phần hiển thị. If (P1.Mã OR P2.Mã == 0000) then“ cả đoạn thẳng thuộc cửa sổ hiển thị” Bước 2 : Nếu mã của P1 và P2 có cùng một vị trí mà ở đó P1 và P2 => cùng phía If (P1.Mã AND P2.Mã != 0000) then “ 2 điểm nằm về 1 phía của cửa sổ” Bước 3: Xét giao điểm: D(1010) B(1000) y max A(0001)PTIT ymin C(0100) xmin xmax Hình 4.7 Mô tả thuật toán Cohen Sutherland outcode Tìm giao điểm của đường thẳng với cửa sổ, chính xác hơn là với phần mở rộng của đường biên. Chú ý: các đường biên mà điểm cuối được chọn sẽ “đẩy ngang qua” nhằm thay đổi mã “1” thành “0” Nếu: Bít 1 là 1: cắt y=ymax Bít 2 là 1: cắt y= ymin 60
  62. Chương 4: Các giải thuật đồ hoạ cơ sở Bít 3 là 1: cắt x=xmax Bít 4 là 1: cắt x=xmin Nhìn trên hình ta có: gọi điểm cuối của đoạn (x1,y1) Nếu C được chọn thì đường y=ymin chọn để tính phần cắt nhau (bít 2 = 1) Nếu D được chọn thì y=ymax hoặc x=xmax (bít 1 và bít 3 =1) Toạ độ cắt: xi xmin / xmax x xmin yi y1 m(xi x1 ) x xmax Hoặc: xi x1 (yi y1 )/ m y ymin yi ymin / ymax y ymax Có m là độ dốc của đoạn thẳng m=(y2-y1)/(x2-x1) Bây giờ thay điểm cuối (x1,y1) với điểm cắt (xi,yi) Ví dụ: Cho cửa sổ cắt tỉa hình chữ nhật có góc trái dưới L(-3,1), góc phải trên R(2,6) Hãy tìm mã vùng dành cho các điểm cuối của các đoạn AB có A(-2,3), B(1,2) ; CD có C(-4,7), D(-2,10) ; IK có I(-4,2), K(-1,7) Tìm hạng mục cắt tỉa của chúng Giải: . Mã vùng Bít 1 = sign(y-ymax) = sign(y-6) Bít 2 = sign(ymin-y) = sign(1-y) Bít 3 = sign(x-xmax) = sign(x-2) Bít 4 = sign(xmin-x)= sign(-3-x) Qui ước sign(a) = 1 nếu a dương = 0 nếu a âm Vậy: PTIT A(-2,3) có (0000) B(1,2) có (0000) C(-4,7)có (1001) D(-2,10) có (1000) I(-4,2) có (0001) K(-1,7) có (1000) . Hạng mục cắt tỉa AB có mã vùng đều là (0000) nên nó nằm hoàn toàn trong CD có (1001) and (1000) = (1000) (!= (0000)) nên hoàn toàn nằm ngoài IK có (0001) or (1000) =(1001) và (0001) and (1000) =(0000) nên phải xén tỉa. Xét I(0001) dựa trên đường biên xmin =-3 xc xmin yc y1 m(xc x1 ) xmin = -3 61
  63. Chương 4: Các giải thuật đồ hoạ cơ sở m=(y2-y1)/x2-x1)= (7-2)/ (-1-(-4)) = 5/3 yc=2 + 5/3 (-3-(-4)) = 11/3 Thay I bởi I1 (-3,11/3) (có mã vùng 0000) Xét K(1000) cắt ymax =6 xc x1 (yc y1 )/ m yc ymax yc=6 xc=-1 +(6-7)/(5/3)=-8/5 Thay K bởi K1(-8/5,6) có mã vùng 0000) Vậy sau khi xén tỉa đoạn IK thu được I1K1 Cài đặt bằng c/c++ là : #define LEFT_EDGE 0x1 #define RIGHT_EDGE 0x2 #define TOP_EDGE 0x8 #define BOTTOM_EDGE 0x4 #define INSIDE(a) (!a) #define REJECT(a,b) (a&b) #define ACCEPT(a,b) (!(a|b)) unsigned char encode(double x, double y, double xmin, double ymin, double xmax, double ymax){ unsigned char code = 0x00; if (x xmax) code = code | RIGHT_EDGE; if (y ymax) code = code | BOTTOM_EDGE; return code; } 4.2.3.2. Giải thuật LyangbarskyPTIT : U1=0 P1(x1,y1) P(u) P (x ,y ) 2 2 2 U2=1 O Hình 4.8 Phương trình tham số cho đoạn thẳng Biểu diễn đoạn thẳng theo tham biến: đoạn thẳng bất kỳ đi qua hai điểm P1(x1,y1) và P2(x2,y2) chúng ta có phương trình tham biến : x=x(u) có 0<=u<=1 62
  64. Chương 4: Các giải thuật đồ hoạ cơ sở y=y(u) Vì vectơ chỉ có một chiều nên vectơ vị trí: P(u)=P1 + (P2-P1).u x = x1 + (x2 - x1)u = x1 + x.u y = y1 + (y2 - y1)u = y1 + y.u U1=1 top P2 Ur ymax P1 Ut left Ul right U0=0 ymin Ub bottom xmin xmax Hình 4.9 Mô tả giải thuật LyaBarsky . Khi ta chuyển động dọc theo đường mở rộng với u thẳng từ - tới + thì ta phải: o Chuyển từ bên ngoài vào bên trong hai đường biên của cửa sổ cắt tỉa (ở dưới và bên trái) o Sau đó chúng ta di chuyển từ trong ra bên ngoài của hai đường biên khác (từ trên và từ bên phải) . Với điểm (x,y) nằm bên trong cửa sổ cắt tỉa: xmin <= x1 + x.u <= xmax ymin <= y1 + y.u <= ymax Suy ra: - x.u <= x1 – xmin k=1 x.u <= xmax – x1 k=2 - y.u <= y1 – ymin k=3 PTIT y.u <= ymax – y1 k=4 Viết tổng quát: Pk.u <=qk có k=1,2,3,4 Trong đó: P1 = - xq1=x1 – xmin (phải) P2 = xq2=xmax – x1 (trái) P3 = - yq3=y1 – ymin (trên) P4 = yq4=ymax – y1 (dưới) Xét: . Nếu Pk = 0: điều đó tương đương với việc đoạn thẳng đang xét song song với cạnh thứ k của hình chữ nhật clipping. 63
  65. Chương 4: Các giải thuật đồ hoạ cơ sở a) Nếu qk = 0 thì đoạn thẳng nằm trong hoặc nằm trên cạnh của cửa sổ clipping. Yêu cầu khảo sát tiếp. . Nếu Pk  0: đoạn thẳng đang xét sẽ cắt cạnh k tương ứng của cửa sổ clipping tại vị trí trên đoạn thẳng uk = qk/Pk a) Pk 0 thì đoạn thẳng mở rộng tiến hành từ trong ra ngoài của đường biên tương ứng. Kết hợp lại ta có các bước sau: (Với u0 Exit qk>=0 thực hiện bước tiếp theo Bước 2: Tính: q  U max 0  u : u k , P 0 0  k k k  Pk  q  U min 1  u : u k , P 0 1  k k k  Pk  u0 là các giá trị cực đại của tập hợp đang chứa 0 và các giá trị uk được tính u1 là các giá trị cực tiểu của tập hợp đang chứa 1 và các giá trị uk được tính Ví dụ: cho cửa sổ cắt tỉa hình chữ nhật có góc trái dưới L(1,2) và góc phải trên R(9,8). Có các đoạn AB toạ độ A(11,10) và B(11,6), đoạn CD toạ độ C(3,2) và D(8,4), đoạn IJ toạ độ I(-1,7) và J(11,1). Tìm các hạng mục cắt tỉa. Giải: . Xét AB PTIT P1 = 0q1=10 P2 = 0q2=-2 P3 = -4q3=4 P4 = 4q4=2 Có P2 =0 mà q2 =-2 0) 64
  66. Chương 4: Các giải thuật đồ hoạ cơ sở Vậy CD nằm hoàn toàn trong cửa sổ . Xét IJ P1 = -12q1=-2 u1=1/6 P2 = 12 q2=10 u2=5/6 P3 = 6q3=5 u3=5/6 P4 = -6 q4=1 u4=-1/6 Vậy u0=max(0,1/6,-1/6)=1/6 (với Pk 0) Vì u0 *u1) retVal = FALSE; else if (r > *u0) *u0 = r; } else if ( p > 0.0) { r = q / p; if (r < *u0) retVal = FALSE;PTIT else if (r < *u1) *u1 = r; } Else { if (q < 0.0) retVal = FALSE; } return (retVal); } void clipline(double x1, double y1, double x2, double y2, double xmin, double ymin, double xmax, double ymax){ double u0 = 0.0, u1 = 1.0, dx, dy; double oldx1, oldy1, oldx2, oldy2; oldx1 = x1; oldy1 = y1; oldx2 = x2; oldy2 = y2; 65
  67. Chương 4: Các giải thuật đồ hoạ cơ sở dx = x2 - x1; if (cliptest(-dx, x1 - xmin, &u0, &u1)) if (cliptest(dx, xmax-x1, &u0, &u1)) { dy = y2 - y1; if (cliptest(-dy, y1 - ymin, &u0, &u1)) if (cliptest(dy, ymax - y1, &u0, &u1)){ if (u1 0.0){ x1 += u0 * dx; y1 += u0 * dy; } setcolor(RED); line(oldx1, oldy1, x1, y1); line(x2, y2, oldx2, oldy2); setcolor(YELLOW); line(x1, y1, x2, y2); }}} 4.2.4. Giải thuật xén tỉa đa giác (Sutherland Hodgman) 4.2.4.1. Khái niệm Theo qui ước: một đa giác với các đỉnh P1, ,PN (các cạnh là Pi-1Pi và PNP1) được gọi là theo hướng dương nếu các hình theo thứ tự đã cho tạo thành một mạch ngược chiều kim đồng hồ. Nếu bàn tay trái của một người dọc theo bất kỳ cạnh Pi-1Pi hoặc PNP1 cũng chỉ về bên trong đa giác. L R Hình 4.10 Qui tắc tìm hướng dương của một đa giác hướng Khảo sát một điểm so với một đường thẳng: PTITABxAP K P(x,y) A(x1,y1) B(x2,y2) Hình 4.11 Khảo sát một điểm so với đường thẳng Có điểm A(x1,y1), B(x2,y2) và P(x,y) Theo định nghĩa thì tích của hai vectơ (ABxAP) chỉ theo hướng của vectơ K với mặt phẳng (xoy). Có: AB=(x2-x1)i + (y2-y1)j AP=(x-x1)i + (y-y1)j 66
  68. Chương 4: Các giải thuật đồ hoạ cơ sở Vậy ABxAP=[ (x2-x1).(y-y1) – (y2-y1).(x-x1) ].K Do đó hướng được xác định như sau: C (x2 x1)(y y1) (y2 y1)(x x1) Nếu C dương thì P nằm bên trái AB Nếu C âm thì P nằm bên phải AB 4.2.4.2. Giải thuật Hodgman Cho P1, ,PN là danh sách các đỉnh của đa giác đã bị cắt tỉa. Cho cạnh AB (điểm A,B) là cạnh bất kỳ. Đa giác cắt tỉa lồi hướng dương. output A A A A P A i-1 Pi output Pi I Pi-1 Pi Pi-1 B B B B Pi-1 I Pi output output Hình 4.12 Các trường hợp trong giải thuật Hodgman . Nếu cả Pi-1 và Pi đều nằm bên trái của cạnh này thì Pi được lưu lại (đưa vào output) của đa giác cắt tỉa. . Nếu cả Pi-1 và Pi đều nằm bên phải của cạnh thì không có đỉnh nào được lưu lại. . Nếu Pi-1 nằm bên trái và Pi nằm bên phải của cạnh thì giao điểm I của Pi-1Pi với cạnh sẽ được lưu lại. . Nếu Pi-1 nằm bên phải và Pi nằm bên trái thì cả giao điểm I và Pi đều được lưu lại. 4.2.4.3. Minh hoạ thuật toán Sutherland – Hodgman F=P1 (F là đỉnh được đưa vào đầu tiên, S là đỉnh đưa vào trước P - đỉnh được đưa). Sơ đồ bên phải khép kín đa giác bởiPTIT PNP1 67
  69. Chương 4: Các giải thuật đồ hoạ cơ sở Begin P(Vertex Input) Vertex Output, F,AB,N I=1 Tiếp S=Pi N Y SF cắt AB N i=1 i++ F=P1 Y N Tìm giao I SPi cắt AB Y Vertex output I Giao cắt I Vertex output End I S=Pi Y N Y i<N S bên trái Vertex output AB S N End Hình 4.13 Sơ đồ khối thuật toán Hodgman 4.2.4.4. Ví dụ minh hoạ: PTIT A 5 D B C5 A 5 D A A D C4 A A 4 B 1 B 4 C1 B C 1 C2 A B C3 C 2 A B B C B 2 3 D 3 D A E5 D 5 D A E4 D 4 E1 1 E2 D B D C B E3 C 2 3 Hình 4.14 Ví dụ dùng giải thuật Hodgman xén tỉa đa giác A1 A5 68
  70. Chương 4: Các giải thuật đồ hoạ cơ sở Ví dụ 2: hãy sử dụng thuật toán Hodgman để cắt xén đoạn thẳng nối P1(-1,2) đến P2(6,4) trên cửa sổ A(1,1), B(5,1), C(5,3) và D(1,3) I1 P2(6,4) I2 D(1,3) C(5,3) I3 P1(-1,2) B(5,1) A(1,1) Hình 4.15 Ví dụ dùng thuật toán Hodgman xén tỉa đoạn P1P2 Theo thuật toán Hodgman ta xén P1P2 dựa trên từng cạnh. . AB: ta xét C=(x2-x1)(y-y1) – (y2-y1)(x-x1) Điểm P1: C=(5-1)(2-1)-(1-1)(-1-1) = 4 >0 nằm bên trái Điểm P2: C= (5-1)(4-1)-(1-1)(-1-1) = 12 >0 nằm bên trái Vậy P1P2 đều được lưu . BC Điểm P1:C = (5-5)(2-1)-(3-1)(-1-5)= 12 >0 nằm bên trái Điểm P2:C = - (3-1)(6-5) = -2 0 nằm bên trái Điểm I1:C=(1-5)(26/7PTIT -3) = -20/7 <0 nằm bên phải Giao điểm I2: yc 3 xc x1 (yc y1) / m 7 5 1 (3 2). 2 2 VậyI2(5/2,3)có P1I2được lưu . DA Điểm P1: C = -(1-3)(-1-1) = -4nằm bên phải Điểm I2: C = -(1-3)(5/2-1) = 7/2nằm bên trái Giao điểm I3: 69
  71. Chương 4: Các giải thuật đồ hoạ cơ sở xc 1 yc y1 (xc x1 )m I3(1, 18/7) 2 4 2 (1 ( 1)). 2 7 7 Tóm lại: Cắt xén đoạn P1P2 được đoạn I2I3có I2(5/2,3) và I3(1,18/7) Tóm tắt chương: Hiển thị đối tượng là quá trình đưa các mô tả đối tượng từ thế giới thực sang một thiết bị xuất cụ thể nào đó. Mỗi đối tượng có thể được quan sát ở nhiều vị trí và góc độ khác nhau. Thông thường mỗi hình ảnh mà chúng ta quan sát được trên màn hình thiết bị được gọi là một góc nhìn (view) của đối tượng. Quá trình loại bỏ các phần hình ảnh nằm ngoài một vùng cho trước được gọi là xén tỉa. Vùng được dùng để xén tỉa gọi là cửa sổ xén tỉa. Các thuật toán xén tỉa đoạn thẳng Cohen-Sutherland, LyaBarsky đều tập trung giải quyết hai vấn đề chính nhằm tối ưu tốc độ thuật toán đó là: loại bỏ việc tìm giao điểm đối với các đoạn thẳng chắc chắn không cắt cửa sổ (như nằm hoàn toàn trong, nằm hoàn toàn ngoài), và với đoạn thẳng có khả năng cắt cửa sổ, cần phải tìm cách hạn chế số lần tìm giao điểm với các biên không cần thiết. Thuật toán Cohen-Sutherland giải quyết hai ý này thông qua kiểu dữ liệu mã vùng mà về bản chất đó chỉ là sự mô tả vị trí tương đối của vùng đang xét so với các biên của cửa sổ. Còn thuật toán LyaBarsky thì tuy dựa vào phương trình tham số của đoạn thẳng để lập luận nhưng thực chất là dựa trên việc xét các giao điểm có thể có giữa đoạn thẳng kéo dài với các biên của cửa sổ (cũng được kéo dài). Các giao điểm này tương ứng với các giá trị rk = qk/pk. Cả hai thuật toán này đều có thể được mở rộng cho việc xén hình trong đồ hoạ 3D. Bài tập: 1. Tìm phép biến đổi chuẩn hoá tạo ánh xạ cho một cửa sổ mà góc bên trái phía dưới của nó (1,1) và góc bên phải trên (3,5) vào: a. Là màn hình thiPTITết bị được chuẩn hoá toàn bộ. b. Một khung nhìn có góc bên trái dưới (0,0) và góc bên trái trên (1/2,1/2) 2. Cho cửa sổ cắt tỉa hình chữ nhật có góc bên trái dưới (-3,-2) và góc phải trên (2,3), dùng giải thuật Cohen Sutherland xén tỉa đoạn thẳng AB có toạ độ là A(3,2) và B(-2,-4). 3. Cho cửa sổ cắt tỉa hình chữ nhật có góc bên trái dưới (-3,-2) và góc phải trên (2,3), dùng giải thuật LyaBarsky xén tỉa đoạn thẳng AB có toạ độ là A(3,2) và B(- 2,-4). 4. Viết chương trình cài đặt thuật toán Cohen Sutherland. 5. Viết chương trình cài đặt thuật toán LyaBarsky Viết chương trình cài đặt thuật toán Sutherland Hodgman 70
  72. Chương 5: Phép chiếu CHƯƠNG 5: PHÉP CHIẾU –PROJECTION 5.1. KHÁI NIỆM CHUNG 5.1.1.Nguyên lý về 3D (three-Dimension) Đồ họa 3 chiều (3D computer graphics) bao gồm việc bổ xung kích thước về chiều sâu của đối tượng, cho phép ta biểu diễn chúng trong thế giới thực một cách chính xác và sinh động hơn. Tuy nhiên các thiết bị truy xuất hiện tại đều là 2 chiều, Do vậy việc biểu diễn được thực thi thông qua phép tô chát (render) để gây ảo giác (illusion) về độ sâu Đồ hoạ 3D là việc chyển thế giới tự nhiên dưới dạng các mô hình biểu diễn trên các thiết bị hiển thị thông qua kỹ thuật tô chát (rendering). 5.1.2. Đặc điểm của kỹ thuật đồ hoạ 3D Có các đối tượng phức tạp hơn các đối tượng trong không gian 2D . Bao bởi các mặt phẳng hay các bề mặt . Có các thành phần trong và ngoài Các phép biến đổi hình học phức tạp Các phép biến đổi hệ toạ độ phức tạp hơn Thường xuyên phải bổ xung thêm phép chiếu từ không gian 3D vào không gian 2D Luôn phải xác định các bề mặt hiển thị 5.1.3.Các phương pháp hiển thị 3D Với các thiết bị hiển thị 2D thì chúng ta có các phương pháp sau để biểu diễn đối tượng 3D: . Kỹ thuật chiếu (projection): Trực giao (orthographic)/phối cảnh (perspective) . Kỹ thuật đánh dấu độ sâu (depth cueing) . Nét khuất (visible line/surface identification) . Tô chát bề mặt (surfacePTIT rendering) . Cắt lát (exploded/cutaway scenes, cross-sections) Các thiết bị hiển thị 3D: . Kính stereo - Stereoscopic displays* . Màn hình 3D – Holograms 71
  73. Chương 5: Phép chiếu Exploded/cutaway Perspective (phối Shadows as depth cues (tạo bóng cảm scenes (cắt lát) cảnh) and Depth of giác có chiều sâu) Field (chiều sâu) Hình 5.1 Các cách mô tả đối tượng 3D Hình chiếu cạnh Hình chiếu bằng Hình chiếu đứng Hình 5.2 Các góc nhìn khác nhau của mô hình 3D x2 y2 z2 r2 Mô hình 3D Nét khuất (Implicit) Đa giác (3D Modelling) (Polygonal) PTITx sin4 Tham số y cos2 (Parametric) Mảnh nhỏ (Particles) Hình 5.3 Các cách mô tả đối tượng 3D 5.2.PHÉP CHIẾU Định nghĩa về phép chiếu Một cách tổng quát, phép chiếu là phép chuyển đổi những điểm của đối tượng trong hệ thống tọa độ n chiều thành những điểm trong hệ thống tọa độ có số chiều nhỏ hơn n. 72
  74. Chương 5: Phép chiếu Định nghĩa về hình chiếu Ảnh của đối tượng trên mặt phẳng chiếu được hình thành từ phép chiếu bởi các đường thẳng gọi là tia chiếu (projector) xuất phát từ một điểm gọi là tâm chiếu (center of projection) đi qua các điểm của đối tượng giao với mặt chiếu (projection plan). Các bước xây dựng hình chiếu 1. Đối tượng trong không gian 3D với tọa độ thực được cắt theo một không gian xác định gọi là view volume. 2. View volume được chiếu lên mặt phẳng chiếu. Diện tích choán bởi view volume trên mặt phẳng chiếu đó sẽ cho chúng ta khung nhìn. 3. Là việc ánh xạ khung nhìn vào trong một cổng nhìn bất kỳ cho trước trên màn hình để hiển thị hình ảnh. täa ®é thùc täa ®é theo vïng täa ®é thiÕt khung nh×n 3D c¾t bÞ PhÐp biÕn ®æi vµo C¾t theo view PhÐp chiÕu trªn cæng nh×n cña volum mÆt ph¼ng chiÕu täa ®é thiÕt bÞ Hình 5.4 Mô hình nguyên lý của tiến trình biểu diễn đối tượng 3D PhÐp chiÕu h×nh häc ph¼ng PhÐp chiÕu song PhÐp chiÕu phèi c¶nh song PhÐp chiÕu Trùc giao Mét ®iÓm PTITXiªn Axonometric ChiÕu Hai ®iÓm b»ng Cavalier Trimetric ChiÕu Cabinet Ba ®iÓm ®øng ChiÕu Dimetric c¹nh PhÐp chiÕu Isometric kh¸c Hình 5.5 Phân loại các phép chiếu 73
  75. Chương 5: Phép chiếu Hình 5.6 Ví dụ minh hoạ các phép chiếu phối cảnh 5.3. PHÉP CHIẾU SONG SONG (Parallel Projections ) Phép chiếu song song (Parallel Projections) là phép chiếu mà ở đó các tia chiếu song song với nhau hay xuất phát từ điểm vô cùng. Phân loại phép chiếu song song dựa trên hướng của tia chiếu (Direction Of Projection) và mặt phẳng chiếu (projection plane). 5.3.1.Phép chiếu trực giao (Orthographic projection) Là phép chiếu song song và tia chiếu vuông góc với mặt phẳng chiếu. Về mặt toán học, phép chiếu trực giao là phép chiếu với một trong các mặt phẳng toạ độ có giá trị bằng 0. Thường dùng mặt phẳng z=0, ngoài ra x=0 và y=0. Ứng với mỗi mặt phẳng chiếu ta có một ma trận chiếu tương ứng. 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1PTIT0 0 0 1 0 0 [T ] [T ] [T ] y 0 0 1 0 x 0 0 1 0 z 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 Hình 5.7 Phép chiếu trực giao Thông thường thì người ta không sử dụng cả 6 mặt phẳng để suy diễn ngược hình của một đối tượng mà chỉ sử dụng một trong số chúng như: hình chiếu bằng, đứng, cạnh. Cả sáu góc nhìn đều có thể thu được từ một mặt phẳng chiếu thông qua các phép biến đổi hình học như quay, dịch chuyển hay lấy đối xứng. Ví dụ: giả sử chúng ta có hình chiếu bằng trên mặt phẳng z=0, với phép quay đối tượng quanh trục một góc 900 sẽ cho ta hình chiếu cạnh. 74
  76. Chương 5: Phép chiếu Đối với các đối tượng mà các mặt của chúng không song song với một trong các mặt phẳng hệ toạ độ thì phép chiếu này không cho hình dạng thật của vật thể. Muốn nhìn vật thể chính xác hơn người ta phải hình thành phép chiếu thông qua việc quay và dịch chuyển đối tượng sao cho mặt phẳng đó song song với các trục toạ độ. Hình của đối tượng quá phức tạp cần thiết phải biết các phần bên trong của đối tượng đôi lúc chúng ta phải tạo mặt cắt đối tượng. 5.3.2. Phép chiếu trục luợng (Axonometric) Phép chiếu trục lượng là phép chiếu mà hình chiếu thu được sau khi quay đối tượng sao cho ba mặt của đối tượng được trông thấy rõ nhất (thường mặt phẳng chiếu là z=0). Có 3 phép chiếu . Phép chiếu Trimetric . Phép chiếu Dimetric . Phép chiếu Isometric 5.3.2.1.Phép chiếu Trimetric Là phép chiếu hình thành từ việc quay tự do đối tượng trên một trục hay tất cả các trục của hệ tọa độ và chiếu đối tượng đó bằng phép chiếu song song lên mặt phẳng chiếu (thường là mặt phẳng z = 0). Ngoại trừ những mặt phẳng của đối tượng song song với mặt phẳng chiếu không thay đổi. Các mặt khác của đối tượng hay hình dạng của đối tượng thường biến dạng sau phép chiếu.Tuy nhiên tỉ lệ co (Shortening Factor - SF) là tỷ số của độ dài đoạn thẳng chiếu so với độ dài thực tế của đối tượng. Trên cơ sở SF phép chiếu trục lượng được chia làm ba loại sau: . Phép chiếu Trimetric . Phép chiếu Dimetric . Phép chiếu Isometric Việc tính các giá trị SF này của các trục tương ứng dựa vào công thức [U]* [T]. x' y' 0 1 1 0 0 1 x x PTIT ' ' x y 0 1 [U] 0 1 0 1 [T] y y ' ' xz yz 0 1 0 0 1 1 0 0 0 1 [ U ]: là ma trận vector đơn vị của các trục x, y, z bất biến [ T ]: là ma trận chiếu tổng hợp tương ứng SF- tỉ lệ co theo các trục là: f x'2 y'2 2 2 '2 '2 y y y f z x'z y'z f x xx yx 5.3.2.2.Phép chiếu Dimetric Là phép chiếu Trimetric với 2 hệ số tỉ lệ co bằng nhau, giá trị thứ 3 còn lại là tuỳ ý. 75