Thuật toán GJK: cách giải quyết những việc đơn giản theo cách kỳ lạ và đẹp đẽ

• 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

1. Khởi tạo: đặt một vector hướng tùy ý d và tìm điểm đầu tiên p.
2. 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.
3. Thêm điểm mới: từ p, tìm một điểm mới theo hướng về gốc tọa độ.
4. Đơn hình hóa: thêm điểm mới dựa trên hai điểm đầu tiên để tạo simplex.
5. 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.
6. 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.

[GN⁺]

Ý kiến trên Hacker News

• Tôi đã vật lộn gần như suốt 1 năm với GJK vào những năm 1990
  Nó hữu ích cho phát hiện va chạm 3D, và cũng có thể dùng như một thuật toán tìm điểm gần nhất. Ý tưởng cơ bản thì dễ hiểu. Khi có hai khối lồi, bạn lấy tùy ý một điểm từ mỗi khối, tính khoảng cách giữa hai điểm đó, rồi lặp lại quá trình di chuyển dọc theo từng cạnh từ điểm hiện tại để cải thiện khoảng cách và chọn ra cặp điểm gần nhất mới
  Nhưng cách này sẽ hỏng khi điểm gần nhất không còn là một đỉnh nữa, và lúc đó khái niệm simplex trở nên cần thiết. Các tổ hợp điểm gần nhất được chia thành đỉnh-đỉnh, đỉnh-cạnh, đỉnh-mặt, cạnh-cạnh, cạnh-mặt (không có nghiệm duy nhất), mặt-mặt (không có nghiệm duy nhất), và việc xử lý simplex về cơ bản gần như là phân tích các trường hợp này
  Trên thực tế phát sinh rất nhiều vấn đề. Trong engine vật lý, các vật thể thường ổn định ở trạng thái tiếp xúc mặt-mặt, và mô hình va chạm một điểm có thể tạo ra dao động hoặc chuyển động sai. Ngoài ra, khi vị trí hội tụ về tiếp xúc mặt-mặt, GJK phải xử lý hiệu rất nhỏ giữa các giá trị lớn nên có thể mất hoàn toàn chữ số có nghĩa của số thực dấu phẩy động. Điều kiện dừng cũng có thể gây ra vòng lặp vô hạn
  Về lý thuyết thì thanh nhã, nhưng trong thực tế đây là một bài toán phân tích số rất khó. Dù vậy, có lẽ đây vẫn là cách tiếp cận nhanh nhất cho bài toán này. Trường hợp tổng quát là O(log N), và nếu dùng nghiệm cuối cùng làm điểm khởi đầu khi trạng thái mới rất gần trạng thái trước đó thì có thể gần O(1)
  Cố giáo sư Steven Cameron ở Oxford đã làm rất nhiều việc để khiến GJK thực sự hoạt động đúng, và đã dùng GJK trong "Falling Bodies", hệ thống ragdoll 3D thương mại đầu tiên vào cuối những năm 1990

  • Một khi đã tìm thấy tiếp xúc thì gần như chắc chắn bạn còn phải làm gì đó với nó, và để xử lý hữu ích trong đa số trường hợp, bạn cần biết thông tin chồng lấn thực sự
    Phần tính toán này còn tệ hơn về mặt số học. Bạn bắt đầu từ simplex mà GJK tạo ra rồi mở rộng ra ngoài, và trong quá trình đó phải thực hiện phép chia tam giác. Việc hiện thực nó với hiệu năng tốt gần như là một cơn ác mộng thực sự
  • https://www.youtube.com/watch?v=5lHqEwk7YHs
    Tôi tự hỏi liệu bằng sáng chế giờ đã hết hiệu lực chưa, và có ý định công bố mã nguồn không. Xét về mặt lịch sử thì rất có ý nghĩa, và có vẻ sẽ là một tư liệu thú vị kiểu như đọc mã nguồn Doom

• Tôi không tìm được bài nào giải thích thuật toán phát hiện va chạm GJK một cách trực quan, nên đã dành cả buổi chiều để tự viết lại
  Nếu có cách nào làm nó rõ ràng và hiệu quả hơn thì rất mong được góp ý. Dĩ nhiên cũng mong mọi người thông cảm rằng đây là bài viết giải thích nội dung toán học của một học sinh lớp 11

  • Bài viết rất rõ ràng. Nếu tiếp tục làm những việc như thế này, một ngày nào đó bạn có thể viết được một giáo trình xuất sắc; tài năng là điều có thể thấy rõ
    Hiện tại đã tốt rồi, nhưng để hoàn thiện hơn nữa có lẽ nên thêm vài điểm. Một giải thích ngắn về độ phức tạp thời gian trong trường hợp xấu nhất, một mục riêng về điều kiện dừng, và pseudocode xen giữa phần giải thích sẽ rất hữu ích
    Cách giải thích theo góc nhìn toán học như hiện tại là rất phù hợp và đáng giữ lại. Tuy nhiên, nếu sau mỗi bước bạn bổ sung một đoạn pseudocode ngắn thể hiện thuật toán đã tiến triển đến đâu, đồng thời định nghĩa các hàm phụ như S(•), thì có lẽ sẽ còn tốt hơn nữa
    Bài viết của bạn về mô hình ẩn của OpenAI cũng rất hay. Thời gian bỏ ra để tìm xem người tạo ra một kết quả ấn tượng còn làm gì khác gần như lúc nào cũng xứng đáng
  • Với tư cách là một nhà toán học, lời chê nặng nhất của tôi chỉ là nếu viết cho độc giả toán học thì có lẽ tôi sẽ diễn đạt vài chỗ hơi khác đi một chút
    Tiêu đề nên là "as simply as possible". Tôi chưa biết về thuật toán GJK, nhưng nếu hiện giờ tôi đang dạy Calculus III thì chắc tôi sẽ tìm cách đưa nội dung này vào bài giảng. Phần giải thích tốt đến mức như vậy
  • Tôi tò mò không biết thuật toán này có được đảm bảo dừng hay không
    Ở ví dụ hình chữ nhật bo tròn mượt ở cuối bài, tôi không thấy cơ chế nào ngăn nó chỉ ngày càng tiến gần tới đáp án mà không bao giờ thực sự chạm tới. Dĩ nhiên tôi hiểu rằng trong tính toán thực tế, sau một giới hạn độ chính xác hữu dụng nào đó thì không còn lý do gì để tiếp tục nữa
  • Ba tập hợp A, B, A-B trong hình thứ hai làm tôi hơi bối rối
    Ban đầu tôi hiểu là đang áp dụng một phép biến đổi nào đó lên A và B để tạo ra hình A-B. Đọc lại vài lần thì có vẻ A-B không phải là hai tập ở bên trái, mà là giao của một A và B khác, và điểm quan trọng là phần giao đó chồng lên gốc tọa độ hay 0,0. Không biết tôi hiểu vậy có đúng không

• Một bài thuyết trình video về cùng thuật toán: https://www.youtube.com/watch?v=ajv46BSqcK4

  • Cái này cũng đáng tham khảo: https://winter.dev/articles/gjk-algorithm
    Ở cuối có một demo tương tác minh họa hiệu Minkowski

• Bài viết rất rõ ràng và thú vị
  Một cách khác để kiểm tra xem hai tập lồi có giao nhau hay không 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 một điểm thuộc tập lồi thứ nhất và một điểm thuộc tập lồi thứ hai. Nếu giá trị tối ưu bằng 0 thì hai tập giao nhau
  Sẽ rất thú vị nếu so sánh GJK với tối ưu lồi. Tôi không rõ bên nào sẽ có lợi hơn

  • Câu hỏi thú vị đấy. Nếu mức độ chồng lấn đủ lớn thì phương pháp điểm trong có vẻ có thể dừng rất nhanh. Cũng có lẽ thêm được những điều kiện dừng sớm khéo léo

• Hình đầu tiên cho thấy giao nhau của đa giác không lồi, nhưng mãi về sau bài mới nói rằng thuật toán chỉ hoạt động với hình lồi, nên điều này có thể hơi dễ gây hiểu lầm

  • Có giải thích rằng hình không lồi sẽ được chia thành các hình lồi để xử lý

• Tôi đã dùng hàm Minkowski trong openSCAD một thời gian rồi, nên thật vui khi cuối cùng cũng hiểu nó thực sự là gì

• Vì bài này nhận được nhiều sự chú ý hơn dự tính, có lẽ tôi nên nói rõ rằng website cá nhân của tôi về cơ bản là một bộ sưu tập trò đùa nội bộ được trau chuốt khá kỹ
  Nếu muốn liên hệ hoặc có việc gì đó, cứ cho tôi biết qua trả lời bình luận

  • Nếu bạn quan tâm đến việc được cố vấn cho một dự án nghiên cứu, bạn có thể gửi mail: [e-mail]
  • Website rất hay và có vẻ bạn là một người thú vị. Hy vọng bạn sẽ tiếp tục tạo ra những thứ tuyệt vời

• Gần 10 năm trước tôi đã hiện thực GJK dựa trên phần giải thích xuất sắc của Casey: https://www.youtube.com/watch?v=Qupqu1xe7Io

• Tôi từng viết một bài liên quan đến hình học Minkowski: https://nickp.svbtle.com/asteroid-intersections