Giáo trình Kỹ thuật đồ họa máy tính

107 trang Gia Huy 16/05/2022 5230

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Kỹ thuật đồ họa máy tính", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

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

giao_trinh_ky_thuat_do_hoa_may_tinh.pdf

Nội dung text: Giáo trình Kỹ thuật đồ họa máy tính

LỜI GIỚI THIỆU Ngày nay, hình ảnh được tạo ra từ máy tính có mặt ở khắp mọi nơi. Các sản phẩm đồ họa tràn ngập cuộc sống của chúng ta và đạt được đến kỹ thuật mà đôi khi chúng ta không thể nhận ra đó là một hình ảnh nhân tạo. Các chương trình máy tính thường hiển thị kết quả bằng đồ họa. Các chương trình truyền hình và quảng cáo sử dụng hình ảnh từ đồ họa mang lại hiệu quả rõ rệt về tính thẩm mĩ. Nhiều chương trình truyền hình và điện ảnh gần đây pha trộn các diễn viên thực và hình ảnh nhân tạo đến mức người xem có thể rất khó để phân biệt một nhân vật hoặc cảnh thật với hình ảnh do máy tính tạo ra. Ngày càng nhiều máy ảnh kỹ thuật số, thiết bị điện tử sử dụng input là màn hình cảm ứng thay vì bàn phím. Do vậy, kỹ thuật đồ họa máy tính trở thành một lĩnh vực lý thú và có nhiều ứng dụng trong thực tế. Kỹ thuật đồ họa liên quan đến tin học và toán học vì hầu hết các giải thuật vẽ, tô màu cùng các phép biến hình đều được xây dựng dựa trên nền tảng của hình học không gian hai chiều và ba chiều. Hiện nay, Kỹ thuật đồ họa máy tính là một môn học được giảng dạy cho sinh viên chuyên ngành công nghệ thông tin học với 30 tiết lý thuyết. Bài giảng được biên soạn theo đúng chương trình đào tạo của Nhà trường. Nội dung bài giảng tập trung vào các vấn đề chính trong 5 chương như sau: Chương 1: Tổng quan về đồ họa máy tính, giới thiệu các khái niệm và cái nhìn tổng quan về đồ họa máy tính. Chương 2: Đồ họa 2 chiều, trình bày các thuật toán vẽ và tô các đường cơ bản như đường thẳng, đường tròn, các phép biến đổi trên đối tượng đồ họa 2D và các thuật toán xén đoạn thẳng. Chương 3: Đồ họa 3 chiều, Giới thiệu tổng quan về đồ họa 3 chiều, các phép biến đổi và các phép chiếu, một số cách biểu diễn đối tượng đồ họa 3 chiều từ các đối tượng đơn giản như các hình khối, các đa diện Chương 4: Các hệ màu, trình bày về các hệ màu cơ bản cùng các qui tắc phối màu cơ bản trong đồ họa máy tính. Chương 5: Các kỹ thuật đồ họa trong bộ Công cụ Adobe After Effect 1. Mục tiêu môn học: Với các nội dung như trên, sau khi học xong môn này, sinh viên cần đạt được các yêu cầu sau: - Hiểu thế nào là đồ họa trên máy tính. - Thiết kế và cài đặt được các thuật toán vẽ các đường cơ bản như đường thẳng, đường tròn, - Thiết kế và cài đặt được thuật toán tô màu. 1
- Sử dụng được các phép biến hình trong không gian 2 chiều, 3 chiều để làm thay đổi một hình ảnh đã có sẵn. - Có thể tạo một cửa sổ để cắt - dán một hình. - Hiểu được cách biểu diễn của một số đối tượng 3 chiều và các phép chiếu cơ bản. 2. Đối tượng sử dụng Môn Đồ họa máy tính được giảng dạy cho sinh viên năm thứ ba của khoa Công nghệ thông tin – Trường Đại học Kinh tế kỹ thuật công nghiệp. 3. Phương pháp nghiên cứu: Sinh viên nghe đầy đủ các tiết học lý thuyết trên lớp, kết hợp với các ngôn ngữ lập trình đã được học để thực hiện cài đặt các thuật toán trong nội dung môn học. Hình thức đánh giá kết quả: - Điểm quá trình: Kiểm tra lý thuyết kết hợp bài tập cài đặt chương trình - Thi hết học phần: Thi trắc nghiệm. 2
MỤC LỤC LỜI GIỚI THIỆU 1 CHƯƠNG 1: TỔNG QUAN VỀ ĐỒ HỌA MÁY TÍNH 9 1.1. Giới thiệu về đồ họa máy tính 9 1.1.1. Mở đầu 9 1.1.2. Lịch sử phát triển 10 1.1.3. Một số ứng dụng 11 1.1.4 Phân loại các lĩnh vực của kỹ thuật đồ hoạ máy tính 13 1.2. Tổng quan về một hệ đồ họa 14 1.2.1. Phần cứng đồ họa 15 1.2.2. Phần mềm đồ họa 15 1.3 Các kỹ thuật đồ họa 15 1.3.1 Kỹ thuật đồ hoạ điểm 16 1.3.2 Kỹ thuật đồ họa vector 16 CHƯƠNG 2: ĐỒ HỌA 2 CHIỀU 19 2.1. Giới thiệu về các đối tượng đồ họa cơ sở 19 2.1.1 Mở đầu 19 2.1.2 Các hệ tọa độ 20 2.1.3 Các đối tượng đồ họa cơ sở 20 2.2. Các thuật toán vẽ đường thẳng 22 2.2.1 Mở đầu 22 2.2.2 Thuật toán DDA (Digital Differential Analyzer ) 23 2.2.3 Thuật toán Bresenham 25 2.2.4 Thuật toán Midpoint vẽ đường thẳng 27 2.3. Thuật toán Midpoint vẽ đường tròn 29 2.4 Các phép biến đổi cơ sở của đối tượng 2 chiều 31 2.4.1 Mở đầu 31 2.4.2 Phép tịnh tiến 32 2.4.3 Phép biến đổi tỷ lệ tâm O(0,0) 33 2.4.4 Phép quay tâm O(0,0) 34 3
2.4.5. Kết hợp các phép biến đổi. 35 2.5. Một số tính chất của phép biến đổi affine. 37 2.5.1. Bảo toàn đường thẳng: 37 2.5.2 Bảo toàn tính song song 38 2.5.3 Bảo toàn tính tỷ lệ 38 2.6 Một số phép biến đổi khác. 38 2.6.1 Phép biến đổi tỷ lệ tâm bất kỳ 38 2.6.2 Phép quay có tâm quay bất kỳ 39 2.6.3 Phép đối xứng 40 2.6.4 Phép biến đổi ngược 40 2.7 Các thuật toán xén đoạn thẳng. 40 2.7.1 Thuật toán Cohen-Sutherland 42 2.7.2 Thuật toán Liang Barsky 45 CHƯƠNG 3: ĐỒ HỌA 3 CHIỀU 54 3.1. Tổng quan về đồ họa ba chiều 54 3.2. Biểu diển các đối tượng ba chiều 54 3.2.1. Biểu diễn mặt đa giác 55 3.2.2. Lưới đa giác (polygon meshes) 58 3.2.3. Các đường cong và mặt cong 59 3.3. Các phép biến đổi hình học ba chiều 59 3.3.1 Các phép biến đổi cơ bản 60 3.3.2 Các phép đối xứng 63 3.3.3 Phép biến đổi tỷ lệ tâm bất kỳ 64 3.4. Các phép chiếu 64 3.4.1 Phép chiếu song song 65 3.4.2 Phép chiếu phối cảnh 67 CHƯƠNG 4: CÁC HỆ MÀU 73 4.1 Ánh sáng và sự cảm nhận màu sắc của mắt 73 4.2 Biểu diễn màu trên màn hình đồ họa 74 4.2.1 Chế độ hiển thị màu RGBA 74 4
4.2.2. Chế độ hiển thị màu chỉ mục 76 4.3. Hệ RGB (Red – Green – Blue): 77 4.4. Hệ CMY và CMYK (Cyan - Magenta - Yellow): 79 4.4.1 Hệ màu CMY: 79 4.4.2 Hệ màu CMYK: 80 4.5 Một số hệ màu khác 81 4.5.1. Hệ màu HSV (Hue - Saturation - Value): 81 4.5.2. Hệ màu HSI ( Hue - Saturation - Intensity): 82 CHƯƠNG 5: CÁC KỸ THUẬT ĐỒ HỌA TRONG BỘ CÔNG CỤ ADOBE AFTER EFFECT 90 5.1 Giới thiệu về After Effect 90 5.2. Giao diện 91 5.3. Thực hiện một Project 95 5.4. Kỹ thuật Storyboard 98 5.5. Tạo hình đồ họa nhân vật: gắn xương, các chuyển động cơ bản 100 5.6. Kỹ thuật tạo bối cảnh đồ họa 103 TÀI LIỆU THAM KHẢO 107 5
DANH MỤC HÌNH VẼ Hình 2.1: Các điểm lân cận của (xi, yi) 22 Hình 2.2: Đường thẳng có hệ số góc 0 m 1 23 Hình 2.3: Minh họa thuật toán DDA trường hợp 0 <m <1 23 Hình 2.4: Lưu đồ thuật toán vẽ đường thẳng DDA 24 Hình 2.5: Minh họa thuật toán Bresenham, 0<m<1 25 Hình 2.6: Lưu đồ thuật toán vẽ đường thẳng Bresenham 26 Hình 2.7: Minh họa thuật toán Midpoint vẽ đường thẳng 28 Hình 2.8: Các vị trí đối xứng của đường tròn 29 Hình 2.9: Minh họa thuật toán Midpoint vẽ đường tròn 29 Hình 2.10: Lưu đồ giải thuật Midpoint vẽ đường tròn 30 Hình 2.11: Minh họa phép tịnh tiến 32 Hình 2.12: Minh họa phép biến đổi tỷ lệ 33 Hình 2.13: Minh họa phép quay tâm O 34 Hình 2.14: Minh họa phép quay có tâm quay bất kỳ 39 Hình 2.15: (a)Trước khi thực hiện xén đoạn thẳng, (b) sau khi thực hiện 41 Hình 2.16: Cách đánh mã vùng – thuật toán Cohen-Sutherland 42 Hình 2.17: Minh họa thuật toán Cohen - Sutherland 43 Hình 2.18: Giải thuật xén đoạn thẳng Cohen-Sutherland 44 Hình 2.19: Minh họa thuật toán Liang Barsky 46 Hình 3.1: Mô hình wireframe của một hình trụ 55 Hình 3.2: Minh họa mô hình khung kết nối 56 Hình 3.3: Vector pháp tuyến của mặt phẳng 58 Hình 3.4: Triangle strip và quadrilateral mesh 59 Hình 3.5: Minh họa phép tịnh tiến 60 Hình 3.6: Minh họa phép biến đổi tỷ lệ 61 Hình 3.7: Phép quay, (a) quay quanh trục z, (b) quanh trục x, (c) quanh trục y 62 Hình 3.8: Phép chiếu trực giao, (a) phép chiếu 6 mặt, (b) phép chiếu 3 mặt 65 Hình 3.9: Minh họa phép chiếu trục lượng 66 Hình 3.10: Phép chiếu Cavalier, (a) góc ф=450 , (b) ф=300 67 6
Hình 3.11: Phép chiếu Cabinet, (a) góc ф=450 , (b) ф=300 67 Hình 3.12: Minh họa phép chiếu phối cảnh 68 Hình 3.13: (a) Một tâm chiếu, (b) hai tâm chiếu, (c) ba tâm chiếu 68 Hình 3.14: Phép chiếu phối cảnh tâm chiếu I(0,0,d) 69 Hình 4.1: Minh họa phối màu 75 Hình 4.2: Ánh xạ màu lên pixel 76 Hình 4.3: Minh họa sử dụng bản đồ màu để vẽ 76 Hình 4.4: Hệ màu RGB 77 Hình 4.5: Hệ màu CMY 80 Hình 4.6: Hệ màu HSV 81 Hình 4.7: Hệ màu HSI 82 Hình 4.8: Màu đơn sắc (Monochromatic) 83 Hình 4.9: Kết hợp màu kiểu bổ sung 83 Hình 4.9: Kết hợp màu kiểu bổ sung 84 Hình 4.10: Kết hợp màu kiểu bộ ba 84 Hình 4.11: Kết hợp màu kiểu hình chữ nhật 85 Hình 4.12: Kết hợp màu kiểu hình vuông 85 Hình 5.1: Giao diện After Effect 91 Hình 5.2: Mở workspace của After Effect 92 Hình 5.3: Panel trong After Effect 92 Hình 5.4: Các thao tác với Panel trong After Effect 93 Hình 5.5: Các icon Panel trong After Effect 94 Hình 5.6: Vùng an toàn trong After Effect 94 Hình 5.7: Toolbar trong After Effect 95 Hình 5.8: Chức năng New Project trong After Effect 95 Hình 5.9: Hiệu chỉnh Preferences trong After Effect 96 Hình 5.10: Hiệu chỉnh Preferences trong After Effect 96 Hình 5.11: Import File trong After Effect 97 Hình 5.12: Hiệu chỉnh thông số Import File trong After Effect 98 Hình 5.13: Minh họa Storyboard trong After Effect 100 7
Hình 5.14: File PSD nhân vật 101 Hình 5.15: Import File PSD nhân vật 101 Hình 5.16: Mô tả Import File PSD nhân vật 102 Hình 5.17: Layer nhân vật 102 Hình 5.18: Hiệu chỉnh các điểm neo nhân vật 103 Hình 5.19: Tạo mô tả chuyển động nhân vật 103 Hình 5.20: Bối cảnh trong After Effect 104 Hình 5.21a: Công cụ Roto Brush 104 Hình 5.21b: Công cụ Roto Brush 105 8
CHƯƠNG 1: TỔNG QUAN VỀ ĐỒ HỌA MÁY TÍNH Mục tiêu của chương: Sinh viên nắm được về lịch sử ra đời và một số các cột mốc phát triển của đồ họa máy tính, nhận thức được vai trò, các ứng dụng và các thành tựu của đồ họa máy tính trong các lĩnh vực như giáo dục, y tế, giải trí, nghệ thuật, khoa học, kỹ thuật Sinh vên cần nắm được tổng quan về một hệ đồ họa máy tính, phân loại được các lĩnh vực của đồ họa máy tính, nắm được một số chuẩn của đồ họa và cần phân biệt, so sánh được giữa kỹ thuật đồ họa điểm và đồ họa vector. 1.1. Giới thiệu về đồ họa máy tính 1.1.1. Mở đầu Đồ họa máy tính là một lĩnh vực của công nghệ thông tin, liên quan đến việc nghiên cứu, xây dựng và tập hợp các công cụ ( mô hình lý thuyết và phần mềm) khác nhau để kiến tạo, xây dựng lưu trữ và xử lý các mô hình và hình ảnh của đối tượng, sự vật hiện tượng khác nhau trong đời sống, sản xuất và nghiên cứu. Các mô hình và hình ảnh này có thể là các kết quả thu được từ những lĩnh vực khác nhau của rất nhiều ngành khoa học ( vật lý, toán học, ) Đồ họa máy tính cũng là lĩnh vực liên quan đến việc thiết kế, chế tạo phần cứng như: các thiết bị hiển thị, các thiết bị đầu vào như bàn phím, chuột, bút quang các thuật toán cần thiết để phát sinh hình ảnh trên các thiết bị này, các phần mềm được sử dụng cho cả người lập trình hệ thống và người lập trình ứng dụng đồ họa. Đồ họa máy tính tương tác là một trong những phương tiện mang lại thêm nhiều sự thuận lợi cho người dùng trong việc phát sinh hình ảnh. Chúng ta có thể tạo các hình ảnh không chỉ của các đối tượng cụ thể, thực tế, mà còn của các đối tượng trừu tượng, nhân tạo; biểu diễn dữ liệu mà không có tính kế thừa về mặt hình học như kết quả điều tra, khảo sát Hơn nữa, với đồ họa máy tính chúng ta không bị giới hạn trong các ảnh tĩnh. Các ảnh động thông thường mang lại nhiều hiệu quả hơn so với ảnh tĩnh, đặc biệt là với các hiện tượng biến đổi theo thời gian, cả thực tế (như sự đổi hướng của cánh máy bay siêu âm, hay sự phát triển của khuôn mặt người từ lúc trẻ tới lúc già) và trừu tượng (như là xu hướng phát triển của việc sử dụng năng lượng, sự gia tăng dân số, ). Có nhiều cách tiếp cận trong việc học môn đồ họa, trải rộng từ việc nghiên cứu phần cứng, nghiên cứu các kỹ thuật để hiển thị các đối tượng đồ họa tới việc học để biết cách sử dụng một ứng dụng đồ họa. Ở đây chúng ta tiếp cận môn học từ góc độ của người lập trình ứng dụng, sử dụng tất cả các hỗ trợ của phần cứng, các công cụ phần mềm để xây dựng nên các ứng dụng. 9
Tuy nhiên để có thể thiết kế và cài đặt các chương trình ứng dụng đồ họa được tốt, ngoài việc tìm hiểu các khả năng của công cụ lập trình, chúng ta cũng cần phải nắm vững các khái niệm về phần cứng; các vấn đề, các nguyên lí liên quan đến cài đặt phần mềm, các thuật toán, các ứng dụng, 1.1.2. Lịch sử phát triển Năm 1955, hệ thống phòng không SAGE (Môi trường mặt đất bán tự động) bắt đầu hoạt động, sử dụng màn hình quét vector làm đầu ra chính và Light pen là thiết bị đầu vào và được sử dụng rộng rãi vào năm 1958. Tập đoàn thiết bị kỹ thuật số DEC được thành lập vào năm 1957, bắt đầu chế tạo minicomputers mà sau này được sử dụng phát triển đồ họa máy tính. Năm 1960, nhà khoa học người Mỹ, William Fette nghiên cứu, xây dựng mô hình buồng lái máy bay cho hãng Boeing của Mỹ. Ông đã dựa trên hình ảnh 3 chiều của mô hình người phi công trong buồng lái của máy bay để xây dựng nên một mô hình tối ưu cho buồng lái máy bay. Phương pháp này cho phép các nhà thiết kế quan sát một cách trực quan vị trí của người lái trong khoang. Ông đặt tên cho phương pháp này là đồ hoạ máy tính (Computer Graphics). Màn hình là thiết bị thông dụng nhất trong hệ đồ hoạ, các thao tác của hầu hết các màn hình đều dựa trên thiết kế ống tia âm cực CRT (Cathode ray tube). Khi đó máy tính xử lý chậm, đắt và không chắc chắn (không đáng tin cậy). Vào những năm 1960, lĩnh vực này đã có những phát triển đầu tiên. Năm 1961, Ivan Sutherland phát triển dự án Sketchpad tại MIT. Bảng vẽ được sử dụng và một thiết bị light pen làm thiết bị đầu vào chính, một máy hiện sóng là thiết bị đầu ra. Phiên bản đầu tiên chỉ xử lý các số liệu hai chiều và sau đó được phát triển để vẽ, biến đổi và hiển thị các đối tượng 3 chiều dưới dạng hình chiếu xuống mặt phẳng 2 chiều. Kỹ thuật đồ họa liên tục được phát triển vào những năm 1960 và 1970 kéo theo sự ra đời của các chuẩn đồ họa, làm tăng khả năng giao tiếp và tái sử dụng của phần mềm cũng như các thư viện đồ họa. Sự phát triển đột phá của công nghệ điện tử máy tính vào thập niên 1980 làm xuất hiện một loạt các vi mạch hỗ trợ cho việc truy xuất đồ họa, làm giảm giá thành của máy tính cá nhân. Vào cuối những năm 1980, các máy tính đồ họa SGI (Silicon Graphics Inc.) đã tạo ra một số phim hoạt hình ngắn đầu tiên tại Pixar. Hệ điều hành Microsoft Windows 3.0 được xuất xưởng lần đầu tiên vào năm 1990 thúc đẩy to lớn cho khái niệm GUI (Graphical User Interface). Ngày càng nhiều ứng dụng được phát triển chạy trên MS Windows. OpenGL (Thư viện đồ họa mở) được SGI đưa ra năm 1992. Những năm 1990 cũng chứng kiến sự phát triển nhanh chóng trong đồ họa ba chiều, đặc biệt là trong phát triển game, đa phương tiện và hoạt hình. Quake, một trong những game 3D hoàn chỉnh đầu tiên, đã được phát hành vào năm 1996. 10
Ngày nay, đồ họa có những tác động to lớn đến ngành công nghiệp giải trí, các lĩnh vực khoa học, kỹ thuật, y học, thiết kế trang web, truyền thông, xử lý thông tin thiết lập các tương tác mới từ lớn đến nhỏ các yếu tố thực tế ảo, màn hình cỡ lớn, màn hình thực tế ảo, thiết bị cảm ứng đa điểm và điện thoại thông minh [1][5] Nếu nhìn lịch sử đồ họa theo góc độ phát triển của kỹ thuật hiển thị ta sẽ thấy các kỹ thuật hiển thị phát triển theo những giai đoạn sau: • Kỹ thuật hiển thị bằng ký tự: Kỹ thuật này chỉ cho phép hiển thị text và các hình ảnh đồ họa đơn giản. Giao tiếp với người sử dụng thông qua các lệnh dưới dạng text. Có thể sử dụng những ký tự mã hóa đặc biệt để hiển thị đối tượng. Tất cả các chương trình và phần mềm được thực hiện đều là đơn nhiệm. Ví dụ: - Hệ điều hành MS_DOS. Hệ điều hành tiêu biểu của giai đoạn 80, đầu những năm 90 của Microsoft. - Phần mềm soạn thảo văn bản BKED chạy trên môi trường MS_DOS. • Kỹ thuật hiển thị vector: Kỹ thuật này phát triển từ năm 1963 đến năm 1980, cho phép hiển thị text, các đường thẳng, các hình đơn giản. Giao tiếp với người sử dụng được thực hiện thông qua các dòng lệnh, các phím “nóng” và menu chọn. • Kỹ thuật ảnh 2 chiều: Kỹ thuật này cho phép hiển thị các cửa sổ (window), các biểu tượng (icon), và các dòng văn bản (text). Trong giao tiếp với người sử dụng đã hạn chế việc gõ lệnh, thay vào đó người sử dụng có thể thực hiện thông qua các giao diện đồ họa ( Graphical User Interface) • Trạm làm việc đồ họa ( 3D Graphics Workstation) Công nghệ này được phát triển bởi công ty Silicon Graphics, một trong những công ty phát triển đồ họa hàng đầu của Mỹ. Công nghệ này cho phép hiển thị các hình ảnh thực và hình ảnh thời gian thực 3 chiều của hình ảnh và sự vật dựa trên các cảnh 3 chiều. Môi trường giao tiếp với người sử dụng được xây dựng trên cơ sở các hình ảnh 2 chiều, 3 chiều và mô phỏng thế giới thực. [4] 1.1.3. Một số ứng dụng Như đã nói ở trên, đồ họa máy tính không còn là những gì mới mẻ, xa lạ nữa mà nó trở nên gần gũi và cần thiết trên hầu hết các thiết bị chúng ta sử dụng hàng ngày. Dưới đây là một số các ứng dụng cơ bản của đồ họa máy tính. a, Hỗ trợ thiết kế Một trong những ứng dụng lớn nhất của đồ họa máy tính là hỗ trợ thiết kế (CAD – computer-aided design). Ngày nay CAD đã được sử dụng hầu hết trong việc thiết kế các 11
cao ốc, ô tô, máy bay, tàu thủy, tàu vũ trụ, máy tính, trang trí mẫu vải, và rất nhiều sản phẩm khác. Người ta có thể quan sát các đối tượng được thiết kế qua mô tả trên máy tính theo bất kỳ hướng nào. Những thay đổi trên đối tượng được cập nhật nhanh chóng, được thể hiện thử nghiệm lại ngay. b, Biểu diễn thông tin Các công cụ đồ họa trong các ứng dụng có thể phát sinh các biểu đồ, đồ thị, thuận tiện cho việc minh họa mối quan hệ giữa nhiều đối tượng với nhau. Các biểu đồ có thể dưới dạng 2 chiều, 3 chiều, được biểu diễn trực quan. Trong đó, các ứng dụng thường được dùng để tóm lược các dữ liệu về tài chính, thống kê, kinh tế, khoa học, toán học, giúp cho việc nghiên cứu, quản lí, một cách có hiệu quả. c, Lĩnh vực giải trí, nghệ thuật Trong lĩnh vực nghệ thuật, các chương trình máy tính như Paint Shop Pro, Adobe Photoshop, 3D Studio, hỗ trợ rất đắc lực cho các họa sĩ, các nhà tạo mẫu trong việc thiết kế các hình ảnh sống động, và rất thực. Với các chương trình này, người họa sĩ được máy tính tạo cho cảm giác y như đang làm việc ngoài đời thực bằng cách cung cấp các công cụ như khung vẽ, giá vẽ, bảng pha màu, các hiệu ứng ba chiều, làm cho họ cảm thấy rất thoải mái và tiện lợi. Ngoài ra đồ họa máy tính còn giúp tạo ra các chương trình trò chơi, giải trí; hỗ trợ cho các kĩ xảo điện ảnh, cho các nhà làm phim. Có nhiều bộ phim rất nổi tiếng nhờ vào kĩ xảo điện ảnh như : Công viên Khủng long kỉ Jura (Jurassic Park), Titanic, Thế giới nước (Water World), d, Giáo dục và đào tạo Hiện nay các chương trình mô phỏng cấu trúc của các vật thể, tiến trình của các phản ứng hóa học, hoạt động của các gói tin trên mạng máy tính, được dùng rất nhiều trong việc hỗ trợ giảng dạy. Trong đào tạo, các ứng dụng mô phỏng được dùng để kiểm tra trình độ người lái, huấn luyện phi công, điều khiển giao thông, e, Giao tiếp giữa máy tính và người dùng Mọi ứng dụng đều phải có giao diện giao tiếp với người dùng. Giao diện đồ họa thực sự là một cuộc cách mạng mang lại sự thuận tiện và thoải mái cho người dùng ứng dụng. Các ứng dụng dựa trên hệ điều hành MS Windows là một minh họa rất trực quan của giao diện đồ họa. Các chức năng của các ứng dụng này được thiết kế cho người dùng làm việc thông qua các biểu tượng mô tả chức năng đó. Ví dụ: chức năng lưu tập tin được hiểu thông qua biểu tượng đĩa mềm, chức năng in ấn được hiểu thông qua biểu tượng máy in, Để chọn các chức năng, người dùng sử dụng chuột trỏ đến và nhấn vào các biểu tượng tương ứng. Điểm thuận lợi chính khi dùng 12
biểu tượng là kích thước không gian mà nó chiếm ít hơn nhiều so với dùng văn bản để mô tả cho cùng một chức năng, ngoài ra việc nắm bắt các chức năng qua các biểu tượng sẽ dễ dàng hơn rất nhiều khi người dùng gặp trở ngại về mặt ngôn ngữ. Các ứng dụng có giao diện đồ họa còn cho phép người dùng khả năng làm việc dễ dàng với nhiều cửa sổ với nhiều dạng tài liệu khác nhau cùng một lúc. 1.1.4 Phân loại các lĩnh vực của kỹ thuật đồ hoạ máy tính Có nhiều phương pháp để phân loại các lĩnh vực của đồ hoạ máy tính. a, Phân loại theo tiêu chí là mục đích xử lý dữ liệu trong các lĩnh vực: CAD/CAM Kiến tạo đồ họa Đồ họa hoạt hình và nghệ thuật Đồ họa minh họa Kỹ thuật đồ họa Xử lý ảnh Xử lý đồ họa Kỹ thuật phân tích và tạo ảnh Kỹ thuật nhận dạng - Các hệ CAD/CAM (Computer Aided Design/Computer Aided Manufacture System): kỹ thuật đồ hoạ tập hợp các công cụ, các kỹ thuật trợ giúp cho thiết kế các chi tiết và các hệ thống khác nhau: hệ thống cơ, hệ thống điện, hệ thống điện tử - Đồ hoạ hoạt hình và nghệ thuật: bao gồm các công cụ giúp cho các hoạ sĩ, các nhà thiết kế phim hoạt hình chuyên nghiệp làm các kỹ xảo hoạt hình, vẽ tranh Ví dụ: phần mềm 3D Studio, 3D Animation, 3D Studio Max - Đồ hoạ minh hoạ (Presentation Graphics): gồm các công cụ giúp hiển thị các số liệu thí nghiệm một cách trực quan, dựa trên các mẫu đồ thị hoặc các thuật toán có sẵn. - Kỹ thuật xử lý ảnh (Computer Imaging): sau quá trình xử lý ảnh cho ta ảnh số của đối tượng. Trong quá trình xử lý ảnh sử dụng rất nhiều các kỹ thuật phức tạp: kỹ thuật khôi phục ảnh, kỹ thuật làm nổi ảnh, kỹ thuật xác định biên ảnh. - Kỹ thuật phân tích và tạo ảnh (Image Synthesis): là lĩnh vực xây dựng mô hình và hình ảnh của các vật thể dựa trên các đối tượng và mối quan hệ giữa chúng. - Kỹ thuật nhận dạng (Pattern Recognition): từ những ảnh mẫu có sẵn ta phân loại theo cấu trúc, hoặc theo các tiêu chí được xác định từ trước và bằng các thuật toán chọn lọc để có thể phân tích hay tổng hợp ảnh đã cho thành một tập hợp các ảnh gốc, các ảnh 13
gốc này được lưu trong một thư viện và căn cứ vào thư viện này ta xây dựng được các thuật giải phân tích và tổ hợp ảnh. b, Phân loại theo hệ toạ độ dùng trong thuật đồ họa: Kỹ thuật đồ họa 2 chiều Kỹ thuật đồ họa Kỹ thuật đồ họa 3 chiều - Kỹ thuật đồ hoạ hai chiều: là kỹ thuật đồ hoạ máy tính sử dụng hệ toạ độ hai chiều (hệ toạ độ phẳng), sử dụng rất nhiều trong kỹ thuật xử lý bản đồ, đồ thị. - Kỹ thuật đồ hoạ ba chiều: là kỹ thuật đồ hoạ máy tính sử dụng hệ toạ độ ba chiều, đòi hỏi rất nhiều tính toán và phức tạp hơn nhiều so với kỹ thuật đồ hoạ hai chiều.[1] 1.2. Tổng quan về một hệ đồ họa Một trong các yêu cầu chính của một hệ thống đồ họa là các ứng dụng có thể thực thi trên nhiều hệ thiết bị, được phát triển không phụ thuộc vào phần cứng. Để có được điều đó, phải có tiêu chuẩn hóa cho môi trường đồ họa ở mức chức năng, bằng việc cung cấp sự độc lập thiết bị và ngôn ngữ lập trình. Sự độc lập với thiết bị cho phép các chương trình ứng dụng đồ họa chạy trên các hệ thống phần cứng khác nhau. Điều này được thực hiện thông qua thiết bị nhập xuất logic của thư viện đồ họa ánh xạ thiết bị cụ thể. Cho tới nay, có những tiêu chuẩn đồ họa đã được phát triển trong nhiều năm, bao gồm: - GKS(Graphics Kernel System - 1985), phát triển riêng cho các thiết bị nhập xuất 2 chiều. - GKS-3D bổ sung thêm khả năng lập trình 3 chiều. - CGI ( Computer Graphics Interface System): Hệ chuẩn cho các phương pháp giao tiếp với các thết bị ngoại vi. - CGM ( Computer Graphics Metafile): Xác định các chuẩn cho việc lưu trữ và chuyển đổi hình ảnh. - VRML ( Virtual Reality Modeling Language): Ngôn ngữ thực tại ảo, một hướng phát triển trong công nghệ hiển thị được đề xuất bởi công ty Silicon Graphics, sau đó được chuẩn hóa như một chuẩn công nghiệp. - PHIGS (Programmer’s Hierarchical Interactive Graphics Standar): Xác định các phương pháp chuẩn cho mô hình thời gian thực và lập trình hướng đối tượng. - PHIGS+ bao gồm khả năng lập trình không gian, tạo thành thao tác dữ liệu đồ họa phức tạp 14
- OPENGL: Thư viện đồ họa của hãng Silicon Graphics, được xây dựng theo đúng chuẩn của một hệ đồ họa – năm 1993. - DIRECTX: Thư vện đồ họa của hãng Microsoft. Các tiêu chuẩn đồ họa thực tế là kết quả của việc chấp nhận trong công nghiệp thiết kế các giao diện đặc trưng, được đề xuất bởi nhiều công ty. Để đảm bảo sự linh hoạt, các tiêu chuẩn đồ họa thiết lập cho các thay đổi tối thiểu, cho phép định địa chỉ các thiết bị nhập xuất khác nhau. Khởi đầu, người lập trình tạo ra một hệ thống tọa độ mô hình, mô tả đối tượng gọi là hệ thống tọa độ thực. Tiếp theo, là hệ tọa độ tiêu chuẩn và hệ tọa độ thiết bị. Chương trình ứng dụng sẽ giao tiếp với hệ tọa độ chuẩn theo cách thức phù hợp, không quan tâm đến thiết bị xuất được dùng. Do đó, tạo ra sự độc lập với thiết bị trong việc tạo ra hình ảnh của đối tượng 1.2.1. Phần cứng đồ họa Phần cứng đồ họa bao gồm các thành phần: ✓ CPU: Thực hiện các chương trình ứng dụng. ✓ Bộ xử lý hiển thị (Display Processor): Thực hiện công việc hiển thị dữ liệu đồ hoạ. ✓ Bộ nhớ hệ thống (System Memory): Chứa các chương trình và dữ liệu đang thực hiện. ✓ Bộ đệm ( Frame buffer): Chứa các hình ảnh hiển thị. ✓ Bộ điều khiển màn hình (Video Controller): Điều khiển màn hình, chuyển dữ liệu dạng số ở frame buffer thành các điểm sáng trên màn hình. 1.2.2. Phần mềm đồ họa Phần mềm đồ họa bao gồm các công cụ lập trình cung cấp một tập các hàm đồ họa có thể được dùng trong các ngôn ngữ lập trình cấp cao. Các hàm cơ sở của nó bao gồm việc tạo các đối tượng cơ sở của hình ảnh như đoạn thẳng, đa giác, đường tròn, thay đổi màu sắc, chọn khung nhìn, áp dụng các phép biến đổi. Các ứng dụng đồ họa được thiết kế cho những người dùng không phải là lập trình viên, cho phép người dùng tạo các đối tượng, hình ảnh, mà không cần quan tâm tới việc chúng được tạo ra như thế nào. Ví dụ như là Photoshop, AutoCAD, Khi các ứng dụng được thiết kế với các hàm đồ họa chuẩn, nó có thể thực thi được trên nhiều hệ thống khác nhau và được tái sử dụng trong nhiều ứng dụng khác nhau. 1.3 Các kỹ thuật đồ họa Ngày nay, số lượng các hệ thống sử dụng kỹ thuật đồ họa tương tác đã trở nên rất lớn, ngày càng nhiều và càng trở nên đa dạng hơn, phong phú hơn. Tuy vậy, căn cứ vào phương pháp xử lý các dữ liệu trong hệ thống mà người ta phân biệt ra hai hệ thống đồ họa: Kỹ thuật đồ họa điểm (Sample based – Graphics) và kỹ thuật đồ họa vector ( Geometry based – Graphics). 15
1.3.1 Kỹ thuật đồ hoạ điểm Các mô hình, hình ảnh của các đối tượng được hiển thị thông qua từng pixel (từng mẫu rời rạc) trong kỹ thuật này ta có thể: - Tạo ra, thay đổi các thuộc tính, xóa đi từng pixel của mô hình và hình ảnh các đối tượng. - Các mô hình hình ảnh được hiển thị như một lưới điểm (grid) các pixel rời rạc. - Từng pixel đều có vị trí xác định, được hiển thị với một giá trị rời rạc (số nguyên) các thông số hiển thị (màu sắc hoặc độ sáng) Tập hợp tất cả các pixel cho chúng ta mô hình, hình ảnh đối tượng mà chúng ta muốn hiển thị. Có 2 phương pháp để tạo ra các pixel: - Phương pháp dùng phần mềm để vẽ trực tiếp từng pixel một. Dựa trên các lý thuyết mô phỏng để xây dựng nên hình ảnh mô phỏng của sự vật. - Phương pháp rời rạc hoá (số hoá) hình ảnh thực của đối tượng. Có thể sửa đổi (image editing) hoặc xử lý (image processing) mảng các pixel thu được theo những phương pháp khác nhau để thu được hình ảnh đặc trưng của đối tượng. 1.3.2 Kỹ thuật đồ họa vector Nguyên lý xây dựng các mô hình, hình ảnh trong kỹ thuật đồ họa vector như sau: - Xây dựng mô hình hình học (geometrical model) cho mô hình hoặc hình ảnh của đối tượng. - Xác định các thuộc tính của mô hình hình học này. - Quá trình tô trát (rendering) để hiển thị từng điểm của mô hình, hình ảnh thực của đối tượng. Trong kỹ thuật đồ họa vector, chỉ lưu trữ mô tả toán học của các thành phần trong mô hình hình học cùng với các thuộc tính tương ứng của nó mà không lưu lại toàn bộ các pixel của mô hình tô trát ( rendering) được. Các thành phần được mô tả trong mô hình hình học của đối tượng được gọi là các thực thể hình học cơ sở, các đối tượng hình ảnh sẽ được xây dựng từ những thực thể cơ sở này. Hình ảnh được tô trát từ nhiều góc nhìn và điểm nhìn khác nhau. So sánh giữa 2 kỹ thuật đồ họa điểm và đồ họa vector: Đồ hoạ điểm Đồ hoạ vector - Hình ảnh và mô hình của các đối tượng - Hình ảnh và mô hình của các đối tượng được biểu diễn bởi tập hợp các điểm của được biểu diễn bởi tập hợp các thực thể lưới (grid) hình học cơ sở - Thay đổi thuộc tính của các pixel dẫn đến - Xử lý với từng thành phần hình học cơ thay đổi từng phần và từng vùng của đối sở của đối tượng và thực hiện quá trình tô tượng. trát, hiển thị. 16
Đồ hoạ điểm Đồ hoạ vector - Copy được các pixel từ một hình ảnh - Quan sát hình ảnh và mô hình của hình này sang hình ảnh khác. ảnh và sự vật ở nhiều góc độ khác nhau bằng cách thay đổi điểm nhìn và góc nhìn.[1] 17
Câu hỏi ôn tập: 1. Trình bày một số mốc lịch sử phát triển của đồ họa máy tính 2. Trình bày một số ứng dụng của đồ họa máy tính trong các lĩnh vực: giáo dục, y tế, giải trí, nghệ thuật, kỹ thuật 3. Tại sao phải sử dụng các chuẩn đồ họa, nêu một số chuẩn đồ họa? 4. Trình bày tổng quan về phần cứng, phần mềm đồ họa. 5. Trình bày về kỹ thuật đồ họa điểm và kỹ thuật đồ họa vector. 6. Phân biệt giữa đồ họa điểm và đồ họa vector. 18
CHƯƠNG 2: ĐỒ HỌA 2 CHIỀU Mục tiêu của chương: Sinh viên cần nắm được các thuật toán DDA, Bresenham, Midpoint vẽ các đường cơ bản như đường thẳng, đường tròn, có khả năng cài đặt các thuật toán này bằng ngôn ngữ C, C++ Có thể thực hiện tính toán được ảnh của các điểm 2D sau các phép biến đổi: Tỷ lệ tâm O(0,0), tâm bất kỳ, phép tịnh tiến, phép quay tâm O(0,0,0), quay tâm bất kỳ, và các phép lấy đối xứng qua qua trục tọa độ, gốc tọa độ. Sinh viên cần nắm được các tính chất của các phép biến đổi Affine trên đối tượng đồ họa 2D, hiểu và cài đặt được các thuật toán xén đoạn thẳng: Cohen-Sutherland và Liang- Barsky. 2.1. Giới thiệu về các đối tượng đồ họa cơ sở 2.1.1 Mở đầu Bất kì một ảnh mô tả thế giới thực nào bao giờ cũng được cấu trúc từ tập các đối tượng đơn giản hơn. Với các ảnh đồ họa phát sinh bằng máy tính, hình dạng và màu sắc của mỗi đối tượng có thể được mô tả riêng biệt bằng hai cách: - Bằng dãy các pixel tương ứng - Bằng tập các đối tượng hình học cơ sở như: đoạn thẳng, vùng tô đa giác, Sau đó, các ảnh sẽ được hiển thị bằng cách nạp các pixel vào vùng đệm khung. Với các ảnh được mô tả bằng các đối tượng hình học cơ sở, cần phải có một quá trình chuyển các đối tượng này về dạng ma trận các pixel trước. Quá trình này còn được gọi là quá trình chuyển đổi bằng dòng quét (scan- converting). Bất kì công cụ lập trình đồ họa nào cũng cung cấp các hàm để mô tả một ảnh dưới dạng các đối tượng hình học cơ sở hay còn gọi là các đối tượng đồ họa cơ sở (output primitives) và các hàm cho phép kết hợp tập các đối tượng cơ sở để tạo thành đối tượng có cấu trúc phức tạp hơn. Mỗi đối tượng đồ họa cơ sở được mô tả thông qua dữ liệu về tọa độ và các thuộc tính của nó, đây chính là thông tin cho biết kiểu cách mà đối tượng được hiển thị. Đối tượng đồ họa cơ sở đơn giản nhất là điểm và đoạn thẳng, ngoài ra còn có đường tròn, và các đường conics, mặt bậc hai, các mặt và đường cong, các vùng tô đa giác, chuỗi kí tự, cũng được xem là các đối tượng đồ họa cơ sở để giúp xây dựng các ảnh phức tạp. Chương này sẽ khảo sát các thuật toán hiển thị các đối tượng đồ họa cơ sở cho các thiết bị hiển thị dạng điểm. Xét về mặt bản chất, các thuật toán này thực hiện quá trình chuyển đổi các đối tượng đồ họa cơ sở được mô tả trong hệ tọa độ thực về dãy các pixel có tọa độ nguyên của thiết bị hiển thị. Có hai yêu cầu đặt ra cho các thuật toán đó là: 19
Đối tượng được mô tả trong hệ tọa độ thực là đối tượng liên tục, còn đối tượng trong hệ tọa độ thiết bị là đối tượng rời rạc, do đó bản chất của quá trình chuyển đổi này chính là sự rời rạc hóa và nguyên hóa các đối tượng sao cho có thể xác định các điểm nguyên xấp xỉ đối tượng một cách tốt nhất, thực nhất. Nghĩa là đối tượng hiển thị bằng lưới nguyên trên thiết bị hiển thị phải có hình dạng tương tự như đối tượng trong lưới tọa độ thực và “có vẻ” liên tục, liền nét. Sự liên tục trên lưới nguyên của thiết bị hiển thị có được do mắt người không thể phân biệt được hai điểm quá gần nhau. Do các đối tượng đồ họa cơ sở là thành phần chính cấu trúc các đối tượng phức tạp nên các thuật toán hiển thị chúng cần phải được tối ưu hóa về mặt tốc độ, đây chính là điểm mấu chốt cho việc ra đời các thuật toán khác nhau. 2.1.2 Các hệ tọa độ a, Hệ tọa độ thế giới thực Hệ tọa độ thế giới thực (hay hệ tọa độ thực) là hệ tọa độ được dùng mô tả các đối tượng thế giới thực. Một trong các hệ tọa độ thực thường được dùng nhất đó là hệ tọa độ Descartes. Với hệ tọa độ này, bất kì một điểm nào trong mặt phẳng cũng được mô tả bằng một cặp tọa độ (x, y) trong đó x, y R. Các tọa độ thế giới thực cho phép người dùng sử dụng bất kì một thứ nguyên (dimension) quy ước như foot, cm, mm, km, inch, nào và có thể lớn nhỏ tùy ý. b, Hệ tọa độ thiết bị Hệ tọa độ thiết bị là hệ tọa độ được dùng bởi một thiết bị xuất cụ thể nào đó như máy in, màn hình , Đặc điểm chung của các hệ tọa độ thiết bị đó là: - Các tọa độ x, y (x,y N) của hệ tọa độ thiết bị đều bị giới hạn trong một khoảng nào đó (do kích thước của thiết bị). - Khoảng giới hạn các tọa độ x, y là khác nhau đối với từng loại thiết bị khác nhau. c. Hệ tọa độ thiết bị chuẩn Do cách định nghĩa các hệ tọa độ thiết bị khác nhau nên một hình ảnh được hiển thị trên thiết bị này là chính xác nhưng có thể không được hiển thị chính xác ở thiết bị khác. Người ta xây dựng một hệ tọa độ thiết bị chuẩn ( NDCS – Normalized Device Coordinate System) đại diện chung cho tất cả các thiết bị để có thề mô tả các hình ảnh mà không phụ thuộc vào bất kỳ thiết bị nào. Trong hệ tọa độ thiết bị chuẩn, các tọa độ x, y sẽ được gán các giá trị trong đoạn [0,1]. Như vậy, vùng không gian của hệ tọa độ chuẩn chính là hình vuông đơn vị có góc trái dưới (0,0) và góc phải trên (1,1) 2.1.3 Các đối tượng đồ họa cơ sở a. Điểm: Điểm là thành phần cơ sở được định nghĩa trong một hệ tọa độ. Đối với hệ tọa độ hai chiều mỗi điểm được xác định bởi cặp tọa độ (x, y). 20
Ngoài thông tin về tọa độ, điểm còn có thuộc tính màu sắc. b. Đoạn thẳng: Một đường thẳng có thể xác định nếu biết hai điểm thuộc nó. Phương trình đường thẳng đi qua hai điểm (x1, y1) và (x2,y2) có dạng y = mx + b, trong đó: m=Dy/Dx là hệ số góc của đường thẳng, với Dy = y2 - y1, Dx = x2 - x1 Dưới dạng phương trình tham số, ta có: x = x1 + (x2-x1)t y = y1 + (y2-y1)t - Nếu t 0,1], ta có các điểm (x,y) thuộc về đoạn thẳng giới hạn bởi hai điểm (x1, y1) và (x2, y2), - Nếu t − ,+ , ta sẽ có đường thẳng. Các thuộc tính của đoạn thẳng: • Màu sắc • Độ rộng của nét vẽ • Kiểu nét vẽ của đoạn thẳng: nét liền, nét gạch, chấm gạch, Hầu hết các công cụ đồ họa đều định nghĩa tập các kiểu nét vẽ đoạn thẳng và cho phép người dùng định nghĩa thông qua một mẫu (pattern). c. Vùng tô Một vùng tô bao gồm đường biên và vùng bên trong. Đường biên là một đường khép kín. Các thuộc tính của vùng tô bao gồm: • Thuộc tính của đường biên: như thuộc tính của đoạn thẳng. • Thuộc tính của vùng bên trong: màu tô và mẫu tô d. Kí tự, chuỗi kí tự Các chuỗi kí tự giúp hiển thị nội dung các thông điệp theo một ngôn ngữ nào đó. Các thuộc tính của kí tự bao gồm : • Màu sắc của các kí tự. • Font chữ: bộ kí tự dùng hiển thị; Nó định nghĩa kiểu, kích thước của kí tự hiển thị. Hình dạng của mỗi kí tự có thể được xác định bởi một tập các đường gấp khúc (trường hợp font vector) hay là mẫu các pixel (font bitmap). Có nhiều loại font khác nhau như: font bitmap, font truetype, font CHR, • Kích thước: Chiều cao và chiều rộng của kí tự. Các kí tự định nghĩa bằng đường gấp khúc có thể dễ dàng thay đổi kích thước hơn là các kí tự định nghĩa bằng mẫu các 21
pixel. • Khoảng cách giữa các kí tự. • Sự canh lề: canh trái (left text), canh phải (right text), canh giữa (center text), canh hai lề (justify text). • Cách hiển thị tuần tự của các kí tự: có thể là phải sang trái, từ trên xuống dưới, từ trái sang phải, từ dưới lên trên. • Hướng của kí tự [2] 2.2. Các thuật toán vẽ đường thẳng 2.2.1 Mở đầu Ta cần vẽ đoạn thẳng có hai điểm đầu cuối là P1(x1,y1), P2(x2,y2) lên trên một thiết bị hiển thị (màn hình ), có nghĩa là ta cần phải tính toán xem pixel nào sẽ lần lượt được hiển thị sao cho đoạn thẳng hiển thị “giống” với đoạn thẳng thực muốn vẽ nhất. Tọa độ các pixel được hiển thị là các điểm nguyên sau khi xấp xỉ đối tượng thực lần lượt là (xi, yi ),i = 0, 1 Vậy, nếu biết được (xi, yi ) là tọa độ nguyên xác định ở bước thứ i, điểm nguyên tiếp theo (xi+1, yi+1) sẽ được xác định như thế nào? Nhận xét rằng: để đối tượng hiển thị trên lưới nguyên được liền nét, các điểm mà (xi+1, yi+1 ) có thể chọn chỉ là một trong 8 điểm được đánh số từ 1 đến 8 trong hình 1. y i x i Hình 2.1: Các điểm lân cận của (xi, yi) Ta có tọa độ các điểm là: 1(xi +1, yi ) (xi , yi +1) (xi - 1, yi ) (xi, yi −1) (xi +1, yi +1) (xi -1, yi +1) (xi −1, yi −1) (xi +1, yi −1) Phương của đường thẳng sẽ cho ta gợi ý khi chọn một trong 8 điểm trên. Cách chọn các điểm như thế nào sẽ tùy thuộc vào từng thuật toán trên cơ sở xem xét tới vấn đề tối ưu tốc độ. 22
Xét đường thẳng có hệ số góc 0 m 1 và Dx 0. Hình 2.2: Đường thẳng có hệ số góc 0 m 1 Với các đường thẳng dạng này, nếu (xi, yi ) là điểm đã xác định được ở bước thứ i (điểm màu đen) thì điểm cần chọn (xi+1, yi+1) ở bước thứ (i+1) sẽ là một trong hai điểm 1(xi +1, yi ) hoặc (xi +1, yi +1) như hình 2 trên. Như vậy, trong trường hợp 0 m 1, ta có: xi+1 = xi +1, yi+1 { yi, yi + 1 } 2.2.2 Thuật toán DDA (Digital Differential Analyzer ) Với thuật toán DDA, việc quyết định chọn yi+1 là yi hay yi +1 , dựa vào phương trình y = mx + b của đoạn thẳng . yi+1 2 t y i+1 Q yi 2 1 xi xi+1 Hình 2.3: Minh họa thuật toán DDA trường hợp 0 <m <1 t Q(xi+1,y i+1) thuộc đường thẳng thực, ta có: yt = mx + b i+1 i+1 = m(xi + 1) +b = mxi + b + m t t ➔ y i+1 = y i + m t t y là giá trị sau khi làm tròn y i+1, vậy y = round(y ) i+1 i+1 i+1 Do vậy: y = round(yt + m) i+1 i 23
Begin m = Dy/Dx; x = x1; y = y1; putpixel(x,y,c); Sai x ≤ x2 Đúng x = x+1; y = y+m; putpixel(x,round(y),c) ; End Hình 2.3: Lưu đồ thuật toán vẽ đường thẳng DDA Cài đặt minh họa: void DDA_line (int x1, int y1, int x2, int y2, int c) { float m = (float)(y2-y1)/(x2-x1); int x=x1; float y=y1; putpixel(x,round(y),c); for(int i=x1; i<=x2; i++) { x++; y=y+m; putpixel(x,round(y),c); } } 24
Nhận xét: t t • Việc sử dụng công thức y i+1 = y i + m để tính giá trị y tại mỗi bước đã giúp cho thuật toán DDA cải thiện tốc độ so với cách tính y từ phương trình y = mx + b do khử được phép nhân trên số thực. • Tuy nhiên vẫn còn tồn tại phép toán cộng số thực và phép làm tròn. Để cải thiện tốc độ hơn nữa, ta phải thực hiện loại bỏ được các phép toán trên tập số thực như thuật toán Bresenham sau đây.[1][3] 2.2.3 Thuật toán Bresenham Thuật toán Bresenham đưa ra cách chọn yi+1 là yi hay yi +1 một hướng khác, sao cho có thể tối ưu hóa về mặt tốc độ so với thuật toán DDA. Q thuộc đường thẳng thực, ta có: y = mxi+1 + b → y = m(xi +1) +b yi+1 2 d2 y y Q d1 yi 2 1 xi xi+1 Hình 2.4: Minh họa thuật toán Bresenham, 0<m<1 Đặt: d1=y-yi d2=yi+1 – y Pi = Dx(d1-d2) = Dx(2y-2yi -1) Do m = Dy/Dx, ta có: Pi = 2xiDy – 2yiDx + c với c = 2Dy + (2b - 1)Dx Nhận xét rằng do Dx 0 nên dấu của biểu thức d1 − d2 cũng chính là dấu của Pi . Hay nói một cách khác, nếu tại bước thứ i ta xác định được dấu của Pi thì xem như ta xác định được điểm cần chọn ở bước (i+1). Vấn đề còn lại là làm thế nào để tính được Pi tại mỗi bước thật nhanh. Ta có: Pi+1 = 2xi+1Dy – 2yi+1Dx + c Tính: Pi+1 - Pi = 2Dy(xi+1 - xi ) – 2Dx(yi+1 - yi ) do xi+1 = xi +1, suy ra: Pi+1 - Pi = 2Dy - 2Dx(yi+1 - yi ) 25
- Nếu Pi < 0  d1<d2 → điểm Q “gần” điểm 1 hơn nên bước thứ i+1 vẽ điểm 1, Vậy yi+1=yi → Pi+1 - Pi = 2Dy - Nếu Pi ≥ 0  d1≥d2 → điểm Q “gần” điểm 2 hơn nên bước thứ i+1 vẽ điểm 2, Vậy yi+1=yi+1 → Pi+1 - Pi = 2Dy - 2Dx Giá trị P1 được tính từ điểm vẽ đầu tiên (x1, y1 ) theo công thức : P1 = 2Dyx1 − 2Dxy1 + c = 2Dyx1 − 2Dxy1 + 2Dy + (2b −1)Dx  P1 = 2Dy-Dx + 2Dyx1 − 2Dxy1 +2b Do (x1, y1 ) là điểm nguyên thuộc đoạn thẳng, ta có y1 = mx1 + b, m=Dy/Dx, Thế vào phương trình trên, suy ra : P1 = 2Dy − Dx. Lưu đồ giải thuật Bresenham: Begin x = x1; y = y1; Dx=x2-x1;Dy=y2-y1; P = 2Dy-2Dx Putpixel(x,y,c) Sai x ≤ x2 Đúng Sai P<0 Đúng P=P+2Dy-2Dx y=y+1; P=P+2Dy x = x+1 Putpixel(x,y,c) End Hình 2.5: Lưu đồ thuật toán vẽ đường thẳng Bresenham 26
Cài đặt minh họa: void Bre_line(int x1, int y1, int x2, int y2, int c) { int x, y, dx, dy, P, C1, C2; y = y1; Dx = x2 - x1; Dy = y2 - y1; P = 2*Dy - Dx; C1 = 2*Dy; C2 = 2*(Dy - Dx); for (x=x1; x<=x2; x++) { putpixel(x, y, c); if (P < 0) P += C1; else { P +=C2; y++; } } } Nhận xét: • Thuật toán Bresenham đã khử được các phép toán trên tập số thực • Các thao tác trên tập số thực là phép cộng. Do đó, thuật toán Bresenham đã cải thiện tốc độ đáng kể so với thuật toán DDA.[1] 2.2.4 Thuật toán Midpoint vẽ đường thẳng Thuật toán đưa ra cách chọn yi+1 là yi+1 hay yi bằng cách so sánh vị trí tương đối giữa trung điểm M(x +1, y + 1/2) của điểm 1 và 2 với đường thẳng thực. i i • Nếu điểm M nằm phía trên đường thẳng thực, ta chọn vẽ điểm 1 hay yi+1=yi (1) 27
• Ngược lại, nếu điểm M thuộc hoặc nằm phía dưới đường thẳng thực, ta chọn vẽ điểm 2 hay yi+1=yi +1 (2) yi+1 2 y+1/2 M yi 2 1 xi xi+1 Hình 2.6: Minh họa thuật toán Midpoint vẽ đường thẳng Từ phương trình của đường thẳng y = mx + b, m= Dx/Dy, suy ra: xDy – yDx + c = 0 Đặt F(x,y)= xDy - yDx + c. Ta có nhận xét sau: - Nếu M thuộc đường thẳng => F(M) = 0 (3) - Nếu M nằm phía trên đường thẳng => F(M) F(M) >0 (5) Đặt Pi =F(M)=F(xi +1, yi + 1/2),  Pi = 2(xi+1)Dy - 2(yi+1/2)Dx + 2c Tính: Pi+1 - Pi = 2Dy(xi+1 - xi ) – 2Dx(yi+1 - yi ) do xi+1 = xi +1, ta có: Pi+1 - Pi = 2Dy - 2Dx(yi+1 - yi ) - Từ (1) và (4) ta có: Nếu Pi < 0 bước thứ i+1 vẽ điểm 1, Vậy yi+1=yi → Pi+1 - Pi = 2Dy (a) - Từ (2), (3), (5) ta có: Nếu Pi ≥ 0 bước thứ i+1 vẽ điểm 2, Vậy yi+1=yi+1 → Pi+1 - Pi = 2Dy - 2Dx (b) Giá trị P1 được tính từ điểm vẽ đầu tiên (x1, y1 ) theo công thức : P1 = F(x1 +1, y1 + 1/2) = 2(x1+1)Dy – 2( y1+1/2)Dx +2 c P1= 2(x1Dy – y1Dx + c) + 2Dy – Dx, do (x1,y1) thuộc đường thẳng nên x1Dy – y1Dx + c =0 vậy suy ra P1= 2Dy – Dx (c) Nhận xét: từ (a), (b), (c) ta có thuật toán MidPoint cho kết quả tương tự như thuật toán Bresenham 28
2.3. Thuật toán Midpoint vẽ đường tròn Do tính đối xứng của đường tròn nên ta chỉ cần khảo sát trên 1/8 đường tròn, sau đó lấy đối xứng. Giả sử P1(x,y) là một điểm bất kỳ trên cung được khảo sát (cung tô màu xám). Các vị trí đối xứng với P qua các trục tọa độ và các đường phân giác là (±x, ±y) và (±y, ±x). P8 P1 2 2 P7 P2 2 2 P6 P3 2 2 P5 P4 2 2 Hình 2.7: Các vị trí đối xứng của đường tròn Chọn điểm bắt đầu vẽ là điểm (0,R), nếu điểm (xi,yi) là điểm nguyên được vẽ ở bước thứ i thì bước thứ i+1 có thể chọn vẽ điểm 1(xi+1,yi-1) hoặc 2(xi+1,yi) Vậy tại bước i+1 ta có: xi+1 = xi+1 yi+1 {yi,yi - 1} yi 2 M(xi+1,yi -1/2) yi-1 1 xi xi+1 Hình 2.8: Minh họa thuật toán Midpoint vẽ đường tròn Tương tự như thuật toán MidPoint vẽ đoạn thẳng, việc quyết định chọn một trong hai điểm 1 và 2 sẽ được thực hiện thông qua việc xét dấu của hàm F(x,y) tại điểm M là trung điểm nằm giữa chúng. Trong đó F(x,y) = x2 + y2 – R2. Ta có nhận xét: 29
- F(x,y) > 0 nếu điểm (x,y) nằm ngoài đường tròn - F(x,y) =0 nếu điểm (x,y) nằm trên đường tròn - F(x,y) < 0 nếu điểm (x,y) nằm trong đường tròn 2 2 2 Đặt Pi = F(M) = (xi+1) + (yi -1/2) – R 2 2 2 2 Tính Pi+1 – Pi = (xi+1 +1) + (yi+1 -1/2) - (xi+1) - (yi -1/2) 2 2 = 2xi+ 3 + (y i+1– y i) – ( yi+1 – yi) - Nếu Pi= F(M) ≥ 0 thì M nằm trên hoặc nằm phía ngoài đường tròn, vậy bước thứ i+1 vẽ điểm 1 hay yi+1 = yi-1, suy ra: Pi+1=Pi + 2xi - 2yi +5 - Nếu Pi < 0 thì M nằm phía trong đường tròn, bước thứ i+1 vẽ điểm 2 hay yi+1 = yi , Suy ra: Pi+1=Pi + 2xi +3 Tính P1 ứng với điểm ban đầu (0,R): P1 = F(0+1, R-1/2) = 5/4 – R ≈ 1-R Begin x=0; y=R; P=1-R; Putpixel(x,y,c) Sai x < y Đúng Sai P < 0 Đúng P=P+2x-2y+5; y=y-1; P = P + 2x+3; x=x+1; Putpixel(x,y,c); End Hình 2.9: Lưu đồ giải thuật Midpoint vẽ đường tròn 30
Cài đặt minh họa: void MP_circle(int R) { int x, y; x = 0; y = R; P = 1 - R; PutPixel(x, y,c); while (x < y) { if (P < 0) P += 2*x + 3; else { P += 2*(x -y) + 5; y ; } x++; PutPixel(x, y,c); } } 2.4 Các phép biến đổi cơ sở của đối tượng 2 chiều 2.4.1 Mở đầu a, Phép biến đổi: Một trong những ưu điểm quan trọng của đồ họa là cho phép dễ dàng thao tác lên các đối tượng đã được tạo ra. Một nhà quản lí có nhu cầu thu nhỏ các biểu đồ trong một báo cáo, một kiến trúc sư muốn nhìn tòa nhà ở những góc nhìn khác nhau, một nhà thiết kế muốn quan sát và chỉnh sửa các mẫu đối tượng trong quá trình thiết kế, Tất cả các thao tác này có thể được hỗ trợ một cách dễ dàng nhờ vào các phép biến đổi hình học. Các phép biến đổi hình học sẽ làm thay đổi mô tả về tọa độ của các đối tượng, từ đó làm cho đối tượng bị thay đổi về hướng, kích thước và hình dạng. Các phép biến đổi hình học cơ sở bao gồm : tịnh tiến (translation), quay (rotation) và biến đổi tỉ lệ (scaling). Một phép biến đổi là một ánh xạ T được định nghĩa: T : R2 → R2 P (x,y) Q (x,y) 31
Nói cách khác, T là hàm số T(x, y) theo hai biến (x, y): x’= f(x,y) y’=g(x,y) Phép biến đổi Affine là phép biến đổi với f(x, y) và g(x, y) là các hàm tuyến tính. Phép biến đổi này có dạng : x’= ax + cy + e y’ = bx + dy + f với a,b,c,d,e,f R , ad – bc ≠ 0 b, Hệ tọa đồ thuần nhất và ma trận thuần nhất: Tọa độ thuần nhất của một điểm trên mặt phẳng được biểu diễn bằng bộ ba số tỉ lệ (xh, yh,h) không đồng thời bằng 0 và liên hệ với các tọa độ (x, y) của điểm đó bởi công thức: x = xh/h, y = yh/h với h ≠ 0 Nếu một điểm có tọa độ thuần nhất là (x, y, t) thì nó cũng có tọa độ thuần nhất là (h.x,h.y,h.t) trong đó h là số thực khác 0 bất kì. Để đơn giản, ta chọn h = 1, lúc này mỗi điểm P(x, y) sẽ được biểu diễn dưới dạng tọa độ thuần nhất là (x, y,1). Một phép biến đổi tổng quát: x’= ax + cy + e y’ = bx + dy + f với a,b,c,d,e,f R , ad – bc ≠ 0 sẽ có ma trận thuần nhất tổng quát tương ứng là: a b 0 M= c d 0 e f 1 2.4.2 Phép tịnh tiến Phép tịnh tiến thực hiện di chuyển vị trí của một điểm P(x,y) tới vị trí Q(x’,y’) theo vector độ dời (dx,dy), ta có: y x’= x+dx y’=y+dy Ma trận của phép biến đổi: 1 0 0 MT = 0 1 0 x dx dy 1 Hình 2.10: Minh họa phép tịnh tiến 32
Phép biến đổi tịnh tiến được biểu diễn như sau: Q = P.MT 1 0 0 (x’ y’ 1) = (x y 1). 0 1 0 dx dy 1 Ví dụ: Tịnh tiến điểm P(6,1) theo vector độ dời (-4,2) được ảnh Q(x’,y’), ta có: x’= 6 – 4  vậy Q(2,3) y’ = 1 +2 Chúng ta có thể dịch chuyển toàn bộ một đối tượng bằng cách áp dụng quy tắc trên cho mọi điểm thuộc đối tượng. Để tịnh tiến một đoạn thẳng, ta thực hiện tịnh tiến hai điểm đầu và cuối của nó rồi sau đó vẽ lại đoạn thẳng nối hai điểm mới. Với đa giác, ta tịnh tiến các đỉnh của nó sau đó vẽ lại đa giác với các đỉnh mới. Tương tự, để tịnh tiến các đối tượng như đường tròn, ellipse, ta tịnh tiến tâm của chúng tới vị trí mới rồi vẽ lại. [1] 2.4.3 Phép biến đổi tỷ lệ tâm O(0,0) Phép biến đổi tỉ lệ làm thay đổi kích thước, hình dạng của đối tượng. Co hay giãn tọa độ của một điểm P(x, y) theo trục hoành và trục tung với tỷ lệ lần lượt là Sx và Sy được điểm Q(x’,y’): x’= x.Sx y y’=y.Sy Ma trận của phép biến đổi: Sx 0 0 x Ms = 0 Sy 0 Hình 2.11: Minh họa phép biến đổi tỷ lệ 0 0 1 Nhận xét: - Nếu Sx, Sy > 1 ta có phép phóng to, và ảnh Q của P sẽ rời xa gốc tọa độ hơn P. - Nếu Sx, Sy < 1 ta có phép thu nhỏ và ảnh Q sẽ tiến lại gần gốc tọa độ hơn P. - Nếu Sx = Sy ta có phép biến đổi đồng dạng. 33
Phép biến đổi tỷ lệ được biểu diễn như sau: Q = P.MS Sx 0 0 (x’ y’ 1) = (x y 1). 0 Sy 0 0 0 1 2.4.4 Phép quay tâm O(0,0) Phép quay làm thay đổi hướng của đối tượng. Một phép quay cần có tâm quay và góc quay. Góc quay dương được quy ước là chiều ngược chiều kim đồng hồ. Ta có công thức biến đổi của phép quay điểm P(x, y) quanh tâm O(0,0) một góc : x’= x.cosα – y. sinα y’=x. sinα + y. cosα Ma trận của phép biến đổi: cosα sinα 0 MR = -sinα cosα 0 0 0 1 Phép quay được biểu diễn như sau: Q = P.MR cosα sinα 0 (x’ y’ 1) = (x y 1). -sinα cosα 0 0 0 1 y x Hình 2.12: Minh họa phép quay tâm O 34
Ví dụ: Ảnh của điểm P(22,14) sau phép quay 900 quanh tâm O(0,0) là Q(x’,y’): cos900 sin900 0 (x’ y’ 1) = (22 14 1). -sin900 cos900 0 = (-14 22 1) vậy Q(-14,22) 0 0 1 2.4.5. Kết hợp các phép biến đổi. Với một đối tượng đồ họa cho trước ta có thể thực hiện nhiều phép biến đổi lên chúng để đạt được hình ảnh mong muốn. Quá trình áp dụng các phép biến đổi liên tiếp để tạo nên một phép biến đổi tổng thể được gọi là sự kết hợp các phép biến đổi. a, Kết hợp các phép tịnh tiến Nếu ta thực hiện phép tịnh tiến lên P(xP, yP) được Q(xQ,yQ) , rồi lại thực hiện tiếp một phép tịnh tiến khác lên Q, ta được điểm R(xR,yR). Như vậy, R là ảnh của phép biến đổi kết hợp hai phép tịnh tiến liên tiếp: R = Q.MT2 =( P.MT1 ).MT2 = P.(MT1.MT2 ) 1 0 0 1 0 0 (x y 1) = (x y 1). R R P P 0 1 0 0 1 0 d1x d1y 1 d2x d2y 1 1 0 0  (xR yR 1) = (xP yP 1). 0 1 0 d1x+d2x d1y+d2y 1 Vậy: Kết hợp của 2 hay nhiều phép tịnh tiến là một phép tịnh tiến có độ dời bằng tổng các độ dời thành phần. b, Kết hợp các phép biến đổi tỷ lệ Tương tự như phép tịnh tiến, ta thực hiện biến đổi tỷ lệ lên điểm P(xP, yP) được Q(xQ,yQ), rồi lại thực hiện phép biến đổi tỷ lệ khác lên Q, ta được điểm R(xR,yR). Như vậy, R là ảnh của kết hợp hai phép biến đổi tỷ lệ liên tiếp: R = Q.MS2 =( P.MS1 ).MS2 = P.(MS1.MS2 ) S1x 0 0 S2x 0 0 (xR yR 1) = (xP yP 1). 0 S1y 0 0 S2y 0 0 0 1 0 0 1 35
S1x.S2x 0 0 (xR yR 1) = (xP yP 1). 0 S1y. S2y 0 0 0 1 Vậy: Kết hợp của 2 hay nhiều phép biến đổi tỷ lệ là một phép biến đổi tỷ lệ có tỷ lệ biến đổi bằng tích các tỷ lệ biến đổi thành phần. c, Kết hợp các phép quay tâm O(0,0): Kết hợp của 2 phép quay, ta có: R = Q.MR2 =( P.MR1 ).MR2 = P.(MR1.MR2 ) cosα1 sinα1 0 cosα2 sinα2 0 (x’ y’ 1) = (x y 1). -sinα1 cosα1 0 -sinα2 cosα2 0 0 0 1 0 0 1 cos(α1+α2) sinα1+α2) 0 (x’ y’ 1) = (x y 1). -sin(α1+α2) cos(α1+α2) 0 0 0 1 Vậy: Kết hợp của 2 phép quay tâm O là một phép quay tâm O có góc quay bằng tổng góc quay thành phần. Mở rộng ra ta có kết hợp của nhiều phép quay tâm O là một phép quay tâm O có góc quay bằng tổng các góc quay thành phần. d, Kết hợp các phép biến đổi khác nhau Các phép biến đổi tác động lên một đối tượng đồ họa đều là sự kết hợp của các phép biến đổi cơ sở theo một trình tự nào đó. Ở đây, thứ tự thực hiện các phép biến đổi lên một đối tượng khác nhau sẽ cho ảnh khác nhau, điều này được dẫn đến do phép nhân 2 ma trận không có tính chất giao hoán. Ví dụ a: Cho một điểm P(2,3), thực hiện biến đổi tỷ lệ lên P theo tỷ số Sx=1.5, Sy = 2 được ảnh Q1. Quay Q1 một góc 900 độ quanh O(0,0) được điểm ảnh R1: ta có: R1 = Q1.MR = P.(MS .MR) Sx 0 0 cosα sinα 0 (x’ y’ 1) = (x y 1). 0 Sy 0 -sinα cosα 0 0 0 1 0 0 1 36
Sx*cosα Sx*sinα 0  (x’ y’ 1) = (x y 1). -Sy*sinα Sy*cosα 0 0 0 1 1.5*0 1.5*1 0 (x’ y’ 1) = (2 3 1). -2*1 2*0 0 = (-6 3 1). 0 0 1 Vậy ảnh cuối cùng của chuỗi biến đổi lên điểm P(2,3) là R1(-6,3) (a) Ví dụ b: Quay P(2,3) một góc 900 độ quanh O(0,0) được điểm ảnh Q2, thực hiện biến đổi tỷ lệ Q2 theo tỷ số Sx=1.5, Sy = 2 được ảnh R2: ta có: R2 = Q2.MS = P.(MR .MS): cosα sinα 0 Sx 0 0 (x’ y’ 1) = (x y 1). -sinα cosα 0 0 Sy 0 0 0 1 0 0 1 Sx*cosα Sy*sinα 0  (x’ y’ 1) = (x y 1). -Sx*sinα Sy*cosα 0 0 0 1 1.5*0 2*1 0 (x’ y’ 1) = (2 3 1). -1.5*1 2*0 0 = (-4.5 4 1). 0 0 1 Vậy, ảnh cuối cùng của chuỗi biến đổi lên điểm P(2,3) là R2(-4.5,4) (b) Từ (a) và (b) ta thấy R1(-6,3) ≠ R2(-4.5,4) do thứ tự thực hiện các phép biến đổi lên một đối tượng khác nhau sẽ cho ảnh khác nhau. 2.5. Một số tính chất của phép biến đổi affine. 2.5.1. Bảo toàn đường thẳng: Ảnh của một đường thẳng qua phép biến đổi Affine là một đường thẳng. Vậy, để biến đổi một đường thẳng qua hai điểm P1, P2 ta chỉ cần áp dụng phép biến đổi cho hai điểm P1, P2 rồi vẽ lại đường thẳng qua hai điểm mới. 37
Thật vậy, ta có phương trình tham số của đường thẳng qua hai điểm P1, P2 là : P(t) = (1− t)P1 + tP2 . Q(t) là các điểm ảnh nhận được sau khi thực hiện phép biến đổi có ma trận M: Q(t) = P(t).M = (1 − t)P1 + tP2M = (1 − t)P1M + tP2M Nếu gọi Q1, Q2 lần lượt là ảnh của P1, P2 qua phép biến đổi M, ta sẽ có Q1 = P1M, Q2=P2M. Lúc này Q(t) = (1 − t)Q1+tQ2. Đây chính là dạng của phương trình tham số đoạn thẳng qua Q1, Q2. Từ kết quả trên, để biến đổi một đoạn thẳng đi qua hai điểm P1 và P2, ta chỉ cần áp dụng phép biến đổi cho hai điểm P1, P2 rồi vẽ lại đoạn thẳng qua hai điểm mới. 2.5.2 Bảo toàn tính song song Ảnh của hai đường thẳng song song là hai đường song song. Giả sử có 2 đường thẳng song song L đi qua P1 và P2 và L’ đi qua P1’ và P2’. Ta có phương trình tham số: L = P1 + (P2-P1)t = P1 + t và L’= P1’+ (P2’-P1’)t =P1’ + ’t Do L // L’ nên hai đường thẳng cùng phương, hay =’. Khi áp dụng phép biến đổi có ma trận M lên hai đường thẳng, dễ dàng nhận ra ảnh của chúng sẽ có phương M do đó chúng song song. Một hệ quả quan trọng của tính chất này đó là ảnh của các hình bình hành sau phép biến đổi là các hình bình hành. Do phép biến đổi Affine không bảo toàn góc nên ảnh của một hình chữ nhật hay một hình vuông sau biến đổi luôn là một hình bình hành. 2.5.3 Bảo toàn tính tỷ lệ Giả sử C là điểm chia đoạn AB theo tỉ số t. Nếu A’, B’, C’ lần lượt là ảnh A, B, C qua phép biến đổi thì C’ cũng sẽ chia A’B’ theo tỉ số t. Như vậy, nếu AM là trung tuyến cạnh BC của tam giác ABC thì A’M’ cũng là trung tuyến cạnh B’C’ của tam giác A’B’C’. Trong đó A’, B’, C’, M’ lần lượt là ảnh của A, B, C, M. 2.6 Một số phép biến đổi khác. 2.6.1 Phép biến đổi tỷ lệ tâm bất kỳ Có thể xem phép biến đổi tỷ lệ tâm bất kỳ I(x,y) một điểm P theo các tỷ lệ Sx, Sy là một phép biến đổi được kết hợp từ các phép biến đổi cơ sở sau: - Tịnh tiến theo vector (-x,-y) đưa tâm biến đổi về gốc tọa độ, ta có ma trận của phép biến đổi là MT(-I) - Thực hiện phép biến đổi tâm O(0,0) theo tỷ lệ Sx, Sy, ma trận biến đổi là MS 38
- Tịnh tiến theo vector (x,y) đưa tâm biến đổi I về vị trí ban đầu (x,y), ma trận biến đổi là MT(I) Ta có ma trận của phép biến đổi như sau: 1 0 0 Sx 0 0 1 0 0 M = M .M .M = 0 1 0 0 Sy 0 0 1 0 T(-I) S T(I) -x -y 1 0 0 1 x y 1 Sx 0 0  M = 0 Sy 0 (1- Sx).x (1-Sy).y 1 2.6.2 Phép quay có tâm quay bất kỳ Tương tự như phép biến đổi tỷ lệ tâm bất kỳ, có thể xem phép quay quanh tâm I(x,y) một góc α được kết hợp từ các phép biến đổi cơ sở sau: - Tịnh tiến theo vector (-x,-y) đưa tâm quay về gốc tọa độ, ta có ma trận của phép biến đổi là MT(-I) - Thực hiện phép quay tâm O(0,0) một góc α, ma trận biến đổi là MR - Tịnh tiến theo vector (x,y) đưa tâm quay về vị trí ban đầu: MT(I) y y y y x x x x Hình 2.13: Minh họa phép quay có tâm quay bất kỳ Ta có ma trận của phép biến đổi như sau: 1 0 0 cosα sinα 0 1 0 0 M = M .M .M = 0 1 0 -sinα cosα 0 0 1 0 T(-I) R T(I) -x -y 1 0 0 1 x y 1 39
cosα sinα 0  M = -sinα cosα 0 (1-cosα).x+y.sinα -x.sinα+(1-cosα).y 1 2.6.3 Phép đối xứng Ta có ma trận M của các phép đối xứng qua các trục tọa độ Ox, Oy, và tâm O(0,0) lần lượt là: 1 0 0 -1 0 0 -1 0 0 MOx = 0 -1 0 MOy = 0 1 0 MO = 0 -1 0 0 0 1 0 0 1 0 0 1 2.6.4 Phép biến đổi ngược Phép biến đổi ngược dùng để undo một phép biến đổi đã thực hiện. - Q là ảnh của P qua phép biến đổi T có ma trận biến đổi M là: Q = P.M - Phép biến đổi ngược T-1 sẽ có ma trận biến đổi là M-1, với M-1 là ma trận nghịch đảo của M, như vậy: P=Q*M-1 a b 0 Ta có ma trận tổng quát của các phép biến đổi là: M= c d 0 e f 1 Với giả thiết ban đầu ad – bc ≠ 0, ta tính được ma trận nghịch đảo của M là: d -b 0 1 M-1= -c a 0 ad - bc cf-de be–af ad-bc 2.7 Các thuật toán xén đoạn thẳng. Tại một thời điểm nhất định, người sử dụng chỉ muốn hiển thị một phần hình ảnh đã được tạo ra, phần còn lại phải được xác định và xén bỏ. Ví dụ khi thực hiện các thao tác phóng to (zoom) hình ảnh, chỉ một phần của nó có thể được hiển thị, vì vậy không cần thiết và tốn thời gian để tính toán các phần khác của ảnh, nên chúng được xác định và xén bỏ. 40
Thao tác xác định các điểm ảnh nằm trong hay ngoài một vùng cho trước được gọi là xén hình. Vùng được dùng để xén hình gọi là cửa sổ xén (clip window). Tùy thuộc vào từng ứng dụng cụ thể mà cửa sổ xén có thể có dạng là đa giác hay là đường cong khép kín. Trong phần này chúng ta sẽ khảo sát các thuật toán có cửa sổ xén là một hình chữ nhật. Giả sử cửa sổ xén là cửa sổ hình chữ nhật có tọa độ của các điểm dưới trái và điểm trên phải lần lượt là (xmin, ymin) và (xmax, ymax ). Một điểm P(x, y) được coi là nằm bên trong cửa sổ nếu thỏa mãn hệ bất phương trình: xmin ≤ x ≤ xmax ymin ≤ y ≤ ymax Thao tác xén hình là một trong những thao tác cơ bản của quá trình hiển thị đối tượng, do đó vấn đề tối ưu tốc độ luôn là đích cho các thuật toán nhắm đến. Ý tưởng chung của các thuật toán xén đoạn thẳng đó là loại bỏ phép toán tính giao điểm giữa đoạn thẳng với biên của cửa sổ, như đối với các đoạn thẳng đặc biệt nằm hoàn toàn trong hoặc hoàn toàn bên ngoài cửa sổ (ví dụ như đoạn P1P2, P3P4 và P7P8 trong hình 15). Đối với các đoạn thẳng có khả năng cắt cửa sổ, cần phải đưa ra cách tính giao điểm thật nhanh. P7 P8 P3 P1 P6 P2 P4 (b) P5 (a) Hình 2.14: (a)Trước khi thực hiện xén đoạn thẳng, (b) sau khi thực hiện Ta thấy, các đoạn thẳng mà có cả hai điểm đầu cuối nằm hoàn toàn trong cửa sổ thì cả đoạn thẳng nằm trong cửa sổ, đây cũng chính là kết quả sau khi xén (đoạn thẳng P1P2), mặt khác đối với các đoạn thẳng mà có hai điểm đầu cuối nằm về cùng một phía của cửa sổ thì luôn nằm ngoài cửa sổ và sẽ bị mất sau khi xén (đoạn thẳng P3P4, P7P8). Với các đoạn thẳng có khả năng cắt cửa sổ (đoạn thẳng P5P6) để việc tính giao điểm nhanh cần loại bỏ việc xác định giao điểm ảo với các biên kéo dài. 41
2.7.1 Thuật toán Cohen-Sutherland Đây là một trong những thuật toán ra đời sớm nhất và thông dụng nhất. Bằng cách kéo dài các biên của cửa sổ, người ta chia mặt phẳng thành chín vùng gồm cửa sổ và tám vùng xung quanh nó. a, Khái niệm mã vùng (area code) Một con số 4 bit nhị phân gọi là mã vùng sẽ được gán cho mỗi vùng để mô tả vị trí tương đối của vùng đó so với cửa sổ. Bằng cách đánh số từ 1 đến 4 theo thứ tự từ phải qua trái, các bit của mã vùng được dùng theo quy ước để xác định vị trí tương đối của vùng so với cửa sổ: 4 3 2 1 0101 0100 0110 Bottom Top Right Left 0001 0000 0010 1001 1000 1010 Hình 2.15: Cách đánh mã vùng – thuật toán Cohen-Sutherland Điểm P(x,y) có một mã vùng 4 bit CP, bit thứ i (i=1, 4) bằng 1 chỉ ra điểm P ở vị trí tương ứng với cửa sổ. Các giá trị bit trong mã vùng được tính bằng cách xác định tọa độ của điểm P(x, y): Bit 1 được đặt là 1 nếu x xmin, khi đó bit 2 được đặt bằng 0. Bit 2 được đặt là 1 nếu x > xmax, khi đó bit 1 được đặt bằng 0 Bit 3 được đặt là 1 nếu y > ymax, khi đó bit 4 được đặt bằng 0. Bit 4 được đặt là 1 nếu y ymin , khi đó bit 3 được đặt bằng 0 b, Ý tưởng thuật toán: Gán mã C1, C2 cho các điểm đầu cuối P1, P2 của đoạn thẳng cần xén. Ta có các trường hợp: - Nếu C1=C2=0000 ( C1││C2==0000 ) thì P1P2 nằm hoàn toàn bên trong cửa sổ. - Nếu tại cùng một vị trí bít của C1 và C2 đều là 1 (C1&C2 != 0000) thì P1P2 nằm cùng một phía với cửa sổ, vậy nằm hoàn toàn ngoài cửa sổ. - Ngoài hai trường hợp trên: Tìm giao điểm P’(x’,y’) của đoạn thẳng với biên của cửa sổ. Lúc này, đoạn thẳng ban đầu được xén thành P P’, P’P . 1 2 42
- Lặp lại thao tác đã xét cho các đoạn thẳng mới cho tới khi xác định được phần nằm trong hoặc loại bỏ toàn bộ đoạn thẳng. 0101 0100 0110 0001 P1 0000 0010 P6 P3 • P2 1001 1000 1010 P4 • P5 Hình 2.16: Minh họa thuật toán Cohen - Sutherland Tìm giao điểm P’(x’,y’) của P1P2 với biên của cửa sổ: - Nếu bit 1 là 1 ta có x’= xmin , bit 2 là 1: x’= xmax P1P2 cắt cửa sổ tại biên dọc. - Nếu bit 3 là 1 ta có y’= ymax, bit 4 là 1: y’= ymin P1P2 cắt cửa sổ tại biên ngang.[2] Biên ngang: Biên dọc: y’= y hoặc y’ = y x’ = x hoặc x’ = x min max min max x’ = x + (y’ – y )/m y’ = y + m(x’ – x ) 1 1 1 1 43
Giải thuật Begin Code(P1, C1) Code(P2, C2) Đúng Hiển thị C1||C2 = =0000 P1P2 Sai Đúng Xén bỏ C1&C2 !=0000 P1P2 Sai Xác định giao điểm của P1P2 với biên của cửa sổ End Hình 2.17: Giải thuật xén đoạn thẳng Cohen-Sutherland Ví dụ: Cho của sổ xén có tọa độ góc trái dưới là (12, 15), tọa độ góc phải trên là (32,47). Thực hiện xén các đoạn thẳng sau: a, A1(8,25)A2(10,50) b, B1(18,20)B2(28,40) c, C1(21,44)C2(29,52) d, D1(8,20)D2(30,53) Giải: a, Mã vùng CA1 = 0001, CA2 = 0101 Ta có: CA1 &CA2 != 0000 vậy A1A2 nằm hoàn toàn ngoài cửa sổ. A1A2 nằm hoàn toàn về bên trái của cửa sổ, do CA1 &CA2 = 0001: bít 1 bằng 1 tương ứng với vị trí bên trái của cửa sổ. b, Mã vùng CB1 = 0000, CB2 = 0000 Ta có: CB1 ||CB2 = 0000 vậy B1B2 nằm hoàn toàn trong cửa sổ. c, Mã vùng CC1 = 0000, CC2 = 0100 Ta có: CC1 ||CC2 = !0000 và CC1 &CC2 = 0000, suy ra C1C2 cắt cửa sổ. 44
Do bít 3 của CC2 bằng 1 nên tọa độ cắt được tính như sau: y’ = ymax y’ = 47 x’ = x + (y’ – y )/m x’ = 21+ (47-44).(29-21)/(52-44) 1 1 với 1/m=Dx/Dy=(29-21)/(52-44) Vậy C1C2 cắt cửa sổ tại I(24,47) d, Mã vùng CD1 = 0001, CD2 = 0100 Ta có: CD1 ||CD2 = !0000 và CD1 &CD2 = 0000, suy ra D1D2 cắt cửa sổ. Do bít 1 của CD1 bằng 1 nên tọa độ cắt được tính như sau: x’ = xmin x’ = 12 y’ = y1 + (x’ – x1).m y’ = 20+ (12-8).(53-20)/(30-8) m=Dy/Dx=(53-20)/(30-8)=1.5  I1(12,26) Do bít 3 của CD2 bằng 1 nên tọa độ cắt được tính như sau: y’ = ymax y’ = 47 x’ = x1+ (y’ – y1)/m x’ = 8+ (47-20)/1.5  I2( 26,47) Vậy D1D2 cắt cửa sổ tại 2 điểm I1(12,26) và I2(26,47) 2.7.2 Thuật toán Liang Barsky Thuật toán Liang-Barsky được phát triển dựa vào việc phân tích dạng tham số của phương trình đoạn thẳng. Cho 2 điểm P1(x1,y1), P2(x2,y2). Phương trình tham số của đoạn thẳng có 2 điểm đầu cuối P1, P2 là: x = x1 + (x2-x1)t x = x1 + tDx y = y1 + (y2-y1)t y=y1 + tDy Với t [0,1] ta có phương trình tham số của đoạn P1P2 Với t (-∞, +∞) ta có phương trình tham số của đường thằng đi qua P1, P2. Ứng với mỗi giá trị t, ta sẽ có một điểm P(x,y) tương ứng thuộc đường thẳng: - Các điểm ứng với t 1sẽ thuộc về tia P2x. - Các điểm ứng với t 0 sẽ thuộc về tia P1x’. - Các điểm ứng với 0 t 1 sẽ thuộc về đoạn thẳng P1P2 . 45
x P2 t>1 t=1 (xmax,ymax) P1 t=0 x’ t Hệ bất phương trình vô nghiệm (đoạn thẳng không cắt cửa sổ) • Nếu qk ≥ 0 => Tính nghiệm t1, t2 như 2 trường hợp sau: - Với bất phương trình tpk qk mà pk 0, ta có t qk / pk, tính t1 = max{0, qk/pk} 46
- Với bất phương trình tpk qk mà pk 0, ta có t qk / pk, tính t2 = min{1, qk/pk} Nếu t1 > t2 thì đoạn thẳng nằm hoàn toàn ngoài cửa sổ. x = x1 + t Dx Nếu t1 ≤ t2: [2][3] y = y1 + t Dy Cài đặt minh họa: int ClipTest(int p, int q, float &t1, float &t2) { float r; if (p t2) return FALSE; else if (r>t1) t1 = r; } else { if (p>0) { r = float(q)/p; if (r<t1) return FALSE; else if (r<t2) t2 = r; } else // p=0 { if (q<0) return FALSE; } } return TRUE; } int LiangBarskyClipping(POINT P1, POINT P2, RECT R, POINT *Q1, POINT *Q2) { 47
float t1, t2; int Dx, Dy, x1, y1, x2, y2, xmin, ymin, xmax, ymax; t1 = 0; t2 = 1; x1 = P1.x; y1 = P1.y; x2 = P2.x; y2 = P2.y; Dx = x2 - x1; Dy = y2 - y1; xmin = R.Left; ymin = R.Top; xmax = R.Right; ymax = R.Bottom; if (ClipTest(-Dx, x1 - xmin, t1, t2)) // Giai he bat phuong trinh 1 { if (ClipTest(Dx, xmax - x1, t1, t2)) // Giai he bat phuong trinh 2 { if (ClipTest(-Dy, y1 - ymin, t1, t2)) // Giai he bat phuong trinh 3 { if (ClipTest(Dy, ymax - y1, t1, t2)) // Giai he bat pt 4 { Q1.x = x1 + t1. Dx; Q1.y = y1 + t1. Dy; Q2.x = x1 + t2. Dx; Q2.y = y1 + t2. Dy; return TRUE; } // Giai he bat phuong trinh 4 } // Giai he bat phuong trinh 3 } // Giai he bat phuong trinh 2 } // Giai he bat phuong trinh 1 return FALSE; } // LiangBarskyClipping Ví dụ 1: Cho cửa sổ xén có tọa độ góc trái dưới là (5,7), góc phải trên là (25,30) và đoạn thẳng P1P2 có tọa độ là P1(10,11), P2( 27,28). Tìm vị trí tương đối của P1P2 với của sổ và giao điểm P’ ( nếu có ) của P1P2 với cửa sổ: Giải: Ta có: p1= -17 q1= 5 p2= 17 q2= 15 p3= -17 q3= 4 p4= 17 q4= 19 p1, p3 t1 = max{0, -5/17, -4/17} = 0 48
p2, p4 > 0 => t2 = min {1, 15/17, 19/17} = 15/17 t1 x = 10 + 17*15/17 = 25 y= 11 +17*15/17 = 26  P1P2 cắt cửa sổ tại P’(25,26) Ví dụ 2: Cho cửa sổ xén có tọa độ góc trái dưới là (6,4), góc phải trên là (20,18) và đoạn thẳng P1P2 có tọa độ là P1(5,15), P2( 9,19). Tìm vị trí tương đối của P1P2 với của sổ và giao điểm P’ ( nếu có ) của P1P2 với cửa sổ. Giải: Ta có: p1= -4 q1= -1 p2= 4 q2= 15 p3= -4 q3= 11 p4= 4 q4= 3 p1, p3 t1 = max{0, 1/4, -11/4} = 1/4 p2, p4 > 0 => t2 = min {1, 15/4, 3/4} = 3/4 x1 = 5 + 4*1/4 = 6 t1 P1’ y1= 15 +4*1/4 = 16 x1 = 5 + 4*3/4 = 8 P2’ y1= 15 +4*3/4 = 18  P1P2 cắt cửa sổ tại P1’(6,16) và P2’(8,18) 49
Câu hỏi ôn tập chương: 1, Trình bày thuật toán DDA, Bresenham, Midpoint vẽ đường thẳng. 2, Thuật toán Bresenham và Midpoint có cải tiến gì so với thuật toán DDA. 3, Trình bày ý tưởng và thuật toán Midpoint vẽ đường tròn. 4, Trình bày về các phép biến đổi cơ bản: Phép tịnh tiến, phép quay, phép biến đổi tỷ lệ. 5, Xây dựng ma trận của phép biến đổi tỷ lệ tâm bất kỳ và phép quay tâm bất kỳ. 6, Trình bày các tính chất của phép biến đổi Affine. 7, Trình bày thuật toán xén đoạn thẳng Liang-Barsky và thuật toán Cohen-Sutherland. Bài tập ôn tập: 1, Tìm các điểm được vẽ của đoạn thẳng đi qua 2 điểm đầu cuối P1(17,3), P2(23,15) bằng cả 3 thuật toán và so sánh kết quả. 2, Tìm các điểm được vẽ của đoạn thẳng đi qua 2 điểm đầu cuối P1(2,3), P2(11,9) bằng cả 3 thuật toán và so sánh kết quả. 3, Tìm các điểm được vẽ của cung tròn thứ nhất của hình tròn có bán kính R=21. 4, Tìm ảnh của điểm P(5,7) qua phép tịnh tiến có độ dời theo trục Ox là dx=-3, theo trục Oy là dy=10. 0 5, Tìm ảnh của điểm P(8,3) qua phép quay tâm O(0,0) một góc α = 90 . 0 6, Tìm ảnh của điểm P(19,23) qua phép quay tâm I(2,4) một góc α = -60 . 7, Tìm ảnh của điểm P(7,3) qua phép biến đổi tỷ lệ tâm O(0,0) với tỷ lệ biến đổi Sx=1.5, Sy=0.5. 8, Tìm ảnh của điểm P(22,16) qua phép biến đổi tỷ lệ tâm I(7,11) với tỷ lệ biến đổi Sx=2.5, Sy=2. 9, Tìm ảnh của P(3,4) qua phép quay 900 rồi biến đổi theo tỷ lệ Sx=2, Sy=3.3. 10, Tìm ảnh của P(7,19) qua phép biến đổi theo tỷ lệ Sx=2.5, Sy=1.2 rồi quay 450. 11, Thực hiện xén đoạn thẳng P1P2 bằng thuật toán Cohen-Sutherland, biết tọa độ P1(13,28), P2(27,42) và tọa độ góc trái dưới và góc phải trên của cửa sổ xén lần lượt là (15,31), (40,43). 12, Thực hiện xén đoạn thẳng P1P2 bằng thuật toán Liang-Barsky, biết tọa độ P1(60,54), P2(69,72) và tọa độ góc trái dưới và góc phải trên của cửa sổ xén lần lượt là (66,41), (70,68). 13, Tìm câu trả lời đúng nhất : Phép biến đổi Affine luôn biến : a, Một góc vuông thành một góc vuông b, Một góc bẹt thành một góc bẹt c, Một góc nhọn thành một góc nhọn 50
d, Một góc tù thành một góc tù 14, Trọn phát biểu đúng nhất: Thuật toán vẽ đường thẳng DDA đã loại bỏ được: a, Các phép nhân và phép cộng trên tập số thực b, Phép nhân trên tập số thực c, Phép cộng trên tập số thực d, Các phép toán trên tập số thực 15, Trọn phát biểu đúng nhất: Hạn chế của thuật toán DDA là: a, Còn tồn tại phép nhân và phép cộng trên tập số thực b, Còn tồn tại phép nhân và phép làn tròn trên tập số thực c, Còn tồn tại phép làm tròn và phép cộng trên tập số thực d, Còn tồn tại phép làm tròn trên tập số thực 16, Tìm câu trả lời đúng nhất : Phép biến đổi Affine biến : a, Một hình chữ nhật thành một hình chữ nhật b, Một hình chữ nhật thành một hình vuông c, Một hình chữ nhật thành một hình bình hành d, Một hình chữ nhật thành một hình thoi. 17, Trong phép biến đổi Affine, kết hợp của các phép tịnh tiến là một phép tịnh tiến, có: a, véctơ độ dời bằng tổng các véctơ độ dời thành phần b, véctơ độ dời bằng hiệu các véctơ độ dời thành phần c, véctơ độ dời bằng tích các véctơ độ dời thành phần d, Cả ba câu trên đều sai. 18, Trong phép biến đổi Affine, kết hợp của các phép biến đổi tỷ lệ là một phép biến đổi tỷ lệ, có: a, Tỷ lệ biến đổi bằng tổng các tỷ lệ thành phần b, Tỷ lệ biến đổi bằng tích các tỷ lệ thành phần c, Tỷ lệ biến đổi bằng hiệu các tỷ lệ thành phần d, Cả ba câu trên đều sai 19, Trong phép biến đổi Affine, kết hợp của các phép quay là một phép quay, có: a, Góc quay bằng tổng các góc quay thành phần b, Góc quay bằng tích các góc quay thành phần c, Góc quay bằng hiệu các góc quay thành phần 51
d, Cả ba câu trên đều sai 20, Tìm câu trả lời đúng nhất : Phép biến đổi Affine biến : a, Một đường thẳng thành một điểm b, Một đường thẳng thành một đường thẳng c, một đường thẳng thành một mặt phẳng d, cả ba ý trên đều sai. 21.Trong mặt phẳng, tìm phương án không đúng khi biểu diễn một điểm: a.[a b 0] b.[a b 1] c.[a b 2] d.[a b 3] 22.Trong mặt phẳng, tìm phương án đúng khi biểu diễn một điểm: a.[a 0 0]; a≠0 b.[0 a 0]; a≠0 c.[0 0 a] ; a≠0 d.[0 0 0] 23.Trong 2D toạ độ vector của điểm P(3,6) vậy trong các toạ độ sau toạ độ nào không phải là toạ độ đồng nhất của P: a.( 6, 12) b.( 6,12,2) c.( 1.5, 3, 0.5) d.( 3*a, 6*a, a) trong đó a ≠ 0 24.Trong 2D toạ độ vector của điểm P(4,8) vậy trong các toạ độ sau toạ độ nào không phải là toạ độ đồng nhất của P: a.(8, 16, 2) b.( 6, 12, 1.5) c.(5, 10, 2) d.(3*a, 6*a, a) trong đó a ≠ 0 25. Phép biến đổi Afine trong mặt phẳng là: x’=ax+cy+e; y’=bx+dy+f; Vậy phép đối xứng qua tâm O là: a.b=c==e=f=1 và a=d=0 b.b=c=e=f=0 và a=d=1 c.b=c=e=f=0 và a=d=-1 d.b=c=e=f=-1 và a=d=0 26. Phép biến đổi Afine trong mặt phẳng là: x’=ax+cy+e; y’=bx+dy+f; Vậy phép làm béo một đối tượng gấp 2 lần ban đầu là: a.b=c=0, e=f=1, a=d=2 b.b=c=1, e=f=0 và a=d=2 c.b=c=2 và a=d=e=f=0 d.b=c=e=f=0 và a=d=2 27. Phép biến đổi Afine trong mặt phẳng là: x’=ax+cy+e; y’=bx+dy+f; Vậy ma trận của phép tịnh tiến là: 52
a.b=c=0, a=d=1, e=dx và f=dy b.b=c=e=f=0, a=Sx và d=Sy c.b=c=0, e=f=1, a=d=1 d.b=c=1, e=dx f=dy và a=d=0 28. Phép biến đổi Afine trong mặt phẳng là: x’=ax+cy+e; y’=bx+dy+f; Vậy ma trận của phép của phép biến đổi tỷ lệ là: a.b=c=0, a=d=1, e=dx và f=dy b.b=c=e=f=0, a=Sx và d=Sy c.b=c=0, e=f=1 a=Sx và d=Sy d.b=c=1, e=dx f=dy và a=d=0 29. Phép biến đổi Afine trong mặt phẳng là: x’=ax+cy+e; y’=bx+dy+f; Vậy ma trận của phép của phép quay là: a. a=sinα, b=-sinα, c=d=cosα và e=f=0 b. a=sinα, c=-sinα, b=d=cosα và e=f=0 c. b=sinα, c=-sinα, a=d=cosα và e=f=0 d. c=sinα, b=-sinα, a=d=cosα và e=f=0 30. Cho cửa sổ cắt tỉa góc trái dưới (2,12) và góc phải trên (14,27). Mã vùng 4bít của điểm A(22,6) là: a. 1000 b. 1010 c. 0101 d. 0001 31. Cho cửa sổ cắt tỉa có góc trái dưới (2,13) và phải trên (5,26), mã vùng 4bít của điểm M(0,20) là: a. 1010 b. 1100 c. 0101 d. 0001 Bài tập thảo luận: 1, Trình bày thuật toán DDA, Bresenham, Midpoint vẽ đường thẳng trong các trường hợp còn lại của hệ số góc m. 2, Cài đặt các thuật toán vẽ đường thẳng và đường tròn, hình chữ nhật 3, Xây dựng ma trận của phép lấy đối xứng qua tâm bất kỳ 4, Xây dựng ma trận của các phép biến đổi ngược của các phép biến đổi cơ sở. 5, Cài đặt các thuật toán Cohen-Sutherland và Liang-Barsky. 53
CHƯƠNG 3: ĐỒ HỌA 3 CHIỀU Mục tiêu của chương: Sinh viên cần nắm được cách biểu diễn đối tượng đồ họa 3 chiều từ các đối tượng đơn giản như các hình khối, các đa diện Có thể thực hiện tính toán được ảnh của các điểm trong không gian 3 chiều sau các phép biến đổi: Tỷ lệ, tịnh tiến, phép quay tâm O(0,0,0) và quay tâm bất kỳ, các phép lấy đối xứng qua mặt phẳng, qua trục tọa độ. Sinh viên cần nắm được các phương pháp chiếu các đối tượng 3D xuống mặt phẳng thiết bị hiển thị. Có thể tính được hình chiếu của các điểm trong một số phương pháp chiếu song song và phối cảnh. 3.1. Tổng quan về đồ họa ba chiều Các đối tượng trong thế giới thực phần lớn là các đối tượng ba chiều, nên việc thể hiện các đối tượng ba chiều trên máy tính là một công việc hết sức cần thiết để đưa tin học gần gũi với thực tế hơn. Cũng giống như các cách biểu diễn các đối tượng ba chiều trên mặt phẳng ở các thiết bị khác (như của máy ảnh, camera, ), biểu diễn bằng máy tính cũng phải tuân theo các quy luật về phối cảnh, sáng, tối, nhằm giúp người xem có thể tưởng tượng lại hình ảnh một cách gần đúng nhất. Ngoài ra biểu diễn trên máy tính có ưu thế giúp ta có thể quan sát đối tượng ở nhiều góc cạnh khác nhau, ở các khoảng cách khác nhau. Khi chúng ta mô hình hóa và hiển thị một cảnh ba chiều, ta cần phải xem xét rất nhiều khía cạnh và vấn đề khác nhau chứ không đơn giản là thêm vào tọa độ thứ ba cho các đối tượng. Bề mặt đối tượng có thể xây dựng bởi nhiều tổ hợp khác nhau của các mặt phẳng và các mặt cong. Ngoài ra, đôi khi chúng ta cũng cần mô tả một số thông tin về bên trong các đối tượng. Các công cụ hỗ trợ đồ họa (graphics package) thường cung cấp một số hàm hiển thị các thành phần bên trong, những đường nét tiêu biểu hoặc hiển thị một phần của đối tượng ba chiều (solid object). Ngoài ra, các phép biến đổi hình học trong đồ họa 3 chiều thường được sử dụng nhiều hơn và đa dạng hơn trong đồ họa hai chiều. Phép biến đổi hệ quan sát trong không gian ba chiều phức tạp hơn nhiều so với trong không gian hai chiều do chúng ta phải chọn lựa nhiều tham số hơn khi mô tả một cảnh ba chiều sẽ xuất hiện trên màn hình như thế nào. 3.2. Biểu diển các đối tượng ba chiều Các cảnh đồ họa có thể chứa nhiều dạng đối tượng khác nhau: cây, hoa, mây, núi, nước, sắt thép, cỏ, Chính vì vậy, có nhiều phương pháp khác nhau được sử dụng để mô tả các đối tượng sao cho phù hợp với thuộc tính của các loại đối tượng này. 54
Sơ đồ biểu diễn một đối tượng lập thể thường được chia ra làm hai loại, dù không phải tất cả các biểu diễn đều có thể được phân chia một cách rõ ràng thuộc loại nào trong hai loại này. - Phương pháp biểu diễn bề mặt B-reps mô tả các đối tượng ba chiều bằng một tập hợp các bề mặt giới hạn phần bên trong của đối tượng với môi trường bên ngoài. Ví dụ kinh điển của B-reps là việc biểu diễn các mặt đa giác và các mảnh tròn xoay. - Phương pháp biểu diễn theo phân hoạch không gian (space-partitioning representation) thường được dùng để mô tả các thuộc tính bên trong của đối tượng bằng cách phân hoạch phần bên trong của đối tượng thành một tập hợp nhiều đối tượng nhỏ hơn. Trong đồ họa máy tính, các đối tượng lập thể có thể được mô tả bằng các bề mặt (surfaces) của chúng. Ví dụ : Một hình lập phương được xây dựng từ sáu mặt phẳng, một hình trụ được xây dựng từ sự kết hợp của một mặt cong và hai mặt phẳng, và hình cầu được xây dựng chỉ từ một mặt cong. Thông thường để biểu diễn một đối tượng bất kì, người ta dùng các phương pháp xấp xỉ để đưa các mặt về dạng các mặt đa giác (polygon faces). Tuy nhiên trong trường hợp các đối tượng phức tạp, người ta thường dùng một hay nhiều mặt cong trơn (smoothly curved surfaces) ghép nối lại với nhau. Mỗi thành phần dùng để ghép nối được gọi là patch. 3.2.1. Biểu diễn mặt đa giác Phương pháp chung nhất thường dùng để biểu diễn các đối tượng ba chiều là dùng một tập hợp các mặt đa giác xác định bề mặt của đối tượng. Rất nhiều hệ thống đồ họa lưu trữ các đối tượng như là một tập hợp các mặt đa giác. Với cách biểu diễn này ta có thể đơn giản hóa việc biểu diễn và tăng tốc độ hiển thị các đối tượng bởi vì tất cả các bề mặt đều được mô tả bởi các phương trình tuyến tính. Do đó, mô tả các đối tượng thông qua các mặt đa giác thường được dùng cho các đối tượng đồ họa cơ sở. Trong một số trường hợp, ta chỉ có một khả năng chọn lựa là sử dụng biểu diễn đa giác. Tuy nhiên, một số hệ thống đồ họa còn cho phép các khả năng biểu diễn khác ví dụ như bằng các mặt cong spline. Hình 3.1: Mô hình wireframe của một hình trụ 55
Biểu diễn bằng mặt đa giác của các đa diện cho chúng ta một định nghĩa chính xác về các đặc tính của các đối tượng này. Nhưng đối với những đối tượng khác ta chỉ nhận được một biểu diễn gần đúng. Hình 20 cho chúng ta biểu diễn một hính trụ như là một tập hợp các mặt đa giác. Biểu diễn dạng wireframe cho phép chúng ta hiển thị đối tượng rất nhanh. Khi cần thể hiện đối tượng thực hơn, ta có thể dùng kĩ thuật tạo bóng nội suy (interpolating shading). a, Mô hình khung nối kết (Wireframe Model) Mô hình khung nối kết là phương pháp thông dụng và đơn giản để mô hình hóa đối tượng. Mô hình này sử dụng một danh sách các đỉnh và một danh sách các cạnh nối các đỉnh đó. Danh sách các đỉnh cho biết vị trí các đỉnh, danh sách các cạnh xác định thông tin về sự kết nối, cho biết cặp các đỉnh tạo ra cạnh. Các đối tượng 3 chiều khi được thể hiện bằng mô hình này là các đối tượng rỗng. Để hoàn thiện hơn, người ta dùng các kĩ thuật tạo bóng, các kĩ thuật loại bỏ các đường và mặt khuất. Mô hình khung kết nối thường được sử dụng trong việc xem phác thảo (preview) các đối tượng. Ví dụ: Cho hình tứ diện OABC có tọa độ các đỉnh O(0,0,0), A(2,3,1), B(0,0,1), C(2,0,1) y A O x B C Danh sách các cạnh z Cạnh Đỉnh Đỉnh Danh sách các đỉnh OA O A Đỉnh x y z OB O B O 0 0 0 OC O C A 2 3 1 AB A B B 0 0 1 BC B C C 2 0 1 CA C A Hình 3.2: Minh họa mô hình khung kết nối 56
b, Biểu diễn bằng bảng đa giác Ta biểu diễn một mặt đa giác bằng một tập hợp các đỉnh và các thuộc tính kèm theo. Khi thông tin của mỗi mặt đa giác được nhập, dữ liệu điền vào trong các bảng sẽ được dùng cho các xử lí tiếp theo như hiển thị và biến đổi. Các bảng dữ liệu mô tả mặt đa giác có thể tổ chức thành hai nhóm: các bảng hình học và các bảng thuộc tính. Các bảng lưu trữ dữ liệu hình học chứa tọa độ của các đỉnh và các tham số cho biết về định hướng trong không gian của mặt đa giác. Thông tin về thuộc tính của các đối tượng chứa các tham số mô tả độ trong suốt, tính phản xạ và các thuộc tính cho biết đặc điểm bề mặt của đối tượng. Một cách tổ chức thuận tiện để lưu trữ các dữ liệu hình học là tạo ra ba danh sách: một bảng lưu đỉnh, một bảng lưu cạnh và một bảng lưu đa giác. Các giá trị tọa độ cho mỗi đỉnh trong đối tượng được chứa trong bảng lưu đỉnh. Bảng cạnh chứa các con trỏ trỏ đến bảng đỉnh cho biết đỉnh nào được nối với một cạnh của đa giác. Và cuối cùng, bảng lưu đa giác chứa các con trỏ trỏ tới bảng lưu cạnh cho biết những cạnh nào tạo nên đa giác. Ngoài ra, ta cũng có thể thêm một số thông tin bổ sung vào các bảng trên để xử lí nhanh hơn khi cần truy xuất thông tin. Ví dụ, ta có thể thêm một con trỏ từ một cạnh đến các đa giác chứa nó. Tương tự, ta có thể thêm thông tin trong bảng lưu đỉnh để biết những cạnh nào kề với một đỉnh cho trước Vì các bảng lưu thông tin về đối tượng có thể rất phức tạp nên việc kiểm tra tính đúng đắn và đầy đủ của dữ liệu là rất quan trọng. c, Phương trình mặt phẳng Để thực hiện việc hiển thị một đối tượng ba chiều, ta phải xử lí dữ liệu nhập thông qua một quy trính gồm nhiều bước. Trong một số bước này, đôi khi ta cần thông tin về định hướng của đối tượng và cả thông tin về định hướng của từng mặt của đối tượng trong không gian. Những thông tin này có thể lấy được thông qua tọa độ của các đỉnh và phương trình mô tả các mặt đa giác của đối tượng. Phương trình biểu diễn mặt phẳng có dạng: Ax +By +Cz +D =0 Để xác định phương trình mặt phẳng, ta chỉ cần biết ba điểm không thẳng hàng trên mặt phẳng này. Như vậy, để xác định phương trình mặt phẳng qua một đa giác, ta sẽ sử dụng tọa độ của ba đỉnh: (x1, y1,z1 ), (x2, y2,z2 ), (x3, y3,z3 ), trong đa giác này. Ax1 +By1 +Cz1 +D =0 vậy ta có: Ax2 +By2 +Cz2 +D =0 Ax3 +By3 +Cz3 +D =0 Dùng quy tắc Cramer, ta có thể xác định A, B, C, D theo công thức: 57
1 y1 z1 x1 1 z1 A= 1 y2 z2 B= x2 1 z2 1 y3 z3 x3 1 z3 x1 y1 1 x1 y1 z1 C= x2 y2 1 D= - x2 y2 z2 x3 y3 1 x3 y3 z3 Khai triển các định thức trên ta được công thức tường minh của các hệ số: A=y1(z2-z3) +y2(z3-z1) +y3(z1-z2) B=z1(x2-x3) +z2(x3-x1) +z3(x1-x2) C=x1(y2-y3) +x2(y3-y1) +x3(y1-y2) D=x1(y3z2-y2z3) +x2(y1z3-z1y3) +x3(y2z1-y1z2) n=(A,B,C) Hình 3.3: Vector pháp tuyến của mặt phẳng Hướng của mặt phẳng được xác định thông qua vector pháp tuyến của nó. Vector pháp tuyến n =(A, B,C), trong đó A, B, C là các hệ số của phương trình mặt phẳng ta vừa tính được. 3.2.2. Lưới đa giác (polygon meshes) Một số hệ đồ họa cung cấp một số hàm cho phép mô hình hóa các đối tượng. Việc biểu diễn một mặt phẳng là khá đơn giản, nhưng khi đối tượng có cấu tạo bề mặt từ nhiều mặt cong ta cần lợp nhiều patch liên tiếp, điều này được thực hiền nhờ việc dùng các hàm lưới (mesh function). Một dạng thông dụng của lưới đa giác là dãy các tam giác (triagle strip). Hàm này vẽ n-2 tam giác kề nhau khi biết n đỉnh. Dạng này của lưới đa giác dùng trong hầu hết các thư viện đồ họa chuẩn hiện nay như OpenGL hay DirectX. Một dạng hàm tương tự là lưới các tứ giác (quardrilateral mesh). Hàm này vẽ một lưới (n-1)*(m-1) tứ giác lồi từ dãy n*m đỉnh. 58
Khi đa giác được mô tả bởi nhiều hơn ba đỉnh, các đỉnh của nó có thể không đồng phẳng. Điều này có thể dẫn đến các lỗi tính toán. Một phương pháp đơn giản là phân đa giác này thành các tam giác. [6] Hình 3.4: Triangle strip và quadrilateral mesh 3.2.3. Các đường cong và mặt cong Hình ảnh của các đường cong và mặt cong có thể được tạo ra từ một tập hợp các hàm toán học hoặc từ một tập hợp các điểm trên đối tượng. Đối với đối tượng có thể được mô tả bằng các hàm toán học, thư viện đồ họa cung cấp sẵn các hàm cho phép biểu diễn các đối tượng này lên mặt phẳng thiết bị hiển thị. Đối với các đường cong, các hàm trong thư viện sẽ vẽ các điểm theo hình chiếu của chúng. Đối với các mặt cong, một lưới đa giác xấp xỉ với mặt cong sẽ được tạo ra. Các hệ đồ họa tạo ra các lưới tam giác để đảm bảo tính đồng phẳng của các cạnh thuộc cùng một polygon patch. Một đường cong hoặc mặt cong có thể được diễn tả bằng phương trình toán học dạng tham số hoặc không tham số. Tuy nhiên, trong đồ họa máy tính, dạng tham số sẽ thuận tiện cho xử lí hơn. Khi đối tượng được mô tả bởi một tập hợp các điểm rời rạc, đối tượng sẽ được hiển thị thông qua một mặt cong xấp xỉ nào đó dựa trên những điểm đã cho. Các loại đường cong và mặt cong dạng spline hoặc Bezier là những đường cong và mặt cong xấp xỉ thường dùng. Các mặt cong có thể có hình dạng rất phức tạp, đặc biệt khi nó bao gồm nhiều patch kết hợp lại với nhau. 3.3. Các phép biến đổi hình học ba chiều Các phép biến đổi cơ sở trong đồ họa ba chiều là sự mở rộng của các phép biến đổi trong đồ họa hai chiều bằng cách thêm vào việc xem xét tọa độ thứ ba, tọa độ z. Bây giờ, chúng ta sẽ tịnh tiến một đối tượng thông qua việc mô tả một vector tịnh tiến ba chiều. Vector này xác định độ dời của vật theo ba chiều trong không gian. Tương tự như vậy, ta có thể thu phóng đối tượng với các tỉ lệ biến đổi theo cả ba chiều. Sự mở rộng của phép quay ít hiển nhiên hơn hai phép biến đổi cơ sở trên. Khi khảo sát các phép quay trong mặt phẳng hai chiều Oxy, ta chỉ cần khảo sát phép quay quanh một tâm, hay nói cách khác, phép quay quanh một trục vuông góc với mặt phẳng Oxy. Trong không gian ba chiều, ta có thể chọn một trục quay có phương bất kì. 59
Phần lớn các hệ đồ họa xử lí phép quay trong không gian ba chiều như là tổ hợp của ba phép quay với trục quay là các trục tọa độ x, y và z. Như vậy, người dùng có thể dễ dàng xây dựng một phép quay bất kì bằng cách mô tả trục quay và góc quay. Cũng như khi trính bày các phép biến đổi trong đồ họa hai chiều, trong chương này, ta sẽ khảo sát các phép biến đổi trong đồ họa ba chiều dưới dạng ma trận. Một chuỗi bất kì các phép biến đổi sẽ được biểu diễn bằng một ma trận duy nhất là tích của các ma trận tương ứng với các phép biến đổi thành phần. 3.3.1 Các phép biến đổi cơ bản Phép tịnh tiến, quay, biến đổi tỉ lệ, và phép biến dạng là các ví dụ của các phép biến đổi hình học. Chúng còn được biết tới như là các phép biến đổi affine cơ sở. Trong số đó, phép quay có thể nói là quan trọng và hữu dụng nhất vì nó cho phép chúng ta nhìn các đối tượng theo các hướng khác nhau, điều này cho phép chúng ta cảm nhận các hình vẽ ba chiều trực quan hơn, dễ chịu hơn. Phép biến đổi affine là phép biến đổi tuyến tính, khả nghịch. Phép biến đổi này bảo toàn tính song song của các đường thẳng cũng như bảo toàn tính tỉ lệ về khoảng cách của các đoạn thẳng. Tuy nhiên, phép biến đổi này không bảo toàn góc nghiêng và chiều dài các đoạn thẳng. Các phép biến đổi này cũng bảo toàn tỉ lệ về khoảng cách. a, Phép tịnh tiến: Phép tịnh tiến biến điểm P(x,y,z) trong không gian 3D thành một điểm Q(x’,y’,z’) theo vector tịnh tiến d(dx, dy, dz). Trong đó: x’= x + dx y’ = y + dy z’ = z + dz Ma trận M cho phép tịnh tiến có dạng như sau: Hình 3.5: Minh họa phép tịnh tiến 1 0 0 0 0 1 0 0 MT = 0 0 1 0 dx dy dz 1 Ví dụ: Cho điểm P(4,26,12) tịnh tiến theo vector d(3,-3,-11) được điểm Q(x’,y’,z’). Ta có: Q=P.MT 1 0 0 0 0 1 0 0 (x’ y’ z’ 1) = (4 26 12 1). 0 0 1 0 3 -3 -11 1 60
Vậy ảnh của P sau phép tịnh tiến là Q(7,23,1) b, Phép biến đổi tỷ lệ tâm O(0,0,0) Phép biến đổi tỷ lệ thực hiện co dãn một đối tượng theo 3 hướng x, y, z theo các tỷ lệ lần lượt là Sx, Sy, Sz. Gọi Q(x’,y’,z’) là ảnh của P(x,y,z) sau khi thực hiện biến đổi tỷ lệ, ta có: x’= x.Sx y’ = y.Sy z’ = z.Sz Trong đó: - Nếu Sx=Sy=Sz ta có phép biến đổi đồng dạng - Sx, Sy, Sz > 1 ta có phép phóng to. - Sx, Sy, Sz < 1 Ta có phép thu nhỏ Sx 0 0 0 0 Sy 0 0 Ma trận của phép biến đổi tỷ lệ: MS = 0 0 Sz 0 0 0 0 1 Hình 3.6: Minh họa phép biến đổi tỷ lệ c, Phép quay tâm O(0,0,0) Khác với phép quay trong mặt phẳng quanh một điểm bất kì, trong không gian ba chiều ta có phép quay quanh một trục tọa độ. Ở đây, sử dụng hệ tọa độ theo quy ước bàn tay phải và quy định chiều quay dương khi nhìn từ ngoài vào gốc tọa độ là ngược chiều kim đồng hồ: - Quay quanh trục x : từ trục dương y đến trục dương z - Quay quanh trục y : từ trục dương z đến trục dương x 61
- Quay quanh trục z : từ trục dương x đến trục dương y y y y x x x z z z (c) (a) (b) Hình 3.7: Phép quay, (a) quay quanh trục z, (b) quanh trục x, (c) quanh trục y Ta có các ma trận biểu diễn các phép quay quanh trục x, y, z một góc α lần lượt là M(z, α), M(x, α), M(y,α): Quay quanh trục Oz : cosα sinα 0 0 -sinα cosα 0 0 M(z,α)= 0 0 1 0 0 0 0 1 Quay quanh trục Ox: 1 0 0 0 0 cosα sinα 0 M(x,α)= 0 -sinα cosα 0 0 0 0 1 Quay quanh trục Oy: cosα 0 -sinα 0 0 1 0 0 M(y,α)= sinα 0 cosα 0 0 0 0 1 Ví dụ: Tìm ảnh Q(x’,y’,z’) của điểm P(21,15,49) qua phép quay quanh Ox một góc 900. 62
Ta có: Q=P.M(x,α) 1 0 0 0 0 0 1 0 (x’ y’ z’ 1) = (21 15 49 1). 0 -1 0 0 0 0 0 1 Vậy ảnh của P sau phép tịnh tiến là Q(21,-49,15) 3.3.2 Các phép đối xứng a, Phép đối xứng qua mặt phẳng tọa độ: Ta có ma trận M của các phép đối xứng qua các mặt phẳng tọa độ xOy, xOz, yOz lần lượt là: 1 0 0 0 1 0 0 0 -1 0 0 0 0 1 0 0 0 -1 0 0 0 1 0 0 M(xOy)= M(xOz)= M(yOz)= 0 0 -1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 b, Phép đối xứng qua trục tọa độ: Ta có ma trận M của các phép đối xứng qua các trục tọa độ Ox, Oy, Oz lần lượt là: -1 0 0 0 1 0 0 0 -1 0 0 0 0 -1 0 0 0 -1 0 0 0 1 0 0 M(Oz)= M(Ox)= M(Oy) 0 0 1 0 0 0 -1 0 0 0 -1 0 0 0 0 1 0 0 0 1 0 0 0 1 c, Phép đối xứng qua gốc tọa độ: Phép lấy đối xứng qua gốc tọa độ tương đương với phép kết hợp của phép lấy đối xướng qua mặt phẳng xOy và phép lấy đối xứng qua trục Oz: -1 0 0 0 1 0 0 0 -1 0 0 0 0 -1 0 0 0 1 0 0 0 -1 0 0 M(O)= = 0 0 -1 0 0 0 -1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 63
3.3.3 Phép biến đổi tỷ lệ tâm bất kỳ Phép biến đổi tỷ lệ tâm bất kỳ I(x ,y ,z ) được xem là sự kết hợp từ các phép biến đổi i i i cơ sở sau: - Tịnh tiến theo vector (-x ,-y ,-z ) để dịch chuyển tâm biến đổi tỷ lệ về gốc tọa độ, i i i ta có ma trận của phép tịnh tiến là MT(-I) - Thực hiện biến đổi các đối tượng theo các tỷ lệ (Sx, Sy,Sz), ma trận Ms - Tịnh tiến theo vector (x ,y ,z ) để đưa tâm biến đổi tỷ lệ về lại vị trí ban đầu, ma i i i trận MT(I) 1 0 0 0 Sx 0 0 0 1 0 0 0 0 1 0 0 0 Sy 0 0 0 1 0 0 M= M M M = T(-I) s T(I) 0 0 1 0 0 0 Sz 0 0 0 1 0 0 1 0 0 -x -y -z 1 i i i 0 0 0 1 -xi -yi -zi 1 0 0 1 0 x y z 1 i i i Sx 0 0 0 0 Sy 0 0  M= 0 0 Sz 0 (1-Sx)x (1-Sy)y (1-Sz)z 1 i i i 3.4. Các phép chiếu Hình ảnh của các đối tượng trong thế giới thực là hình ảnh 3 chiều. Để có thể biểu diễn chúng trên màn hình các thiết bị hiển thị (2 chiều) một cách sinh động người ta cần thực hiện các phép chiếu, các phép tô chát (render) để gây ảo giác (illusion) về độ sâu. Đồ hoạ 3D là các kỹ thuật biểu diễn thế giới tự nhiên trên các thiết bị hiển thị 2 chiều. Khái niệm về phép chiếu: Một cách tổng quát, phép chiếu là phép chuyển đổi những điểm của đối tượng trong hệ thống tọa độ n chiều thành những điểm trong hệ thống tọa độ có số chiều nhỏ hơn n. Thông thường, ta chiếu các đối tượng đồ họa 3 chiều, miêu tả thế giới thực, xuống mặt phẳng 2 chiều của thiết bị hiển thị. Khái niệm về hình chiếu: Hình chiếu là ảnh của các đối tượng được hình thành từ phép chiếu, là giao của các tia chiếu (projector) với mặt phẳng chiếu. Tia chiếu là tia xuất phát từ một điểm gọi là tâm chiếu (center of projection) đi qua các điểm của đối tượng. Mặt phẳng chiếu (projection plan) là mặt phẳng thiết bị hiển thị. 64
3.4.1 Phép chiếu song song Phép chiếu song song (Parallel Projections) là phép chiếu mà ở đó các tia chiếu song song với nhau hay các tia chiếu xuất phát từ một điểm ở vô cùng. Phân loại phép chiếu song song dựa trên hướng của tia chiếu (Direction Of Projection) tới mặt phẳng chiếu (projection plane) a, Phép chiếu trực giao Là phép chiếu song song và tia chiếu vuông góc với mặt phẳng chiếu. Về mặt toán học, phép chiếu trực giao là phép chiếu mà mặt phẳng chiếu là một trong các mặt phẳng toạ độ, thường dùng mặt phẳng z=0 ( mặt phẳng xOy), ngoài ra có các mặt phẳng x=0 và y=0. Ứng với mỗi mặt phẳng chiếu ta có một ma trận chiếu tương ứng. 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 Tz= Tx= Ty= 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 Với các đối tượng hình hộp, người ta không sử dụng cả 6 mặt phẳng để suy diễn ngược hình của đối tượng (Hình 26a,) mà chỉ sử dụng một trong số chúng như: hình chiếu bằng, đứng, cạnh (Hình 26b,). Cả sáu góc nhìn đều có thể thu được từ một mặt phẳng chiếu thông qua các phép biến đổi hình học như quay, dịch chuyển hay lấy đối xứng. Giả sử chúng ta có hình chiếu bằng trên mặt phẳng z=0, với phép quay đối tượng quanh trục một góc 900 sẽ cho ta hình chiếu cạnh. Đối với các đối tượng mà các mặt của chúng không song song với một trong các mặt phẳng hệ toạ độ thì phép chiếu này không Hình 3.8: Phép chiếu trực giao, (a) phép chiếu 6 mặt, (b) phép chiếu 3 mặt cho hình dạng thật của vật thể. Muốn nhìn vật thể chính xác hơn người ta phải hình thành 65
phép chiếu thông qua việc quay và dịch chuyển đối tượng sao cho mặt phẳng đó song song với các trục toạ độ. Hình của đối tượng quá phức tạp cần thiết phải biết các phần bên trong của đối tượng đôi lúc chúng ta phải tạo mặt cắt đối tượng b, Phép chiếu trục lượng (Axonometric) Phép chiếu trục lượng là phép chiếu mà hình chiếu thu được sau khi quay đối tượng sao cho ba mặt của đối tượng được trông thấy rõ nhất (thường mặt phẳng chiếu là z=0). Kích thước hình chiếu của các đối tượng nằm trên mặt phẳng song song với mặt phẳng chiếu bằng với kích thước của đối tượng. Hình chiếu của các đối tượng nằm trên các mặt còn lại thường biến dạng sau phép chiếu theo tỷ lệ co SF (Shortening Factor). SF là tỷ số của kích thước hình chiếu với kích thước đối tượng thực. Trên cơ sở SF phép chiếu trục lượng được chia làm ba loại sau: - Phép chiếu Trimetric - Phép chiếu Dimetric - Phép chiếu Isometric (a) (b) (c) Hình 3.9: Minh họa phép chiếu trục lượng • Phép chiếu Trimetric Là phép chiếu hình thành từ việc quay tự do đối tượng trên một trục hay trên cả 3 trục của hệ tọa độ và chiếu đối tượng đó bằng phép chiếu song song lên mặt phẳng chiếu (thường là mặt phẳng z = 0). Hệ số co SF của phép chiếu Trimetric theo các hướng x, y, z là khác nhau. • Phép chiếu Dimetric Phép chiếu Dimetric là phép chiếu Trimetric có 2 hệ số co bằng nhau, giá trị thứ 3 còn lại là tuỳ ý. Phép chiếu được xây dựng bằng cách quay đối tượng quanh trục y theo một góc φ, tiếp đó quanh quanh trục ox một góc ϕ và sau cùng là phép chiếu song song lên mặt phẳng z=0. • Phép chiếu Isometric Phép chiếu Isometric là phép chiếu Trimetric mà ở đó hệ số co SF trên 3 trục là bằng nhau. c, Phép chiếu xiên Là phép chiếu song song, nhưng tia chiếu không vuông góc với mặt phẳng chiếu mà nó hợp với mặt phẳng chiếu một góc ф. • Phép chiếu Cavalier Phép chiếu Cavalier là phép chiếu xiên được tạo thành khi các tia chiếu làm thành với mặt phẳng chiếu một góc ф=450 hoặc ф=300. 66
Hệ số co trên các hệ trục toạ độ bằng nhau. Hình 19: Phép chiếu Cavalier, (a) góc ф=450 , (b) ф=300 • Phép chiếu Cabinet Phép chiếu xiên với hệ số co tỉ lệ f = 1/2 . Với phép chiếu Cabinet, giá trị của ф có thể thay đổi tuỳ ý. Các giá trị thường được sử dụng là ф=300 và ф=450 . Hình 20: Phép chiếu Cabinet, (a) góc ф=450 , (b) ф=300 3.4.2 Phép chiếu phối cảnh Phép chiếu phối cảnh là phép chiếu mà các tia chiếu không song song với nhau mà xuất phát từ một điểm gọi là tâm chiếu. 67
Phép chiếu phối cảnh tạo ra hiệu ứng về luật xa gần tạo cảm giác về độ sâu của đối tượng trong thế giới thật mà phép chiếu song song không lột tả được. P(x,y,z) y z x d Tâm chiếu Hình 212: Minh họa phép chiếu phối cảnh Để đạt được phép chiếu phối cảnh của đối tượng ba chiều, chúng ta chiếu các điểm theo đường thẳng chiếu để các đường này gặp nhau ở tâm chiếu. Trong hình 29, tâm chiếu trên trục Oz và có giá trị âm, cách một khoảng d phía sau mặt phẳng chiếu. Bất kỳ điểm nào cũng có thể được chọn làm tâm của phép chiếu, tuy nhiên việc chọn một điểm dọc theo trục Oz sẽ làm đơn giản việc tính toán trong các phương trình biến đổi. Trong trường hợp đối tượng là các đường thẳng song song và cũng song song với mặt phẳng chiếu thì ảnh chiếu nhận được là các đường thẳng song song. Ngược lại, khi đối tượng là các đường thẳng song song nhưng không song song với mặt phẳng chiếu thì ảnh chiếu nhận được sẽ là các đường hội tụ tại một điểm, điểm đó được gọi là tâm chiếu. (c) (a) (b) Hình 22: (a) Một tâm chiếu, (b) hai tâm chiếu, (c) ba tâm chiếu Mỗi tập hợp các đường thẳng song song được chiếu như thế sẽ có một tâm chiếu riêng. 68
Số lượng các tâm chiếu trong một phép chiếu được xác định bởi số lượng các trục của hệ tọa độ thực cắt mặt phẳng chiếu. Hình trên minh họa hình ảnh của các phép chiếu phối cảnh một tâm chiếu (a), hai tâm chiếu (b) và ba tâm chiếu (c) của một hình lập phương.[7] • Phép chiếu phối cảnh một tâm chiếu: Cho điểm P(x,y,z), tìm ảnh P’(x’,y’,z’) của P trên mặt phẳng chiếu z=0 với tâm chiếu I(0,0,d) nằm trên trục Oz. x hoặc y P(x,y,z) P’(x’,y’,0) x x’ I(0,0,d) O(0,0,0) z d z Hình 23: Phép chiếu phối cảnh tâm chiếu I(0,0,d) x’/d = x/(z+d) x’ = x/(z/d+1) Từ hình 31, ta có: y’/d = y/(z+d) y’ = y/(z/d+1) P’(x’, y’, 0) được viết dưới dạng tọa độ thuần nhất là P’(x’,y’,0,h) trong đó h=1. Khi đặt h’=z/d +1, ta có tọa độ thuần nhất của P’ là P’(x,y,0,h’). Từ đó ta có thể đưa ra ma trận của phép chiếu có dạng: 1 0 0 0 0 1 0 0 Mz = 0 0 0 1/d 0 0 0 1 69
Tương tự như vậy, để tìm ảnh P’(x’,y’,z’) của P(x,y,z) trên mặt phẳng chiếu x=0 ( y=0) với tâm chiếu I(k,0,0) ( I(0,r,0)) nằm trên trục Ox (Oy), ta có: 1 0 0 1/k 1 0 0 0 0 1 0 0 0 1 0 1/r Mx = My = 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 70
Câu hỏi ôn tập chương: 1, Trình bày phương pháp biểu diễn mặt đa giác và lưới đa giác. 2, Trình bày các phép biến đổi 3 chiều: Phép tịnh tiến, phép biến đổi tỷ lệ, phép quay và các phép lấy đối xứng. 3, Thế nào là phép chiếu song song, có những loại chiếu song song nào? 4, Thế nào là phép chiếu phối cảnh, có những loại chiếu phối cảnh nào? 5, Xây dụng ma trận của phép lấy đối xứng qua tâm bất kỳ. Hướng dẫn: Phép lấy đối xứng qua tâm bất kỳ là tổng hợp từ các phép biến đổi sau: - Phép tịnh tiến đưa tâm về gốc tọa độ - Phép lấy đối xứng tâm O(0,0,0) - Phép tịnh tiến đưa tâm đối xứng về vị trí ban đầu. 6, Xây dựng ma trận của phép lấy đối xứng qua mặt phẳng y = x. Hướng dẫn: Phép lấy đối xứng qua mặt phẳng y = x là tổng hợp từ các phép biến đổi sau: - Phép quay 450 quanh trục Oz để đưa mặt phẳng y=x về mặt phẳng yOz - Phép lấy đối xứng qua mặt phẳng yOz - Phép quay -450 quanh trục Oz để đưa về vị trí ban đầu của mặt phẳng y=x. Bài tập ôn tập: 1, Tìm ảnh của điểm P(5,7,1) qua phép tịnh tiến có độ dời theo trục Ox là dx=-3, theo trục Oy là dy=10, theo trục Oz là dz=7. 0 2, Tìm ảnh của điểm P(4,5,9) qua phép quay quanh trục Ox một góc α = -90 . 0 3, Tìm ảnh của điểm P(2,5,11) qua phép quay quanh trục Oy một góc α = 60 . 4, Tìm ảnh của điểm P(6,17,14) qua phép biến đổi tỷ lệ tâm O(0,0,0) với tỷ lệ biến đổi Sx=1.5, Sy=0.5, Sz=2. 5, Tìm ảnh của điểm P(2,12,6) qua phép biến đổi tỷ lệ tâm I(3,4,9) với tỷ lệ biến đổi Sx=2.5, Sy=2, Sz=1.5. 6, Tìm ảnh của đoạn thẳng P1(2,4,1)P2(7,10,22) sau khi thực hiện phóng to gấp 2 lần, cho biết ảnh của P1 vẫn là chính nó. 7, Tìm ảnh của điểm P(9,1,23) qua phép lấy đối xứng tâm I(3,4,17). 8, Tìm ảnh của điểm P(24,6,19) qua phép lấy đối xứng mặt phẳng xOy, trục Ox, tâm O(0,0,0) 9, Tìm ảnh của đoạn P1(4,16,23)P2(5,17,2) sau khi thực hiện chiếu phối cảnh một tâm chiếu tại: a, Ix(5,0,0) b, Iy(0,12,0) c, Iz(0,0,4) 71
10, Cho tam giác ABC có tọa độ: A(1,3,11), B(5,15,23), C(8,18,31). Tìm hình chiếu trực giao của tam giác ABC trên mặt phẳng chiếu xOy. 11, Chứng minh rằng trong các phép biến đổi, tâm biến đổi là điểm bất động (có ảnh là chính nó). 12. Anh ( chị) hãy trọn phát biểu đúng nhất: Trong phép biến đổi tỷ lệ, Sx, Sy được gọi là các hệ số tỷ lệ: a, Nếu Sx=Sy=Sz ta có phép biến đổi tỷ lệ đồng dạng b, Nếu Sx >1, Sy >1, Sz>1 ta có phép phóng to, đồng thời ảnh sẽ rời xa gốc tọa độ c, Nếu Sx <1, Sy <1, Sz <1 ta có phép thu nhỏ, đồng thời ảnh sẽ về gần gốc tọa độ d, Cả 3 ý trên đều đúng 13.Trong 3D có điểm P(13,25,1), đối xứng qua trục oy được Q là: a. (13,-25,-1) b. (-13,25,-1) c. (-25,13,1) d. (25,-13,1) 14.Trong 3D có điểm P(6,10,5), đối xứng qua gốc tọa độ O(0,0,0) được Q là: a. (-6,10,5) b. (6,-10,5) c. (-6,-10,-5) d. (-10,-6,-5) 15. Sau khi thực hiện tịnh tiến P(10,8,1) theo véc tơ độ dời (-6,3,9) rồi biến đổi theo tỷ lệ Sx=0.5, Sy=2, Sz=1 ta được Q là: a. (2,22,10) b. (22,2,10) c. (-1,19,5) d. (19,-1,5) 16. Trong không gian, lấy đối xứng điểm A(6,9,8) qua trục Oz rồi quay 90độ quanh Ox ta được điểm B(x,y,z) có tọa độ là: a. B(6,9,8) b. B(8,-9,6) c. B(-6,-9,8) d. B(-6,-8,-9) 17. Trong không gian, lấy đối xứng điểm A(2,5,3) qua trục Ox ta được điểm B(x,y,z) có tọa độ là: a. B(2,-5,-3) b. B(-2,5,-3) c. B(-5,2,3) d. B(5,-3,2) 72
CHƯƠNG 4: CÁC HỆ MÀU Mục tiêu của chương: Sinh viên cần nắm được khái niệm về ánh sáng và màu sắc theo hướng tiếp cận của kỹ thuật đồ họa, hiểu được cơ chế cảm nhận các sắc màu khác nhau của mắt người. Hiểu rõ về các chế độ màu RGBA và chỉ mục màu, biết xác định kích thước của bộ đệm dành cho bảng màu khi cho trước số bit để hiển thị màu cho 1 pixel. Hiểu về kỹ thuật phối màu để tạo ra một màu không có trong bảng màu. Sinh viên cần nắm được các cơ chế phối màu và hiển thị màu trên các hệ màu RGB, CMY, CMY-K, HSV 4.1 Ánh sáng và sự cảm nhận màu sắc của mắt Về mặt vật lý, ánh sáng bao gồm các photon - các hạt ánh sáng nhỏ, mỗi hạt đi dọc theo đường đi riêng của nó và mỗi hạt lại dao động theo tần số riêng (hay bước sóng, năng lượng riêng). Các photon có bước sóng nằm trong khoảng từ 390 nanomet (nm) (tím) và 720 nm (đỏ) bao phủ các màu của quang phổ nhìn thấy được, tạo thành các màu của cầu vồng (tím, chàm, xanh dương, xanh lục, vàng, cam, đỏ). Tuy nhiên, mắt của chúng ta cảm nhận được rất nhiều màu sắc không có trong cầu vồng - ví dụ như trắng, đen, nâu, hồng Làm thế nào điều này xảy ra? Những gì mắt thực sự nhìn thấy là một hỗn hợp các photon có tần số khác nhau. Nguồn sáng thực được đặc trưng bởi sự phân bố tần số photon mà chúng phát ra. Ánh sáng trắng lý tưởng bao gồm một lượng ánh sáng bằng nhau của tất cả các tần số. Ánh sáng laser thường rất tinh khiết và tất cả các photon đều có tần số gần như giống hệt nhau (cũng như hướng và pha). Ánh sáng từ đèn hơi natri có nhiều ánh sáng hơn ở tần số vàng. Ánh sáng từ hầu hết các ngôi sao trong không gian có sự phân bố phụ thuộc nhiều vào nhiệt độ của chúng. Sự phân bố tần số ánh sáng từ hầu hết các nguồn trong môi trường phức tạp hơn. Mắt người nhận biết màu sắc khi các tế bào trong võng mạc (tế bào hình nón) được kích thích sau khi tiếp nhận các photon ánh sáng. Ba loại tế bào hình nón khác nhau phản ứng tốt nhất với ba bước sóng ánh sáng khác nhau: một loại tế bào hình nón phản ứng tốt nhất với ánh sáng đỏ, một loại với màu xanh lá cây và loại kia là màu xanh lam. (Một người bị mù màu thường thiếu một hoặc nhiều loại tế bào hình nón.) Khi một chùm photon đi vào mắt, các tế bào hình nón trong võng mạc bị kích thích với mức độ nào đó. Mỗi mức độ kích thích tương đương với một màu sắc nhất định. Mắt có thể cảm nhận được các màu không có trong quang phổ do lăng kính hoặc cầu vồng tạo ra. Ví dụ, nếu chiếu một chùm photon đỏ (red) và xanh (blue) để cả hai loại tế bào hình nón màu đỏ và màu xanh trong võng mạc bị kích thích, mắt ta sẽ thấy nó là màu đỏ tươi (magenta), không có trong quang phổ. Các kết hợp khác cho màu nâu, màu xanh lam và màu tím nhạt một số màu không có trong trong phổ màu. 73