Tạo đa giác mặt cắt 2D từ lưới 3D

Question

Tôi đang viết một trò chơi sử dụng mô hình 3D để vẽ một cảnh (chiếu từ trên xuống), nhưng một công cụ vật lý 2D để tính toán phản ứng với va chạm, v.v. vài tài sản 3D mà tôi muốn có thể tự động tạo ra một hitbox bằng cách 'cắt' lưới 3D bằng mặt phẳng XY và tạo một đa giác từ các cạnh kết quả.

Google không thực hiện điều này với tôi (và cũng không có nhiều tài liệu hữu ích về SO). Gợi ý?

Các mắt tôi đang xử lý sẽ được đơn giản hóa phiên bản của các mô hình được hiển thị, được kết nối, đóng, không lồi và có chi không.

Answer 1

Vì mắt lưới của bạn không lồi, mặt cắt kết quả có thể bị ngắt kết nối, do đó thực sự bao gồm nhiều đa giác. Điều này có nghĩa là mỗi tam giác phải được kiểm tra, vì vậy bạn sẽ cần ít nhất O (n) hoạt động cho tam giác n.

Dưới đây là một cách để làm điều đó:

T <- the set of all triangles 
P <- {} 
while T is not empty: 
    t <- some element from T 
    remove t from T 
    if t intersects the plane: 
    l <- the line segment that is the intersection between t and the plane 
    p <- [l] 
    s <- l.start 
    while l.end is not s: 
     t <- the triangle neighbouring t on the edge that generated l.end 
     remove t from T 
     l <- the line segment that is the intersection between t and the plane 
     append l to p 
    add p to P 

này sẽ chạy trong thời gian O (n) thời gian cho n hình tam giác, với điều kiện là hình tam giác của bạn có gợi ý để ba người hàng xóm của họ, và đó T hỗ trợ liên tục thời gian ñuoåi (ví dụ: một bộ băm).

Giống như tất cả các thuật toán hình học, ma quỷ nằm trong chi tiết. Hãy suy nghĩ cẩn thận về những trường hợp đỉnh của tam giác chính xác trong mặt phẳng, ví dụ.

Answer 2

Bạn có thể thực hiện việc này bằng cách sử dụng hình học bằng cách tìm tất cả các đa giác giao nhau với mặt phẳng và sau đó tìm phân đoạn chính xác của giao lộ. các phân đoạn này là các đường của đa giác 2D mà bạn đang tìm kiếm.