Phát hiện bề mặt có thể nhìn thấy

Khi chúng ta xem một bức tranh có chứa các vật thể và bề mặt không trong suốt, thì chúng ta không thể nhìn thấy các đối tượng đó từ chế độ xem ở phía sau từ các vật gần mắt hơn. Chúng ta phải loại bỏ các bề mặt ẩn này để có được hình ảnh màn hình trung thực. Việc xác định và loại bỏ các bề mặt này được gọi làHidden-surface problem.

Có hai cách tiếp cận để loại bỏ các vấn đề bề mặt ẩn - Object-Space method và Image-space method. Phương pháp không gian đối tượng được thực hiện trong hệ tọa độ vật lý và phương pháp không gian ảnh được thực hiện trong hệ tọa độ màn hình.

Khi chúng ta muốn hiển thị một đối tượng 3D trên màn hình 2D, chúng ta cần xác định những phần của màn hình có thể nhìn thấy từ một vị trí xem đã chọn.

Phương pháp đệm sâu (Z-Buffer)

Phương pháp này được phát triển bởi Cutmull. Đó là một cách tiếp cận không gian hình ảnh. Ý tưởng cơ bản là kiểm tra độ sâu Z của mỗi bề mặt để xác định bề mặt gần nhất (nhìn thấy được).

Trong phương pháp này, mỗi bề mặt được xử lý riêng biệt từng vị trí pixel trên bề mặt. Các giá trị độ sâu của một pixel được so sánh và bề mặt gần nhất (z nhỏ nhất) xác định màu sẽ hiển thị trong bộ đệm khung.

Nó được áp dụng rất hiệu quả trên các bề mặt của đa giác. Các bề mặt có thể được xử lý theo bất kỳ thứ tự nào. Để ghi đè các đa giác gần hơn từ các đa giác xa, hai bộ đệm được đặt tênframe buffer và depth buffer, được sử dụng.

Depth buffer được sử dụng để lưu trữ các giá trị độ sâu cho vị trí (x, y), khi các bề mặt được xử lý (0 ≤ độ sâu ≤ 1).

Các frame buffer được sử dụng để lưu giá trị cường độ của giá trị màu tại mỗi vị trí (x, y).

Các tọa độ z thường được chuẩn hóa thành phạm vi [0, 1]. Giá trị 0 cho tọa độ z biểu thị ngăn cắt phía sau và 1 giá trị cho tọa độ z biểu thị ngăn cắt phía trước.

Thuật toán

Step-1 - Đặt các giá trị bộ đệm -

Bộ đệm sâu (x, y) = 0

Framebuffer (x, y) = màu nền

Step-2 - Xử lý từng đa giác (Từng đa giác một)

Đối với mỗi vị trí pixel được chiếu (x, y) của một đa giác, hãy tính độ sâu z.

Nếu Z> bộ đệm độ sâu (x, y)

Tính toán màu bề mặt,

đặt bộ đệm độ sâu (x, y) = z,

framebuffer (x, y) = surfacecolor (x, y)

Ưu điểm

• Nó rất dễ thực hiện.
• Nó làm giảm vấn đề tốc độ nếu được thực hiện trong phần cứng.
• Nó xử lý một đối tượng tại một thời điểm.

Nhược điểm

• Nó yêu cầu bộ nhớ lớn.
• Đó là quá trình tốn thời gian.

Phương pháp dòng quét

Nó là một phương pháp không gian ảnh để xác định bề mặt nhìn thấy. Phương pháp này chỉ có một thông tin về độ sâu cho một dòng quét. Để yêu cầu một dòng quét các giá trị độ sâu, chúng ta phải nhóm và xử lý tất cả các đa giác giao nhau với một dòng quét nhất định cùng một lúc trước khi xử lý dòng quét tiếp theo. Hai bảng quan trọng,edge table và polygon table, được duy trì cho điều này.

The Edge Table - Nó chứa các điểm cuối tọa độ của mỗi dòng trong khung cảnh, độ dốc nghịch đảo của mỗi dòng và các con trỏ vào bảng đa giác để kết nối các cạnh với bề mặt.

The Polygon Table - Nó chứa các hệ số mặt phẳng, đặc tính vật liệu bề mặt, dữ liệu bề mặt khác và có thể là con trỏ đến bảng cạnh.

Để tạo thuận lợi cho việc tìm kiếm các bề mặt vượt qua một đường quét nhất định, một danh sách các cạnh đang hoạt động được hình thành. Danh sách hiện hoạt chỉ lưu trữ những cạnh vượt qua dòng quét theo thứ tự tăng dần x. Ngoài ra, một cờ được thiết lập cho mỗi bề mặt để cho biết vị trí dọc theo đường quét là bên trong hay bên ngoài bề mặt.

Vị trí pixel trên mỗi dòng quét được xử lý từ trái sang phải. Tại giao điểm bên trái với một bề mặt, cờ bề mặt được bật và ở bên phải, cờ bị tắt. Bạn chỉ cần thực hiện tính toán độ sâu khi nhiều bề mặt đã bật cờ của chúng tại một vị trí đường quét nhất định.

Phương pháp phân khu vực

Phương pháp chia nhỏ khu vực tận dụng lợi thế bằng cách định vị những khu vực khung nhìn đại diện cho một phần của một bề mặt. Chia tổng vùng xem thành các hình chữ nhật nhỏ hơn và nhỏ hơn cho đến khi mỗi vùng nhỏ là hình chiếu của một phần của một bề mặt nhìn thấy được hoặc không có bề mặt nào cả.

Tiếp tục quá trình này cho đến khi các phần nhỏ được phân tích dễ dàng như thuộc về một bề mặt hoặc cho đến khi chúng được giảm xuống kích thước của một pixel. Một cách dễ dàng để làm điều này là chia liên tiếp khu vực thành bốn phần bằng nhau ở mỗi bước. Có bốn mối quan hệ có thể có mà một bề mặt có thể có với một ranh giới khu vực xác định.

• Surrounding surface - Một trong đó hoàn toàn bao quanh khu vực.

• Overlapping surface - Một phần nằm trong và một phần bên ngoài khu vực.

• Inside surface - Một cái nằm hoàn toàn trong khu vực.

• Outside surface - Một cái hoàn toàn nằm ngoài khu vực.

Các thử nghiệm để xác định khả năng hiển thị bề mặt trong một khu vực có thể được nêu theo bốn cách phân loại này. Không cần chia nhỏ khu vực cụ thể nữa nếu một trong các điều kiện sau là đúng:

• Tất cả các bề mặt là bề mặt bên ngoài đối với khu vực.
• Trong khu vực chỉ có một bề mặt bên trong, chồng chéo hoặc xung quanh.
• Một bề mặt xung quanh che khuất tất cả các bề mặt khác trong ranh giới khu vực.

Nhận diện khuôn mặt sau

Một phương pháp không gian-đối tượng nhanh chóng và đơn giản để xác định các mặt sau của hình đa diện dựa trên các phép thử "bên trong-bên ngoài". Một điểm (x, y, z) nằm "bên trong" bề mặt đa giác với các tham số mặt phẳng A, B, C và D nếu Khi một điểm bên trong nằm dọc theo đường ngắm của bề mặt, đa giác phải là mặt sau ( chúng ta đang ở bên trong khuôn mặt đó và không thể nhìn thấy mặt trước của nó từ vị trí xem của chúng ta).

Chúng ta có thể đơn giản hóa việc kiểm tra này bằng cách xem xét vectơ pháp tuyến N đến một bề mặt đa giác, có các thành phần Descartes (A, B, C).

Nói chung, nếu V là một vectơ theo hướng quan sát từ vị trí của mắt (hoặc "máy ảnh"), thì đa giác này là mặt sau nếu

V.N > 0

Hơn nữa, nếu mô tả đối tượng được chuyển đổi thành tọa độ chiếu và hướng xem của bạn song song với trục z đang xem, thì -

V = (0, 0, V _z ) và V.N = V _Z C

Vì vậy ta chỉ cần coi dấu của C là thành phần của vectơ pháp tuyến N.

Trong hệ thống xem thuận tay phải với hướng xem dọc theo trục $ Z_ {V} $ âm, đa giác là mặt sau nếu C <0. Ngoài ra, chúng tôi không thể nhìn thấy bất kỳ mặt nào mà pháp tuyến có z thành phần C = 0, vì hướng xem là về phía đa giác đó. Do đó, nói chung, chúng ta có thể gắn nhãn bất kỳ đa giác nào là mặt sau nếu vectơ pháp tuyến của nó có giá trị thành phần az -

C <= 0

Các phương pháp tương tự có thể được sử dụng trong các gói sử dụng hệ thống quan sát thuận tay trái. Trong các gói này, các thông số mặt phẳng A, B, C và D có thể được tính toán từ tọa độ đỉnh đa giác được chỉ định theo chiều kim đồng hồ (không giống như hướng ngược chiều kim đồng hồ được sử dụng trong hệ thống thuận tay phải).

Ngoài ra, mặt sau có vectơ pháp tuyến hướng ra xa vị trí xem và được xác định bởi C> = 0 khi hướng xem dọc theo trục $ Z_ {v} $ dương. Bằng cách kiểm tra tham số C cho các mặt phẳng khác nhau xác định một đối tượng, chúng ta có thể xác định ngay lập tức tất cả các mặt sau.

Phương pháp A-Buffer

Phương pháp đệm A là một phần mở rộng của phương pháp đệm sâu. Phương pháp A-buffer là một phương pháp phát hiện khả năng hiển thị được phát triển tại Lucas film Studios cho hệ thống kết xuất Renders Everything You Ever Saw (REYES).

Bộ đệm A mở rộng trên phương pháp đệm độ sâu để cho phép độ trong suốt. Cấu trúc dữ liệu quan trọng trong bộ đệm A là bộ đệm tích lũy.

Mỗi vị trí trong A-buffer có hai trường:

• Depth field - Nó lưu trữ một số thực dương hoặc âm

• Intensity field - Nó lưu trữ thông tin cường độ bề mặt hoặc giá trị con trỏ

Nếu độ sâu> = 0, số được lưu tại vị trí đó là độ sâu của một bề mặt chồng lên vùng pixel tương ứng. Sau đó, trường cường độ lưu trữ các thành phần RGB của màu bề mặt tại điểm đó và phần trăm độ phủ pixel.

Nếu độ sâu <0, nó cho biết sự đóng góp của nhiều bề mặt vào cường độ pixel. Sau đó, trường cường độ lưu trữ một con trỏ đến danh sách dữ liệu bề mặt được liên kết. Bộ đệm bề mặt trong bộ đệm chữ A bao gồm:

• Thành phần cường độ RGB
• Tham số Opacity
• Depth
• Phần trăm phạm vi khu vực
• Nhận dạng bề mặt

Thuật toán tiến hành giống như thuật toán bộ đệm độ sâu. Giá trị độ sâu và độ mờ được sử dụng để xác định màu cuối cùng của pixel.

Phương pháp phân loại theo độ sâu

Phương pháp sắp xếp theo chiều sâu sử dụng cả hoạt động không gian ảnh và không gian đối tượng. Phương pháp phân loại theo chiều sâu thực hiện hai chức năng cơ bản:

• Đầu tiên, các bề mặt được sắp xếp theo thứ tự độ sâu giảm dần.

• Thứ hai, các bề mặt được quét chuyển đổi theo thứ tự, bắt đầu với bề mặt có độ sâu lớn nhất.

Việc chuyển đổi quét các bề mặt đa giác được thực hiện trong không gian hình ảnh. Phương pháp giải bài toán bề mặt ẩn này thường được gọi làpainter's algorithm. Hình sau đây cho thấy tác dụng của phân loại theo độ sâu:

Thuật toán bắt đầu bằng cách sắp xếp theo độ sâu. Ví dụ, ước tính "độ sâu" ban đầu của một đa giác có thể được coi là giá trị z gần nhất của bất kỳ đỉnh nào của đa giác.

Chúng ta hãy lấy đa giác P ở cuối danh sách. Xét tất cả các đa giác Q có hoành độ z trùng với P. Trước khi vẽ P, chúng ta thực hiện các bài kiểm tra sau. Nếu bất kỳ phép thử nào sau đây là dương tính, thì chúng ta có thể cho rằng P có thể được rút ra trước Q.

• Các phạm vi x không chồng lên nhau?
• Các phạm vi y không trùng lặp?
• P có nằm hoàn toàn phía đối diện với mặt phẳng Q theo quan điểm không?
• Q có nằm hoàn toàn cùng phía trên mặt phẳng P là điểm ngắm không?
• Các hình chiếu của đa giác không trùng nhau?

Nếu tất cả các thử nghiệm không thành công, thì chúng tôi chia P hoặc Q bằng cách sử dụng mặt phẳng của cái kia. Các đa giác cắt mới đang chèn vào thứ tự độ sâu và quá trình này tiếp tục. Về mặt lý thuyết, sự phân vùng này có thể tạo ra O (n ² ) đa giác riêng lẻ, nhưng trên thực tế, số lượng đa giác nhỏ hơn nhiều.

Cây phân vùng không gian nhị phân (BSP)

Phân vùng không gian nhị phân được sử dụng để tính toán khả năng hiển thị. Để xây dựng cây BSP, người ta nên bắt đầu với các đa giác và dán nhãn tất cả các cạnh. Chỉ xử lý một cạnh tại một thời điểm, hãy mở rộng mỗi cạnh để nó chia đôi mặt phẳng. Đặt cạnh đầu tiên trên cây làm gốc. Thêm các cạnh tiếp theo dựa trên việc chúng ở bên trong hay bên ngoài. Các cạnh kéo dài phần mở rộng của một cạnh đã có trong cây được chia thành hai và cả hai đều được thêm vào cây.

• Từ hình trên, đầu tiên lấy A làm gốc.

• Lập danh sách tất cả các nút trong hình (a).

• Đặt tất cả các nút ở phía trước thư mục gốc A ở phía bên trái của nút A và đặt tất cả các nút nằm sau gốc A sang bên phải như hình (b).

• Xử lý tất cả các nút phía trước đầu tiên và sau đó là các nút phía sau.

• Như trong hình (c), đầu tiên chúng ta sẽ xử lý nút B. Vì không có gì ở phía trước của nútB, chúng tôi đã đặt NIL. Tuy nhiên, chúng tôi có nútC ở phía sau của nút B, vì vậy nút C sẽ đi đến phía bên phải của nút B.

• Lặp lại quy trình tương tự cho nút D.