Detekce kolize

Ve fyzikálních simulací, videohry, a výpočetní geometrie , detekce kolizí zahrnuje použití algoritmů k testování kolizí (průsečík zadaných pevných látek) pro výpočet podílu trajektorií, data dopadu a místa dopadu. Dopadu na fyzické simulace.

Přehled

Ve fyzické simulaci chceme provádět experimenty, například hrát kulečník . Fyzika kulečníkových koulí je dobře popsána, s použitím tuhé těleso pohyb a pružné kolize modelů . Měl by být uveden počáteční popis scény s přesným fyzickým popisem kulečníkového stolu a míčků, stejně jako počáteční polohy všech míčků. Vzhledem k určitému počátečnímu impulsu na bílou kouli (pravděpodobně v důsledku toho, že hráč zasáhl míč ocasem), chceme vypočítat trajektorie, přesné pohyby a konečné polohy všech koulí pomocí počítačového programu . Program pro simulaci této hry by měl několik částí, z nichž jedna by byla zodpovědná za výpočet přesných dopadů mezi kulečníkovými koulemi. Ukázalo se zejména, že tento příklad je velmi citlivý na numerické nestability : malá chyba ve výpočtu by mohla způsobit důležité změny v konečných polohách koulí.

Videohry mají podobné potřeby, s několika zásadními rozdíly. Zatímco fyzikální simulace by měla simulovat fyziku reálného světa co nejpřesněji, videohry to mohou dělat způsobem, který je přijatelný pouze v reálném čase a robustním způsobem. Kompromisy jsou povoleny, pokud je výsledná simulace uspokojivá pro hráče.

V oblasti výpočetní geometrie nás zajímají algoritmy umožňující přesnou detekci kolizí (spíš fyzikální simulátory). Tyto algoritmy však musí mít dobré časy provádění. Bohužel většina algoritmů používaných ve fyzických simulacích a videohrách nemá uspokojivou nejhorší složitost z hlediska Landauovy notace , i když se ukazuje, že v praxi fungují velmi dobře.

Detekce kolizí ve fyzické simulaci

Fyzické simulátory se liší ve způsobu, jakým reagují na kolizi. Mezi přístupem KISS a chytrým je velká propast . Někteří používají tvrdost materiálu k výpočtu síly, která vyřeší srážku v následujících krocích způsobem blízkým realitě. Tento výpočet může být velmi náročný na CPU, v závislosti na měkkosti objektu. Některé simulátory odhadují datum srážky pomocí lineární interpolace, vracejí se zpět do simulace a vypočítávají srážku pomocí nejabstrahující metody zákonů zachování .

Některé iterují přes lineární interpolaci ( Newtonova metoda ), aby vypočítaly datum srážky s větší přesností než zbytek simulace. Detekce kolizí využívá časovou konzistenci, která umožňuje jemnější časové kroky bez zvýšení zatížení procesoru (viz např. Řízení letového provozu ).

Po tuhé kolizi se mohou objevit konkrétní stavy klouzání a nehybnosti. Například Open Dynamics Engine používá omezení k jejich simulaci. Omezení zabraňují setrvačnosti a následně nestabilitě. Implementace nehybnosti grafem scény se vyhne tomu, aby se objekty driftovaly.

Jinými slovy

Fyzické simulátory obecně fungují dvěma způsoby: a posteriori nebo a priori . Kromě tohoto rozdílu je většina moderních algoritmů detekce kolizí rozdělena do hierarchie algoritmů.

A posteriori nebo a priori

V případě a posteriori postupuje fyzická simulace v malém časovém intervalu, poté se kontroluje, zda se objekty setkávají. V každém kroku simulace je vytvořen seznam všech kolidujících těles a polohy a trajektorie těchto objektů jsou korigovány tak, aby zohledňovaly kolizi. Říkáme, že tato metoda je a posteriori, protože nám obvykle chybí skutečný okamžik srážky; je detekován pouze tehdy, když k němu skutečně došlo.

V apriórních metodách píšeme algoritmus detekce kolizí, který bude schopen velmi přesně předpovědět trajektorie fyzických těles. Okamžiky srážek jsou počítány s velkou přesností a fyzická těla se nikdy neprotínají. Jeden to volá apriorně, protože vypočítá momenty kolizí před aktualizací konfigurace objektů.

Hlavní výhody a posteriori metod spočívají v tom, že v tomto případě algoritmus detekce kolize nemusí brát v úvahu nespočetné množství fyzických proměnných; algoritmu je dán jednoduchý seznam objektů a program vrátí seznam kolidujících objektů. Algoritmus detekce kolizí nemusí řešit tření, elastické kolize nebo horší neelastické kolize a deformovatelná tělesa. Kromě toho jsou a posteriori algoritmy v praxi jednodušší dimenze než a priori algoritmy . A priori algoritmus musí skutečně spravovat časovou proměnnou, která a posteriori v problému chybí .

Na druhou stranu, a posteriori algoritmy způsobují problémy ve fázi korekce, kde musí být opraveny křižovatky (které nejsou fyzicky správné). Ve skutečnosti je takový algoritmus někdy považován za inherentně chybný a nestabilní.

Výhody a priori algoritmů zvyšují věrnost a stabilitu. Je obtížné (ale ne zcela nemožné) oddělit fyzickou simulaci od algoritmu detekce kolize. V nejjednodušších případech však nemá problém předem určit datum srážky dvou objektů (vzhledem k některým počátečním údajům) žádné přesně definované řešení - obvykle je nutný algoritmus pro nalezení nulové hodnoty funkce .

Protože je nemožné získat přesné hodnoty, lze také použít jednoduchý a posteriori algoritmus a poté použít dichotomické vyhledávání k pokusu o výpočet počátečního okamžiku kolize, pokud existuje. Avšak kromě skutečnosti, že tato metoda může vynechat některé kolize, je známo, že dichotomické vyhledávání je relativně neúčinné ve srovnání s jinými metodami nulového vyhledávání, jako je Newtonova metoda .

Určité předměty zůstávají v kontaktu, to znamená při srážce, ale bez poskakování nebo prolínání, jako váza umístěná na stole. Ve všech případech vyžaduje situace kontaktu zvláštní zacházení: pokud se dva objekty srazí ( a posteriori ) nebo sklouznou ( a priori ) a jejich relativní pohyb je pod prahovou hodnotou, tření se stane adhezí a dva objekty jsou uspořádány do stejného grafu scény . To by však mohlo způsobit problémy v a posteriori algoritmech .

Optimalizace

Naivní přístupy k detekci kolizí mezi více objekty jsou velmi pomalé. Testování každého objektu proti sobě bude fungovat, ale je příliš neefektivní, aby se dalo použít, když je počet objektů velký. Aplikováno na objekty se složitou geometrií je testování každé plochy s každou tváří druhého objektu samo o sobě poměrně pomalé. Pro urychlení řešení tohoto problému byl proto proveden značný výzkum.

N - prořezávání těla

U problémů, kdy se několik těles pohybuje současně (například kulečníkové koule ), umožňuje krok předvýběru snížit počet párů předmětů, které je třeba při kolizi zohlednit.

U objektů existují dvojice objektů, které se mohou nakonec srazit (viz Binomický koeficient ). Iterace všemi páry by vedla k algoritmu s časovou složitostí . V kulečníkovém příkladu se třinácti míčky na stole bude testováno sedmdesát osm párů. Pokud je však v severní polovině tabulky pouze sedm kuliček a šest v jižní části, můžeme se omezit na testování kuliček severní části mezi nimi, stejně jako v jižní části. V tomto případě bude testováno pouze třicet šest párů míčků. $ne$ ${\ displaystyle {n \ zvolit 2} = n (n-1) / 2}$ $O (n ^ 2)$

Problém je v tom, že pro velké objekty, které jsou si velmi blízké, není vždy snadné najít linii (jako v příkladu kulečníku), která odděluje objekty do dvou sad bez průniku . To lze opravit pomocí rekurzivního algoritmu ; dostanete program, který vypadá, že funguje rychleji než naivní přístup obecně.

Z hlediska chování v nejhorším případě jeden upozornění, že pokud jsou všechny objekty zaujímají stejný bod z prostoru , pak to bude nutné testovacích párů. Proto nás více zajímají algoritmy, jejichž časová složitost je vyjádřena jako funkce velikosti jejich výstupu. V našem případě tyto algoritmy poběží rychleji, pokud je počet kolizí malý. $ne$ ${\ displaystyle n (n-1) / 2 = O (n ^ {2})}$

Využijte časovou soudržnost

V mnoha aplikacích se uspořádání fyzických těl z jednoho kroku na druhý mění jen velmi málo. Některé objekty se ani nepohybují. Algoritmy byly vytvořeny tak, aby výpočty provedené v předchozím kroku mohly být znovu použity v aktuálním kroku.

Z makroskopického hlediska je cílem detekce kolizí najít dvojice objektů, které by se mohly protínat. Tyto páry budou vyžadovat další zpracování. Výkonný algoritmus k tomu vyvinul MC Lin z Berkley University, který navrhl použít ohraničující rámečky pro všechny objekty ve scéně.

Ve třech rozměrech je každá krabička reprezentována kartézským součinem tří intervalů (krabička by byla ). Pozorujeme, že dvě pole a kříží se právě tehdy, když se kříží , kříží a zkříží . Předpokládá se, že z jednoho časového kroku k dalšímu, je-li a protínají, pak je velmi pravděpodobné, že bude vždy překročil v dalším kroku. Stejně tak, pokud si v předchozím kroku neprošly cestu, je vysoce pravděpodobné, že se v dalším kroku stále neprotínají. ${\ displaystyle I_ {1} \ krát I_ {2} \ krát I_ {3} = [a_ {1}, b_ {1}] \ krát [a_ {2}, b_ {2}] \ krát [a_ {3 }, b_ {3}]}$ ${\ displaystyle I_ {1} \ krát I_ {2} \ krát I_ {3}}$ ${\ displaystyle J_ {1} \ krát J_ {2} \ krát J_ {3}}$ $I_1$ $J_ {1}$ $I_ {2}$ $J_ {2}$ $I_ {3}$ ${\ displaystyle J_ {3}}$ $I_ {k}$ $J_ {k}$

Redukujeme tedy problém na následující, od jednoho kroku ke druhému, které se protínají. Máme seznam intervalů (jeden pro každou osu), všechny stejné délky (stejný jako počet ohraničujících rámečků). V každém seznamu může každý interval protínat všechny ostatní. Takže pro každý seznam máme matici z binárních hodnot a velikost : jestliže intervaly a protínají. $ne$ ${\ displaystyle M = (m_ {ij})}$ ${\ displaystyle (n \ krát n)}$ ${\ displaystyle m_ {ij} = 1}$ $i$ $j$

Předpokládá se, že matice spojená se seznamem intervalů se z jednoho kroku na druhý téměř nezmění. Chcete-li to využít, je seznam intervalů implementován se seznamem intervalů. Každý prvek seznamu je spojen se souřadnicemi konce limitů intervalu a také jedinečným celočíselným identifikátorem představujícím tento interval. Poté se použije třídicí algoritmus k seřazení seznamu podle souřadnic a aktualizaci matice v procesu. Není těžké pochopit, že tento algoritmus bude relativně rychlý, pokud se uspořádání boxů významně nezmění z jednoho kroku na druhý. $M$ $M$

V případě deformovatelných těl, jako je oblečení , nemusí být takový algoritmus použitelný a algoritmus prořezávání n-těl může být nejlepší.

Pokud je rychlost objektů omezena výše, lze dvojici objektů filtrovat podle vzdálenosti mezi nimi a doby trvání časového kroku.

Prořezávání párů

Jakmile jsme pro další výzkum vybrali pár fyzických těl, musíme kolize pečlivě zkontrolovat. V mnoha aplikacích jsou však různé objekty (pokud nejsou příliš deformovatelné) popsány sadou menších primitiv, zejména trojúhelníků. Takže teď máme dvě sady trojúhelníků a (pro zjednodušení předpokládáme, že každá sada má stejný počet trojúhelníků). ${\ displaystyle S = {S_ {1}, S_ {2}, ..., S_ {n}}}$ ${\ displaystyle T = {T_ {1}, T_ {2}, ..., T_ {n}}}$

Zjevnou věcí je prozkoumat kolize všech trojúhelníků proti všem trojúhelníkům , ale to zahrnuje srovnání , které jsou nepříjemné. Pokud je to možné, je žádoucí použít algoritmus velikosti ke snížení počtu párů trojúhelníků, které musíme zkontrolovat. $S_j$ $T_ {k}$ $n ^ {2}$

Nejpoužívanější rodina algoritmů je známá jako Hierarchical Volume Boundary Method . Jako krok předzpracování pro každý objekt (v našem příkladu a ) vypočítáme hierarchii objemů ohraničení. Pak, pokaždé, když budeme muset zkontrolovat kolize mezi, a v každém kroku, použijí se objemy hierarchických hranic ke snížení počtu párů trojúhelníků, které mají být studovány. Pro zjednodušení uvedeme příklad pomocí hraničních koulí, ačkoli bylo poznamenáno, že sféry jsou v mnoha případech nežádoucí. $S$ $T$ $S$ $T$

Pokud je množina trojúhelníků, můžeme vypočítat hraniční sféru . Existuje mnoho způsobů, jak si vybrat , pouze předpokládáme, že jde o sféru, která zcela obsahuje a je co nejmenší. $E$ ${\ displaystyle B (E)}$ ${\ displaystyle B (E)}$ ${\ displaystyle B (E)}$ $E$

Můžeme předem vypočítat a . Je zřejmé, že pokud tyto dvě sféry nemají průnik (a je velmi snadné to otestovat), pak ani ne a . Není to mnohem lepší než algoritmus ořezávání n- těl. ${\ displaystyle B (S)}$ ${\ displaystyle B (T)}$ $S$ $T$

Pokud je to však sada trojúhelníků, můžeme ji rozříznout na dvě poloviny a . Můžeme to udělat na a na , pak můžeme vypočítat (předem) hraniční koule a . Doufáme zde, že tyto hraniční koule budou mnohem menší než a . A pokud například B (s) a B (L (t)) nemají žádný průnik, pak nemá smysl testovat jakýkoli trojúhelník proti jakémukoli trojúhelníku v . ${\ displaystyle E = {E_ {1}, E_ {2}, ..., E_ {m}}}$ ${\ displaystyle L (E): = {E_ {1}, E_ {2}, ..., E_ {m / 2}}}$ ${\ displaystyle R (E): = {E_ {m / 2 + 1}, ..., E_ {m-1}, E_ {m}}}$ $S$ $T$ ${\ displaystyle B (L (S)), B (R (S))}$ ${\ displaystyle B (L (T)), B (R (T))}$ ${\ displaystyle B (S)}$ ${\ displaystyle B (T)}$ $S$ ${\ displaystyle L (T)}$

Jako předpočítání můžeme vzít každé fyzické tělo (představované množinou trojúhelníků) a rekurzivně jej rozložit na binární strom, kde každý uzel představuje množinu trojúhelníků a jeho dvě děti představují a . V každém uzlu stromu, jak předpočítáváme hraniční sféru . $NE$ ${\ displaystyle L (N)}$ ${\ displaystyle R (N)}$ ${\ displaystyle B (N)}$

Když přijde čas otestovat dvojici objektů na kolizi, lze jejich strom hraniční koule použít k eliminaci mnoha párů trojúhelníků.

Mnoho variant algoritmů se získá výběrem něčeho jiného než sféry pro . Pokud zvolíme ohraničovací rámečky zarovnané s osou, dostaneme stromy AABB. Skokově orientované skokové stromy se nazývají OBB stromy. Některé stromy se snadněji aktualizují, pokud se změní kořenový objekt. Některé šachty mohou místo jednoduchých trojúhelníků pojmout primitiva vyššího řádu, jako jsou splajny . ${\ displaystyle B (T)}$

Detekce přesně shodných kolizí

Po provedení prořezávání zůstává určitý počet párů, kandidátů na kontrolu detekce přesných kolizí.

Základní pozorování spočívá v tom, že pro jakoukoli dvojici disjunktních konvexních objektů existuje v prostoru rovina tak, že jeden z objektů leží zcela na jedné straně tohoto povrchu a druhý objekt na opačné straně. To umožňuje vývoj velmi rychlých algoritmů detekce kolizí pro konvexní objekty.

Počáteční práce v této oblasti zahrnovala metody „konvexní separace“. Dva trojúhelníky se v zásadě srazí, pouze pokud je nelze oddělit rovnou plochou procházející třemi vrcholy. To znamená, že pokud jsou trojúhelníky a kde každý je vektorem , pak můžeme vzít tři vrcholy, najít rovinnou plochu procházející každým ze tří vrcholů a zkontrolovat, zda se jedná o rovinnou separační plochu. Pokud je takovým plochým povrchem separační rovina, pak se trojúhelníky považují za disjunktní. Na druhou stranu, pokud je některou z těchto rovin separační rovina, pak se trojúhelníky považují za průsečíky. Těchto plánů je dvacet. ${\ displaystyle {v1, v2, v3}}$ ${\ displaystyle {v4, v5, v6}}$ ${\ displaystyle vj}$ ${\ mathbb R} ^ {3}$ ${\ displaystyle vi, vj, vk}$

Pokud jsou trojúhelníky koplanární, není tento test zcela úspěšný. Můžete také přidat několik dalších plochých povrchů, například ploché povrchy, které jsou kolmé na hrany trojúhelníku, abyste problém zcela vyřešili. V ostatních případech se objekty, které se spojují lícem dolů, musí nutně také někde spojit pod určitým úhlem, proto bude globální detekce kolize schopna najít kolizi.

Od té doby byly vyvinuty lepší metody. K nalezení nejbližších bodů na povrchu dvou konvexních polyedrických objektů jsou k dispozici velmi rychlé algoritmy. Rané dílo MC Lin používalo variantu simplexního algoritmu v lineární optimalizaci . Algoritmus na vzdálenost od Gilbert-Johnsonův Keerthi (v) nahradil tento přístup. Tyto algoritmy se blíží v konstantním čase, kdy se opakovaně aplikují na stacionární páry nebo pomalu se pohybující objekty, pokud jsou použity s těmito výchozími body z předchozí kontroly kolize.

Výsledkem všech těchto algoritmických prací může být detekce kolizí účinně prováděna u tisíců pohybujících se objektů v reálném čase na běžných počítačích a herních konzolách.

Prořezávání a priori

Když je většina zúčastněných objektů pevná, což se u videohier často stává, lze použít a priori metody s použitím předpočtu pro rychlejší provedení.

V tomto případě je také žádoucí prořezávání, a to jak prořezávání n-těl, tak prořezávání párů, ale algoritmy musí brát v úvahu čas a typy pohybů použitých v základním fyzickém systému.

Přesná detekce párových kolizí je vysoce závislá na trajektoriích a pro výpočet okamžitého nárazu je často nutné použít algoritmus vyhledávání digitálního kořene.

Zvažte příklad dvou pohyblivých trojúhelníků a . Průnik dvou trojúhelníků můžeme kdykoli zkontrolovat pomocí výše zmíněných dvaceti rovin. Můžeme to však udělat lépe, protože těchto dvacet plánů můžeme postupem času dodržovat. Pokud rovina prochází body dovnitř , je třeba následovat dvacet rovin . Každá rovina musí být sledována s ohledem na tři vrcholy, což dává šedesát hodnot, které je třeba sledovat. Použití kořenového rozlišení pro těchto šedesát funkcí produkuje přesné časy kolizí pro dva dané trojúhelníky a dvě dané cesty. Všimněte si zde, že pokud se předpokládá, že trajektorie vrcholů jsou lineární polynomy v , šedesát finálních funkcí jsou ve skutečnosti kubické polynomy a v tomto výjimečném případě je možné najít přesný čas kolize pomocí vzorce pro kořeny kubické polynomy. Někteří numeričtí analytici naznačují, že použití kořenového vzorce kubických polynomů pro polynomy není tak stabilní jako použití kořenového rozlišení. ${\ displaystyle {\ displaystyle {v_ {1} (t), v_ {2} (t), v_ {3} (t)}}}$ ${\ displaystyle {\ displaystyle {v_ {4} (t), v_ {5} (t), v_ {6} (t)}}}$ ${\ displaystyle {\ displaystyle P (u, v, w)}}$ ${\ displaystyle {\ displaystyle u, v, w}}$ ${\ displaystyle {\ displaystyle {\ mathbb {R}} ^ {3}}}$ ${\ displaystyle {\ displaystyle P (v_ {i} (t), v_ {j} (t), v_ {k} (t))}}$ ${\ displaystyle {\ displaystyle t}}$

Prostorové rozdělení

Další algoritmy jsou seskupeny do kategorie prostorového dělení, která zahrnuje „ oktree “, dělení v binárním prostoru (nebo BSP stromy) a další podobné přístupy. Pokud je prostor rozdělen na určitý počet jednoduchých buněk a pokud lze prokázat, že dva objekty nejsou ve stejné buňce, není nutné kontrolovat, zda se protínají. Jelikož je možné předem vypočítat stromy BSP, je tento přístup vhodný pro řešení zdí a pevných překážek ve hrách. Tyto algoritmy jsou obecně starší než algoritmy popsané výše.

Ohraničující krabice

Ohraničující rámečky (nebo ohraničující svazky) jsou většinou 2D obdélníky nebo 3D kvádry, ale jsou možné i jiné tvary. Byly vyzkoušeny ohraničující kosočtverec, minimální ohraničující rovnoběžník, konvexní trup , ohraničující kruh nebo ohraničující koule a ohraničující elipsa, ale ohraničující rámečky zůstávají pro svou jednoduchost nejoblíbenější. [3] ohraničovací rámečky se obvykle používají během počáteční fáze (prořezávání) detekce kolize, aby bylo nutné podrobně porovnávat pouze objekty, jejichž ohraničující rámečky se překrývají.

Těžiště segmentů trojúhelníků

Ve 3D modelování se často používá trojúhelníkový síťový objekt. Normálně je kolizním prvkem setkání trojúhelník-trojúhelník nebo ohraničující tvar spojený se sítí. Těžiště trojúhelníku nazýváme umístění těžiště (takové, že by bylo v rovnováze na bodu tužky). Simulaci stačí fyzickým parametrům přidat rozměr těžiště. Vzhledem k těžištěm jak pro objekt, tak pro cíl je možné určit segment spojující tyto dva body.

Vektor polohy těžiště trojúhelníku je průměr vektorů polohy jeho vrcholů. Pokud tedy vrcholy mají kartézské souřadnice , a , těžiště bude . ${\ displaystyle {\ displaystyle (x_ {1}, y_ {1}, z_ {1})}}$ ${\ displaystyle {\ displaystyle (x_ {2}, y_ {2}, z_ {2})}}$ ${\ displaystyle {\ displaystyle (x_ {3}, y_ {3}, z_ {3})}}$ ${\ displaystyle {\ displaystyle \ left ({\ frac {(x_ {1} + x_ {2} + x_ {3})} {3}}, {\ frac {(y_ {1} + y_ {2} + y_ {3})} {3}}, {\ frac {(z_ {1} + z_ {2} + z_ {3})} {3}} \ vpravo)}}$

Vzdálenost mezi dvěma body je ${\ displaystyle \ mathrm {distance} = {\ sqrt {(z_ {2} -z_ {1}) ^ {2} + (x_ {2} -x_ {1}) ^ {2} + (y_ {2} -y_ {1}) ^ {2}}}}$

Délka segmentu je tedy nastavitelným kritériem kontaktu. Jak se objekty přibližují, délka klesá na prahovou hodnotu. Koule vycentrovaná na těžiště, aby měla velikost tak, aby zahrnovala všechny vrcholy trojúhelníků.

Videohry

Videohry musí svůj omezený výpočetní čas rozdělit mezi několik úkolů. Přes toto omezení zdrojů a použití relativně primitivních algoritmů detekce kolizí byli programátoři schopni vytvořit uvěřitelné, i když nepřesné systémy pro použití ve hrách.

Po dlouhou dobu měly videohry omezený počet věcí, se kterými se musely vypořádat. Takže kontrola všech párů nebyl žádný problém. Ve dvojrozměrných hrách mohl hardware v některých případech účinně detekovat a hlásit překrývající se pixely mezi skřítky na obrazovce. V ostatních případech je mozaikování obrazovky a binování každého spritu v dlaždicích, které pokrývá, dostatečné k zajištění dostatečné velikosti a pro spárované kontroly se používají obdélníkové nebo kruhové obálky, které se považují za dostatečně přesné.

Trojrozměrné hry využívaly metody prostorového dělení pro prořezávání n-těl a po dlouhou dobu používaly jednu nebo několik koulí na skutečný 3D objekt pro párové ovládání. Přesné ovládací prvky jsou velmi vzácné, s výjimkou několika žánrů, jako je simulace. Ale ani tam nemusí být ve všech případech nutně použity přesné kontroly.

Protože hry používají zjednodušenou fyziku, není stabilita nezbytná. Téměř všechny hry využívají detekci po kolizi a kolize jsou často řešeny pomocí velmi jednoduchých pravidel. Pokud se například protagonista ocitne uvnitř zdi, mohl by být jednoduše přesunut zpět na své poslední známé dobré místo. Některé hry vypočítají, jak daleko může protagonista cestovat, než se dostane do zdi, a umožní mu pohybovat se jen tak daleko.

Trochu sofistikovanějším a výraznějším účinkem je fyzický model „ ragdoll “. Pokud je postava z videohry vyřazena z činnosti, namísto přehrávání předdefinované animace je zjednodušená kostra postavy animována, jako by to byla hadrová panenka. Tato hadrová panenka spadne a může zasáhnout prostředí, v takovém případě se chová správně.

V mnoha videohrách stačí dostat protagonisty do jediného bodu k detekci kolizí s prostředím. V tomto případě poskytují stromy dělení binárního prostoru jednoduchý, efektivní a životaschopný algoritmus ke kontrole, zda je bod zahrnut do krajiny nebo ne. Takovou datovou strukturu lze také použít k půvabné manipulaci se situací „klidové polohy“, když protagonista běží podél rozlohy. Srážky mezi postavami a srážky s projektily a nebezpečí jsou řešeny samostatně.

Simulátor bude robustní, pokud bude na jakýkoli vstup reagovat rozumným způsobem. Například, když si představíme závodní videohru s vysokorychlostními automobily, z jedné simulační fáze do druhé je možné, že auta postoupí podstatnou vzdálenost podél závodního okruhu. Pokud v cestě stojí mělká překážka (například cihlová zeď), není zcela nepravděpodobné, že by auto přes ni úplně skočilo, což je nežádoucí účinek. V jiných příkladech není „oprava“, kterou algoritmy později vyžadují, implementována správně a postavy končí ve zdech nebo spadají daleko do hluboké prázdnoty temnoty. To jsou znaky špatné detekce kolizí a špatného simulačního systému fyziky.

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z článku Wikipedie v angličtině s názvem „ Detekce kolizí “ ( viz seznam autorů ) .

http://www.cs.berkeley.edu/~jfc/mirtich/collDet.html
„Efektivní detekce kolizí pro animaci a robotiku (diplomová práce)“, Lin, Ming C z University of California (Berkeley) publikovaná v roce 1993

Podívejte se také

Související články

externí odkazy

OZCollide Bezplatná, rychlá a multiplatformní knihovna 3D detekce kolizí.
2D posuvná kolize v DarkBasic