Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ขั้นตอนวิธีการตรวจสอบการชน (อังกฤษ: Collision detection) เป็นขั้นตอนวิธีที่ใช้จำลองการชนกันของวัตถุตั้งแต่ 2 ชิ้นขึ้นไป โดยส่วนมากจะพบได้ในวิดีโอเกมหรือการจำลองระบบของวัตถุ และยังใช้ในวิทยาการหุ่นยนต์ด้วย ในการตัดสินใจว่าวัตถุสองชิ้นชนกันหรือไม่นั้น ขั้นตอนวีธีการตรวจสอบการชนจะต้องคำนวณเวลาที่จะเกิดการชน (time of impact-TOI) และสามารถระบุพิกัดส่วนที่ชนกันได้ (contact manifold) การจำลองการชนกันของวัตถุโดยหลักแล้วจะใช้หลักการจาก พีชคณิตเชิงเส้น (linear algebra) และ
การอธิบายขั้นตอนวิธี
โดยส่วนมากการจำลองการชนกันของระบบของวัตถุจะเกิดขึ้นในสองลักษณะคือ การชนนั้นถูกตรวจพบหลังจากที่มีการชนเกิดขึ้นจริง (posteriori, discrete) และการชนที่ถูกตรวจพบก่อนที่มีการชนเกิดขึ้น (priori, continuous)
- ในระบบ posteriori จะปล่อยให้วัตถุต่าง ๆ เคลื่อนที่ไปในระยะเวลาอันสั้น แล้วเช็คว่ามีวัตถุสองชิ้นใด ๆ หรือไม่ที่ชนกัน (การอินเตอร์เซคกันของวัตถุ) หรือวัตถุอาจอยู่ใกล้กันมากจนถือว่าเกิดการชนขึ้น ในแต่ละขั้นของการจำลองเหตุการณ์ จะมีรายการของวัตถุที่อินเตอร์เซคกัน ซึ่งตำแหน่งและวิถีการเดินทางของวัตถุเหล่านี้จะถูกกำหนดไว้อย่างแน่นอนแล้วสำหรับการคำนวณการชน เราเรียกระบบนี้ว่า posteriori เพราะว่าส่วนมากเราจะพลาดการชนกันของวัตถุจริง ๆ ไป แล้วค้นพบการชนหลังจากที่การชนนั้นเกิดขึ้นจริง
- ในระบบ priori นั้นเป็นขั้นตอนวิธีการตรวจสอบการชนที่สามารถพยากรณ์วิถีการเดินทางและเวลาขณะที่เกิดการชนของวัตถุได้อย่างแม่นยำ วัตถุเหล่านั้นจะไม่เคลื่อนที่ผ่านกันจริง ๆ (interpenetrate) เราเรียกระบบนี้ว่า priori เพราะว่าเราสามารถคำนวณเวลาขณะที่เกิดการชนของวัตถุได้ก่อนที่จะปรับข้อมูลของวัตถุนั้น ๆ
คอมพิวเตอร์จะมองวัตถุเป็นรูปหลายเหลี่ยม (polygons) การจะค้นหาว่ามีรูปหลายเหลี่ยมสองรูปชนกันหรือไม่นั้นทำได้ยากและเสียเวลา หนึ่งในวิธีที่ง่ายและมีประสิทธิภาพมากกว่าคือ กำหนดทรงกลมล้อมที่รอบรูปหลายเหลี่ยมได้พอดี แล้วตรวจสอบว่าทรงกลมสองอันทับซ้อนกันหรือไม่ ด้วยการคำนวณว่าระยะห่างระหว่างจุดศูนย์กลางทรงกลมสองอันน้อยกว่ารัศมีของทรงกลมทั้งสองบวกกันหรือไม่ ( (x1-x2) 2 + (y1-y2) 2 + (z1-z2) 2 ≤ r12 + r22) เท่านั้น ถ้าน้อยกว่าแสดงว่ามีการชนเกิดขึ้น แต่การแทนวัตุทั้งก้อนด้วยทรงกลมนั้นทำให้เกิดความคลาดเคลื่อนค่อนข้างมาก เมื่อตรวจพบว่าทรงกลมสองอันใด ๆ ชน (อินเตอร์เซค) กัน วัตถุนั้นอาจไม่ได้ชนกันจริง ๆ เพื่อความแม่นยำมากขึ้นจึงแบ่งทรงกลมที่ล้อมรอบวัตถุทั้งก้อน เป็นทรงกลมเล็ก ๆ ที่มีขนาดใกล้เคียงกับวัตถุนั้น ๆ แล้วตรวจสอบแต่ละอันว่าอินเตอร์เซคกันอีกหรือไม่ ถ้าพบว่ามีการชนเกิดขึ้น (อินเตอร์เซคกัน) ก็อาจแบ่งทรงกลมให้เล็กลงไปอีก เพื่อตรวจสอบการชน (อินเตอร์เซค) ต่อไป ทั้งนี้ขึ้นอยู่กับว่าต้องการความแม่นยำมากแค่ไหน ซึ่งก็ต้องแลกมาด้วยเวลาเช่นกัน
แต่เนื่องจากวัตถุส่วนใหญ่ในวิดีโอเกมเป็นรูปสี่เหลี่ยม จึงอาจจะใช้รูปสี่เหลี่ยมแทนทรงกลมในการประมาณรูปร่างของวัตถุ เรียกวิธีการนี้ว่า กล่องล้อมรอบที่จัดเรียงตามแนวแกน (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 (N2) เนื่องจากมีวัตถุที่ต้องตรวจสอบ N ชิ้น เลือกมา 2 ชิ้นคือ (N choose 2) = (N!) / (2!* (N-2) !) = N* (N-1) * (N-2) !/2* (N-2) ! = N* (N-1) /2 ≈ N2 อย่างไรก็ตาม มีขั้นตอนวิธีที่สามารถปรับปรุงเวลาการทำงานให้ดีขึ้นได้ดังที่กล่าวไว้ในการอธิบายขั้นตอนวิธี ทำให้ได้ประสิทธิภาพการทำงานที่ดีที่สุดเป็น 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 2011-03-17 ที่ เวย์แบ็กแมชชีน
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
khntxnwithikartrwcsxbkarchn xngkvs Collision detection epnkhntxnwithithiichcalxngkarchnknkhxngwtthutngaet 2 chinkhunip odyswnmakcaphbidinwidioxekmhruxkarcalxngrabbkhxngwtthu aelayngichinwithyakarhunyntdwy inkartdsinicwawtthusxngchinchnknhruximnn khntxnwithikartrwcsxbkarchncatxngkhanwnewlathicaekidkarchn time of impact TOI aelasamarthrabuphikdswnthichnknid contact manifold karcalxngkarchnknkhxngwtthuodyhlkaelwcaichhlkkarcak phichkhnitechingesn linear algebra aelakarxthibaykhntxnwithiodyswnmakkarcalxngkarchnknkhxngrabbkhxngwtthucaekidkhuninsxnglksnakhux karchnnnthuktrwcphbhlngcakthimikarchnekidkhuncring posteriori discrete aelakarchnthithuktrwcphbkxnthimikarchnekidkhun priori continuous inrabb posteriori caplxyihwtthutang ekhluxnthiipinrayaewlaxnsn aelwechkhwamiwtthusxngchinid hruximthichnkn karxinetxreskhknkhxngwtthu hruxwtthuxacxyuiklknmakcnthuxwaekidkarchnkhun inaetlakhnkhxngkarcalxngehtukarn camiraykarkhxngwtthuthixinetxreskhkn sungtaaehnngaelawithikaredinthangkhxngwtthuehlanicathukkahndiwxyangaennxnaelwsahrbkarkhanwnkarchn eraeriykrabbniwa posteriori ephraawaswnmakeracaphladkarchnknkhxngwtthucring ip aelwkhnphbkarchnhlngcakthikarchnnnekidkhuncring inrabb priori nnepnkhntxnwithikartrwcsxbkarchnthisamarthphyakrnwithikaredinthangaelaewlakhnathiekidkarchnkhxngwtthuidxyangaemnya wtthuehlanncaimekhluxnthiphankncring interpenetrate eraeriykrabbniwa priori ephraawaerasamarthkhanwnewlakhnathiekidkarchnkhxngwtthuidkxnthicaprbkhxmulkhxngwtthunn khxmphiwetxrcamxngwtthuepnruphlayehliym polygons karcakhnhawamiruphlayehliymsxngrupchnknhruximnnthaidyakaelaesiyewla hnunginwithithingayaelamiprasiththiphaphmakkwakhux kahndthrngklmlxmthirxbruphlayehliymidphxdi aelwtrwcsxbwathrngklmsxngxnthbsxnknhruxim dwykarkhanwnwarayahangrahwangcudsunyklangthrngklmsxngxnnxykwarsmikhxngthrngklmthngsxngbwkknhruxim x1 x2 2 y1 y2 2 z1 z2 2 r12 r22 ethann thanxykwaaesdngwamikarchnekidkhun aetkaraethnwtuthngkxndwythrngklmnnthaihekidkhwamkhladekhluxnkhxnkhangmak emuxtrwcphbwathrngklmsxngxnid chn xinetxreskh kn wtthunnxacimidchnkncring ephuxkhwamaemnyamakkhuncungaebngthrngklmthilxmrxbwtthuthngkxn epnthrngklmelk thimikhnadiklekhiyngkbwtthunn aelwtrwcsxbaetlaxnwaxinetxreskhknxikhruxim thaphbwamikarchnekidkhun xinetxreskhkn kxacaebngthrngklmihelklngipxik ephuxtrwcsxbkarchn xinetxreskh txip thngnikhunxyukbwatxngkarkhwamaemnyamakaekhihn sungktxngaelkmadwyewlaechnkn aetenuxngcakwtthuswnihyinwidioxekmepnrupsiehliym cungxaccaichrupsiehliymaethnthrngklminkarpramanruprangkhxngwtthu eriykwithikarniwa klxnglxmrxbthicderiyngtamaenwaekn axis aligned bounding boxes AABBs hrux xxkhthris octrees cderiyngtamaenwaekn hmaykhwamwaklxngnnkhnankbaekninrabbphikdchaksammiti hruxaetladankhxngklxngtngchakkbaeknhnung caknneracungna AABBs khxngaetlawtthuipsrangepn tnimAABBs ephuxichepntwtrwcsxbwaekidkarchnkhunhruxim dwykarethiybklxnginpmrakkhxngtnimsxngtn waxinetxreskhknhruxim thaichkmioxkasthiwtthucachnkn cungthakartrwcsxbtxipdwykareriyksalngiptamtnimcnthungibkhxngmn ephuxhawaswnihnthiehluxmlakn dwykaroprecktklxngthngsxnglngbnaeknhnung aelwtrwcsxbwamichwngthisxbthbknhruxim withikarnieriykwathvsdibthkaraeykcakknbnaekn Separating Axis Theorem cakthvsdibthnithaihthrabwa mikaraeykcakknbnaeknephiyng 15 aebbethann thakarehluxmlaknekidkhuninthuk karaeykcakknbnaekn hmaykhwamwaklxngthngsxngnnxinetxreskhkn hmaykhwamwamikarchnekidkhunnnexng pyhathieraphicarnaxyuniekiywkhxngkbkarekidkarchnknkhxngwtthuinchwngewlathikahndhruxim thaiskhwamerwihkboprecktchnkhxngklxng aelwekidkarehluxmlaknkhrbthng 15 aebb aesdngwamikarchnknekidkhun xikthngyngsamarthichokhrngsrangkhxmulthikhlaykhlungkbtnimAABBs ephuxaeykklumkhxngsingthichnxxkcakklumkhxngsingthithukchn aelwtrwcsxbwamioxkashruximthicaekidkarchnkn karkhanwntamlksnanisamarthkhdaeykwtthuthiimekidkarchnidxyangrwderw sungmiprasiththiphaphkarthanganxyuthi O NlogN khntxnwithithiekiywkhxngkhntxnwithitang thiekiywkhxngkbkhntxnwithikartrwcsxbkarchnodyswnmak caepnkhntxnwithithiichtrwcsxbephimetimephuxihkartrwcsxbkarchnepnipxyangaemnyathisud Optimization dngni karichpraoychncakkarxyutidknxyangchwkhrawkhxngwtthu Exploiting temporal coherence karkhdkrxngkhuwtthuid Pairwise pruning kartrwcsxbkarchnkhxngkhuwtthuhnung Exact pairwise collision detection karkhdkrxngkxntrwcsxb A priori pruning karaebngodyphunthi Spatial partitioning rhsethiymaesdngkarthangan 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 gt 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 gt bool foreach polygon p1 in e1 foreach polygon p2 in e2 if polygons intersect p1 p2 then return true return falsekarwiekhraahkhwamsbsxnechingewlakhntxnwithikartrwcsxbkarchnnnmiprasiththiphaphinkarthanganechingewlaepn O N2 enuxngcakmiwtthuthitxngtrwcsxb N chin eluxkma 2 chinkhux N choose 2 N 2 N 2 N N 1 N 2 2 N 2 N N 1 2 N2 xyangirktam mikhntxnwithithisamarthprbprungewlakarthanganihdikhuniddngthiklawiwinkarxthibaykhntxnwithi thaihidprasiththiphaphkarthanganthidithisudepn O NlogN xangxingS 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 2011 03 17 thi ewyaebkaemchchin