Соқтығысуды анықтау: Есептеу геометриясы және қолданыстары

Кіріспе

Компьютерлік геометрияда соқтығысуды анықтау

Соқтығысуды анықтау – екі немесе одан көп кеңістіктік нысандардың, көбінесе компьютерлік графика нысандарының, қиылысын анықтаудың есептеулік мәселесі. Ол түрлі есептеу салаларында қолданылады, ең бастысы – компьютерлік графика, компьютерлік ойындар, компьютерлік модельдеу, робототехника және есептеу физикасы. Соқтығысуды анықтау – есептеу геометриясының классикалық мәселесі. Соқтығысуды анықтау алгоритмдерін 2D немесе 3D кеңістіктік нысандармен жұмыс істеуге қарай бөлуге болады.

Шолу

Физикалық симуляция кезінде бильярд ойнау сияқты тәжірибелер жүргізіледі. Бильярд шарларының физикасы қатты денелердің қозғалысы және серпімді соқтығысулар аясында жақсы түсініледі. Бірінші кезде, бильярд үстелі мен шарлардың өте нақты физикалық сипаттамасы, сондай-ақ барлық шарлардың бастапқы орналасуы беріледі. Кью-допқа күш түсіргенде (вероятно, ойыншының таяқшамен соққаннан туындаған), компьютерлік бағдарлама арқылы барлық шарлардың траекториясын, нақты қозғалысын және соңғы тоқтау орындарын есептеуді қалаймыз. Осы ойынды симуляциялайтын бағдарлама бірнеше бөліктен тұрады, олардың бірі бильярд шарларының арасындағы соқтығысуларды дәл есептеуге жауапты болады. Бұл мысал да нашар жағдайға ие болып шықты: есептеулердегі кез келген кішкентай қате бильярд шарларының соңғы орнын күрт өзгертеді. Видео ойындарда да ұқсас талаптар бар, бірақ маңызды айырмашылықтар да кездеседі. Кейбір компьютерлік симуляциялар нақты физиканы мүмкіндігінше дәл симуляциялауы керек болса, компьютерлік ойындар нақты физиканы қанағаттанарлық түрде, нақты уақытта және тұрақты түрде симуляциялауы керек. Нәтижеде ойыншыларға ұнайтын симуляция болған жағдайда, шарттардан бас тартуға болады.

Компьютерлік модельдегі соқтығысуды анықтау

Физикалық симуляторлар соқтығысуға реакция жасау әдісімен ерекшеленеді. Кейбіреулері күшті есептеу үшін материалдың жұмсақтығын пайдаланады, бұл соқтығысуды келесі уақыт қадамдарында нақты жағдайдағыдай шешеді. Бұл жұмсақ емес материалдар үшін процессорды көп жүктейді. Кейбір симуляторлар соқтығысу уақытын сызықтық интерполяция арқылы бағалайды, симуляцияны кері қайтарады және соқтығысуды сақталу заңдарының абстрактілі әдістерімен есептейді. Ал кейбіреулері соқтығысу уақытын есептеу үшін сызықтық интерполяцияны (Ньютон әдісі) қайталайды, бұл симуляцияның қалған бөлігіне қарағанда әлдеқайда жоғары дәлдікпен жасалады. Соқтығысуды анықтау уақыт байланыстылығын пайдаланады, бұл процессорлық жүктемені күрт арттырмай, тіпті кішкентай уақыт қадамдарын мүмкін етеді, мысалы, әуе трафигін басқаруда. Икемсіз соқтығысудан кейін сығу және тоқтау сияқты арнайы күйлер пайда болуы мүмкін, мысалы, Open Dynamics Engine оларды симуляциялау үшін шектеулерді қолданады. Шектеулер инерциядан және осылайша тұрақсыздықтан сақтайды. Сахналық граф арқылы тоқтауды іске асыру, қателіктердің туындауына жол бермейді. Басқаша айтқанда, физикалық симуляторлар көбінесе екі тәсілдің бірімен жұмыс істейді: соқтығысу a posteriori (соқтығысу болғаннан кейін) немесе a priori (соқтығысу болғанға дейін) анықталады. A posteriori және a priori арасындағы айырмашылықтан басқа, қазіргі заманғы соқтығысуды анықтау алгоритмдерінің барлығы дерлік алгоритмдердің иерархиясына бөлінеді. Көбінесе "дискретті" және "үздіксіз" терминдері, a posteriori және a priori терминдерінен гөрі қолданылады.

Апостериор (дискретті) және априор (тікелей)

Апостериорлық жағдайда физикалық модельдеу шағын қадаммен ілгерілеумен жүзеге асырылады, содан кейін кез келген нысандардың қиылысып жатыр ма, көрінетіндей қиылысып жатыр ма, жоқ па, тексеріледі. Әрбір модельдеу қадамында қиылысатын барлық денелердің тізімі құрылады және осы нысандардың орналасуы мен траекториялары соқтығысуды ескеру үшін «бекітіледі». Бұл әдіс апостериорлық деп аталады, себебі ол әдетте соқтығысудың нақты сәтін жіберіп алады және соқтығысу болғаннан кейін ғана анықтайды. Априорлық әдістерде физикалық денелердің траекториясын өте дәл болжауға қабілетті соқтығысуды анықтау алгоритмі бар. Соқтығысу сәттері жоғары дәлдікпен есептеледі және физикалық денелер ешқашан бір-бірімен араласпайды. Бұл априорлық деп аталады, өйткені соқтығысуды анықтау алгоритмі физикалық денелердің конфигурациясын жаңартпастан бұрын соқтығысу сәттерін есептейді. Апостериорлық әдістердің басты артықшылықтары төмендегідей. Бұл жағдайда соқтығысуды анықтау алгоритміне физикалық айнымалылардың көптеген түрлерін білудің қажеті жоқ; физикалық денелердің қарапайым тізімі алгоритмге беріледі және бағдарлама қиылысатын денелердің тізімін қайтарады. Соқтығысуды анықтау алгоритміне үйкеліс, серпімді соқтығысулар немесе одан да нашар, серпімсіз соқтығысулар және деформацияланатын денелерді түсінудің қажеті жоқ. Сонымен қатар, апостериорлық алгоритмдер априорлық алгоритмдерге қарағанда бір өлшеммен қарапайым. Априорлық алгоритм уақыт айнымалысымен жұмыс істеуі керек, ол апостериорлық мәселеде жоқ. Екінші жағынан, апостериорлық алгоритмдер «бекіту» қадамында қиындықтар тудырады, онда физикалық тұрғыдан дұрыс емес қиылыстарды түзету қажет. Сонымен қатар, егер дискретті қадам тым үлкен болса, соқтығысу байқалмай қалуы мүмкін, нәтижесінде нысан жеткілікті жылдам немесе кішкентай болса, екінші нысан арқылы өтіп кетуі мүмкін. Априорлық алгоритмдердің артықшылықтары – жоғары сенімділік және тұрақтылық. Физикалық модельдеуді соқтығысуды анықтау алгоритмінен бөлу қиын (бірақ толығымен мүмкін емес). Дегенмен, ең қарапайым жағдайларды қоспағанда, екі дененің қай кезде соқтығысатынын алдын ала анықтау мәселесі (кейбір бастапқы деректерді ескере отырып) жабық түрдегі шешімге ие емес – әдетте сандық түбір іздеуші қолданылады. Кейбір нысандар тыныш күйде болады, яғни соқтығысады, бірақ бір-бірінен секірмейді де, бір-біріне енбейді, мысалы, үстелде тұрған құмыра. Барлық жағдайларда тыныш күйдегі байланысқа арнайы қарау қажет: Егер екі нысан соқтығысса (апостериорлық) немесе сырғыса (априорлық) және олардың салыстырмалы қозғалысы белгілі бір шектен төмен болса, үйкеліс тоқтауға айналады және екі нысан да сахна графигінің бір тармағына орналасады.

In the a posteriori case, the physical simulation is advanced by a small step, then checked to see if any objects are intersecting or visibly considered intersecting. At each simulation step, a list of all intersecting bodies is created, and the positions and trajectories of these objects are "fixed" to account for the collision. This method is called a posteriori because it typically misses the actual instant of collision, and only catches the collision after it has actually happened. In the a priori methods, there is a collision detection algorithm which will be able to predict very precisely the trajectories of the physical bodies. The instants of collision are calculated with high precision, and the physical bodies never actually interpenetrate. This is called a priori because the collision detection algorithm calculates the instants of collision before it updates the configuration of the physical bodies. The main benefits of the a posteriori methods are as follows. In this case, the collision detection algorithm need not be aware of the myriad of physical variables; a simple list of physical bodies is fed to the algorithm, and the program returns a list of intersecting bodies. The collision detection algorithm doesn't need to understand friction, elastic collisions, or worse, nonelastic collisions and deformable bodies. In addition, the a posteriori algorithms are in effect one dimension simpler than the a priori algorithms. An a priori algorithm must deal with the time variable, which is absent from the a posteriori problem. On the other hand, a posteriori algorithms cause problems in the "fixing" step, where intersections (which aren't physically correct) need to be corrected. Moreover, if the discrete step is too large, the collision could go undetected, resulting in an object which passes through another if it is sufficiently fast or small. The benefits of the a priori algorithms are increased fidelity and stability. It is difficult (but not completely impossible) to separate the physical simulation from the collision detection algorithm. However, in all but the simplest cases, the problem of determining ahead of time when two bodies will collide (given some initial data) has no closed form solution—a numerical root finder is usually involved. Some objects are in resting contact, that is, in collision, but neither bouncing off, nor interpenetrating, such as a vase resting on a table. In all cases, resting contact requires special treatment: If two objects collide (a posteriori) or slide (a priori) and their relative motion is below a threshold, friction becomes stiction and both objects are arranged in the same branch of the scene graph.

Оңтайландыру

Бірнеше нысанды соқтығысуды анықтаудың ең қарапайым тәсілдері өте баяу. Әр нысанды басқа барлық нысандармен тексеру, әрине, жұмыс істейді, бірақ нысандар саны көп болған жағдайда мұндай әдіс тиімсіз болады. Күрделі геометриясы бар нысандарды әр бетін бір-бірімен тексеру арқылы салыстыру да өте баяу. Сондықтан, осы мәселені жылдамдату үшін көптеген зерттеулер жүргізілді.

Уақытша үйлесімділікті пайдалану

Көптеген қолданбаларда физикалық денелердің конфигурациясы бір уақыт қадамынан келесі қадамға өте аз өзгереді. Көптеген объектілер мүлдем қозғалмауы мүмкін. Алгоритмдер бұрынғы уақыт қадамында жасалған есептеулерді ағымдағы қадамда қайта пайдалануға мүмкіндік береді, нәтижесінде есептеудің жылдам аяқталуын қамтамасыз етеді. Соқтығысуды анықтаудың жалпы мақсаты – потенциалды түрде қиылысатын объектілер жұптарын табу. Осы жұптарға қосымша талдау қажет. Осындай жоғары өнімділік алгоритмді Калифорния университетінің (Беркли) профессоры Минг С. Лин жасады, ол сахнадағы барлық n дене үшін осьтерге сәйкес шектейтін қораптарды пайдалануды ұсынды. Әрбір қорап үш интервалдың көбейтіндісімен сипатталады (мысалы, қорап ). Шектейтін қораптардың соқтығысуын анықтау үшін кең таралған алгоритм – «сыпыру және кесу» әдісі. Екі мұндай қораптың қиылысуы, тек қана егер , және қиылысса ғана болады. Егер және қиылысса, келесі уақыт қадамында да олардың қиылысуы ықтимал. Сол сияқты, егер олар бұрынғы уақыт қадамында қиылыспаса, онда олардың қиылыспауы да ықтимал. Сондықтан, мәселені кадрдан кадрға қай интервалдар қиылысып жатқанын анықтауға келтіреміз. Бізде үш интервал тізімі бар (әр ось үшін біреу) және барлық тізімдердің ұзындығы бірдей (әр тізімнің ұзындығы , шектейтін қораптардың саны). Әр тізімде әрбір интервал тізімдегі басқа барлық интервалдармен қиылысуы мүмкін. Сондықтан, әр тізім үшін 0 мен 1-ден тұратын матрица болады: егер және интервалдары қиылысса, онда 1, қиылыспаса – 0. Біздің болжамымыз бойынша, интервалдар тізіміне сәйкес матрица бір уақыт қадамынан келесі қадамға өте аз өзгереді. Бұл мүмкіндікті пайдалану үшін интервалдар тізімі, шын мәнінде, таңбаланған соңғы нүктелер тізімі ретінде сақталады. Тізімнің әрбір элементі интервалдың соңғы нүктесінің координатасын және осы интервалды анықтайтын бірегей бүтін санды қамтиды. Содан кейін тізім координаттар бойынша сұрыпталады және матрица жаңартылады. Егер шектейтін қораптардың конфигурациясы бір уақыт қадамынан келесі қадамға айтарлықтай өзгеретін болса, бұл алгоритмнің салыстырмалы түрде жылдам жұмыс істейтініне сену оңай. Деформацияланатын денелердің (мысалы, мата симуляциясы) жағдайында, төменде талқыланғандай, нақты жұптық кесу алгоритмін қолдану мүмкін болмайды, ал n дене кесу алгоритмі ең жақсы нәтиже береді. Егер сахнадағы физикалық денелердің жылдамдығына жоғарғы шек қойылса, онда объектілер жұптарын олардың бастапқы қашықтығы мен уақыт қадамының мөлшеріне сүйене отырып кесуге болады.

In many applications, the configuration of physical bodies from one time step to the next changes very little. Many of the objects may not move at all. Algorithms have been designed so that the calculations done in a preceding time step can be reused in the current time step, resulting in faster completion of the calculation. At the coarse level of collision detection, the objective is to find pairs of objects which might potentially intersect. Those pairs will require further analysis. An early high performance algorithm for this was developed by Ming C. Lin at the University of California, Berkeley , who suggested using axis aligned bounding boxes for all n bodies in the scene. Each box is represented by the product of three intervals (i. e., a box would be ). A common algorithm for collision detection of bounding boxes is sweep and prune. Observe that two such boxes, and intersect if, and only if, intersects , intersects and intersects It is supposed that, from one time step to the next, if and intersect, then it is very likely that at the next time step they will still intersect. Likewise, if they did not intersect in the previous time step, then they are very likely to continue not to. So we reduce the problem to that of tracking, from frame to frame, which intervals do intersect. We have three lists of intervals (one for each axis) and all lists are the same length (since each list has length , the number of bounding boxes.) In each list, each interval is allowed to intersect all other intervals in the list. So for each list, we will have an matrix of zeroes and ones: is 1 if intervals and intersect, and 0 if they do not intersect. By our assumption, the matrix associated to a list of intervals will remain essentially unchanged from one time step to the next. To exploit this, the list of intervals is actually maintained as a list of labeled endpoints. Each element of the list has the coordinate of an endpoint of an interval, as well as a unique integer identifying that interval. Then, we sort the list by coordinates, and update the matrix as we go. It's not so hard to believe that this algorithm will work relatively quickly if indeed the configuration of bounding boxes does not change significantly from one time step to the next. In the case of deformable bodies such as cloth simulation, it may not be possible to use a more specific pairwise pruning algorithm as discussed below, and an n body pruning algorithm is the best that can be done. If an upper bound can be placed on the velocity of the physical bodies in a scene, then pairs of objects can be pruned based on their initial distance and the size of the time step.

Жұппен кесу

Біз зерттеу үшін екі денені таңдап алғаннан кейін, соқтығысуларды мұқият тексеруіміз керек. Дегенмен, көптеген қолданбаларда жеке денелер (егер олар тым деформацияланбаса) кіші примитивтер жиынтығымен, әсіресе үшбұрыштармен сипатталады. Енді бізде екі үшбұрыштар жиынтығы бар, және (айқындық үшін, әр жиынтықта үшбұрыштар саны бірдей деп есептейміз). Барлық үшбұрыштарды бір-бірімен соқтығысу үшін тексеру – ең қарапайым нәрсе, бірақ бұл көптеген салыстыруларды қажет етеді, бұл өте тиімсіз. Мүмкін болса, тексеруге қажет үшбұрыштар жұптарының санын азайту үшін кесу алгоритмін қолдану ұсынылады. Алгоритмдердің ең көп қолданылатын тобы – иерархиялық шектеу көлемдері әдісі деп аталады. Алдын ала өңдеу кезінде әрбір дене үшін (мысалы, және) шектеу көлемдерінің иерархиясын есептейміз. Содан кейін, әр уақыт қадамында, және арасындағы соқтығысуларды тексеру қажет болғанда, қарастырылып отырған үшбұрыштар жұптарының санын азайту үшін иерархиялық шектеу көлемдері қолданылады. Мысал ретінде шектеу шарларын қолданамыз, бірақ көп жағдайда шарлар тиімсіз болуы мүмкін. Егер – үшбұрыштар жиынтығы болса, онда біз шектеу шарларын алдын ала есептей аламыз. Шарды қалай таңдаудың көптеген тәсілдері бар, біз тек шардың жиынтықты толығымен қамтитынын және мүмкіндігінше кіші екенін ғана қарастырамыз. Алдын ала есептеу арқылы біз есептей аламыз және Егер бұл екі шар қиылыспаса (мұны тексеру оңай), онда және де қиылыспайды. Бірақ бұл n-дене кесу алгоритмінен айтарлықтай жақсырақ емес. Егер – үшбұрыштар жиынтығы болса, онда оны екі бөлікке бөлуге болады, және Біз осыны және үшін де жасай аламыз, содан кейін шектеу шарларын (алдын ала) есептей аламыз және Үміт – бұл шектеу шарлары мен шарларынан әлдеқайда кіші болады. Мысалы, егер және қиылыспаса, онда жиынтықтағы кез келген үшбұрықты жиынтықтағы кез келген үшбұрықпен тексерудің қажеті жоқ. Алдын ала есептеу ретінде, әрбір физикалық денені (үшбұрыштар жиынтығымен бейнеленген) аламыз және оны екілік ағашқа рекурсивті түрде бөлеміз, онда әр түйін үшбұрыштар жиынтығын көрсетеді, ал оның екі баласы және болады. Ағаштағы әр түйінде шектеу шарларын алдын ала есептей аламыз. Егер денелердің соқтығысын тексеру қажет болса, олардың шектеу шарлары ағашы көптеген үшбұрыштар жұптарын жою үшін қолданылуы мүмкін. Алгоритмдердің көптеген нұсқалары шардан басқа нәрсені таңдау арқылы алынады. Егер оське сәйкес шектеу қораптарын таңдасақ, AABBTrees аламыз. Бағытталған шектеу қораптары ағаштары OBBTrees деп аталады. Кейбір ағаштарды негізгі дене өзгерген жағдайда жаңарту оңай. Кейбір ағаштар қарапайым үшбұрыштардың орнына сплайндар сияқты жоғары ретті примитивтерді қабылдай алады.

Once we've selected a pair of physical bodies for further investigation, we need to check for collisions more carefully. However, in many applications, individual objects (if they are not too deformable) are described by a set of smaller primitives, mainly triangles. So now, we have two sets of triangles, and (for simplicity, we will assume that each set has the same number of triangles.) The obvious thing to do is to check all triangles against all triangles for collisions, but this involves comparisons, which is highly inefficient. If possible, it is desirable to use a pruning algorithm to reduce the number of pairs of triangles we need to check. The most widely used family of algorithms is known as the hierarchical bounding volumes method. As a preprocessing step, for each object (in our example, and ) we will calculate a hierarchy of bounding volumes. Then, at each time step, when we need to check for collisions between and , the hierarchical bounding volumes are used to reduce the number of pairs of triangles under consideration. For simplicity, we will give an example using bounding spheres, although it has been noted that spheres are undesirable in many cases. If is a set of triangles, we can pre calculate a bounding sphere There are many ways of choosing , we only assume that is a sphere that completely contains and is as small as possible. Ahead of time, we can compute and Clearly, if these two spheres do not intersect (and that is very easy to test), then neither do and This is not much better than an n body pruning algorithm, however. If is a set of triangles, then we can split it into two halves and We can do this to and , and we can calculate (ahead of time) the bounding spheres and The hope here is that these bounding spheres are much smaller than and And, if, for instance, and do not intersect, then there is no sense in checking any triangle in against any triangle in
As a precomputation, we can take each physical body (represented by a set of triangles) and recursively decompose it into a binary tree, where each node represents a set of triangles, and its two children represent and At each node in the tree, we can pre compute the bounding sphere
When the time comes for testing a pair of objects for collision, their bounding sphere tree can be used to eliminate many pairs of triangles. Many variants of the algorithms are obtained by choosing something other than a sphere for If one chooses axis aligned bounding boxes, one gets AABBTrees. Oriented bounding box trees are called OBBTrees. Some trees are easier to update if the underlying object changes. Some trees can accommodate higher order primitives such as splines instead of simple triangles.

Дәл жұптық соқтығысуды анықтау

Біз кесуді аяқтағаннан кейін, дәл соқтығысуды тексеру үшін бірнеше үміткер жұптар қалады. Негізгі байқау мынадай: егер екі дөңгелек нысан бөлек болса, онда оларды бөлетін жазықтықты табуға болады, яғни бір нысан жазықтықтың бір жағында, ал екіншісі – қарама-қарсы жағында орналасады. Бұл дөңгелек нысандар үшін өте жылдам соқтығысуды анықтау алгоритмдерін жасауға мүмкіндік береді. Бұл саладағы алғашқы жұмыстар «бөлу жазықтығы» әдістерін қамтыды. Екі үшбұрыш, егер оларды үш төбесінен өтетін жазықтықпен бөліп алу мүмкін болмаса ғана соқтығысады. Яғни, егер үшбұрыштар және олардың әрқайсысы вектор болса, онда үш төбеден өтетін жазықтықты тауып, оның бөлу жазықтығы болатынын тексеруге болады. Егер мұндай жазықтық бөлу жазықтығы болса, үшбұрыштар бөлек деп есептеледі. Ал егер мұндай жазықтықтардың ешқайсысы бөлу жазықтығы болмаса, үшбұрыштар қиылысады деп саналады. Мұндай жазықтықтар жиырмаға жуық. Егер үшбұрыштар бір жазықтықта жатса, бұл тест толыққанды нәтиже бермейді. Мәселені толық шешу үшін, үшбұрыштың қабырғаларына перпендикуляр жазықтықтар сияқты қосымша жазықтықтарды қосуға болады. Басқа жағдайларда, жазық бетпен кездесетін нысандар міндетті түрде басқа жерде бұрышта да кездесуі керек, сондықтан жалпы соқтығысуды анықтау соқтығысуды таба алады. Содан бері жақсы әдістер әзірленді. Екі дөңгелек көпбұрышты нысанның бетіндегі ең жақын нүктелерді табу үшін өте жылдам алгоритмдер бар. Минг К. Линнің ертедегі жұмыстары сызықтық бағдарламалаудан алынған симплекс алгоритмінің өзгеруін қолданды. Гилберт-Джонсон-Кеертти арақашықтығы алгоритмі бұл тәсілді ескірді. Бұл алгоритмдер, егер олар стационарлық немесе баяу қозғалатын нысандар жұптарына қайта-қайта қолданылса, алдыңғы соқтығысу тексеруінен алынған бастапқы нүктелермен қолданылса, тұрақты уақытқа жақын нәтиже береді. Осы алгоритмдік жұмыстың нәтижесі – соқтығысуды анықтау, мыңдаған қозғалатын нысандарды нақты уақытта, әдеттегі жеке компьютерлер мен ойын консольдерінде тиімді жүзеге асыруға мүмкіндік береді.

Once we're done pruning, we are left with a number of candidate pairs to check for exact collision detection. A basic observation is that for any two convex objects which are disjoint, one can find a plane in space so that one object lies completely on one side of that plane, and the other object lies on the opposite side of that plane. This allows the development of very fast collision detection algorithms for convex objects. Early work in this area involved "separating plane" methods. Two triangles collide essentially only when they can not be separated by a plane going through three vertices. That is, if the triangles are and where each is a vector in , then we can take three vertices, , find a plane going through all three vertices, and check to see if this is a separating plane. If any such plane is a separating plane, then the triangles are deemed to be disjoint. On the other hand, if none of these planes are separating planes, then the triangles are deemed to intersect. There are twenty such planes. If the triangles are coplanar, this test is not entirely successful. One can add some extra planes, for instance, planes that are normal to triangle edges, to fix the problem entirely. In other cases, objects that meet at a flat face must necessarily also meet at an angle elsewhere, hence the overall collision detection will be able to find the collision. Better methods have since been developed. Very fast algorithms are available for finding the closest points on the surface of two convex polyhedral objects. Early work by Ming C. Lin used a variation on the simplex algorithm from linear programming. The Gilbert Johnson Keerthi distance algorithm has superseded that approach. These algorithms approach constant time when applied repeatedly to pairs of stationary or slow moving objects, when used with starting points from the previous collision check. The end result of all this algorithmic work is that collision detection can be done efficiently for thousands of moving objects in real time on typical personal computers and game consoles.

Априорлық кесу

Орындалатын нысандардың көпшілігі бейнеойындарға тәндей тұрақты болған жағдайда, орындау жылдамдығын арттыру үшін алдын ала есептеуді қолданатын априорлы әдістерді пайдалануға болады. Мұнда n-дене кесу және жұптық кесу де қажет, бірақ алгоритмдер уақытты және негізгі физикалық жүйеде қолданылатын қозғалыс түрлерін ескеруі тиіс. Дәл жұптық соқтығысуды анықтауда траекторияға тәуелділік өте жоғары, сондықтан соқтығысу сәтін есептеу үшін сандық түбірді табу алгоритмін қолдану қажет. Мысалы, уақыт бойынша қозғалатын екі үшбұрышты қарастырайық. Кез келген уақыт мезгілінде екі үшбұрыштың қиылысуын бұрын айтылған жиырма жазықтықты пайдалана отырып тексеруге болады. Дегенмен, біз одан да жақсы нәтижеге қол жеткізе аламыз, себебі осы жиырма жазықтықтың барлығын уақыт бойынша қадағалауға болады. Егер жазықтық белгілі бір нүктелер арқылы өтетін болса, онда 20 жазықтықты қадағалау қажет. Әрбір жазықтықты үш төбемен салыстыру керек, бұл 60 мәнді береді. Осы алпыс функция бойынша түбірді табу алгоритмін қолдану екі берілген үшбұрыш пен екі берілген траектория үшін дәл соқтығысу уақытын анықтайды. Мұнда егер төбелердің траекториялары сызықтық полиномдар деп есептелсе, онда соңғы алпыс функция шын мәнінде кубикалық полиномдар болып табылады, және осы ерекше жағдайда кубикалық түбірлер формуласын пайдалана отырып, дәл соқтығысу уақытын табу мүмкін. Кейбір сандық талдаушылар кубикалық түбірлер формуласын пайдалану, полиномдар үшін түбір табушыны пайдалануға қарағанда сандық тұрақтылығы жағынан нашар деп санайды.

Ғарыштық бөлік

Альтернативті алгоритмдер кеңістіктік бөлу шаңырағының астында топтастырылған, оған октрелер, екілік кеңістікті бөлу (немесе BSP ағаштары) және басқа да ұқсас тәсілдер кіреді. Егер кеңістік бірнеше қарапайым жасушаға бөлінсе және екі нысан бір жасушада емес екені дәлелденсе, оларды қиылысуға тексерудің қажеті жоқ. BSP ағаштарын алдын ала есептеуге болатындықтан, бұл тәсіл ойындардағы қабырғалар мен тұрақты кедергілерді басқаруға өте ыңғайлы. Бұл алгоритмдер әдетте жоғарыда сипатталған алгоритмдерге қарағанда ескі.

Шектеу қораптары

Шектеуші қораптар (немесе шектеуші көлемдер) көбінесе 2D тіктөртбұрыш немесе 3D кубоид болып келеді, бірақ басқа да пішіндер мүмкін. Видео ойында шектеуші қорап кейде Hitbox деп аталады. Шекаралық алмаз, ең кішкентай шектеуші параллелограмм, дөңгелек қабықша, шектеуші шеңбер немесе шектеуші шар, сондай-ақ шектеуші эллипс та қолданылып көрілген, алайда шектеуші қораптар қарапайымдылығының арқасында ең көп таралған болып табылады. Шектеуші қораптар әдетте соқтығысуды анықтаудың алғашқы (іріктеу) кезеңінде қолданылады, сондықтан егжей-тегжейлі салыстыру тек қана жабысатын шектеуші қораптары бар объектілер үшін қажет.

Үшбұрыштың орталық сегменттері

Үшбұрышты тор объектісі 3D дене модельдеуінде жиі қолданылады. Әдетте соқтығысу функциясы үшбұрышты үшбұрышпен кесісуі немесе тормен байланысты шектеу пішіні болып табылады. Үшбұрыштың центройды – бұл қарындаш ұшында тепе-теңдік сақтайтын масса орталығы. Симуляцияға физикалық параметрлерге центроидты өлшемді қосу жеткілікті. Егер объект пен нысананың центроидтары белгілі болса, осы екі нүктені қосатын сызық сегментін анықтауға болады. Үшбұрыштың центройдысының координаттық векторы оның төбелерінің координаттық векторларының орташа мәніне тең. Егер оның төбелерінің координаттары , және болса, онда центроид мына жерде көрсетілген. Бұл – екі 3D нүкте арасындағы сызық сегментінің арақашықтығын есептейтін функция. Мұнда сегменттің ұзындығы/арақашықтығы сегменттің реттелетін "соқтығысу" өлшемі болып табылады. Объектілер жақындағанда ұзындығы шекті мәнге дейін азаяды. Үшбұрыш-сфера тиімді геометриялық тестке айналады. Центроидта орналасқан сфераның мөлшері үшбұрыштың барлық төбелерін қамтуға мүмкіндік береді.

Бейне ойындар

Видео ойындар өте шектеулі есептеу уақытын бірнеше тапсырмаға бөліп отырады. Бұл ресурстардың шектеулі болуына және салыстырмалы түрде қарапайым соқтығысуды анықтау алгоритмдерін пайдалануға қарамастан, бағдарламашылар ойындарда қолдануға болатын сенімді, бірақ дәл емес жүйелерді жасауға қол жеткізді. Ұзақ уақыт бойы видео ойындарда өте шектеулі сандағы объектілер қарастырылды, сондықтан барлық жұптарды тексеру қиындық тудырмады. Екі өлшемді ойындарда кейбір жағдайларда аппараттық жабдық экрандағы спрайттар арасындағы пикселдердің қабаттасуын тиімді анықтап, хабарлай алды. Басқа жағдайларда, экранды жай ғана плиткалап, әр спрайтты оның үстінен өтетін плиткаларға байлау жеткілікті кесуді қамтамасыз етеді, ал жұптық тексеру үшін шектейтін тіктөртбұрыштар немесе шеңберлер – хитбокстар қолданылады және жеткілікті дәлді деп есептеледі. Үш өлшемді ойындар денелерді кесу үшін кеңістікті бөлу әдістерін қолданды және ұзақ уақыт бойы жұптық тексеру үшін нақты 3D объектіге бір немесе бірнеше шарды қолданды. Нақты тексеру өте сирек кездеседі, тек шындықты жақын симуляциялауға тырысатын ойындарда ғана. Тіпті сонда да, нақты тексеру барлық жағдайларда қолданылмайды. Ойындар нақты физиканы еліктемейді, сондықтан тұрақтылық мәселесі аса маңызды емес. Көптеген ойындар апостериор соқтығысуды анықтауды қолданады, ал соқтығысулар өте қарапайым ережелерді қолдану арқылы шешіледі. Мысалы, егер кейіпкер қабырғаға кіріп кетсе, оны жай ғана соңғы белгілі жақсы орнына қайтаруға болады. Кейбір ойындар кейіпкердің қабырғаға кірмей тұрып қанша қашықтыққа қозғала алатынын есептеп, оған тек осы қашықтықта қозғалуға рұқсат береді. Көптеген жағдайларда бейнеойындарда кейіпкерлерді нүкте ретінде жақындату, оларды қоршаған ортамен соқтығысуды анықтау үшін жеткілікті. Бұл жағдайда, бинарлық кеңістікті бөлу ағаштары нүктенің декорацияға кіргенін немесе кірмегенін тексеру үшін тиімді, жылдам және қарапайым алгоритмді ұсынады. Мұндай дерек құрылымы кейіпкер жерге жүгіріп бара жатқанда "демалыс күйі" жағдайын да тиімді басқаруға мүмкіндік береді. Кейіпкерлер арасындағы соқтығысулар, оқ-дәрілермен және қауіпті нысандармен соқтығысулар бөлек қарастырылады. Сенімді симулятор кез келген кіріске ақылға қонымды жауап береді. Мысалы, егер біз жоғары жылдамдықты жарыс машинасының бейнеойынын елестетсек, бір симуляциялық қадамнан келесісіне машиналар жарыс жолы бойымен айтарлықтай қашықтыққа жылжуы мүмкін. Егер жолда терең емес кедергі болса (мысалы, кірпіш қабырғасы), машина оның үстінен толығымен секіріп өтуі мүмкін, бұл өте жағымсыз. Басқа жағдайларда, апостериор алгоритмдерінің талап ететін "түзету" дұрыс жүзеге асырылмағандықтан, кейіпкерлерді қабырғаларға қамап тастайтын немесе олардың арқылы өтуге және сонда мәңгілік босқа түсуге мүмкіндік беретін қателер пайда болады, онда өлімге әкелетін түпсіз шұңқыр болуы мүмкін немесе болмауы мүмкін, кейде "қара тозақ", "көк тозақ" немесе "жасыл тозақ" деп аталады, басым түсіне байланысты. Бұл – соқтығысуды анықтау және физикалық модельдеу жүйесінің сәтсіздігінің белгілері. Big Rigs: Over the Road Racing – бұл соқтығысуды анықтау жүйесі бұзылған немесе тіпті жоқ ойынның әйгілі мысалы.

Video games have to split their very limited computing time between several tasks. Despite this resource limit, and the use of relatively primitive collision detection algorithms, programmers have been able to create believable, if inexact, systems for use in games. For a long time, video games had a very limited number of objects to treat, and so checking all pairs was not a problem. In two dimensional games, in some cases, the hardware was able to efficiently detect and report overlapping pixels between sprites on the screen. In other cases, simply tiling the screen and binding each sprite into the tiles it overlaps provides sufficient pruning, and for pairwise checks, bounding rectangles or circles called hitboxes are used and deemed sufficiently accurate. Three dimensional games have used spatial partitioning methods for body pruning, and for a long time used one or a few spheres per actual 3D object for pairwise checks. Exact checks are very rare, except in games attempting to simulate reality closely. Even then, exact checks are not necessarily used in all cases. Because games do not need to mimic actual physics, stability is not as much of an issue. Almost all games use a posteriori collision detection, and collisions are often resolved using very simple rules. For instance, if a character becomes embedded in a wall, they might be simply moved back to their last known good location. Some games will calculate the distance the character can move before getting embedded into a wall, and only allow them to move that far. In many cases for video games, approximating the characters by a point is sufficient for the purpose of collision detection with the environment. In this case, binary space partitioning trees provide a viable, efficient and simple algorithm for checking if a point is embedded in the scenery or not. Such a data structure can also be used to handle "resting position" situation gracefully when a character is running along the ground. Collisions between characters, and collisions with projectiles and hazards, are treated separately. A robust simulator is one that will react to any input in a reasonable way. For instance, if we imagine a high speed racecar video game, from one simulation step to the next, it is conceivable that the cars would advance a substantial distance along the race track. If there is a shallow obstacle on the track (such as a brick wall), it is not entirely unlikely that the car will completely leap over it, and this is very undesirable. In other instances, the "fixing" that posteriori algorithms require isn't implemented correctly, resulting in bugs that can trap characters in walls or allow them to pass through them and fall into an endless void where there may or may not be a deadly bottomless pit, sometimes referred to as "black hell", "blue hell", or "green hell", depending on the predominant color. These are the hallmarks of a failing collision detection and physical simulation system. Big Rigs: Over the Road Racing is an infamous example of a game with a failing or possibly missing collision detection system.

Hitbox (жақсылық)

Hitbox – видео ойындарда соқтығысуды нақты уақыт режимінде анықтау үшін жиі қолданылатын көрінбейтін пішін; ол шектеуші қораптың бір түрі. Көбінесе ол 2D ойындарда тіктөртбұрыш, ал 3D ойындарда текше болып келеді және көрінетін нысанға (мысалы, модель немесе спрайт) бекітіліп, оның қозғалысын қадағалайды. Дөңгелек немесе сфера пішіндері де жиі кездеседі, бірақ олар көбінесе «қораптар» деп аталады. Анимациялық нысандардың әрбір қозғалатын бөлігіне, қозғалыс кезінде дәлдікті қамтамасыз ету үшін hitbox тіркелуі мүмкін. Hitbox-тар «бір жақты» соқтығысуларды анықтау үшін қолданылады, мысалы, кейіпкердің соққыға немесе оққа түюі. Олар кері байланыспен соқтығысуларды анықтауға қолайлы емес (мысалы, қабырғаға соқтығысу), себебі адамдар мен жасанды интеллект үшін hitbox-тың үнемі өзгеретін орнын басқару қиынға түседі; мұндай соқтығысулар көбінесе оське сәйкес келетін қарапайым шектеуші қораптармен шешіледі. Ойыншылар осы типтегі өзара әрекеттесулерді білдіру үшін «hitbox» терминін пайдалана береді. Hurtbox – кіріс соққыларын анықтау үшін қолданылатын hitbox. Бұл контексте «hitbox» термині көбінесе зиян келтіретін нысандар үшін қолданылады. Мысалы, шабуыл тек шабуылшының соққысының айналасындағы hitbox, қарсыластың денесіндегі hurtbox-пен жанасқанда ғана тиімді болады, ал қарсыластың hitbox-тарының соқтығысуы ойыншылардың соққыларын алмастыруға немесе тоқтатуға әкелуі мүмкін, ал hurtbox-тар бір-бірімен өзара әрекеттеспейді. Бұл термин индустрияда стандартизацияланбаған; кейбір ойындар hitbox және hurtbox анықтамаларын ауыстырады, ал басқалары екі жақ үшін де тек «hitbox» терминін қолданады.