ขั้นตอนวิธีการตรวจสอบการชน

ขั้นตอนวิธีการตรวจสอบการชน (อังกฤษ: Collision detection) เป็นขั้นตอนวิธีที่ใช้จำลองการชนกันของวัตถุตั้งแต่ 2 ชิ้นขึ้นไป โดยส่วนมากจะพบได้ในวิดีโอเกมหรือการจำลองระบบของวัตถุ และยังใช้ในวิทยาการหุ่นยนต์ด้วย ในการตัดสินใจว่าวัตถุสองชิ้นชนกันหรือไม่นั้น ขั้นตอนวีธีการตรวจสอบการชนจะต้องคำนวณเวลาที่จะเกิดการชน (time of impact-TOI) และสามารถระบุพิกัดส่วนที่ชนกันได้ (contact manifold) การจำลองการชนกันของวัตถุโดยหลักแล้วจะใช้หลักการจาก พีชคณิตเชิงเส้น (linear algebra) และเรขาคณิตเชิงคำนวณ

การอธิบายขั้นตอนวิธี

โดยส่วนมากการจำลองการชนกันของระบบของวัตถุจะเกิดขึ้นในสองลักษณะคือ การชนนั้นถูกตรวจพบหลังจากที่มีการชนเกิดขึ้นจริง (posteriori, discrete) และการชนที่ถูกตรวจพบก่อนที่มีการชนเกิดขึ้น (priori, continuous)

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

คอมพิวเตอร์จะมองวัตถุเป็นรูปหลายเหลี่ยม (polygons) การจะค้นหาว่ามีรูปหลายเหลี่ยมสองรูปชนกันหรือไม่นั้นทำได้ยากและเสียเวลา หนึ่งในวิธีที่ง่ายและมีประสิทธิภาพมากกว่าคือ กำหนดทรงกลมล้อมที่รอบรูปหลายเหลี่ยมได้พอดี แล้วตรวจสอบว่าทรงกลมสองอันทับซ้อนกันหรือไม่ ด้วยการคำนวณว่าระยะห่างระหว่างจุดศูนย์กลางทรงกลมสองอันน้อยกว่ารัศมีของทรงกลมทั้งสองบวกกันหรือไม่ ( (x₁-x₂) ² + (y₁-y₂) ² + (z₁-z₂) ² ≤ r₁² + r₂²) เท่านั้น ถ้าน้อยกว่าแสดงว่ามีการชนเกิดขึ้น แต่การแทนวัตุทั้งก้อนด้วยทรงกลมนั้นทำให้เกิดความคลาดเคลื่อนค่อนข้างมาก เมื่อตรวจพบว่าทรงกลมสองอันใด ๆ ชน (อินเตอร์เซค) กัน วัตถุนั้นอาจไม่ได้ชนกันจริง ๆ เพื่อความแม่นยำมากขึ้นจึงแบ่งทรงกลมที่ล้อมรอบวัตถุทั้งก้อน เป็นทรงกลมเล็ก ๆ ที่มีขนาดใกล้เคียงกับวัตถุนั้น ๆ แล้วตรวจสอบแต่ละอันว่าอินเตอร์เซคกันอีกหรือไม่ ถ้าพบว่ามีการชนเกิดขึ้น (อินเตอร์เซคกัน) ก็อาจแบ่งทรงกลมให้เล็กลงไปอีก เพื่อตรวจสอบการชน (อินเตอร์เซค) ต่อไป ทั้งนี้ขึ้นอยู่กับว่าต้องการความแม่นยำมากแค่ไหน ซึ่งก็ต้องแลกมาด้วยเวลาเช่นกัน

แต่เนื่องจากวัตถุส่วนใหญ่ในวิดีโอเกมเป็นรูปสี่เหลี่ยม จึงอาจจะใช้รูปสี่เหลี่ยมแทนทรงกลมในการประมาณรูปร่างของวัตถุ เรียกวิธีการนี้ว่า กล่องล้อมรอบที่จัดเรียงตามแนวแกน (axis-aligned bounding boxes-AABBs) หรือ ออคทรีส์ (octrees) "จัดเรียงตามแนวแกน" หมายความว่ากล่องนั้นขนานกับแกนในระบบพิกัดฉากสามมิติ หรือแต่ละด้านของกล่องตั้งฉากกับแกนหนึ่ง ๆ

จากนั้นเราจึงนำ AABBs ของแต่ละวัตถุไปสร้างเป็น ต้นไม้AABBs เพื่อใช้เป็นตัวตรวจสอบว่าเกิดการชนขึ้นหรือไม่ ด้วยการเทียบกล่องในปมรากของต้นไม้สองต้น ว่าอินเตอร์เซคกันหรือไม่ ถ้าใช่ก็มีโอกาสที่วัตถุจะชนกัน จึงทำการตรวจสอบต่อไปด้วยการเรียกซ้ำลงไปตามต้นไม้จนถึงใบของมัน เพื่อหาว่าส่วนไหนที่เหลื่อมล้ำกัน ด้วยการโปรเจกต์กล่องทั้งสองลงบนแกนหนึ่ง ๆ แล้วตรวจสอบว่ามีช่วงที่ซ้อบทับกันหรือไม่ วิธีการนี้เรียกว่าทฤษฎีบทการแยกจากกันบนแกน (Separating Axis Theorem) จากทฤษฎีบทนี้ทำให้ทราบว่า มีการแยกจากกันบนแกนเพียง 15 แบบเท่านั้น ถ้าการเหลื่อมล้ำกันเกิดขึ้นในทุก ๆ การแยกจากกันบนแกน หมายความว่ากล่องทั้งสองนั้นอินเตอร์เซคกัน หมายความว่ามีการชนเกิดขึ้นนั่นเอง

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

ขั้นตอนวิธีที่เกี่ยวข้อง

ขั้นตอนวิธีต่าง ๆ ที่เกี่ยวข้องกับขั้นตอนวิธีการตรวจสอบการชนโดยส่วนมาก จะเป็นขั้นตอนวิธีที่ใช้ตรวจสอบเพิ่มเติมเพื่อให้การตรวจสอบการชนเป็นไปอย่างแม่นยำที่สุด (Optimization) ดังนี้

• การใช้ประโยชน์จากการอยู่ติดกันอย่างชั่วคราวของวัตถุ (Exploiting temporal coherence)
• การคัดกรองคู่วัตถุใด ๆ (Pairwise pruning)
• การตรวจสอบการชนของคู่วัตถุหนึ่ง (Exact pairwise collision detection)
• การคัดกรองก่อนตรวจสอบ (A priori pruning)
• การแบ่งโดยพื้นที่ (Spatial partitioning)

รหัสเทียมแสดงการทำงาน

//Extremely Simplified Game Loop  while (1) { process_input (); update_objects (); render_world (); }  update_objects () { for (each_object) save_old_position (); calc new_object_position {based on velocity accel. etc.} if (collide_with_other_objects () ) new_object_position = old_position (); {or if destroyed object remove it etc.} } 

while the game is running: foreach entity in the world update (entity)  update (entity) : entity.old_position := entity.current_position modify entity.current_position based on entity.velocity and other factors if Colliding (entity) then entity.current_position := entity.old_position  Colliding (current_entity) -> bool: foreach entity in the world if entity != current_entity then if Entities_Collide (current_entity, entity) then return true return false  Entities_Collide (e1, e2) -> bool: foreach polygon p1 in e1 foreach polygon p2 in e2 if polygons_intersect (p1, p2) then return true return false 

การวิเคราะห์ความซับซ้อนเชิงเวลา

ขั้นตอนวิธีการตรวจสอบการชนนั้นมีประสิทธิภาพในการทำงานเชิงเวลาเป็น O (N²) เนื่องจากมีวัตถุที่ต้องตรวจสอบ N ชิ้น เลือกมา 2 ชิ้นคือ (N choose 2) = (N!) / (2!* (N-2) !) = N* (N-1) * (N-2) !/2* (N-2) ! = N* (N-1) /2 ≈ N² อย่างไรก็ตาม มีขั้นตอนวิธีที่สามารถปรับปรุงเวลาการทำงานให้ดีขึ้นได้ดังที่กล่าวไว้ในการอธิบายขั้นตอนวิธี ทำให้ได้ประสิทธิภาพการทำงานที่ดีที่สุดเป็น O (NlogN)

อ้างอิง

• S. Gottschalk. Separating Axis Theorem, TR96-024, UNC Chapel Hill, 1990.
  
• N. Greene. “Detecting intersection of a rectangular solid and a convex polyhedron, ” Graphics Gems IV. Academic Press, 1994. introduces several techniques that speed up the overlap computation of a box and a convex polyhedron.
  
• For more information about AABBs take a look at J. Arvo and D. Kirk. “A survey of ray tracing acceleration techniques, ” An Introduction to Ray Tracing. Academic Press, 1989.
  
• http://www.gamedev.net/page/resources/_/reference/programming/game-programming/collision-detection/practical-collision-detection-r736