Tìm dù hai hình tam giác giao nhau hoặc không

Question

Given 2 tập hợp các điểm

((x1, y1, z1), (x2, y2, z2), (x3, y3, z3)) và

((p1, q1, r1), (p2, q2, r2), (p3, q3, r3)) mỗi hình thành một tam giác trong không gian 3D.

Bạn sẽ tìm hiểu xem các tam giác này có giao nhau hay không?

Một giải pháp rõ ràng cho vấn đề này là tìm phương trình mặt phẳng hình thành bởi mỗi tam giác. Nếu các mặt phẳng song song, thì chúng không giao nhau.

Khác, tìm ra phương trình đường thẳng được hình thành bởi giao điểm của các mặt phẳng này bằng cách sử dụng vectơ bình thường của các mặt phẳng này.

Bây giờ, nếu dòng này nằm ở cả hai vùng tam giác, thì hai tam giác này giao nhau, nếu không thì sẽ không.

trianglesIntersect(Triangle T1, Triangle T2) 
{ 
    if(trianglesOnParallelPlanes(T1, T2)) 
    { 
     return false 
    } 
    Line L1 = lineFromPlanes(planeFromTriangle(T1), planeFromTriangle(T2)) 
    if(lineOnTriangle(T1, L1) AND lineOnTriangle(T2, L1)) 
    { 
     return true 
    } 
    return false 
} 

Vì tôi biết cách viết các chức năng ở trên, tôi nên xem xét những triển khai nào khác của tam giácIntersect?

Có các thuật toán nhanh hơn để giải quyết vấn đề này không?

Answer 1

Visit this table of geometric intersection algorithms kê biếu không của realtimerendering.com, nhìn vào mục nhập cho nút giao thông hình tam giác/hình tam giác, và làm theo các tài liệu tham khảo, ví dụ để Christer Ericson, Real-Time Collision Detection, trang 172. (Một cuốn sách mà tôi khuyên bạn nên đánh giá cao.)

Các ý tưởng cơ bản là đơn giản. Nếu hai tam giác cắt nhau, thì hai cạnh của một tam giác giao nhau với nhau (cấu hình bên trái trong sơ đồ bên dưới), hoặc một cạnh của mỗi tam giác cắt nhau (cấu hình bên phải).

Vì vậy, thực hiện sáu dòng kiểm tra ngã tư phân khúc tam giác và xem nếu một trong các cấu hình này được tìm thấy.

Bây giờ, bạn hỏi, làm cách nào để thực hiện kiểm tra giao cắt đoạn đường/tam giác? Vâng, thật dễ dàng. Truy cập this table of geometric intersection algorithms, xem mục nhập cho các đoạn đường thẳng (đường ray)/tam giác và thực hiện theo các tham chiếu ...

(Điều quan trọng là được nêu ở trên không xử lý hình tam giác đồng bộ một cách chính xác. điều này không quan trọng: ví dụ, khi phát hiện một va chạm giữa các lưới tam giác, các trường hợp đồng phẳng không rõ ràng nên nó không quan trọng kết quả nào được trả về. như một trường hợp đặc biệt hoặc đọc trong Ericson đối với một số phương pháp khác, ví dụ: separating-axis method hoặc Tomas Möller's interval overlap method.)