Giáo trình Đồ họa máy tính (Chi tiết)

227 trang Gia Huy 16/05/2022 6250

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Đồ họa máy tính (Chi tiết)", để 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_do_hoa_may_tinh_chi_tiet.pdf

Nội dung text: Giáo trình Đồ họa máy tính (Chi tiết)

Đồ họa máy tính MỤC LỤC Chƣơng 1 TỔNG QUAN VỀ ĐỒ HOẠ MÁY TÍNH 1 1.1. Các khái niệm tổng quan của kỹ thuật đồ họa máy tính 1 1.1.1. Kỹ thuật đồ họa máy tính 1 1.1.2.Kỹ thuật đồ họa tƣơng tác 1 1.2. Các kỹ thuật đồ họa 2 1.2.1.Kỹ thuật đồ hoạ điểm 3 1.2.2.Kỹ thuật đồ hoạ Vecto 4 1.2.3. Sự phát triển của kỹ thuật hiển thị 5 1.3. Phân loại các lĩnh vực của kỹ thuật đồ họa 7 1.3.1. Phân loại theo mục đích xử lý dữ liệu 7 1.3.2. Phân loại theo hệ tọa độ dùng trong kỹ thuật đồ họa 8 1.4.Giới thiệu một số ứng dụng của kỹ thuật đồ họa 8 1.4.1. Hỗ trợ thiết kế 8 1.4.2. Biểu diễn thông tin 9 1.4.3. Lĩnh vực giải trí, nghệ thuật 9 1.4.4. Điều khiển các quá trình sản xuất 10 1.4.5. Lĩnh vực bản đồ 10 1.4.5. Giáo dục và đào tạo 10 1.4.6. Giao tiếp giữa máy tính và ngƣời dùng 11 1.5. Hệ đồ họa tƣơng tác 12 1.5.1. Mô hình hệ tọa độ tƣơng tác 12 1.5.2. Các thành phần của hệ đồ họa tƣơng tác 12 1.6. Phần cứng đồ họa 15 1.6.1. Các thành phần phần cứng của hệ tọa độ tƣơng tác 15 1.6.2. Các thiết bị hiển thị (thiết bị ra dữ liệu) 15 1.6.3. Các thiết bị vào dữ liệu 19 CÂU HỎI CHƢƠNG 1 20 Chƣơng 2CÁC GIẢI THUẬT XÂY DỰNG CÁC THỰC THỂ CƠ SỞ 22 2.1 Giới thiệu 22 2.2. Các đối tƣợng đồ họa cơ sở 23 i
Đồ họa máy tính 2.2.1 Điểm 23 2.2.2. Đƣờng thẳng, đƣờng gấp khúc 24 2.2.3 Vùng tô 25 2.2.4 Kí tự, chuỗi kí tự 26 2.3. Giải thuật sinh đƣờng thẳng 27 2.3.1 Nguyên lý chung 27 2.3.2 Thuật toán DDA (Digital Differential Analyzer) 28 2.3.3 Giải thuật Bresenham 31 2.3.4 Thuật toán MidPoint 35 2.4. Giải thuật sinh đƣờng tròn 37 2.4.1 Nguyên lý chung 37 2.4.2 Thuật toán MidPoint 38 2.4.3 Giải thuật Bresenham 43 2.5. Giải thuật sinh elip 45 2.5.1. Giải thuật Midpoint 45 2.5.2. Giải thuật Bresenham 48 2.6. Giải thuật sinh đa giác 50 2.7. Giải thuật sinh ký tự 51 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 2 55 Hƣớng dẫn giải bài tập 61 Chƣơng 3CÁC GIẢI THUẬT ĐỒ HOẠ CƠ SỞ 64 3.1. Hệ toạ độ và mô hình chuyển đổi 64 3.1.1. Các hệ thống tọa độ trong đồ họa 64 3.1.2. Phép chuyển đổi 65 3.2. Các giải thuật xén tỉa 66 3.2.1. Khái niệm 66 3.2.2. Các giải thuật xén tỉa đoạn thẳng 66 3.2.3. Giải thuật Hodgman 76 3.3. Các giải thuật tô miền kín 77 3.3.1. Giải thuật đƣờng biên 77 3.3.2. Giải thuật dòng quét cho việc tô màu vùng 78 ii
Đồ họa máy tính CÂU HỎI VÀ BÀI TẬP CHƢƠNG 3 82 Hƣớng dẫn giải bài tập 88 Chƣơng 4CÁC PHÉP BIẾN ĐỔI HÌNH HỌC 2 CHIỀU 92 4.1.Phƣơng pháp biểu diễn đối tƣợng trong không gian hai chiều 92 4.2. Phép biến đổi Afine 2D 93 4.3. Các phép biến đổi hình học cơ sở 93 4.3.1. Phép tịnh tiến 93 4.3.2. Phép biến đổi tỉ lệ 94 4.3.2. Phép quay 95 4.3.3. Phép đối xứng 96 4.3.4. Phép biến dạng 96 4.4. Hệ tọa độ thuần nhất và các phép biến đổi 97 4.4.1. Hệ tọa độ thuần nhất 97 4.4.2. Biểu diễn các phép biến đổi dƣới dạng tọa độ thuần nhất 98 4.4.3. Phép biến đổi ngƣợc 99 4.5. Kết hợp các phép biến đổi 100 4.5.1. Kết hợp các phép tịnh tiến 100 4.5.2. Kết hợp các phép tỉ lệ 102 4.5.3. Kết hợp các phép quay 104 4.5.4. Phép quay có tâm quay là điểm bất kỳ 104 4.5.5. Phép tỉ lệ giữ nguyên điểm chốt 105 4.6. Phép biến đổi giữa các hệ tọa độ 106 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 4 108 Hƣớng dẫn giải bài tập 113 Chƣơng 5CÁC PHÉP BIẾN ĐỔI HÌNH HỌC 3 CHIỀU 123 5.1. Giới thiệu đồ họa ba chiều 123 5.1.1. Tổng quan về đồ họa ba chiều 123 5.1.2. Sơ lƣợc về quy trình hiển thị 124 5.1.3. Mô hình khung nối kết (Wireframe Model) 126 5.2. Một số khái niệm 128 5.2.1. Phƣơng pháp biểu diễn điểm trong không gian 3 chiều. 128 iii
Đồ họa máy tính 5.2.2. Phƣơng pháp biểu diễn sử dụng hệ tọa độ đồng nhất. 129 5.2.3. Công thức biến đổi Affine. 130 5.2.4. Các hệ trục tọa độ theo quy ƣớc bàn tay phải và bàn tay trái 131 5.3. Các phép biến đổi hình học 3 chiều cơ sở 131 5.3.1. Phép tịnh tiến 131 5.3.2. Phép biến đổi tỉ lệ 132 5.3.3. Phép biến dạng 133 5.3.4. Phép quay 134 5.3.5.Phép đối xứng. 139 5.3.6 Kết hợp các phép biến đổi affine ba chiều 144 5.4. Các phép chiếu của vật thể trong không gian lên mặt phẳng 144 5.4.1. Định nghĩa chung 144 5.4.2. Phân loại phép chiếu 145 5.4.3. Phép chiếu song song 146 5.4.4. Phép chiếu phối cảnh (Perspective Projection) 154 5.5. Phép biến đổi mô hình và phép biến đổi hệ trục toạ độ 158 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 5 160 Hƣớng dẫn giải bài tập 168 Chƣơng 6MÀU SẮC TRONG ĐỒ HỌA 175 6.1. Ánh sáng đơn sắc 175 6.1.1. Cƣờng độ sáng và cách tính 175 6.1.2. Hiệu chỉnh Gama 176 6.2. Lý thuyết màu sắc trong đồ họa 182 6.2.1. Cảm nhận màu sắc 182 6.2.2. Yếu tố vật lý 184 6.2.3. Biểu đồ màu CIE 185 6.3. Giới thiệu về các hệ màu trong màn hình đồ họa 189 6.3.1. Mô hình màu RGB 189 6.3.2.Mô hình màu CMY 192 6.3.3. Mô hình màu YIQ 193 6.3.4. Mô hình màu HSV 194 iv
Đồ họa máy tính 6.3.5. Mô hình màu HLS 196 6.3.6. Chuyển đổi giữa các hệ màu 197 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 6 215 Hƣớng dẫn giải bài tập 220 v
Đồ họa máy tính Chƣơng 1TỔNG QUAN VỀ ĐỒ HOẠ MÁY TÍNH 1.1. Các khái niệm tổng quan của kỹ thuật đồ họa máy tính Đồ họa máy tính là tất cả những gì liên quan đến việc sử dụng máy tính để phát sinh ra hình ảnh. Các vấn đề liên quan tới công việc này bao gồm: tạo, lƣu trữ, thao tác trên các mô hình (các mô tả hình học của đối tƣợng) và các ảnh. 1.1.1. Kỹ thuật đồ họa máy tính Kỹ thuật đồ hoạ máy tính (Computer Graphics) có thể định nghĩa nhƣ một lĩnh vực của công nghệ thông tin mà ở đó 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 (model) và hình ảnh (image) của đối tƣợng, sự vật hiện tƣợng khác nhau trong cuộc 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 nhiều ngành nghề khoa học (vật lý, toán học, thiên văn học ) và bao trùm nhiều thể loại nhƣ: cấu trúc phân tử, cấu trúc sinh học, mô hình vũ trụ Thuật ngữ kỹ thuật đồ hoạ máy tính đƣợc đề xuất bởi nhà khoa học ngƣời Mỹ William Fetter vào năm 1960. Khi đó ông đang nghiên cứu xây dựng mô hình buồng lái máy bay cho hãng Boeing của Mỹ. William Fetter đã dựa trên các hình ảnh ba chiều của mô hình ngƣời phi công trong buồng lái 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 Boeing. Đây là phƣơng pháp nghiên cứu rất mới và có những tính năng vƣợt trội hơn tất cả những phƣơng pháp nghiên cứu xây dựng mô hình buồng lái máy bay khác trƣớc đó đƣợc áp dụng trong hãng Boeing. Phƣơng pháp này cho phép nhà thiết kế quan sát một cách trực quan vị trí của ngƣời lái trong khoang buồng lái. William Fetter đã đặt tên cho phƣơng pháp của mình là Computer Graphics. 1.1.2.Kỹ thuật đồ họa tƣơng tác Cũng nhƣ mọi lĩnh vực khác trong công nghệ thông tin, một hệ thống sử dụng kỹ thuật đồ hoạ tƣơng tác là một hệ thống xử lý thông tin bao gồm ba thành phần với các thao tác tƣơng ứng: Nhập (vào) dữ liệu: thông qua các thiết bị vào dữ liệu nhƣ chuột, máy quét, bàn phím Xử lý và lƣu trữ dữ liệu Hiển thị/ kết xuất kết quả: thông qua các thiết bị nhƣ màn hình, máy in 1
Đồ họa máy tính Ngoài những đặc thù chung đã đƣợc liệt kê ở trên, hệ thống kỹ thuật đồ hoạ tƣơng tác còn có một đặc điểm: trong hệ thống này, các thông tin và dữ liệu đặc trƣng đƣợc hiển thị trên màn hình một cách trực quan và ngƣời sử dụng có thể quan sát, theo dõi, thay đổi giá trị hoặc khuôn dạng của chúng một cách tƣơng tác (interactive) và ngay lập tức những thay đổi này đƣợc hệ thống ghi nhận và xử lý . Kết quả của sự thay đổi sẽ đƣợc hệ thống xử lý ngay trên các mô hình, cấu trúc hoặc hình ảnh của các đối tƣợng và hiển thị chúng ngay trên màn hình ngƣời sử dụng mong muốn. Nhập dữ liệu Xử lý lƣu trữ Hiển thị kết quả USER Hình 1.1 Mô hình chung của hệ đồ họa tương tác Nhƣ trên mô hình chung của một hệ thống sử dụng kỹ thuật đồ hoạ tƣơng tác, ngƣời sử dụng có khả năng giao tiếp tƣơng tác với hệ thống ở cả ba giai đoạn trong quá trình xử lý thông tin. Hệ thống đồ hoạ tƣơng tác đầu tiên đƣợc thiết kế và xây dựng bởi Ivan Sutherland năm 1963 mang tên Sketchpad. Hệ thống này đƣợc dùng để thiết kế mạch điện và bao gồm những thành phần sau: CRT màn hình. Bút chì sáng và một bàn phím bao gồm một số phím bấm chức năng. Máy tính chứa chƣơng trình xử lý các thông tin. Ngƣời sử dụng có thể vẽ mạch điện trực tiếp lên màn hình thông qua bút sáng, chƣơng trình sẽ phân tích và tính toán những thông số cần thiết của mạch điện do ngƣời sử dụng vẽ nên. 1.2. 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 ngày càng nhiều và đa dạng. Tuy vậy căn cứ vào phƣơng pháp xử lý dữ liệu trong hệ thống, có thể phân kỹ thuật đồ họa thành hai loại: kỹ thuật đồ họa điểm (Sample – Based Graphics) và kỹ thuật đồ họa vector (Geometry – Based Graphics). 2
Đồ họa máy tính 1.2.1.Kỹ thuật đồ hoạ điểm Nguyên lý xây dựng các mô hình và hình ảnh trong kỹ thuật đồ họa điểm là: Các mô hình, hình ảnh của các đối tƣợng đƣợc hiển thị thông qua từng điểm ảnh (pixel). Đặc điểm của kỹ thuật đồ họa điểm: - Có thể tạo ra, thay đổi thuộc tính, xoá đi từng điểm ảnh 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 (grid) các điểm ảnh rời rạc, từng điểm ảnh đề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ị ví dụ nhƣ màu sắc hoặc độ sáng. - Tập hợp tất cả các điểm ảnh của lƣới điểm cho ta mô hình, hình ảnh đối tƣợng ta muốn hiển thị để nghiên cứu hoặc xây dựng. Có hai phƣơng pháp để tạo ra các điểm ảnhtrong kỹ thuật đồ họa điểm: - Dùng phần mềm để vẽ trực tiếp từng điểm ảnh một, dựa trên các lý thuyết mô phỏng để xây dựng nên các đối tƣợng hoặc hình ảnh thực của sự vật. - Rời rạc hóa (số hóa) hình ảnh thực của đối tƣợng, sau đó có thể sửa đổi hoặc xử lý mảng các điểm ảnh 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. Hình 1.2 Ví dụ ảnh đồ họa điểm 3
Đồ họa máy tính Hình 1.3 Kỹ thuật đồ họa điểm 1.2.2.Kỹ thuật đồ hoạ Vector Nguyên lý của kỹ thuật này là xây dựng mô hình hình học (geometrical model) cho hình ảnh đối tƣợng, xác định các thuộc tính của mô hình hình học, sau đó dựa trên mô hình này để thực hiện quá trình tô trát (rendering) để hiển thị từng điểm trên mô hình, hình ảnh của đối tƣợng. Mô hình của một hình ảnh phải lột tả một cách chính xác và làm nổi bật những điểm chính nhất của hình ảnh đó. Thông thƣờng quá trình mô hình hóa sử dụng phƣơng pháp thiết kế từ trên xuống (top-down) và kết quả thu đƣợc là một sơ đồ phân cấp. Sơ đồ này cần phải chỉ rõ những thành phần cơ sở của đối tƣợng và phƣơng thức kết nối giữa các thành phần này. Ở kỹ thuật này, ta chỉ lƣu trữ mô hình 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 mà không cần lƣu lại toàn bộ tất cả các pixel của hình ảnh đối tƣợng. 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à thực thể cơ sở hình học của mô hình hình học. Hình ảnh đƣợc xây dựng từ các thực thể cơ sở sau đó đƣợc tô trát theo điểm ảnh nhƣng những điểm ảnh này không đƣợc lƣu trữ nhƣ một thành phần của mô hình. Nhƣ thế hình ảnh có thể đƣợc tô trát từ nhiều điểm nhìn và góc nhìn khác nhau dựa trên cùng một mô hình mẫu. 4
Đồ họa máy tính Hình 1.4 Ví dụ về hình ảnh đồ họa vector Hình 1.5 Kỹ thuật đồ họa Vector 1.2.3. Sự phát triển của kỹ thuật hiển thị Đồ hoạ máy tính là một trong những lĩnh vực quan trọng nhất đóng góp cho quá trình phát triển của môi trƣờng giao diện trong lịch sử phát triển của máy tính. Những phát triển này đƣợc nảy sinh nhƣ sau: Giao diện đồ họa tƣơng tác với ngƣời sử dụng. Xây dựng các phần mềm trực quan (thiết kế quảng cáo, hiển thị khoa học, ) 5
Đồ họa máy tính Những yêu cầu này đã thúc đẩy sự phát triển của kỹ thuật đồ hoạ, giao diện với ngƣời sử dụng càng đẹp, càng phải dễ sử dụng càng làm sáng tỏ những kỹ thuật mới trong đồ hoạ Các kỹ thuật hiển thị đã nảy sinh và phát triển theo những giai đoạn sau: 1) Kỹ thuật hiển thị bằng ký tự Kỹ thuật này chỉ cho phép hiển thị văn bản và các hình đồ hoạ đơn giản. Giao tiếp với ngƣời sử dụng thông qua các lệnh dƣới dạng văn bản. Để có thể mã hoá những phƣơng thức hiển thị khác nhau của đối tƣợng ngƣời ta sử dụng những ký tự mã hoá đặc biệt. 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 những năm 1980 và đầu những năm 1990 của hãng Microsoft; phần mềm soạn thảo văn bản BKED chạy trên môi trƣờng MS- DOS. 2) Kỹ thuật hiển thị vector Kỹ thuật này phát triển từ 1963 đến 1980 cho phép hiển thị văn bản và vẽ các đƣờng thẳng, các mô hình mô phỏng đơn giản. Ngƣời sử dụng có thể quan sát thấy các hình ảnh 2D và 3D của các đối tƣợng. 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 ký tự nóng và menu chọn. Ở đây xuất hiện ý tƣởng ban đầu về phƣơng thức WYSIWYG (What You See Is What You Get – Bạn nhìn thấy gì thì bạn nhận đƣợc cái đó). Môi trƣờng sử dụng (hệ điều hành) là đơn nhiệm hoặc đa nhiệm phân tán. 3) Ảnh hai 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ế tối đa việc gõ các lệnh (tuy nhiên vẫn cho phép ngƣời sử dụng nhập lệnh theo phƣơng thức này). Việc tƣơng tác với ngƣời sử dụng đƣợc thực hiện thông qua kỹ thuật tiêu biểu sau: - Thông qua WIWP (Windows, icon,menus, pointer) của giao diện đồ hoạ (Graphics Use Interface): có thể chọn và nhấn vào thực đơn ta muốn mà không phải viết lệnh. - Xử lý trực tiếp các đối tƣợng (drag and drop). Ở đây phƣơng thức WYSIWYG đƣợc hoàn thiện và phát triển. Môi trƣờng sử dụng thông thƣờng là đa nhiệm (multi-task) hoặc cơ chế Client -Server trên mạng. 6
Đồ họa máy tính Ví dụ điển hình cho các hệ điều hành thuộc kỹ thuật này là các hệ điều hành windows 3x và sau đó là windows 9x của hãng Microsoft. 4) Trạm làm việc đồ hoạ (3D Graphics workstation) và các công nghệ hiển thị tiên tiến khác Công nghệ này đƣợc xây dựng và phát triển trong công ty Sillcon Graphics, một trong những công ty hàng đầu của Mỹ về lĩnh vực đồ hoạ. Công nghệ này cho phép hiển thị các hình ảnh thực và hình ảnh không gian ba chiều của hình ảnh của sự vật dựa trên các cảnh trí (Sence) 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 hai chiều (2D), ba chiều (3D) và mô phỏng thế giới thực. Các thao tác xử lý trực tiếp các đối tƣợng đƣợc xây dựng mạnh hơn. Môi trƣờng làm việc thông thƣờng là đa nhiệm và Client – Server 1.3. Phân loại các lĩnh vực của kỹ thuật đồ họa 1.3.1. Phân loại theo mục đích xử lý dữ liệu Hình 1.6 Phân loại theo các lĩnh vực của đồ họa máy tính - Kỹ thuật xử lý ảnh (Computer Imaging): sau quá trình xử lý ảnh cho ta ảnh số của đối tƣợng. Trong quá trình xửlý ảnh sử dụng 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. Ví dụ ảnh chụp vũ trụ, ảnh truyền qua vệ tinh - 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 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. 7
Đồ họa máy tính - Kỹ thuật tổng hợp ảnh (Image Synthesis): là lĩnh vực xây dựng mô hình và hình ảnh của các vật thể dựa trên các đối tƣợng và mối quan hệ giữa chúng. - Các hệ CAD/CAM (Computer Aided Design/Computer Aided Manufacture System): kỹ thuật đồ hoạ tập hợp các công cụ, các kỹ thuật trợ giúp cho thiết kế các chi tiết và các hệthống khác nhau: hệ thống cơ, hệ thống điện, hệ thống điện tử . - Đồ hoạ 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. - Đồ hoạ hoạt hình và nghệ thuật: bao gồm các công cụ giúp cho các hoạ sĩ, các nhà thiết kế phim hoạt hình chuyên nghiệp làm các kỹ xảo hoạt hình, vẽ tranh Ví dụ: phần mềm 3D Studio, 3D Animation, 3D Studio Max. 1.3.2. Phân loại theo hệ tọa độ dùng trong kỹ thuật đồ họa Hình 1.7 Phân loại theo hệ tọa độ - 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ệ tọa độ 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ệ tọa độ ba chiều, đòi hỏi 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.4.Giới thiệu một số ứng dụng của kỹ thuật đồ họa 1.4.1. 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 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. Sử dụng những chƣơng trình này, đầu tiên các đối tƣợng đƣợc hiển thị dƣới dạng các phác thảo của phần khung (wireframe outline), từ đó có thể thấy đƣợc toàn bộ hình dạng và các thành phần bên trong của đối tƣợng. Sử dụng kĩ thuật này, ngƣời thiết kế sẽ dễ dàng nhận thấy ngay các thay đổi của đối tƣợng khi tiến hành hiệu chỉnh các chi tiết hay thay đổi góc nhìn, . 8
Đồ họa máy tính Một khi đã thiết kế xong phần khung của đối tƣợng, các mô hình chiếu sáng, tô màu và tạo bóng bề mặt sẽ đƣợc kết hợp để tạo ra kết quả cuối cùng gần với thế giới thực. Hình 1.8 Phác thảo phần khung và kết quả của thiết kế xy lanh 1.4.2. Biểu diễn thông tin Đây là các ứng dụng sử dụng đồ họa máy tính để phát sinh các biểu đồ, đồ thị, dùng minh họa mối quan hệ giữa nhiều đối tƣợng với nhau. Các ứng dụng này thƣờng đƣợc dùng để tóm lƣợc các dữ liệu về tài chính, thống kê, kinh tế, khoa học, toán học, giúp cho việc nghiên cứu, quản lí, thêm có hiệu quả. Hình 1.9 Thông tin tóm lược được biểu diễn qua các biểu đồ 1.4.3. 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 9
Đồ họa máy tính 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 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 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 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), Hình 1.10 Hình ảnh được tạo ra từ chương trình đồ họa 1.4.4. Điều khiển các quá trình sản xuất Các chƣơng trình cho phép theo dõi toàn bộ quá trình nào đó xảy ra trong thực tế bằng cách mô phỏng toàn bộ các diễn biến xảy ra trong quá trình này và thông qua các giao thức ghép nối ngƣời ta có thể kiểm soát đƣợc toàn bộ diễn biến của quá trình thực hiện. 1.4.5. Lĩnh vực bản đồ Đồ họa máy tính đƣợc sử dụng để xây dựng và in các bản đồ địa lý nhƣ bản đồ địa hình, bản đồ dân số, Một trong những ứng dụng hiện nay là hệ thống thông tin địa lý GIS (Geographical Information System), kết hợp giữa đa phƣơng tiện (Multimedia) và cơ sở dữ liệu (Database) 1.4.5. 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. 10
Đồ họa máy tính 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, Hình 1.11 Chương trình học về máy tính 1.4.6. 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 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. 11
Đồ họa máy tính Hình 1.12 Giao diện của chương trình MS Word 1.5.Hệ đồ họa tƣơng tác 1.5.1.Mô hình hệ tọa độ tƣơng tác 1) Khái niệm xử lý theo lô (Batch processing) Xử lý theo lô là chế độ thao tác của máy tính trong đó các chỉ thị lệnh chƣơng trình đƣợc thực hiện lệnh này liên tiếp sau lệnh kia mà không cần sự can thiệp của ngƣời sử dụng máy tính. Xử lý theo lô thể hiện sự hiệu quả khi sử dụng nguồn tài nguyên dự trữ của máy tính, nhƣng thể hiện sự bất tiện khi ngƣời sử dụng cần hiệu chỉnh lỗi và giao tiếp với máy tính. 2) Khái niệm tƣơng tác (Interactive processing) Đây là phƣơng pháp xử lý của máy tính, cho phép ngƣời dùng có thể bắt giữ và hiệu chỉnh các sai sót trƣớc khai thao tác xử lý đƣợc hoàn chỉnh. Tính năng này của các phần mềm hiện nay cho phép ngƣời sử dụng xử lý dễ dàng hơn, các thao tác thực hiện mềm dẻo hơn. 1.5.2. Các thành phần của hệ đồ họa tƣơng tác Hình 1.13 Mô hình của hệ đồ họa tương tác Mô hình ứng dụng (application model) 12
Đồ họa máy tính Phần mềm ứng dụng (application program) Hệ thống đồ họa (phần mềm hệ thống) o Thƣ viện đồ họa (phần mềm đồ họa hệ thống) o Phần cứng đồ họa Thành phần xử lý tƣơng tác ngƣời dùng (Interaction Handling) Các chuẩn của hệ đồ họa 1) Mô hình ứng dụng và xây dựng mô hình ứng dụng (Application Model) Mô hình ứng dụng phải lƣu trữ tất cả các dữ liệu, các đối tƣợng và mối liên kết giữa các đối tƣợng này để có thể hiển thị hoặc biểu diễn chung. Một đối tƣợng có thể đƣợc biểu diễn bằng sự kết hợp giữa dữ liệu và một số thủ tục mô tả các đối tƣợng này (sử dụng ngôn ngữ lập trình hƣớng đối tƣợng). Nhƣ vậy mô hình ứng dụng có thể đƣợc chia làm 2 thành phần: - Mô hình dữ liệu (data model): (mảng ghi tọa độ các pixel, danh sách các đối tƣợng, ) lƣu lại dữ liệu về các đối tƣợng và thông thƣờng ngƣời ta dùng các cơ sở dữ liệu (database) để lƣu trữ dữ liệu này. - Thƣ viện mô tả: Các thủ tục mô tả các đối tƣợng đƣợc xây dựng nên từ các thực thể cơ sở (primitive) để có thể mô tả các thành phần (component) của các đối tƣợng, các thuộc tính (attribute) của các thành phần này, các phƣơng thức kết nối (connectivity) giữa các thành phần. 2) Phần mềm ứng dụng (application program) Phần mềm ứng dụng đƣợc xây dựng để có thể tạo ra, lƣu giữ lại, lấy ra những dữ liệu và các thủ tục từ mô hình ứng dụng (application model). Phần mềm này đƣợc xây dựng trên cơ sở mô hình ứng dụng và ở phần mềm ứng dụng các đối tƣợng, dữ liệu sẽ đƣợc hiển thị trên màn hình theo phƣơng thức ngƣời dùng mong muốn. Ngoài ra để hệ thống là hệ đồ họa tƣơng tác, phần mềm ứng dụng phải xây dựng đƣợc giao diện với ngƣời sử dụng một cách thuận tiện, để các thay đổi mà ngƣời sử dụng muốn có thể tƣơng tác lên ngay lập tức các đối tƣợng và hiển thị lại chúng. 3) Hệ thống đồ họa (graphics system) Phần mềm đồ họa hệ thống là tập hợp các lệnh đồ họa của hệ thống (graphics output commands), tập hợp các lệnh này cần phải thực hiện công việc hiển thị cái gì 13
Đồ họa máy tính (what object) và chúng sẽ đƣợc hiển thị nhƣ thế nào (how). Phần mềm đồ họa hệ thống là phần mềm xây dựng trên cơ sở một thể loại phần cứng nhất định và phụ thuộc vào phần cứng. Phần cứng đồ họa: là tập hợp các thiết bị điện tử (CPU, màn hình, chuột, bàn phím, ) giúp cho việc thực hiện các phần mềm đồ họa. Phần mềm đồ họa (application program) sẽ vẽ các đối tƣợng nhờ gọi các hàm và thủ tục có ở thƣ viện đồ họa, sử dụng các tài nguyên của phần cứng đồ họa. 4) Thành phần thƣ viện đồ họa a) Các thực thể cơ sở (các ảnh gốc) Thực thể cơ sở là các đối tƣợng cơ bản nhất cho việc xây dựng các đối tƣợng và hình ảnh, thông thƣờng các thực thể cơ sơ bao gồm: - Điểm (pixel) - Đƣờng thẳng (line) - Đƣờng tròn (circle) - Đa giác (polygon) b) Các thuộc tính Thuộc tính của các thực thể cơ sở và thay đổi các thuộc tính này cũng đóng vai trò quan trọng trong việc xây dựng các đối tƣợng và hình ảnh. Thông thƣờng thuộc tính có thể liệt kê ra gồm: - Màu sắc (color) - Kiểu đƣờng vẽ (line style) - Kiểu văn bản (text style) - Mẫu tô (pattern). Các phép biến đổi và hệ quan sát: một khi đã xây dựng ảnh gốc và thuộc tính, chúng ta thu đƣợc một hình ảnh xác định trong hệ tọa độ không gian thực, có thể phải sử dụng một số phép biến đổi nào đó, sau đó cần phải chiếu phần quan sát đƣợc của các đối tƣợng và ảnh sang một thiết bị xuất cụ thể nào đó. c) Chiếu sáng Cùng với việc chiếu phần quan sát đƣợc của ảnh, ngƣời ta còn phải tính toán đƣợc cƣờng độ sáng của từng điểm ảnh đƣợc chiếu. Đây là một quá trình tính toán phức tạp dựa trên những công thức toán học và bản chất quang học, sinh học của hấp thụ và phản chiếu ánh sáng. 14
Đồ họa máy tính 1.6. Phần cứng đồ họa 1.6.1. Các thành phần phần cứng của hệ tọa độ tƣơng tác Các thành phần phần cứng của hệ đồ hoạ tƣơng tác gồm: - 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. - Gói phần mềm đồhoạ(Graphics Package): cung cấp các hàm đồhoạcho chƣơng trình ứng dụng - Phần mềm ứng dụng (Application Program): phần mềm đồhoạ ứng dụng. - Bộ đệm (Frame buffer): có nhiệm vụ chứa các hình ảnh hiển thị. - Bộ điều khiển màn hình(Video Controller): điều khiển màn hình, chuyển dữliệu dạng số ởframe buffer thành các điểm sáng trên màn hình. Hình 1.14 Các thành phần cứng của hệ đồ hoạ tương tác 1.6.2. Các thiết bị hiển thị (thiết bị ra dữ liệu) 1)Màn hình CRT Màn hình là thiết bị hiển thị thông dụng nhất trong một hệ đồ họa. Các thao tác của hầu hết màn hình đều dựa trên thiết kế của ống tia âm cực (CRT – cathode ray tube). 15
Đồ họa máy tính a) Cấu tạo của CRT Hình dƣới đây minh họa thao tác cơ sở của một ống tia âm cực. Một chùm các tia điện tử (tia âm cực) phát ra từ một súng điện tử, vƣợt qua các hệ thống hội tụ (focusing) và dẫn hƣớng (deflection) sẽ hƣớng tới các vị trí xác định trên màn hình đƣợc phủmột lớp phosphor. Tại mỗi vị trí tƣơng tác với tia điện tử, hạt phosphor sẽ phát ra một chấm sáng nhỏ. Vì ánh sáng phát ra bởi các hạt phosphor mờ dần rất nhanh nên cần phải có một cách nào đó để duy trì ảnh trên màn hình. Một trong các cách đó là lặp đi lặp lại nhiều lần việc vẽ lại ảnh thật nhanh bằng cách hƣớng các tia điện tử trở lại vị trí cũ. Kiểu hiển thị này gọi là refresh CRT. Hình 1.15 Cấu tạo của CRT Hình 1.16 Công nghệ màn hình CRT Số lƣợng tối đa các điểm có thể hiển thị trên một CRT đƣợc gọi là độ phân giải (Resolution). Hay độ phân giải là số lƣợng các điểm trên một cm mà có thể đƣợc vẽ theo chiều ngang và chiều dọc (đƣợc xem nhƣ tổng số điểm theo mỗi hƣớng). Kích thƣớc vật lý của màn hình đồ hoạ đƣợc tính từ độ dài của đƣờng chéo màn hình và thƣờng dao động từ 12-27 inch, hoặc lớn hơn. 16
Đồ họa máy tính Thuộc tính khác của màn hình là tỷ số phƣơng (aspect ratio). Nó là tỷ lệ của các điểm dọc và các điểm ngang cần để phát sinh các đoạn thẳng có độ dài đơn vị theo cả hai hƣớng trên màn hình. Màn hình có tỷ số phƣơng khác một, thì hình vuông hiển thị trên đó thành hình chữ nhật còn hình tròn thành hình Ellipse. b) Phƣơng thức hiển thị Căn cứ vào phƣơng thức hiển thị các dữ liệu hình học trên màn hình, ngƣời ta có hai loại thiết bị hiển thị: Các thiết bị hiển thị dạng vector Quét vector theo tọa độ các điểm đầu và cuối của vector. Ngƣời ta sử dụng các cuộn lái tia để quét thành các đoạn thẳng và nhƣ thế để vẽ đƣợc một đối tƣợng đồ họa ngƣời ta phải phân tích đối tƣợng thành các đoạn thẳng cơ sở và lần lƣợt vẽ chúng. Các thiết bị hiển thị dạng đƣờng rất thích hợp cho việc hiển thị các đối tƣợng hình học, tịnh tiến, quay dễ dàng nhƣng lại không hiệu quả với việc tô màu các vùng kín vì để làm đƣợc điều này chúng ta phải vẽ nhiều đƣờng thẳng thật gần nhau để xấp xỉ thành vùng đƣợc tô và điều này hạn chế tốc độ của ứng dụng. Nhƣ vậy đối với các ảnh phức tạp cần tới thời gian vẽ lớn, tốc độ làm tƣơi chậm, màn hình sẽ bị nháy. Hình 1.17. Kiến trúc hiển thị Vector Kiến trúc hiển thị vector làm việc với tệp hiển thị chứa những vector mà hệ thống cần phải hiển thị (display commands) MOVE 10 , 15 LINE 400 , 300 LINE 600 , 800 Refesh Buffer 17
Đồ họa máy tính Các thiết bị hiển thị dạng điểm Tia điện tử quét ngang trên màn hình từ trái sang phải, khi quét hết một dòng ngang, tia điện tử đƣợc dập tắt và lái hồi về đầu dòng tiếp (hồi ngang). Một hàng là một tập hợp các điểm X khi tia điện tử quét từ trái sang phải thì nó cũng lái theo chiều dọc từ trên xuống dƣới Y.Mỗi điểm màn hình tại một điểm sáng (tối) đƣợc gọi là pixel. Hình 1.18 Kiến trúc hiển thị Bitmap Bộ đệm (frame buffer) đƣợc tổ chức nằm bên trong bộ nhớ của hệ thống (8086/8088). Có riêng một bộ xử lý hiển thị. Dữ liệu hiển thị đƣợc dùng chung, bộ nhớ đƣợc tổ chức thành không gian nhớ ảo, Video RAM đƣợc phân biệt. (80486/80586). Hình 1.19. Mô hình dữ liệu của thiết bị hiển thị điểm 2) Màn hình tinh thểlỏng (Liquid Crystal Display – LCD) Dựa vào công nghệ truyền ánh sáng qua điện cực mà đặt giữa là cuộn dây xoắn. Khi chƣa có từ trƣờng (chƣa có dòng điện) ở cuộn dây thì ánh sáng truyền thẳng, khi có từ trƣờng thì ánh sáng truyền đổi chiều. 18
Đồ họa máy tính Hình 1.17 Công nghệ truyền ánh sáng trong màn hình tinh thể lỏng 3) Máy in Hiện tại có nhiều loại máy in, sử dụng các công nghệ khác nhau nhƣ in kim, in phun, in laser. Nhƣng dƣới quan điểm của những ngƣời nghiên cứu đồ họa vi tính, ta sẽ xem xét tới khái niệm chất lƣợng của bản in. . Dot size: đƣờng kính của một điểm in bé nhất mà máy in có thể in đƣợc . Addressability: khả năng địa chỉ hoá các điểm in có thể có trên một đơn vị độ dài (dot per inch) . Số lƣợng màu có thể vẽ trên một điểm Dot size Point per inch InkJet 8-20/100 inch 200÷ 600 Laser 5/1000 inch 1500 Máy vẽ 6÷ 15/1000 inch 1000÷ 2000 1.6.3. Các thiết bị vào dữ liệu Bàn phím: Bàn phím xuất hiện trong hầu hết các máy tính, nó là thiết bị để nhập dữ liệu dạng văn bản và dữ liệu số. Đây là loại thiết bị quen thuộc nhất đối với ngƣời dùng tuy có nhƣợc điểm là tƣơng tác chậm. Chuột: Cùng với sự xuất hiện của các ứng dụng của các hệ đồ họa có tốc độ tƣơng tác cao, chuột là thiết bị ngày càng quen thuộc với ngƣời sử dụng. Ngƣời ta dùng chuột để chỉ và chọn các chức năng phù hợp với yêu cầu của mình. Với cách giao tiếp này giữa ngƣời dùng và máy tính ngày càng trở nên thân thiện và dễ dàng hơn. 19
Đồ họa máy tính CÂU HỎI CHƢƠNG 1 Chọn một phƣơng án đúng cho mỗi câu hỏi sau: 1. Để tạo ra các điểm ảnh (pixel) thì các phƣơng pháp nào không đúng: [a] Tô trát (rendering) [b] Rời rác hoá (số hoá) hình ảnh thực của đối tƣợng [c] Dựa vào các lý thuyết mô phỏng (Fract ) [d] Dùng phần mềm vẽ trực tiếp từng điểm ảnh một 2. Chọn phƣơng án sai cho kỹ thuật đồ hoạ điểm: [a] Dễ dàng thay đổi thuộc tính của đối tƣợng (màu sắc, độ sáng) [b] Quan sát đối tƣợng ở nhiều góc nhìn khác nhau bằng cách thay đổi góc nhìn [c] Xoá đi dễ dàng từng pixel của đối tƣợng [d] Đối tƣợng đƣợc hiển thị thông qua từng mẫu rời rạc 3. Chọn phƣơng án không phải là ứng dụng của kỹ thuật đồ hoạ: [a] Tính khối lƣợng vật liệu (sắt, thép ) cho một toà nhà [b] Điều khiển các quá trình sản xuất [c] Tính thể tích hoặc diện tích các hình trong thiết kế công trình xây dựng [d] Giải trí nghệ thuật và mô phỏng 4. Các chuẩn sau thì chuẩn nào không thuộc chuẩn giao diện của hệ đồ hoạ: [a] GKS [b] OPENGL [c] IEEE802.11 [d]—CGI 5. Tỷ số phƣơng (aspect ratio) của màn hình là 1,4 vậy một hình tròn khi hiển thị trên màn hình đó sẽ cho: [a] Hình ellipse nằm ngang (bán kính theo trục x dài hơn bán kính theo trục y) [b] Hình tròn [c] Hình thoi [d] Hình ellipse đứng (bán kính theo trục x ngắn hơn bán kính theo trục y) 6. Giả sử màn hình của bạn đang sử dụng có độ phân giải (Resolution) là 1024x768 thì số điểm ảnh của màn hình là: [a] 784641 [b] 785408 [c] 786431 [d]—786432 20
Đồ họa máy tính 7. Giả sử màn hình của bạn đang sử dụng có độ phân giải (Resolution) là 640x480 thì số điểm ảnh của màn hình là: [a] 306081 [b] 307200 [c] 306082 [d]—307199 8. Nói rằng : kỹ thuật đồ hoạ điểm giúp cho chúng ta quan sát hình ảnh ở nhiều góc độ khác nhau bằng cách thay đổi góc nhìn là đúng hay sai? [a] Đúng [b]—Sai 9. Phát biểu: kỹ thuật đồ hoạ vector = mô hình hình học + tô trát, là đúng hay sai? [a] Đúng [b]—Sai 10. Khi biểu diễn tƣờng minh đoạn thẳng có dạng y=kx+m, trong đó k là hệ số góc của đoạn. Phƣơng trình không thể nhận giá trị k= ∞ [a] Đúng [b]—Sai 11. Trong hệ tọa độ thiết bị sử dụng để hiển thị các hình ảnh : [a] Hệ tọa độ nguyên [b] Hệ tọa độ thế giới thực [c] Hệ tọa độ thiết bị [d] Hệ tọa độ chuẩn 12. Hệ tọa độ thực thƣờng đƣợc dùng để mô tả các đối tƣợng trong thế giới thực là hệ tọa độ : [a] Descartes [b] Device coordinates [c] Normalized device coordinates [d]—XYZ 13. Các điểm trong hệ tọa độ thực đƣợc định nghĩa là : [a] Xác định [b] Liên tục [c] Thống nhất [d] Rời rạc 21
Đồ họa máy tính Chƣơng 2 CÁC GIẢI THUẬT XÂY DỰNG CÁC THỰC THỂ CƠ SỞ 2.1 Giới thiệ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í dụ một ảnh thể hiện bài trí của một căn phòng sẽ đƣợc cấu trúc từ các đối tƣợng nhƣ cây cảnh, tủ kính, bàn ghế, tƣờng, ánh sáng đè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: hoặc là bằng dãy các pixel tƣơng ứng hoặc là bằng tập các đối tƣợng hình học cơ sở nhƣ đoạn thẳng hay 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. Hình 2.1 Ảnh cánh tay robot được cấu tạotừ các đối tượng đồ họa cơ sở 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 phải 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 22
Đồ họa máy tính 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 splines, 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 này đó là:Đố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 Hình 2.2 Quá trình chuyển đổi một đoạn thẳng về dãy các pixel nhau. tương ứng 2.2. Các đối tƣợng đồ họa cơ sở 2.2.1 Điểm Điểm là thành phần cơ sở đƣợc định nghĩa trong một hệ tọa độ. Đối với hệ tọa độ hai chiều mỗi điểm đƣợc xác định bởi cặp tọa độ (x, y). Ngoài thông tin về tọa độ, điểm còn có thuộc tính là màu sắc. 23
Đồ họa máy tính 2.2.2. Đƣờng thẳng, đƣờng gấp khúc a. Đường 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 sau: x - x x - x 1 = 2 1 y - y1 y2- y1 Hay ở dạng tƣơng đƣơng (x -x1)(y2- y1)=(x2 - x1)(y - y1) Khai triển có dạng y = mx+k y2-y1 Dy với m= = , k = y1 – mx1. x2-x1 Dx Đây đƣợc gọi là phƣơng trình đoạn chắn của đƣờng thẳng. Nếu khai triển dƣới dạng (y2 –y1)x –(x2 – x1)y –x1y2 + x2y1 = 0 và đặt A = y2 – y1, B = -(x2 – x1), C = x2y1 – x1y2 thì phƣơng trình đƣờng thẳng có dạng Ax + By + C = 0. Dạng này gọi là phƣơng trình tổng quát của đƣờng thẳng. Phƣơng trình tham số của đƣờng thẳng có dạng các tọa độ x, y đƣợc mô tả qua một thành phần thứ ba là t. Dạng này rất thuận tiện khi khảo sát các đoạn thẳng. x= 1-t x1+tx2 y= 1-t y1+ty2 Nếu t [0,1], các điểm (x,y) thuộc về đoạn thẳng giới hạn bởi 2 điểm (x1, y1), (x2, y2), nếu t [- ,+ ] ta có toàn bộ đƣờng thẳng. Một đoạn thẳng là một đƣờng thẳng bị giới hạn bởi hai điểm đầu, cuối Hình 2.3 Dạng tham số của phương trình đường thẳng b. Đường gấp khúc Đƣờng gấp khúc là tập các đoạn thẳng nối với nhau một cách tuần tự. Các đoạn thẳng này không nhất thiết phải tạo thành một hình khép kín và các đoạn có thể cắt lẫn 24
Đồ họa máy tính nhau. Điểm giao của hai đoạn thẳng đƣợc gọi là đỉnh. Các đƣờng gấp khúc đƣợc xác định qua danh sách các đỉnh, mỗi đỉnh đƣợc cho bởi các cặp tọa độ (xi, yi). Một đa giác là một đƣờng gấp khúc có điểm đầu và điểm cuối trùng nhau. Hình 2.4: Đường gấp khúc (a) và đa giác (b) Các thuộc tính của đoạn thẳng bao gồm: - Màu sắc - Độ rộng của nét vẽ. - Kiểu nét vẽ của đoạn thẳng có thể là một trong các dạng nhƣ hình 2.5. 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 có thể dùng và cho phép ngƣời dùng định nghĩa kiểu đoạn thẳng của mình thông qua một mẫu (pattern) gồm các số 0, 1. Đối với đƣờng gấp khúc, các đoạn thẳng trong cùng một đƣờng gấp khúc thì có cùng một thuộc tính. Hình 2.5 Kiểu nét vẽ của đoạn thẳng 2.2.3 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 ví dụ nhƣ đa giác.Các thuộc tính của vùng tô bao gồm: Thuộc tính của đƣờng biên: chính là các thuộc tính nhƣ thuộc tính của đoạn thẳng. Thuộc tính của vùng bên trong: bao gồm màu tô và mẫu tô. 25
Đồ họa máy tính Hình 2.6 Vùng tô với các mẫu đường biên và mẫu tô 2.2.4 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ị; font chữ đị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 (đối với 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 pixel. Khoảng cách giữa các kí tự. Sự canh chỉnh (gióng lề): canh trái (left text), canh phải (right text), canh giữa (center text), canh đều nhau (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ự. Hình 2.7 Dạng Bitmap và vector của font ký tự B 26
Đồ họa máy tính 2.3. Giải thuật sinh đƣờng thẳng 2.3.1 Nguyên lý chung Trên mặt phẳng bất kỳ, một điểm đƣợc xác định bởi cặp hai giá trị tọa độ x và y mô tả khoảng cách từ điểm đó đến các trục. Điểm nằm trên đƣờng thẳng khi giá trị tọa độ điểm thỏa mãn phƣơng trình biểu diễn đƣờng thẳng đó. Xét bài toán: Vẽ đoạn thẳng đi qua 2 điểm A(x1,y1) và B(x2,y2) Phƣơng trình đƣờng thẳng đi qua hai điểm A(x1,y1) và B(x2,y2) có thể biểu diễn dƣới dạng y = mx + k với m = (y2 – y1)/(x2 – x1), k = y1 – mx1. Từ phƣơng trình này có thể xây dựng quá trình vẽ đƣờng thẳng bằng cách cho một thành phần toạ độ x hay y biến đổi theo từng đơn vị và tính giá trị nguyên của thành phần tọa độ còn lại. Do các đƣờng thẳng đƣợc mô tả trong hệ tọa độ thực nhƣng khi hiển thị trong máy tính, hệ tọa độ là lƣới nguyên nên bản chất của quá trình vẽ đƣờng thẳng chính là sự nguyên hóa các tọa độ các điểm thuộc đƣờng thẳng và vẽ các điểm ảnh tƣơng ứng. Nguyên lý chung là cho một thành phần tọa độ biến đổi theo từng đơn vị và tính tọa độ nguyên còn lại sao cho gần với tọa độ thực nhất. Việc quyết định chọn x hay y biến đổi phụ thuộc vào độ rộng của đƣờng thẳng. Xét trƣờng hợp hệ số góc 0< m< 1và Dx 0, khi đó độ biến thiên trên trục x sẽ lớn hơn độ biến thiên theo trục y.Cho x biến thiên mỗi lần một điểm ảnh (Δx=1)từ x1 tiến tới x2, độ biến thiên của y tính theo x nhiều nhất là một điểm ảnh. b) a) Hình 2.8 Nguyên hóa của các tọa độ khi sinh đường thẳng độ biến thiên của x lớn hơn độ biến thiên của y (a) và độ biến thiên của y lớn hơn độ biến thiên của x (b) 27
Đồ họa máy tính Để đơn giản hóa quá trình xây dựng giải thuật, ta xét các đƣờng thẳng có hệ số góc dƣơng và nhỏ hơn 1 để đảm bảo bộ biến thiên theo trục x lớn hơn độ biến thiên theo trục y. Khi đó cho x biến thiên mỗi lần một pixel và độ biến thiên của y đƣợc tính theo x. Giả sử 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 trƣờng hợp (điểm màu trắng) nhƣ hình vẽ sau: (xi+1, yi+1) 2 y (x +1, y ) i 1 i i x i Hình 2.9 Các điểm xi 1, yi 1 chọn ở bước (i+1) cho trường hợp đoạn thẳng có hệ số góc 0<m<1 xi 1 xi 1 Nhƣ vậy : yi yi 1 yi 1 Vấn đề còn lại là cách chọn một trong hai điểm trên nhƣ thế nào để có thể tối ƣu về mặt tốc độ. 2.3.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 của đoạn thẳng y = mx +b. Nghĩa là, ta sẽ tính tọa độ của điểm xi 1, y thuộc về đoạn thẳng thực. Tiếp đó, yi+1sẽ là giá trị sau khi làm tròn giá trị tung độ y. y m xi 1 b Nhƣ vậy: yi 1 Round y Nếu tính trực tiếp giá trị thực y ở mỗi bƣớc từ phƣơng trìnhy = mx + b thì phải cần một phép toán nhân và một phép toán cộng số thực. Để cải thiện tốc độ, ngƣời ta tính giá trị thực của y ở mỗi bƣớc theo cách sau để khử phép tính nhân trên số thực: Nhận xét yi 1 mx i 1 b m xi 1 b= mxi + b + m mà yi = mxi + b 28
Đồ họa máy tính Do đó: yi+1 = yi + m Hình 2.10 Minh họa thuật toán DDA Thuật toán này do cách làm tròn tọa độ thực ở những bƣớc tính toán cuối cùng nên độ chính xác của giải thuật cao, đƣờng thẳng vẽ đƣợc thể hiện gần với đƣờng thẳng thực tế. Tuy nhiên cũng vì vậy mà tốc độ tính toán chậm do phải làm việc thƣờng xuyên trên số thực và các phép toán phức tạp nên thuật toán ít đƣợc sử dụng. Lưu đồ thuật toán và chương trình cài đặt thuật toán DDA vẽ đường thẳng procedure LineDDA (x1, y1, x2, y2, color :integer) begin var x,i:integer; y, m: real; x := x1; y := y1; m := (y2-y1)/(x2-x1); putpixel(x, Round(y), Color); for i:=x1 to x2 -1 do begin x := x +1; y :=y + m; putpixel(x, Round(y), Color); end; end; 29
Đồ họa máy tính Begin m=Dy/Dx; x=x1; y=y1; putpixel(x, Round(y), c); x<x2 No Yes x=x+1; y=y+m; putpixel(x, Round(y),c); End Ví dụ 2.1. Áp dụng giải thuật DDA, tính các điểm đƣợc vẽ trên đoạn thẳng giới hạn bởi 2 điểm A(12, 20) và B(22, 27) Ta có Dx = 22-12=10; Dy = 27-20=7; m = 0.7 Bƣớc xi yi y 0 12 20 20 1 13 21 20.7 2 14 21 21.4 3 15 22 22.1 4 16 23 22.8 5 17 24 23.5 30
Đồ họa máy tính 6 18 24 24.2 7 19 25 24.9 8 20 26 25.6 9 21 26 26.3 10 22 27 27 Nhận xét Việc sử dụng công thức yi+1 = yi + m để tính giá trị y tại mỗi bƣớc đã giúp cho thuật toán DDA nhanh hơn hẳn 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, việc cộng dồn giá trị thực m vào y có thể sẽ tích lũy sai số làm cho hàm làm tròn có kết quả sai dẫn tới việc xác định vị trí của điểm vẽ ra bị chệch hƣớng so với đƣờng thẳng thực. Điều này chỉ xảy ra khi vẽ đoạn thẳng khá dài. Tuy đã khử đƣợc phép nhân số thực nhƣng thuật toán DDA vẫn còn bị hạn chế về mặt tốc độ do vẫn còn phép toán cộng số thực và làm tròn. Có thể khắc phục thao Dy tác cộng số thực m và làm tròn trong thuật toán bằng cách nhận xét m với Dy, Dx Dx là các số nguyên. 2.3.3 Giảithuật Bresenham Thuật toán Bresenham đƣa ra cách chọn yi+1 là yi hay yi +1theo 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. Vấn đề mấu chốt ở đây là làm thế nào để hạn chế tối đa các phép toán trên số thực trong thuật toán. Ý tƣởng của thuật toán Bresenham đƣợc trình bày nhƣ sau : Hình 2.11 Minh họa thuật toán Bresenham 31
Đồ họa máy tính Gọi x i 1,y là điểm thuộc đoạn thẳng. Ta có: y m xi 1 b. d1 y yi Đặt d2 yi 1 y Xét tất cả các vị trí tƣơng đối của y so với y i và yi 1, việc chọn điểm x i 1 ,yi 1 là S hay P phụ thuộc vào việc so sánh d1 và d2 hay dấu củad1 d 2 Nếu d1 d2 0, chọn điểm S, tức là yi 1 yi . Ngƣợc lại, nếud1 d2 0 , chọn điểm P, tức là yi 1 yi 1. Xét pi Dx d1 d2 Dx 2y 2yi 1 pi Dx2 m xi 1 b 2yi 1 Dy Thay m vào phƣơng trình trên ta đƣợc: p 2Dyx 2Dxy c , với Dx i i i c 2Dy 2b 1 Dx . Nhận xét: do Dx 0 nên dấu của biểu thức d1 d 2 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 đã xác định đƣợc dấu của pi thì xem nhƣ xác định đƣợc điểm cần chọn ở bƣớc (i+1). Tính đƣợc pi tại mỗi bƣớc: Ta có: pi 1 pi 2Dyxi 1 2Dxy i 1 c 2Dyxi 2Dxy i c pi 1 pi 2Dy xi 1 xi 2Dx yi 1 yi pi 1 pi 2Dy 2Dx yi 1 yi , do xi 1 xi 1 Từ đây có thể suy ra cách tính pi 1 từ pi nhƣ sau: - Nếu pi 0 thì pi 1 pi 2Dy do chọn yi 1 yi . - Ngƣợc lại, nếu pi 0 , thì pi 1 pi 2Dy 2Dx , do chọn yi 1 yi 1. Giá trị p0 đƣợc tính từ điểm vẽ đầu tiên x0 ,y0 theo công thức: 32
Đồ họa máy tính p0 2Dyx0 2Dxy 0 c 2Dyx0 2Dxy 0 2Dy 2b 1 Dx Do x0 ,y0 là điểm nguyên thuộc về đoạn thẳng nên ta có: Dy y mx b x b . 0 0 Dx 0 Thế vào phƣơng trình trên ta tính đƣợc: p0 2Dy Dx . Lƣu đồ thuật toán và chƣơng trình cài đặt thuật toán Bresenham vẽ đƣờng thẳng 33
Đồ họa máy tính procedure LineBres (x1, y1, x2, y2, color:integer) begin var Dx, Dy, p, Const1, Const2, i : integer; x, y:integer; Dx := x2 - x1; Dy := y2 - y1; p := 2*Dy - Dx; Const1 := 2*Dy; Const2 := 2*(Dy-Dx); x := x1; y := y1; putpixel(x, y, Color); for i:=x1 to x2 do begin if (p<0) then p := p + Const1 else begin p := p + Const2; y := y + 1; end; x:= x +1; putpixel(x, y, Color); end; end; Ví dụ 2.2.Tính các điểm đƣợc vẽ trên đoạn thẳng giới hạn bởi 2 điểm A(12, 20), B(22, 27). Ta có: Dx = 22 -12 =10, Dy = 27 – 20 = 7 Const1 = 2Dy = 14, Const2 = 2(Dy - Dx) = -6 P0 = 2Dy – Dx = 14 – 10 = 4 Ta có bảng xác định các điểm vẽ nguyên của đoạn thẳng AB nhƣ sau: Bƣớc xi yi p 0 12 20 4 1 13 21 -2 34
Đồ họa máy tính 2 14 21 12 3 15 22 6 4 16 23 0 5 17 24 -6 6 18 24 8 7 19 25 2 8 20 26 -4 9 21 26 10 10 22 27 4 Nhận xét Thuật toán Bresenham chỉ làm việc trên số nguyên và các thao tác trên số nguyên chỉ là phép cộng và phép dịch bit (phép nhân 2) điều này là một cải tiến làm tăng tốc độ đáng kể so với thuật toán DDA. Ý tƣởng chính của thuật toán nằm ở chỗ xét dấu pi để quyết định điểm kế tiếp, và sử dụng công thức truy hồi pi+1 - pi để tính pi bằng các phép toán đơn giản trên số nguyên. Thuật toán này cho kết quả tƣơng tự nhƣ thuật toán DDA. 2.3.4 Thuật toán MidPoint Thuật toán MidPoint đƣa ra cách chọn yi+1 là yi hay yi +1 bằng cách so sánh điểm thực Q(xi + 1, y) với điểm MidPoint là trung điểm của S và P (hình 2.11). Ta có: Nếu điểm Q nằm dƣới điểm MidPoint, ta chọn S. Ngƣợc lại nếu điểm Q nằm trên điểm MidPoint ta chọn P. Hình 2.12 Minh họa thuật toán MidPoint 35
Đồ họa máy tính Ta có dạng tổng quát của phƣơng trình đƣờng thẳng: Ax By C 0 với A y2 y1 , B x 2 x1 ,C x 2 y1 x1y 2 Đặt F x, y Ax By C , ta có nhận xét : 0 Nếu x, y nằm phía dƣới đƣờng thẳng Lúc này việc chọn các điểm S, P ở trên đƣợc đƣa về việc xét dấu của 1 pi 2F MidPoint 2F x i 1, y i . 2 Nếu pi 0, điểm MidPoint nằm phía trên đoạn thẳng. Lúc này điểm thực Q nằm dƣới điểm MidPoint nên ta chọn S, tức là yi 1 yi . Ngƣợc lại, nếu pi 0, điểm MidPoint nằm phía dƣới đoạn thẳng. Lúc này điểm thực Q nằm trên điểm MidPoint nên ta chọn P, tức là yi 1 yi 1. Mặt khác: 1 1 pi 1 pi 2F x i 1 1, y i 1 2F x i 1, yi 2 2 1 1 p i 1 p i 2 A x i 1 1 B y i 1 C 2 A x i 1 B y i C 2 2 pi 1 pi 2A 2B yi 1 yi 2Dy 2Dx yi 1 yi Vậy: pi 1 pi 2Dy , nếu pi 0 do ta chọn yi 1 yi . pi 1 pi 2Dy 2Dx , nếu pi 0 do ta chọn yi 1 yi 1. Ta tính giá trị p0 ứng với điểm ban đầu x 0 , y 0 : vì x 0 , y 0 là điểm thuộc đoạn thẳng nên Ax0 By 0 C 0 1 1 p0 2F x 0 1, y 0 2 A x 0 1 B y 0 C 2 2 p0 2 Ax0 By0 C 2A B 2A B 2Dy Dx 36
Đồ họa máy tính Nhận xét: Thuật toán MidPoint cho kết quả tƣơng tự nhƣ thuật toán Bresenham. 2.4. Giải thuật sinh đƣờng tròn 2.4.1 Nguyên lý chung Phƣơng trình đƣờng tròn có tâm là gốc tọa độ, bán kính R là: x 2 y2 R 2 . Từ phƣơng trình này ta có thể đƣa về dạng y R 2 x 2 . Để vẽ các đƣờng tròn có tâm x C , yC bất kì, đơn giản chỉ cần tịnh tiến các điểm sau khi vẽ xong đƣờng tròn có tâm là gốc tọa độ theo vector tịnh tiến x C , yC . Do tính đối xứng nên để vẽ toàn bộ đƣờng tròn, ta chỉ cần vẽ cung ¼ đƣờng tròn sau đó lấy đối xứng để xác định các điểm còn lại. Một trong những cách đơn giản nhất là cho x chạy từ 0 đến R, sau đó tính y từ công thức trên (chỉ lấy giá trị dƣơng) rồi làm tròn để xác định giá trị nguyên tƣơng ứng. Cách làm này không hiệu quả do gặp phải các phép toán nhân và lấy căn làm hạn 37
Đồ họa máy tính chế tốc độ, ngoài ra đƣờng tròn vẽ ra theo cách này có thể không liền nét (trừ trƣờng hợp R lớn) khi x gần R (do chỉ có một giá trị y duy nhất cho một giá trị x). Chúng ta có thể khắc phục điều này bằng cách điều chỉnh đối tƣợng thay đổi là x (rồi tính y theo x) hay y (rồi tính x theo y) tùy vào giá trị tuyệt đối của hệ số góc đƣờng tròn là lớn hơn hay nhỏ hơn 1, nhƣng cách làm này đòi hỏi thêm các phép tính toán và kiểm tra nên làm cho thuật toán phức tạp thêm (hình 2.12) Một cách tiếp cận khác là vẽ các điểm Rcos θ ,Rsin θ , với θ chạy từ 00 đến 900. Cách này sẽ khắc phục hạn chế đƣờng không liền nét của thuật toán trên, tuy nhiên điểm hạn chế chính của thuật toán này đó là chọn bƣớc nhảy cho θ nhƣ thế nào cho phù hợp khi bán kính thay đổi. (0,17) (17,0) Hình 2.13Đường tròn vẽ ra không liền nét 2.4.2 Thuật toán MidPoint Do tính đối xứng của đƣờng tròn (C) nên ta chỉ cần vẽ cung (C1/8) là cung 1/8 đƣờng tròn, sau đó lấy đối xứng. Cung (C1/8) đƣợc mô tả nhƣ sau (cung của phần tô xám trong hình vẽ): (-x,y) (x,y) 2 0 x R (-y,x) (y,x) 2 2 R R y R 2 (-y,-x) 2 (y,-x) (-x,-y) (x,-y) Hình 2.14 Các vị trí đối xứng trên đường tròn (C) tương ứng với (x,y) Nhƣ vậy nếu có (x, y) (C1/8) thì các điểm (y, x), (y,-x), (x,-y), (-x,-y), (-y,-x), (-y,x), (-x,y) sẽ thuộc (C). 38
Đồ họa máy tính Chọn điểm bắt đầu để vẽ là điểm (0, R). Dựa vào hình vẽ, nếu x i , y i là điểm nguyên đã tìm đƣợc ở bƣớc thứ i, thì điểm xi 1,yi 1 ở bƣớc thứ (i+1) là sự lựa chọn giữa S và P. Hình 2.15 Thuật toán MidPoint vẽ đường tròn xi 1 xi 1 Nhƣ vậy: yi yi 1 yi 1 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 S và P sẽ đƣợc thực hiện thông qua việc xét dấu của một hàm nào đó tại điểm MidPoint là điểm nằm giữa chúng. Đặt F x, y x 2 y 2 R 2 , ta có : 0 Nếu x, y nằm ngoài đƣờng tròn 1 Xét pi F MidPoint F x i 1, y i . Ta có: 2 Nếu pi 0, điểm MidPoint nằm trong đƣờng tròn. Lúc này điểm thực Q gần S hơn nên ta chọn S, tức là yi 1 yi . Ngƣợc lại, nếu pi 0 , điểm MidPoint nằm ngoài đƣờng tròn. Lúc này điểm thực Q gần P hơn nên ta chọn P, tức là yi 1 yi 1. Mặt khác: 39
Đồ họa máy tính 1 1 pi 1 pi F x i 1 1, y i 1 F x i 1, y i 2 2 2 2 2 1 2 2 1 2 p i 1 p i x i 1 1 y i 1 R x i 1 y i R 2 2 2 2 2 1 2 2 1 2 p i 1 p i x i 2 y i 1 R x i 1 y i R 2 2 2 2 pi 1 pi 2x i 3 y i 1 y i y i 1 y i Vậy: pi 1 pi 2x i 3, nếu pi 0 do ta chọn yi 1 yi . pi 1 pi 2x i 2yi 5, nếu pi 0 do ta chọn yi 1 yi 1. Ta tính giá trị p0ứng với điểm ban đầu x0 , y0 là (0, R) và trung điểm tiếp theo đƣợc suy ra là (1, R – 1/2). Theo công thức: 1 p0 F x 0 1, y0 2 1 F 1, R 2 = 1 + (R2 – R + 1/4) –R2 5 = R 4 Lƣu đồ thuật toán và chƣơng trình cài đặt thuật toán MidPoint vẽ đƣờng tròn 40
Đồ họa máy tính // Giải thuật vẽ 8 điểm đối xứng procedureput8Pixel(x, y, Color: integer) { putpixel(x, y, Color);putpixel(y, x, Color); putpixel(y,-x, Color);putpixel(x,-y, Color); putpixel(-x,-y, Color);putpixel(-y,-x, Color); putpixel(-y, x, Color); putpixel(-x, yF, Color); } alse //Giải thuật Midpoint T procedure CircleMidPoint (R, color:rue integer) 41
Đồ họa máy tính begin var x, y, p:integer; x := 0; y := R; put8Pixel(x, y, color); p:= 1 - R; // 5/4-R while (x < y) do begin if (p < 0) then p := 2*x + 3 else begin p :=p+ 2*(x -y) + 5; y := y -1; end; x++; put8Pixel(x, y, color); end; end; Ví dụ 2.3. Tính các điểm đƣợc vẽ trên đƣờng tròn có bán kính bằng 15 và tâm tại gốc tọa độ. Ta có: x = 0, y = 15, p = 1- R = -14 Bƣớc xi yi p 0 0 15 -14 1 1 15 -11 2 2 15 -6 3 3 15 1 4 4 14 -18 5 5 14 -7 6 6 14 6 7 7 13 -5 8 8 13 12 9 9 12 7 10 10 11 6 42
Đồ họa máy tính 11 11 10 9 2.4.3 Giải thuật Bresenham Giả sử (xi,yi) đã vẽ đƣợc. Cần chọn điểm kế tiếp là (xi +1,yi) hoặc (xi +1,yi -1) 2 2 2 Từ phƣơng trình: x + y = R ta tính đƣợc giá trị y thực ứng với xi +1 là: 2 2 2 y = R - (xi +1) (3.1) Hình 2.14 Thuật toán Bresenham sinh đường tròn 2 2 2 2 2 Đặt: d1 = yi - y = yi - R + (xi + 1) 2 2 2 2 2 d2 = y - (yi - 1) = R - (xi + 1) - (yi - 1) Suy ra: 2 2 2 2 pi = d1 - d2 = 2.(xi + 1) + yi + (yi - 1) - 2R (3.2) 2 2 2 2 pi+1 = 2.(xi+1 + 1) + y i+1 + (yi+1 - 1) - 2R (3.3) Từ (3.2) và (3.3) ta có: 2 2 pi+1 - pi = 4xi + 6 + 2.(y i+1 - yi ) - 2.(yi+1 - yi) 2 2 pi+1 = pi + 4xi + 6 + 2.(y i+1 - yi ) - 2.(yi+1 - yi) (3.4) * Nhận xét: Nếu pi< 0: ta chọn yi+1 = yi thay vào (3.4) pi+1 = pi + 4xi + 6 Nếu pi 0: chọn yi+1 = yi– 1 thay vào (3.4) pi+1 = pi + 4.(xi - yi) + 10 Ta chọn điểm đầu tiên cần vẽ (0, R), theo (3.2) ta có: p1 = 3 - 2R Lƣu đồ thuật toán và chƣơng trình cài đặt thuật toán Bresenham vẽ đƣờng tròn 43
Đồ họa máy tính procedure Circle(r, color: integer) begin var: x, y, p x :=0, y :=r; p :=3 - 2*r; while (x<=y) do begin put8pixel(x, y, color); if (p<0)then p:=p + 4*x + 6 else begin p:=p + 4*(x-y) + 10; y:=y-1; end; x:=x+1; end; 44
Đồ họa máy tính end; Ví dụ 2.4. Tính các điểm đƣợc vẽ trên đƣờng tròn có bán kính bằng 15 Ta có: x = 0, y = 15, p = 3 - 2R = -27 Bƣớc xi yi p 0 0 15 -27 1 1 15 -21 2 2 15 -11 3 3 15 3 4 4 14 -35 5 5 14 -13 6 6 14 13 7 7 13 -9 8 8 13 25 9 9 12 15 10 10 11 13 2.5. Giải thuật sinh Elippse 2.5.1. Giải thuật Midpoint Tƣơng tự thuật toán vẽ đƣờng tròn, sử dụng thuật toán Midpoint để vẽ, chỉ cần vẽ 1/4 Ellipse, sau đó lấy đối xứng qua các trục tọa độ sẽ vẽ đƣợc toàn bộ Ellipse. Sự khác biệt so với thuật toán vẽ đƣờng tròn là ta phải vẽ 2 phần (chia cung từ (0,b) đến (a,0) tại Q, có độ dốc -1) (Hình 2.16) Trên phần 1: x thay đổi thì y thay đổi theo Trên phần 2: y thay đổi thì x thay đổi theo ( 0, b) Q, độ dốc = -1 ( a, 0) Hình 2.16Mô tả giải thuật sinh đường Ellipse 45
Đồ họa máy tính Xét Ellipse có tâm O, các bán kính là a và b, phƣơng trình là: x2 y2 + =1 a2 b2 + Xét trên phần 1: Bắt đầu từ điểm (0, b), giả sử bƣớc thứ i điểm (xi,yi) đã vẽ, bƣớc thứ i + 1 ta chọn điểm A(xi+1, yi) hoặc điểm B(xi+1,yi-1). Ta có: 2 2 2 2 2 2 pi = f(xi+1,yi-1/2) = b (xi+1) + a (yi-1/2) -a b 2 2 2 2 2 2 pi+1 = f(xi+1+1,yi+1-1/2) = b (xi+1+1) + a (yi+1-1/2) -a b 2 2 2 2 2 2 pi+1 - pi = b ((xi+1+1) - (xi+1) )+ a ((yi+1-1/2) - (yi-1/2) ) ( do xi+1 = xi+1) 2 2 2 2 pi+1 = pi + b (2xi+ 3) + a ((yi+1-1/2) - (yi-1/2) ) 2 - Nếu pi< 0 chọn A với xi+1 = xi+1 và yi+1 = yi do đó: pi+1 = pi + b (2xi +3) - Nếu pi ≥ 0 chọn B với xi+1 = xi+1 và yi+1=yi -1 do đó: 2 2 2 2 pi+1 = pi + b (2xi +3) + a ((yi-1 -1/2) - (yi-1/2) ) 2 2 = pi + b (2xi +3) + a (-3yi +9/4 +yi -1/4) 2 2 = pi + b (2xi +3) + a (-2yi +2) 2 2 Hay pi+1 = pi + b (2xi +3) + a (-2yi +2) - Tính p1 tại (0,b) 2 2 2 2 2 p1 = f(x1+1, y1-1/2) = b + a (b-1/2) -a b 2 2 2 p1 = b - a b +a /4 + Xét trên phần 2: Ta lấy tọa độ của điểm vẽ sau cùng trong phần 1 của đƣờng cong để tính giá trị ban đầu cho phần 2. Giả sử điểm (xk,yk) vừa chuyển quét cuối cùng của phần 1 nhập vào bƣớc j cho phần 2 (xj,yj). Điểm vẽ kế tiếp có thể là: C(xj,yj-1) hoặc D(xj+1, yj-1) Ta có: 2 2 2 2 2 2 qj = f(xj+1/2,yj-1) = b (xj+1/2) + a (yj-1) -a b 46
Đồ họa máy tính 2 2 2 2 2 2 qj+1 = f(xj+1+1/2,yj+1-1) = b (xj+1+1/2) + a (yj+1-1) -a b 2 2 2 2 2 2 qj+1 - qj = b ((xj+1+1/2) - (xj+1/2) )+ a ((yj+1-1) - (yj-1) ) (do yi+1 = yi - 1) 2 2 2 2 qj+1 = qj + b ((xj+1+1/2) - (xj+1/2) )+ a (3 – 2yi) - Nếu qj< 0 chọn D với yj+1=yj-1 và xj+1=xj +1 2 2 2 2 qj+1 = qj + b ((xj+3/2) - (xj+1/2) ) +a (-2yj +3) 2 2 qj+1 = qj + b (3xj +9/4- xj -1/4) +a (-2yj +3) 2 2 Hay qj+1 = qj + b (2xj +2) +a (-2yj +3) - Nếu qj ≥ 0 chọn C với yj+1=yj -1 và xj+1= xj 2 Hay qj+1 = qj + a (3 - 2yj ) - Tính q1: 2 2 2 2 2 2 q1 = f(xk+1/2,yk -1) = b (xk+1/2) + a (yk-1) -a b Thủ tục sinh Ellipse: procedure Ellipse(xc, yc, a, b, color: integer) begin var x, y, fx, fy, a2, b2, p: integer; x := 0; y := b; a2 := a * a; b2 := b * b; fx := 0; fy := 2 * a2 * y; plot(xc, yc, x,y, color); p := ROUND(b2-(a2*b)+(0.25*a)); while (fx < fy) do begin x:= x +1; fx := 2*b2; if (p<0) then p := p +b2*(2*x +3) else begin y := y -1; p := p + b2*(2*x +3) + a2*(-2*y +2); 47
Đồ họa máy tính fy := fy - 2*a2; end; plot(xc, yc, x, y, color); end; p := ROUND(b2*(x+0.5)*(x+0.5) + a2*(y-1)*(y-1) - a2*b2); {b2(x+1/2)2+a2(y-1)2 - a2b2} while (y>0) do begin y := y -1; fy :=fy - 2*a2; if (p>=0) then p := p + a2*(3 - 2*y) else begin x := x +1; fx := fx + 2*b2; p := b2*(2*x+2) + a2*(-2*y +3); end; plot(xc, yc, x, y, color); end; end; 2.5.2. Giải thuật Bresenham Giả sử điểm (xi,yi) đã đƣợc vẽ. Điểm tiếp theo cần chọn sẽ là (xi+1,yi) hoặc (xi+1,yi-1) 2 2 b 2 2 Thay (xi +1) vào phƣơng trình Elippse ta đƣợc: y = - .(xi +1) + b a 2 Đặt: 2 2 2 2 2 d1= yi - y = yi + .(xi +1) -b 2 2 2 2 2 d2= y - (yi -1) = - .(xi +1) + b - (yi -1) 2 2 2 pi = d1 - d2 = 2.[ .(xi +1) - b ] + 2.(yi + yi) -1 2 2 2 pi+1 = 2[ .(xi+1 +1) - b ] + 2.(yi+1 + yi+1) -1 48
Đồ họa máy tính Suy ra: 2 b 2 2 2 2 pi+1 - pi = 2 [(xi+1 +1) - (xi +1) ] + 2.( yi+1 - yi + yi+1 - yi) ( ) a 2 *Nhận xét: pi< 0: Chọn yi+1 = yi ( ) pi+1 = pi + 2. .(2x + 3) pi 0: Chọn yi+1 = yi -1 ( ) pi+1 = pi + 2. .(2x + 3) - 4yi Với điểm đầu tiên (0,b), ta có: p1 = 2 - 2b + 1 Từ đó, ta có thủ tục vẽ Ellipse nhƣ sau: Procedure Ellipse(xc,yc,a,b:Integer;Color:Byte); Var p,a2,b2:real; x,y:integer; (* *) Procedure VeDiem; Begin PutPixel(xc+x,yc+y,Color); PutPixel(xc-x,yc+y,Color); PutPixel(xc-x,yc-y,Color); PutPixel(xc+x,yc-y,Color); End; (* *) Begin a2:=a*a; b2:=b*b; {Nhanh 1} x:=0; y:=b; p:=2*b2/a2 - 2*b + 1; While (b2/a2)*(x/y)<1 do Begin VeDiem; If p<0 then p:=p + 2*(b2/a2)*(2*x+3) else Begin p:=p - 4*y + 2*(b2/a2)*(2*x+3); y:=y-1; End; 49
Đồ họa máy tính x:=x+1; End; {Nhanh 2} y:=0; x:=a; p:=2*(a2/b2) - 2*a + 1; While (a2/b2)*(y/x)<=1 do Begin VeDiem; If p<0 then p:=p + 2*(a2/b2)*(2*y+3) else Begin p:=p - 4*x + 2*(a2/b2)*(2*y+3); x:=x-1; End; y:=y+1; End; End; 2.6. Giải thuật sinh đa giác Việc biểu diễn đa giác thông qua: - Tập các đoạn thẳng - Tập các điểm thuộc đa giác Các loại đa giác: Hình 2.17 Các loại đa giác Đa giác lồi: Là đa giác có đƣờng thẳng nối bất kỳ 2 điểm bên trong nào của đa giác đều nằm trọn trong đa giác. Đa giác không lồi là đa giác lõm. Các đƣờng thẳng bao đa giác - cạnh của đa giác. Các điểm giao của cạnh - đỉnh của đa giác. Thông tin cần thiết để xác định đa giác: - Số cạnh - Tọa độ các đỉnh của đa giác Giải thuật sinh đa giác: 50
Đồ họa máy tính procedure Polygon (arrayx, arrayy,n) begin //n là số đỉnh của đa giác //arrayx là mảng hoành độ các đỉnh của đa giác //arrayy là mảng tung độ các đỉnh của đa giác if (n<3) then exit; for i: = 1 to n – 1 do line(arrayx[i],arrayy[i], arrayx[i+1], arrayy[i+1]); line(arrayx[i+1],arrayy[i+1], arrayx[1], arrayy[1]); end; 2.7. Giải thuật sinh ký tự Trong màn hình text, truy xuất các ký tự trên màn hình đƣợc hỗ trợ bởi phần cứng. Các ký tự đƣợc lƣu trữ trong bộ nhớ ROM, dƣới dạng bitmap hay các ma trận ảnh. Phần cứng sẽ đƣa ký tự lên màn hình tại ví trí xác định, tính toán cuốn trang và xuống dòng. Trong đồ hoạ: + Vector: Định nghĩa các ký tự theo những đƣờng cong mềm bao ngoài của chúng, tốn kém về mặt tính toán. Biểu diễn ký tự vector có một số đặc điểm sau: Phức tạp (tính toán phƣơng trình) Lƣu trữ gọn nhẹ Các phép biến đổi dựa vào các công thức biến đổi Kích thƣớc phụ thuộc vào môi trƣờng ( không có kích thƣớc cố định) Hình 2.18 Ký tự vector 51
Đồ họa máy tính Xây dựng theo phƣơng pháp định nghĩa các ký tự bởi đƣờng cong mềm bao ngoài của chúng dễ dàng thay đổi kích thƣớc của ký tự cũng nhƣ nội suy ra các dạng của ký tự. Hoàn toàn độc lập với thiết bị. + Bitmap: Định nghĩa mỗi ký tự với 1 font chữ cho trƣớc là 1 ảnh bitmap hình chữ nhật nhỏ. Biểu diễn ký tự bitmap có một số đặc điểm sau: Đơn giản trong việc sinh ký tự ( copypixel) Lƣu trữ lớn Các phép biến đổi (I,B, scale) đòi hỏi lƣu trữ thêm kích thƣớc không đổi Hình 2.19 Ký tự bitmap Bitmap: Sử dụng hàm copypixel (copy điểm ảnh) đƣợc lƣu trữ trong bộ nhớ cố định - Fontcache, đƣa vào bộ nhớ đệm hiển thị. Mỗi 1 ký tự nhƣ 1 ma trận 2 chiều của các điểm ảnh - mặt nạ. procedure Hàm_sinh_ki_tu (mask) { xmax, ymax, xmin, ymin //các giới hạn của mặt nạ xo, yo//điểm gốc trên bộ đệm hiển thị for i:= y min to ymax – 1 do for j:= xmin to xmax -1 do if (mask(i,j) <> 0) then copypixel ((mask(i,j), pixel(xo+j, yo+i)); } Ký tự fontcache bitmap đơn giản của SRG lƣu trữ các ký tự theo chuỗi liên tiếp nhau trong bộ nhớ. Nhƣng độ rộng các ký tự khác nhau, truy nhập các fontcache thông qua bản ghi về cấu trúc cho từng kí tự. Cấu trúc font chữ Charlocation =record leftx: integer; 52
Đồ họa máy tính width: integer;; end; fontcache =record CacheId: integer; Height: integer; // Độ rộng chữ CharSpace: integer; // Khoảng cách giữa các ký tự Table: array [0 127] of Charlocation; end; Bài tập áp dụng: Bài toán: Vẽ đồ thị của hàm số y = f(x) trên đoạn [Min,Max]. Ý tưởng: Cho x chạy từ đầu đến cuối để lấy các tọa độ (x,f(x)) sau đó làm tròn thành số nguyên rồi nối các điểm đó lại với nhau. Giải thuật: Bƣớc 1: Xác định đoạn cần vẽ [Min,Max]. Bƣớc 2: - Đặt gốc tọa độ lên màn hình (x0,y0). - Chia tỷ lệ vẽ trên màn hình theo hệ số k. - Chọn bƣớc tăng dx của mỗi điểm trên đoạn cần vẽ. Bƣớc 3: Chọn điểm đầu cần vẽ: x = Min, tính f(x) Đổi qua tọa độ màn hình và làm tròn: x1:=x0 + Round(x.k); y1:=y0 - Round(y.k); Di chuyển đến (x1,y1): MOVETO(x1,y1); Bƣớc 4: Tăng x lên với số gia dx: x:=x + dx; Đổi qua tọa độ màn hình và làm tròn: x2:=x0 + Round(x.k); y2:=y0 - Round(y.k); Vẽ đến (x2,y2): LINETO(x2,y2); Bƣớc 5: Lặp lại bƣớc 4 cho đến khi x > Max thì dừng. Ví dụ: Vẽ đồ thị hàm số f(x) = Sin(x) Uses crt,Graph; 53
Đồ họa máy tính Var dau,cuoi:real; Gd,Gm:Integer; Function F(x:real):real; Begin F:=Sin(x); End; Procedure VeHinhSin(ChukyDau,ChuKyCuoi:real); var x1,y1,x2,y2:integer; a,x,k:real; x0,y0:word; Begin x0:=GetMaxX div 2; y0:=GetMaxY div 2; K:=GetMaxX/30; a:=Pi/180; x:=ChuKyDau; x1:=x0 + Round(x*k); y1:=y0 - Round(F(x)*k); Moveto(x1,y1); While x<ChuKyCuoi do Begin x:=x+a; x2:=x0 + Round(x*k); y2:=y0 - Round(F(x)*k); LineTo(x2,y2); End; End; BEGIN Gd:=0; InitGraph(Gd,Gm,’C:\BP\BGI’); Dau:=-4*Pi; cuoi:=4*Pi; VeHinhSin(Dau,cuoi); repeat until KeyPressed; CloseGraph; END. 54
Đồ họa máy tính CÂU HỎI VÀ BÀI TẬP CHƢƠNG 2 Chọn một phƣơng án đúng cho mỗi câu hỏi sau: 1. Xây dựng giải thuật tổng quát để vẽ đoạn thẳng ta có xét hệ số k (hệ số góc của đoạn thẳng) có tất cả các trƣờng hợp của k: [a] 2 [b] 4 [c] 6 [d] 8 2. Để biểu diễn đoạn thẳng thông qua phƣơng trình tham số nhƣ sau: [a] f(x,y)=0 hay ax + by +c =0 [b] x(v)=x1 +v(x2 -x1 ) và y(v) = y1 +v(y2 -y1 ) có v Є [0,1] [c] P(u) = P1 + u(P2 -P1 ) có u Є [0,1] [d] y=f(x) hay y=kx+b 3. Trong giải thuật Bresenham (vẽ đoạn thẳng) dùng biểu diễn đoạn thẳng là: [a] Phƣơng trình không tƣờng minh [b] Phƣơng trình tƣờng minh [c] Phƣơng trình các điểm gần với đoạn thẳng [d] Phƣơng trình tham số 4. Trong giải thuật Midpoint (vẽ đoạn thẳng) dùng biểu diễn đoạn thẳng là: [a] Phƣơng trình không tƣờng minh [b] Phƣơng trình tƣờng minh [c] Phƣơng trình điểm giữa [d] Phƣơng trình tham số 5. Giải thuật sau là giải thuật nào đã học? procedure Function(xt,yt,r,c:integer){ var x, y, d:integer; x := 0; y := r; d := 3 - 2 * r; 55
Đồ họa máy tính while (x <= y) do begin putpixel(xt + x, yt + y, c); putpixel(xt - x, yt + y, c); putpixel(xt + x, yt - y, c); putpixel(xt - x, yt - y, c); putpixel(xt + y, yt + x, c); putpixel(xt - y, yt + x, c); putpixel(xt + y, yt - x, c); putpixel(xt - y, yt - x, c); if (d < 0) then d := d+ 4 * x + 6; else begin d := d+4 * (x-y) + 10; y := y -1; end; x:= x +1; end; end; [a] Giải thuật Bresenham xây dựng đƣờng tròn [b] Giải thuật Midpoint xây dựng đƣờng tròn [c] Giải thuật Bresenham xây dựng đƣờng Ellipse [d] Giải thuật Midpoint xây dựng đƣờng Ellipse 6. Giải thuật sau là giải thuật nào đã học? procedure Function(xt, yt, r, c:integer){ var x, y, d:integer; x := 0; y := r; d := 1 - r; while (x <= y) do begin putpixel(xt + x, yt + y, c); putpixel(xt - x, yt + y, c); putpixel(xt + x, yt - y, c); putpixel(xt - x, yt - y, c); putpixel(xt + y, yt + x, c); putpixel(xt - y, yt + x, c); putpixel(xt + y, yt - x, c); putpixel(xt - y, yt - x, c); if (d < 0) then d :=d+ 2 * x + 3; 56
Đồ họa máy tính else begin d :=d+ 2* (x-y) + 5; y:=y-1; end; x:=x+1; end; end; [a] Giải thuật Bresenham xây dựng đƣờng tròn [b] Giải thuật Midpoint xây dựng đƣờng Ellipse [c] Giải thuật Midpoint xây dựng đƣờng tròn [d] Giải thuật Bresenham xây dựng đƣờng Ellipse 7. Điểm đầu nút của đoạn thẳng (-2,6) và (6,18), tính giá trị của k: [a] k= 3 [b] k= -6 [c] k= 1.5 [d] k= -3 8. Đoạn mã sau là thuộc giải thuật Bresenham vẽ đoạn thẳng: dx:=x2-x1; dy:=y2-y1; for x:=x1 to x2 do begin putpixel(x,y,c); if(p<0) then p :=p+ 2*dy; else begin p :=p+ 2*dy - 2*dx; y:=y+1; end; end; [a] Đúng [b]—Sai 9. Điểm đầu nút của đoạn thẳng (-2,-6) và (3,-2), tính giá trị của k : [a] k= -0.8 [b] k= 3 [c] k= 0.8 [d] k= 1.5 10. Giải thuật sau là giải thuật nào? procedure ThuTuc(X[],Y[]) begin 57
Đồ họa máy tính for i:=0 to 6 do line(X[i],Y[i],X[i+1],Y[i+1]); line(X[i+1],Y[i+1],X[0],Y[0]); end; [a] Giải thuật vẽ đƣờng bao đa giác với số đỉnh là 8 [b] Giải thuật tô đa giác với số đỉnh là 7 [c] Giải thuật vẽ đƣờng bao đa giác với số đỉnh là 7 [d] Giải thuật vẽ đƣờng bao đa giác với số đỉnh là 6 11. Giải thuật sau là giải thuật nào? procedure ThuTuc( X[], Y[]) begin for i:=0 to 5 do line(X[i],Y[i],X[i+1],Y[i+1]); line(X[i+1],Y[i+1],X[0], Y[0]); end; [a] Giải thuật vẽ đƣờng bao đa giác với số đỉnh là 7 [b] Giải thuật vẽ đƣờng bao đa giác với số đỉnh là 5 [c] Giải thuật tô đa giác với số đỉnh là 6 [d] Giải thuật vẽ đƣờng bao đa giác với số đỉnh là 6 12. Phƣơng trình không tƣờng minh cho đƣờng tròn là: (r là bán kính của đƣờng tròn) [a] f(x,y)=x2 +y2 -r2 =0 [b] f(x +1,y -1/2)=0 [c] (x-1)2 + (y-1)2 = (r-1)2 [d] f(x,y)=b2x2 + a2y2 - a2b2 =0 13. Phƣơng trình không tƣờng minh cho đƣờng Ellipse là: (ra là bán kính theo trục ox, rb là bán kính theo trục oy và (xc,yc) là tọa độ tâm): [a] f(x,y) = rb2(xc+x)2 + ra2(yc+y)2 - ra2rb2 = 0 [b] f(x,y)=(xc+x)2/ra2 + (yc+y)2/rb2 - ra2rb2 =0 [c] f(x i +1,y i -1/2) = 0 [d] ra2(xc+x)2 + rb2(yc+y)2 - ra2rb22=0 14. Theo giải thuật Midpoint vẽ đoạn thẳng thì d i = f(x i +1,y i +1/2) - trung điểm, với giá trị nào của d để trung điểm nằm dƣới đoạn thẳng: [a] di = 0 [b] di = di+1 [c] di > 0 [d] di < 0 15. Đoạn thẳng có 2 điểm cuối là (1,1) và (8,5). Dùng thuật toán Bresenham vẽ đoạn thẳng tính các giá trị tại x=3. 58
Đồ họa máy tính [a] p=5 và y=3 [b] p=2 và y=4 [c] p=-3 và y= 2 [d] p=-3 và y= 3 16. Đoạn thẳng có 2 điểm cuối là (1,1) và (8,5). Dùng thuật toán Midpoint vẽ đoạn thẳng tính các giá trị tại x=3. [a] d=4 và y=3 [b] d=-3 va y=3 [c] d=-2 và y=2 [d] d=2 và y=2 Bài tập 1. Tính các điểm đƣợc vẽ trên các đoạn thẳng giới hạn bởi các cặp điểm sau: a. A(10, 20), B(18, 27) theo thuật toán DDA b. C(16,19), D(24, 25) theo thuật toán Bresenham C. E(15, 17), F(23, 22) theo thuật toán Midpoint 2. Tính các điểm đƣợc vẽ trên các đƣờng tròn sau: a. Đƣờng tròn có phƣơng trình (x – 6)2 + (y-3)2 = 121 theo thuật toán Midpoint b. Đƣờng tròn có bán kính bằng 10 và tâm tại điểm (5, 5) theo thuật toán Bresenham 3. Trình bày giải thuật DDA sinh đƣờng thẳng với hệ số góc m > 1, Dx >0. Áp dụng giải thuật, tính các điểm đƣợc vẽ trên đoạn thẳng giới hạn bởi 2 điểm với các tọa độ A(15, 27), B(22, 35). 4. Trình bày giải thuật Midpoint sinh đƣờng thẳng với hệ số góc m > 1, Dx >0. Áp dụng giải thuật, tính các điểm đƣợc vẽ trên đoạn thẳng giới hạn bởi 2 điểm A(12, 19); B(18, 27). 5. Trình bày giải thuật Bresenham sinh đƣờng thẳng với hệ số góc m > 1, Dx >0. Áp dụng giải thuật, tính các điểm đƣợc vẽ trên đoạn thẳng giới hạn bởi 2 điểm A(20, 22); B(25, 30). 6. Áp dụng giải thuật Bresenham viết hàm sinh đoạn thẳng (xét tất cả các trƣờng hợp của hệ số góc). 7. Áp dụng giải thuật Midpoint viết hàm sinh đoạn thẳng (xét tất cả các trƣờng hợp của hệ số góc). 8. Áp dụng giải thuật DDA viết hàm sinh đoạn thẳng (xét tất cả các trƣờng hợp của hệ số góc). 59
Đồ họa máy tính 9. Dùng giải thuật Midpoint viết hàm sinh đƣờng tròn có toạ độ tâm (xc, yc) và bán kính r. 10. Áp dụng các giải thuật DDA, Bresenham, Midpoint tính các điểm đƣợc vẽ trên các đoạn thẳng giới hạn bởi các cặp điểm sau: a. A(9, 22), B(19, 28) b. C(10,10), D(15, 21) c. E(9, 19), F(1, 29) 11. Tính các điểm đƣợc vẽ trên các đƣờng tròn sau: a. Đƣờng tròn có phƣơng trình (x – 2)2 + (y-7)2 = 121 theo thuật toán Midpoint b. Đƣờng tròn có bán kính bằng 13 và tâm tại điểm (1, -5) theo thuật toán Bresenham 12. Cài đặt thủ tục vẽ đoạn thẳng theo thuật toán Bresenham và MidPoint cho các trƣờng hợp hệ số góc m>1, m<-1, -1<m<0. 13. Viết thủ tục LineTo(x,y:Integer); để vẽ đoạn thẳng từ vị trí hiện thời đến điểm có tọa độ (x,y). 14. Viết thủ tục LineRel(dx,dy:Integer); để vẽ đoạn thẳng từ vị trí hiện thời đến điểm mới cách điểm hiện thời một khoảng theo trục x là dx và theo trục y là dy. 15. Cài đặt thủ tục vẽ đƣờng tròn theo thuật toán MidPoint. 16. Viết thủ tục Arc(x0,y0,g1,g2:Integer; R:Word); để vẽ cung tròn có tâm (x0,y0) bán kính R với góc bắt đầu là g1 và góc kết thúc là g2. 17. Viết thủ tục Sector(x0,y0,g1,g2:Integer; Rx,Ry:Word); để vẽ cung Ellipse có tâm (x0,y0) bán kính theo trục X là Rx, bán kính theo trục Y là Ry với góc bắt đầu là g1 và góc kết thúc là g2. 18. Viết thủ tục DrawPoly(P:Array; n:Byte; xc,yc,R:Word); để vẽ một đa giác đều có n đỉnh lƣu trong mảng P nội tiếp trong đƣờng tròn tâm (xc,yc) bán kính R. 19. Viết thủ tục Circle3P(A,B,C:ToaDo2D); để vẽ đƣờng tròn đi qua 3 điểm A,B,C. 20. Viết thủ tục Arc3P(A,B,C:ToaDo2D); để vẽ cung tròn đi qua 3 điểm A,B,C. 21. Vẽ đồ thị các hàm số sau: y = ax2 + bx + c, y = ax3 + bx2 + cx + d, y = ax4 + bx3 + cx2 + dx + e ax b ax 2 bx c y = , y = . cx d dx e 60
Đồ họa máy tính 22. Vẽ các đƣờng cong sau: x 2 y 2 y2 = 2px + = 1 - = 1 a 2 b 2 Hƣớng dẫn giải bài tập 1. a. Stt 1 2 3 4 5 6 7 8 9 x 10 11 12 13 14 15 16 17 18 y 20 21 22 23 24 24 25 26 27 b. Stt 1 2 3 4 5 6 7 8 9 x 16 17 18 19 20 21 22 23 24 y 19 20 21 21 22 23 24 24 25 P 4 0 -4 8 4 0 -4 8 4 c. Stt 1 2 3 4 5 6 7 8 9 x 15 16 17 18 19 20 21 22 23 y 17 18 18 19 19 20 21 21 22 P 2 -4 6 0 10 4 -2 8 2 2. a. Stt 1 2 3 4 5 6 7 8 9 x 6 7 8 9 10 11 12 13 14 y 14 14 14 14 13 13 12 11 11 P -10 -7 -2 5 -6 5 0 -1 16 b. Stt 1 2 3 4 5 6 7 8 9 x 5 6 7 8 9 10 11 12 13 y 15 15 15 15 14 14 13 12 11 P -17 -11 -1 13 -5 17 11 13 23 3. - Giải thuật DDA sinh đƣờng thẳng với hệ số góc m > 1, Dx >0. void ddaline (int x1,int y1,int x2,int y2,int c) { int x=x1; float y=y1; float k=(float)(x2-x1)/(y2-y1); 61
Đồ họa máy tính putpixel(x,round(y),c); for(int i=y1;i 1, Dx >0. void Mid_line(int x1, int y1, int x2, int y2, int c) { int x, y, dx, dy,d; y = y1; dx = x2 - x1; dy = y2 - y1; d= 2dx - dy; for (y=y1; y<=y2; y++) { putpixel(x, y, c); if (d < 0) d = d + 2dx; else { x ++; d = d + 2dx - 2dy; } } } 62
Đồ họa máy tính - Áp dụng giải thuật, tính các điểm đƣợc vẽ trên đoạn thẳng giới hạn bởi 2 điểm A(12, 19); B(18, 27). Stt 1 2 3 4 5 6 7 8 9 x 12 13 14 14 15 16 17 17 18 y 19 20 21 22 23 24 25 26 27 P 4 0 -4 8 4 0 -4 8 4 5. Giải thuật Bresenham sinh đƣờng thẳng với hệ số góc m > 1, Dx >0. void Bre_line(int x1, int y1, int x2, int y2, int c) {int x, y, dx, dy,p,const1,const2; y = y1; dx = x2 - x1; dy = y2 - y1; p = 2*dx - dy; const1 = 2*dx; const2 = 2*(dx-dy); for (y=y1; y<=y2; y++) { putpixel(x, y, c); if (p < 0) p += const1; // p=p + 2dx else { p +=const2; //p=p+2dx-2dy x++; } } } - Áp dụng giải thuật, tính các điểm đƣợc vẽ trên đoạn thẳng giới hạn bởi 2 điểm A(12, 19); B(18, 27). Stt 1 2 3 4 5 6 7 8 9 x 20 21 21 22 23 23 24 24 25 y 22 23 24 25 26 27 28 29 30 P 2 -4 6 0 -6 4 -2 8 2 63
Đồ họa máy tính Chƣơng 3 CÁC GIẢI THUẬT ĐỒ HOẠ CƠ SỞ 3.1. Hệ toạ độ và mô hình chuyển đổi 3.1.1. Các hệ thống tọa độ trong đồ họa 1) Hệ toạ độ thực (WCS – World Coordinate System) Hệ toạ độ của đối tƣợng đƣợc các chƣơng trình ứng dụng sử dụng để mô tả toạ độ các đối tƣợng trong thế giới thực. Đơn vị trong hệ thống toạ độ phụ thuộc vào không gian và kích thƣớc của đối tƣợng đƣợc mô tả: mm, m, km Hình 3.1 Hệ toạ độ thực 2) Hệ toạ độ thiết bị (DCS – Device Coordinate System) Là hệ thống toạ độ của thiết bị nơi hiển thị hình ảnh và không gian của đối tƣợng mà ứng dụng mô tả. Không gian của hệ thống của toạ độ này chính là kích thƣớc của thiết bị hiển thị đƣợc sử dụng. Ví dụ: màn hình VGA 640x480, SVGA 600x800 Hình 3.2 DCS – Device Coordinate System 3) Hệ toạ độ thiết bị chuẩn (NDCS – Normalized Device Coordinate System) 64
Đồ họa máy tính Chuyển đổi đối tƣợng từ không gian thực vào toạ độ thiết bị hiển thị. Phần mềm đồ hoạ đƣợc viết sẽ thực hiện sự chuyển đổi mà chƣa thể xác định rõ kích thƣớc của thiết bị cũng nhƣ độ phân giải. Ta có công cụ độc lập với thiết bị nhằm mô tả vùng hiển thị ra hệ toạ độ thiết bị chuẩn hoá. Coi NDCS nhƣ hệ toạ độ thiết bị có kích thƣớc màn hình hiển thị là một hình vuông có cạnh là một đơn vị (1x1). Hình 3.3 NDCS – Normalized Device Coordinate System - Qui trình để chuyển đổi các đối tƣợng trong WCS sang NDCS đƣợc gọi là phép ánh xạ cửa sổ sang cổng xem hay phép biến đổi chuẩn hoá (Window to Viewport mapping or Normalization Transformation) - Qui trình có thể áp các toạ độ thiết bị hiển thị chuẩn hoá sang các thiết bị rời rạc đƣợc gọi là phép biến đổi trạm làm việc (Workstation Transformation) 3.1.2. Phép chuyển đổi - Một cửa sổ (window) đƣợc chỉ định bởi bốn toạ độ thực (WCS): Xwmin, Xwmax, Ywmin, Ywmax - Một cổng xem (viewport) đƣợc mô tả bởi bốn toạ độ thiết bị chuẩn hoá (NDCS): Xvmin, Xvmax, Yvmin, Yvmax a) b) Hình 3.4 a)Đối tượng cổng xem; b)Đối tượng trong cửa sổ 65
Đồ họa máy tính Mục đích của phép ánh xạ này là chuyển đổi các toạ độ thực (Xw,Yw) của một điểm tuỳ ý sang thiết bị chuẩn hoá tƣơng ứng (Xv,Yv). Để giữ lại khoảng cách của điểm trong cổng xem bằng với khoảng cách của điểm trong cửa sổ, với yêu cầu: − − 푣 푣 푖푛 = 푤 푤 푖푛 푣 − 푣 푖푛 푤 − 푤 푖푛 − − 푣 푣 푖푛 = 푤 푤 푖푛 푣 − 푣 푖푛 푤 − 푤 푖푛 푣 = 푣 푖푛 + ( 푤 − 푤 푖푛 )푠 푣 = 푣 푖푛 + ( 푤 − 푤 푖푛 )푠 푣 − 푣 푖푛 푠 = 푤 − 푤 푖푛 푣 − 푣 푖푛 푠 = 푤 − 푤 푖푛 3.2. Các giải thuật xén tỉa 3.2.1. Khái niệm Xén tỉa là tiến trình xác định các điểm của một đối tƣợng nằm trong hay ngoài cửa sổ hiển thị. Nằm trong đƣợc hiển thị, nằm ngoài loại bỏ. Việc loại từng điểm ảnh của đối tƣợng thƣờng chậm nhất là khi đối tƣợng mà phần lớn nằm ngoài cửa sổ hiển thị. 3.2.2. Các giải thuật xén tỉa đoạn thẳng 1) Bài toán: Cho cửa sổ với các đƣờng biên có tọa độ góc dƣới trái và góc trên phải lần lƣợt là (xwmin, ywmin), (xwmax, ywmax) và đoạn thẳng cho bởi 2 điểm P1(x1, y1), P2(x2, y2). Hãy xác định phần hiển thị của đoạn thẳng trong cửa sổ trên. 2) Ý tưởng: Hình 3.5. Điểm và đoạn thẳng bị cắt khỏi cửa sổ 66
Đồ họa máy tính Việc cắt các điểm khỏi cửa sổ đƣợc hiểu đơn giản là chúng ta kiểm tra các giá trị tọa độ để xác định xem chúng có nằm bên trong biên không. Một điểm ở vị trí (x,y) đƣợc giữ lại để chuyển đổi sang vùng quan sát nếu nó thỏa các bất phƣơng trình sau: xwmin ≤ x ≤ xwmax, ywmin ≤ y ≤ ywmax Nếu điểm nào không thỏa một trong bốn bất phƣơng trình trên, nó bị cắt bỏ. Trong hình 3.5, điểm P1 đƣợc giữ lại, trong khi điểm P2 bị cắt bỏ. Hình 3.5 minh họa các quan hệ có thể có giữa các vị trí đoạn thẳng với biên cửa sổ. Chúng ta kiểm tra một đoạn thẳng xem có bị cắt hay không bằng việc xác định xem hai điểm đầu mút đoạn thẳng là nằm trong hay nằm ngoài cửa sổ. Một đoạn thẳng với cả hai đầu nằm trong cửa sổ thì đƣợc giữ lại hết, nhƣ đoạn từ P5 đến P6. Một đoạn với một đầu nằm ngoài (P9) và một đầu nằm trong (P10) sẽ bị cắt bớt tại giao điểm với biên cửa sổ (P‘9). Các đoạn thẳng có cả hai đầu đều nằm ngoài cửa sổ, có thể rơi vào hai trƣờng hợp: toàn bộ đoạn thẳng đều nằm ngoài hoặc đoạn thẳng cắt hai cạnh cửa sổ. Đoạn từ P3 đến P4 bị cắt bỏ hoàn toàn. Nhƣng đoạn từ P7 đến P8 sẽ đƣợc giữ lại phần từ P‘7 đến P‘8. Thuật toán clipping đƣờng (line-clipping) xác định xem đoạn nào toàn bộ nằm trong, đoạn nào bị cắt bỏ hoàn toàn hay bị cắt một phần. Đối với các đoạn bị cắt bỏ một phần, các giao điểm với biên cửa sổ phải đƣợc tính. Vì một hình ảnh có thể chứa hàng ngàn đoạn thẳng, việc xử lý clipping nên đƣợc thực hiện sao cho có hiệu quả nhất. Trƣớc khi đi tính các giao điểm, một thuật toán nên xác định rõ tất cả các đoạn thẳng đƣợc giữ lại hoàn toàn hoặc bị cắt bỏ hoàn toàn. Với những đoạn đƣợc xem xét là bị cắt bỏ, việc xác định các giao điểm cho phần đƣợc giữ lại nên đƣợc thực hiện với sự tính toán ít nhất. 3) Giải thuật Cohen Sutherland Outcode Một tiếp cận để cắt các đoạn là dựa trên cơ chế đánh mã đƣợc phát triển bởi Cohen và Sutherland. Mọi điểm ở hai đầu mút đoạn thẳng trong hình ảnh sẽ đƣợc gán một mã nhị phân 4 bit, đƣợc gọi là mã vùng (region code) nhƣ ở hình 3.6, giúp nhận ra vùng tọa độ của một điểm. Các vùng này đƣợc xây dựng dựa trên sự xem xét với biên cửa sổ. Mỗi vị trí bit trong mã vùng đƣợc dùng để chỉ ra một trong bốn vị trí tọa độ tƣơng ứng của điểm so với cửa sổ: bên trái (left), phải (right), trên đỉnh (top), dƣới đáy (bottom). Việc đánh số theo vị trí bit trong mã vùng từ 1 đến 4 cho từ phải sang trái, các vùng tọa độ có thể liên quan với vị trí bit nhƣ sau: 67
Đồ họa máy tính 4 3 2 1 Trên Dƣới Phả Trái i Hình 3.6 Vị trí các bit trong mã vùng nhị phân Giá trị 1 ở bất kỳ vị trí nào chỉ ra rằng điểm ở vị trí tƣơng ứng, ngƣợc lại bit ở vị trí đó là 0. Nếu một điểm nằm trong cửa sổ, mã vị trí là 0000. Một điểm bên dƣới và bên trái cửa sổ có mã vùng là 0101 (xem hình 3.7) 1001 1000 1010 Cửa sổ 0001 0010 0000 0101 0100 0110 Hình 3.7 Các mã vùng nhị phân cho các điểm đầu mút đoạn thẳng được dùng để định nghĩa các vùng tọa độ liên hệ với một cửa sổ. Các giá trị bit trong mã vùng đƣợc xác định bằng cách so sánh giá trị tọa độ (x,y) của điểm đầu mút với biên cửa sổ. Bit 1 bằng 1 nếu x < xwmin. Các giá trị của ba bit còn lại đƣợc xác định bằng cách so sánh tƣơng tự. Bít 4 = sign(y-yw ) max Bít 3 = sign(yw -y) min Bít 2 = sign(x-xw ) (3.1) max Bít 1 = sign(xw -x) min Trong đó ta có quy ƣớc: sign a = 1 nếu a ≥ 0 0 nếu a < 0 Khi xây dựng xong các mã vùng cho tất cả các điểm đầu mút, chúng ta có thể xác định nhanh chóng đoạn thẳng nào là hoàn toàn nằm trong cửa sổ, đoạn nào là hoàn toàn nằm ngoài. Bất kỳ đoạn nào có mã vùng của cả 2 đầu mút là 0000 thì nằm trong cửa sổ và chúng ta chấp nhận các đƣờng này. Bất kỳ đƣờng nào mà trong hai mã vùng 68
Đồ họa máy tính của hai đầu mút có một số 1 ở cùng vị trí bit thì đoạn thẳng hoàn toàn nằm ngoài cửa sổ, và chúng ta loại bỏ các đoạn này. Ví dụ, ta bỏ đoạn có mã vùng ở một đầu là 1001, còn đầu kia là 0101 (có cùng bit 1 ở vị trí 1 nên cả hai đầu mút của đoạn này nằm ở phía bên trái cửa sổ). Một phƣơng pháp có thể đƣợc dùng để kiểm tra các đoạn cho việc cắt toàn bộ là thực hiện phép logic and với cả hai mã vùng. Nếu kết quả không phải là 0000 thì đoạn nằm bên ngoài cửa sổ (hình 3.8). Hình 3.8 Các đoạn từ một điểm này đến một điểm khác có thể cắt cửa sổ hoặc giao điểm với các biên nằm ngoài cửa sổ. Các đƣờng không đƣợc nhận dạng là hoàn toàn nằm trong hay hoàn toàn nằm ngoài một cửa sổ thông qua các phép kiểm tra trên sẽ đƣợc tìm giao điểm với biên cửa sổ. Nhƣ đƣợc chỉ ra ở hình 3.8, các đƣờng thuộc nhóm này có thể cắt hoặc không cắt cửa sổ. Chúng ta có thể xử lý các đoạn này bằng cách so sánh một điểm đầu mút (điểm đang nằm ngoài cửa sổ) với một biên cửa sổ để xác định phần nào của đƣờng sẽ bị bỏ. Sau đó, phần đƣờng đƣợc giữ lại sẽ đƣợc kiểm tra với các biên khác, và chúng ta tiếp tục cho đến khi toàn bộ đƣờng bị bỏ đi hay đến khi một phần đƣờng đƣợc xác định là nằm trong cửa sổ. Chúng ta xây dựng thuật toán để kiểm tra các điểm đầu mút tƣơng tác với biên cửa sổ là ở bên trái, bên phải, bên dƣới hay trên đỉnh. Để minh họa các bƣớc xác định trong việc cắt các đoạn khỏi biên cửa sổ dùng thuật toán của Cohen-Sutherland, chúng ta xem các đoạn trong hình 3.8 đƣợc xử lý nhƣ thế nào. Bắt đầu ở điểm đầu mút bên dƣới từ P1 đến P2, ta kiểm tra P1 với biên trái, phải và đáy cửa sổ và thấy rằng điểm này nằm phía dƣới cửa sổ. Ta tìm giao điểm P‘1 với biên dƣới. Sau khi tìm giao điểm P‘1, ta bỏ đoạn từ P1 đến P‘1. Tƣơng tự, vì P2 bên ngoài cửa sổ, ta kiểm tra và thấy rằng điểm này nằm phía trên cửa sổ. Giao điểm P‘2 đƣợc tính, và đoạn từ P‘1 đến P‘2 đƣợc giữ lại. Kết thúc quá trình xử lý đoạn P1P2. Bây giờ xét đoạn kế tiếp, P3P4. Điểm P3 nằm bên trái cửa sổ, vì vậy ta xác định giao điểm P‘3 và loại bỏ đoạn từ P‘3 đến P3. Bằng cách kiểm tra mã vùng phần đoạn thẳng 69
Đồ họa máy tính từ P‘3 đến P4, chúng ta thấy rằng phần còn lại này nằm phía dƣới cửa sổ và cũng bị bỏ luôn. Các giao điểm với biên cửa sổ có thể đƣợc tính bằng cách dùng các tham số của phƣơng trình đƣờng thẳng. Với một đƣờng thẳng đi qua hai điểm (x1, y1) và (x2, y2), tung độ y của giao điểm với một biên dọc cửa sổ có thể tính đƣợc theo công thức: y = y1 + m (x - x1) (3.2) Ở đây giá trị x đƣợc đặt là xwmin hoặc xwmax, và hệ số góc m đƣợc tính bằng m = (y2 - y1)/ (x2 - x1) Tƣơng tự, nếu ta tìm giao điểm với biên ngang, hoành độ x có thể đƣợc tính nhƣ sau: x = x1 + (y - y1)/m (3.3) Với y là ywmin hoặc ywmax. Nhƣ vậy việc thực hiện giải thuật Cohen-Sutherland chia làm hai bƣớc: Bƣớc 1: Gán mã vùng 4-bit cho mỗi điểm đầu, cuối của đoạn thẳng theo nguyên tắc (3.1). Bƣớc 2: Quá trình kiểm tra vị trí của đoạn thẳng so với cửa sổ. Giả sử 2 điểm đầu cuối của đoạn thẳng là P1 và P2 đã đƣợc cấp mã. Trƣờng hợp1: Mã của P1 hoặc P2 đều = 0000 thì đoạn thẳng thuộc phần hiển thị. If (P1.Mã || P2.Mã == 0000) then―đoạn thẳng thuộc cửa sổ‖ Trƣờng hợp 2:Mã của P1 và P2 có cùng một vị trí mà ở đó ≠ 0 thì P1 và P2 phải nằm cùng một phía của cửa sổ. If (P1.Mã & P2.Mã != 0000) then ― 2 điểm nằm về 1 phía của cửa sổ‖ Trƣờng hợp 3:Tìm giao điểm của đƣờng thẳng với cửa sổ, chính xác hơn là với phần mở rộng của đƣờng biên theo (3.2) hoặc (3.3) sau đó quay trở lại bƣớc 1. Sơ đồ giải thuật Cohen-Sutherland 70
Đồ họa máy tính Ví dụ 3.1. Cho cửa sổ với các đƣờng biên: xmin = 25, ymin = 24, xmax = 149, ymax = 84 và các đoạn thẳng: + Đoạn thẳng AB với điểm A(-99, 124); điểm B(273, 4) + Đoạn thẳng CD với điểm C(86, 168); điểm D(275, 42) + Đoạn thẳng EF với điểm E(48, 42); điểm F(137, 64) Áp dụng giải thuật Cohen-Sutherland xác định chính xác phần nào trong các đoạn thẳng trên đƣợc hiển thị. Giải: + Đoạn thẳng AB với điểm A có mã 1001, điểm B có mã 0110, do đó thực hiện xén tỉa đoạn thẳng AB. Xén tỉa AB với biên trái ta đƣợc điểm A‘ với tọa độ đƣợc tính nhƣ sau: M = (y2 - y1)/(x2 – x1) = (4 - 124)/ (273 + 99) = -120 / 372 xA‘ = 25 120 y = y + m (x – x ) = 124 - 25 + 99 = 84 A‘ A A‘ A 372 đoạn thẳng AB trở thành A‘B với điểm A‘(25, 84), và điểm A‘ có mã 0000. 71
Đồ họa máy tính - Xén tỉa A‘B với biên phải, đoạn thẳng A‘B trở thành A‘B‘ với điểm B‘(149, 44) với điểm B‘ có mã 0000. - Do A‘ và B‘ đều có mã bằng 0000 nên đoạn thẳng A‘B‘ đã nằm trong cửa sổ do đó kết thúc đoạn thẳng AB đƣợc xén tỉa thành A‘B‘ + Đoạn thẳng CD vơi điểm C có mã (1000) điểm D có mã 0010, thực hiện xén tỉa CD với biên phải đoạn thẳng CD thành đoạn thẳng CD‘ với D‘(149, 126) và điểm D‘ có mã (1000), ta thấy mã điểm C và D‘ có bít thứ 4 giống nhau do đó đoạn thẳng CD‘ nằm phía trên cửa sổ, vậy đoạn thẳng CD nằm ngoài cửa sổ. + Đoạn thẳng EF với điểm E có mã 0000 và điểm F có mã 0000 vậy đoạn thẳng EF nằm trong cửa sổ. 4) Giải thuật chia trung điểm Ý tƣởng của thuật toán tƣơng tự nhƣ thuật toán tìm nghiệm bằng phƣơng pháp chia nhị phân. Với M là trung điểm của đoạn thẳng AB ta có nhận xét: Nếu mã(A) ≠ 0000, mã(B) ≠ 0000, mã(M) ≠ 0000 thì ta có: [mã(A) AND mã(M)] ≠ 0000 hoặc [mã(M) AND mã(B)] ≠ 0000. Hay nói cách khác ‗Nếu cả ba điểm A, B, M đều nằm ngoài cửa sổ thì có ít nhất một đoạn thẳng nằm ngoài hoàn toàn cửa sổ‘. Dựa trên ý tƣởng trên, giải thuật chia trung điểm xén tỉa đoạn thẳng P1P2bao gồm các bƣớc sau: Bƣớc 1: Xác định mã của điểm đầu P1, điểm cuối P2 của đoạn thẳng P1P2 Bƣớc 2: Nếu mã của hai điểm P1, P2 đều bằng 0000 thì toàn bộ đoạn thẳng đƣợc hiển thị. Kết thúc Bƣớc 3: Nếu mã của hai điểm P1, P2 khác 0000 và mã(P1) and mã(P2) khác 0000 thì toàn bộ đoạn thẳng không đƣợc hiển thị. Kết thúc Bƣớc 4: Đoạn thẳng đƣợc xén tỉa theo cách sau: chia đoạn thẳng thành 2 phần bằng nhau, và lặp lại bƣớc 1 cho hai đoạn vừa chia cho đến khi toàn bộ các đoạn hoặc nằm trong hoàn toàn hoặc nằm ngoài hoàn toàn (loại bỏ đi những phần đoạn thẳng nằm ngoài hoàn toàn so với cửa sổ). Ví dụ 3.2.Cho cửa sổ với các đƣờng biên: xmin = 25, ymin = 24, xmax = 149, ymax = 84 và các đoạn thẳng: + Đoạn thẳng AB với điểm A(36, 36); điểm B(84, 228) + Đoạn thẳng CD với điểm C(49, 149); điểm D(98, 103) 72
Đồ họa máy tính + Đoạn thẳng EF với điểm E(53, 64); điểm F(94, 37) Áp dụng giải thuật Chia trung điểm xác định chính xác phần nào trong các đoạn thẳng trên đƣợc hiển thị. Giải: + Đoạn thẳng AB: với điểm A có mã 0000 và điểm B có mã 1000, ta thực hiện chia đoạn thẳng thành 2 đoạn thẳng AM, MB với M(60, 132) có mã 1000.Đoạn thẳng MB với M có mã 1000 và điểm B có mã 1000 với mã(M) and mã(B) ≠ 0000, nên đoạn thẳng nằm ngoài cửa sổ, loại bỏ đoạn thẳng MB. Thực hiện xén tỉa đoạn thẳng AM có điểm A nằm trong, M nằm ngoài, ta gọi M1 là trung điểm của đoạn AM với M1(48, 84) có mã 0000 do đó đoạn thẳng AB đƣợc xén tỉa thành đoạn thẳng AM1. + Đoạn thẳng CD với C có mã 1000 và điểm D có mã 1000 với mã(C) and mã(D) ≠ 0000, nên đoạn thẳng nằm ngoài cửa sổ. + Đoạn thẳng EF có mã 2 điểm E, F đều bằng 0000 nên đoạn thẳng EF nằm trong cửa sổ. 5. Giải thuật 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. Chúng ta có thể viết phƣơng trình đƣờng thẳng qua 2 điểm (x1, y1) và (x2, y2) theo hình thức tham số: x = x1 + (x2 – x1)u = x1 + Δx u (3.4) y = y1 + (y2 – y1)u = y1 + Δy u Với Δx = x2 – x1 và Δy = y2 – y1. Tham số u đƣợc gán các giá trị từ 0 đến 1, và các tọa độ (x,y) là tọa độ các điểm trên đƣờng ứng với các giá trị cụ thể của u trong đoạn [0,1]. Khi u = 0, (x, y) = (x1, y1). Ở đầu kia của đoạn, u = 1 và (x, y) = (x2, y2).Nếu một điểm (x, y) dọc theo đƣờng mà nằm trong cửa sổ đƣợc định nghĩa bởi các tọa độ (xwmin, ywmin) và (xwmax, ywmax), thì các điều kiện sau đây phải đƣợc thỏa mãn: xwmin ≤ x1 + Δx u ≤ xwmax (3.5) ywmin ≤ y1 + Δy u ≤ ywmax Bốn bất phƣơng trình trên có thể đƣợc viết lại theo hình thức sau: pk u ≤ qk, k = 1, 2, 3, 4 (3.6) ở đây p và q đƣợc định nghĩa nhƣ sau: 73
Đồ họa máy tính p1 = -Δx, q1 = x1 - xwmin (3.7) p2 = Δx, q2 = xwmax – x1 p3 = -Δy, q3 = y1 - ywmin p4 = Δy, q4 = ywmax – y1 Bất kỳ đoạn thẳng nào song với một trong các biên cửa sổ sẽ có pk = 0, giá trị k phụ thuộc vào biên cửa sổ (k = 1, 2, 3, và 4 tƣơng ứng với biên trái, phải, dƣới, trên). Nếu với các giá trị đó của k, chúng ta có thể gặp qk 0, đoạn thẳng tiến từ bên trong ra bên ngoài. Với pk khác 0, chúng ta có thể tính giá trị của u tƣơng ứng với điểm mà tại đó đoạn thẳng kéo dài cắt biên k kéo dài của cửa sổ: u = qk/pk (3.8) Đối với mỗi đoạn thẳng, chúng ta có thể tính các giá trị cho các tham số u1 và u2 để xác định phần nào của đoạn nằm bên trong cửa sổ. Giá trị của u1 đƣợc xác định bằng cách nhìn ở các cạnh của cửa sổ xem đoạn kéo dài nào từ ngoài vào trong (p 0). Một giá trị của rk đƣợc tính cho mỗi biên cửa sổ, và giá trị của u2 là nhỏ nhất trong tập chứa và các giá trị đã đƣợc tính của r. Nếu u1> u2, đoạn hoàn toàn nằm ngoài cửa sổ và có thể bị vứt bỏ. Ngƣợc lại, các điểm đầu mút của đoạn bị cắt đƣợc tính từ hai giá trị của tham số u. Nhƣ vậy việc thực hiện giải thuật Liang-Barsky chia thành các bƣớc sau: Bƣớc 1: Tính pk, qk theo (3.7) Bƣớc1: Nếuk:pk=0 qk Kết thúc qk ≥ 0 thực hiện bƣớc tiếp theo Bƣớc 2: Tính u1, u2 74
Đồ họa máy tính q  u max 0  u : u k , P 0 1  k k k  Pk  qk  u2 min 1 uk : uk , Pk 0 P k  Tính tọa độ giao điểm Q1(x1 + u1dx, y1 + u1 dy); Q2(x2 + u2dx, y2 + u2 dy) Ví dụ 3.3.Cho cửa sổ hình chữ nhật có góc trái dƣới xwmin = 1, ywmin = 2, góc phải trên xwmax = 9, ywmax = 8 và các đoạn thẳng AB có toạ độ A(11,10) và B(11,6), đoạn thẳng CD có toạ độ C(3,2), D(8,4), đoạn thẳng IJ có toạ độ I(-1,7) và J(11,1). Xác định phần hiển thị của các đoạn thẳng trong cửa sổ. Giải: + Xét đoạn thẳng AB P1 = 0; q1 = 10 P2 = 0; q2 = -2 P3 = 4; q3 = 8 P4 = -4; q4 = -2 Có P2 = 0 mà q2 = -2 0) Với [u1, u2] = [0, 1] => CD nằm hoàn toàn trong cửa sổ + Xét đoạn thẳng IJ P1 = -12; q1= -2; u1=1/6 75
Đồ họa máy tính P2 = 12; q2 = 10; u2=5/6 P3 = 6; q3 = 5; u3=5/6 P4 = -6; q4 = 1; u4=-1/6 Vậy: u1 = max(0, 1/6, -1/6) = 1/6 (với Pk 0) Giao điểm của đoạn thẳng IJ với cửa sổ là Q1, Q2 với: Q1(-1 + (1/6). 12 , 7 + (1/6). (-6)) ; Q2(11 + (5/6).12, 1 + (5/6).(-6)) Phần hiển thị của đoạn IJ là từ Q1(1, 6) đến Q2(9,2) 3.2.3. Giải thuật Hodgman Một kỹ thuật cho việc clipping đa giác, đƣợc phát triển bởi Hodgman, thực hiện việc clipping bằng cách so sánh một đa giác với lần lƣợt mỗi biên cửa sổ. Kết quả trả về của thuật toán là một tập các đỉnh định nghĩa vùng bị cắt (vùng này đƣợc tô với một màu hay một mẫu tô nào đó). Các vùng đa giác đƣợc định nghĩa bằng việc xác định một dãy có thứ tự các đỉnh. Để cắt một đa giác, chúng ta so sánh lần lƣợt mỗi đỉnh với biên một cửa sổ. Các đỉnh nằm bên trong cạnh cửa sổ này đƣợc giữ lại cho việc clipping với biên kế tiếp của cửa sổ (hình 3.9). Thuật toán đƣợc trình bày nhƣ sau: Giả sử v1, v2, , vn là các đỉnh của đa giác. Quá trình xén tỉa đƣợc thực hiện trên các cảnh của đa giác tạo bởi 2 đỉnh liên tiếp vi và vi+1 có 4 trƣờng hợp có thể xảy ra: (i) Nếu vi nằm ngoài, vi+1 nằm trong, ta lƣu giao điểm I của cạnh vivi+1với biên của cửa sổ và vi+1. (ii) Nếu cả vi, vi+1 đều nằm trong, ta sẽ lƣu vi+1. (iii) Nếu vi nằm trong, vi+1 nằm ngoài, ta sẽ lƣu giao điểm I. (iv) Nếu cả vi, vi+1 đều nằm ngoài, ta không lƣu gì cả. 76
Đồ họa máy tính Vi I Vi+1 Vi Vi+1 Vi Vi+1 I Vi+1 Vi (i) (ii) (iii) (iv) Hình 3.9 Các trường hợp xén tỉa một cạnh của cửa sổ với biên cửa sổ Ví dụ 3.4:Xén tỉa đa giác v1v2v3v4v5 trên cửa sổ đƣợc giới hạn bởi các biên we1, we2, we3, we4. Giải: Hình 3.10 Các bước xén tỉa đa giác v1v2v3v4v5 3.3. Các giải thuật tô miền kín 3.3.1. Giải thuật đƣờng biên Bài toán: Cần tô màu một vùng nếu biết đƣợc màu của đƣờng biên vùng tô và một điểm nằm bên trong vùng tô Ý tưởng: Bắt đầu từ một điểm nằm bên trong vùng tô, kiểm tra các điểm lân cận của nó đã đƣợc tô với màu muốn tô, hay điểm lân cận có màu trùng với màu 77
Đồ họa máy tính biên không? Nếu cả hai trƣờng hợp đều không phải thì ta sẽ tô điểm đó với màu muốn tô. Quá trình này đƣợc lặp lại cho đến khi không còn tô đƣợc nữa thì dừng (hình 3.11). Hình 3.11 Tô màu theo đường biên Có 2 quan điểm về cách tô này. Đó là dùng 4 điểm lân cận (có thể gọi là 4 liên thông) hay 8 điểm lân cận (8 liên thông) (hình 3.12). (a) (b) Hình 3.12 (a) 4 điểm lân cận, (b) 8 điểm lân cận Thuật toán đƣờng biên : procedure Boundary_fill ( x,y, mauto, maubien :integer); begin mau_ht:= getpixel(x, y); if ((mau_ht maubien) )then begin putpixel(x,y,color); Boundary_fill ( x+1,y, mauto, maubien ); Boundary_fill ( x-1,y, mauto, maubien ); Boundary_fill ( x,y+1, mauto, maubien ); Boundary_fill ( x,y-1, mauto, maubien ); end; end ; 3.3.2. Giải thuật dòng quét cho việc tô màu vùng Giải thuật dựa trên ý tƣởng sử dụng một đƣờng quét trên trục y của màn hình đi từ ymax đến ymin của vùng cần đƣợc tô màu. Với mỗi giá trị y = yi đƣờng thẳng quét cắt các đƣờng biên của vùng cần tô tạo ra đoạn thẳng y = yi với x [xmin, xmax]. Trên đoạn 78
Đồ họa máy tính thẳng đó chúng ta tô màu các điểm tƣơng ứng đi từ xmin đến xmax có các điểm tô (xi, yi) y = yi. Đơn giản nhất ví dụ tô màu hình chữ nhật: procedure scanline_rectg(x1,y1,x2,y2,c :integer) {(x1,y1) là tọa độ điểm dưới cùng bên trái} {(x2, y2) là tọa độ điểm trên cùng bên phải} begin var i,j :integer; for i := y1 to y2 do for j :=x1 to x2 do putpixel(i,j,c); end ; Phép tô màu 1 đa giác bất kỳ sẽ phức tập hơn rất nhiều so với hình chữ nhật Giả sử vùng tô đƣợc cho bởi 1 đa giác n đỉnh: pi (xi, yi), i=0,1, ,n-1. Đa giác này có thể là đa giác lồi, đa giác lõm hay đa giác tự cắt Các bƣớc tóm tắt chính của thuật toán: - Tìm ytop, ybottom lần lƣợt là giá trị lớn nhất, nhỏ nhất của tập các tung độ của các đỉnh của đa giác đã cho. ytop = max{yi,(xi,yi) P}, ybottom = min{yi,(xi,yi) P}. - Ứng với mỗi dòng quét y = k, với k thay đổi từ ybottom đến ytop lặp: + Tìm tất cả các hoành độ giao điểm của dòng quét y = k với các cạnh của đa giác + Sắp xếp các hoành độ giao điểm theo thứ tự tăng dần: x0, x1, + Tô màu các đoạn thẳng trên đƣờng thẳng y = k lần lƣợt đƣợc giới hạn bởi các cặp (x0, x1), (x2,x3), , (x2k,x2k+1). Ta sẽ gặp 1 số vấn đề sau: - Ứng với mỗi dòng quét không phải lúc nào tất cả các cạnh của đa giác cũng tham gia cắt dòng quét. Do đó để cải thiện tốc độ cần phải có một cách nào đó để hạn chế đƣợc số cạnh cần tìm giao điểm ứng với mỗi dòng quét. 79
Đồ họa máy tính - Nếu số giao điểm tìm đƣợc giữa các cạnh đa giác và dòng quét là lẻ (điều này chỉ xảy ra khi dòng quét sẽ đi qua các đỉnh của đa giác) khi đó ta sẽ tính số điểm là 2 thì có thể tô không chính xác. Ngoài ra, việc tìm giao điểm của dòng quét với các cạnh nằm ngang là trƣờng hợp đặc biệt Hình 3.13 Giải thuật scanline cho một đa giác bất kỳ Để giải quyết các vấn đề trên ta có các phƣơng pháp sau: + Danh sách các cạnh kích hoạt (AET - Active Edge Table) Mỗi cạnh của đa giác đƣợc xây dựng từ 2 đỉnh kề nhau Pi(xi,yi) và Pi+1(xi+1,yi+1) gồm các thông tin sau: ymin: giá trị nhỏ nhất trong 2 đỉnh của cạnh xIntersect: hoành độ giao điểm của cạnh với dòng quét hiện đang xét DxPerScan: giá trị 1/m (m là hệ số góc của cạnh) DeltaY: khoảng cách từ dòng quét hiện hành tới đỉnh ymax Hình 3.14 Thông tin của một cạnh Danh sách các cạnh kích hoạt AET: danh sách này dùng để lƣu các tập cạnh của đa giác có thể cắt ứng với dòng quét hiện hành và tập các điểm giao tƣơng ứng. Nó có một số đặc điểm: Các cạnh trong danh sách đƣợc sắp xếp theo thứ tự tăng dần của các hoành độ giao điểm để có thể tô màu các đoạn giao một cách dễ dàng. 80
Đồ họa máy tính Thay đổi ứng với mỗi dòng quét đang xét, do đó danh sách này sẽ đƣợc cập nhật liên tục trong quá trình thực hiện thuật toán. Đầu tiên ta có danh sách chứa toàn bộ các cạnh của đa giác gọi là ET (Edge Table) đƣợc sắp xếp theo thứ tự tăng dần của ymin, rồi sau mỗi lần dòng quét thay đổi sẽ di chuyển các cạnh trong ET thoả điều kiện sang AET. Một dòng quét y = k chỉ cắt 1 cạnh của đa giác khi và chỉ khi k ≥ ymin và DeltaY >0. Chính vì vậy mà với các tổ chức của ET (sắp theo thứ tự tăng dần của ymin) điều kiện để chuyển các cạnh từ ET sang AET sẽ là k ≥ ymin; và điều kiện để loại một cạnh ra khỏi AET là DeltaY ≤0 + Công thức tìm giao điểm nhanh Nếu gọi xk, xk+1 lần lƣợt là các hoành độ giao điểm của một cạnh nào đó với các dòng quét y = k và y = k+1 ta có: xk+1 - xk = 1/m ((k+1) - k) = 1/m hay xk+1 = xk + 1/m Hình 3.15 Công thức tìm giao điểm nhanh Nhƣ vậy nếu lƣu hoành độ giao điểm ứng với dòng quét trƣớc lại, cùng với hệ số góc của cạnh, ta xác định đƣợc hoành độ giao điểm ứng với dòng quét kế tiếp theo công thức trên. Nên thông tin của cạnh có 2 biến: DxPerScan, xIntersect. + Trƣờng hợp dòng quét đi ngang qua một đỉnh: Tính 1 giao điểm nếu chiều của 2 cạnh kề của đỉnh đó có xu hƣớng tăng hay giảm Tính 2 giao điểm nếu chiều của 2 cạnh kề của đỉnh đó có xu hƣớng thay đổi, nghĩa là tăng-giảm hay giảm-tăng. Hình 3.16 Qui tắc tính một giao điểm (A) và hai giao điểm (B) 81