Khử các mặt khuất và đường khuất

• Mục tiêu

  Học xong chương này sinh viên cần phải nắm bắt được các vấn đề sau:

  • Việc tạo ra các hình ảnh thực là sự xác định và xóa bỏ các phần của ảnh mà ta không nhìn thấy được từ một vị trí quan sát.
  • Nắm vững các tiếp cận khử mặt khuất và đường khuất.
• Kiến thức cơ bản

  Kiến thức toán học : kiến thức cơ bản về cách vẽ hình trong hình học không gian

  Kiến thức tin học : kỹ thuật lập trình và cấu trúc dữ liệu.

• Tài liệu tham khảo

  Computer Graphics . Donald Hearn, M. Pauline Baker. Prentice-Hall, Inc., Englewood Cliffs, New Jersey , 1986 (chapters 13, 260-284)

• Nội dung cốt lõi

  Các tiếp cận khử các mặt khuất, đường khuất bao gồm :

  • Phương pháp dùng vùng đệm độ sâu
  • Phương pháp đường quét
  • Phương pháp sắp xếp theo độ sâu
  • Phương pháp phân chia vùng

Một vấn đề lớn cần được quan tâm đến trong việc tạo ra các hình ảnh thực là sự xác định và xóa bỏ các phần của bức ảnh mà ta không nhìn thấy được từ một vị trí quan sát.

Có nhiều tiếp cận chúng ta cần để giải quyết vấn đề này, và cũng có nhiều thuật toán khác nhau đã và đang được phát triển để xóa bỏ các phần bị che khuất một cách hiệu quả cho những loại ứng dụng khác nhau. Vài phương pháp đòi hỏi nhiều bộ nhớ hơn, một vài cần nhiều thời gian xử lý hơn, một số khác lại chỉ áp dụng được cho những kiểu đối tượng đặc biệt. Phương pháp nào được chọn cho một ứng dụng cụ thể dựa vào các nhân tố như độ phức tạp của ảnh, kiểu đối tượng được hiển thị, các thiết bị hiện có, và các hình ảnh cần hiển thị là tĩnh hay động. Trong chương này, chúng ta khảo sát tỉ mỉ một vài trong số các phương pháp được dùng biến nhất để xóa bỏ các đường khuất và mặt khuất.

Một tiếp cận không gian ảnh được dùng phổ biến để khử mặt khuất là phương pháp vùng đệm độ sâu, còn được gọi là phương pháp z-buffer. Một cách cơ bản, thuật toán này kiểm tra tính nhìn thấy được của các mặt mỗi lần một điểm. Với mỗi vị trí pixel (x,y) trên mặt phẳng quan sát, mặt nào có giá trị tọa độ z nhỏ nhất ở vị trí pixel đó thì nhìn thấy được. Hình 4 trình bày ba mặt có độ sâu khác nhau, với sự quan tâm đến vị trí (x, y) trong hệ quan sát bàn tay trái. Mặt S1 có giá trị z nhỏ nhất ở vị trí này vì vậy giá trị độ sáng ở (x, y) được lưu.

Hai vùng đệm được cần để cài đặt phương pháp này. Một vùng đệm độ sâu (depth buffer) được dùng để lưu trữ các giá trị z cho mỗi vị trí (x, y) của các mặt được so sánh. Vùng đệm thứ hai là vùng đệm làm tươi (refresh buffer) (hay còn gọi là vùng đệm khung), lưu giữ các giá trị độ sáng cho mỗi vị trí (x, y).

Phương pháp này có thể được thực hiện hiệu quả trong các hệ tọa độ chuẩn, với các giá trị độ sâu thay đổi từ 0 đến 1. Giả sử rằng một không gian chiếu (projection volume) được ánh xạ vào một không gian quan sát hình hộp chuẩn, ánh xạ của mỗi mặt lên mặt phẳng quan sát là một phép chiếu trực giao. Độ sâu của các điểm trên bề mặt của một đa giác được tính từ phương trình mặt phẳng. Ban đầu, tất cả các vị trí trong vùng đệm độ sâu được đặt giá trị 1 (độ sâu lớn nhất), và vùng đệm làm tươi được khởi tạo giá trị của độ sáng nền. Mỗi mặt (đã được lập danh sách trong các bảng đa giác (polygon tables)) sau đó được xử lý. Mỗi lần một đường quét (scane line), tính độ sâu, hoặc giá trị z, ở mỗi vị trí (x, y). Giá trị z vừa được tính xong sẽ được so sánh với các giá trị lưu trữ trước đó trong vùng đệm độ sâu ở vị trí đó. Nếu giá trị z vừa được tính xong nhỏ hơn các giá trị trước đó, giá trị z mới sẽ được lưu, và độ sáng của mặt ở vị trí đó cũng được cập nhật lại vào vị trí tương ứng trong vùng đệm làm tươi

Ở ví trí (x, y), mặt S1 có giá độ sâu nhỏ nhất và vì thế được nhìn thấy ở ví trí đó

Chúng ta có thể tổng kết các bước của thuật toán vùng đệm độ sâu như sau:

1. Khởi tạo vùng đệm độ sâu và vùng đệm làm tươi để với tất cả các vị trí(x,y), depth(x, y)=1 và refresh(x,y)= background.

2. Đối với mỗi vị trí trên mỗi mặt, so sánh các giá trị độ sâu với các giá trị độ sâu được lưu trước đó trong vùng đệm độ sâu để xác định tính chất nhìn thấy được.

a. Tính giá trị z cho mỗi vị trí (x, y) trên mặt.

b. Nếu z<depth(x,y)thì đặt lại depth(x,y)=zvà refresh(x,y)=i, với i là giá trị độ sáng trên mặt ở vị trí (x, y).

Trong bước cuối cùng, nếu z không nhỏ hơn giá trị trong vùng đệm độ sâu ở vị trí đó, điểm không được nhìn thấy. Khi quá trình này được hoàn thành cho tất cả các mặt, vùng đệm độ sâu chứa các giá trị z của các mặt nhìn thấy được và vùng đệm làm tươi chỉ chứa các giá trị độ sáng của các mặt nhìn thấy được đó.

Các giá trị độ sâu cho một vị trí (x, y) được tính từ phương trình của mỗi mặt:

(3)

Với mỗi đường quét bất kỳ (xem hình 5), các tọa độ x trên cùng đường quét sai khác nhau 1, và các giá trị y giữa hai đường quét cũng sai khác nhau 1. Nếu độ sâu của vị trí (x,y) được xác định là z, khi đó độ sâu z’ của vị trí kế tiếp (x+1, y) dọc theo theo đường quét có được từ phương trình 3 như sau:

hoặc

(4)

Từ vị trí (x, y) trên một đường quét, vị trí kế tiếp qua phải có tọa độ (x+1, y), và vị trí liền ngay bên dưới trên dòng kế tiếp có tọa độ (x, y-1)

Tỷ số A/C không đổi với mỗi mặt, vì vậy giá trị độ của điểm kế tiếp trên cùng đường quét có được từ giá trị trước đó với một phép trừ.

Chúng ta thu được các giá trị độ sâu giữa các đường quét theo cách tương tự. Một lần nữa giả sử rằng vị trí (x, y) có độ sâu z. Khi đó ở vị trí (x, y-1) trên đường quét ngay bên dưới, giá trị độ sâu được tính từ phương trình mặt phẳng như sau:

hoặc:

(5)

ở đây cần một phép cộng hằng B/C với giá trị độ sâu z trước đó.

Phương pháp vùng đệm độ sâu thì dễ dàng để cài đặt, và nó không cần sắp xếp các mặt trong ảnh. Nhưng nó cần đến một vùng đệm thứ hai đó là vùng đệm làm tươi. Một hệ thống với độ phân giải 1024 x 1024 có thể cần hơn một triệu vị trí trong vùng đệm độ sâu, với mỗi vị trí cần đủ bit để lưu giữ các tọa độ z tăng. Một cách để giảm bớt không gian lưu giữ cần thiết là tại mỗi thời điểm chỉ xử một phần của ảnh, dùng một vùng độ sâu nhỏ hơn. Sau mỗi phần ảnh được xử lý xong, vùng đệm được dùng lại cho phần kế tiếp.

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 6 ở 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 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 S1 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 S1 đượ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 S2 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.

Các đường quét cắt hình chiếu của hai mặt S1 và S2 trên mặt phẳng chiếu. Các đường nét đứt chỉ ra rằng đó là biên của mặt bị che khuất.

Danh sách động cho đường quét 2 và 3 trong hình 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 S1 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 S1 được được giả thiết là nhỏ hơn của mặt S2, vì vậy độ sáng của mặt S1 đượ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 S1 trở thành off, và độ sáng của mặt S2 đượ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 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 S1 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). 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 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.

Các ví dụ về hướng các mặt che khuất lẫn nhau.

Chia một mặt ra làm nhiều mặt để tránh các vấn đề nhìn thấy và không nhìn thấy luân phiên giữa hai mặt.

Ta có thể sử dụng cả hai phương pháp không gian ảnh và không gian đối tượng trong một thuật toán khử mặt khuất. Phương pháp sắp xếp theo độ sâu (depth- sorting method) là một sự nối kết của hai tiếp cận trên, nó thực hiện các công việc cơ bản sau:

• Các mặt được sắp theo thứ tự giảm dần của độ sâu.
• Các mặt được vẽ theo thứ tự từ mặt có độ sâu lớn nhất đến mặt có độ sâu nhỏ nhất (vẽ từ mặt xa nhất đến mặt gần nhất).

Các các thao tác sắp xếp được thực hiện trong không gian đối tượng, còn sự chuyển đổi dòng quét (scan conversion) được thực hiện trong không gian ảnh.

Phương pháp giải quyết vấn đề mặt khuất này đôi khi còn được gọi là thuật toán của họa sĩ (painter’s algorithm). Để tạo ra một bức sơn dầu (oil painting), đầu tiên họa sĩ sơn các độ sáng nền. Kế tiếp, các đối tượng ở xa nhất được thêm vào. Sau cùng, các đối tượng ở gần được vẽ phủ lên các đối tượng ở xa đó. Mỗi lớp vẽ sau phủ lên lớp vẽ trước đó. Dùng kỹ thuật tương tự, chúng ta đầu tiên sắp xếp các mặt theo khoảng cách từ chúng đến mặt quan sát. Các giá trị độ sáng của mặt xa nhất được nhập vào vùng vùng đệm làm tươi. Với mỗi mặt kế tiếp (xét theo thứ tự độ sâu giảm dần), ta “sơn” các độ sáng của mặt lên vùng đệm làm tươi (phủ lên các độ sáng của mặt được xử lý trước đó).

Việc sơn các mặt đa giác lên vùng đệm làm tươi dựa theo độ sâu được thực hiện trong vài bước. Đầu tiên, các mặt được sắp xếp dựa vào giá trị z lớn nhất của mỗi mặt. Mặt với độ sâu lớn nhất (gọi là S) sau đó được so sánh với các mặt còn lại trong danh sách để xác định xem có bất kỳ sự chồng độ sâu nào không (nằm chồng lên nhau). Nếu không có sự chồng độ sâu nào xảy ra, S được vẽ ra (vẽ ra theo từng đường quét). Trong hình 9 trình bày hai mặt không có sự chồng độ sâu (hai mặt không nằm chồng nhau), hình chiếu của chúng lên mặt phẳng xz. Xử lý này sau đó được lặp lại cho mặt kế tiếp trong danh sách. Khi không có sự chồng độ sâu nào xảy ra, mỗi mặt sẽ được xử lý theo thứ tự độ sâu đó cho đến khi tất cả đều được quét qua. Nếu có một sự chồng độ sâu được phát hiện ở bất kỳ điểm nào trong danh sách, ta cần làm vài so sánh bổ sung để xác định xem mặt nào nên được sắp xếp lại.

Với mỗi mặt nằm chồng với S, ta thực hiện các phép kiểm tra sau. Chỉ cần một trong số các phép kiểm tra này là đúng (true), ta không cần sắp lại vị trí mặt đó. Các phép kiểm tra được lập danh sách theo mức độ khó tăng dần:

1. Trên mặt phẳng xy, các hình chữ nhật bao quanh hai mặt không chồng lên nhau.
2. Mặt S thì ở “phía ngoài” mặt nằm chồng, so sánh dựa vào mặt phẳng quan sát.
3. Mặt nằm chồng thì ở “phía trong ” mặt S, so sánh dựa vào mặt phẳng quan sát.
4. Các hình chiếu của hai mặt lên mặt phẳng quan sát không nằm chồng lên nhau.

Vừa khi một phép kiểm tra được phát hiện là đúng cho một mặt nằm chồng, ta biết rằng mặt không nằm phía sau S. Vì vậy ta chuyển đến mặt chồng S kế tiếp. Nếu tất cả các mặt mặt nằm chồng vượt qua được ít nhất một trong các phép kiểm tra trên, ta không phải sắp xếp và S có thể được vẽ ra.

Phép kiểm tra 1 được thực hiện trong hai phần: Chúng ta kiểm tra sự nằm chồng theo hướng x, sau đó kiểm tra nằm chồng theo hướng y. Nếu cái nào trong hai hướng này được phát hiện là không có nằm chồng, hai mặt phẳng không che khuất nhau. Một ví dụ về hai mặt có nằm chồng theo hướng z nhưng không chồng theo hướng x được cho trong hình 10.

Chúng ta có thể thực hiện phép kiểm tra 2 bằng cách thế tọa độ tất cả các đỉnh của S vào phương trình mặt của mặt nằm chồng và kiểm tra dấu của kết quả. Giả sử rằng mặt nằm chồng có hệ số A’, B’, C’, và D’. Nếu A’x + B’y + C’z + D’ > 0 với mỗi đỉnh có tọa độ (x, y, z) của S, mặt S sẽ ở “phía ngoài” mặt nằm chồng S’ (xem hình 11). Như được đề cập trước đây, các hệ số A’, B’, C’, và D’ phải được xác định trước để pháp vector của mặt nằm chồng S’ chỉ ra xa khỏi mặt phẳng quan sát.

Mặt S hoàn toàn ở “phía ngoài” mặt nằm chồng S’ khi nhìn từ mặt quan sát xy.

Mặt nằm chồng S’ hoàn toàn ở “phía trong” mặt S, khi nhìn từ mặt quan sát xy.

Phép kiểm tra 3 được thực hiện dùng các hệ số A, B, C, và D của mặt S. Nếu tọa độ (x, y, z) của tất cả các đỉnh của mặt nằm chồng S’ thỏa điều kiện Ax + By + Cz + D < 0, khi đó mặt nằm chồng S’ sẽ ở “phía trong” mặt S (cung cấp pháp vector của mặt S hướng ra xa mặt phẳng quang sát). Hình 12 trình bày một mặt nằm chồng S’ thỏa phép kiểm tra này. Trong ví dụ này, mặt S thì không ở “phía ngoài” S’ (phép kiểm tra 2 không đúng).

Nếu tất cả các phép kiểm tra từ 1 đến 3 đều thất bại (sai), chúng ta thử đến phép kiểm tra 4 bằng cách kiểm tra sự cắt nhau giữa các cạnh biên của hai mặt, dùng các phương trình đường thẳng trong mặt xy. Như được minh họa trong hình 13, hai mặt có thể cắt hoặc không cắt nhau thậm chí khi các không gian bao quanh chồng nhau theo các hướng x, y, và z (xem hình 13).

Hai mặt với các biên chữ nhật nằm chồng nhau trong mặt xy

Nếu tất cả bốn phép kiểm tra trên đều thất bại với một mặt nằm chồng cụ thể S’, ta đổi chỗ hai mặt S và S’ cho nhau trong danh sách đã được sắp. Một ví dụ của hai mặt sẽ được sắp xếp lại với thủ tục này được cho trong hình 14. Tuy nhiên, ta vẫn không biết chắc rằng ta đã tìm gặp mặt xa nhất tính từ mặt phẳng quan sát chưa. Hình 15 minh họa một trường hợp mà tại đó đầu tiên chúng ta đổi chổ S và S’’ với nhau. Nhưng vì S’’che khuất một phần của S’ (nhìn lên từ mặt xy), chúng ta cần đổi chổ S’’ và S’ với nhau để có ba mặt được sắp hợp lý theo độ sâu. Do đó, chúng ta cần lặp lại quá trình kiểm tra cho mỗi mặt, cái vừa được sắp lại trong danh sách.

Mặt S có độ sâu z lớn hơn

Thuật toán vừa được phác thảo có thể đi vào một vòng lặp vô tận nếu hai hay nhiều mặt che khuất lẫn nhau một cách luân phiên như trong hình 7 (xem hình 7).

Trong các trường hợp như thế, thuật toán sẽ lặp đi lặp lại không ngừng việc đổi chỗ vị trí của các mặt nằm chồng nhau. Để tránh các vòng lặp như thế, chúng ta có thể đặt cờ trạng thái cho mặt nào vừa được sắp đến vị trí xa hơn để nó không bị di chuyển lại nữa. Nếu có một sự cố gắng được làm để đổi chỗ các mặt lần thứ hai, ta chia nó ra làm hai phần tại đường cắt (đường giao) của hai mặt. Mặt ban đầu sau đó được thay thế bởi hai mặt mới, và ta lại tiếp tục quá trình xử lý như trước đây.

Kỹ thuật khử mặt khuất này thì hiệu quả cho phương pháp không gian ảnh, nhưng các phương pháp không gian đối tượng có thể được dùng để thực hiện việc sắp xếp các mặt theo độ sâu. Phương pháp phân chia vùngtận dụng các thuận lợi của các vùng cố kết trong ảnh bằng cách xác định các vùng quan sát này để tách chúng làm nhiều phần nhỏ, mỗi phần được xem như một mặt đơn lẻ. Chúng ta áp dụng phương pháp này bằng cách phân chia thành công toàn bộ vùng quan sát thành các hình chữ nhật càng lúc càng nhỏ cho đến khi mỗi vùng nhỏ là hình chiếu của một phần của một mặt đơn lẻ nhìn thấy được, hoặc cho đến khi không thể tiếp tục phân chia.

Các phần chia được thực hiện thành công với phép chia 2.

Để thực hiện phương pháp này, ta cần xây dựng các phép kiểm tra để xác định nhanh chóng vùng là một phần của một mặt đơn lẻ hoặc cho ta biết vùng thì quá phức tạp để phân tích bình thường. Bắt đầu với cái nhìn tổng thể, ta áp dụng các phép kiểm tra để xác định xem có nên phân chia toàn bộ vùng thành các hình chữ nhật nhỏ hơn không. Nếu các phép kiểm tra chỉ ra rằng mặt quan sát đủ phức tạp, ta phân chia nó. Kế tiếp, chúng ta áp dụng các phép kiểm tra đến mỗi vùng nhỏ hơn, chia nhỏ những vùng này nếu các phép kiểm tra xác định rằng tính nhìn thấy được của một mặt đơn là vẫn chưa chắc chắn. Chúng ta tiếp tục quá trình này đến khi các phần phân chia là dễ dàng được phân tích như là một mặt đơn lẻ hoặc đến khi chúng được thu giảm kích thước thành một pixel.

Một cách để phân chia một vùng thành công là chia kích thước nó ra làm 2, như trong hình 16. Một vùng quan sát với độ phân giải 1024x1024 có thể được chia 10 lần trước khi một phần chia giảm thành 1 điểm.

Các phép kiểm tra để xác định tính nhìn thấy được của một mặt đơn trong phạm vi vùng chỉ định được thực hiện bằng cách so sánh các mặt với biên của vùng. Có bốn khả năng có thể xảy ra khi xem xét mối quan hệ giữa một mặt với biên vùng chỉ định. Ta có thể mô tả đặc điểm của các quan hệ này theo các cách sau (xem hình 17):

Mặt bao quanh (surrounding surface)là mặt hoàn toàn bao quanh một vùng. Mặt nằm chồng (overlapping surface)là mặt có một phần nằm trong và một phần nằm ngoài vùng.

Mặt bên trong (inside surface)là mặt hoàn toàn nằm bên trong vùng.

Mặt bên ngoài (outside surface)là mặt hoàn toàn nằm bên ngoài vùng.

Các quan hệ có thể xảy ra giữa các mặt đa giác và một vùng chữ nhật.

Các phép kiểm tra để xác định tính nhìn thấy được của mặt trong phạm vị một vùng có thể được đề cập giới hạn trong bốn loại này. Không có sự phân chia nào thêm nữa cho một vùng nếu một trong các điều kiện sau là đúng (true):

1. Tất cả các mặt nằm bên ngoài vùng.
2. Chỉ một mặt bên trong, mặt nằm chồng hoặc mặt bao quanh ở trong vùng.
3. Một mặt bao quanh che khuất tất cả các mặt khác trong phạm vi các biên của vùng.

Kiểm tra 1 có thể được thực hiện bằng cách kiểm tra các biên chữ nhật bao quanh các mặt với biên của vùng. Kiểm tra 2 cũng có thể dùng các biên chữ nhật trong mặt xy để xác định mặt nằm trong. Với những kiểu mặt khác, các biên chữ nhật có thể được dùng như một bước kiểm tra ban đầu. Nếu một biên chữ nhật cắt vùng theo cách nào đó, các kiểm tra tiếp theo mới được thực hiện để xác định xem mặt là: mặt bao quanh, mặt nằm chồng, hay mặt bên ngoài. Nếu được xác định là mặt bên trong, mặt nằm chồng, hay mặt bao quanh, các giá trị độ sáng pixel của nó được chuyển đến vùng thích hợp trong vùng đệm khung.

Một phương pháp để thực hiện bước 3 là sắp xếp các mặt dựa theo độ sâu nhỏ nhất của chúng. Sau đó, với mỗi mặt bao quanh, ta đi tính giá trị z lớn nhất trong vùng được xem xét. Nếu giá trị lớn nhất z của một mặt nào (trong số các mặt mặt bao quanh) nhỏ hơn giá trị z nhỏ nhất của các mặt còn lại trong vùng, kiểm tra 3 thỏa. Hình 18 trình bày một ví dụ chứa các điều kiện của phương pháp này.

Một mặt bao quanh với độ sâu lớn nhất của zmax (xét trong vùng quan sát) che khuất tất cả các mặt mà độ sâu nhỏ nhất x_min của chúng lớn hơn z_max.

Một phương pháp khác để thực hiện kiểm tra 3 mà không cần đến sắp xếp độ sâu là dùng các phương trình mặt phẳng để tính các giá trị z ở bốn đỉnh của vùng cho tất cả các mặt bao quanh, mặt nằm chồng, hay mặt bên trong. Nếu các giá trị z của một trong số các mặt bao quanh mà nhỏ hơn các giá trị z của các mặt còn lại, kiểm tra 3 đúng. Sau đó vùng có thể được tô với các giá trị độ sáng của mặt bao quanh.

Trong vài trường hợp, cả hai phương pháp cho kiểm tra 3 trên sẽ thất bại để xác định đúng một mặt bao quanh che khuất tất cả các mặt còn lại khác. Việc kiểm tra thêm nữa sẽ được thực hiện để xác định mặt đơn che phủ vùng, tuy nhiên, thuật toán sẽ nhanh hơn nếu ta phân chia vùng hơn là tiếp tục làm các kiểm tra phức tạp. Khi các mặt bên ngoài và mặt bao quanh vừa được xác định cho một vùng, chúng nó sẽ còn lại các mặt bên ngoài và bao quanh cho tất cả các phần phân chia của vùng. Hơn nữa, vài mặt bên trong và mặt nằm chồng có thể đang chờ để bị loại bỏ khi quá trình phân chia tiếp tục, để các vùng trở nên dễ dàng hơn cho phân tích. Trong trường hợp đã đi đến giới hạn, kích thước vùng chia chỉ còn là 1 pixel, ta đơn giản đi tính độ sâu của mỗi mặt có liên quan ở điểm đó và chuyển giá trị độ sáng của mặt gần nhất vào vùng đệm khung.

Vùng A được phân chia thành 2 vùng A1 và A2 bằng cách dùng biên của mặt S trên mặt phẳng chiếu.

Như một thay đổi lên quá trình phân chia cơ bản, ta có thể phân chia các vùng dọc theo biên của mặt thay vì chia chúng làm 2. Nếu các mặt vừa được sắp theo độ sâu nhỏ nhất, ta có thể dùng mặt có giá trị z nhỏ nhất để phân chia một vùng được cho. Hình 19 minh họa phương pháp này để phân chia các vùng. Hình chiếu của biên mặt S được dùng để phân chia vùng ban đầu thành các phần A1 và A2. Mặt S sau đó trở thành mặt bao quanh của A1 và các phép kiểm tra 2 và 3 có thể được áp dụng để xác định xem việc phân chia thêm nữa có cần thiết không. Trong trường hợp tổng quát, sự phân chia ít hơn được cần dùng tiếp cận này, tuy nhiên nhiều xử lý thêm nữa sẽ được cần để chia vùng và phân tích mối liên hệ giữa các mặt với các biên vùng chia.