วิดีโอการสอนฟิสิกส์เกม - ส่วนที่ II: การตรวจจับการชนกันของวัตถุที่เป็นของแข็ง

นี่คือส่วนที่ 2 ของซีรีส์สามตอนของเราเกี่ยวกับฟิสิกส์ของวิดีโอเกม สำหรับส่วนที่เหลือของซีรีส์นี้ โปรดดูที่:

ส่วนที่ 1: ความรู้เบื้องต้นเกี่ยวกับพลวัตของร่างกายที่แข็งแกร่ง
ส่วนที่ III: การจำลองร่างกายที่เข้มงวด

ในตอนที่ 1 ของซีรีส์นี้ เราสำรวจร่างกายที่แข็งทื่อและการเคลื่อนไหวของพวกมัน อย่างไรก็ตาม ในการสนทนานั้น สิ่งของต่างๆ ไม่ได้โต้ตอบกัน หากไม่มีการทำงานเพิ่มเติม วัตถุจำลองที่แข็งกระด้างสามารถเคลื่อนที่เข้าหากันได้ หรือ "แทรกซึม" ซึ่งไม่พึงปรารถนาในกรณีส่วนใหญ่

เพื่อจำลองพฤติกรรมของวัตถุที่เป็นของแข็งได้สมจริงมากขึ้น เราต้องตรวจสอบว่าพวกมันชนกันทุกครั้งที่เคลื่อนที่หรือไม่ และถ้าเป็นเช่นนั้น เราต้องทำอะไรสักอย่างกับมัน เช่น การใช้แรงที่เปลี่ยนความเร็วของพวกมัน ดังนั้น ว่าพวกเขาจะเคลื่อนไปในทิศทางตรงกันข้าม นี่คือจุดที่การทำความเข้าใจฟิสิกส์การชนกันเป็นสิ่งสำคัญอย่างยิ่งสำหรับนักพัฒนาเกม

ในส่วนที่ II เราจะครอบคลุมขั้นตอนการตรวจจับการชน ซึ่งประกอบด้วยการค้นหาคู่ของวัตถุที่ชนกันระหว่างวัตถุจำนวนมากที่อาจกระจัดกระจายอยู่ทั่วโลก 2D หรือ 3D ในตอนต่อไปและขั้นสุดท้าย เราจะพูดถึง "การแก้ไข" การชนเหล่านี้มากขึ้นเพื่อขจัดการแทรกสอด

สำหรับการทบทวนแนวคิดเกี่ยวกับพีชคณิตเชิงเส้นที่อ้างถึงในบทความนี้ คุณสามารถดูหลักสูตรข้อขัดข้องเกี่ยวกับพีชคณิตเชิงเส้นได้ในส่วนที่ 1

ฟิสิกส์การชนกันในวิดีโอเกม

ในบริบทของการจำลองวัตถุแข็งเกร็ง การชนกันเกิดขึ้นเมื่อรูปร่างของวัตถุแข็งเกร็งสองตัวตัดกัน หรือเมื่อระยะห่างระหว่างรูปร่างเหล่านี้ต่ำกว่าค่าความเผื่อเล็กน้อย

ถ้าเรามี n วัตถุในการจำลอง ความซับซ้อนในการคำนวณของการตรวจจับการชนด้วยการทดสอบแบบคู่คือ O ( n 2 ) ตัวเลขที่ทำให้นักวิทยาศาสตร์คอมพิวเตอร์ต้องประจบประแจง จำนวนการทดสอบแบบคู่จะเพิ่มขึ้นแบบกำลังสองตามจำนวนวัตถุ และการพิจารณาว่ารูปร่างทั้งสองในตำแหน่งและทิศทางที่ขัดแย้งกันนั้นไม่ถูกแล้วหรือไม่ ในการเพิ่มประสิทธิภาพกระบวนการตรวจจับการชน โดยทั่วไปเราแบ่งขั้นตอนออกเป็น 2 เฟส ได้แก่ เฟสกว้าง และ เฟส แคบ

ระยะกว้างมีหน้าที่ในการค้นหาคู่ของวัตถุแข็งเกร็งที่ อาจ ชนกัน และไม่รวมคู่ที่ไม่ชนกันอย่างแน่นอน จากท่ามกลางชุดของวัตถุทั้งหมดที่อยู่ในการจำลอง ขั้นตอนนี้จะต้องสามารถปรับขนาดได้ดีมากกับจำนวนของวัตถุแข็งเกร็ง เพื่อให้แน่ใจว่าเราจะอยู่ภายใต้ความซับซ้อนของเวลา O ( n 2 ) ได้ดี เพื่อให้บรรลุเป้าหมายนั้น โดยทั่วไประยะนี้จะใช้การ แบ่งพื้นที่ว่าง ควบคู่ไปกับ ปริมาณขอบเขต ที่กำหนดขอบเขตบนสำหรับการชนกัน

ระยะแคบทำงานบนคู่ของวัตถุแข็งที่พบโดยระยะกว้างที่อาจชนกัน เป็นขั้นตอนการปรับแต่งที่เรากำหนดว่าการชนเกิดขึ้นจริงหรือไม่ และสำหรับการชนแต่ละครั้งที่พบ เราจะคำนวณจุดสัมผัสที่จะใช้ในการแก้ปัญหาการชนกันในภายหลัง

ในหัวข้อถัดไป เราจะพูดถึงอัลกอริธึมบางอย่างที่สามารถใช้ได้ในระยะกว้างและระยะแคบ

ระยะกว้าง

ในระยะกว้างของฟิสิกส์การชนกันของวิดีโอเกม เราจำเป็นต้องระบุคู่ของวัตถุแข็งกระด้างที่ อาจ ชนกัน วัตถุเหล่านี้อาจมีรูปร่างที่ซับซ้อน เช่น รูปหลายเหลี่ยมและรูปทรงหลายเหลี่ยม และสิ่งที่เราทำได้เพื่อเร่งความเร็วนี้คือการใช้รูปร่างที่เรียบง่ายกว่าเพื่อล้อมวัตถุ ถ้า ปริมาตร ที่มีขอบเหล่านี้ไม่ตัดกัน รูปร่างจริงจะไม่ตัดกัน หากตัดกัน รูปร่างจริง อาจ ตัดกัน

ขอบเขตของวอลุ่มที่ได้รับความนิยมบางประเภท ได้แก่ Oriented bounding Boxes (OBB), วงกลมในแบบ 2D และทรงกลมในแบบ 3D ลองดูขอบเขตขอบเขตที่ง่ายที่สุดอันใดอันหนึ่ง: border-aligned bounding box (AABB)

AABB ได้รับความรักมากมายจากโปรแกรมเมอร์ฟิสิกส์ เพราะพวกเขาเรียบง่ายและมีข้อดีข้อเสีย AABB 2 มิติอาจแสดงด้วยโครงสร้างแบบนี้ในภาษา C:

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

ฟิลด์ min แสดงถึงตำแหน่งของมุมล่างซ้ายของกล่อง และฟิลด์ max แสดงถึงมุมบนขวา

เพื่อทดสอบว่า AABB สองตัวตัดกันหรือไม่ เราต้องค้นหาว่าเส้นโครงของพวกมันตัดกันบนแกนพิกัดทั้งหมดหรือไม่:

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

รหัสนี้มีตรรกะเดียวกันกับฟังก์ชัน b2TestOverlap จากเอ็นจิ้น Box2D (เวอร์ชัน 2.3.0) โดยจะคำนวณความแตกต่างระหว่างค่า min สุดและ max ของ AABB ทั้งสองแบบในทั้งสองแกนในคำสั่งซื้อทั้งสอง หากค่าใดค่าหนึ่งเหล่านี้มากกว่าศูนย์ AABB จะไม่ตัดกัน

แม้ว่าการทดสอบการทับซ้อนของ AABB จะมีราคาถูก แต่ก็ไม่ได้ช่วยอะไรมากหากเรายังคงทำการทดสอบแบบคู่สำหรับทุกคู่ที่เป็นไปได้ เนื่องจากเรายังมีความซับซ้อนของเวลา O ( n 2 ) ที่ไม่ต้องการ เพื่อลดจำนวนการทดสอบการทับซ้อนของ AABB เราสามารถใช้การ แบ่งพื้นที่ บางประเภท ซึ่งทำงานบนหลักการเดียวกับดัชนีฐานข้อมูลที่เร่งการสืบค้น (ฐานข้อมูลทางภูมิศาสตร์ เช่น PostGIS จริง ๆ แล้วใช้โครงสร้างข้อมูลและอัลกอริธึมที่คล้ายกันสำหรับดัชนีเชิงพื้นที่) ในกรณีนี้ AABB จะเคลื่อนที่อยู่ตลอดเวลา ดังนั้นโดยทั่วไปแล้ว เราต้องสร้างดัชนีขึ้นใหม่หลังจากทุกขั้นตอนของการจำลอง

มีอัลกอริธึมการแบ่งพื้นที่และโครงสร้างข้อมูลมากมายที่สามารถใช้ได้ เช่น กริดแบบสม่ำเสมอ, ควอดทรีในรูปแบบ 2 มิติ, ออคทรี ในรูปแบบ 3 มิติ และการแฮชเชิงพื้นที่ ให้เราพิจารณาอัลกอริธึมการแบ่งพาร์ทิชันเชิงพื้นที่ที่เป็นที่นิยมสองแบบอย่างละเอียดยิ่งขึ้น: sort and sweep และ bounding volume hierarchies (BVH)

อัลกอริธึมการเรียงลำดับและกวาด

วิธีการ เรียงลำดับและกวาด (หรือเรียกอีกอย่างว่า กวาดและพรุน ) เป็นหนึ่งในตัวเลือกยอดนิยมในหมู่โปรแกรมเมอร์ฟิสิกส์สำหรับใช้ในการจำลองร่างกายที่เข้มงวด ตัวอย่างเช่น เครื่องยนต์ Bullet Physics มีการนำวิธีนี้ไปใช้ในคลาส btAxisSweep3

การฉายภาพของ AABB หนึ่งตัวบนแกนพิกัดเดียวโดยพื้นฐานแล้วเป็นช่วง [ b , e ] (นั่นคือจุดเริ่มต้นและจุดสิ้นสุด) ในการจำลองของเรา เราจะมีวัตถุที่แข็งกระด้างจำนวนมาก และด้วยเหตุนี้ AABB จำนวนมาก และนั่นหมายถึงช่วงหลาย ๆ ช่วงเวลา เราต้องการค้นหาว่าช่วงใดที่ตัดกัน

ในอัลกอริธึมการเรียงลำดับและกวาด เราแทรกค่า b และ e ทั้งหมดในรายการเดียว และเรียงลำดับจากน้อยไปมากตามค่าสเกลาร์ จากนั้นเราจะ กวาด หรือสำรวจรายการ เมื่อใดก็ตามที่พบค่า b ช่วงเวลาที่สอดคล้องกันจะถูกเก็บไว้ในรายการของ ช่วงเวลาที่แอ็คทีฟ แยกจากกัน และเมื่อใดก็ตามที่พบค่า e ช่วงเวลาที่สอดคล้องกันจะถูกลบออกจากรายการของช่วงเวลาที่แอ็คทีฟ ช่วงเวลาใดๆ ที่ใช้งานอยู่ทั้งหมดจะตัดกัน (ดูรายละเอียดในวิทยานิพนธ์ปริญญาเอกของ David Baraff หน้า 52 ฉันขอแนะนำให้ใช้เครื่องมือออนไลน์นี้เพื่อดูไฟล์คำลงท้าย) รายการช่วงเวลาสามารถนำมาใช้ซ้ำได้ในแต่ละขั้นตอนของการจำลอง ซึ่งเราสามารถจัดเรียงใหม่ได้อย่างมีประสิทธิภาพ รายการนี้ใช้การเรียงลำดับการแทรก ซึ่งดีในการเรียงลำดับรายการที่เรียงลำดับเกือบ

ในสองและสามมิติ การรันการเรียงลำดับและการกวาด ตามที่อธิบายไว้ข้างต้น บนแกนพิกัดเดียวจะลดจำนวนการทดสอบทางแยก AABB โดยตรงที่ต้องทำ แต่ผลตอบแทนอาจดีกว่าแกนพิกัดหนึ่งมากกว่าอีกแกนหนึ่ง ดังนั้นจึงมีการใช้รูปแบบที่ซับซ้อนมากขึ้นของอัลกอริธึมการเรียงลำดับและการกวาด ในหนังสือของเขา Real-Time Collision Detection (หน้า 336) Christer Ericson นำเสนอรูปแบบที่มีประสิทธิภาพซึ่งเขาจัดเก็บ AABB ทั้งหมดไว้ในอาร์เรย์เดียว และสำหรับการเรียงลำดับและการกวาดแต่ละครั้ง แกนพิกัดหนึ่งแกนจะถูกเลือกและอาร์เรย์จะถูกจัดเรียงตาม ค่า min สุดของ AABB ในแกนที่เลือก โดยใช้การเรียงลำดับแบบด่วน จากนั้น อาร์เรย์จะถูกข้ามผ่านและดำเนินการทดสอบการทับซ้อนของ AABB ในการกำหนดแกนถัดไปที่ควรใช้ในการคัดแยก จะมีการคำนวณความแปรปรวนของจุดศูนย์กลางของ AABB และเลือกแกนที่มีความแปรปรวนมากกว่าสำหรับขั้นตอนต่อไป

ไดนามิก Bounding Volume Trees

วิธีการแบ่งพาร์ติชั่นเชิงพื้นที่ที่มีประโยชน์อีกวิธีหนึ่งคือ ไดนามิก bounding volume tree หรือที่เรียกว่า Dbvt นี่คือประเภทของ ลำดับชั้นของวอลุ่มที่มีขอบเขต

Dbvt เป็นไบนารีทรีที่แต่ละโหนดมี AABB ที่ล้อมรอบ AABB ทั้งหมดของเด็ก AABB ของตัวแข็งนั้นอยู่ในโหนดปลายสุด โดยปกติ Dbvt จะถูก "สอบถาม" โดยให้ AABB ที่เราต้องการตรวจหาทางแยก การดำเนินการนี้มีประสิทธิภาพเนื่องจากโหนดลูกของโหนดที่ไม่ตัดกับ AABB ที่สืบค้นไม่จำเป็นต้องทดสอบการทับซ้อนกัน ดังนั้น การสืบค้นข้อมูลการชนกันของ AABB จะเริ่มต้นจากรูท และดำเนินต่อไปเรื่อยๆ ผ่านทรีสำหรับโหนด AABB ที่ตัดกับ AABB ที่สืบค้นเท่านั้น ต้นไม้สามารถปรับสมดุลได้ด้วยการหมุนของต้นไม้ เช่นเดียวกับในต้นไม้ AVL

Box2D มีการใช้งาน Dbvt ที่ซับซ้อนในคลาส b2DynamicTree คลาส b2BroadPhase มีหน้าที่ในการดำเนินการเฟสกว้าง และใช้อินสแตนซ์ของ b2DynamicTree เพื่อดำเนินการสืบค้น AABB

ระยะแคบ

หลังจากช่วงกว้างของฟิสิกส์การชนกันของวิดีโอเกม เรามีชุดของวัตถุแข็งกระด้างที่ อาจ ชนกันได้ ดังนั้น สำหรับแต่ละคู่ เมื่อพิจารณาจากรูปร่าง ตำแหน่ง และทิศทางของวัตถุทั้งสอง เราจำเป็นต้องค้นหาว่าอันที่จริงแล้วพวกมันชนกันหรือไม่ ถ้าพวกมันกำลังตัดกันหรือถ้าระยะทางต่ำกว่าค่าความคลาดเคลื่อนเล็กน้อย เราจำเป็นต้องรู้ด้วยว่าจุดสัมผัสใดระหว่างวัตถุที่ชนกัน เนื่องจากสิ่งนี้จำเป็นสำหรับการแก้ไขการชนกันในภายหลัง

รูปร่างนูนและเว้า

ตามกฎทั่วไปของฟิสิกส์ของวิดีโอเกม การพิจารณาว่ารูปร่างที่กำหนดเองสองรูปตัดกันหรือไม่ หรือเพื่อคำนวณระยะห่างระหว่างรูปร่างนั้นไม่ใช่เรื่องง่าย อย่างไรก็ตาม คุณสมบัติหนึ่งที่มีความสำคัญอย่างยิ่งในการพิจารณาว่าแข็งเพียงใดคือความ นูน ของรูปร่าง รูปร่างอาจเป็นได้ทั้งแบบ นูน หรือ เว้า และรูปร่างเว้านั้นยากต่อการใช้งาน ดังนั้นเราจึงต้องใช้กลยุทธ์ในการจัดการกับรูปร่างเหล่านี้

ในรูปร่างนูน ส่วนของเส้นตรงระหว่างจุดสองจุดภายในรูปร่างจะอยู่ภายในรูปร่างอย่างสมบูรณ์เสมอ อย่างไรก็ตาม สำหรับรูปร่างเว้า (หรือ “ไม่นูน”) สิ่งเดียวกันนี้ไม่เป็นจริงสำหรับจุดเชื่อมต่อที่เป็นไปได้ทั้งหมดของเส้นในรูปร่าง หากคุณพบส่วนของเส้นตรงอย่างน้อยหนึ่งส่วนที่อยู่นอกรูปร่างได้เลย แสดงว่ารูปร่างนั้นเว้า

ในการคำนวณ เป็นที่พึงปรารถนาที่รูปร่างทั้งหมดจะนูนออกมาในการจำลอง เนื่องจากเรามีอัลกอริธึมการทดสอบระยะทางและทางแยกที่ทรงพลังจำนวนมากที่ทำงานกับรูปร่างนูน ไม่ใช่วัตถุทั้งหมดที่จะนูนออกมา และโดยปกติเราจะแก้ไขวัตถุนั้นในสองวิธี: เปลือกนูนและการสลายตัวที่นูน

ตัวเรือนูน ของรูปร่างคือรูปร่างนูนที่เล็กที่สุดที่บรรจุไว้ทั้งหมด สำหรับรูปหลายเหลี่ยมเว้าในสองมิติ มันจะเหมือนกับการตอกตะปูบนจุดยอดแต่ละอันแล้วพันหนังยางรอบตะปูทั้งหมด ในการคำนวณเปลือกนูนสำหรับรูปหลายเหลี่ยมหรือรูปทรงหลายเหลี่ยม หรือโดยทั่วไป สำหรับชุดของจุด อัลกอริธึมที่ดีที่จะใช้คืออัลกอริธึม quickhull ซึ่งมีความซับซ้อนเวลาเฉลี่ยของ O ( n log n )

แน่นอน หากเราใช้เปลือกนูนแทนวัตถุเว้า มันจะสูญเสียคุณสมบัติเว้าไป พฤติกรรมที่ไม่พึงประสงค์ เช่น การชนกันของ "ผี" อาจปรากฏชัด เนื่องจากวัตถุจะยังคงแสดงภาพกราฟิกเว้า ตัวอย่างเช่น รถยนต์มักจะมีรูปร่างเว้า และถ้าเราใช้ตัวถังนูนเพื่อเป็นตัวแทนของมันตามร่างกายแล้ววางกล่องบนมัน กล่องอาจดูเหมือนลอยอยู่ในช่องว่างด้านบน

โดยทั่วไป ตัวเรือนูนมักจะดีพอที่จะเป็นตัวแทนของวัตถุเว้า อาจเป็นเพราะการชนกันที่ไม่สมจริงนั้นไม่ค่อยสังเกตเห็นได้ชัดเจน หรือคุณสมบัติเว้าของพวกมันไม่จำเป็นสำหรับสิ่งที่ถูกจำลอง ในบางกรณี เราอาจต้องการให้วัตถุเว้ามีลักษณะเป็นรูปร่างเว้า ตัวอย่างเช่น หากเราใช้เปลือกนูนเพื่อเป็นตัวแทนของชาม เราไม่สามารถใส่อะไรเข้าไปข้างในได้ วัตถุก็จะลอยอยู่บนนั้น ในกรณีนี้ เราสามารถใช้การ สลายตัวแบบนูน ของรูปร่างเว้าได้

อัลกอริธึมการสลายตัวแบบนูนจะได้รับรูปร่างเว้าและส่งกลับชุดของรูปร่างนูนที่มีการรวมเหมือนกันกับรูปร่างเว้าดั้งเดิม รูปร่างเว้าบางรูปสามารถแสดงได้ด้วยรูปร่างนูนจำนวนมากเท่านั้น และอาจมีค่าใช้จ่ายสูงในการคำนวณและใช้งาน อย่างไรก็ตาม การประมาณค่ามักจะดีพอ และด้วยเหตุนี้ อัลกอริธึมเช่น V-HACD จึง สร้างรูปทรงหลายเหลี่ยมนูนชุดเล็กๆ จากรูปทรงหลายเหลี่ยมเว้า

ในกรณีของฟิสิกส์การชนกันหลายๆ กรณี ศิลปินสามารถประดิษฐ์การสลายตัวแบบนูนได้ด้วยมือ ซึ่งช่วยลดความจำเป็นในการเสียภาษีด้วยอัลกอริธึมการสลายตัว เนื่องจากประสิทธิภาพเป็นหนึ่งในแง่มุมที่สำคัญที่สุดในการจำลองแบบเรียลไทม์ จึงเป็นความคิดที่ดีที่จะสร้างการแสดงทางกายภาพที่เรียบง่ายสำหรับออบเจกต์กราฟิกที่ซับซ้อน ภาพด้านล่างแสดงการยุบตัวแบบนูนที่เป็นไปได้ของรถ 2D โดยใช้รูปทรงนูนเก้าแบบ

การทดสอบทางแยก - ทฤษฎีบทแกนแยก

ทฤษฎีบทแยกแกน (SAT) ระบุว่ารูปร่างนูนสองรูปจะไม่ตัดกันก็ต่อเมื่อมีแกนอย่างน้อยหนึ่งแกนที่การฉายภาพมุมฉากของรูปร่างบนแกนนี้ไม่ตัดกัน

โดยปกติแล้ว การหาเส้นในแบบ 2D หรือระนาบแบบ 3D นั้นจะมองเห็นได้ชัดเจนกว่าซึ่งแยกรูปร่างทั้งสองออกจากกัน ซึ่งใช้หลักการเดียวกันได้อย่างมีประสิทธิภาพ เวกเตอร์มุมฉากกับเส้นในแบบ 2 มิติ หรือเวกเตอร์ปกติของระนาบในแบบ 3 มิติ สามารถใช้เป็น "แกนแยก" ได้

เครื่องมือฟิสิกส์ของเกมมีรูปทรงต่างๆ มากมาย เช่น วงกลม (ทรงกลมในแบบ 3 มิติ) ขอบ (ส่วนของเส้นเดียว) และรูปหลายเหลี่ยมนูน (รูปทรงหลายเหลี่ยมในแบบ 3 มิติ) สำหรับรูปร่างแต่ละคู่ พวกมันมีอัลกอริธึมการตรวจจับการชนกันเฉพาะ วิธีที่ง่ายที่สุดคืออัลกอริธึมวงกลมวงกลม:

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

แม้ว่า SAT จะใช้กับวงกลม แต่ง่ายกว่ามากที่จะตรวจสอบว่าระยะห่างระหว่างจุดศูนย์กลางน้อยกว่าผลรวมของรัศมีหรือไม่ ด้วยเหตุผลดังกล่าว SAT จึงถูกใช้ในอัลกอริธึมการตรวจจับการชนสำหรับคู่ของคลาสรูปร่างเฉพาะ เช่น รูปหลายเหลี่ยมนูนเทียบกับรูปหลายเหลี่ยมนูน (หรือรูปหลายเหลี่ยมในแบบ 3 มิติ)

สำหรับรูปร่างคู่ใด ๆ มีแกนจำนวนอนันต์ที่เราสามารถทดสอบการแยกได้ ดังนั้น การกำหนดแกนที่จะทดสอบก่อนจึงเป็นสิ่งสำคัญสำหรับการนำ SAT ไปใช้อย่างมีประสิทธิภาพ โชคดีที่เมื่อทำการทดสอบว่ารูปหลายเหลี่ยมนูนคู่หนึ่งชนกันหรือไม่ เราสามารถใช้ขอบปกติของขอบเป็นแกนแยกที่อาจเกิดขึ้นได้ เวกเตอร์ตั้งฉาก n ของขอบตั้งฉากกับเวกเตอร์ขอบ และชี้ออกนอกรูปหลายเหลี่ยม สำหรับแต่ละขอบของรูปหลายเหลี่ยมแต่ละอัน เราแค่ต้องหาว่าจุดยอดทั้งหมดของรูปหลายเหลี่ยมอื่นอยู่ ด้านหน้า ขอบหรือไม่

หากการทดสอบใดๆ ผ่าน นั่นคือถ้าจุดยอดทั้งหมดของรูปหลายเหลี่ยมอื่นอยู่ ข้างหน้า จุดยอดแล้ว รูปหลายเหลี่ยมจะไม่ตัดกัน พีชคณิตเชิงเส้นให้สูตรง่ายๆ สำหรับการทดสอบนี้: ให้ขอบของรูปร่างแรกที่มีจุดยอด a และ b และจุดยอด v บนรูปร่างอื่น ถ้า ( v - a ) · n มากกว่าศูนย์ จุดยอดจะอยู่ข้างหน้า ของขอบ

สำหรับรูปทรงหลายเหลี่ยม เราสามารถใช้ face normals และ cross product ของการผสมผสานขอบทั้งหมดจากแต่ละรูปร่าง ฟังดูเหมือนมีอะไรให้ทดสอบมากมาย อย่างไรก็ตาม เพื่อให้เร็วขึ้น เราสามารถแคชแกนแยกสุดท้ายที่เราใช้และลองใช้อีกครั้งในขั้นตอนต่อไปของการจำลอง หากแกนแยกที่แคชไว้ไม่แยกรูปร่างอีกต่อไป เราสามารถค้นหาแกนใหม่โดยเริ่มจากใบหน้าหรือขอบที่อยู่ติดกับใบหน้าหรือขอบก่อนหน้า วิธีนี้ได้ผลเพราะร่างกายมักจะไม่ขยับหรือหมุนไปมาระหว่างขั้นตอนมากนัก

Box2D ใช้ SAT เพื่อทดสอบว่ารูปหลายเหลี่ยมนูนสองรูปกำลังตัดกันในอัลกอริธึมการตรวจจับการชนกันของรูปหลายเหลี่ยม-รูปหลายเหลี่ยมใน b2CollidePolygon.cpp

ระยะทางในการคำนวณ - อัลกอริทึมของ Gilbert-Johnson-Keerthi

ในกรณีฟิสิกส์การชนกันหลายๆ กรณี เราต้องการพิจารณาว่าวัตถุชนกัน ไม่เพียงแต่ว่าวัตถุเหล่านั้นกำลังตัดกันจริงๆ เท่านั้น แต่ยังรวมถึงหากวัตถุเหล่านั้นอยู่ใกล้กันมาก ซึ่งทำให้เราต้องทราบระยะห่างระหว่างวัตถุด้วย อัลกอริทึม Gilbert-Johnson-Keerthi (GJK) คำนวณระยะห่างระหว่างรูปร่างนูนสองรูปและจุดที่ใกล้ที่สุด เป็นอัลกอริธึมที่สวยงามซึ่งทำงานร่วมกับการแสดงรูปร่างนูนโดยนัยผ่านฟังก์ชันสนับสนุน ผลรวม Minkowski และซิมเพล็กซ์ ดังที่อธิบายไว้ด้านล่าง

รองรับฟังก์ชั่น

ฟังก์ชันสนับสนุน s A ( d ) ส่งคืนจุดบนขอบเขตของรูปร่าง A ที่มีการฉายภาพสูงสุดบนเวกเตอร์ d ในทางคณิตศาสตร์ มีดอทโปรดัคสูงสุดที่มี d สิ่งนี้เรียกว่า จุดสนับสนุน และการดำเนินการนี้เรียกอีกอย่างว่า การทำแผนที่สนับสนุน ในเชิงเรขาคณิต จุดนี้เป็นจุดที่ไกลที่สุดในรูปร่างในทิศทางของ d

การหาจุดรองรับบนรูปหลายเหลี่ยมนั้นค่อนข้างง่าย สำหรับจุดสนับสนุนสำหรับ vector d คุณแค่ต้องวนผ่านจุดยอดของมันแล้วหาจุดที่มีจุดผลคูณสูงสุดด้วย d เช่นนี้

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

อย่างไรก็ตาม พลังที่แท้จริงของฟังก์ชันสนับสนุนคือช่วยให้ทำงานกับรูปร่างต่างๆ เช่น กรวย กระบอกสูบ และวงรี และอื่นๆ ได้ง่าย การคำนวณระยะห่างระหว่างรูปร่างโดยตรงนั้นค่อนข้างยาก และหากไม่มีอัลกอริธึมอย่าง GJK คุณมักจะต้องแยกรูปร่างออกเป็นหลายเหลี่ยมหรือหลายเหลี่ยมเพื่อทำให้สิ่งต่างๆ ง่ายขึ้น อย่างไรก็ตาม นั่นอาจนำไปสู่ปัญหาเพิ่มเติม เนื่องจากพื้นผิวของรูปทรงหลายเหลี่ยมไม่เรียบเท่าพื้นผิวของทรงกลม เว้นแต่ว่ารูปทรงหลายเหลี่ยมจะมีรายละเอียดมาก ซึ่งอาจนำไปสู่ประสิทธิภาพที่ไม่ดีระหว่างการตรวจจับการชน ผลข้างเคียงที่ไม่พึงประสงค์อื่น ๆ อาจปรากฏขึ้นเช่นกัน ตัวอย่างเช่น ทรงกลม "รูปทรงหลายเหลี่ยม" อาจไม่หมุนอย่างราบรื่น

เพื่อให้ได้จุดรองรับสำหรับทรงกลมที่มีศูนย์กลางที่จุดกำเนิด เราแค่ต้องทำให้เป็นมาตรฐาน d (นั่นคือ คำนวณ d / || d || ซึ่งเป็นเวกเตอร์ที่มีความยาว 1 (ความยาวหน่วย) ที่ยังคงชี้ไปในทิศทางเดียวกัน ของ d ) แล้วเราก็คูณมันด้วยรัศมีทรงกลม

ตรวจสอบกระดาษของ Gino van den Bergen เพื่อค้นหาตัวอย่างเพิ่มเติมของฟังก์ชันสนับสนุนสำหรับกระบอกสูบ กรวย และรูปทรงอื่นๆ

แน่นอน วัตถุของเราจะถูกแทนที่และหมุนจากจุดเริ่มต้นในพื้นที่จำลอง ดังนั้นเราจำเป็นต้องคำนวณจุดรองรับสำหรับรูปร่างที่แปลงแล้ว เราใช้การ แปลงสัมพัทธ์ T ( x ) = R x + c เพื่อแทนที่และหมุนวัตถุของเรา โดยที่ c คือเวกเตอร์การกระจัด และ R คือ เมทริกซ์การหมุน การแปลงนี้จะหมุนวัตถุรอบจุดกำเนิดก่อนแล้วจึงแปล ฟังก์ชันสนับสนุนสำหรับรูปร่างที่แปลง แล้ว A คือ:

Minkowski Sums

ผลรวม Minkowski ของสองรูปร่าง A และ B ถูกกำหนดเป็น:

นั่นหมายความว่าเราคำนวณผลรวมของจุดทั้งหมดที่อยู่ใน A และ B ผลลัพธ์ก็เหมือนกับการ พองตัว A กับ B

ในทำนองเดียวกัน เรากำหนดความ แตกต่าง Minkowski เป็น:

ซึ่งเราสามารถเขียนเป็นผลรวม Minkowski ของ A ด้วย -B :

สำหรับนูน A และ B นั้น A⊕B ก็นูนเช่นกัน

คุณสมบัติที่มีประโยชน์อย่างหนึ่งของความแตกต่าง Minkowski คือถ้ามันมีที่มาของพื้นที่ รูปร่างจะตัดกัน ดังที่เห็นในภาพก่อนหน้า ทำไมถึงเป็นอย่างนั้น? เพราะถ้ารูปร่างสองรูปตัดกัน พวกมันมีจุดร่วมอย่างน้อยหนึ่งจุด ซึ่งอยู่ในตำแหน่งเดียวกันในอวกาศ และความแตกต่างของมันคือเวกเตอร์ศูนย์ ซึ่งจริงๆ แล้วคือจุดกำเนิด

คุณลักษณะที่ดีอีกประการหนึ่งของความแตกต่าง Minkowski ก็คือ หากไม่มีจุดกำเนิด ระยะห่างต่ำสุดระหว่างจุดกำเนิดและความแตกต่าง Minkowski ก็คือระยะห่างระหว่างรูปร่าง

ระยะห่างระหว่างสองรูปร่างถูกกำหนดเป็น:

กล่าวอีกนัยหนึ่ง ระยะห่างระหว่าง A และ B คือความยาวของเวกเตอร์ที่สั้นที่สุดที่ไปจาก A ถึง B เวกเตอร์นี้มีอยู่ใน A⊖B และเป็นอันที่มีความยาวน้อยที่สุด ซึ่งจึงเป็นอันที่ใกล้กับจุดกำเนิดมากที่สุด

โดยทั่วไปไม่ง่ายที่จะสร้างผลรวม Minkowski ของสองรูปร่างอย่างชัดเจน โชคดีที่เราสามารถใช้การสนับสนุนการทำแผนที่ที่นี่เช่นกัน เนื่องจาก:

ซิมเพล็กซ์

อัลกอริทึม GJK จะค้นหาจุดบนความแตกต่าง Minkowski ที่ใกล้กับจุดกำเนิดมากที่สุด ทำได้โดยการสร้างชุดของ ซิมเพล็กซ์ ที่ใกล้กับจุดกำเนิดในการทำซ้ำแต่ละครั้ง ซิมเพล็กซ์ – หรืออย่างเฉพาะเจาะจงมากขึ้น k-ซิ มเพล็กซ์สำหรับจำนวนเต็ม k – คือเปลือกนูนของ k + 1 จุดที่ สัมพันธ์กันอย่างอิสระ ในปริภูมิ k- มิติ นั่นคือถ้าสองคะแนนจะต้องไม่ตรงกันสำหรับสามคะแนนพวกเขาจะต้องไม่อยู่บนเส้นเดียวกันและถ้าเรามีสี่คะแนนพวกเขาจะต้องไม่นอนบนระนาบเดียวกันด้วย ดังนั้น 0-simplex คือจุด 1-simplex คือส่วนของเส้นตรง 2-simplex เป็นรูปสามเหลี่ยมและ 3-simplex คือจัตุรมุข หากเราลบจุดหนึ่งออกจากด้านเดียว เราจะลดมิติของจุดนั้นลงหนึ่งจุด และหากเราเพิ่มจุดไปยังจุดด้านเดียว เราจะเพิ่มมิติของจุดนั้นขึ้นหนึ่งจุด

GJK ในการดำเนินการ

มารวมกันเพื่อดูว่า GJK ทำงานอย่างไร ในการกำหนดระยะห่างระหว่างรูปร่าง A และ B สองรูปร่าง เราเริ่มต้นด้วยการหาผลต่างของ Minkowski A⊖B เรากำลังค้นหาจุดที่ใกล้เคียงที่สุดกับจุดกำเนิดบนรูปร่างผลลัพธ์ เนื่องจากระยะทางถึงจุดนี้คือระยะห่างระหว่างรูปร่างทั้งสองดั้งเดิม เราเลือกจุด v ใน A⊖B ซึ่งจะเป็นการประมาณระยะทางของเรา นอกจากนี้เรายังกำหนดชุดจุดว่าง W ซึ่งจะประกอบด้วยจุดในการทดสอบซิมเพล็กซ์ปัจจุบัน

จากนั้นเราเข้าสู่วง เราเริ่มต้นด้วยการรับจุดสนับสนุน w = s A⊖B (- v ) จุดบน A⊖B ซึ่งการฉายภาพลงบน v นั้นอยู่ใกล้กับจุดกำเนิดมากที่สุด

ถ้า || w || ไม่ต่างจาก || . มากนัก วี || และมุมระหว่างพวกเขาไม่ได้เปลี่ยนแปลงมากนัก (ตามค่าความคลาดเคลื่อนที่กำหนดบางอย่าง) หมายความว่าอัลกอริธึมมาบรรจบกันและเราสามารถส่งคืน || วี || เป็นระยะทาง

มิฉะนั้นเราจะเพิ่ม w ให้กับ W หากเปลือกนูนของ W (นั่นคือ ซิมเพล็กซ์) มีจุดกำเนิด รูปร่างจะตัดกัน และนี่ก็หมายความว่าเราทำเสร็จแล้ว มิฉะนั้น เราจะพบจุดในช่องซิมเพล็กซ์ที่ใกล้กับจุดกำเนิดมากที่สุด จากนั้นเรารีเซ็ต v ให้เป็นค่าประมาณใหม่ที่ใกล้เคียงที่สุด สุดท้าย เราลบจุดใดก็ตามใน W ที่ไม่เกี่ยวข้องกับการคำนวณจุดที่ใกล้เคียงที่สุด (ตัวอย่างเช่น ถ้าเรามีสามเหลี่ยมและจุดที่ใกล้ที่สุดกับจุดกำเนิดอยู่ที่ขอบด้านใดด้านหนึ่ง เราสามารถลบจุดจาก W ที่ไม่ใช่จุดยอดของขอบนี้ได้) จากนั้นเราทำซ้ำขั้นตอนเดียวกันนี้จนกว่าอัลกอริธึม บรรจบกัน

ภาพถัดไปแสดงตัวอย่างการทำซ้ำสี่ขั้นตอนของอัลกอริทึม GJK วัตถุสีน้ำเงินแสดงถึงความแตกต่างของ Minkowski A⊖B และเวกเตอร์สีเขียวคือ v คุณสามารถดูได้ที่นี่ว่า v หาจุดที่ใกล้ที่สุดกับจุดกำเนิดได้อย่างไร

สำหรับคำอธิบายโดยละเอียดและเชิงลึกของอัลกอริทึม GJK โปรดดูบทความ A Fast and Robust GJK Implementation for Collision Detection of Convex Objects โดย Gino van den Bergen บล็อกสำหรับกลไกฟิสิกส์ dyn4j ยังมีโพสต์ที่ยอดเยี่ยมเกี่ยวกับ GJK

Box2D มีการนำอัลกอริทึม GJK ไปใช้ใน b2Distance.cpp ในฟังก์ชัน b2Distance ใช้เฉพาะ GJK ในช่วงเวลาของการคำนวณผลกระทบในอัลกอริทึมสำหรับการตรวจจับการชนกันอย่างต่อเนื่อง (หัวข้อที่เราจะกล่าวถึงในรายละเอียดเพิ่มเติม)

เอ็นจิ้นฟิสิกส์ Chimpunk ใช้ GJK สำหรับการตรวจจับการชนทั้งหมด และการใช้งานอยู่ใน cpCollision.c ในฟังก์ชัน GJK หากอัลกอริธึม GJK รายงานทางแยก ก็ยังจำเป็นต้องรู้ว่าจุดสัมผัสคืออะไร พร้อมกับความลึกในการเจาะ ในการทำเช่นนั้น มันใช้อัลกอริธึม Expanding Polytope ซึ่งเราจะสำรวจต่อไป

การกำหนดความลึกการเจาะ - อัลกอริธึม Polytope ที่ขยายออก

ตามที่ระบุไว้ข้างต้น หากรูปร่าง A และ B ตัดกัน GJK จะสร้าง W ด้านเดียวที่มีจุดกำเนิดภายในความแตกต่างของ Minkowski A⊖B ในขั้นตอนนี้ เรารู้เพียงว่ารูปร่างตัดกัน แต่ในการออกแบบระบบตรวจจับการชนกันหลายๆ ระบบ นับว่าเป็นที่พึงปรารถนาที่จะคำนวณว่าเรามีทางแยกมากน้อยเพียงใด และจุดใดที่เราสามารถใช้เป็นจุดสัมผัสได้ ดังนั้น เราจัดการกับการชนกันอย่างสมจริง Expanding Polytope Algorithm (EPA) ช่วยให้เราได้รับข้อมูลดังกล่าว โดยเริ่มต้นจากจุดที่ GJK ค้างไว้: ด้วยซิมเพล็กซ์ที่มีจุดกำเนิด

ความลึกของการเจาะ คือความยาวของ เวกเตอร์การแปลขั้นต่ำ (MTV) ซึ่งเป็นเวกเตอร์ที่เล็กที่สุดซึ่งเราสามารถแปลรูปร่างที่ตัดกันเพื่อแยกรูปร่างออกจากรูปร่างอื่น

เมื่อรูปร่างทั้งสองตัดกัน ความแตกต่าง Minkowski ของพวกมันจะมีจุดกำเนิด และจุดบนขอบเขตของความแตกต่าง Minkowski ที่ใกล้กับจุดกำเนิดมากที่สุดคือ MTV อัลกอริธึม EPA ค้นหาจุดนั้นโดยการขยายซิมเพล็กซ์ที่ GJK ให้เราเป็นรูปหลายเหลี่ยม แบ่งขอบของมันตามลำดับด้วยจุดยอดใหม่

อันดับแรก เราพบขอบของซิมเพล็กซ์ที่ใกล้กับจุดกำเนิดมากที่สุด และคำนวณจุดสนับสนุนในส่วนต่างของ Minkowski ในทิศทางที่เป็นปกติกับขอบ จากนั้นเราแยกส่วนขอบนี้โดยเพิ่มจุดสนับสนุนนี้เข้าไป เราทำซ้ำขั้นตอนเหล่านี้จนกว่าความยาวและทิศทางของเวกเตอร์จะไม่เปลี่ยนแปลงมากนัก เมื่ออัลกอริทึมมาบรรจบกัน เราก็มี MTV และความลึกในการเจาะ

การใช้ GJK ร่วมกับ EPA ทำให้เราได้คำอธิบายโดยละเอียดของการชนกัน ไม่ว่าวัตถุจะตัดกันอยู่แล้ว หรืออยู่ใกล้พอที่จะถือว่าเป็นการชนกัน

อัลกอริทึม EPA ได้อธิบายไว้ในบทความ Proximity Queries และ Penetration Depth Computation on 3D Game Objects ซึ่งเขียนโดย Gino van den Bergen ด้วย บล็อก dyn4j ยังมีโพสต์เกี่ยวกับ EPA

การตรวจจับการชนกันอย่างต่อเนื่อง

เทคนิคฟิสิกส์ของวิดีโอเกมที่นำเสนอจนถึงขณะนี้ทำการตรวจจับการชนกันสำหรับสแน็ปช็อตแบบคงที่ของการจำลอง สิ่งนี้เรียกว่า การตรวจจับการชนแบบไม่ต่อเนื่อง และจะไม่สนใจสิ่งที่เกิดขึ้นระหว่างขั้นตอนก่อนหน้าและปัจจุบัน ด้วยเหตุนี้ จึงอาจตรวจไม่พบการชนกันโดยเฉพาะอย่างยิ่งสำหรับวัตถุที่เคลื่อนที่เร็ว ปัญหานี้เรียกว่าการ ขุดอุโมงค์

เทคนิคการตรวจจับการชนกันอย่างต่อเนื่องพยายามค้นหา เมื่อ วัตถุสองชิ้นชนกันระหว่างขั้นตอนก่อนหน้าและขั้นตอนปัจจุบันของการจำลอง พวกเขาคำนวณ เวลาที่กระทบ เพื่อให้เราสามารถย้อนเวลากลับไปและประมวลผลการชน ณ จุดนั้นได้

เวลาที่กระทบ (หรือเวลาที่สัมผัส) t c คือช่วงเวลาที่ระยะห่างระหว่างวัตถุสองชิ้นเป็นศูนย์ หากเราสามารถเขียนฟังก์ชันสำหรับระยะห่างระหว่างวัตถุทั้งสองตามเวลา สิ่งที่เราต้องการค้นหาคือรูทที่เล็กที่สุดของฟังก์ชันนี้ ดังนั้น เวลาของการคำนวณผลกระทบจึงเป็น ปัญหาในการค้นหาราก

สำหรับเวลาของการคำนวณผลกระทบ เราจะพิจารณาสถานะ (ตำแหน่งและทิศทาง) ของร่างกายในขั้นตอนก่อนหน้า ณ เวลา t ผม -1 และในขั้นตอนปัจจุบัน ณ เวลา t ผม เพื่อให้ง่ายขึ้น เราถือว่าการเคลื่อนที่เชิงเส้นระหว่างขั้นตอนต่างๆ

เรามาลดความซับซ้อนของปัญหาโดยสมมติว่ารูปร่างเป็นวงกลม สำหรับวงกลมสองวง C 1 และ C 2 ที่มีรัศมี r 1 และ r 2 โดยที่จุดศูนย์กลางมวล x 1 และ x 2 ตรงกับเซนทรอยด์ (กล่าวคือ โดยธรรมชาติจะหมุนรอบจุดศูนย์กลางมวล) เราสามารถเขียนฟังก์ชันระยะทาง เช่น:

เมื่อพิจารณาการเคลื่อนที่เชิงเส้นระหว่างขั้นตอน เราสามารถเขียนฟังก์ชันต่อไปนี้สำหรับตำแหน่งของ C 1 จาก ti -1 ถึง t i

เป็นการประมาณค่าเชิงเส้นตั้งแต่ x 1 ( ti -1 ) ถึง x 1 ( t i ) สามารถทำได้เช่นเดียวกันสำหรับ x 2 สำหรับช่วงเวลานี้ เราสามารถเขียนฟังก์ชันระยะทางอื่น:

ตั้งค่านิพจน์นี้ให้เท่ากับศูนย์ แล้วคุณจะได้สมการกำลังสองบน t สามารถหารากได้โดยตรงโดยใช้สูตรกำลังสอง ถ้าวงกลมไม่ตัดกัน สูตรกำลังสองจะไม่มีคำตอบ หากเป็นเช่นนั้น อาจส่งผลให้มีหนึ่งหรือสองราก หากมีเพียงรูทเดียว ค่านั้นก็คือเวลาที่กระทบ หากมีสองราก ส่วนที่เล็กที่สุดคือเวลาที่กระทบ และอีกอันคือเวลาที่วงกลมแยกออกจากกัน โปรดทราบว่าเวลาที่กระทบที่นี่เป็นตัวเลขตั้งแต่ 0 ถึง 1 ไม่ใช่เวลาในหน่วยวินาที มันเป็นเพียงตัวเลขที่เราสามารถใช้เพื่อสอดแทรกสถานะของวัตถุไปยังตำแหน่งที่แม่นยำที่เกิดการชนกัน

การตรวจจับการชนกันอย่างต่อเนื่องสำหรับวัตถุที่ไม่ใช่วงกลม

การเขียนฟังก์ชันระยะทางสำหรับรูปร่างประเภทอื่นๆ นั้นยาก โดยหลักแล้วเนื่องจากระยะห่างขึ้นอยู่กับทิศทาง ด้วยเหตุผลนี้ เรามักใช้อัลกอริธึมแบบวนซ้ำที่ย้ายออบเจ็กต์เข้ามาใกล้มากขึ้นเรื่อยๆ ในการวนซ้ำแต่ละครั้ง จนกว่าพวกมันจะ อยู่ใกล้พอ ที่จะถูกพิจารณาว่าชนกัน

อัลกอริธึม ความก้าวหน้าแบบอนุรักษ์นิยม จะเคลื่อนตัวไปข้างหน้า (และหมุนพวกมัน) ซ้ำ ๆ ในการวนซ้ำแต่ละครั้งจะคำนวณขอบเขตบนสำหรับการกระจัด อัลกอริทึมดั้งเดิมถูกนำเสนอในวิทยานิพนธ์ระดับปริญญาเอกของ Brian Mirtich (หัวข้อ 2.3.2) ซึ่งพิจารณาการเคลื่อนที่ของวัตถุ บทความนี้โดย Erwin Coumans (ผู้เขียน Bullet Physics Engine) นำเสนอเวอร์ชันที่ง่ายกว่าซึ่งใช้ความเร็วเชิงเส้นและความเร็วเชิงมุมคงที่

อัลกอริทึมจะคำนวณจุดที่ใกล้เคียงที่สุดระหว่างรูปร่าง A และ B วาดเวกเตอร์จากจุดหนึ่งไปยังอีกจุดหนึ่ง และฉายภาพความเร็วบนเวกเตอร์นี้เพื่อคำนวณขอบเขตบนสำหรับการเคลื่อนที่ รับรองได้ว่าไม่มีจุดใดบนร่างกายที่จะเคลื่อนไหวเกินกว่าที่คาดการณ์ไว้ จากนั้นจะเคลื่อนตัวไปข้างหน้าตามจำนวนนี้และทำซ้ำจนกว่าระยะทางจะตกอยู่ภายใต้ค่าความคลาดเคลื่อนเล็กน้อย

ในบางกรณีอาจต้องใช้การวนซ้ำหลายครั้งเกินไป ตัวอย่างเช่น เมื่อความเร็วเชิงมุมของวัตถุตัวใดตัวหนึ่งสูงเกินไป

การแก้ปัญหาการชนกัน

เมื่อตรวจพบการชนกันแล้ว จำเป็นต้องเปลี่ยนการเคลื่อนที่ของวัตถุที่ชนกันในลักษณะที่สมจริง เช่น ทำให้วัตถุกระเด็นออกจากกัน ในตอนต่อไปและตอนสุดท้ายของทฤษฎีนี้ เราจะพูดถึงวิธีการยอดนิยมบางวิธีในการแก้ปัญหาการชนกันในวิดีโอเกม

อ้างอิง

หากคุณสนใจที่จะเข้าใจอย่างลึกซึ้งยิ่งขึ้นเกี่ยวกับฟิสิกส์การชนกัน เช่น อัลกอริธึมและเทคนิคการตรวจจับการชน หนังสือ Real-Time Collision Detection โดย Christer Ericson เป็นสิ่งที่ต้องมี

เนื่องจากการตรวจจับการชนนั้นอาศัยรูปทรงเรขาคณิตเป็นอย่างมาก บทความของ Toptal Computational Geometry ใน Python: From Theory to Application จึงเป็นการแนะนำหัวข้อที่ยอดเยี่ยม