- Thuật toán GJK là một cách để kiểm tra xem hai hình có chồng lấp lên nhau hay không
- Để kiểm tra xem hình A và hình B có chồng lấp hay không, chỉ cần xác định xem có điểm nào của hai hình trùng nhau hay không
Hiệu Minkowski
- Tạo một tập hợp mới bằng cách lấy mọi điểm của hai hình trừ cho nhau.
- Nếu tập hợp mới này chứa gốc tọa độ, điều đó có nghĩa là hai hình chồng lấp lên nhau.
- Tập hợp này được gọi là hiệu Minkowski.
Ý tưởng cơ bản của thuật toán
- Kiểm tra xem hiệu Minkowski của A và B có chứa gốc tọa độ hay không.
- Nếu hiệu chứa gốc tọa độ thì hai hình chồng lấp.
Các bước của thuật toán
- Khởi tạo: đặt một vector hướng tùy ý
d và tìm điểm đầu tiên p.
- Tìm điểm: tính tích vô hướng của
d và p; nếu dương thì tiếp tục, nếu âm thì kết thúc.
- Thêm điểm mới: từ
p, tìm một điểm mới theo hướng về gốc tọa độ.
- Đơn hình hóa: thêm điểm mới dựa trên hai điểm đầu tiên để tạo simplex.
- Kiểm tra chứa gốc tọa độ: xác nhận xem hình đã đơn hình hóa có chứa gốc tọa độ hay không.
- Lặp lại: tiếp tục cho đến khi chứa gốc tọa độ hoặc tìm được bằng chứng rằng nó không chứa.
Ý kiến của GN⁺
- Điểm thú vị: Thuật toán GJK là một ví dụ hay về việc giải một bài toán phức tạp bằng phép biến đổi toán học đơn giản.
- Vì sao hữu ích: Nó được dùng rất hiệu quả trong đồ họa thời gian thực, chẳng hạn như phát hiện va chạm.
- Góc nhìn phê phán: Việc triển khai thuật toán có thể phức tạp và đòi hỏi phải hiểu thật chính xác.
- Công nghệ liên quan: Các thuật toán phát hiện va chạm khác gồm có SAT(Separating Axis Theorem).
- Điều cần cân nhắc: Khi dùng thuật toán GJK, cần tính đến độ phức tạp của hình và chi phí tính toán.
1 bình luận
Ý kiến trên Hacker News
Thuật toán GJK: Vào những năm 1990, tôi đã vật lộn suốt một năm để hiểu thuật toán GJK. Nó hữu ích cho việc phát hiện va chạm và tìm các điểm gần nhau nhất. Ý tưởng cơ bản khá dễ hiểu. Bắt đầu với hai khối rắn lồi, chọn các điểm ngẫu nhiên và cố gắng cải thiện khoảng cách giữa từng cặp điểm. Chọn cặp điểm gần nhất rồi lặp lại. Khi điểm gần nhất không còn là đỉnh nữa thì cần đến khái niệm "simplex". Về cơ bản là phải phân tích nhiều trường hợp khác nhau. Trong các physics engine, vấn đề xuất hiện khi vật thể ổn định ở trạng thái tiếp xúc mặt với mặt. Về mặt lý thuyết, đây là một lời giải thanh nhã, nhưng trong thực tế lại là một bài toán phân tích số khó. Dù vậy, đây có lẽ vẫn là cách tiếp cận nhanh nhất. Trường hợp tổng quát là O(log N), còn nếu vị trí gần với vị trí trước đó thì là O(1). Cố Giáo sư Stephen Cameron tại Oxford đã nghiên cứu rất nhiều để triển khai GJK cho đúng. GJK đã được dùng trong hệ thống ragdoll 3D thương mại "Falling Bodies" vào cuối những năm 1990.
Viết phần giải thích về GJK: Vì không tìm được một lời giải thích trực quan về thuật toán phát hiện va chạm GJK, tôi đã tự viết một bài. Nếu có cách nào làm cho nó rõ ràng hơn và hiệu quả hơn, xin hãy cho tôi biết. Đây là phần giải thích toán học của một học sinh trung học, nên hãy tiếp nhận với mức độ hoài nghi phù hợp.
Video về thuật toán GJK: Chia sẻ liên kết tới một bài thuyết trình video về cùng thuật toán này. Liên kết video
Khen bài viết: Bài viết rất tuyệt. Rất rõ ràng và thú vị.
So sánh với tối ưu lồi: Một cách khác để kiểm tra giao điểm giữa hai tập lồi là giải một bài toán tối ưu lồi nhằm cực tiểu hóa chuẩn của hiệu giữa hai điểm. Nếu giá trị tối ưu bằng 0 thì hai tập có giao điểm. Tôi muốn xem sự so sánh giữa thuật toán GJK và phương pháp tối ưu lồi. Tôi không chắc cách nào tốt hơn.
Khen bài viết và hiểu nhầm: Bài viết rất hay. Tuy nhiên, hình đầu tiên cho thấy giao điểm của các dạng không lồi, trong khi về sau mới nói rõ rằng thuật toán này chỉ hoạt động với các dạng lồi.
Lần đầu biết đến thuật toán GJK: Đây là lần đầu tôi nghe về thuật toán GJK.
Bài blog liên quan: Tôi đã viết một bài blog liên quan đến hình học Minkowski. Liên kết blog
Trang web cá nhân: Tôi bất ngờ vì nhận được sự chú ý, nên muốn nói rằng trang web cá nhân của tôi đầy những câu đùa. Nếu muốn liên hệ, hãy cho tôi biết qua phần trả lời.
Sử dụng hàm Minkowski: Tôi đã dùng hàm Minkowski trong openSCAD, và thật vui khi cuối cùng cũng biết nó thực sự là gì.
Khen thuật toán: Thật là một thuật toán tuyệt vời.