Bod intersekce pohybující se koule a trianglové polévky

[Játro.m]

Nazdar,

jak vyplývá z nadpisu, hledám nějaký přesný a šikovný řešení pro kolizi pohybující se koule která je definovaná radiusem, pozicí a direkcí.
Koule představuje granát a jeho pohyb je dejme tomu exponenciální.

Trojúhelník jsou obyčejný 3 vertexy a normála.

Doposud jsem používal nějakou http://nopaste.ceske-hry.cz/223434 vygooglenou funkci pro kolizi těchto dvou primitiv, ale jelikož je ta funkce pro ty kolize strašně pomalá a v některejch případech nepřesná, tak bych se jí rád zbavil.

Ještě pro upřesnění, když jsem tuhle funkci měl v cyklu kde updatuju fyziku, tak je přesná, problém je ve velkým dopadu na výkon, kde se to pohybovalo okolo 9ms a to si prostě nemůžu dovolit.

Moje nápady byly, že bych provedl klasický raycast z původní pozice hodu granátu, vůči trojúhelníkům, se kterýma může granát kolidovat - mění se pouze direkce paprsku a díky tomu bych nejspíš došel na přesný průsečík s trojúhelníkem.

kód funkce pro raycast: http://nopaste.ceske-hry.cz/223435

Tahle metoda ale nefungovala, vždycky se mi podařilo dostat falešnej průsečík.

Je ten nápad s raycastem uplně napytel? Nemám žádnej nápad, proč mi ta funkce vrací falešný kolize, zkoušel jsem laborovat s argumentama a jediný co mě napadlo, tak je špatná direkce paprsku, kterou jsem vzal direkci pohybu z fyziky a znormalizoval.

Budu rád za jakoukoliv odpověď, která by mě pomohla tuhle pekelnost vyřešit.
_________________
Jeden z vývojářů hry Grenade Madness.

[VODA]

Zkus si pročíst tohle. Snažil jsem se najít odkazy na net, ale většina článků z gamedev už neexistuje. Tak jsem zabalil postahované zdroje.

Když jsem programoval kolizní systém, tak jsem vycházel z těchto zdrojů + optimalizace pak pomocí octree...
_________________
Opravdovost se pojí s trýzní...

[perry]

Co zkusit tohle: http://cg-dev.ltas.ulg.ac.be/inf/Paper_46.pdf
Nějak podrobně jsem to nestudoval, ale z letmého projetí to vypadá dobře...
_________________
Perry.cz

[]semo[]

A s kolika trojúhelníkama tu kolizi počítáš? Máš nějaký optimalizační struktury? Kdybys měl jednoduchý octtree, tak pomocí AABB toho granátu vyzobneš jen pár trojúhelníků a testneš je. Nebo raději místo AABB, použít ty raycasty, jak píšeš. Ale raději třeba 4 ve stejném směru (granát by byl mezi nimi). No a pak máš jen pár trojúhelníků, který testneš vůči kouli a nemusíš se vůbec trápit s nějakou rychlostí funkce trojúhelník vs. koule. (Pokud těch granátů nebudeš házet tuny :-))
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory

[Vilem Otte]

Spíše bych doporučil přímo protestovat testy Sweep-sphere - triangle test: například: http://www.flipcode.com/archives/Moving_Sphere_VS_Triangle_Collision.shtml nebo lépe http://www.scribd.com/doc/70705422/14/The-sweep-test

Optimalizace pro komplexní scénu je poté triviální - buď pomocí spaciálních stromů (Octree, či lépe KD-tree), nebo pomocí BVH (hierarchií ohraničujících těles - bounding volume hierarchy).

Standardním prohledáváním do hloubky se dostaneš až na listy kde je geometrie, které jsou v intersekci s koulí, proti každému z nich provedeš zmíněný sweep test.
_________________
Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.

[Játro.m]

Úžasné! Granáty už nepropadají při nízkejch frameratech.
Použil jsem kód z flipcodu, kterej doporučoval Vilem.
Vyřešeno.

Teď otázka mimo topic, ale přece.

Mám 3rd kameru, na hráčově ramenu, provádím tam kolizi s geometrií levelu pomocí jednoho paprsku - (pozice středu kamery, inverzní direkce kamery a radius) a testuju vzdálenost do určitýho maxima - rozuměj, funkce pro průsečík s geometrií mi vrátí nejbližší vzdálenost a pokud je vzdálenost menší než nějaký maximum v mým případě 100.0, tak se radius kamery zmenší na tuhle vzdálenost. Princip co jsem použil je sice sexy, funguje, ale občas se stává, že když tou kamerou zajedu do geometrie, tak se sice přisune k hráčově ramenu, ale klepe se, nebo uplně mine, WTF.

Založil jsem to na faktu, že když budu kolidovat s jedním trojúhelníkem, kterej při té kolizi vyberu a bude se ta kamera hejbat minimálně, tak to musí přece vracet stejnou vzdálenost, jenže nevrací, poskakuje to o jednotky.

Klidně bych si nechal poradit nějakej lepší systém, protože v tomhle ohledu jsem hodně vařil z vody a inspiroval se na nějaké kameře v unity, kde je komplexní systém kolizí a netuším jak to funguje na pozadí.


_________________
Jeden z vývojářů hry Grenade Madness.

[Ladis]

Pokud to přeskakuje mezi polygony a nevymyslíš to jinak, tak výsledek můžeš třeba průměrovat z posledních snímků.
_________________
Award-winning game developer

[VladR]

To velmi nepomoze, odstrani to sice to seknutie, ale zanesie to delay, co bude pre hraca na nervy.

Jatro.m : Azda by si nechcel, ze tak jednoduchy system kamery bude fungovat vo vsetkych pripadoch ?

Jednoduche, ale pracne riesnie by bolo, ze mas rucne spraveny tzv. CameraBoundingBox v leveli, kde si to naeditujes (aj s pripadnymi inymi parametrami).
Ale to by sme museli najprv vidiet v pohybe, ze aky rozsah uhlov ta kamera ma, ci to je nejako fixne, alebo s amozes natocit lubovolne....

[Vilem Otte]

Obecně většina her (i profesionálních) s tímto mívá problém (tedy pochopil-li jsem správně problém - mezi kameru a postavu se dostane geometrie a hráč nevidí postavu, příp. scénu).

Camera bounding box je jedna z možností jak to provést (jak popsal VladR, nicméně pouze pro statický mesh).

Zatím nejefektivnější řešení jsem viděl u her na Arauně a Brigade - kde se provede raycast vícero polopřímek a dle toho se stanoví pozice kamery (nedělá se jen do směru pohledu, ale také do směru možných rotací) - chce to však celkem rychlý, přesný a efektivní ray tracer.

Další možné řešení je zneviditelňovat objekty (třeba i za pomocí textury - ať je pěkný přechod) mezi kamerou a postavou.
_________________
Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.