phương pháp đường quét (Scan-Line Method)

Phương pháp không gian ảnh để khử các mặt bị che khuất này là sự mở rộng của thuật toán scan-line để tô phần bên trong của một đa giác. Thay vì chỉ tô một mặt, bây giờ chúng ta xử lý với nhiều mặt. Khi mỗi đường quét được xử lý, tất cả các mặt đa giác cắt đường quét đó sẽ được kiểm tra để xác định xem mặt nào nhìn thấy được. Ở mỗi vị trí trên cùng đường quét các tính toán độ sâu được thực hiện cho mỗi mặt để xác định mặt gần mặt phẳng quan sát nhất. Khi mặt mặt nhìn thấy được được xác định, giá trị độ sáng cho vị trí đó được nhập vào vùng đệm làm tươi (refresh buffer).

Một đa giác trong không gian ba chiều được cài đặt có thể bao gồm cả hai bảng: bảng các cạnh (edge table) và bảng đa giác (polygon table), tương tự như trong hình 7-23 ở cuối chương này. Bảng các cạnh (edge table) chứa tọa độ các đỉnh đầu mút của mỗi cạnh, đảo hệ số góc của mỗi đường thẳng qua cạnh, và các chỉ diểm (pointer) đến bảng đa giác để xác định mặt nào chứa mỗi cạnh. Bảng đa giác chứa các hệ số của phương trình mỗi mặt, thông tin về độ sáng cho các mặt, và có thể chỉ đến bảng các cạnh.

Để dễ dàng nghiên cứu các mặt cắt một đường quét được cho, chúng ta cài đặt một danh sách động chứa các cạnh lấy thông tin trong bảng cạnh. Danh sách động này sẽ chỉ chứa các cạnh cắt đường quét hiện hành, được sắp xếp theo thứ thự x tăng. Và, chúng ta định nghĩa một cờ (flag) cho mỗi mặt, cờ này được đặt là on hay off để chỉ ra mỗi vị trí nằm dọc trên đường quét là nằm trong hay nằm ngoài mặt. Các đường quét được xử lý từ trái sang phải. Ở biên bên trái nhất của một mặt, cờ của mặt là on; và ở biên bên phải nhất cờ là off.

Hình 7-6 minh họa phương pháp scan-line để xác định vị trí các phần nhìn thấy được dọc theo một đường quét. Danh sách động cho đường quét 1 (scan line 1) lấy thông tin từ bảng các cạnh đối với các cạnh AB, BC, HE, và FG. Đối với các vị trí dọc theo đường quét này giữa các cạnh AB và BC, chỉ cờ mặt S₁ là on. Do đó, không phép tính độ sâu nào là cần thiết, và thông tin độ sáng của mặt S₁ được lấy từ bảng đa giác để nhập vào vùng làm tươi. Tương tự, các cạnh HE và FG, chỉ cờ cho mặt S₂ là on. Không vị trí nào khác dọc theo đường quét 1 cắt các mặt, vì vậy các giá trị độ sáng trong các vùng khác được đặt là độ sáng nền.Độ sáng nền có thể được nạp vào trong vùng đệm trong một thủ tục khởi tạo.

Danh sách động cho đường quét 2 và 3 trong hình 7-6 chứa các cạnh DA, HE, BC, và FG. Dọc theo đường quét 2 từ cạnh DA đến cạnh EH, chỉ cờ của mặt S₁ là on. Nhưng giữa HE và BC, các cờ cho cả hai mặt là on. Trong đoạn này, các tính toán độ về độ sâu phải được thực hiện bằng cách dùng tham số mặt của các mặt. Trong ví dụ này, độ sâu của mặt S₁ được được giả thiết là nhỏ hơn của mặt S₂, vì vậy độ sáng của mặt S₁ được nạp vào trong vùng đệm làm tươi đến khi biên BC được gặp. Sau đó cờ của mặt S₁ trở thành off, và độ sáng của mặt S₂ được lưu cho đến cạnh FG được đi qua.

Chúng ta có thể tận dụng các thuận lợi có được từ quan hệ cố kết dọc theo các đường quét khi chúng ta đi từ đường này đến đường kế tiếp. Trong hình 7-6, đường quét 3 có danh sách động giống như của dòng 2. Bởi vì không có thay đổi nào xảy ra tại các giao điểm đường, ta không cần tính lại độ sâu giữa các cạnh HE và BC. Hai mặt phải có hướng tương tự như được xác định trên đường quét 2, vì vậy độ sáng cho mặt S₁ không cần nhập lại.

Dù có bao nhiêu mặt được xếp chồng lên nhau, ta cũng có thể dùng phương pháp scan-line này. Các cờ cho các mặt được đặt để chỉ rõ xem một vị trí là bên trong hay bên ngoài, và các tính toán về độ sâu được thực hiện khi các mặt xếp chồng lên nhau. Trong vài trường hợp, các mặt có thể che khuất nhau một cách luân phiên (xem hình 7-7). Khi các phương pháp cố kết được dùng, ta cần cẩn thận để lưu vết phần nào của mặt là thấy được trên mỗi đường quét. Một cách để xử lý trường hợp này là phân chia các mặt. Cụ thể, mặt ABC trong hình 7-8 có thể được chia làm ba mặt ABED, DEGF, và CFG. Mỗi mặt nhỏ có thể được xét như một mặt riêng biệt, để mà không có hai mặt nào là bị che khuất và nhìn thấy một cách luân phiên.