อัลกอริทึม GJK: วิธีแก้ปัญหาที่เรียบง่ายให้ดูพิศวงและงดงาม
(computerwebsite.net)- อัลกอริทึม GJK คือวิธีตรวจสอบว่ารูปทรงสองรูปซ้อนทับกันหรือไม่
- หากต้องการตรวจสอบว่ารูปทรง A และรูปทรง B ซ้อนทับกันหรือไม่ ก็เพียงตรวจดูว่ามีจุดใดจุดหนึ่งของทั้งสองรูปที่ทับกันหรือไม่
ผลต่างแบบ Minkowski
- นำทุกจุดของรูปทรงสองรูปมาลบกันเพื่อสร้างเซตใหม่
- หากเซตใหม่นี้มีจุดกำเนิดรวมอยู่ด้วย ก็หมายความว่ารูปทรงทั้งสองซ้อนทับกัน
- สิ่งนี้เรียกว่า ผลต่างแบบ Minkowski
แนวคิดพื้นฐานของอัลกอริทึม
- ตรวจสอบว่าผลต่างแบบ Minkowski ของ A และ B มีจุดกำเนิดอยู่ภายในหรือไม่
- หากผลต่างนั้นมีจุดกำเนิดอยู่ภายใน แสดงว่ารูปทรงทั้งสองซ้อนทับกัน
ขั้นตอนของอัลกอริทึม
- กำหนดค่าเริ่มต้น: ตั้งค่าเวกเตอร์ทิศทาง
dแบบใดก็ได้ และหาจุดแรกp - หาจุด: คำนวณดอทโปรดักต์ของ
dและpถ้าเป็นบวกให้ดำเนินการต่อ ถ้าเป็นลบให้จบ - เพิ่มจุดใหม่: จาก
pให้หาจุดใหม่ในทิศทางของจุดกำเนิด - ทำให้เป็นซิมเพล็กซ์: ใช้สองจุดแรกเป็นฐานแล้วเพิ่มจุดใหม่เพื่อสร้างซิมเพล็กซ์
- ตรวจสอบการครอบคลุมจุดกำเนิด: ตรวจสอบว่ารูปทรงที่ย่อให้เป็นซิมเพล็กซ์แล้วครอบคลุมจุดกำเนิดหรือไม่
- ทำซ้ำ: ทำซ้ำจนกว่าจะครอบคลุมจุดกำเนิด หรือจนกว่าจะพบหลักฐานว่าไม่ครอบคลุม
ความเห็นของ GN⁺
- จุดที่น่าสนใจ: อัลกอริทึม GJK เป็นตัวอย่างที่ดีของการแก้ปัญหาซับซ้อนด้วยการแปลงทางคณิตศาสตร์ที่เรียบง่าย
- เหตุผลที่มีประโยชน์: มีประโยชน์มากในงานกราฟิกส์แบบเรียลไทม์ เช่น การตรวจจับการชนกัน
- มุมมองเชิงวิจารณ์: การนำอัลกอริทึมนี้ไปใช้งานจริงอาจซับซ้อน และต้องอาศัยความเข้าใจที่แม่นยำ
- เทคโนโลยีที่เกี่ยวข้อง: อัลกอริทึมตรวจจับการชนกันแบบอื่นมี เช่น SAT(Separating Axis Theorem)
- ข้อควรพิจารณา: เมื่อนำอัลกอริทึม GJK ไปใช้ ควรคำนึงถึงความซับซ้อนของรูปทรงและต้นทุนในการคำนวณ
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
ช่วงทศวรรษ 1990 ผมต้องลำบากกับ GJK อยู่เกือบปี
มันมีประโยชน์สำหรับการตรวจจับการชนแบบ 3D และยังใช้เป็นอัลกอริทึมหาจุดที่ใกล้ที่สุดได้ด้วย แนวคิดพื้นฐานเข้าใจง่าย เมื่อมีวัตถุนูนสองชิ้น ให้เลือกจุดใด ๆ จากแต่ละวัตถุอย่างละจุด คำนวณระยะห่างระหว่างสองจุดนั้น จากนั้นลองขยับจากจุดปัจจุบันไปตามแต่ละขอบเพื่อดูว่าจะลดระยะได้ไหม แล้วเลือกจุดที่ใกล้ที่สุดใหม่ ทำซ้ำแบบนี้ไปเรื่อย ๆ
แต่ถ้าจุดที่ใกล้ที่สุดไม่ใช่จุดยอดอีกต่อไป วิธีนี้จะพัง และตรงนี้จึงต้องใช้แนวคิดเรื่อง simplex การจับคู่ของจุดที่ใกล้ที่สุดแบ่งได้เป็น จุดยอด-จุดยอด, จุดยอด-ขอบ, จุดยอด-หน้า, ขอบ-ขอบ, ขอบ-หน้า (ไม่มีคำตอบเอกลักษณ์), หน้า-หน้า (ไม่มีคำตอบเอกลักษณ์) และการจัดการ simplex โดยพื้นฐานแล้วก็ใกล้เคียงกับการวิเคราะห์กรณีเหล่านี้
ในทางปฏิบัติมีปัญหาเกิดขึ้นมาก ใน physics engine วัตถุมักจะนิ่งอยู่ในสถานะสัมผัสแบบหน้า-หน้า และโมเดลการชนที่เป็นจุดเดียวอาจทำให้เกิดการสั่นหรือการเคลื่อนที่ที่ผิดพลาดได้ นอกจากนี้ เมื่อตำแหน่งลู่เข้าไปสู่การสัมผัสแบบหน้า-หน้า GJK จะต้องจัดการกับผลต่างเล็ก ๆ ระหว่างค่าขนาดใหญ่ ทำให้สูญเสียเลขนัยสำคัญของ floating point ไปทั้งหมดได้ เงื่อนไขการจบก็อาจทำให้เกิดลูปไม่สิ้นสุดได้เช่นกัน
ในเชิงทฤษฎีมันสง่างาม แต่ในทางปฏิบัติเป็นปัญหา numerical analysis ที่ยากมาก ถึงอย่างนั้นก็อาจเป็นแนวทางที่เร็วที่สุดสำหรับปัญหานี้ โดยทั่วไปเป็น O(log N) และถ้าใช้คำตอบล่าสุดเป็นจุดเริ่มต้นในสถานการณ์ที่ใกล้กับตำแหน่งก่อนหน้า ก็แทบจะเป็น O(1)
ศาสตราจารย์ Steven Cameron ผู้ล่วงลับแห่ง Oxford ทำงานอย่างมากเพื่อให้ GJK ทำงานได้ถูกต้อง และในช่วงปลายทศวรรษ 1990 ระบบ ragdoll 3D เชิงพาณิชย์ตัวแรกอย่าง "Falling Bodies" ก็ใช้ GJK
การหาสิ่งนี้แย่กว่าในเชิงตัวเลข เริ่มจาก simplex ที่ GJK สร้างไว้แล้วขยายออกไปด้านนอก และระหว่างนั้นต้องทำการแบ่งสามเหลี่ยมด้วย การ implement ให้มีประสิทธิภาพแทบจะเป็นฝันร้าย
สงสัยว่าสิทธิบัตรหมดอายุแล้วหรือยัง และมีความคิดจะเปิดเผยโค้ดไหม น่าจะเป็นข้อมูลที่มีความหมายทางประวัติศาสตร์และน่าสนใจคล้ายกับการอ่านซอร์สของ Doom
ผมหาบทความที่อธิบาย อัลกอริทึมตรวจจับการชน GJK แบบเข้าใจง่ายไม่ได้ เลยใช้เวลาช่วงบ่ายเขียนสรุปเอง
ถ้ามีวิธีทำให้ชัดเจนและมีประสิทธิภาพขึ้นก็บอกกันได้ แน่นอนว่าอยากให้เผื่อใจไว้หน่อยว่าบทความนี้เป็นงานของนักเรียนมัธยมปลายปีที่ 2 ที่อธิบายเนื้อหาคณิตศาสตร์
ตอนนี้ก็ดีอยู่แล้ว แต่ถ้าจะทำให้สมบูรณ์ยิ่งขึ้น อาจเพิ่มบางอย่างได้ เช่น คำอธิบายสั้น ๆ เกี่ยวกับ time complexity ในกรณีแย่ที่สุด, ส่วนแยกสำหรับเงื่อนไขการจบ และ pseudocode แทรกระหว่างคำอธิบาย
วิธีอธิบายจากมุมมองทางคณิตศาสตร์แบบตอนนี้เหมาะดีและควรรักษาไว้ แต่หลังแต่ละขั้น ถ้าเพิ่ม pseudocode สั้น ๆ ที่นิยามฟังก์ชันช่วยอย่าง
S(•)และบอกว่าอัลกอริทึมดำเนินไปถึงไหนแล้ว ก็น่าจะดียิ่งขึ้นบทความเกี่ยวกับโมเดลลับของ OpenAI ก็ดีเช่นกัน เวลาที่ใช้ค้นดูว่าคนที่สร้างผลงานน่าประทับใจเคยทำอะไรอีกบ้าง แทบจะคุ้มค่าเสมอ
ชื่อเรื่องควรเป็น "as simply as possible" ผมไม่เคยรู้จักอัลกอริทึม GJK มาก่อน แต่ถ้าตอนนี้กำลังสอน Calculus III อยู่ ผมคงพยายามหาทางใส่เนื้อหานี้เข้าไปในชั้นเรียน นั่นแปลว่าคำอธิบายดีมาก
ในตัวอย่างสี่เหลี่ยมมุมมนท้ายบทความ ผมไม่แน่ใจว่ามีอะไรป้องกันไม่ให้มันเข้าใกล้คำตอบขึ้นเรื่อย ๆ แต่ไม่เคยไปถึงจริง ๆ แน่นอนว่าในการคำนวณจริง ผมรู้ว่าไม่มีเหตุผลต้องทำต่อหลังพ้นขีดจำกัดความแม่นยำที่ใช้ได้จริง
ตอนแรกเข้าใจว่าเป็นการแปลงบางอย่างกับ A และ B แล้วได้รูปร่าง A-B ออกมา แต่พออ่านซ้ำหลายครั้ง ดูเหมือนว่า A-B ไม่ได้หมายถึงสองเซตทางซ้าย แต่หมายถึงอินเตอร์เซกชันของ A และ B อีกคู่หนึ่ง และประเด็นสำคัญคืออินเตอร์เซกชันนั้นทับกับจุดกำเนิดหรือ 0,0 ใช่ไหม อยากรู้ว่าผมเข้าใจถูกหรือเปล่า
วิดีโอนำเสนอที่พูดถึงอัลกอริทึมเดียวกัน: https://www.youtube.com/watch?v=ajv46BSqcK4
ตอนท้ายมีเดโมแบบ interactive ที่แสดง Minkowski difference
บทความชัดเจนและน่าสนใจมาก
อีกวิธีหนึ่งในการตรวจว่าชุดนูนสองชุดตัดกันหรือไม่ คือแก้ปัญหา convex optimization ที่มินิไมซ์ norm ของผลต่างระหว่างจุดที่อยู่ในชุดนูนชุดแรกกับจุดที่อยู่ในชุดนูนชุดที่สอง ถ้าค่าที่เหมาะที่สุดเป็น 0 แปลว่าสองชุดนั้นตัดกัน
น่าจะน่าสนใจถ้าเปรียบเทียบอัลกอริทึม GJK กับ convex optimization ผมไม่แน่ใจว่าฝั่งไหนได้เปรียบกว่า
ภาพแรกแสดงการตัดกันของ รูปทรงไม่นูน แต่ข้อเท็จจริงที่ว่าอัลกอริทึมทำงานได้เฉพาะกับรูปทรงนูนเพิ่งมาปรากฏทีหลังมาก จึงอาจทำให้เข้าใจผิดเล็กน้อย
ผมใช้ ฟังก์ชัน Minkowski ใน openSCAD มาสักพักแล้ว ดีใจที่ได้รู้ว่าจริง ๆ แล้วมันคืออะไร
เพราะดูเหมือนว่าจะได้รับความสนใจมากกว่าที่คาดไว้ คงต้องบอกไว้ว่าเว็บไซต์ส่วนตัวของผมโดยพื้นฐานแล้วเป็น ชุดมุกวงใน ที่ซับซ้อน
ถ้าอยากติดต่อหรือมีอะไรให้ทำ ก็ตอบกลับมาได้
เกือบ 10 ปีก่อน ผม implement GJK โดยอาศัยคำอธิบายยอดเยี่ยมของ Casey: https://www.youtube.com/watch?v=Qupqu1xe7Io
ผมเคยเขียนบทความเกี่ยวกับ Minkowski geometry ไว้: https://nickp.svbtle.com/asteroid-intersections