Bài giảng Đồ họa máy tính: Xác định mặt hiện

12/10/2007Bùi Thế Duy - Bộ môn KHMT 1 Đồ họa máy tính Xác định mặt hiện (Visible surface determination) 12/10/2007Bùi Thế Duy - Bộ môn KHMT 2 Loại bỏ mặt ẩn z Với sự phát triển của các thiết bị hiển thị dẫn đến nhu cầu thể hiện các vật thể một cách thực tế hơn, đòi hỏi các mô hình có rất nhiều đa giác. z Từ đó dẫn đến nhu cầu phát triển các thuật toán để loại bỏ mặt ẩn (hidden surface removal). z Một số thuật toán được gọi chính xác hơn là các thuật toán mặt hiện (visible surface algorithms), but tuy nhiên cả hai tên đều được dùng thay nhau. 12/10/2007Bùi Thế Duy - Bộ môn KHMT 3 Sự hữu hình của các đối tượng cơ bản z Chúng ta không muốn phí thời gian để hiển thị những đối tượng không đóng góp vào bức ảnh cuối cùng. z Một đối tượng có thể không hữu hình vì 3 lý do: – Nằm ngoài vùng hiển thị – Quay vào trong (back-facing) – Bị che bởi các đối tượng khác gần người quan sát hơn z Làm thế nào để loại bỏ chúng một cách hiệu quả? z Làm thế nào để xác định chúng một cách hiệu quả? 12/10/2007Bùi Thế Duy - Bộ môn KHMT 4 Vấn đề hữu hình Hai vấn đề còn lại: (Chúng ta đã làm quen với clipping) • Loại bỏ các bề mặt hướng ra phía khác so với người quan sát. • Loại bỏ các bề mặt che bởi các đối tượng gần hơn. 12/10/2007Bùi Thế Duy - Bộ môn KHMT 5 Các thuật toán mặt hiện Loại bỏ/Xác định Mặt/đoạn Ẩn/hiện z Yêu cầu – Có thể xử lý các tập đối tượng khác nhau – Có thể xử lý một lượng lớn các đại lượng hình học Phân loại: Sutherland, Sproull, Schumacher (1974): z Không gian vật thể – Tính toán hình học liên quan đến đa giác – Độ chính xác số thực – Thường xử lý cảnh vật theo thứ tự các vật thể z Không gian ảnh – Visibility at pixel samples – Độ chính xác số nguyên – Thường xử lý cảnh vật theo thứ tự ảnh 12/10/2007Bùi Thế Duy - Bộ môn KHMT 6 Xác định mặt sau z Chúng ta thường thấy trong mô hình hóa, các đỉnh của một đa giác thường được tính theo chiều ngược theo chiều kim đồng hồ khi nhìn vào từ bên ngoài – vec- tơ pháp tuyến N trỏ ra ngoài. z Kiểm tra thành phần z của vec-tơ pháp tuyến. Nếu âm – quay vào trong. 12/10/2007Bùi Thế Duy - Bộ môn KHMT 7 Xử lý sự chồng chéo? Làm thế nào để vẽ các đa giác theo đúng thứ tự để có được kết quả đúng? Có phải đây chỉ là vấn đề sắp xếp? Chỉ đúng với 2D, tuy nhiên trong 3D các đa giác chồng chéo lên nhau có thể tạo thành một thứ tự vòng tròn, không sắp xếp được. 12/10/2007Bùi Thế Duy - Bộ môn KHMT 8 Thuật toán Z-buffering z Rất đơn giản, có thể ghép vào thuật toán đường quét. z Nội suy z trong quá trình tính toán. z Lưu trữ một ma trận độ sâu tương ứng với ảnh đầu ra. z Mỗi khi xử lý một đa giác, so sánh với các giá trị z đang lưu trữ. z Lưu lại giá trị màu của những điểm gần nhất. 12/10/2007Bùi Thế Duy - Bộ môn KHMT 9 Cài đặt z Khởi tạo bộ đệm ảnh với màu nền. z Khởi tạo bộ đệm độ sâu với z = giá trị max. của mặt phẳng clipping. z Cần tính giá trị z cho mỗi điểm – Bằng cách nội suy từ các đỉnh đa giác. z Cập nhật cả bộ đệm ảnh và bộ đệm độ sâu. 12/10/2007Bùi Thế Duy - Bộ môn KHMT 10 Tại sao thuật toán z-buffering lại thông dụng? Lợi điểm z Dễ dàng cài đặt trên phần cứng. – Kết hợp với thuật toán đường quét. – Bộ nhớ cho z-buffer không quá đắt z Xử lý được nhiều loại đối tượng hình học – không chỉ đa giác. z Có thể xử lý cảnh vật phức tạp đến bất cứ mức nào z Không cần tính toán phần giao giữa các đối tượng. Nhược điểm z Tốn thêm bộ nhớ và băng thông z Tốn thời gian tính toán những đối tượng ẩn 12/10/2007Bùi Thế Duy - Bộ môn KHMT 11 Thuật toán Painters (không gian vật thể) z Vẽ các bề mặt theo thứ tự từ sau đến trước – các đa giác gần hơn sẽ được vẽ đề lên đa giác xa hơn. z Hỗ trợ tính trong suốt. z Vấn đề mấu chốt là xác định thứ tự. z Không phai lúc nào cũng thực hiện được. 12/10/2007Bùi Thế Duy - Bộ môn KHMT 12 Cây BSP (Binary Space Partitioning) •Trả về thứ tự vẽ. •Chọn đa giác bất kỳ •Chia cảnh vật ra 2 nửa không gian: trước và sau. •Chia những đa giác nằm ở cả hai nửa không gian. •Chọn một đa giác ở mỗi nửa – chia đôi cảnh vật tiếp. •Tiếp tục chia cho đến khi mỗi phần chỉ còn một đa giác. 3 41 2 5 View of scene from above 12/10/2007Bùi Thế Duy - Bộ môn KHMT 13 Cây BSP 3 3 41 2 5 5a 5b 1 2 5a 4 5b sauTrước Chọn đa giác bất kỳ Chia cảnh vật ra 2 nửa không gian: trước và sau. Chia những đa giác nằm ở cả hai nửa không gian. Chọn một đa giác ở mỗi nửa – chia đôi cảnh vật tiếp. Tiếp tục chia cho đến khi mỗi phần chỉ còn một đa giác. 12/10/2007Bùi Thế Duy - Bộ môn KHMT 14 Cây BSP 3 3 41 2 5 5a 5b 4 5b Trước 2 15a Trước Chọn đa giác bất kỳ Chia cảnh vật ra 2 nửa không gian: trước và sau. Chia những đa giác nằm ở cả hai nửa không gian. Chọn một đa giác ở mỗi nửa – chia đôi cảnh vật tiếp. Tiếp tục chia cho đến khi mỗi phần chỉ còn một đa giác. sau 12/10/2007Bùi Thế Duy - Bộ môn KHMT 15 Cây BSP 3 3 41 2 5 5a 5b sauTrước 2 15a Trước 5b 4 Chọn đa giác bất kỳ Chia cảnh vật ra 2 nửa không gian: trước và sau. Chia những đa giác nằm ở cả hai nửa không gian. Chọn một đa giác ở mỗi nửa – chia đôi cảnh vật tiếp. Tiếp tục chia cho đến khi mỗi phần chỉ còn một đa giác. 12/10/2007Bùi Thế Duy - Bộ môn KHMT 16 Cây BSP 3 3 41 2 5 sau 2 1 Trước 5 4 sau sau Chọn đa giác bất kỳ Chia cảnh vật ra 2 nửa không gian: trước và sau. Chia những đa giác nằm ở cả hai nửa không gian. Chọn một đa giác ở mỗi nửa – chia đôi cảnh vật tiếp. Tiếp tục chia cho đến khi mỗi phần chỉ còn một đa giác. Cây khác 12/10/2007Bùi Thế Duy - Bộ môn KHMT 17 Hiện thị cây BSP z Once we have the regions – need priority list z BSP tree can be traversed to yield a correct priority list for an arbitrary viewpoint. z Start at root polygon. – If viewer is in front half-space, draw polygons behind root first, then the root polygon, then polygons in front. – If polygon is on edge – either can be used. – Recursively descend the tree. z If eye is in rear half-space for a polygon – then can back face cull. 12/10/2007Bùi Thế Duy - Bộ môn KHMT 18 Cây Tree. z Cần một lượng lớn tính toán khi bắt đầu – Chia đa giác z Nhanh chóng để xác định tính hữu hình khi cây được tạo ra. z Có thể được sử dụng để tính toán sự hữu hình chính xác cho bất kỳ cảnh vật nào. ⇒ Hiệu quả khi các vật thể không thay đổi trong cảnh vật. 12/10/2007Bùi Thế Duy - Bộ môn KHMT 19 Thuật toán Warnock z Lai giữa không gian vật thể và không gian ảnh. z Sử dụng giải pháp đồ họa chuẩn:- nếu tình huống phức tạp quá, thì chia nhỏ bài toán ra. z Bắt đầu với một cửa sổ gốc: – Nếu không có hay chỉ có một đa giác giao với cửa sổ, quét đa giác đó – Nếu không thì chia cửa sổ ra làm bốn – Tiếp tục như vậy cho đến khi chỉ có một hoặc không có đa giác nào giao với cửa sổ, hoặc đạt đến độ sâu nào đó – Độ sâu có thể là độ phân giải điểm, Hiển thị đa giác gần nhất 12/10/2007Bùi Thế Duy - Bộ môn KHMT 20 Ví dụ về thuật toán Warnock 12/10/2007Bùi Thế Duy - Bộ môn KHMT 21 Hiệu năng của thuật toán Warnock z Chia không gian màn hình (độ phân giải màn hình, r = w*h), thuật toán lai giữa không gian vật thể và không gian ảnh, tốt với một số lượng nhỏ đối tượng, chính xác. z Bộ nhớ làm việc: O(n) z Bộ nhớ lưu trữ: O(n lg r) z Thời gian để xác định tính hữu hình : O(n*r) z Vẽ thừa: không 12/10/2007Bùi Thế Duy - Bộ môn KHMT 22 Hiệu năng của thuật toán BSP z Xây dựng cây và duyệt cây (thuật toán thứ tự trong không gian vật thể – tốt với một số lượng nhỏ các đối tượng, chính xác) z Bộ nhớ làm việc: O(1), O(lg n) z Bộ nhớ lưu trữ: O(n2) z Thời gian để xác định tính hữu hình: O(n2) z Vẽ thừa: không 12/10/2007Bùi Thế Duy - Bộ môn KHMT 23 Hiệu suất của Z-buffer z Brute-force image-space algorithm scores best for complex scenes – not very accurate but is easy to implement and is very general. z Bộ nhớ làm việc: O(1) z Bộ nhớ lưu trữ: O(1) z Thời gian để xác định tính hữu hình: O(n) z Vẽ thừa: tối đa 12/10/2007Bùi Thế Duy - Bộ môn KHMT 24 Ví dụ. Cảnh kiến trúc Một lượng lớn đối tượng bị che khuất 12/10/2007Bùi Thế Duy - Bộ môn KHMT 25 Sự che khuất ở các mức độ khác nhau 12/10/2007Bùi Thế Duy - Bộ môn KHMT 26 Tổng kết z Xác định mặt quay vào trong z Thuật toán z-buffer z Thuật toán BSP z Thuật toán Warnock