🔙 Quay lại trang tải sách pdf ebook Giáo Trình Đồ Hoạ Máy Tính Ebooks Nhóm Zalo ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC KHOA CÔNG NGHỆ THÔNG TIN TS. NGUYỄN HỮU TÀI GIÁO TRÌNH ĐỒ HỌA MÁY TÍNH (ĐÀO TẠO CỬ NHÂN CÔNG NGHỆ THÔNG TIN) NHÀ XUẤT BẢN ĐẠI HỌC HUẾ Huế, 2017 Mã số sách: GT/ -2017 ii LỜI NÓI ĐẦU Giáo trình Đồ họa Máy tính nhằm mang đến cho người học là các sinh viên ngành Công nghệ Thông tin những kiến thức cơ bản và chuyên sâu trong lĩnh vực đồ họa máy tính, rèn luyện và phát triển kỹ năng thực hành thực nghiệm, kỹ năng lập trình cho lĩnh vực đồ họa máy tính. Nội dung của giáo trình với thời lượng giảng dạy 3 tín chỉ gồm có 6 chương, 2 phục lục và 7 bài thực nghiệm được trình bày hướng dẫn chi tiết nhằm từng bước phát triển kỹ năng lập trình đồ họa, hiểu sâu và đánh giá chính xác các lý thuyết và giải thuật đồ họa. Bố cục của giáo trình gồm: Chương 1: Các yếu tố cơ sở của đồ họa Trình bày các khái niệm cơ bản về thiết bị đồ họa và điểm ảnh (Pixel). Giới thiệu và trình bày chi tiết các giải thuật dựng các đường cơ bản như: Đoạn thẳng, đường tròn, ellipse. Hướng dẫn chi tiết các bước để tạo ứng dụng khung phục vụ cho việc thực hành thực nghiệm thông qua “Bài thực nghiệm số 1”, để từ đó dẫn dắt làm quen và trang bị từng bước các kiến thức lập trình đồ họa trên windows với VC++ và MFC. Chương 2: Các hệ màu và cơ chế tổ chức bộ nhớ màn hình Trình bày đôi nét về cấu trúc màn hình màu. Tính chất giao thoa ánh sáng và nguyên lý tạo điểm màu trên màn hình hay máy in. Giới thiệu sơ bộ về các hệ màu RGB, CMY, HSV. Tìm hiểu về cơ chế tổ chức bộ nhớ màn hình, cách tính địa chỉ để truy xuất thông tin điểm ảnh thông qua mode đồ họa căn bản 13H, và chuẩn hiển thị đồ họa cao cấp Vesa. Chương 3: Các phép xén hình và tô màu Giới thiệu phạm vi và ứng dụng của bài toán xén hình. Trình bày chi tiết các giải thuật xén hình căn bản như: Xén đoạn thẳng vào hình chữ nhật, xén đa giác vào hình chữ nhật. Giới thiệu bài toán tô màu và ứng dụng. Trình bày chi tiết 2 giải thuật tô màu gồm: Giải thuật vết dầu loang (Flood fill), và giải thuật tô đa giác theo dòng quét (Scan-line). Tìm hiểu sâu hơn về vấn đề xử lý đồ họa của hệ thống thông qua “Bài thực nghiệm số 2” để xử iii lý bài toán tô màu theo giải thuật vết dầu loang. Chương 4: Các phép biến đổi hình học Trình bày lý thuyết biến đổi hình học affine với căn bản là các phép tính toán ma trận. Hệ tọa độ thuần nhất và lợi ích của nó trên mô hình xử lý máy tính. Một số ví dụ hướng dẫn thực hiện các bước phân tích bài toán biến hình phức tạp về thành tổng hợp của những phép biến hình cơ bản, dựa trên việc tính tích các ma trận. Phân tích bài toán quan sát vật thể trong không gian 3 chiều và sự mô phỏng thế giới thực. Chương 5: Mô hình WireFrame Trình bày chi tiết về mô hình Wireframe và cách thức tổ chức lưu trữ thông tin. Hướng dẫn xây dựng một ứng dụng mô phỏng việc quan sát vật thể 3 chiều trong không gian theo mô hình Wireframe, trong đó áp dụng kết hợp kiến thức của chương 4 và chương 5, thông qua “Bài thực nghiệm số 3”. Chương 6: Mô hình các mặt đa giác và vấn đề khử mặt khuất Giới thiệu mô hình các mặt đa giác, ưu và nhược điểm, cùng cách thức tổ chức lưu trữ thông tin. Giới thiệu bài toán khử mặt khuất và trình bày chi tiết các giải thuật sắp xếp theo độ sâu, giải thuật chọn lọc mặt sau, giải thuật vùng đệm độ sâu. “Bài thực nghiệm số 4” giúp phát triển ứng dụng 3DViewer mô phỏng việc quan sát vật thể trong không gian 3 chiều trên máy tính, trong đó vấn đề khử mặt khuất được xử lý bởi giải thuật chọn lọc mặt sau. Và “Bài thực nghiệm số 5” phát triển một bản nâng cấp của ứng dụng 3DViewer, trong đó vấn đề khử mặt khuất được xử lý bởi giải thuật vùng đệm độ sâu. Cuối cùng, hệ thống 2 phụ lục nhằm giúp sinh viên có thể tìm hiểu và nghiên cứu sâu hơn một số vấn đề mà trong khuôn khổ thời gian có hạn của học phần không cho phép tìm hiểu sâu. Nội dung cơ bản của các phụ lục bao gồm: Phụ lục 1: Các phương pháp dựng đường cong và mặt cong Trình bày chi tiết các phương pháp tạo đường cong và mặt cong hiệu quả trên mô hình máy tính. iv Phụ lục 2: Các mô hình chiếu sáng Trình bày chi tiết việc tính toán mô phỏng các loại hình chiếu sáng lên vật thể 3 chiều nhằm tăng tính trung thực của hình ảnh mô phỏng, tạo cho hình ảnh mô phỏng được trung thực và “đẹp hơn”. Đề xuất các giải pháp công nghệ xử lý kết hợp nhằm giải quyết vấn đề tốc độ thực thi cho bài toán xử lý mô phỏng hình ảnh 3 chiều trên máy tính. “Bài thực nghiệm số 6” và “Bài thực nghiệm số 7” giúp phát triển và hoàn thiện hơn nữa ứng dụng 3DView, để ứng dụng có thể mô phỏng trung thực hơn các đối tượng 3 chiều. Qua đó, giúp sinh viên có được kiến thức sâu hơn và kỹ năng vững vàng về vấn đề xử lý mô phỏng đối tượng 3 chiều trên máy tính. Với mong muốn tạo điều kiện tốt nhất để sinh viên có thể dễ dàng lĩnh hội kiến thức lý thuyết, phát triển năng lực thực nghiệm và kỹ năng giải quyết vấn đề nói chung hay kỹ năng lập trình nói riêng, tác giả đã cố gắng để trình bày các vấn đề thuộc lĩnh vực đồ họa máy tính một cách chi tiết mạch lạc và chuẩn xác nhất có thể, các kỹ thuật xử lý luôn sát với công nghệ trong thực tiễn. Hy vọng rằng cuốn sách sẽ mang lại nhiều bổ ích cho sinh viên cũng như bạn đọc. Tác giả cũng mong nhận được nhiều đóng góp ý kiến của quý đồng nghiệp cùng bạn đọc để cuốn sách được hoàn thiện hơn trong lần tái bản sau. Tác giả TS. Nguyễn Hữu Tài v vi MỤC LỤC Chương 1 ................................................................................................... 1 1. Các khái niệm cơ bản .................................................................. 1 1.1. Thiết bị đồ họa và điểm ảnh ................................................. 1 1.2. Điểm và đoạn thẳng trong mặt phẳng .................................. 2 2. Các giải thuật vẽ đoạn thẳng ....................................................... 3 2.1. Vẽ đoạn thẳng dựa vào phương trình ................................... 3 2.2. Vẽ đoạn thẳng dựa vào giải thuật Bresenham ..................... 6 2.3. Môi trường thực nghiệm và các bước thiết lập cơ bản ...... 13 2.4. So sánh đánh giá hai giải thuật dựng đường thẳng ............ 20 3. Các giải thuật vẽ đường tròn ..................................................... 23 3.1. Giải thuật vẽ đường tròn MidPoint .................................... 24 3.2. Giải thuật vẽ đường tròn Bresenham ................................. 29 3.3. So sánh đánh giá hai giải thuật dựng đường tròn .............. 32 4. Giải thuật vẽ Ellipse .................................................................. 33 4.1. Giải thuật Bresenham cho vẽ hình Ellipse ......................... 35 4.2. Tóm tắt giải thuật Bresenham cho vẽ Ellipse .................... 38 4.3. Cài đặt giải thuật ................................................................ 38 5. Bài tập cuối chương .................................................................. 44 Chương 2 ................................................................................................. 46 1. Đôi nét về cấu trúc màn hình màu ............................................ 46 2. Các hệ màu ................................................................................ 47 2.1. Hệ RGB .............................................................................. 48 2.2. Hệ màu CMY ..................................................................... 49 2.3. Hệ màu HSV ...................................................................... 50 3. Cơ chế tổ chức bộ nhớ màn hình .............................................. 54 3.1. Cơ chế hoạt động của chế độ màn hình độ phân giải 320 × 200 với 256 màu.............................................................................. 55 3.2. Cơ chế hoạt động của màn hình theo chuẩn Vesa ............. 56vii 4. Kỹ thuật thực hiện vẽ đồ họa ở hậu trường (Off-screen Rendering) ........................................................................................... 58 Chương 3 ................................................................................................. 63 1. Trường hợp hình F là một tập hữu hạn điểm ............................ 64 2. Trường hợp xén một đoạn thẳng vào một vùng hình chữ nhật trong không gian 2 chiều ..................................................................... 64 2.1. Khi cạnh của hình chữ nhật song song với trục tọa độ ...... 64 2.2. Khi 1 cạnh của hình chữ nhật tạo với trục hoành một góc  ......................................................................................................... 77 3. Clipping một đa giác vào trong một vùng hình chữ nhật ......... 77 3.1. Giải thuật Sutherland-Hodgman ........................................ 77 3.2. Cài đặt giải thuật ................................................................ 79 3.3. Nhược điểm của giải thuật Sutherland-Hodgman và hướng xử lý khắc phục ............................................................................... 82 4. Một số giải thuật tô màu ........................................................... 83 4.1. Giải thuật vết dầu loang ..................................................... 83 4.2. Giải thuật tô màu đa giác theo dòng quét (Scan-line Algorithm) ..................................................................................... 104 5. Bài tập cuối chương ................................................................ 115 Chương 4 ............................................................................................... 117 1. Các phép biến đổi hình học hai chiều (Affine 2D) ................. 118 1.1. Phép tịnh tiến ................................................................... 118 1.2. Phép đồng dạng ................................................................ 118 1.3. Phép đối xứng .................................................................. 119 1.4. Phép quay quanh gốc tọa độ ............................................ 120 1.5. Phép biến dạng (Twist Transformation) .......................... 120 1.6. Tọa độ thuần nhất (Homogeneous Coordinates) ............. 120 1.7. Tổng hợp các phép biến đổi Affine ................................. 120 1.8. Phép quay quanh điểm bất kỳ .......................................... 122 1.9. Các ví dụ minh họa .......................................................... 123viii 1.10. Biến đổi hệ trục tọa độ (hay biến đổi ngược) ................ 126 1.11. Cài đặt ............................................................................ 127 2. Các phép biến đổi Affine 3D .................................................. 128 2.1. Các hệ trục tọa độ ............................................................ 128 2.2. Các công thức biến đổi .................................................... 129 3. Các phép chiếu vật thể trong không gian lên mặt phẳng ........ 132 3.1. Phép chiếu phối cảnh (Perspective) ................................. 132 3.2. Phép chiếu song song ....................................................... 133 4. Quan sát vật thể 3 chiều và quay hệ quan sát ......................... 133 4.1. Biến đổi từ hệ trục cục bộ sang hệ trục người quan sát ... 134 4.2. Phép chiếu phối cảnh ....................................................... 140 4.3. Phép chiếu song song ....................................................... 141 4.4. Cài đặt .............................................................................. 142 5. Bài tập cuối chương ................................................................ 142 Chương 5 ............................................................................................... 144 1. Mô hình Wireframe ................................................................ 145 2. Vẽ hình dựa trên dữ liệu kiểu WireFrame với các phép chiếu 147 2.1. Phép chiếu trực giao đơn giản .......................................... 147 2.2. Phép chiếu phối cảnh đơn giản ........................................ 147 2.3. Cài đặt thực nghiệm cho mô hình wireframe ................... 148 3. Bài tập cuối chương ................................................................ 160 Chương 6 ............................................................................................... 162 1. Mô tả đối tượng 3 chiều bằng mô hình các mặt đa giác ......... 162 2. Xây dựng cấu trúc dữ liệu cho mô hình các mặt đa giác ........ 164 3. Các phương pháp khử mặt khuất ............................................ 167 3.1. Giải thuật người thợ sơn với chiến lược sắp xếp theo chiều sâu (Depth-Sorting) ....................................................................... 167 3.2. Giải thuật chọn lọc mặt sau (Back-Face Detection) ........ 170 3.3. Cài đặt minh họa cho giải thuật chọn lọc mặt sau ........... 172 ix 3.4. Giải thuật vùng đệm độ sâu (Z-Buffer)............................ 190 3.5. Cài đặt minh họa cho giải thuật “vùng đệm độ sâu” ....... 193 4. Bài tập cuối chương ................................................................ 203 Chương 7 ............................................................................................... 204 1. Nguồn sáng xung quanh ......................................................... 204 2. Nguồn sáng định hướng .......................................................... 204 2.1. Khái niệm ......................................................................... 204 2.2. Tính toán mô phỏng ......................................................... 205 2.3. Cài đặt giải thuật .............................................................. 207 3. Nguồn sáng điểm .................................................................... 209 4. Mô hình bóng Phong ............................................................... 209 4.1. Khái niệm ......................................................................... 209 4.2. Tính toán mô phỏng ......................................................... 211 4.3. Cài đặt giải thuật .............................................................. 216 5. 4. BÀI TẬP CUỐI CHƯƠNG ................................................ 228 Chương 8 ............................................................................................... 229 1. Đường cong Bezier và mặt cong Bezier ................................. 230 1.1. Giải thuật De Casteljau .................................................... 231 1.2. Dạng Bernstein của các đường cong và mặt cong Bezier 232 1.3. Dạng biểu diễn ma trận của đường Bezier ....................... 233 1.4. Các tính chất của đường cong Bezier .............................. 234 1.5. Đánh giá đường cong Bezier và sự khác biệt của đường cong Spline .................................................................................... 237 2. Đường cong Spline và B-Spline ............................................. 239 TÀI LIỆU THAM KHẢO ..................................................................... 242 x xi DANH SÁCH HÌNH VẼ Hình 1.1. Giao diện đồ họa windows 8 thể hiện trên màn hình của hãng Dell ............................................................................................................ 1 Hình 1.2. Minh họa việc hiển thị hình ảnh đồ họa trên thiết bị .......... 2 Hình 1.3. Ảnh minh họa một đoạn thẳng từ A(5,4) đến B(10,7) ........ 5 Hình 1.4. Minh họa việc chọn lựa điểm P hay Q dựa vào các tham số ................................................................................................................... 7 Hình 1.5. Minh họa đoạn thẳng được vẽ trên thiết bị đồ họa. Các Pixel vuông màu đỏ là hình ảnh thể hiện của đoạn thẳng AB trên màn hình.......................................................................................................... 12 Hình 1.6. Các bước tạo một project phục vụ cho quá trình thực nghiệm ..................................................................................................... 14 Hình 1.7. Giao diện MFC Application Wizard giúp chọn lựa kiểu ứng dụng ......................................................................................................... 15 Hình 1.8. Hình ảnh của một ứng dụng dạng dialog based làm khuôn mẫu xây dựng các ứng dụng thực nghiệm đồ họa máy tính ................... 15 Hình 1.9. Thiết kế giao diện chương trình LineDemo ...................... 16 Hình 1.10. Menu ngữ cảnh trong quá trình tạo biến nhận dữ liệu từ edit control .............................................................................................. 16 Hình 1.11. Đặt tên và xác định các thông số cho biến ...................... 17 Hình 1.12. Các bước để thêm một hàm xử lý vào lớp CLineDemoDlg ................................................................................................................. 17 Hình 1.13. Xác định tên hàm và các tham số ................................... 18 Hình 1.14. Kết quả thực thi chương trình với hình ảnh biểu diễn cho một đoạn thẳng AB được tính toán theo giải thuật Bresenham .............. 20 Hình 1.15. Đồ thị toán học của đường tròn tâm O bán kính R ......... 23 Hình 1.16. Minh họa việc chọn lựa điểm P hay Q ............................ 24 Hình 1.17. Minh họa hàm circle f ....................................................... 25 Hình 1.18. Minh họa việc hiển thị các điểm ảnh của đường tròn với các kích cỡ khác nhau ............................................................................. 28 xii Hình 1.19. Hình Ellipse với các cung AC và BC ............................. 33 Hình 1.20. Minh họa kỹ thuật tô ellipse theo dòng quét ................... 41 Hình 1.21. Hình ảnh thực nghiệm dựng đường ellipse và hình ellipse bởi giải thuật Bresenham ........................................................................ 44 Hình 2.1. Màu sắc và sự giao thoa .................................................... 46 Hình 2.2. Hai loại cấu trúc màn hình màu: (a) CRT, (b) LCD ......... 47 Hình 2.3. Ảnh biểu diễn của một mũi tên màu trắng, và một chữ E trên máy tính được phóng lớn tương ứng với hai loại màn hình CRT và LCD ......................................................................................................... 47 Hình 2.4. Biểu đồ thể hiện các sắc độ trong không gian màu chuẩn CIE 1931 ................................................................................................. 48 Hình 2.5. Không gian màu trong chế độ 24-bit ................................ 49 Hình 2.6. Hệ màu CMYK chuyên dùng trong in ấn ......................... 49 Hình 2.7. Hệ màu HSV biểu diễn trong chế độ số thực (từ 0 đến 1) 50 Hình 2.8. Hệ màu HSV biểu diễn trong chế độ lượng hóa nguyên .. 51 Hình 2.9. Minh họa việc chuyển đổi qua lại giữa 2 hệ màu HSV và RGB ........................................................................................................ 51 Hình 2.10. Minh họa hệ màu HSL .................................................... 54 Hình 2.11. Minh họa hệ màu Lab ..................................................... 54 Hình 2.12. Một số mode màn hình cùng thông tin chi tiết về độ phân giải và số màu có thể hiển thị, số bit phân phối cho 3 thành phần màu RGB của một điểm ảnh ........................................................................... 57 Hình 2.13. Minh họa tình huống tiêu cực khi thực hiện đồ họa trực tiếp trên vùng bộ nhớ dành riêng cho màn hình với các ứng dụng đồ họa đòi hỏi nhiều thời gian xử lý. Người sử dụng có thể quan sát thấy một chuỗi các hình ảnh đang trong quá trình xây dựng, thay vì chỉ một hình ảnh hoàn thiện như mong muốn .............................................................. 59 Hình 3.1. Minh họa kỹ thuật Clipping trong phần mềm AutoCad ... 63 Hình 3.2. Minh họa việc xén đoạn thẳng AB vào hình chữ nhật ...... 64 Hình 3.3. Minh họa các tình huống có thể xảy ra khi xén đoạn thẳng vào hình chữ nhật .................................................................................... 69 xiii Hình 3.4. Phân bổ mã vùng dựa theo vị trí tương ứng với hình chữ nhật .......................................................................................................... 71 Hình 3.5. Minh họa tình huống xử lý phức tạp nhất đối với thuật toán Liang-Barsky ........................................................................................... 76 Hình 3.6. Minh họa bài toán xén đa giác vào hình chữ nhật ............ 77 Hình 3.7. Minh họa kết quả các bước của giải thuật ........................ 78 Hình 3.8. Hình ảnh thực nghiệm giải thuật Sutherland-Hodgman. Với đầu vào là đa giác lớn (viền màu đỏ) chúng ta thu được đa giác nhỏ (viền màu xanh blue) ........................................................................................ 83 Hình 3.9. Minh họa tình huống còn sai sót của giải thuật ................ 83 Hình 3.10. Ảnh gốc và bản sửa đổi của nó, thu được sau khi tiến hành tô màu vùng nền đen thành nền xanh theo giải thuật vết dầu loang ....... 84 Hình 3.11. Giao diện cho ứng dụng minh họa bài toán tô màu sử dụng giải thuật vết dầu loang .................................................................. 86 Hình 3.12. Hình ảnh trước khi, trong khi, và sau khi một vùng ảnh trên cửa sổ được tô màu theo giải thuật vết dầu loang ............................ 90 Hình 3.13. Chi phí thời gian với các hàm thao tác điểm ảnh SetPixel và GetPixel trên Device Context ............................................................. 91 Hình 3.14. Giao diện chương trình nâng cấp với nút “Fast Flood Fill” ................................................................................................................. 94 Hình 3.15. Chi phí thời gian với các hàm thao tác điểm ảnh SetPixel và GetPixel trên Memory Device Context .............................................. 96 Hình 3.16. Nâng cấp giao diện với nút “The best Flood Fill” ........ 100 Hình 3.17. Kết quả tô màu và chi phí thời gian thực hiện hàm MyBestFloodFill, thông qua việc truy xuất trực tiếp vào bộ nhớ của ảnh DIB để lấy thông tin hay thiết lập thông tin của điểm ảnh ................... 103 Hình 3.18. Minh họa một số tình huống của dòng quét trong giải thuật Scan-line....................................................................................... 104 Hình 3.19. Minh họa hình ảnh đa giác trước (a) và sau khi được tô (b) ............................................................................................................... 104 Hình 3.20. Hình ảnh phóng lớn mô tả quá trình quét (scan) theo hàng xiv để tiến hành tô màu đa giác theo thời gian............................................ 105 Hình 3.21. Minh họa bài toán “mê cung” ....................................... 105 Hình 3.22. Minh họa cơ chế nội suy giao điểm trong giải thuật tô đa giác theo dòng quét (Scanline Algorithm) ............................................ 107 Hình 3.23. Kết quả tô đa giác có 28 đỉnh ....................................... 115 Hình 3.24. Kết quả tô đa giác có 561 đỉnh, trong đó phần nhiều là các cạnh với độ dài rất bé ............................................................................ 115 Hình 4.1. Hình ảnh thu được từ các góc quan sát khác nhau của cùng một đối tượng. Việc thay đổi góc quan sát được thực hiện thông qua các phép biến đổi hình học 3 chiều ............................................................. 117 Hình 4.2. Minh họa phép biến đổi đồng dạng cho một tam giác .... 119 Hình 4.3. Hình vẽ minh họa phép quay quanh điểm M .................. 124 Hình 4.4. Minh họa phép biến đổi thuận và biến đổi nghịch .......... 126 Hình 4.5. Hệ tọa độ 3 chiều trực tiếp và gián tiếp .......................... 128 Hình 4.6. Hệ tọa độ Đề-cát và hệ tọa độ cầu .................................. 129 Hình 4.7. Minh họa phép chiếu phối cảnh ...................................... 132 Hình 4.8. Minh họa bài toán quan sát vật thể trong không gian 3 chiều ...................................................................................................... 134 Hình 4.9. Tịnh tiến hệ trục OXYZ thành O’X1Y1Z1....................... 135 Hình 4.10. Quay hệ trục O’X1Y1Z1 thành O’X2Y2Z2 ..................... 136 Hình 4.11. Quay hệ trục O’X2Y2Z2 thành O’X3Y3Z3 ..................... 138 Hình 4.12. Đảo chiều trục X của hệ trục O’X3Y3Z3 để thu được hệ trục quan sát O’X’Y’Z’ ......................................................................... 139 Hình 4.13. Phép chiếu phối cảnh trong bài toán quan sát vật thể 3 chiều ...................................................................................................... 140 Hình 4.14. Minh họa tính chất của phép chiếu phối cảnh .............. 141 Hình 5.1. Minh họa công đoạn số hóa đối tượng 3 chiều ............... 145 Hình 5.2. Mô hình wireframe cho một nhân vật trong game .......... 146 Hình 5.3. Cách bố trí một phép chiếu phối cảnh đơn giản ............. 148 Hình 5.4. Giao diện chương trình WireFrameDemo ...................... 149 xv Hình 5.5. Menu ngữ cảnh cho phép tạo một class cho project ....... 149 Hình 5.6. Tạo một MFC Class ........................................................ 150 Hình 5.7. Thiết lập tham số cho lớp CWireFrame .......................... 150 Hình 5.8. Thực hiện Class Wizard với lớp CWireFrameDemoDlg để thêm các sự kiện .................................................................................... 157 Hình 5.9. Thêm các hàm xử lý sự kiện chuột trên cửa sổ chính của chương trình .......................................................................................... 157 Hình 5.10. Một số góc quan sát đối tượng được thiết lập thông qua các thao tác rê chuột .............................................................................. 159 Hình 5.11. Đối tượng được thể hiện với các kích cỡ khác nhau ..... 160 Hình 6.1. Hình ảnh của một số đối tượng 3 chiều thể hiện theo mô hình các mặt đa giác .............................................................................. 162 Hình 6.2. Minh họa việc số hóa thông tin vật thể 3 chiều theo mô hình các mặt đa giác .............................................................................. 163 Hình 6.3. Minh họa đối tượng theo mô hình các mặt đa giác: (a) Một nhân vật game theo mô hình các mặt đa giác cùng với phép ánh xạ hình ảnh bề mặt vật liệu lên các đa giác; (b) Một con Hổ với các mặt đa giác chưa tô màu; (c) Con Hổ với các đa giác được tô màu bằng phương pháp ánh xạ hình ảnh bề mặt vật liệu lên các đa giác .................................... 164 Hình 6.4. Minh họa sai lệch của giải thuật sắp xếp theo độ sâu khi hai mặt phẳng ở trong trạng thái cắt nhau ................................................... 168 Hình 6.5. Minh họa sai lệch của giải thuật sắp xếp theo độ sâu khi hai mặt đa giác ở trong trạng thái chồng lên nhau ...................................... 168 Hình 6.6. Minh họa phép kiểm tra phần kéo dài trên trục Z ........... 169 Hình 6.7. Hình ảnh 2 mặt đa giác đan chéo vào nhau .................... 170 Hình 6.8. Minh họa cho mô hình chọn lọc mặt sau ........................ 171 Hình 6.9. Kết quả thực nghiệm xử lý với hình cầu cấu tạo bởi 450 mặt đa giác theo giải thuật chọn lọc mặt sau: (a) Hình thể hiện các mặt quan sát được; (b) Hình thể hiện các mặt quan sát được và vector pháp tuyến của mỗi bề mặt đa giác (có xử lý vấn đề chiếu sáng).................. 172 Hình 6.10. Tạo lớp CObject_3D ..................................................... 173 xvi Hình 6.11. Hình ảnh thực nghiệm cài đặt giải thuật chọn lọc mặt sau ............................................................................................................... 183 Hình 6.12. Hình ảnh thực nghiệm cài đặt giải thuật chọn lọc mặt sau, với các đối tượng hình cầu, khủng long (Dinasaur) từ các file dữ liệu mô tả ............................................................................................................ 188 Hình 6.13. Hình minh họa cách xác định tích hữu hướng của hai vector và cách áp dụng .......................................................................... 190 Hình 6.14. Minh họa hình chiếu của 2 mặt phẳng lên mặt phẳng chiếu và phần chồng lấp (overlap) giữa chúng ............................................... 191 Hình 6.15. Minh họa cơ chế nội suy giao điểm trong giải thuật tô đa giác theo dòng quét (Scanline Algorithm) có tính đến nội suy độ sâu của tạo ảnh, để có thể áp dụng vào giải thuật vùng đệm độ sâu. Ở đây z1 chính là giá trị độ sâu của điểm P1, và P1 là tạo ảnh của P’1 ................. 193 Hình 6.16. Mô hình trực thăng (Hughes 500) được xử lý mặt khuất theo giải thuật vùng đệm độ sâu, có xử lý thêm vấn đề chiếu sáng nhằm tạo ra hình ảnh trung thực ..................................................................... 202 Hình 6.17. Mô hình trực thăng (Hughes 500) với một số mặt được lược bỏ để có thể quan sát được phần bên trong của đối tượng. Xử lý mặt khuất theo giải thuật vùng đệm độ sâu .................................................. 203 Hình 7.1. Sự khuếch tán của ánh sáng trên các bề mặt ................... 204 Hình 7.2. Sự phản xạ của ánh sáng trên các bề mặt ........................ 205 Hình 7.3. Mô phỏng hiện tượng phản chiếu trên bề mặt đối tượng với phần sáng trắng được đánh dấu bởi vòng màu đỏ ................................. 206 Hình 7.4. Các hình cầu được số hóa theo mô hình các mặt đa giác với số mặt lần lượt là (a) 200 mặt, (b) 450 mặt, (c) 16.200 mặt ................. 210 Hình 7.5. Minh họa kết quả xử lý tô bóng (a) Tô bóng thường, (b) Tô bóng theo giải thuật Phong.................................................................... 211 Hình 7.6. Vector pháp tuyến của các điểm trên một mặt cong ....... 211 Hình 7.7. Minh họa vector pháp tuyến tại các đỉnh của đa giác ..... 212 Hình 7.8. Minh họa các bước nội suy vector pháp tuyến cho từng điểm trên mặt đa giác ............................................................................ 213 xvii Hình 7.9. Hình ảnh thực nghiệm minh họa hình cầu 50 mặt không sử dụng phương pháp tô bóng cong (với chỉ một vector pháp tuyến cho mỗi bề mặt)................................................................................................... 213 Hình 7.10. Hình ảnh thực nghiệm minh họa hình cầu 50 mặt sử dụng phương pháp tô bóng Phong, với các vector pháp tuyến tại các đỉnh của bề mặt (hay đa giác) không cùng phương với vector pháp tuyến bề mặt mà có xu hướng ngả ra bên ngoài như mặt cong .................................. 214 Hình 7.11. Minh họa như Hình 7.10, nhưng được giản lược bớt một số mặt nhằm giúp quan sát rõ hơn các vector pháp tuyến tại đỉnh và bề mặt. Hình ảnh cho thấy các vector pháp tuyến tại đỉnh của bề mặt có xu hướng nghiêng ra bốn phía bên ngoài như của một mặt cong .............. 215 Hình 7.12. Minh họa đối tượng với các vector nút ......................... 215 Hình 7.13. Kết quả thực nghiệm cài đặt với giải thuật z-buffer kết hợp phương pháp tô bóng Phong (so sánh với Hình 6.9 để thấy sự khác biệt) ....................................................................................................... 227 Hình 7.14. Kết quả thực nghiệm so sánh giữa phương pháp tô bóng thường (a) và tô bóng Phong trên cùng một hình cầu lõm màu xám có 800 mặt đa giác ..................................................................................... 228 Hình 8.1. Thay đổi chất lượng hình ảnh với hàm ánh xạ có dạng đường cong Bezier bậc 3, cung cấp khả năng điều chỉnh hình dạng và độ cong của hàm ánh xạ một cách uyển chuyển và đơn giản .................... 229 Hình 8.2. Minh họa việc nội suy đường cong Bezier ..................... 232 Hình 8.3. Đường cong Bezier bậc 3 được vẽ bởi chương trình Paint của Microsoft. Các điểm tròn (màu đỏ) chính là các điểm kiểm soát của nó ........................................................................................................... 233 Hình 8.4. Một đường cong Spline được vẽ bởi chương trình AutoCad ............................................................................................................... 239 Hình 8.5. Đường cong Multi-Spline với các điểm điểu khiển (hay vector tiếp tuyến) giúp điều khiển độ cong ........................................... 239 xviii xix DANH SÁCH BẢNG BIỂU Bảng 3.1. Bảng quy tắc đánh mã ............................................................ 70 Bảng 4.1. Bảng ma trận của các phép biến đổi cơ bản trong không gian 2 chiều theo hệ tọa độ thuần nhất ............................. 121 Bảng 5.1. Danh sách thông tin lưu trữ theo mô hình WireFrame của chiếc ghế ......................................................................................... 145 Bảng 6.1. Bảng danh sách thông tin các đỉnh của đa giác theo mô hình các mặt đa giác ...................................................................................... 164 xx xxi DANH MỤC THUẬT NGỮ VÀ CHỮ VIẾT TẮT Ký hiệu và chữ viết tắt Giải nghĩa Affine 2D Không gian Affine 2 chiều Affine geometry Hình học Affine Back-Face Detection Giải thuật chọn lọc mặt sau Bezier/Bézier Tên của giải thuật phát sinh đường cong hay mặt cong trong lĩnh vực đồ họa Bresenham Tên của một số giải thuật dựng hình (đoạn thẳng, đường tròn, đường ellipse) trong giáo trình này B-spline Dạng tổng quát hóa của đường cong hay mặt cong Bezier Không gian màu, được xây dựng trên 3 màu cơ sở CMY Cohen Cyan (màu lục lam), Magenta (màu đỏ tươi), Yellow (màu vàng) Sutherland Tên giải thuật xén đoạn thẳng vào hình chữ nhật Ngữ cảnh (hay bối cảnh) thiết bị đồ họa, là một cấu DC (Device context) trúc định nghĩa một tập các đối tượng đồ họa và các thuộc tính liên quan của chúng, có 4 loại DC khác nhau trong MFC là: Display, Printer, Memory (or compatible), và Information Depth-Sorting Giải thuật người thợ sơn hay sắp xếp theo chiều sâu DIB Ảnh bitmap không phụ thuộc thiết bị Device-Independent Bitmap Flood Fill Chỉ quá trình tô màu theo giải thuật vết dầu loang Homogeneous Coordinates Tọa độ thuần nhất HSV Không gian màu, được xây dựng trên 3 thành phần cơ sở là H (Hue, sắc màu), S (Saturation, độ bão hòa) và xxii V (Value, thể hiện độ sáng) Liang-Barsky Tên một giải thuật xén đoạn thẳng vào hình chữ nhật Thư viện chứa các lớp C++ dùng để bao bọc các hàm MFC API của hệ điều hành Windows Microsoft Foundation Class Library MidPoint Tên của một giải thuật dựng đường tròn Pixel Điểm ảnh Polygon mesh model Phong Mô hình các mặt đa giác lưu trữ thông tin của đối tượng trong không gian 3 chiều Tên của một mô hình xử lý ánh sáng, giúp cho đối tượng 3 chiều có hình dáng cong có được hình ảnh bóng sáng sát với thực tế hơn các mô hình tạo bóng sáng khác trong lĩnh vực đồ họa RGB Không gian màu, được xây dựng trên 3 màu cơ sở Red, Green và Blue ScanLine Tên một thuật toán tô đa giác theo phương pháp quét dòng (scan line) trong giáo trình này Sutherland Hodgman Tên một giải thuật xén đa giác vào hình chữ nhật Một tổ chức tiêu chuẩn kỹ thuật cho chuẩn hiển thị VESA trên máy tính Video Electronics Standards Association WireFrame Mô hình khung dây lưu trữ thông tin về hình dáng (bộ khung) của đối tượng trong không gian 3 chiều Z-Buffer Giải thuật vùng đệm độ sâu xxiii Chương 1 CÁC YẾU TỐ CƠ SỞ CỦA ĐỒ HỌA Trong chương này sẽ trình bày các khái niệm về điểm ảnh, tọa độ điểm ảnh và ma trận điểm ảnh trên thiết bị đồ họa. Trình bày các giải thuật giúp dựng hình một cách hiệu quả đối với các đối tượng cơ bản như đoạn thẳng, hình tròn, hình ellipse. 1. CÁC KHÁI NIỆM CƠ BẢN 1.1. Thiết bị đồ họa và điểm ảnh Thiết bị đồ họa được hiểu là những phương tiện giúp chúng ta thể hiện được các hình ảnh thông qua sự điều khiển của máy tính. Từ đó, chúng ta có thể liệt kê một số thiết bị quen thuộc như màn hình máy tính, máy in, máy vẽ,… Hình 1.1 cho thấy khả năng hiển thị sinh động hình vẽ, chữ, hình ảnh thu được từ camera trên một màn hình máy tính của hãng Dell. Để có thể điều khiển được quá trình hiển thị thông tin (hình vẽ, chữ viết, hình ảnh,…) trên thiết bị đồ họa, chúng ta cần hiểu được tính chất cấu tạo của chúng. Trong chương này, chúng ta cần tìm hiểu một số khái niệm cơ bản liên quan đến quá trình dựng hình. Hình 1.1. Giao diện đồ họa windows 8 thể hiện trên màn hình của hãng Dell 1 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Mỗi thiết bị đồ họa có một mặt phẳng (hai chiều) được phân chia thành các dòng (rows) và các cột (columns). Giao của các dòng và các cột tạo nên các điểm ảnh, thuật ngữ tiếng Anh là Pixel. Kích thước của điểm ảnh phụ thuộc vào diện tích của bề mặt hiển thị và số điểm ảnh tối đa mà thiết bị điều khiển và hiện được trên bề mặt đó. Độ phân giải của thiết bị màn hình thường được biểu diễn bởi khả năng phân chia với số cột và số dòng cực đại. Ví dụ, màn hình LCD Full HD sẽ cho khả năng phân chia được 1920 cột và 1080 dòng, từ đó tạo nên hơn 2 triệu điểm ảnh. Các cột và các dòng được đánh chỉ số bắt đầu từ 0 tại vị trí góc trên bên trái như minh họa trong Hình 1.2. Từ đó, mỗi điểm ảnh được định danh thông qua một cặp chỉ số (x,y), trong đó x và y lần lượt là chỉ số cột và chỉ số dòng tạo nên điểm ảnh, cặp chỉ số này còn được gọi là tọa độ điểm ảnh trên thiết bị đồ họa. Dễ thấy rằng, tọa độ điểm ảnh trên thiết bị đồ họa luôn luôn phải là một cặp số nguyên dương hoặc bằng không. Các cặp giá trị tọa độ thực (không nguyên) hoặc âm không được chấp nhận, vì nó không giúp hệ thống xác định được điểm ảnh cần điều khiển. Hình 1.2. Minh họa việc hiển thị hình ảnh đồ họa trên thiết bị 1.2. Điểm và đoạn thẳng trong mặt phẳng Về mặt toán học, một đoạn thẳng bao gồm một tập vô hạn các điểm trong mặt phẳng với cặp tọa độ thực và không có kích thước (hay kích thước vô cùng bé). Khái niệm này có nhiều khác biệt với khái niệm Pixel trên thiết bị đồ họa mà người học cần nắm vững trước khi bắt đầu tìm hiểu bài toán dựng hình trong lĩnh vực đồ họa máy tính. Từ Hình 1.2 2 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài chúng ta có thể hiểu rằng quá trình dựng hình trên thiết bị đồ họa chính là quá trình xác định một tập các điểm ảnh (pixel) sao cho chúng có thể thể hiện được hình ảnh mà chúng ta mong muốn ở mức tốt nhất (tối ưu nhất) có thể. Ví dụ, đoạn thẳng màu đen được thể hiện bằng một tập 6 pixel liên tiếp nhau như minh họa trong Hình 1.2, mỗi pixel có một kích thước cụ thể phụ thuộc vào kích thước và độ phân giải của thiết bị. 2. CÁC GIẢI THUẬT VẼ ĐOẠN THẲNG Phương trình tổng quát của một đường thẳng được viết dưới dạng: y  ax  b Trong đó: - a là hệ số góc hay còn gọi là độ dốc, nó phản ánh mối tương quan giữa 2 biến số x và y. - b là khoảng chắn trên trục hoành. Phương trình đường thẳng đi qua 2 điểm A(xa, ya) và B(xb, yb) được viết dưới dạng: y y (1.1) x x a y y   a  b a Trong đó xa ≠ xb và ya ≠ yb. x x  b a (Khi xa = xb thì phương trình là x = xa, còn khi ya = yb thì phương trình là y = ya) Đặt b a b a x  x  x và y  y  y thì (1.1) trở thành  y  y y    x x   x a a x y   y a(1.2)  y  ax  b với    x a a b ax y    2.1. Vẽ đoạn thẳng dựa vào phương trình Khi biết phương trình của một đường, chúng ta hoàn toàn có thể vẽ được đường biểu diễn nhờ vào các tính toán trên phương trình. Ở đây, 3 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài đường mà chúng ta cần biểu diễn là một đoạn thẳng AB với A(xa,ya) và B(xb,yb). Phương trình biểu diễn được cho bởi (1.2) với     a b a b x x ,x , y y , y Quy trình dựng hình có thể tóm tắt như sau:  Nếu y  x , nghĩa là biến số x biến thiên nhanh hơn biến số y, lúc này để đảm bảo tính liên tục của các điểm vẽ chúng ta cho biến số x thay đổi tuần tự và tính biến số y qua phương trình. Cụ thể như sau: Cho x nhận các giá trị nguyên lần lượt từ xa đến xb, với mỗi giá trị x chúng ta thực hiện:  Tính y  ax  b thông qua phương trình.  Vẽ điểm (x, round(y)). Ở đây điểm trên đoạn thẳng có tọa độ là (x, y). Song chúng ta không thể vẽ điểm đó bởi giá trị y là một giá trị thực trong khi các hệ thống biểu diễn đồ họa chỉ có hữu hạn điểm và mỗi điểm có tọa độ nguyên. Từ đó chúng ta buộc phải minh họa cho điểm (x, y) thuộc đoạn thẳng thực bởi một điểm trên hệ thống thiết bị đồ họa gần với nó nhất, đó chính là điểm có tọa độ cột là x và dòng là giá trị làm tròn về số nguyên của y.  Ngược lại, nghĩa là biến số y biến thiên nhanh hơn biến số x, lúc này để đảm bảo tính liên tục của các điểm vẽ chúng ta cho biến số y thay đổi tuần tự và tính biến số x qua phương trình. Cụ thể như sau: Cho y nhận các giá trị nguyên lần lượt từ ya đến yb, với mỗi giá trị y chúng ta thực hiện:  x y b x  x  (hay a a y x x   )  Tính a  Vẽ điểm (round(x), y)  y y   y Ví dụ: Cho A(5, 4) đến B(10, 7) để vẽ đoạn thẳng AB chúng ta thực hiện các bước sau: Tính: x  xb  xa  10  5  5;y  yb  ya  7  4  34 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài   a   y  x  3 5 a a b ax y     1  Vì y  x , nên chúng ta cho x nhận các giá trị nguyên lần lượt từ xa đến xb, với mỗi giá trị x chúng ta cần thực hiện:  Tính y  ax  b thông qua phương trình.  Vẽ điểm (x, round(y)). 5 6 7 8 9 10 4 5 6 7 Hình 1.3. Ảnh minh họa một đoạn thẳng từ A(5,4) đến B(10,7) Cụ thể như sau: Khi x = xa = 5: y = ax+b = 4; Vẽ điểm (5,4) Khi x = 6: y = 23/5 = 4.6; Vẽ điểm (6,5) Khi x = 7: y = 26/5 = 5.2; Vẽ điểm (7,5) Khi x = 8: y = 29/5 = 5.8; Vẽ điểm (8,6) Khi x = 9: y = 32/5 = 6.4; Vẽ điểm (9,6) Khi x = 10: y = 7; Vẽ điểm (10,7) Kết quả chúng ta có hình vẽ đoạn thẳng AB có thể minh họa như trong Hình 1.3. 5 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài 2.2. Vẽ đoạn thẳng dựa vào giải thuật Bresenham Mục 2.1 đã đưa ra quy trình để vẽ một đoạn thẳng AB bất kỳ trên thiết bị đồ họa. Tuy nhiên, phương pháp tính toán còn chưa thật sự hiệu quả. Cụ thể, tại mỗi bước lặp để tìm ra được tọa độ của một điểm vẽ, chúng ta cần phải tính 1 phép nhân và 1 phép cộng trên trường số thực, cùng với một phép tính làm tròn (round) số thực về số nguyên. Cũng với cách tiếp cận trên, song giải thuật Bresenham hướng tới một sự phân tích bài toán sâu sắc hơn để đi đến một quy trình ít tính toán hơn. Giả thiết đầu tiên mà giải thuật Bresenham đặt ra là hệ số góc của đoạn thẳng a [0,1], các trường hợp còn lại của hệ số góc như a (1,  ); a [1, 0); hay a  (; 1) có thể được quy về trường hợp đoạn thẳng có hệ số góc a [0,1] thông qua các phép lấy đối xứng, quy trình xử lý cụ thể đối với các đoạn thẳng có hệ số góc a [0,1] sẽ được bàn thảo và hướng dẫn tại mục 2.2.3. Từ giả thiết đặt ra là hệ số góc của đoạn thẳng a [0,1], chúng ta có thể suy ra rằng, trên toàn bộ đoạn thẳng tham số x luôn luôn biến thiên nhanh hơn tham số y. Từ đó, đưa đến quy trình: Cho x nhận các giá trị nguyên lần lượt từ xa đến xb, với mỗi giá trị x chúng ta cần phải tìm ra một giá trị y nguyên để (x,y) chính là tọa độ của điểm cần minh họa trên thiết bị. Và điểm mấu chốt ở đây là việc tìm ra giá trị y phải thông qua ít phép tính toán hơn quy trình đã trình bày ở mục 2.1. Giả thiết với hai điểm đầu mút A(xa, ya) và B(xb, yb) có tọa độ nguyên và xa < xb (nếu cần thì hoán đổi hai đầu mút A và B để thỏa mãn giải thiết xa < xb ). Rõ ràng, điểm ảnh đầu tiên cần biểu diễn trên thiết bị chính là điểm A có tọa độ (xa, ya). Nếu gọi điểm ảnh được lựa chọn đầu tiên trong quy trình là (x0, y0) thì: (x0, y0) = (xa, ya) Theo lập luận quy nạp:  Giả thiết rằng đến bước thứ i chúng ta đã chọn được điểm ảnh thứ i, hay nói cách khác là điểm ảnh được chọn ở bước thứ i với tên gọi là (xi, yi) đã được xác định giá trị. 6 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài  Vậy đến bước tiếp theo, bước thứ i+1, chúng ta sẽ chọn điểm ảnh nào? Nói cách khác là điểm ảnh được chọn ở bước thứ (i+1) với tên gọi (xi+1, yi+1) sẽ được xác định các giá trị ra sao? Chú ý: xi, yi là tên gọi của tọa độ điểm ảnh thứ i, ví dụ (x0, y0) là tên gọi của điểm ảnh được lựa chọn đầu tiên (i = 0) và có giá trị (xa, ya) Để trả lời câu hỏi này chúng ta cần dựa vào một số lập luận sau đây: Như đã trình bày thì điểm ảnh chọn thứ i+1 sẽ phải có hoành độ x bằng hoành độ của điểm ảnh được lựa chọn trước đó cộng thêm 1: Hay xi1  xi 1 Gọi M là điểm thuộc AB sao cho xM  xi1  xi 1 Thì: yM  axM  b  a(xi 1)  b  (axi  b)  a Vậy điểm tiếp theo thuộc đoạn thẳng mà chúng ta cần tìm điểm ảnh minh họa trên thiết bị là M( xi 1, (axi  b)  a ). Câu hỏi đặt ra là chúng ta sẽ chọn điểm nào trong 2 điểm ảnh P( xi 1,i y ) và Q( xi 1, yi 1) để minh họa cho M trên thiết bị đồ họa (xem Hình 1.4). xi xi+1 P yi yi+1 I M d2 d1 Q Hình 1.4. Minh họa việc chọn lựa điểm P hay Q dựa vào các tham số Để trả lời câu hỏi này chúng ta cần xem xét một biểu thức trung gian: Đặt ( ) 1 M P d  y  y và ( ) 2 Q M d  y  y 7 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Xét biểu thức:   y y  1 2( ) ( ) 2 ( ) 2P Q d d y y y y y y y y          2 M P Q M M P Q M Nếu gọi I là trung điểm của QP thì:   M I d  d  2 y  y 1 2 Rõ ràng là:  Nếu 0 d1  d2  dẫn đến M I y  y , suy ra P gần điểm M hơn Q, vậy chúng ta sẽ chọn điểm ảnh P làm điểm minh họa cho điểm M thuộc đường thẳng trên thiết bị đồ họa.  Nếu 0 d1  d2  dẫn đến M I y  y , suy ra Q gần điểm M hơn P, vậy chúng ta sẽ chọn điểm ảnh Q làm điểm minh họa cho M trên thiết bị đồ họa.  Nếu 0 d1  d2  dẫn đến M I y  y , suy ra khả năng lựa chọn P và Q là như nhau, song chúng ta phải quyết định chọn một điểm ảnh. Trong tình huống này giải thuật quy định chọn điểm Q. Vậy để tìm được điểm minh họa tiếp theo chúng ta cần xét dấu của biểu thức 1 2 d  d . Tuy nhiên, chúng ta thấy biểu thức 1 2 d  d còn khá phức tạp, và phải thực hiện tính toán trên trường số thực do trong đó có xuất hiện phép chia: yM  (axi  b)  a  (axi  (axa  ya))  a (1.3)  y  y x  x y    y  x i a a   x x Để tránh tính biểu thức 1 2 d  d trên trường số thực, người ta hướng tới một biểu thức tương đương về dấu đó là: ( ) d1 d2 P x i    Việc đưa x vào nhằm loại bỏ mẫu số trong biểu thức 1 2 d  d , từ đó thu được biểu thức Pi tính trên trường số nguyên. Thật vậy: P x d d x y y y x y y y             ( ) (2 ( )) (2 ( 1)) 1 2 i M P Q M i i (2 2 1) 2 2           x y y xy xy x M i M i 8 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Thay yM bởi giá trị ở (1.3) chúng ta được: P yx yx xy y xy x i  2 i  2 a  2 a  2  2 i   yx xy yx xy y x  2 i  2 i  2 a  2 a  2  (1.4) Chúng ta thấy, biểu thức Pi được xác lập từ tọa độ của điểm chọn thứ i là (xi, yi). Vậy Pi1 sẽ được xác lập từ điểm chọn thứ i+1 là (xi+1, yi+1) như sau: P yx xy yx xy y x i1  2 i1  2 i1  2 a  2 a  2   (1.5) Vì dấu của Pi và dấu của ( ) 1 2 d  d là tương đương nên có thể tóm tắt quy tắc chọn điểm ảnh tiếp theo như sau:  Nếu Pi  0 : Thì chọn điểm ảnh P làm điểm minh họa cho M trên thiết bị đồ họa. Hay nói cách khác là điểm ảnh chọn thứ i+1 là (xi+1, yi+1) sẽ có giá trị bằng P. Nghĩa là (xi+1, yi+1) = (xi + 1, yi), từ đó thay vào công thức (1.5), chúng ta có: P y x xy yx xy y x P y i1  2 ( i 1)  2 i  2 a  2 a  2    i  2  Nếu Pi  0 : Thì chọn điểm Q là điểm minh họa cho M trên thiết bị đồ họa. Hay nói cách khác là điểm chọn thứ i+1 là (xi+1, yi+1) sẽ có giá trị bằng Q. Nghĩa là: (xi+1, yi+1) = (xi + 1, yi + 1), từ đó thay vào công thức (1.5) chúng ta có: P y x x y yx xy y x                2 ( 1) 2 ( 1) 2 2 2 1 i i i a a 2 2      P y x i Khi i = 0, ta có (x0, y0) = (xa, ya) thay vào (1.4) chúng ta có: P yx yx xy y xy x y x 0  2 0  2 a  2 a  2  2 0    2   Từ đây, chúng ta thấy được quy trình chọn ra các điểm trên thiết bị để minh họa cho đoạn thẳng AB theo giải thuật Bresenham như sau:  Điểm chọn đầu tiên (i = 0) là (x0, y0) = (xa, ya) và giá trị P  2y  x 0. 9 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài  Dựa vào giá trị của P0 là âm hay dương mà chúng ta lại chọn được điểm tiếp theo (x1,y1) và tính được giá trị P1.  Dựa vào giá trị của P1 là âm hay dương mà chúng ta lại chọn được điểm tiếp theo (x2,y2) và tính được giá trị P2.  Cứ như vậy, chúng ta tìm ra được tập các điểm trên thiết bị đồ họa để minh họa cho đoạn thẳng AB. 2.2.1. Tóm tắt giải thuật Bresenham Đầu vào: Tọa độ (xa, ya) và (xb, yb) của đoạn thẳng AB thỏa mãn giả thiết hệ số góc thuộc đoạn [0,1] và xa < xb. Đầu ra: Vẽ các điểm ảnh nhằm thể hiện hình ảnh đoạn thẳng AB trên mặt phẳng thiết bị đồ họa.  Bước 1: (Bước khởi động, tính toán các giá trị ban đầu) ∆x = xb – xa ; ∆y = yb – ya; Const1 = 2∆y; Const2 = 2∆y – 2∆x P0 = 2∆y – ∆x; (x0, y0) = (xa, ya) Vẽ điểm (x0, y0)  Bước 2: (Bước lặp, thực hiện tính các giá trị điểm ảnh) Với mỗi giá trị i (i = 0, 1, 2,…) chúng ta xét dấu Pi  Nếu Pi <0: Thì xác định điểm tiếp theo là: (xi+1, yi+1) = (xi + 1, yi) Pi+1 = Pi + Const1  Ngược lại (tức Pi ≥ 0): Thì xác định điểm tiếp theo là: (xi+1, yi+1) = (xi + 1, yi + 1) Pi+1 = Pi + Const2 Vẽ điểm (xi+1, yi+1) vừa tìm được  Bước 3: (Xác định điều kiện lặp) Lặp lại bước 2 với những giá trị i tiếp theo, cho đến khi điểm tìm được trùng với B, nghĩa là xi+1 = xb thì giải thuật kết thúc. 10 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài 2.2.2. Ví dụ Cho đoạn thẳng AB với A(5,6) và B(10,10). Sử dụng giải thuật Bresenham, chúng ta có thể tìm được các điểm ảnh cần vẽ để biểu diễn đoạn AB trên màn hình như sau:  Bước 1: ∆x = 10 – 5 = 5; ∆y = 10 – 6 = 4; Const1 = 2∆y = 8; Const2 = 2∆y – 2∆x = 8 – 10 = –2; P0 = 2∆y – ∆x = 8 – 5 = 3; (x0, y0) = (xa , ya) = (5, 6) Vẽ điểm (x0, y0)  Bước 2: i = 0: Ta có P0 = 3 ≥ 0 nên: (x1, y1) = (x0 +1, y0 +1) = (6, 7) P1 = P0 + Const2 = 3 + (–2) = 1 Vẽ điểm (x1, y1) = (6, 7) i = 1: Ta có P1 = 1 ≥ 0 nên: (x2, y2) = (x1 + 1, y1 + 1) = (7, 8) P2 = P1 + Const2 = 1 + (–2) = –1 Vẽ điểm (x2, y2) = (7, 8) i = 2: Ta có P2 = –1 < 0 nên: (x3, y3) = (x2 + 1, y2) = (8, 8) P3 = P2 + Const1 = –1 + 8 = 7 Vẽ điểm (x3, y3) = (8, 8) i = 3: Ta có P3 = 7 ≥ 0 nên: 11 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài (x4, y4) = (x3 + 1, y3 + 1) = (9, 9) P4 = P3 + Const2 = 7 + (–2) = 5 Vẽ điểm (x4, y4) = (9, 9) i = 4: Ta có P4 = 5 ≥ 0 nên: (x5, y5) = (x4 + 1, y4 + 1) = (10, 10) P5 = P4 + Const2 = 5 + (–2) = 3 Vẽ điểm (x5, y5) = (10, 10) Vì x5 = xb = 10, nên kết thúc vòng lặp và cũng là kết thúc giải thuật. Hình vẽ minh họa (xem Hình 1.5) 5 6 7 8 9 10 6 7 8 9 10 Hình 1.5. Minh họa đoạn thẳng được vẽ trên thiết bị đồ họa. Các Pixel vuông màu đỏ là hình ảnh thể hiện của đoạn thẳng AB trên màn hình 2.2.3. Hướng dẫn cho các trường hợp hệ số góc ngoài đoạn [0, 1] Giả sử cho A(0, 50), B(100, 10), để dựng đoạn thẳng AB chúng ta cần tiến hành một số phân tích: x = xb – xa = 100 – 0 = 100 y = yb – ya = 10 – 50 = –40 12 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Suy ra hệ số góc a = y/x = –0.4  [–1, 0] Lúc này, ta cần lấy đối xứng của AB qua trục OX để được CD với C(0, –50) D(100, –10), nên xét trên đoạn thẳng CD chúng ta có: x = xd – xc = 100 – 0 = 100 y = yd – yc = (–10) – (–50) = 40 Suy ra hệ số góc a = y/x = 0.4  [1, 0] thỏa mãn điều kiện của giải thuật Bresenham. Từ đó, chúng ta có thể áp dụng giải thuật Bresenham để tính toán ra các điểm ảnh cần vẽ trên CD, nhưng chúng ta sẽ không vẽ nó (vì mục đích chúng ta là dựng hình AB) mà lại lấy đối xứng qua trục OX (tức đối xứng ngược lại với lúc đầu) rồi mới vẽ, thì lúc này các điểm ảnh vẽ ra sẽ là hình ảnh của đoạn thẳng AB. Như thế, CD chỉ đóng vai trò trung gian nhằm áp dụng được giải thuật còn kết quả sau cùng chúng ta thu được vẫn là hình ảnh minh họa cho đoạn AB. Áp dụng tương tự: - Trường hợp hệ số góc a (1,) , lúc này chúng ta cần lấy đối xứng qua đường phân giác của góc phần tư thứ nhất để hệ số góc được quy về [0, 1]. - Trường hợp hệ số góc a  (,1), lúc này chúng ta cần lấy 2 lần đối xứng. Đối xứng qua OX rồi tiếp đến đối xứng qua đường phân giác. Xét điểm M(x,y). Đối xứng qua OX chúng ta được tọa độ mới là (x, –y). Tiếp đến lấy đối xứng qua tia phân giác góc phần tư thứ nhất chúng ta được (–y, x). Hay nói cụ thể hơn là với một đoạn thẳng đầu vào có tọa độ là A(xa, ya) và B(xb, yb) thì đoạn thẳng trung gian của nó sẽ là CD với C(–ya, xa) và D(–yb, xb). 2.3. Môi trường thực nghiệm và các bước thiết lập cơ bản Chúng tôi đề xuất sinh viên thực hành thực nghiệm trên môi trường Microsoft Visual C++ sử dụng thư viện MFC (Microsoft Foundation Class Library) để có thể dễ dàng tương tác sâu với thiết bị đồ họa và mang lại năng lực thực thi mạnh mẽ. Đồng thời, nó cũng phù hợp với nền tảng kiến thức lập trình hướng đối tượng và kỹ năng lập trình với ngôn ngữ C++ mà sinh viên đã được trang bị trước khi đến với môn học này. 13 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Tuy nhiên, sinh viên cũng cần phải trang bị và trau dồi thêm khả năng lập trình xử lý sự kiện trên giao diện đồ họa của Windows và một số kiến thức cơ bản về MFC. Bài thực nghiệm số 1: Dưới đây là các bước hướng dẫn để sinh viên có thể tiếp cận với quy trình xây dựng một ứng dụng đồ họa cơ bản, ứng dụng này bước đầu đặt nền tảng cho quá trình thực hành thực nghiệm, là quá trình quan trọng giúp người học có thể kiểm tra tính đúng đắn, tính thực tiễn của các lý thuyết đã được học thông qua kết quả thực nghiệm và các phân tích đánh giá, mang lại hiểu biết sâu sắc và đa chiều trên thực tiễn.  Bước 1: Tạo một dự án (project) mới trong Microsoft Visual Studio sử dụng ngôn ngữ Visual C++ và thư viện MFC: 1 3 5 2 4 Hình 1.6. Các bước tạo một project phục vụ cho quá trình thực nghiệm Khi hộp thoại MFC Application Wizard xuất hiện, cần bấm nút Next để chuyển đến mục Application Type. Tiếp đến click chọn mục “Dialog based” như hình dưới đây, rồi cuối cùng bấm nút Finish để kết thúc quá trình tạo khung ứng dụng. 14 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài 7 8 Hình 1.7. Giao diện MFC Application Wizard giúp chọn lựa kiểu ứng dụng Kết thúc quá trình trên, Microsoft sẽ tạo ra một khung ứng dụng (template / bản mẫu) với các thành phần và giao diện như hình dưới đây: Cửa sổ giao diện Project với các file mã nguồn, file tài nguyên,… Hình 1.8. Hình ảnh của một ứng dụng dạng dialog based làm khuôn mẫu xây dựng các ứng dụng thực nghiệm đồ họa máy tính 15 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài  Bước 2: Thiết kế lại giao diện Các edit control để nhập số liệu Button control dùng để thực hiện lệnh vẽ với thuộc tính ID là: IDC_BUTTON1 Hình 1.9. Thiết kế giao diện chương trình LineDemo Tùy thuộc vào yêu cầu của bài toán mà chúng ta có những giải pháp thiết kế giao diện khác nhau. Hình 1.9 là thiết kế đơn giản cho bài toán dựng đoạn thẳng AB với các tọa độ được nhập vào thông qua các hộp nhập liệu (edit control).  Bước 3: Tạo các biến nhận dữ liệu từ các edit control Click chuột phải vào edit control cần tạo biến nhận dữ liệu, tiếp đến chọn mục “Add variable…” trong menu ngữ cảnh. Hình 1.10. Menu ngữ cảnh trong quá trình tạo biến nhận dữ liệu từ edit control 16 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Sau đó, cần thiết lập thuộc tính Category là Value, kế đến là tên biến và các thông số cơ bản khác như trong Hình 1.11. Thực hiện tương tự với các edit control còn lại để tạo các biến nhận dữ liệu tọa độ của đoạn thẳng AB. Các biến cần tạo gồm: xa, ya, xb, yb kiểu số nguyên. Hình 1.11. Đặt tên và xác định các thông số cho biến  Bước 4: Thêm hàm BresLine vào lớp CLineDemoDlg với chức năng tính toán theo giải thuật Bresenham và vẽ hình lên cửa sổ giao diện. Hình 1.12. Các bước để thêm một hàm xử lý vào lớp CLineDemoDlg Đầu tiên chúng ta click vào tab “Class View”, tiếp đến click chuột phải vào mục CLineDemoDlg, rồi chọn mục AddAdd Function… 17 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Hình 1.13. Xác định tên hàm và các tham số Sau cùng, cần xác định tên hàm, kiểu trả về của hàm và danh sách các tham số như trong Hình 1.13. Sau khi hoàn thành cần bấm nút Finish để chuyển sang công đoạn viết mã lệnh cho hàm.  Bước 5: Viết mã lệnh thực thi cho hàm BresLine: void CLineDemoDlg::BresLine(int xa, int ya, int xb, int yb) { /* Giả thiết đầu vào thỏa mãn hai điều kiện của giải thuật Bresenham là hệ số góc a thuộc [0, 1] và xa < xb. Từ đó, chúng ta chỉ cần thực hiện theo đúng các bước đã được nêu ra trong giải thuật. Để giải quyết với đầu vào tổng quát, sinh viên cần tham khảo thêm phần hướng dẫn xử lý cho các tình huống hệ số góc a ngoài đoạn [0, 1]. Phần này được xem như một yêu cầu nâng cấp mã lệnh mà sinh viên cần thực hiện */ /* Lấy con trỏ quản lý đối tượng Device Context của cửa sổ giao diện chương trình để có thể tiến hành vẽ các điểm ảnh trên cửa sổ */ CDC *p_DC = this->GetDC(); COLORREF Color = RGB(255, 0, 0); //Màu đỏ //Thực hiện Bước 0: 18 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài int Dx = xb - xa, Dy = yb - ya; int P = 2 * Dy - Dx, Const1 = 2 * Dy, Const2 = 2 * Dy - 2 * Dx; int x = xa, y = ya; p_DC->SetPixel(x, y, Color); // Thực hiện Bước 2 (bước lặp): while (x < xb) // Điều kiện dừng (Bước 3) { x++; if (P < 0) { P += Const1; } else { y++; P += Const2; } p_DC->SetPixel(x, y, Color); } }  Bước 6: Bấm DoubleClick vào nút “Vẽ đoạn thẳng” (tức nút có ID là IDC_BUTTON1) để chương trình MS Visual Studio tự động thêm vào một hàm đáp ứng sự kiện khi người sử dụng click (hay bấm chọn) vào nút “Vẽ đoạn thẳng” có dạng: void CLineDemoDlg::OnBnClickedButton1() {} Tiếp đến chúng ta cần viết mã lệnh cho hàm này như sau: void CLineDemoDlg::OnBnClickedButton1() { /* Gọi lệnh thực thi việc cập nhật dữ liệu vào các biến xa, ya, xb, yb */ UpdateData(true); // Gọi hàm vẽ đoạn thẳng theo giải thuật Bresenham đã cài đặt BresLine(xa, ya, xb, yb); } 19 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài  Bước 7: Biên dịch và thực thi chương trình, nhập tọa độ của đoạn thẳng AB vào các edit control, rồi click nút “Vẽ đoạn thẳng” để thấy được hình ảnh biểu diễn cho đoạn thẳng AB được hiển thị trên cửa sổ như hình dưới đây: Hình 1.14. Kết quả thực thi chương trình với hình ảnh biểu diễn cho một đoạn thẳng AB được tính toán theo giải thuật Bresenham 2.4. So sánh đánh giá hai giải thuật dựng đường thẳng Sau đây, chúng ta sẽ tiến hành so sánh và đánh giá hai giải thuật dựng đoạn thẳng trên một số tiêu chí quan trọng: 1. Yêu cầu về phần cứng thực thi tính toán Rõ ràng rằng, hai giải thuật có hai yêu cầu khác nhau về phần cứng thực thi tính toán. Cụ thể:  Giải thuật vẽ đoạn thẳng dựa vào phương trình: Yêu cầu tính toán với kiểu dữ liệu số thực, vì vậy một hệ thống đồ họa nếu sử dụng giải thuật này sẽ cần có vi xử lý hỗ trợ tính toán số thực, yêu cầu này không phải khi nào cũng được đáp ứng. Thực tế cho thấy, rất nhiều hệ thống thiết bị trong công nghiệp cho đến giải trí và gia dụng có màn hình hiển thị đồ họa cấp thấp (độ phân giải thấp với nhiệm vụ hiển thị các thông tin đơn 20 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài giản), được xây dựng trên các vi xử lý số nguyên 8-bit, 16-bit, hay 32-bit nhằm đáp ứng yêu cầu về giá thành. Do đó, các hệ thống này không thể đáp ứng được yêu cầu của giải thuật, hoặc chỉ đáp ứng miễn cưỡng theo một cách phức tạp hơn đó là xây dựng các modul phần mềm hỗ trợ xử lý số thực dựa trên các lệnh tính toán số nguyên. Ngay cả vi xử lý máy tính 16 bit của hãng Intel có mã hiệu là 8086 được thiết kế trong giai đoạn 1976 - 1978, và trang bị trên các máy IBM PC, có kiến trúc bộ xử lý số học và logic (Arithmetic Logic Unit, hay ALU) chỉ thực hiện các tính toán trên trường số nguyên. Vì vậy, các tính toán số thực trên máy tính giai đoạn đó phải được thực hiện thông qua giải pháp phần mềm, mất nhiều thời gian thực thi.  Giải thuật Bresenham: Chỉ yêu cầu các tính toán căn bản trên trường số nguyên gồm: So sánh, cộng, trừ, và phép dịch bit để thực hiện phép nhân 2. Những yêu cầu tính toán này là hết sức căn bản và có thể thực hiện được trên hầu hết các hệ thống vi xử lý. 2. Số lệnh máy cần thực hiện để tính toán tọa độ các điểm ảnh Giải thuật vẽ đoạn thẳng dựa vào phương trình Giải thuật vẽ đoạn thẳng Bresenham ∆x = xb – xa Tính toán trong phần khởi động ∆x = xb – xa ∆y = yb – ya a = ∆y / ∆y b = -a * xa + ya x = xa y = ya ∆y = yb – ya Const1 = 2∆y Const2 = 2∆y – 2∆x P = 2∆y – ∆x x = xa y = ya Nhận xét: Số lệnh máy cần thực hiện ở giai đoạn khởi động của cả hai giải thuật không khác nhau đáng kể. Mặt khác, do bước khởi động chỉ thực hiện một lần, nên góp phần không đáng kể vào chi phí thời gian tính toán của toàn bộ quy trình thực thi của giải thuật. 21 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Tính toán trong vòng lặp để thu được tọa độ một điểm ảnh minh họa x = x +1 y = int (a.x + b + 0.5)  Tổng cộng: - 3 lệnh cộng số thực - 1 lệnh nhân số thực - 1 lệnh lấy phần nguyên của số thực x = x +1 Nếu P < 0: P = P + Const1 Ngược lại: y = y + 1 P = P + Const2  Tổng cộng trong tình huống xấu nhất: - 3 lệnh cộng số nguyên - 1 lệnh chuyển hướng thực thi (hay lệnh nhảy)  Tổng cộng trong tình huống tốt nhất: - 2 lệnh cộng số nguyên - 1 lệnh chuyển hướng thực thi (hay lệnh nhảy) Nhận xét: Ở đây, chúng ta chỉ so sánh mang tính tương đối, vì 2 giải thuật có yêu cầu nền tảng tính toán cùng các lệnh máy khác nhau, nên sẽ rất khác nhau khi thực hiện trên các nền tảng kiến trúc vi xử lý khác nhau. Nhưng nhìn chung, giải thuật dựa vào phương trình ngoài yêu cầu phải thực hiện trên dữ liệu số thực, nó còn nhiều hơn một lệnh nhân số thực, vì thế khi đoạn thẳng càng dài, kéo theo số lần lặp càng lớn, thì hiệu quả cải thiện về thời gian tính toán của giải thuật Bresenham càng cao. Từ những so sánh và đánh giá trên cho thấy, chúng ta nên lựa chọn giải thuật Bresenham để cài đặt trên các hệ thống đồ họa để mang lại hiệu quả thực thi tốt nhất, còn giải thuật dựng đường tròn dựa vào phương trình chỉ mang tính tham khảo và so sánh. 22 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài 3. CÁC GIẢI THUẬT VẼ ĐƯỜNG TRÒN A B -R O +R Hình 1.15. Đồ thị toán học của đường tròn tâm O bán kính R Phương trình đường tròn tâm O (gốc tọa độ) bán kính R (nguyên) là: X2 + Y2 = R2 Trong mục này, chúng ta chỉ cần tìm phương pháp vẽ đường tròn có tâm tại gốc tọa độ. Bởi vì, nếu chúng ta vẽ được đường tròn có tâm tại gốc, thì bằng cách thêm vào phép tịnh tiến chúng ta sẽ thu được đường tròn có tâm ở vị trí bất kỳ. Dễ thấy, để vẽ được đường tròn tâm gốc tọa độ chúng ta chỉ cần tìm phương pháp vẽ cung một phần tám AB như trên Hình 1.15, kết hợp với các phép lấy đối xứng chúng ta sẽ có các phần còn lại của đường tròn. Với cung AB thì rõ ràng độ dốc của nó thuộc đoạn [-1, 0]. Điều này chúng ta có thể dễ dàng thấy qua góc của tiếp tuyến với cung AB hay qua đạo hàm phương trình biểu diễn cung AB. Vì cung AB có độ dốc trong khoảng [-1, 0], nên chúng ta suy ra rằng trên toàn bộ cung AB khi biến số x tăng thì biến số y giảm, và tốc độ thay đổi của y chậm hơn của x. Từ đây, chúng ta có thể đề ra một quy trình dựng cung AB nhằm đảm bảo tính liên tục (hay nối tiếp, liền kề) của các pixel được chọn, cụ thể:  Cho biến số x nhận lần lượt các giá trị nguyên từ xa đến xb. Với mỗi giá trị x, chúng ta thực hiện:  Tìm giá trị y nguyên tương ứng để pixel có tọa độ (x,y) sẽ là điểm 23 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài gần nhất với điểm có tọa độ thực (x, ycircle) vốn thuộc đường tròn về mặt toán học.  Vẽ pixel (x,y) tìm được và các điểm đối xứng của nó để có được đường tròn. Trong mục này, chúng ta sẽ đi tìm hiểu 2 giải thuật cho phép dựng đường tròn (thực chất là dựng cung AB và các đối xứng của nó) một cách hiệu quả về mặt tốc độ tính toán. 3.1. Giải thuật vẽ đường tròn MidPoint Giải thuật MidPoint hay còn gọi là giải thuật xét điểm giữa.  Điểm ảnh (hay Pixel) đầu tiên được chọn để dựng cung AB sẽ chính là điểm A(0,R), nghĩa là điểm chọn đầu tiên của quy trình dựng hình với tên gọi (x0,y0) sẽ có tọa độ (0,R). Nói cách khác, chúng ta có: (x0,y0) = (0,R)  Giả sử ở bước thứ i, chúng ta đã xác định được giá trị điểm ảnh cần vẽ của bước này là (xi,yi), hay nói cách khác là điểm vẽ thứ i là (xi,yi) đã được xác định giá trị. Câu hỏi đặt ra là đến bước thứ i+1, chúng ta sẽ chọn điểm vẽ thứ (i+1) như thế nào? Hay nói theo một cách khác là điểm chọn thứ (i+1) với tên gọi là (xi+1,yi+1) có giá trị bằng bao nhiêu? xi xi+1Q yi-1 yi I P Cung AB Hình 1.16. Minh họa việc chọn lựa điểm P hay Q dựa vào các tham số khi dựng cung AB trên màn hình 24 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Vì điểm ảnh chọn lựa tiếp theo của quy trình dựng hình phải được thực hiện trên cơ sở tuân thủ quy tắc đã đề ra ở phần đầu mục 3, nên hoành độ x của nó phải tăng một giá trị so với giá trị của điểm chọn trước đó, hay nói cách khác là: xi1  xi 1 Mặt khác, trên cung AB (xem Hình 1.16) khi x tăng thì y giảm, và tốc độ thay đổi của y chậm hơn của x, nên với giá trị x tăng 1 đơn vị (hay một cột) thì giá trị y sẽ thay đổi một lượng ∆y với ràng buộc -1≤ ∆y ≤0. Mà điểm ảnh chọn bước trước là (xi,yi) nên điểm ảnh chọn ở bước tiếp theo chỉ có thể là một trong hai điểm ảnh P(xi+1, yi) và Q(xi+1, yi –1). Để quyết định được điểm chọn là P hay Q, chúng ta hướng đến một biểu thức mà dấu của nó cho phép chúng ta ra quyết định chọn điểm nào.  > 0 K M  < 0 R Hình 1.17. Minh họa hàm circle f Trước hết, chúng ta xét hàm (xem Hình 1.17): 2 2 2 fcircle (x, y)  x  y  R Với một điểm M(x,y) thì rõ ràng chúng ta có:  ƒcircle(M) = ƒ(x,y) = x2 + y2 – R2 < 0 khi và chỉ khi điểm M nằm trong đường tròn (tâm O bán kính R).  ƒcircle(M) = ƒ(x,y) = x2 + y2 – R2 > 0 khi và chỉ khi điểm M nằm ngoài đường tròn (tâm O bán kính R).  ƒcircle(M) = ƒ(x,y) = x2 + y2 – R2 = 0 khi và chỉ khi điểm M nằm trên đường tròn. 25 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Từ kết quả trên, nếu chúng ta gọi I là trung điểm của đoạn thẳng PQ thì tọa độ của I là (xi + 1,yi – 0.5) và: Đặt Pi = ƒcircle(I) = ƒcircle (xi +1,yi – 0.5) = (xi +1)2 + (yi – 0.5)2 – R2(1.6)  Khi Pi = ƒcircle(I) < 0: Thì điểm I nằm trong đường tròn tâm O bán kính R, vì thế điểm P sẽ gần với đường tròn hơn điểm Q. Suy ra điểm P sẽ được chọn làm điểm ảnh biểu diễn cho cung AB ở bước thứ i+1.  Khi Pi = ƒcircle(I) > 0: Thì điểm I nằm ngoài đường tròn, vì thế điểm Q sẽ gần với đường tròn hơn điểm P. Suy ra điểm Q sẽ được chọn làm điểm ảnh biểu diễn cho cung AB ở bước thứ i+1.  Khi Pi = ƒcircle(I) = 0: Thì điểm I nằm trên đường tròn, suy ra khả năng lựa chọn P và Q là như nhau, song chúng ta phải quyết định chọn một điểm. Trong tình huống này giải thuật quy định chọn điểm Q. Từ đây chúng ta thấy, dấu của biểu thức Pi có thể được sử dụng như một hàm ra quyết định cho việc lựa chọn điểm ảnh điểm tiếp trong quá trình dựng hình. Để giải thuật được đơn giản người ta tối ưu hóa việc tính Pi theo công thức truy hồi, cụ thể: Pi1 = ƒ(xi+1 +1, yi+1 – 0.5) = (xi+1 + 1)2 + (yi+1 – 0.5)2 – R2(1.7) Dấu của Pi sẽ quyết định giá trị Pi1 như sau:  Nếu Pi < 0: Thì điểm chọn tiếp theo là P(xi +1,yi), điều đó có nghĩa là (xi+1,yi+1) = (xi +1,yi). Thay vào (1.7) chúng ta thu được: Pi1 = (xi + 1 + 1)2 + (yi – 0.5)2 – R2 = Pi + 2xi + 3  Nếu Pi ≥ 0: Thì điểm chọn tiếp theo là Q(xi + 1,yi – 1), điều đó có nghĩa là (xi+1, yi+1) = (xi + 1, yi – 1). Thay vào (1.7) chúng ta được: Pi1 = (xi + 1 + 1)2 + (yi – 1 – 0.5)2 – R2 = Pi + 2(xi – yi) + 5 26 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Đầu tiên, chúng ta chọn điểm A(0,R), nghĩa là (x0,y0) = (0,R), thay vào (1.6) chúng ta có: 1 5 P   R    R 0 1 4 4 Từ đây, quy trình dựng hình có thể được thực hiện theo trình tự sau:  Tính P0, vẽ điểm (x0,y0) = (0,R).  Dựa vào dấu của P0 chúng ta lại chọn được điểm vẽ tiếp theo (x1,y1) và giá trị P1.  Dựa vào dấu của P1 chúng ta lại chọn được điểm vẽ tiếp theo (x2,y2) và giá trị P2.  Quá trình trên được lặp đi lặp lại cho đến khi chúng ta vẽ được điểm nguyên gần nhất với B.  Một điểm đáng chú ý ở đây là: Các giá trị P tiếp theo có được bằng cách cộng giá trị P trước đó với một lượng nguyên 2xi  3 hoặc 2(xi  yi)  5 tùy theo dấu của P . Song, nếu giá trị P khởi đầu là 1 P0  1 R  là một giá trị thực sẽ làm cho việc tính các giá trị P 4 tiếp theo cũng phải xử lý trên trường số thực. Một điều dễ thấy là nếu chúng ta thay đổi giá trị P0 khởi đầu thành 1–R thì dấu của P0 và các Pi có được sau đó không hề thay đổi (mặt dù giá trị có bị giảm một lượng 0.25), dẫn đến kết quả chọn lựa các điểm ảnh của giải thuật không hề bị thay đổi, nhưng các tính toán giá trị P chỉ cần thực hiện trên trường số nguyên. Sự thay đổi này giúp giảm độ phức tạp tính toán nếu xét trên khía cạnh thực hiện bằng phần mềm (software) hay giảm yêu cầu về kiến trúc phần cứng nếu xét trên khía cạnh thực hiện bằng phần cứng (Hardware). 3.1.1. Tóm tắt giải thuật vẽ đường tròn MidPoint  Bước 1: (Bước khởi động, tính toán các giá trị ban đầu) P0 = 1 – R; (x0,y0) = (0,R) Vẽ điểm (x0,y0) 27 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài  Bước 2: (Bước lặp, thực hiện tính các giá trị điểm ảnh) Với mỗi giá trị i (i=0,1,2,…) chúng ta xét dấu Pi.  Nếu Pi<0: Thì xác định điểm tiếp theo là: (xi+1,yi+1) = (xi+1,yi) Pi+1=Pi+ 2xi + 3  Ngược lại (tức Pi ≥ 0): Thì xác định điểm tiếp theo là: (xi+1,yi+1) = (xi+1,yi –1) Pi+1 = Pi + 2(xi – yi) + 5 Vẽ điểm (xi+1,yi+1) vừa tìm được.  Bước 3: (Xác định điều kiện lặp) Lặp lại bước 2 với những giá trị i tiếp theo, cho đến khi chúng ta vẽ được điểm nguyên gần nhất với B, nghĩa là: (R xi+1 = round(xb) = )2 Round thì giải thuật kết thúc. 3.1.2. Cài đặt  Sinh viên cần xây dựng hàm vẽ đường tròn theo giải thuật đã trình bày trên. Trên cơ sở đó, mở rộng chương trình LineDemo với chức năng mới là vẽ đường tròn.  Nâng cấp chương trình với khả năng vẽ phóng lớn, với thiết kế giao diện như hình dưới đây: Hình 1.18. Minh họa việc hiển thị các điểm ảnh của đường tròn với các kích cỡ khác nhau 28 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài 3.2. Giải thuật vẽ đường tròn Bresenham Lập luận tương tự giải thuật trên, song không dùng hàm ƒcircle mà dùng biểu thức ( ) 1 2 d  d . Giải thuật được trình bày chi tiết như sau:  Điểm ảnh đầu tiên được chọn để vẽ sẽ là điểm A(0, R), nghĩa là: (x0, y0) = (0, R)  Giả sử đến bước thứ i chúng ta đã chọn được điểm ảnh (xi, yi) để vẽ. Câu hỏi đặt ra là đến bước thứ i+1 chúng ta sẽ chọn điểm ảnh có tên gọi (xi+1, yi+1) với giá trị bằng bao nhiêu? Vì điểm ảnh tiếp theo sẽ chọn theo quy tắc đã nêu ở phần đầu mục 3, nên hoành độ x của điểm ảnh chọn ở bước sau sẽ tăng một giá trị so với điểm ảnh được lựa chọn ở bước trước, hay nói cách khác là: xi1  xi 1 Đồng thời, trên cung AB khi x tăng thì y giảm và tốc độ thay đổi của y chậm hơn của x, nên rõ ràng chúng ta thấy rằng với giá trị x tăng 1 thì giá trị y sẽ thay đổi một lượng ∆y với điều kiện ràng buộc là -1 ≤ ∆y ≤0. Mà điểm ảnh chọn bước trước là (xi,yi) nên điểm ảnh chọn tiếp theo chỉ có thể là một trong hai điểm P(xi + 1, yi) và Q(xi + 1, yi – 1). Để quyết định được điểm ảnh cần chọn là P hay Q, chúng ta hướng đến một biểu thức mà dấu của nó cho phép chúng ta ra quyết định chọn điểm nào. 1 d y y  P  và 2 2 Đặt: 2 2 2 Q d  y  y giá trị y ở đây chính là tung độ của cung AB ứng với hoành độ x  xi 1 Đặt: Pi = d1 – d2 = yP2 + yQ2 – 2y2 = yi2 + (yi –1)2 – 2(R2 – xi+12) = yi2 + (yi–1)2 – 2(R2 – (xi +1)2) = yi2 + (yi–1)2 – 2R2 + 2(xi +1)2 (1.8) Dấu của biểu thức Pi cho phép xác định điểm ảnh được chọn tiếp theo là P hay Q.  Khi Pi < 0: Thì điểm ảnh P sẽ gần với đường tròn hơn điểm ảnh Q, do đó chúng ta sẽ chọn điểm ảnh P làm điểm biểu diễn (vẽ). 29 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài  Khi Pi > 0: Thì điểm ảnh Q sẽ gần với đường tròn hơn P, do đó chúng ta sẽ chọn điểm ảnh Q làm điểm biểu diễn.  Khi Pi = 0: Thì khoảng cách từ P và Q đến đường tròn đều bằng nhau, nên chúng ta có thể chọn P hay Q đều được. Trong tình huống này giải thuật quy ước chọn điểm ảnh Q làm điểm biểu diễn. Từ đây, chúng ta thấy có thể dựa vào dấu của biểu thức Pi để ra quyết định chọn điểm tiếp theo. Để giải thuật được đơn giản người ta tối ưu hóa việc tính Pi theo công thức truy hồi: Pi1 = yi+12 + (yi+1 – 1)2 – 2R2 + 2(xi+1 + 1)2(1.9) Dấu của Pi sẽ quyết định giá trị Pi1 cụ thể như sau:  Nếu Pi < 0: Thì điểm ảnh chọn tiếp theo là P(xi+1, yi), nghĩa là: (xi+1,yi+1) = (xi + 1,yi) Thay vào (1.9) chúng ta được: Pi1 = yi2 + (yi – 1)2 – 2R2 + 2((xi +1)+1)2 = Pi + 2(2(xi+1)+1) = Pi + 4xi + 6  Nếu Pi ≥ 0: Thì điểm ảnh chọn tiếp theo là Q(xi + 1, yi – 1), nghĩa là: (xi+1,yi+1) = (xi + 1,yi – 1) Thay vào (1.9) chúng ta được: Pi1 = (yi – 1)2 + (yi – 2)2 – 2R2 + 2((xi + 1) + 1)2 = Pi + (-4yi + 4) + 2(2(xi + 1) + 1) = Pi + 4(xi – yi) + 10 Đầu tiên, chúng ta chọn điểm ảnh A(0,R), nghĩa là (x0,y0) = (0,R), thay vào (1.8) chúng ta có: P0 = y02 + (y0 – 1)2 – 2R2 + 2(x0 +1)2 = R2 + (R – 1)2 – 2R2 + 2 = R2 + R2 – 2R + 1 – 2R2 + 2 = 3 – 2R Vậy quy trình vẽ được thực hiện như sau: 30 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài  Tính P0, vẽ điểm ảnh (x0,y0) = (0,R).  Dựa vào dấu của P0 chúng ta lại chọn được điểm vẽ tiếp theo (x1,y1) và giá trị P1.  Dựa vào dấu của P1 chúng ta lại chọn được điểm vẽ tiếp theo (x2,y2) và giá trị P2.  Quá trình trên được lặp đi lặp lại cho đến khi chúng ta vẽ được điểm ảnh nguyên gần nhất với B. 3.2.1. Tóm tắt giải thuật vẽ đường tròn Bresenham  Bước 1: (Bước khởi động, tính toán các giá trị ban đầu) P0 = 3 – 2R; (x0,y0) = (0,R) Vẽ điểm (x0,y0).  Bước 2: (Bước lặp, thực hiện tính các giá trị điểm ảnh) Với mỗi giá trị i (i=0,1,2,…) chúng ta xét dấu Pi.  Nếu Pi<0: Thì xác định điểm tiếp theo là: (xi+1,yi+1) = (xi + 1,yi) Pi+1 = Pi+ 4xi +6  Ngược lại (tức Pi ≥ 0): Thì xác định điểm tiếp theo là: (xi+1,yi+1) = (xi + 1,yi – 1) Pi+1 = Pi + 4(xi – yi) + 10 Vẽ điểm (xi+1,yi+1) vừa tìm được.  Bước 3: (Xác định điều kiện lặp) Lặp lại bước 2 với những giá trị i tiếp theo, cho đến khi chúng ta vẽ được điểm nguyên gần nhất với B. Điều này có nghĩa là khi xi+1 = Round(xb) thì giải thuật kết thúc. 3.2.2. Cài đặt Sinh viên cần cài đặt một hàm vẽ đường tròn theo giải thuật Bresenham và chương trình sử dụng hàm để vẽ các đường tròn ngẫu nhiên. 31 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài 3.3. So sánh đánh giá hai giải thuật dựng đường tròn Sau đây, chúng ta sẽ tiến hành so sánh và đánh giá hai giải thuật dựng đường tròn trên một số tiêu chí quan trọng: 1. Yêu cầu về phần cứng thực thi tính toán Rõ ràng rằng cả hai giải thuật MidPoint và Bresenham đều chỉ yêu cầu tính toán trên trường số nguyên, vì vậy yêu cầu về phần cứng thực thi tính toán của cả hai giải thuật là như nhau, hay không có sự khác biệt. 2. Số lệnh máy cần thực hiện để tính toán được tọa độ điểm ảnh Giải thuật vẽ đường tròn MidPoint Giải thuật vẽ đường tròn Bresenham P = 1 – R x = 0 y = R Tính toán trong phần khởi động P = 3 – 2R x = 0 y = R Nhận xét: Số lệnh máy cần thực hiện ở giai đoạn khởi động của cả hai giải thuật không khác nhau đáng kể. Mặt khác, do bước khởi động chỉ thực hiện một lần, nên góp phần không đáng kể vào chi phí thời gian tính toán của toàn bộ quy trình thực thi của giải thuật. Tính toán trong vòng lặp để thu được tọa độ một điểm ảnh minh họa x = x + 1 Nếu P < 0: P = P + 2x + 3 Ngược lại: y = y – 1 P = P + 2(x – y) + 5 x = x + 1 Nếu P < 0: P = P + 4x + 6 Ngược lại: y = y – 1 P = P + 4(x – y) + 10  Tổng cộng trong tình huống xấu nhất: - 3 lệnh cộng số nguyên - 2 lệnh trừ số nguyên  Tổng cộng trong tình huống xấu nhất: - 3 lệnh cộng số nguyên - 2 lệnh trừ số nguyên 32 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài - 1 lệnh nhân số nguyên - 1 lệnh chuyển hướng thực thi (hay lệnh nhảy)  Tổng cộng trong tình huống tốt nhất: - 3 lệnh cộng số nguyên - 1 lệnh nhân số nguyên - 1 lệnh chuyển hướng thực thi (hay lệnh nhảy) - 1 lệnh nhân số nguyên - 1 lệnh chuyển hướng thực thi (hay lệnh nhảy)  Tổng cộng trong tình huống tốt nhất: - 3 lệnh cộng số nguyên - 1 lệnh nhân số nguyên - 1 lệnh chuyển hướng thực thi (hay lệnh nhảy) Nhận xét: Dễ thấy rằng, cả hai giải thuật là giống nhau về các loại lệnh và số lệnh cần thực thi. Qua kết quả so sánh trên có thể giúp chúng ta đi đến kết luận rằng cả hai giải thuật là tương đương nhau trên các tiêu chí đánh giá. Vì vậy, chúng ta có thể chọn lựa một trong hai giải thuật trên để cài đặt trên các hệ thống đồ họa, và chúng mang lại hiệu quả thực thi ngang nhau. 4. GIẢI THUẬT VẼ ELLIPSE Phương trình chính tắc của Ellipse có dạng: 2 2 x(1.10) y   1 2 2 a b A(0,b) C(x0, y0) B(a,0) Hình 1.19. Hình Ellipse với các cung AC và BC 33 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Để dựng được ellipse, chúng ta chỉ cần tìm cách dựng cung AB, các phần còn lại dễ dàng có được bằng cách lấy đối xứng. Tư tưởng chung để dựng một đường bất kỳ là cần phải xác định ra các miền mà trên phạm vi toàn miền luôn xác định được một biến số biến thiên nhanh hơn biến số còn lại. Rõ ràng, trên cung AB thì độ dốc giảm liên tục từ điểm A (độ dốc bằng 0) đến B (độ dốc tiến đến   ). Xét về tốc độ biến thiên của 2 biến số thì:  Tốc độ biến thiên của biến số X giảm dần từ A đến B.  Tốc độ biến thiên của biến số Y tăng dần từ A đến B. Rõ ràng, trên cung AB phải có một điểm mà tại đó tốc độ biến thiên của X và Y bằng nhau (song, x tăng thì y giảm), đó chính là điểm có độ dốc bằng -1. Gọi C(x0,y0) là điểm nằm trên cung AB của ellipse mà tiếp tuyến tại đó có độ dốc bằng -1. Khi đó, tiếp tuyến d của ellipse sẽ có dạng: x x . . y y 0   2 a 2 b 0 1 Mặt khác, về mặt lý thuyết thì độ dốc của d sẽ bằng đạo hàm của cung AB tại tiếp điểm C(x0,y0). Từ đó, chúng ta có: 2 x b 0    Đạo hàm của cung AB tại điểm C = 1 2 y a 0 4 b Suy ra: 2 y  (1.11) 20 x 4 0 a Đồng thời, do C thuộc ellipse nên chúng ta có: 2 20   x(1.12) y 0 2 a 1 2 b Từ (1.11) và (1.12) chúng ta suy ra: 2 a 2 b  và 2 2 x 0a b y  2 2  34 0a b  Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Chúng ta sẽ trình bày giả thuật để vẽ cung AC (Đi từ A đến C theo chiều kim đồng hồ). Cung CB được thực hiện một cách tương tự khi chúng ta đổi vai trò của x và y. Các phần còn lại của ellipse có được bằng cách lấy đối xứng. Trên cung AC độ dốc nằm trong đoạn [0, -1], nghĩa là x tăng thì y giảm và tốc độ biến thiên của x lớn hơn của y. Vậy, tư tưởng của giải thuật dựng cung AC sẽ là: Cho tham số x biến thiên tuần tự từ xa đến xc với các giá trị nguyên, và với mỗi giá trị x chúng ta tìm một giá trị y nguyên gần nhất với giá trị y thực của ellipse. Phần tiếp theo dưới đây sẽ trình bày chi tiết giải thuật Bresenham áp dụng cho dựng ellipse. 4.1. Giải thuật Bresenham cho vẽ hình Ellipse Rõ ràng, điểm ảnh đầu tiên được chọn để dựng cung AC sẽ là điểm A(0, b), nghĩa là: (x0, y0) = (0, b) Giả sử đến bước thứ i chúng ta đã chọn được điểm ảnh (xi, yi) để vẽ. Câu hỏi đặt ra là đến bước thứ i+1, chúng ta sẽ chọn điểm ảnh có tên gọi (xi+1, yi+1) với giá trị bằng bao nhiêu? Vì điểm tiếp theo sẽ có hoành độ x tăng một giá trị so với giá trị của điểm chọn trước, hay nói cách khác là: xi1  xi 1 Đồng thời, vì trên cung AC khi x tăng thì y giảm và tốc độ thay đổi của y chậm hơn của x, nên rõ ràng chúng ta thấy là với giá trị x tăng 1 thì giá trị y thay đổi một lượng ∆y với ràng buộc –1 ≤ ∆y ≤ 0. Mà điểm chọn bước trước là (xi, yi) nên điểm chọn tiếp theo (xi+1, yi+1) chỉ có thể là một trong hai điểm P(xi + 1, yi) và Q(xi + 1, yi – 1). Để quyết định được điểm chọn là P hay Q, chúng ta hướng đến một biểu thức mà dấu của nó cho phép chúng ta ra quyết định chọn điểm nào. Đặt: 2 2 1 d y y  P  và 2 2 2 Q d  y  y (giá trị y ở biểu thức trên là tung độ của cung AC ứng với hoành độ đang xét xi+1). 35 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài 1 2 P (d d )a i   = [yP2 + yQ2 – 2y2 ].a2 Đặt 2 2 2 2 b a x  i)].a2 ( ) 1 = [ yi2 + (yi – 1)2 – 2( 2 a 2 2 2 2 ( ( 1) ) b a x  i ].a2 = [yi2 + (yi – 1)2 – 2 a = yi2.a2 + (yi – 1)2.a2 – 2b2.[a2 – (xi + 1)2] = yi2.a2 + (yi – 1)2.a2 – 2b2.a2 + 2b2.(xi + 1)2(1.13) (lượng a2 được đưa vào nhằm mục đích khử mẫu của ( ) 1 2 d  d , song không làm cho Pi và ( ) 1 2 d  d khác dấu). Dấu của biểu thức Pi cho phép chúng ta xác định điểm ảnh tiếp theo là P hay Q. Cụ thể:  Khi Pi < 0: Thì điểm P sẽ sát với cung AC hơn điểm Q, do đó chúng ta sẽ chọn điểm P làm điểm biểu diễn (vẽ).  Khi Pi > 0: Thì điểm Q sẽ sát với cung AC hơn điểm P, do đó chúng ta sẽ chọn điểm Q làm điểm biểu diễn.  Khi Pi = 0: Thì khoảng cách từ P và Q đến cung AC đều bằng nhau, nên chúng ta có thể chọn P hay Q đều được. Trong tình huống này giải thuật quy ước chọn điểm Q làm điểm biểu diễn. Vậy từ đây, chúng ta thấy có thể dựa vào dấu của biểu thức Pi để ra quyết định chọn điểm tiếp theo. Để giải thuật được đơn giản người ta tối ưu hóa việc tính Pi theo công thức truy hồi: Pi1 = yi+12.a2 + (yi+1 – 1)2.a2 – 2b2.a2 + 2b2.(xi+1 + 1)2(1.14) Dấu của Pi sẽ quyết định giá trị Pi1 cụ thể như sau:  Nếu Pi < 0: Thì điểm chọn tiếp theo là P(xi + 1, yi), nghĩa là: (xi+1, yi+1) = (xi + 1, yi). 36 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Thay vào (1.14) chúng ta được: Pi1 = yi2.a2 + (yi – 1)2.a2 – 2b2.a2 + 2b2.[(xi + 1) + 1]2 = Pi + 2b2.[2(xi + 1) + 1] = Pi + 2b2(2xi + 3)  Nếu Pi ≥ 0: Thì điểm chọn tiếp theo là Q(xi + 1, yi – 1), nghĩa là: (xi+1, yi+1) = (xi + 1, yi – 1) Thay vào (1.14) chúng ta được: Pi1 = (yi – 1)2.a2 + (yi – 2)2.a2 – 2b2.a2 + 2b2.[(xi + 1) + 1]2 = Pi + a2(-4yi + 4) + 2b2[2(xi + 1) + 1] = Pi + 4a2(1 – yi) + 2b2(2xi + 3) = Pi + 2b2(2xi + 3) + 4a2(1 – yi) Đầu tiên, chúng ta chọn điểm A(0, b), nghĩa là (x0, y0) = (0, b), thay vào (1.13) chúng ta có: P0 = y02.a2 + (y0 – 1)2.a2 – 2b2.a2 + 2b2.(x0 + 1)2 = b2.a2 + (b – 1)2.a2 – 2a2.b2 + 2b2 = b2.a2 + a2.b2 – 2a2.b + a2 – 2a2.b2 + 2b2 = –2a2.b + a2 + 2b2 = a2.(1 – 2b) + 2b2 Vậy quy trình vẽ được thực hiện như sau:  Tính P0, vẽ điểm (x0, y0) = (0, b).  Dựa vào dấu của P0 chúng ta lại chọn được điểm vẽ tiếp theo (x1, y1) và giá trị P1.  Dựa vào dấu của P1 chúng ta lại chọn được điểm vẽ tiếp theo (x2, y2) và giá trị P2.  Quá trình trên được lặp đi lặp lại cho đến khi chúng ta vẽ được điểm nguyên gần nhất với C. 37 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài 4.2. Tóm tắt giải thuật Bresenham cho vẽ Ellipse  Bước 1: (Bước khởi động, tính toán các giá trị ban đầu) P0 = a2(1 – 2b) + 2b2 ; (x0, y0) = (0, b) Vẽ điểm (x0, y0).  Bước 2: (Bước lặp, thực hiện tính các giá trị điểm ảnh) Với mỗi giá trị i (I = 0, 1, 2,…) chúng ta xét dấu Pi  Nếu Pi < 0: Thì xác định điểm tiếp theo là: (xi+1, yi+1) = (xi + 1, yi) Pi+1 = Pi + 2b2(2xi + 3)  Ngược lại (tức Pi ≥ 0): Thì xác định điểm tiếp theo là: (xi+1, yi+1) = (xi + 1, yi – 1) Pi+1 = Pi + 2b2(2xi + 3) + 4a2(1 – yi) Vẽ điểm (xi+1, yi+1) vừa tìm được.  Bước 3: (Xác định điều kiện lặp) Lặp lại bước 2 với những giá trị i tiếp theo, cho đến khi chúng ta vẽ được điểm nguyên gần nhất với C, nghĩa là: 2 a xi+1 = Round(xC) = ( ) Round thì giải thuật kết thúc. 2 2 a b Chú ý: Tóm tắt giải thuật trên chỉ áp dụng cho đoạn AC. Để dựng đoạn BC, chúng ta cần có sự thay đổi vai trò của của x và y cũng như a và b. Cụ thể, để dựng được cung BC cần hoán đổi trong toàn bộ giải thuật: x thành y và y ngược lại thành x, a thành b và b ngược lại thành a. 4.3. Cài đặt giải thuật Sau đây là phần cài đặt minh họa cho giải thuật vẽ ellipse gồm có: (1) Hàm Bre_Ellipse thực hiện chức năng vẽ đường ellipse (không tô màu phần bên trong). (2) Hàm FillEllipse thực hiện chức năng vẽ hình ellipse có tô màu phần bên trong hình. 38 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài 1. Hàm Bre_Ellipse Đầu vào: Con trỏ ngữ cảnh thiết bị pDC, tọa độ tâm của ellipse (X_center, Y_center), bán kính theo trục x là a và bán kính theo trục y là b, màu sắc của đường ellipse là PenColor. Đầu ra: Hình ảnh thể hiện của ellipse trên ngữ cảnh thiết bị. void CLineDlg::Bre_Ellipse(CDC * pDC, int X_center, int Y_center, int a, int b, COLORREF PenColor) { if ((a <= 0) || (b <= 0)) return; int x, y; int P; int Const1, Const2; Const1 = int(double(a*a) / sqrt(double(a*a + b*b)) + 0.5); Const2 = int(double(b*b) / sqrt(double(a*a + b*b)) + 0.5); // Vẽ cung AC x = 0; y = b; P = a*a*(1 - 2 * b) - 2 * b*b; pDC->SetPixel(x + X_center, y + Y_center, PenColor); pDC->SetPixel(x + X_center, -y + Y_center, PenColor); while (x < Const1) { if (P < 0) P += 2 * b*b*(2 * x + 3); else { P += 2 * b*b*(2 * x + 3) + 4 * a*a*(1 - y); if (y > Const2) y--; } x++; pDC->SetPixel(x + X_center, y + Y_center, PenColor); pDC->SetPixel(x + X_center, -y + Y_center, PenColor); pDC->SetPixel(-x + X_center, y + Y_center, PenColor); pDC->SetPixel(-x + X_center, -y + Y_center, PenColor); } 39 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài // Vẽ cung BC y = 0; x = a; P = b*b*(1 - 2 * a) - 2 * a*a; pDC->SetPixel(x + X_center, y + Y_center, PenColor); pDC->SetPixel(-x + X_center, y + Y_center, PenColor); while (y < Const2) { if (P < 0) P += 2 * a*a*(2 * y + 3); else { P += 2 * a*a*(2 * y + 3) + 4 * b*b*(1 - x); if (x > Const1) x--; } y++; pDC->SetPixel(x + X_center, y + Y_center, PenColor); pDC->SetPixel(x + X_center, -y + Y_center, PenColor); pDC->SetPixel(-x + X_center, y + Y_center, PenColor); pDC->SetPixel(-x + X_center, -y + Y_center, PenColor); } } 2. Hàm FillEllipse Phần bên trong của ellipse được tiến hành tô theo kiểu quét dòng. Tại mỗi bước, chúng ta tính được điểm (xi, yi) theo giải thuật và xác định được thêm 3 điểm đối xứng của nó lần lượt là (-xi, yi), (xi, -yi), (-xi, -yi). Từ đó, xác định được 2 dòng quét là: Line 1: Từ điểm (-xi, yi) đến điểm (xi, yi). Line 2: Từ điểm (-xi, -yi) đến điểm (xi, -yi). Tiến hành tô màu cho Line 1 và Line 2 như Hình 1.20 dưới đây. 40 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Line 1 Line 2 Hình 1.20. Minh họa kỹ thuật tô ellipse theo dòng quét Tiến hành xây dựng hàm FillEllipse với thông tin vào ra: Đầu vào: Con trỏ ngữ cảnh thiết bị pDC, tọa độ tâm của ellipse (X_center, Y_center), bán kính theo trục x là a và bán kính theo trục y là b, màu sắc của đường ellipse là PenColor và màu tô bên trong đường ellipse là BrushColor. Đầu ra: Hình ảnh thể hiện của ellipse trên ngữ cảnh thiết bị. void FillEllipse(CDC * pDC, int X_center, int Y_center, int a, int b, COLORREF PenColor, COLORREF BrushColor) { if ((a <= 0) || (b <= 0)) return; CPen MyPen(PS_SOLID, 1, BrushColor); HGDIOBJ OldPen = pDC->SelectObject(MyPen); int x, y, Old_y; int P; int Const1, Const2; Const1 = int((double(a*a) / sqrt(double(a*a + b*b))) +0.5); Const2 = int((double(b*b) / sqrt(double(a*a + b*b))) +0.5); // Vẽ cung AC x = 0; y = b; P = a*a*(1 - 2 * b) - 2 * b*b; pDC->SetPixel(x + X_center, y + Y_center, PenColor); 41 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài pDC->SetPixel(x + X_center, -y + Y_center, PenColor); Old_y = y; while (x < Const1) { if (P < 0) P += 2 * b*b*(2 * x + 3); else { P += 2 * b*b*(2 * x + 3) + 4 * a*a*(1 - y); if (y > Const2) y--; } x++; pDC->SetPixel(x + X_center, y + Y_center, PenColor); pDC->SetPixel(x + X_center, -y + Y_center, PenColor); pDC->SetPixel(-x + X_center, y + Y_center, PenColor); pDC->SetPixel(-x + X_center, -y + Y_center, PenColor); if (y != Old_y) { pDC->MoveTo(-x + 1 + X_center, y + Y_center); pDC->LineTo(x + X_center, y + Y_center); pDC->MoveTo(-x + 1 + X_center, -y + Y_center); pDC->LineTo(x + X_center, -y + Y_center); Old_y = y; } } // Vẽ cung BC y = 0; x = a; P = b*b*(1 - 2 * a) - 2 * a*a; pDC->SetPixel(x + X_center, y + Y_center, PenColor); pDC->SetPixel(-x + X_center, y + Y_center, PenColor); if (y != Old_y) { pDC->MoveTo(-x + 1 + X_center, y + Y_center); pDC->LineTo(x + X_center, y + Y_center); 42 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Old_y = y; } while (y < Const2) { if (P < 0) P += 2 * a*a*(2 * y + 3); else { P += 2 * a*a*(2 * y + 3) + 4 * b*b*(1 - x); if (x > Const1) x--; } y++; pDC->SetPixel(x + X_center, y + Y_center, PenColor); pDC->SetPixel(x + X_center, -y + Y_center, PenColor); pDC->SetPixel(-x + X_center, y + Y_center, PenColor); pDC->SetPixel(-x + X_center, -y + Y_center, PenColor); if (x > 0) { pDC->MoveTo(-x + 1 + X_center, y + Y_center); pDC->LineTo(x + X_center, y + Y_center); pDC->MoveTo(-x + 1 + X_center, -y + Y_center); pDC->LineTo(x + X_center, -y + Y_center); } } pDC->SelectObject(OldPen); } Kết quả thực thi phần cài đặt trên được thể hiện qua Hình 1.21. dưới đây: 43 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Hình 1.21. Hình ảnh thực nghiệm dựng đường ellipse và hình ellipse bởi giải thuật Bresenham 5. BÀI TẬP CUỐI CHƯƠNG 1. Cho điểm A(5, 7) và B(15, 15). Sử dụng giải thuật Bresenham đã cho để tìm tọa độ các điểm vẽ (xi , yi). 2. Kế thừa dự án LineDemo trong bài thực nghiệm số 1 đã được trình bày chi tiết tại mục 2.3, sinh viên cần xây dựng một hàm vẽ đoạn thẳng tổng quát cho phép vẽ đoạn thẳng AB trong mọi trường hợp hệ số góc. 3. Sử dụng giải thuật vẽ đường tròn Midpoint để tính giá trị các điểm vẽ (xi , yi) biết rằng R = 20. 4. Cài đặt một hàm vẽ đường tròn theo giải thuật MidPoint. 5. Cài đặt một hàm cho phép tô màu phần diện tích bên trong của đường tròn. Hàm có dạng void FillCircle(int x, int y, int R, COLORREF FillColor). 6. Cài đặt hàm vẽ đường ellipse theo giải thuật Bresenham. 44 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài 7. Cài đặt một hàm tô màu phần bên trong của một Ellipse. 8. Hãy xây dựng một giải thuật để dựng đường cong bậc 2 (Parabol) dạng tổng quát, y = ax2 + bx + c, trên một đoạn xác định [x1, x2]. 9. Viết chương trình vẽ đường Parabol. 10. Xây dựng chương trình cho phép vẽ biểu đồ (Chart) từ số liệu đầu vào như trong chức năng vẽ đồ thị của chương trình Microsoft Excel. 11. Hãy xây dựng một thư viện đồ họa riêng với các hàm vẽ các đường cơ bản do bạn tự viết dựa trên những kiến thức đã được lĩnh hội. 45 Chương 2 CÁC HỆ MÀU VÀ CƠ CHẾ TỔ CHỨC BỘ NHỚ MÀN HÌNH Giao thoa màu sắc là chìa khóa cho các kỹ thuật tái tạo hình ảnh màu trên các thiết bị đồ họa như màn hình, máy in. Trong chương này, chúng ta sẽ tìm hiểu qua về cấu trúc và cách thức tạo điểm ảnh màu trên màn hình, từ đó tìm hiểu về các hệ màu và giải quyết bài toán chuyển đổi giữa các hệ màu cũng như tính ứng dụng của mỗi hệ màu, và cuối cùng chúng ta sẽ tìm hiểu về cách thức tổ chức hoạt động của bộ nhớ màn hình thông qua một mode màn hình cụ thể và đơn giản đó là mode 13h. 1. ĐÔI NÉT VỀ CẤU TRÚC MÀN HÌNH MÀU Màn hình màu như máy tính hay tivi về cơ bản được cấu tạo từ một ma trận các điểm ảnh có khả năng hiển thị với màu sắc thay đổi theo yêu cầu. Sở dĩ có được khả năng này là bởi tính chất giao thoa màu sắc của ánh sáng (xem Hình 2.1) và mỗi điểm ảnh được cấu tạo từ 3 điểm ảnh đơn sắc như Hình 2.2. Mắt người với đặc điểm độ nhạy kém, nên với thiết kế các điểm đơn sắc đủ bé và khoảng cách quan sát đủ xa thì mắt người sẽ không thể nhìn thấy hình ảnh 3 điểm đơn sắc riêng biệt mà chúng bị nhòe làm một và cho hình ảnh một màu tổng hợp theo nguyên lý giao thoa. Hình 2.1. Màu sắc và sự giao thoa 46 Chương 2 - Các hệ màu và cơ chế bộ nhớ màn hình Nguyễn Hữu Tài Hình 2.2. Hai loại cấu trúc màn hình màu: (a) CRT, (b) LCD Hình 2.3. Ảnh biểu diễn của một mũi tên màu trắng, và một chữ E trên máy tính được phóng lớn tương ứng với hai loại màn hình CRT và LCD 2. CÁC HỆ MÀU Trên các thiết bị hiển thị như màn hình máy tính, màn hình tivi và phần lớn các thiết bị hiển thị màu thông dụng khác người ta chọn 3 màu Red, Green và Blue để biểu diễn tất cả các màu sắc khác nhau của hình ảnh, cũng như người họa sĩ chỉ dùng một số màu cơ bản, song các bức tranh được vẽ ra lại rất phong phú về màu sắc. Một câu hỏi đặt ra là tại sao lại chọn 3 màu trên mà không phải là một nhóm màu nào khác. Để trả lời câu hỏi này, chúng ta hãy tìm hiểu qua về cấu tạo mắt người. Mắt con người chúng ta cảm nhận màu sắc thông qua các tế bào võng mô hình nón. Ba màu Red, Green và Blue được mắt con người cảm nhận rõ nhất, chúng có bước sóng dài lần lượt là 580nm, 545nm và 440nm. Sự hòa trộn của 3 bước sóng này sẽ cho chúng ta được những màu sắc khác 47 Chương 2 - Các hệ màu và cơ chế bộ nhớ màn hình Nguyễn Hữu Tài nhau. Năm 1931, Commission internationale de l'éclairage, được gọi tắt là CIE, đã định nghĩa mối liên hệ giữa màu sắc vật lý trong dải phổ điện từ mà mắt người nhìn thấy được (dựa trên bước sóng) với màu sắc được cảm nhận sinh lý trong trường thị giác người. Những ràng buộc toán học định nghĩa không gian màu là những công cụ thiết yếu cho việc quản lý màu sắc. Chúng cho phép chuyển đổi qua lại giữa các hình thức thể hiện màu sắc qua in ấn, màn hình, hay các thiết bị ghi hình. Trên cơ sở đó, hình thành nên chuẩn không gian màu RGB (tài liệu tham khảo số 6). Hiệu nay, không phải chỉ có hệ màu RGB mà còn có những hệ khác như: CMY, HSV, HSL, YCbCr, Lab,... Phần tiếp theo sẽ trình bày một số hệ màu cơ bản và thông dụng. Hình 2.4. Biểu đồ thể hiện các sắc độ trong không gian màu chuẩn CIE 1931 2.1. Hệ RGB RGB là chữ viết tắt của 3 từ Red, Green và Blue. Hệ này có miền không gian giá trị là một khối 3 chiều. Mỗi màu xác định trên 3 thành phần là R, G, B. Sự gia giảm các thành phần này sẽ tạo ra các màu sắc khác nhau tạo nên một không gian màu. 48 Chương 2 - Các hệ màu và cơ chế bộ nhớ màn hình Nguyễn Hữu Tài Blue(0,0,255) Cyan (0,255,255) Mageta (255,0,255) White (255,255,255) Black(0,0,0) Green (0,255,0) Red Yellow (255,0,0) (255,255,0) Hình 2.5. Không gian màu trong chế độ 24-bit Cường độ của mỗi thành phần R,G,B được mã hóa trong các mức khác nhau. Có các mức mã hóa khá phổ biến là: Mã hóa 16, 64 và 256 mức. Hiện nay, mức mã hóa 256 mức là phổ biến (từ 0 đến 255). Nếu cường độ của mỗi thành phần được mã hóa trong 256 mức thì cần 8 bit để mã hoá, vậy một màu biểu diễn bởi 3 thành phần đơn sắc RGB sẽ lưu trữ bởi 24 bit, chế độ này thường được gọi là chế độ màu thực (True color - 24 bit), bởi vì nó có thể biểu biễn đến khoảng 16,7 triệu màu. 2.2. Hệ màu CMY Hình 2.6. Hệ màu CMYK chuyên dùng trong in ấn CMY là 3 chữ viết tắt từ: Cyan (màu lục lam), Magenta (màu đỏ tươi), Yellow (màu vàng). Công thức chuyển đổi từ hệ RGB sang hệ CMY như sau: 49 Chương 2 - Các hệ màu và cơ chế bộ nhớ màn hình Nguyễn Hữu Tài C = 1 – R M = 1 – G Y = 1 – B Hệ màu này thường được sử dụng trong in ấn. Tuy nhiên, để tiết kiệm mực màu do chúng thường có giá thành đắt hơn mực đen, người ta dùng mực đen để hiển thị các điểm ảnh màu xám thay cho việc hòa trộn các màu CMY để tạo ra điểm màu xám, từ đó chúng ta có hệ màu CMYK để chỉ hệ màu CMY có sử dụng thêm màu đen trong các hệ thống in ấn. 2.3. Hệ màu HSV Hình 2.7. Hệ màu HSV biểu diễn trong chế độ số thực (từ 0 đến 1) Hệ màu HSV được viết tắt từ 3 chữ sau: Hue (màu sắc), Saturation (sự bão hòa) và Value (giá trị, thể hiện mức độ sáng tối). Ba màu Red, Green và Blue trong hệ màu RGB có lẽ là 3 màu mà mắt con người cảm nhận ánh sáng chứ không phải là màu mà mắt con người cảm nhận màu sắc. Màu sắc (Hue, hay color) được đo bởi tần số ánh sáng, còn độ sáng được đo bởi cường độ. Màu càng sáng thì cường độ càng lớn. Hình 2.7 minh họa hệ màu HSV được biểu diễn trong không gian số thực với Hue có giá trị từ 0 → 360, trong khi S và V có giá trị trong khoảng 0 → 1. Người ta cũng có thể áp dụng việc lượng tử hóa các giá trị S và V về không gian số nguyên với giá trị giao động trong khoảng 0 → 255 như 50 Chương 2 - Các hệ màu và cơ chế bộ nhớ màn hình Nguyễn Hữu Tài Hình 2.8, trong đó: Màu đỏ hoàn toàn được biểu diễn là (0 độ, 255, 255), màu xanh (green) được biểu diễn là (120 độ, 255, 255). Hình 2.8. Hệ màu HSV biểu diễn trong chế độ lượng hóa nguyên Hình 2.9. Minh họa việc chuyển đổi qua lại giữa 2 hệ màu HSV và RGB Trong nhiều tình huống áp dụng không đòi hỏi độ chính xác cao, thay vì biểu diễn thành phần Hue trong miền giá trị từ 0 → 360, người ta lượng tử hóa nó vào một thang giá trị nguyên từ 0 đến 255, đưa đến khả năng biểu diễn và lưu trữ giá trị Hue trong 1 byte. 51 Chương 2 - Các hệ màu và cơ chế bộ nhớ màn hình Nguyễn Hữu Tài Dưới đây là các hàm chuyển đổi giá trị điểm ảnh từ không gian màu RGB sang HSV và ngược lại. Trong đó, các thành phần R, G, B, H, S, V đều được biểu diễn dưới dạng số nguyên 1 byte với miền giá trị biến thiên từ 0 đến 255. typedef struct RgbColor { BYTE b; BYTE g; BYTE r; }; typedef struct HsvColor { BYTE h; BYTE s; BYTE v; }; void RgbToHsv(RgbColor rgb, HsvColor &hsv) { BYTE rgbMin, rgbMax; rgbMin = rgb.r < rgb.g ? (rgb.r < rgb.b ? rgb.r : rgb.b) : (rgb.g < rgb.b ? rgb.g : rgb.b); rgbMax = rgb.r > rgb.g ? (rgb.r > rgb.b ? rgb.r : rgb.b) : (rgb.g > rgb.b ? rgb.g : rgb.b); hsv.v = rgbMax; if (hsv.v == 0) { hsv.h = 0; hsv.s = 0; return; } hsv.s = 255 * long(rgbMax - rgbMin) / hsv.v; if (hsv.s == 0) { hsv.h = 0; return; } 52 Chương 2 - Các hệ màu và cơ chế bộ nhớ màn hình Nguyễn Hữu Tài if (rgbMax == rgb.r) hsv.h = 0 + 43 * (rgb.g - rgb.b) / (rgbMax - rgbMin); else if (rgbMax == rgb.g) hsv.h = 85 + 43 * (rgb.b - rgb.r) / (rgbMax - rgbMin); else hsv.h = 171 + 43 * (rgb.r - rgb.g) / (rgbMax - rgbMin); } void HsvToRgb(HsvColor hsv, RgbColor &rgb) { BYTE region, remainder, p, q, t; if (hsv.s == 0) { rgb.r = hsv.v; rgb.g = hsv.v; rgb.b = hsv.v; return; } region = hsv.h / 43; remainder = (hsv.h - (region * 43)) * 6; p = (hsv.v * (255 - hsv.s)) >> 8; q = (hsv.v * (255 - ((hsv.s * remainder) >> 8))) >> 8; t = (hsv.v * (255 - ((hsv.s * (255 - remainder)) >> 8))) >> 8; switch (region) { case 0: rgb.r = hsv.v; rgb.g = t; rgb.b = p; break; case 1: rgb.r = q; rgb.g = hsv.v; rgb.b = p; break; case 2: rgb.r = p; rgb.g = hsv.v; rgb.b = t; break; case 3: rgb.r = p; rgb.g = q; rgb.b = hsv.v; break; case 4: rgb.r = t; rgb.g = p; rgb.b = hsv.v; 53 Chương 2 - Các hệ màu và cơ chế bộ nhớ màn hình Nguyễn Hữu Tài break; default: rgb.r = hsv.v; rgb.g = p; rgb.b = q; break; } } Các hệ màu HSL và HSI là một dạng biểu diễn khác của hệ màu HSV trong đó giá trị V được thay bởi I (Intensity: Cường độ) hay L (Lightness: Độ sáng). Công thức tính I hay L từ các giá trị R, G, và B được cho bởi: I = (R + G + B)/3 L = (min(R,G,B) + max(R,G,B))/2 Hình 2.10. Minh họa hệ màu HSL Hình 2.11. Minh họa hệ màu Lab 3. CƠ CHẾ TỔ CHỨC BỘ NHỚ MÀN HÌNH Địa chỉ bộ nhớ logic dùng cho màn hình trong hệ điều hành MS-DOS được bắt đầu từ: B800:0000 với chế độ text. A000:0000 với các chế độ đồ họa. 54 Chương 2 - Các hệ màu và cơ chế bộ nhớ màn hình Nguyễn Hữu Tài Trong phần này chúng ta chỉ đề cập đến chế độ đồ họa. Thông tin hiển thị trên màn hình được bố trí trong bộ nhớ bắt đầu từ địa chỉ logic A000:0000 đến A000:FFFF với kích thước là 64KB, song cách bố trí như thế nào lại phụ thuộc vào chế độ (mode) màn hình mà chúng ta chọn để hoạt động. Thông thường, một card điều khiển đồ họa có thể hoạt động trong nhiều mode khác nhau. Để ra chỉ thị cho card hoạt động theo một mode nào đó, chúng ta cần triệu gọi các hàm phục vụ đặt chế độ màn hình của Bios, và truyền tham số mode cho hàm. Do có rất nhiều mode đồ họa khác nhau và mỗi mode lại có một cơ chế bố trí thông tin riêng. Trong phần này chỉ trình bày:  Một mode khá thông dụng, được dùng chủ yếu trong các trò chơi (games) chạy trên hệ điều hành MS-DOS, đó là mode 13h (Hexa). Đây là mode với độ phân giải là 320 × 200 với 256 màu, trong chế độ này một byte trong vùng nhớ màn hình lưu trữ thông tin của một điểm, hay nói cách khác là có sự tương ứng một-một giữa điểm ảnh và byte nhớ trong vùng nhớ màn hình. Mặt khác, kích thước bộ nhớ đủ để lưu trữ toàn bộ các điểm ảnh trên màn hình là 320 × 200 × 1 byte = 64.000 byte < 64 KB, kích thước này vừa đủ để nằm gọn trong một phân đoạn bộ nhớ (memory segmentation) A000. Vì thế, các thao tác xử lý điểm ảnh trong chế độ này khá đơn giản và nhanh chóng.  Chuẩn Vesa (Video Electronics Standards Association): Hầu như tất cả các Card điều khiển màn hình thông dụng đều hỗ trợ mode này. Với mode bạn có thể đặt độ phân giải từ 640 × 400, 640 × 480,… lên đến 1024 × 800 hay cao hơn nữa tùy vào khả năng kỹ thuật của Card. Tương tự màu sắc có thể từ 16 màu, 256 màu, Hight color -16 bit hay True color - 24 bit hay 32 bit. 3.1. Cơ chế hoạt động của chế độ màn hình độ phân giải 320 × 200 với 256 màu Trong chế độ này, màn hình được chia ra 320 cột và 200 hàng tạo nên 320 × 200 điểm ảnh (pixel). Tuy độ phân giải thấp, song nó lại có ưu điểm là truy cập nhanh chóng, nhờ cơ chế bố trí thông tin đơn giản. Pixel[cột 0, dòng 0] (ở góc trên bên trái màn hình) tương ứng với byte 55 Chương 2 - Các hệ màu và cơ chế bộ nhớ màn hình Nguyễn Hữu Tài nhớ có địa chỉ A000:0000, tương tự Pixel[cột 1, dòng 0] tương ứng với byte nhớ có địa chỉ A000:0001,… Hay nói một cách tổng quát, pixel tại cột x dòng y tương ứng với byte nhớ [A000 : (y * 320 + x)] Lệnh sau cho phép vẽ màu có số 255 cho điểm có tọa độ (x, y): Mem[$A000 : (y * 320 + x)] = 255 Câu lệnh trên cho phép vẽ ra màn hình 1 điểm có màu 255 tại vị trí (x, y). Tuy nhiên, màu có số 255 là màu như thế nào lại phụ thuộc vào thanh ghi màu số 255 lưu trữ các giá trị RGB mô tả cách hòa ra màu 255 như thế nào. Để quyết định màu cho một thanh ghi màu, chúng ta cần đến các hàm phục vụ của Bios để đặt giá trị cho thanh ghi màu. 3.2. Cơ chế hoạt động của màn hình theo chuẩn Vesa Video Electronics Standards Association (VESA) là một tổ chức tiêu chuẩn kỹ thuật cho chuẩn hiển thị trên máy tính. Chuyên phát triển các chuẩn giao diện kỹ thuật số cho các thiết bị hiển thị (màn hình, tivi,…). Hình 2.12 thể hiện các thông tin chi tiết về một số mode màn hình đồ họa máy tính theo chuẩn Vesa, công bố năm 1998. Các tài liệu công bố về các mode hiện đại hơn gần đây đòi hỏi người dùng phải trả phí thành viên mới được cung cấp. VESA cung cấp nhiều mode đồ họa cao cấp, ví dụ mode 11Bh cho độ phân giải 1280 × 1024, với khả năng biểu diễn được khoảng 16.8 triệu màu do sử dụng 24 bit để biểu diễn thông tin một điểm ảnh trong không gian màu RGB. Bộ nhớ cần thiết để lưu trữ 1280×1024 điểm ảnh (hay một trang màn hình) là: 1280 × 1024 × 3 byte = 3.75 MB. Trong nền tảng hệ điều hành 16-bit MS-DOS, việc truy xuất bộ nhớ màn hình để thay đổi giá trị các điểm ảnh trên màn hình thông qua địa chỉ logic có segment mặc định A000 là khá phức tạp. Cụ thể, do hệ điều hành MS-DOS chỉ cung cấp không gian địa chỉ logic từ A000:0000 đến A000:FFFF với kích thước là 64 KB như là một cửa sổ để định vị truy xuất đến bộ nhớ RAM màn hình, trong khi kích thước bộ nhớ chúng ta cần truy xuất lên đến 3.75 MB. Để giải quyết vấn đề này, người ta chia 56 Chương 2 - Các hệ màu và cơ chế bộ nhớ màn hình Nguyễn Hữu Tài bộ nhớ RAM màn hình thành nhiều dải, thuật ngữ là band, mỗi band có kích thước 64 KB vừa đúng với kích thước của cửa sổ truy xuất A000:0000 đến A000:FFFF mà hệ điều hành cung cấp. Từ đó, để truy xuất thông tin của một điểm ảnh M(x,y) lưu trữ trong bộ nhớ RAM màn hình, chúng ta cần tính toán để biết được vùng nhớ của điểm ảnh M thuộc band nào và có địa chỉ offset trên band là bao nhiêu? Hình 2.12. Một số mode màn hình cùng thông tin chi tiết về độ phân giải và số màu có thể hiển thị, số bit phân phối cho 3 thành phần màu RGB của một điểm ảnh Các bước tính toán địa chỉ truy xuất cho một điểm ảnh M(x,y) gồm: - Xác định số byte để lưu trữ một dòng ảnh, thường bằng số điểm ảnh trên một dòng nhân với số byte dữ liệu cho một điểm ảnh, kết quả phải được làm tròn lên số nguyên là bội số của DWORD (hay 4 byte): Byte_per_line = int((1280 × 3byte + 3) /4) × 4 = 3840 57