Đồ họa 3D - Các thuật toán khử mặt khuất

ĐỒ HỌA 3D
CÁC THUẬT TOÁN KHỬ
MẶT KHUẤT
Giảng viên : Bùi Tiến Lên
Bài toán
Input : Danh sách các mặt đa giác {f0, f1, ... , fn-1} (trong 
hệ tọa độ quan sát)
Trang 2
Bài toán
Output :
Trang 3
Một số phương pháp
-Thuật toán loại bỏ mặt sau
-Thuật toán depth sorting
-Thuật toán z-buffer
-Thuật toán Scanline
-Thuật toán Warnock
-Thuật toán BSP
Trang 4
-Thuật toán Ray casting
Thuật toán loại bỏ mặt sau
Mặt trước
Trang 6
Mặt sau
Trang 7
Thuật toán
Duyệt tuần tự các mặt đa giác trong danh sách.
Xét đa giác f
bước 1 Xác định v
bước 2 Tính v.n
bước 3 Xét giá trị v.n
-≥0 loại bỏ mặt đa giác f
Trang 8
-<0 giữ lại mặt đa giác f
n
v
mặt đa giác
Ví dụ
Trang 9
Ví dụ
Trang 10
Áp dụng
Trang 11
Áp dụng
Trang 12
Lưu ý
Trang 13
Thuật toán depth sorting
Độ sâu là gì ?
Điểm : độ sâu p = -pz
Đa giác : độ sâu f = min{độ sâu p0, ... , độ sâu pn-1}
Trang 15
Thuật toán
bước 1 Sắp xếp các mặt đa giác trong danh sách 
theo thứ tự độ sâu tăng dần.
bước 2 Vẽ các mặt đa giác theo thứ tự đã sắp xếp.
Trang 16
Ví dụ
1
3
Trang 17
2
Ví dụ
Trang 18
Lưu ý
Trang 19
Thuật toán z-buffer
Thuật toán
Khởi động z-buffer
Duyệt tuần tự các mặt đa giác
Nếu độ sâu trên mặt đa giác nhỏ hơn độ sâu tương ứng 
đang trong lưu trong buffer thì cập nhật lại z-buffer và 
color-buffer
Trang 21
Ví dụ
1
2
Trang 22
3
Duyệt đa giác 1
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞
6 6 6 6
6 6 6 6
6 6 6 6
6 6 6 6
∞ 6 6 6 6 ∞
∞ 6 6 6 6 ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ 6 6 6 6 ∞
∞ 6 6 6 6 ∞
Trang 23
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
Duyệt đa giác 2
4 4
4
4 4 4
∞ 4 4 6 6 ∞
∞ 4 6 6 6 ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ 4 4 4 6 ∞
∞ 6 6 6 6 ∞
∞ 6 6 6 6 ∞
∞ 6 6 6 6 ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ 6 6 6 6 ∞
∞ 6 6 6 6 ∞
Trang 24
∞ ∞ ∞ ∞ ∞ ∞∞ ∞ ∞ ∞ ∞ ∞
Duyệt đa giác 3
5
5 5
∞ 4 4 6 6 ∞
∞ 4 6 6 6 ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ 4 4 4 6 ∞
∞ 5 5 6 6 ∞
∞ 4 4 6 6 ∞
∞ 4 6 6 6 ∞
∞ ∞ ∞ ∞ ∞ ∞
∞ 4 4 4 6 ∞
∞ 6 6 6 6 ∞
Trang 25
∞ ∞ ∞ ∞ ∞ ∞∞ ∞ ∞ ∞ ∞ ∞
Trang 26
Thuật toán Scanline
Thuật toán Scanline
Trang 28
Thuật toán Warnock
Thuật toán Warnock
Trang 30
Thuật toán BSP
Thuật toán BSP
Trang 32
Thuật toán Ray Casting