Chương 1 CÁC YẾU TỐ CƠ SỞ CỦA ĐỒ HỌA Trong chương này sẽ trình bày các khái niệm về điểm ảnh, tọa độ điểm ảnh và ma trận điểm ảnh trên thiết bị đồ họa. Trình bày các giải thuật giúp dựng hình một cách hiệu quả đối với các đối tượng cơ bản như đoạn thẳng, hình tròn, hình ellipse. CÁC KHÁI NIỆM CƠ BẢN 1. Thiết bị đồ họa và điểm ảnh Thiết bị đồ họa được hiểu là những phương tiện giúp chúng ta thể hiện được các hình ảnh thông qua sự điều khiển của máy tính.
Từ đó, chúng ta có thể liệt kê một số thiết bị quen thuộc như màn hình máy tính, máy in, máy vẽ,… Hình 1.1 cho thấy khả năng hiển thị sinh động hình vẽ, chữ, hình ảnh thu được từ camera trên một màn hình máy tính của hãng Dell. Để có thể điều khiển được quá trình hiển thị thông tin (hình vẽ, chữ viết, hình ảnh,…) trên thiết bị đồ họa, chúng ta cần hiểu được tính chất cấu tạo của chúng. Trong chương này, chúng ta cần tìm hiểu một số khái niệm cơ bản liên quan đến quá trình dựng hình. Giao diện đồ họa windows 8 thể hiện trên màn hình của hãng Dell 1 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Mỗi thiết bị đồ họa có một mặt phẳng (hai chiều) được phân chia thành các dòng (rows) và các cột (columns).
Giao của các dòng và các cột tạo nên các điểm ảnh, thuật ngữ tiếng Anh là Pixel. Kích thước của điểm ảnh phụ thuộc vào diện tích của bề mặt hiển thị và số điểm ảnh tối đa mà thiết bị điều khiển và hiện được trên bề mặt đó. Độ phân giải của thiết bị màn hình thường được biểu diễn bởi khả năng phân chia với số cột và số dòng cực đại. Ví dụ, màn hình LCD Full HD sẽ cho khả năng phân chia được 1920 cột và 1080 dòng, từ đó tạo nên hơn 2 triệu điểm ảnh.
Các cột và các dòng được đánh chỉ số bắt đầu từ 0 tại vị trí góc trên bên trái như minh họa trong Hình 1. Từ đó, mỗi điểm ảnh được định danh thông qua một cặp chỉ số (x,y), trong đó x và y lần lượt là chỉ số cột và chỉ số dòng tạo nên điểm ảnh, cặp chỉ số này còn được gọi là tọa độ điểm ảnh trên thiết bị đồ họa. Dễ thấy rằng, tọa độ điểm ảnh trên thiết bị đồ họa luôn luôn phải là một cặp số nguyên dương hoặc bằng không. Các cặp giá trị tọa độ thực (không nguyên) hoặc âm không được chấp nhận, vì nó không giúp hệ thống xác định được điểm ảnh cần điều khiển.
Minh họa việc hiển thị hình ảnh đồ họa trên thiết bị 1. Điểm và đoạn thẳng trong mặt phẳng Về mặt toán học, một đoạn thẳng bao gồm một tập vô hạn các điểm trong mặt phẳng với cặp tọa độ thực và không có kích thước (hay kích thước vô cùng bé). Khái niệm này có nhiều khác biệt với khái niệm Pixel trên thiết bị đồ họa mà người học cần nắm vững trước khi bắt đầu tìm hiểu bài toán dựng hình trong lĩnh vực đồ họa máy tính.2 2 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài chúng ta có thể hiểu rằng quá trình dựng hình trên thiết bị đồ họa chính là quá trình xác định một tập các điểm ảnh (pixel) sao cho chúng có thể thể hiện được hình ảnh mà chúng ta mong muốn ở mức tốt nhất (tối ưu nhất) có thể. Ví dụ, đoạn thẳng màu đen được thể hiện bằng một tập 6 pixel liên tiếp nhau như minh họa trong Hình 1.2, mỗi pixel có một kích thước cụ thể phụ thuộc vào kích thước và độ phân giải của thiết bị.
CÁC GIẢI THUẬT VẼ ĐOẠN THẲNG Phương trình tổng quát của một đường thẳng được viết dưới dạng: y ax b Trong đó: - a là hệ số góc hay còn gọi là độ dốc, nó phản ánh mối tương quan giữa 2 biến số x và y. - b là khoảng chắn trên trục hoành. Phương trình đường thẳng đi qua 2 điểm A(xa, ya) và B(xb, yb) được viết dưới dạng: y ya x xa (1.1) yb ya xb xa Trong đó xa ≠ xb và ya ≠ yb. (Khi xa = xb thì phương trình là x = xa, còn khi ya = yb thì phương trình là y = ya) Đặt x xb xa và y yb ya thì (1.1) trở thành y y y x xa ya x x y a y ax b với x (1.
Vẽ đoạn thẳng dựa vào phương trình Khi biết phương trình của một đường, chúng ta hoàn toàn có thể vẽ được đường biểu diễn nhờ vào các tính toán trên phương trình. Ở đây, 3 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài đường mà chúng ta cần biểu diễn là một đoạn thẳng AB với A(x a,ya) và B(xb,yb). Phương trình biểu diễn được cho bởi (1.2) với x xa, xb , y ya , yb Quy trình dựng hình có thể tóm tắt như sau: Nếu y x , nghĩa là biến số x biến thiên nhanh hơn biến số y, lúc này để đảm bảo tính liên tục của các điểm vẽ chúng ta cho biến số x thay đổi tuần tự và tính biến số y qua phương trình. Cụ thể như sau: Cho x nhận các giá trị nguyên lần lượt từ xa đến xb, với mỗi giá trị x chúng ta thực hiện: Tính y ax b thông qua phương trình.
Ở đây điểm trên đoạn thẳng có tọa độ là (x, y). Song chúng ta không thể vẽ điểm đó bởi giá trị y là một giá trị thực trong khi các hệ thống biểu diễn đồ họa chỉ có hữu hạn điểm và mỗi điểm có tọa độ nguyên. Từ đó chúng ta buộc phải minh họa cho điểm (x, y) thuộc đoạn thẳng thực bởi một điểm trên hệ thống thiết bị đồ họa gần với nó nhất, đó chính là điểm có tọa độ cột là x và dòng là giá trị làm tròn về số nguyên của y. Ngược lại, nghĩa là biến số y biến thiên nhanh hơn biến số x, lúc này để đảm bảo tính liên tục của các điểm vẽ chúng ta cho biến số y thay đổi tuần tự và tính biến số x qua phương trình.
Cụ thể như sau: Cho y nhận các giá trị nguyên lần lượt từ ya đến yb, với mỗi giá trị y chúng ta thực hiện: y b x x Tính x (hay x y ya xa ) a y y Vẽ điểm (round(x), y) Ví dụ: Cho A(5, 4) đến B(10, 7) để vẽ đoạn thẳng AB chúng ta thực hiện các bước sau: Tính: x xb xa 10 5 5; y yb ya 7 4 3 4 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài y 3 a x 5 b ax a y a 1 Vì y x , nên chúng ta cho x nhận các giá trị nguyên lần lượt từ xa đến xb, với mỗi giá trị x chúng ta cần thực hiện: Tính y ax b thông qua phương trình. Ảnh minh họa một đoạn thẳng từ A(5,4) đến B(10,7) Cụ thể như sau: Khi x = xa = 5: y = ax+b = 4; Vẽ điểm (5,4) Khi x = 6: y = 23/5 = 4.6; Vẽ điểm (6,5) Khi x = 7: y = 26/5 = 5.2; Vẽ điểm (7,5) Khi x = 8: y = 29/5 = 5.8; Vẽ điểm (8,6) Khi x = 9: y = 32/5 = 6.4; Vẽ điểm (9,6) Khi x = 10: y = 7; Vẽ điểm (10,7) Kết quả chúng ta có hình vẽ đoạn thẳng AB có thể minh họa như trong Hình 1. 5 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài 2. Vẽ đoạn thẳng dựa vào giải thuật Bresenham Mục 2.1 đã đưa ra quy trình để vẽ một đoạn thẳng AB bất kỳ trên thiết bị đồ họa.
Tuy nhiên, phương pháp tính toán còn chưa thật sự hiệu quả. Cụ thể, tại mỗi bước lặp để tìm ra được tọa độ của một điểm vẽ, chúng ta cần phải tính 1 phép nhân và 1 phép cộng trên trường số thực, cùng với một phép tính làm tròn (round) số thực về số nguyên. Cũng với cách tiếp cận trên, song giải thuật Bresenham hướng tới một sự phân tích bài toán sâu sắc hơn để đi đến một quy trình ít tính toán hơn. Giả thiết đầu tiên mà giải thuật Bresenham đặt ra là hệ số góc của đoạn thẳng a [0, 1] , các trường hợp còn lại của hệ số góc như a (1, ); a [1, 0) ; hay a ( ; 1) có thể được quy về trường hợp đoạn thẳng có hệ số góc a [0, 1] thông qua các phép lấy đối xứng, quy trình xử lý cụ thể đối với các đoạn thẳng có hệ số góc a [0, 1] sẽ được bàn thảo và hướng dẫn tại mục 2.
Từ giả thiết đặt ra là hệ số góc của đoạn thẳng a [0, 1] , chúng ta có thể suy ra rằng, trên toàn bộ đoạn thẳng tham số x luôn luôn biến thiên nhanh hơn tham số y. Từ đó, đưa đến quy trình: Cho x nhận các giá trị nguyên lần lượt từ xa đến xb, với mỗi giá trị x chúng ta cần phải tìm ra một giá trị y nguyên để (x,y) chính là tọa độ của điểm cần minh họa trên thiết bị. Và điểm mấu chốt ở đây là việc tìm ra giá trị y phải thông qua ít phép tính toán hơn quy trình đã trình bày ở mục 2. Giả thiết với hai điểm đầu mút A(xa, ya) và B(xb, yb) có tọa độ nguyên và xa < xb (nếu cần thì hoán đổi hai đầu mút A và B để thỏa mãn giải thiết xa < xb ).
Rõ ràng, điểm ảnh đầu tiên cần biểu diễn trên thiết bị chính là điểm A có tọa độ (xa, ya). Nếu gọi điểm ảnh được lựa chọn đầu tiên trong quy trình là (x0, y0) thì: (x0, y0) = (xa, ya) Theo lập luận quy nạp: Giả thiết rằng đến bước thứ i chúng ta đã chọn được điểm ảnh thứ i, hay nói cách khác là điểm ảnh được chọn ở bước thứ i với tên gọi là (xi, yi) đã được xác định giá trị. 6 Chương 1 - Các yếu tố cơ sở của đồ họa Nguyễn Hữu Tài Vậy đến bước tiếp theo, bước thứ i+1, chúng ta sẽ chọn điểm ảnh nào? Nói cách khác là điểm ảnh được chọn ở bước thứ (i+1) với tên gọi (xi+1, yi+1) sẽ được xác định các giá trị ra sao?