Gilbert-Johnson-Keerty algoritme

Gilbert-Johnson- Kerthi -algoritmen ( forkortet GJK ) er en algoritme til at bestemme afstanden mellem to konvekse sæt (objekter). I modsætning til mange andre afstandsalgoritmer kræver GJK ikke, at geometridataene gemmes i et bestemt format. I stedet er GJK-algoritmen helt afhængig af understøttelsen af funktionen og genererer iterativt (ved hjælp af iterationer) de nærmeste simplices for korrekt at bestemme afstanden mellem to konvekse objekter . Samtidig bruger GJK-algoritmen i sit arbejde begreberne Minkowski summer for to konvekse former.

I tilfælde af at finde afstanden mellem to ikke-konvekse objekter, kan du: [1]

opdele et ikke-konveks objekt i flere konvekse og derefter anvende metoden på de resulterende konvekse objekter;
repræsentere geometrien som en trekantet overflade og bruge den generelle trekantede mesh-kollisionsalgoritme ( engelsk mesh ), som igen inkluderer brugen af den konvekse objektkollisionsalgoritme.

Beskrivelse

Gilbert-Johnson-Keerty-algoritmen giver en ret effektiv metode til at detektere kollisioner mellem konvekse objekter. Den bygger på flere nøglepunkter, som er opsummeret nedenfor: [2]

Minkowski sum : Der er to sætogderes Minkowski sum er defineret som: [2] $EN$ $B$

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

Denne definition ser ud til at være forkert, da det er meningsløst at summere pointene. I denne løse bemærkning og lad hellere opfattes som vektorer , hvor er oprindelsen til verdenskoordinatsystemet. [2] $x$ $y$ ${\vec {x}}=\mathbf {x} -\mathbf {o}$ $\mathbf {o}$

Konfiguration Space Obstacle ( CSO ) . For et par konvekse objekter vil deres CSO blive givet , det vil sige Minkowski-summen af og . Dette sæt er især nyttigt i kollisionsdefinitioner, da det kan bevises, at og skærer hinanden, hvis og kun hvis deres CSO'er indeholder oprindelsen af koordinatsystemet: [2] $(A,\;B)$ $AB$ $EN$ $-B$ $EN$ $B$

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

Derudover er deres afstand givet af:

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

På samme måde kan indtrængningsdybden for par af objekter udtrykkes i forhold til deres CSO som: [2]

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

For et par skærende objekter realiseres indtrængningsdybden af det punkt på grænsen , der er tættest på koordinatsystemets udspring. $AB$

Support kortlægning . Support Mapping er en funktion, der tager en vektor og en konveks mængde og returnerer det mest "ekstreme" punkt for det konvekse objekt i den retning (vektorretning ). Formelt set: [2] $S_{A}(v)$ $v$ $EN$ $EN$ $v$

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

Adskillelsesplan/akse : Givet to objekter og , en plan der adskiller og , hvis for hvert punkt og for hvert punkt . Vektoren er kendt som en "svagt adskillelsesakse " for og fordi der er mindst ét adskillelsesplan, der er normalt på den, eller tilsvarende, $EN$ $B$ $H(v,\;\delta )$ $EN$ $B$ $a\in A,\;v\cdot a+\delta \geqslant 0$ $b\in B,\;v\cdot b+\delta \geqslant 0$ $v$ $EN$ $B$

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

Den generelle idé med GJK-algoritmen er at udforske konfigurationsforhindringsrummet (CSO) for to givne objekter og lede efter en simplex, der indeholder oprindelsen af koordinatsystemet. Hvis søgningen ender med et negativt svar, det vil sige, at oprindelsen af koordinatsystemet ligger uden for CSO'en, så skærer objekterne ikke hinanden. [3] I dette tilfælde repræsenterer det punkt fra CSO'en, der er tættest på koordinatsystemets oprindelse, adskillelsesaksen og , og denne kan igen bruges som udgangspunkt for kollisionstest i efterfølgende iterationer. [2] $EN$ $B$ $EN$ $B$

På den anden side, hvis søgningen var vellykket, og objekterne derefter krydser hinanden, er der behov for beregninger for at udføre kollisionsreaktionen og nogle andre detaljer med hensyn til kollisionen. For eksempel et typisk kredsløb, der forsøger at bestemme penetrationsdybden, som igen skal finde et punkt på CSO-grænsen, der vil være tættest på koordinatsystemets oprindelse. Van den Bergen [ 4] foreslår en udvidet polytopalgoritme til dette tilfælde . Vores system beregner dog relativ information - hitfacet ( engelsk hit face ) , altså det ansigt på CSO-skallen, der er tættest på koordinatsystemets oprindelse. Ved at analysere hjørnerne i dette ansigt er det muligt at bestemme, hvilken del af objektet, der deltog i kollisionen. Her skelnes der mellem to hovedtilfælde: kant-kant-kollisioner ( kant - kant ) og top-flade kollisioner ( vertex-face ) . For at forstå, hvordan de konstituerende dele identificeres, skal du bemærke, at hver af CSO'erne svarer til et par vektorer . For eksempel er et toppunkt på en konveks genstand kollideret med en flade på et konveks objekt , hvilket er kendetegnet ved, at alle tre hjørner af anslagsfladen svarer til det samme toppunkt af objektet , men til tre forskellige hjørner af objektet . [2] $(a_{i},\;b_{j}),\;a_{i}\i A,\;b_{j}\i B$ $EN$ $B$ $EN$ $B$

Brug

GJK-algoritmen bruges ofte i simuleringssystemer, computeranimation og computerspil . I denne tilstand, når man beregner den endelige (output, resulterende) simplex fra den forrige iteration, bruges den som startdata i den næste iteration (ramme, ramme). Hvis positionen i den nye ramme er tæt på den samme position i den gamle ramme, vil algoritmen konvergere i en eller to iterationer.

Algoritmens stabilitet, hastighed og hukommelsesfodaftryk har gjort den populær inden for kollisionsdetektion i realtid , især i fysikmotorer til computerspil. [en]

Noter

↑ 1 2 Jatin Chhugani, Sergey Lyalin, Aleksey Bader, Teresa Morrison, Alexei Soupikov, Stephen Junkins, Pradeep Dubey, Mikhail Smelyanskiy. Spilfysikpræstation på Larrabee-arkitekturen . Intel Software Network (13. maj 2009 (sidst ændret)). — En detaljeret artikel, der overvejer alle aspekter og funktioner i implementeringen af moderne spilfysik, samt optimering af spilfysikalgoritmer til Intel Larrabee . Hentet 1. juli 2009. Arkiveret fra originalen 14. februar 2012. (Russisk)
↑ 1 2 3 4 5 6 7 8 Yalmar Ponce Atencio. 5.1 GJK - algoritmen . lcg.ufrj.br (14. oktober 2005). — Matematisk beskrivelse af GJK. Hentet 1. juli 2009. Arkiveret fra originalen 3. april 2012.
↑ Med andre ord skærer to polyedre kun hinanden, hvis deres Minkowski-forskel indeholder oprindelsen af koordinatsystemet.
↑ G. van den Bergen. "Effektiv kollisionsdetektion af komplekse deformerbare modeller ved hjælp af AABB-træer." J graf. Tools, 2(4):1-13, 1997.

Eksterne links

Gilbert, EG, Johnson, DW, Keerthi, SS En hurtig procedure til at beregne afstanden mellem komplekse objekter i tredimensionelt rum . IEEE Xplore (april 1988). — Original udgivelse af Gilbert, Johnson og Kirty. Hentet 1. juli 2009. Arkiveret fra originalen 3. april 2012.
Chong Jin Ong, Gilbert, EG Gilbert-Johnson-Keerthi-afstandsalgoritmen: en hurtig version til inkrementelle bevægelser ( utilgængelig link- historie ) . IEEE Xplore (20. april 1997). — Offentliggørelse af den forbedrede algoritme. Hentet: 1. juli 2009.
Beregning af afstanden mellem objekter . OXFORD UNIVERSITETS COMPUTING LABORATORY. Hentet 1. juli 2009. Arkiveret fra originalen 3. april 2012.
gjkd — En 2D-implementering af GJK-algoritmen skrevet i D- programmeringssproget
Shen-Po Shiang, Yu-Ren Chien, Jing-Sin Liu. Om forbedring af GJK-algoritme for afstandsberegning mellem konvekse polyedre: sammenligning af forbedringer . Institut for Informationsvidenskab. Academia Cinica. Nankang, Taipei, Taiwan 11529 ROC Hentet 1. juli 2009. Arkiveret fra originalen 24. maj 2012.
Alexander Igorevich Sinyakov. Gilbert-Johnson-Keerthi-algoritme . GameDev.ru (20. februar 2006). — Matematisk beskrivelse af GJK. Hentet: 1. juli 2009. (Russisk)