Gilbert-Johnson-Keerty-algoritmi

Gilbert -Johnson-Kerthi - algoritmi ( lyhennettynä GJK ) on algoritmi kahden kuperan joukon (objektin) välisen etäisyyden määrittämiseksi. Toisin kuin monet muut etäisyysalgoritmit, GJK ei vaadi geometriatietojen tallentamista mihinkään tiettyyn muotoon. Sen sijaan GJK-algoritmi luottaa täysin funktion tukeen ja luo iteratiivisesti (iteraatioita käyttämällä) lähimmät yksinkertaistukset kahden kuperan objektin välisen etäisyyden määrittämiseksi oikein . Samaan aikaan GJK-algoritmi käyttää työssään Minkowskin summan käsitteitä kahdelle konveksille muodolle.

Jos etsit kahden ei-kuperan objektin välistä etäisyyttä, voit: [1]

jaa ei-kupera objekti useisiin kuperoihin ja käytä sitten menetelmää tuloksena oleviin kuperakohteisiin;
esittää geometriaa kolmiomaisena pintana ja käyttää yleistä kolmioverkkotörmäysalgoritmia ( englanniksi mesh ), joka sisältää jälleen konveksin objektin törmäysalgoritmin käytön.

Kuvaus

Gilbert-Johnson-Keerty-algoritmi tarjoaa melko tehokkaan menetelmän konveksien objektien välisten törmäysten havaitsemiseen. Se perustuu useisiin avainkohtiin, joista on yhteenveto alla: [2]

Minkowski-summa : On olemassa kaksi joukkoaja, niiden Minkowski-summa määritellään seuraavasti: [2] $A$ $B$

A+B=\{x+y\colon \;\;x\in A,\;y\in B\}.

Tämä määritelmä näyttää olevan virheellinen, koska pisteiden summaaminen on merkityksetöntä. Tässä löysässä huomautuksessa ja tulkitaan pikemminkin vektoreina , missä on maailman koordinaattijärjestelmän origo. [2] $x$ $y$ ${\vec {x}}=\mathbf {x} -\mathbf {o}$ $\mathbf {o}$

Configuration Space Obstacle ( CSO ) . Konveksiobjektien parille annetaan niiden CSO , eli Minkowskin summa ja . Tämä joukko on erityisen hyödyllinen törmäysmäärittelyissä, koska voidaan todistaa, että ja leikkaavat, jos ja vain jos niiden kansalaisjärjestöt sisältävät koordinaattijärjestelmän origon: [2] ${\näyttötyyli (A,\;B)}$ $AB$ $A$ ${\näyttötyyli -B}$ $A$ $B$

A\cap B\neq \varnothing \equiv 0\in AB.

Lisäksi niiden etäisyys saadaan seuraavasti:

d(A,\;B)=\min\{\|x\|\colon x\in AB\}.

Vastaavasti objektiparien tunkeutumissyvyys voidaan ilmaista niiden CSO:na seuraavasti: [2]

p(A,\;B)=\inf\{\|x\|\colon x\in AB\}.

Leikkaavien kohteiden parin tunkeutumissyvyys toteutuu rajan pisteessä, joka on lähinnä koordinaattijärjestelmän origoa. $AB$

Tuki kartoitus . Support Mapping on funktio, joka ottaa vektorin ja kuperan joukon ja palauttaa "äärimmäisimmän" pisteen kuperalle objektille kyseisessä suunnassa (vektorisuunta ). Muodollisesti: [2] $S_{A}(v)$ $v$ $A$ $A$ $v$

S_{A}(v)\in A\mid v\cdot S_{A}(v)=\max\{v\cdot x\colon x\in A\}.

Erotteleva Plane/Axis : Koska kaksi esinettä ja , Taso , joka erottaa ja , jos jokaiselle pisteelle ja jokaiselle pisteelle . Vektoria kutsutaan "heikosti erottavaksi akseliksi " ja koska siinä on ainakin yksi erotustaso, joka on normaali tai vastaava, $A$ $B$ $H(v,\;\delta )$ $A$ $B$ $a\in A,\;v\cdot a+\delta \geqslant 0$ $b\in B,\;v\cdot b+\delta \geqslant 0$ $v$ $A$ $B$

v\cdot S_{A}(-v)\geqslant v\cdot S_{B}(v).

GJK-algoritmin yleinen idea on tutkia konfiguraatioesteavaruutta (CSO) kahdelle tietylle objektille ja etsiä simpleksiä, joka sisältää koordinaattijärjestelmän origon. Jos haku päättyy kielteiseen vastaukseen, eli koordinaattijärjestelmän origo on CSO:n ulkopuolella, objektit eivät leikkaa. [3] Tässä tapauksessa CSO:n piste, joka on lähinnä koordinaattijärjestelmän origoa, edustaa erotusakselia ja , ja tätä puolestaan voidaan käyttää törmäystestauksen lähtökohtana myöhemmissä iteraatioissa. [2] $A$ $B$ $A$ $B$

Toisaalta, jos haku onnistui ja sitten kohteet leikkaavat, tarvitaan laskelmia törmäysvasteen suorittamiseksi ja joitain muita törmäykseen liittyviä yksityiskohtia. Esimerkiksi tyypillinen piiri, joka yrittää määrittää tunkeutumissyvyyden, jonka puolestaan on löydettävä CSO-rajalla piste, joka on lähinnä koordinaattijärjestelmän origoa. Van den Bergen [ 4] ehdottaa laajennettua polytooppialgoritmia tähän tapaukseen . Järjestelmämme kuitenkin laskee suhteelliset tiedot - osumapinnan ( englanniksi hit face ) , eli CSO-kuoren pinnan, joka on lähinnä koordinaattijärjestelmän origoa. Analysoimalla tämän pinnan kärkipisteitä on mahdollista määrittää, mikä kappaleen osa osallistui törmäykseen. Tässä erotetaan kaksi päätapausta: reuna-reuna törmäykset ( reuna - reuna ) ja kärkipinnan törmäykset ( vertex-face ) . Ymmärtääksesi, kuinka osat tunnistetaan, huomaa, että kukin kansalaisjärjestö vastaa vektoriparia . Esimerkiksi kuperan objektin kärki on törmännyt kuperan objektin pintaan , jolle on tunnusomaista se, että iskupinnan kaikki kolme kärkeä vastaavat samaa objektin kärkeä , mutta kolmea eri objektin kärkeä . [2] $(a_{i},\;b_{j}),\;a_{i}\in A,\;b_{j}\in B$ $A$ $B$ $A$ $B$

Käyttö

GJK-algoritmia käytetään usein simulaatiojärjestelmissä, tietokoneanimaatioissa ja tietokonepeleissä . Tässä tilassa laskettaessa lopullista (ulostuloa, tuloksena olevaa) simpleksia edellisestä iteraatiosta, sitä käytetään lähtötietona seuraavassa iteraatiossa (kehys, kehys). Jos paikka uudessa kehyksessä on lähellä samaa sijaintia vanhassa kehyksessä, niin algoritmi konvergoi yhdessä tai kahdessa iteraatiossa.

Algoritmin vakaus, nopeus ja muistijalanjälki ovat tehneet siitä suositun reaaliaikaisessa törmäyksentunnistuksessa , erityisesti tietokonepelien fysiikkamoottoreissa . [yksi]

Muistiinpanot

↑ 1 2 Jatin Chhugani, Sergey Lyalin, Aleksey Bader, Teresa Morrison, Aleksei Soupikov, Stephen Junkins, Pradeep Dubey, Mikhail Smelyanskiy. Pelin fysiikan suorituskyky Larrabee-arkkitehtuurissa . Intel Software Network (13. toukokuuta 2009 (viimeksi muokattu)). — Yksityiskohtainen artikkeli, jossa tarkastellaan kaikkia modernin pelifysiikan toteutuksen näkökohtia ja ominaisuuksia sekä Intel Larrabeen pelifysiikan algoritmien optimointia . Haettu 1. heinäkuuta 2009. Arkistoitu alkuperäisestä 14. helmikuuta 2012. (Venäjän kieli)
↑ 1 2 3 4 5 6 7 8 Yalmar Ponce Atencio. 5.1 GJK- algoritmi . lcg.ufrj.br (14. lokakuuta 2005). — GJK:n matemaattinen kuvaus. Haettu 1. heinäkuuta 2009. Arkistoitu alkuperäisestä 3. huhtikuuta 2012.
↑ Toisin sanoen kaksi monitahoa leikkaavat vain, jos niiden Minkowski-ero sisältää koordinaattijärjestelmän origon.
↑ G. van den Bergen. "Tehokas törmäysten havaitseminen monimutkaisten muotoaan muuttavien mallien avulla AABB-puiden avulla." J Graph. Tools, 2(4):1-13, 1997.

Ulkoiset linkit

Gilbert, EG, Johnson, DW, Keerthi, SS Nopea menetelmä monimutkaisten objektien välisen etäisyyden laskemiseksi kolmiulotteisessa avaruudessa . IEEE Xplore (huhtikuu 1988). - Gilbertin, Johnsonin ja Kirtyn alkuperäinen julkaisu. Haettu 1. heinäkuuta 2009. Arkistoitu alkuperäisestä 3. huhtikuuta 2012.
Chong Jin Ong, Gilbert, EG Gilbert-Johnson-Keerthi-etäisyysalgoritmi: nopea versio inkrementaalisille liikkeille ( pääsemätön linkki - historia ) . IEEE Xplore (20. huhtikuuta 1997). — Parannetun algoritmin julkaiseminen. Haettu: 1.7.2009.
Objektien välisen etäisyyden laskeminen . OXFORD YLIOPISTO TIETOJEN LABORATORIO. Haettu 1. heinäkuuta 2009. Arkistoitu alkuperäisestä 3. huhtikuuta 2012.
gjkd — GJK-algoritmin 2D-toteutus, joka on kirjoitettu D -ohjelmointikielellä
Shen-Po Shiang, Yu-Ren Chien, Jing-Sin Liu. GJK-algoritmin tehostamisesta kuperoiden polyhedrien välisen etäisyyden laskemiseksi: parannusten vertailu . Tietotekniikan instituutti. Academia Cinica. Nankang, Taipei, Taiwan 11529 ROC Haettu 1. heinäkuuta 2009. Arkistoitu alkuperäisestä 24. toukokuuta 2012.
Aleksanteri Igorevitš Sinyakov. Gilbert-Johnson-Keerthi-algoritmi . GameDev.ru (20. helmikuuta 2006). — GJK:n matemaattinen kuvaus. Haettu: 1.7.2009. (Venäjän kieli)