Törmäysten havaitseminen

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 29. lokakuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 20 muokkausta .

Törmäysten havaitseminen on laskennallinen ongelma kahden tai useamman kohteen välisten risteyskohtien havaitsemisessa. Aihe liittyy useimmiten sen käyttöön fysiikkamoottoreissa , tietokoneanimaatiossa ja robotiikassa . Sen lisäksi, että törmäyksenilmaisinjärjestelmät määrittävät, ovatko kaksi esinettä törmänneet, ne voivat laskea törmäysajan ja raportoida kontaktikerääjän (leikkauspisteiden joukko) [1]. Reaktio törmäykseen (mitä tapahtuu, kun törmäys havaitaan) riippuu tietystä mallinnetusta prosessista. Törmäyksentunnistusalgoritmit käyttävät laajasti lineaarialgebran ja laskennallisen geometrian käsitteitä. Törmäyksentunnistusalgoritmit ovat yksi kolmiulotteisten tietokonepelien fysiikan pääkomponenteista .

Yleiskatsaus

Fyysisen mallin toimintaan kuuluu fyysisten kokeiden suorittaminen, kuten biljardin pelaaminen . Biljardipallojen törmäyksen fysiikkaa kuvaavat hyvin solid-state-fysiikka ja täydellisen elastisen iskun teoria . Alkuehdot asetetaan biljardipöydän ja -pallojen ehdottoman tarkan fyysisen ominaisuuksien sekä pallojen alkukoordinaattien perusteella. Kun otetaan huomioon lyöntipallon kiihtyvyys (oletettavasti seurausta siitä, että pelaaja lyö lyöntipalloa lyöntitikulla), haluamme laskea tietokoneohjelman avulla kaikkien pallojen tarkat liikeradat, nopeus ja pysähtymispaikka. Biljardia simuloiva fysiikkamoottori koostuu useista komponenteista, joista yksi on vastuussa pallojen välisten törmäysten tarkasta laskemisesta. Tämä komponentti on esimerkki mallin epävakaasta osasta - pienet virheet törmäyslaskelmissa johtavat merkittäviin muutoksiin tuloksissa - pallojen lopulliset asennot pöydällä.

Tietokonepeleillä on suunnilleen samat vaatimukset fysikaalisille moottoreille, lukuun ottamatta joitakin merkittäviä eroja. Vaikka fyysisten kokeiden simulointi vaatii tarkimman matemaattisen laitteen luomista, joka kuvaa todellista maailmaa, tietokonepelit tarvitsevat fysiikkaa, joka näyttää vain uskottavalta, mutta samalla reaaliajassa laskettuna , vaikkakin karkeasti. Kompromissit ovat sallittuja, kunhan se sopii pelaajalle ja on hyväksyttävää visuaalista realismia. Siksi törmäyksen varalta tarkistettu kappale - niin kutsuttu hitbox - on yksinkertaisempi kuin kolmiulotteinen merkkimalli . Erityisesti Team Fortress 2 :n hahmoilla on kolme osumalaatikkoa:

suuri laatikko (sama kaikille luokille) - tarkistaaksesi törmäyksen ohjusten kanssa;
kulkeeko merkki aukon läpi - tämän määrittää pienempi suuntaissärmiö (myös yhteinen kaikille luokille);
luotien tarkistaminen - suuntaissärmiöiden yhdistelmä, joka toistaa karkeasti kuviota (jokaisella luokalla on oma).

World of Tanksissa (ja joissakin muissa sotilasajoneuvo-simulaattoreissa) käytetään kehittyneempää törmäyksentunnistusjärjestelmää . Tässä hitboxin sijaan käytetään säiliön monikulmion törmäysmallia. Se on paljon karkeampi kuin taisteluajoneuvon visuaalinen malli, mutta sen avulla voit laskea riittävän tarkasti ammuksen tankkiin kohdistuvan törmäyskulman, mikä on tärkeää laskettaessa läpäisyä ja / tai kimmotusta sekä iskua. saranoiduilla seuloilla varustetut ammukset. World of Warshipsissä käytetään vieläkin kehittyneempää törmäyksentunnistusjärjestelmää . Tässä ei lasketa vain ammuksen törmäystä laivaelementtiin, vaan myös ammuksen räjähdyksen vaikutusta: sirpaleita, iskuaaltoa, ottaen huomioon törmäysmallin yksityiskohtien sijainti.

Törmäysten havaitseminen fysiikan simulaatioissa

Fysikaaliset moottorit eroavat tavasta, jolla ne reagoivat törmäyksiin. Jotkut käyttävät materiaalien joustavuutta laskeakseen voiman, joka syntyy törmäyksestä ja vaikuttaa törmäyksen tulokseen myöhemmillä aikaväleillä, mikä on laskennallisesti melko kallista. Jotkut mallit laskevat likimääräisen törmäysajan lineaarista interpolaatiota käyttäen, minkä jälkeen ne "palauttavat" kohtauksen tilaa tietyllä hetkellä ja laskevat törmäyksen energian säilymisen lakien perusteella.

Jotkut käyttävät iteratiivista lineaarista interpolaatiota ( Newtonin menetelmä ) laskeakseen törmäysajan paljon suuremmalla tarkkuudella kuin muut laskelmat. Törmäysten havaitsemismenetelmä rikkoo aikakoherenssin periaatetta, jotta aikavälien tarkkuutta voidaan parantaa lisäämättä järjestelmän laskentaresurssien kokonaiskuormitusta.

Joustamattoman törmäyksen jälkeen voi esiintyä erityisiä liuku- tai lepotiloja, joita esimerkiksi emuloidaan rajoituksilla vapaassa fysiikkamoottorissa Open Dynamics Engine . Rajoitukset sulkevat pois inertian ja sen seurauksena epävakauden. Levon toteuttaminen kohtauskaavion kannalta välttää siirtymät.

Toisin sanoen fyysisten mallien toteutukset jaetaan yleensä kahteen polkuun:

törmäyksen havaitseminen jälkikäteen ,
a priori lähestymistapa (havaitseminen ennen törmäystä).

Sen lisäksi, että ne jaetaan jälkikäteen ja a priori -lähestymistapoihin, lähes kaikki nykyaikaiset törmäyksentunnistusalgoritmit on jaettu algoritmien hierarkiaan.

Erot jälkikäteen ja a priori lähestymistavan välillä

Jälkikäteen tapahtuvassa lähestymistavassa mallin laskenta toteutetaan laskemalla näkymän tilat lyhyin aikavälein, joista jokainen tarkistetaan risteävien kohteiden esiintymisen varalta tai jotka sijaitsevat niin lähellä, että niitä voidaan pitää risteävinä . . Simuloinnin jokaisessa vaiheessa luodaan lista risteävistä kappaleista, joiden paikat ja liikeradat "korjataan" ottaen huomioon törmäyksen tosiasia. Tätä lähestymistapaa kutsutaan jälkikäteen, koska itse asiassa törmäyksen välitön tarkka hetki jää huomaamatta ja se havaitaan jonkin aikaa sen tapahtumisen jälkeen (tai jonkin aikaa ennen, riippuen algoritmista).

A priori -lähestymistavalla luodaan törmäyksen havaitsemisalgoritmi, joka pystyy ennustamaan fyysisten kappaleiden liikeradan suurella tarkkuudella. Tämä malli kuvaa törmäyksiä suurella tarkkuudella, eivätkä fyysiset kappaleet pohjimmiltaan koskaan joudu molemminpuolisen tunkeutumisen tilaan. Tätä lähestymistapaa kutsutaan a priori, koska kappaleiden törmäyshetket määräytyvät ennen kuin kohtauksen kohteiden tilakonfiguraatio muuttuu.

Sen tärkeimmät edut johtuvat jälkikäteen suuntautuvasta lähestymistavasta. Algoritmin ei tarvitse manipuloida merkittävää määrää fyysisiä muuttujia - sen syöte on yksinkertainen luettelo fyysisistä kappaleista, tuloksena on leikkaavien kappaleiden osajoukko. Algoritmin ei tarvitse käsitellä kitkavoimia, kimmoisia tai, mikä pahempaa, joustamattomia törmäyksiä, ja myös laskea muotoaan muuttavien kappaleiden sisäisen tilan muutosta . Lisäksi a posteriori -algoritmi on olennaisesti yhden ulottuvuuden verran yksinkertaisempi, koska a priori -lähestymistapassa joudutaan käsittelemään lisäakselia - aikaa, jolta a posteriori lähestymistapa säästyy.

Toisaalta a posteriori algoritmit johtavat ongelmiin tapahtuneiden kappaleiden tunkeutumisten "korjaus" vaiheessa, joita ei esiinny todellisessa fyysisessä kohtauksessa.

A priori -lähestymistavan etuja ovat mallin tarkkuus ja vakaus. On vaikeaa (mutta teoreettisesti mahdollista) erottaa täysin kohtausmallin fyysinen komponentti törmäyksen havaitsemisalgoritmista. Useimmissa tapauksissa, yksinkertaisimpia lukuun ottamatta, kahden kappaleen törmäyshetken ennustamisen ongelmalla joistakin lähtötiedoista ei ole yleistä ratkaisua, joka on abstrakti muusta mallista. Juuren etsimiseen käytetään numeerista menetelmää.

Jotkut ruumiit ovat lepokontaktissa, toisin sanoen ne ovat muodollisesti jatkuvassa törmäyksessä, mikä ei johda kehon vastenmielisiin liikkeisiin tai tunkeutumiseen (esimerkiksi pöydällä seisova maljakko). Kaikissa tapauksissa kosketus levossa vaatii poikkeuksellista lähestymistapaa: jos kaksi kappaletta törmäävät toisiinsa ("a posteriori") tai liukuvat ("a priori") ja niiden suhteellinen liike on tietyn kynnyksen alapuolella, kitkaa käsitellään tarttumisena, ja molemmat esineet yhdistetään yhdeksi kohtauskaavion haaraksi .

Optimointi

Ilmeiset lähestymistavat törmäysten havaitsemiseen koko kohtauksessa, jossa on monia kohteita, ovat melko hitaita. Kunkin kohteen törmäyksen tarkistaminen kunkin kohteen kanssa on toimivaa, mutta erittäin tehotonta laskennallisen monimutkaisuuden kannalta suurelle määrälle objekteja. Monimutkaisen geometrian kohteiden tarkistaminen törmäyksen esiintymisen varalta ilmeisellä menetelmällä kappaleiden yksittäisten pintojen törmäyksen tarkistamiseksi on sinänsä erittäin kallista. Näin ollen merkittävä osa alan tutkimusta kohdistuu suorituskykyongelmien ratkaisemiseen.

Ajallisen koherenssin soveltaminen

Monissa sovelluksissa fyysisten kappaleiden konfiguraatio muuttuu hyvin vähän iteratiivisen ajanjakson aikana. Monet kohteet kohtauksessa eivät liiku ollenkaan. Algoritmit luodaan siten, että edellisessä iteraatiossa tehtyjen laskelmien tuloksia käytetään seuraavassa, mikä johtaa suorituskyvyn kasvuun.

Karkean törmäyksen havaitsemisen tasolla tavoitteena on löytää esineitä, jotka voivat mahdollisesti leikkiä. Nämä parit vaativat lisäanalyysiä. Yhden näistä algoritmeista kehitti Ming Chieh Lin Kalifornian yliopistosta Berkeleyssä [2] , joka ehdotti kehysten rajausmenetelmän käyttöä, jonka reunavektorit ovat kollineaarisia karteesisen koordinaattijärjestelmän kantavektoreiden kanssa kaikille N:lle. kohtauksen ruumiit. Myöhemmin näistä rajoituslaatikoista tuli nimitystä Axis-aligned bounding box (AABB).

Jokaista suuntaissärmiötä edustaa segmenttien kolmikko, esimerkiksi . Yleinen algoritmi rajoituslaatikoiden törmäysten havaitsemiseksi on " pyyhkäise ja karsi " -algoritmi [ 3 ] . Ilmeisesti kaksi tällaista suuntaissärmiötä ja leikkaa jos ja vain jos leikkaa kanssa , leikkaa kanssa ja leikkaa kanssa . Oletetaan, että jos yhdestä aikaiteraatiosta toiseen ja leikkaavat, niin on hyvin todennäköistä, että ne leikkaavat edelleen seuraavassa iteraatiossa. Lisäksi, jos ne eivät leikkaaneet edellisessä iteraatiossa, on erittäin todennäköistä, että ne eivät leikkaa seuraavassa. $I_1 \kertaa I_2 \kertaa I_3=[a_1,b_1] \kertaa [a_2,b_2] \kertaa [a_3,b_3]$ $I_1 \kertaa I_2 \kertaa I_3$ $J_1 \ kertaa J_2 \ kertaa J_3$ $I_1$ $J_{1}$ $minä_{2}$ $J_{2}$ $I_3$ $J 3}$ $minä_{k}$ ${\displaystyle J_{k))$

Joten ongelma johtuu iteratiivisesta ohjauksesta "kehyksestä" "kehykseen" sen suhteen, mitkä segmentit leikkaavat. Intervallilla on kolme luetteloa (yksi kullekin koordinaattiakselille), ja kaikki kolme samanpituisia, koska kunkin pituus on yhtä suuri kuin kohtauksen kohteiden lukumäärän ja vastaavasti niiden rajoituslaatikoiden lukumäärän mukaan. Jokainen lista vastaa matriisia, jonka alkiot ovat 1 tai 0. - jos segmentit ja leikkaavat ja muuten. $n$ ${\displaystyle M_{n\times n))$ $m_{{ij}}$ $m_{ij}=1$ $i$ $j$ $m_{ij}=0$

Oletetaan, että matriisi pysyy käytännössä muuttumattomana iteraatiosta toiseen. Tätä varten viivaosien luettelo on merkittyjen ääripisteiden muodossa. Jokaisella luettelon elementillä on ääripisteen koordinaatit ja yksilöllinen numero, joka tunnistaa janan. Lista lajitellaan koordinaattien mukaan ja matriisi päivitetään oikeassa järjestyksessä. On helppo varmistaa, että ilmoitettu algoritmi tarjoaa riittävän korkean suorituskyvyn, jos rajoitusruutujen konfiguraatio ei muutu merkittävästi yhdessä iteraatiossa. ${\displaystyle M_{n\times n))$

Jos kyseessä ovat muotoaan muuttavat kappaleet , kuten kudoksen fyysisen mallin renderöinti , ei ole mitään tapaa käyttää tarkempaa menetelmää - alla kuvattu parinpoistoalgoritmi ja " n - bodyn karsimista" käyttävistä algoritmeista tulee paras menetelmä. .

Jos kohtauksessa olevien fyysisten kappaleiden nopeudelle voidaan asettaa maksimiarvorajoitus, voidaan kohteiden parit poistaa törmäysehdokkaiden luettelosta niiden alkuperäisen etäisyyden toisistaan ja aikaiterointiaskeleen koon perusteella . $\Delta t$

Pareittainen vähennys

Kun kohtauskohdepari on valittu lisätutkimuksia varten, tarvitaan tarkempi törmäystarkastus. Monissa sovelluksissa jotkin kohteista (jos niiden geometrinen konfiguraatio on suhteellisen vakio, eli ne eivät ole alttiina vakaville muodonmuutoksille) kuvataan joukolla pienikokoisia primitiivisiä, enimmäkseen kolmioita. Eli on olemassa kaksi joukkoa kolmioita ja (yksinkertaisuuden vuoksi oletetaan, että joukkojen kardinaliteetti on yhtä suuri). $S={S_1,S_2,\pisteet,S_n}$ $T={T_1,T_2,\pisteet,T_n}$

Ilmeinen tapa testata kappaleita törmäyksen varalta on testata kaikki järjestetyt kolmioparit törmäyksen varalta. Tällaisen tarkistuksen monimutkaisuus on kuitenkin , mikä on erittäin tehotonta. On tarpeen käyttää "pudotus"-algoritmia, jos mahdollista, vähentääksesi tarkistettavien kolmioparien määrää. ${\näyttötyyli (S_{j}, T_{k})}$ $\operaattorinimi{O}(n^2)$

Yleisimmin käytetty algoritmiperhe on hierarkkinen rajoitustilavuusmenetelmä . Alustavana vaiheena jokaiselle objektille (esimerkissämme tämä on ja ) lasketaan ja määritetään rajavien objektien hierarkia. Tämän jälkeen jokaisella iteraatiokerralla, kun on tarkistettava, onko kohteiden ja välillä törmäys , rajaavia tilavuuksia käytetään vähentämään testiin kuuluvien kolmioiden määrää. Yksi yksinkertaisimmista rajoitustyypeistä on pallo. $S$ $T$ $S$ $T$

Kolmioiden joukolle voidaan laskea rajoituspallo . On olemassa useita tapoja valita , tärkeintä on, että pallo peittää kokonaan kolmion muotoisten primitiivien joukon ja on samalla mahdollisimman pieni. $E$ $B(E)$ $B(E)$ $B(E)$ $B(E)$

Kun määritetään kappaleiden ja törmäyksen olemassaolo , voidaan ensinnäkin laskea pallot ja . On selvää, että jos nämä pallot eivät leikkaa, niin molemmat ja eivät leikkaa . Tämä ei kuitenkaan ole paljon tehokkaampi kuin n -kappaleen karsintaalgoritmi. $S$ $T$ $B(S)$ $B(T)$ $S$ $T$

Antaa olla joukko kolmioita. Sitten se voidaan jakaa kahteen osaan: ja . Vastaavasti voidaan osioida ja laskea rajaavat pallot ja . $E={E_1,E_2,\pisteet,E_m}$ $L(E):={E_1,E_2,\pisteet,E_{m/2}}$ $R(E):={E_{m/2+1},\pisteet,E_{m-1},E_m}$ $S$ $T$ ${\näyttötyyli B(L(S)),B(R(S))}$ ${\näyttötyyli B(L(T)),B(R(T))}$

Laskelma on, että nämä rajaavat pallot ovat paljon pienempiä kuin ja . Ja jos esimerkiksi ja eivät leikkaa, ei ole mitään järkeä tarkistaa joukon kolmioiden leikkauspisteitä kolmioista alkaen . $B(S)$ $B(T)$ $B(S)$ ${\näyttötyyli B(L(T))}$ $S$ $L(T)$

Alustavien laskelmien aikana on mahdollista tarkastella jokaista fyysistä kappaletta, joka on esitetty kolmioiden joukkona, ja hajottaa se binääripuuksi , jossa solmut (solmut) ovat kolmiojoukkoja ja niiden jälkeläiset ovat ja . Tämän puun jokaiselle solmulle voidaan laskea rajoituspallo . Tällaisessa tapauksessa, kun on tarpeen tarkistaa seuraavan kappaleparin törmäys, voidaan niiden ennalta laskettujen rajapallojen binääripuiden avulla sulkea pois merkittävä osa tarkistettavista kolmiojoukoista. $N$ $L(N)$ $R(N)$ $B(N)$

Monet "puu"-algoritmien lisätoteutukset saadaan valitsemalla muita stereometrisiä objekteja rajoittaviksi tilavuuksiksi pallojen sijaan. Kun valitaan suuntaissärmiö, joka on suunnattu yhdensuuntaisesti mittausjärjestelmän akselien kanssa ( eng. axis-aligned bounding box ), saadaan ns. AABB-puut ( eng. AABB-Trees ). OBB- puut (tai OOBB-puut ) saadaan käyttämällä laatikkoa, joka on suunnattu kohteen oman koordinaattijärjestelmän mukaan. Osa puista on helpompi päivittää, jos pääobjekti muuttuu. Jotkut puut voivat työskennellä korkeamman asteen primitiivien, kuten splineen , kanssa peruskolmioiden sijaan.

Tarkka pareittainen törmäystunnistus

Kun mahdollisen törmäyksen ehdokasparien alustava vähennys on tapahtunut, on tarpeen suorittaa tarkka yhteentörmäystarkastus jokaisen jäljellä olevan parin osalta.

Päähavainto on, että kahdelle kuperalle ei-vierekkäiselle kohteelle on olemassa taso, jossa yksi kohde on kokonaan tämän tason toisella puolella ja toinen toisella. Tämä seikka mahdollistaa nopeiden törmäysten havaitsemisalgoritmien kehittämisen kuperalle kohteelle.

Varhainen työ tällä alueella hahmotteli erotustason menetelmiä . Kaksi kolmiota törmäävät olennaisesti vain silloin, kun niitä ei voida erottaa kolmen kärjen kautta kulkevalla tasolla. Näin on, jos kolmiot ja , jossa jokainen vektori on kohdassa , voit valita kolme kärkeä - , piirtää tason kaikkien kolmen läpi ja tarkistaa, erotteleeko taso. Jos jokin näistä tasoista eroaa toisistaan, kolmiot eivät leikkaa; ja leikkaavat, jos päinvastoin mikään niistä ei eroa. Tällaisia lentokoneita on yhteensä 20. ${v_{1},v_{2},v_{3))$ ${v_{4},v_{5},v_{6))$ $v_{j}$ $\mathbb R^3$ ${\displaystyle v_{i},v_{j},v_{k))$

Jos kolmiot ovat samassa tasossa, tämä testi ei ole täysin onnistunut. Voit kuitenkin lisätä tasoja, jotka ovat esimerkiksi kohtisuorassa kolmion pintoihin nähden, ratkaistaksesi ongelman yleisessä tapauksessa. Muissa tapauksissa esimerkiksi reunoistaan koskettavien kohteiden on välttämättä kohdattava jossain kulmia, ja siksi törmäysongelman tulee pystyä ratkaisemaan yleisellä törmäyksentunnistusmenetelmällä.

Sen jälkeen on kehitetty parempia menetelmiä. Tällä hetkellä on saatavilla erittäin nopeita algoritmeja kahden kuperan monitahoisen kappaleen pinnan lähimpien pisteiden löytämiseen. Vuonna 1993 M. C. Lin käytti väitöskirjassaan lineaarisen ohjelmoinnin simpleksimenetelmän muunnelmaa [4] . Myöhemmin Gilbert-Johnson-Curthy-algoritmi korvasi tämän lähestymistavan. Nämä algoritmit lähestyvät vakiolaskenta-aikaa, kun niitä sovelletaan peräkkäin paikallaan olevien tai hitaasti liikkuvien kappaleiden pareihin, kun niitä käytetään aiemman törmäysilmaisimen iteraation alkudatan kanssa.

Kaikkien näiden edistysten tulos on kyky havaita tehokkaasti reaaliajassa tuhansien liikkuvien kappaleiden törmäykset tyypillisessä henkilökohtaisessa tietokoneessa tai pelikonsolissa .

A priori leikkaus

Tapauksissa, joissa suurin osa näyttämöllä olevista kohteista on liikkumattomia, kuten usein tietokonepeleissä, voidaan laskelmia nopeuttaa käyttämällä ennakkolaskutoimia käyttäviä menetelmiä.

Näissä tilanteissa karsiminen (pudottaminen) on toivottavaa: sekä "n-body karsiminen" että parillinen karsiminen. Näiden algoritmien laskeminen vie kuitenkin aikaa ja ottaa huomioon taustalla olevassa fyysisessä järjestelmässä käytetyt liiketyypit.

Tarkassa parittaisessa törmäystunnistuksessa algoritmi tulee erittäin riippuvaiseksi törmäyksessä mukana olevien kappaleiden liikeradalta, ja ainakin yhden kappaleen kohdalla on käytettävä numeerista juurihakualgoritmia törmäyshetken laskemiseen.

Tarkastellaan esimerkiksi kahta ajassa liikkuvaa kolmiota: ja . Milloin tahansa näiden kahden kolmion leikkaus voidaan testata käyttämällä kahtakymmentä edellä käsiteltyä tasoa. Prosessia voidaan kuitenkin parantaa, koska näitä kahtakymmentä konetta voidaan seurata ajan myötä. Jos on taso, joka kulkee pisteen läpi , tämä tarkoittaa, että seurantaan on käytettävissä kaksikymmentä tasoa. Jokaista tasoa on seurattava kolmen kärjen suhteen, mikä antaa kuusikymmentä seuranta-arvoa. Käyttämällä juurihakua näille kuudellekymmenelle funktiolle laskee tarkan törmäysajan kahdelle tietylle kolmiolle ja kahdelle tietylle liikeradalle. Jos kärkiratojen katsotaan olevan lineaarisia polynomeja (polynomeja) kohdassa , niin loput kuusikymmentä funktiota ovat kuutiopolynomeja, ja tässä poikkeustapauksessa on mahdollista saada tarkka törmäysaika kuutiojuurien kaavalla. Jotkut numeerisen analyysin asiantuntijat uskovat, että kuutiojuurikaavan käyttö ei ole numeerisesti yhtä vakaata kuin polynomin juurruttaminen. ${v_1(t),v_2(t),v_3(t)}$ ${v_4(t),v_5(t),v_6(t)}$ $P(u,v,w)$ $u, v, w$ $\mathbb R^3$ $t$

Spatiaalinen osiointi

Vaihtoehtoiset algoritmit voidaan ryhmitellä sen perusteella, että ne käyttävät tilan osiointia , joka sisältää BSP-puut , oktreet ja muut vastaavat lähestymistavat . Jos käytetty spatiaalinen osiointialgoritmi jakaa objektien sisältävän kohtauksen aluejoukkoon, ja jos kaksi objektia ovat eri alueilla, niitä ei tarkisteta leikkauspisteiden varalta. Koska BSP-puut voidaan laskea etukäteen, tämä lähestymistapa sopii hyvin seinien ja muiden kiinteiden esteiden käsittelyyn peleissä. Nämä tilan osiointialgoritmit ovat yleensä vanhempia kuin edellä kuvatut algoritmit.

Törmäysten havaitseminen tietokonepeleissä

Tietokonepelien, erityisesti konsolipelien , on jaettava monet tehtävästään hyvin rajallisten laitteistoresurssien ja hyvin rajallisten peliprosessien suoritusaikojen välillä. Näistä rajoituksista ja suhteellisen primitiivisten ja epätarkkojen törmäyshavaitsemisalgoritmien käytöstä huolimatta pelien kehittäjät ovat pystyneet luomaan visuaalisesti uskottavia ja suhteellisen realistisia fysiikan alijärjestelmiä.

Tietokonepeleissä oli melko pitkään fyysisesti vuorovaikutuksessa keskenään hyvin rajallinen määrä esineitä, joten kaikkien kohteiden risteysten tarkistaminen ei ollut ongelma. 2D-peleissä joissakin tapauksissa laitteisto pystyi havaitsemaan ja raportoimaan tehokkaasti risteäviä pikseleitä näytön spritien välillä. Muissa tapauksissa tehokas hylkääminen (vähennys) saatiin aikaan ruudun yksinkertaisella laatoituksella (murtamalla sirpaleiksi - laatoiksi ) ja sitomalla jokainen sprite laattaan, jonka kanssa se leikkaa. Rajauslaatikoita ja/tai ympyröitä käytettiin parien risteyksien tarkistamiseen, mikä katsottiin melko tarkaksi.

3D-pelit käyttävät spatiaalista osiointitekniikkaa "n-bodyn karsimiseen" ja ovat pitkään käyttäneet yhtä tai useampaa rajauspalloa yksittäiselle 3D-objektille parikohtaisten risteysten tarkistamiseen. Tarkat tarkastukset ovat olleet hyvin harvinaisia, lukuun ottamatta pelejä, jotka yrittävät matkia todellisuutta suhteellisen tarkasti. Mutta näissäkään tapauksissa risteysten tarkkoja tarkastuksia ei aina tehdä, vaan vain pelin kannalta tärkeimmissä paikoissa ja/tai tilanteissa.

Koska pelien ei tarvitse jäljitellä tarkasti todellisuutta, vakaus ei ole ratkaisevaa. Lähes kaikissa peleissä käytetään jälkikäteen törmäysten havaitsemismenetelmiä, ja törmäykset ratkaistaan usein hyvin yksinkertaisilla säännöillä. Esimerkiksi jos virtuaalinen hahmo "putoaa" seinän läpi, se voidaan yksinkertaisesti siirtää takaisin viimeiseen tunnettuun "oikeaan" paikkaansa. Jotkut pelit eivät tunnista törmäystä ollenkaan, vaan yksinkertaisesti mittaavat hahmon kulkeman matkan ja jos tämä etäisyys on yhtä suuri tai suurempi kuin jokin ennalta määrätty matka, jonka hahmo voi kävellä (esimerkiksi huoneen pituus seinästä seinään), estä sitten häntä liikkumasta pidemmälle.

Useimmissa tietokonepeleissä pääkohteet törmäysten ja tunkeutumisten välttämiseksi ovat maasto ja tason ympäristö - staattiset, ei-interaktiiviset ja tuhoutumattomat rakenteet (vuoret, puut, rakennukset, aidat jne.). Tässä tapauksessa merkkiä edustaa vain yksi piste, ja binääritilan osiointimenetelmä tarjoaa käyttökelpoisen, yksinkertaisen ja tehokkaan tavan tarkistaa, onko merkkiä edustava piste ympäristössä vai ei. Merkkien ja muiden dynaamisten objektien väliset törmäykset huomioidaan ja käsitellään erikseen.

Vankka törmäyksentunnistus- ja resoluutiosimulaattori vastaa älykkäästi mihin tahansa syötteeseen. Törmäysten havaitsemisen jälkikäteen perustuvan lähestymistavan perusteella voidaan olettaa, että kilpapelissä pelaaja kiihdyttää autossa suurella nopeudella, törmää esteeseen, kuten seinään ja törmäyksentunnistusjärjestelmä havaitsee törmäyksen jälkeen. se on tapahtunut, ja silloin auto on jo "uppoutunut" seinään tai jopa "putoaa loputtomaan tyhjyyteen", jota kutsutaan "mustaksi helvetiksi", "siniseksi helvetiksi" tai "vihreäksi helvetiksi" vallitsevasta väristä riippuen. grafiikkamoottorissa . _ Siksi jälkikäteen törmäyksen havaitsemismekanismin on käsiteltävä tällaiset tilanteet oikein. Yksi ratkaisu tällaisiin tilanteisiin on "jatkuvan törmäyksen ilmaisu" ( eng. Continuous Collision Detection ). [5]

Muistiinpanot

↑ Ericsson, Christer. Reaaliaikainen törmäysten tunnistus. Elsevier, 2005, s. 13.
↑ Ming Chieh Lin . _ Lin-Canny Lähimpien ominaisuuksien algoritmi . UC Berkeley (31. tammikuuta 1996). Haettu 29. heinäkuuta 2011. Arkistoitu alkuperäisestä 10. maaliskuuta 2012.
↑ Lakaise ja karsi . GameDev.ru (30. elokuuta 2007). — Algoritmin kuvaus ja esimerkkejä ohjelmakoodista. Haettu 8. heinäkuuta 2009. Arkistoitu alkuperäisestä 15. lokakuuta 2012. (Venäjän kieli)
↑ Ming Chieh Lin . _ Tehokas törmäysten havaitseminen animaatiossa ja robotiikassa (väitöskirja) (englanniksi) : päiväkirja. - Kalifornian yliopisto Berkeleyssä , 1993. (linkki ei ole käytettävissä)
↑ Erwin Coumans. Jatkuva törmäysten havaitseminen ja fysiikka (englanniksi) ( PDF ) (linkki ei saatavilla) . Sony Computer Entertainment (elokuu 2005). Haettu 30. heinäkuuta 2011. Arkistoitu alkuperäisestä 10. maaliskuuta 2012.

Linkit

OZCollide on ilmainen, nopea ja monialustainen törmäystunnistuskirjasto.
Pohjois-Carolinan yliopiston Chapel Hillissä törmäyshavaitsemistutkimuksen verkkosivusto
Oxfordin yliopiston professori Steven Cameronin verkkosivuilla artikkeli törmäysten havaitsemisesta
Kuinka välttää törmäys - artikkeli George Beck , Wolfram Demonstrations Project
IvanVR1. Törmäyksen havaitseminen (törmäyksen havaitseminen) . GameDev.ru (21. kesäkuuta 2002). Haettu: 29. heinäkuuta 2011. (määrätön)