Giáo trình Đồ họa trong Pascal - Chương 1: Màn hình của máy tính - Bài 14: Xác định đường khuất mặt khuất

$14. Xác định đường khuất mặt khuất
Để có thể tạo ra ảnh nổi trong không gian 3 chiều người ta phải bỏ đi các mặt khuất đường khuất hoặc dựa vào màu sắc để tạo nên độ sáng tối khác nhau, điều này dẫn đến bài toán xác định mặt khuất đường khuất trong kỹ thuật đồ hoạ
1. Xác định phía trước phía sau của một mặt
Giả sử cho một vật thể trong không gian 3D được giới hạn bởi các mặt là các đa giác 
Một mặt giới hạn cùng vật thể là phần giới hạn của mặt phẳng chứa đa giác đó giả sử mặt phẳng có phương trình: 
ax+by+cz+d=0 (*)
Mặt phẳng (*) chia không gian thành hai phần. Chúng ta quy ước tất cả các điểm (x,y,z) mà ax+by+cz+d <0 là phía sau của mặt và tập các điểm (x,y,z) mà ax+by+cz+d =0 là phần phía trước của mặt 
Với các quy định trên thì vật thể là tập hợp tất cả các điểm thuộc phần phía sau của tất cả các mặt tạo nên vật thể
Từ đây ta cũng suy ra những điểm nằm về phía sau của tất cả các mặt tạo nên phần bên trong vật thể, phần còn lại của không gian là phần bên ngoài vật thể, suy ra người quan sát có thể nhìn thấy vật thể khi người đó ở phía ngoài vật thể
Giả sử vật thể 3D được cho bởi danh sách các mặt và mỗi mặt là danh sách các cạnh hoặc các đỉnh. Mỗi mặt là một đa giác lồi. Ta giả sử các cạnh được đánh số theo chiều ngược chiều kim đồng hồ.
Gọi là véctơ pháp tuyến của mặt ABCD ngược với hướng nhìn từ bên ngoài
Giả sử người quan sát ở vị trí nhìn vào vật thể. Lấy một điểm P bất kỳ trên mặt Si của vật thể khi đó vectơ tạo nên hướng nhìn của người quan sát đối với mặt Si
Xét tích các hướng khi đó nếu góc thì mặt Si chứa điểm P bị che khuất khi đó các cạnh tạo nên mặt bị che khuất không nhìn thấy, nó tạo nên các đường khuất. Ngược lại nếu thì người quan sát nhìn thấy mặt Si và do đó các cạnh tạo nên mặt Si không bị che khuất
Chú ý: 
1. Chúng ta chú ý rằng nếu mặt phẳng song song với hướng nhìn thì hình ảnh của mặt trên mặt phẳng chiếu là một đoạn thẳng
2. Việc xác định các đường khuất mặt khuất dựa theo nguyên tắc trên đối với các vật thể có hình dạng tuỳ ý là rất phức tạp vì các cạnh có thể bị che khuất một phần do các mặt khác mà không phải bị che khuất toàn bộ. Nguyên tắc trên chỉ thích hợp với các vật thể đơn giản
2. Thuật toán mô tả vật thể theo độ sâu
(Depth buffer Method)
Bây giờ chúng ta khảo sát một thuật toán khác - gọi là thuật toán mô tả vật thể theo độ sâu, ý tưởng của thuật toán rất đơn giản là dựa vào khoảng cách giữa mỗi điểm trên vật thể với vị trí người quan sát để tô màu sáng tối khác nhau
Ưu điểm của phương pháp này là vật thể có thể có hình dạng bất kỳ không nhất thiết là đa diện, dễ ứng dụng, dễ hiểu
Bài toán như sau : 
Giả sử cho vật thể V được giới hạn bởi các mặt S1,S2...... Sm, các điểm (i,j) thuộc mặt Sk của vật thể được tô bởi màu f(k,i,j) (k=1,m) (để đơn giản ta có thể giả thiết các điểm của mỗi mặt Sk được tô cùng một màu fk). Giả sử người quan sát ở vị trí và nhìn vật thể theo hướng OZ
Thuật toán mô tả vật thể theo độ sâu được thể hiện như sau:
Ta sử dụng hai mảng : một mảng gọi là mảng depth(i,j) dùng để chứa độ sâu theo hướng OZ của điểm (i,j) nào đó, mảng thứ hai là mảng có tên gọi color(i,j) dùng để chứa màu cần tô của điểm (i,j)
Thuật toán:
1. Với mỗi điểm (i,j) thuộc hình chữ nhật bao vật thể ta đặt
	depth(i,j):=0; color(i,j):=
2. For (mỗi điểm (i,j) thuộc hình chữ nhật bao vật thể) Do
 Begin
	For k:=1 To m Do
	Begin
	 If (điểm (i,j) thuộc mặt Sk) Then
	 Begin
	Tính độ sâu của điểm (i,j) thuộc Sk : z:=(-aki-bkj-dk)/ck
	If (z<depth(i,j)) Then
	Begin
	depth(i,j):=z; color(i,j):=f(k,i,j);
	End;
	 End;
	End;
 End;
3. Với mỗi điểm (i,j) thuộc hình chữ nhật bao vật thể
	vẽ điểm (i,j) bằng màu color(i,j);
4. Kết thúc
Ưu điểm của thuật toán này như trên đã nêu đơn giản, dễ áp dụng cho mọi đối tượng. Nhiều lúc nó còn có ưu điểm lớn hơn là với vật thể phức tạp, số mặt tăng lên số phép tính không tăng. Nhược điểm lớn nhất là kích thước của 2 mảng tăng nhanh khi độ phân giải của màn hình tăng
Chú ý: Nếu các mặt của vật thể là các đa giác nghĩa là một phần của mặt phẳng: ax+by+cz+d=0
khi đó việc tính độ sâu z được tính theo công thức:
3. Thuật toán xác định vật thể theo đường quét
Phương pháp này còn có tên gọi là thuật toán scan-line
ý tưởng của thuật toán như sau:
Giả sử cho vật thể V trong không gian 3D. Người quan sát ở vị trí E nhìn vật thể V theo hướng OZ khi đó ta thực hiện các bước sau:
1. Chiếu vật thể V theo hướng OZ lên mặt phẳng chiếu XOY. Giả sử S1,S2......Sm tương ứng là hình chiếu của các mặt V1,V2.....Vm của vật thể V
2. Giả sử hình chiếu của vật thể được bao bởi hình chữ nhật
(xmin , xmax) x (ymin , ymax)
For i:= ymin To ymax Do
Begin
 Kẻ đường thẳng y= i (song song với OX)
 Gọi x1<= x2 <= ... <= xm là hoànhđộ của các giao điểm 
 của tia quét với biên của các mặt hình chiếu
 For j:=1 To m-1 Do
 Begin
	xét đoạn thẳng xjxj+1
	If (xjxj+1 chỉ thuộc 1 mặt) Then (tô màu xjxj+1 theo mặt đó) 
	Else
	Begin
	 	Tại mỗi điểm trên đoạn xác định độ sâu của điểm 
	theo từng mặt để chọn được mặt gần nhất và
	tô màu của điểm theo mặt đó
	End;
 End;	
End;
Chú ý:
Phương pháp này thực chất là cải tiến của phương pháp độ sâu ở trên với cách này có thể làm giảm kích thước của mảng độ sâu và mảng màu trong thuật toán độ sâu.