Výpočet kolize objektů

[Juraj]

Tak zdravím Vás,

už mám zase "touhu" něco tvořit a potřebuji vaši radu

chtěl bych v 3D scéně začí se základnímy výpočty kolizí, např. kam objekt u kamery (člověk) může, kam ne, aby se nepropadl a nebo neprolezl zeď. Mě samotného napadá vytvořit si nějaké pole, které bude např. obsahovat pomocí nějakého vzorečku ifnormace zda tam a tam může a při změně pozice bych to v tomto poli testoval, ale nejsem si jist jak moc rychlé by toto řešení bylo.

Jaká je Vaše praxe?? Je více způsobů jak vypočítat kolize??

[Augi]

No mít trojrozměrné pole booleanů je sice rychlá možnost, ale jen pro statické objekty - v případě testování vzájemné kolize dynamických objektů bys musel to pole dost updatovat. Ale tahle metoda by asi byla dost paměťově náročná a taky nepřesná.

V 3D grafice se pro výpočet kolize používají často nějaké obalující objekty - např. koule nebo kvádry. Tyto objekty mohou být navíc strukturované, tzn. že nejprve se testuje kolize proti kouli a pokud je pozitivní, tak se dále testuje kolize vůči několika menším objektům (koulím, kvádrům, příp. i geometrie meshe) uvnitř velké koule.

[Juraj]

[Augi]

Jo - testuješ jen kvádry proti sobě - příp. si není problém dopsat kolizi kvádr - koule a používat oba typy obalovacích objektů.

To abys testoval jen kvádry v okolí si můžeš zajistit např. tím, že ve světě budeš mít několik oblastí (reprezentovaných např. kvádry) a každý objekt bude vědět, do kterých světových kvádrů zasahuje. Pak stačí zkoušet kolizi na objekty, které se zasahují do stejných světových kvádrů jako testovaný objekt.
Můžeš klidně udělat "pravidelné světové kvádry" tak, že si svět rozřežeš mřížkou na oblasti. Pak každé oblasti bude příslušet jedna položka v poli, kterou můžeš jednoduše naindexovat výpočtem z pozice testovaného objektu. Tato položka si bude jednoduše pamatovat, které objekty do příslušné oblasti zasahují...

[Quiark]

Pokud nemáš velkou scénu s mnoha objekty, tak by mohlo stačit každý s každým. Jinak můžeš zvážit nějaké metody na dělení prostoru (BSP trees, quadtrees, ...), se kterými se dá poměrně rychle zjistit, které objekty jsou poblíž.
_________________
Mám strach

[]semo[]

Tohle sem před pár rokama dělal ve své první hře, takže sem toho ještě moc neuměl. Udělal sem to tak, že objekty se poskládaly z několika kvádrů a koulí (přičemž kvádry jsou mnohem užitečnější, řek bych) a terén byla výšková mapa, která měla funkci pro vrácení výšky v nějakém bodě. Testoval sem každý pohybující se objekt vůči každému pohybujícímu i statickému objektu. Clustering sem dopsal až dýl (když scéna obsahovala pár stovek kolizních objektů). Abych nezapoměl, pohybující se objekty měly navíc kromě koulí a kvádrů i kolizní body pro ten terén.

Suma sumárum, potřeboval sem napsat: KvádrXKvádr, KvádrXKoule, KouleXKoule, BodXVýšková mapa.

Na Č-H jsem o tom napsal i článek, ale po velkém pádu se asi ztratil, můžu ti ho poslat.
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory

[Marek]

[]semo[]

Eosie:
i to by šlo, kdyžtak ať se některý z adminů vyjádří
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory

[OndraSej]

semo> Pravdepodobne to tu mam, takze znovuvydani by nemel byt problem. Jinak tech clanku je vic, tak ktery je tehle konkretni, at to nemusim cist
- Pojednání o optimalizaci herních 3D enginů
- Vykreslování rozsáhlé krajiny v reálném čase
- Skrytá úskalí v 3D
_________________
http://trionteam.net

[]semo[]

ani jeden :)

byl to seriál, který byl v tomto pořadí:

1) Fyzika pro lamy od lamy (a další vlnolamy)
2) Kolize a následná reakce
3) Skládání fyzikálních objektů

A druhej byl ten o kolizích. Z těch co si psal, stojí za znovuvydání Skrytá úskalí v 3D, řek bych. Ale kolizí se netýká ;)
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory

[OndraSej]

Tak ja to jeste jednou prohrabu a nebudu hledat podle jmena, ale podle nazvu.
_________________
http://trionteam.net

[]semo[]

kdyžtak to mám
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory

[Juraj]

Jen bych se chtěl ještě zeptat, jak snadno vyrvořit pomyslnou kvádr kolem daného objektu např kolem modelu??

Nevím zda se snažím jít správnou cestou, ale myslím is že by to mělo jít vypočítat pomocí world matice objektu, je to tak? Nebo existuje nějaký snažší spůsob, já daný objekt vykrelsuji po částech, proto mě jiná možnost nenapadá..

[]semo[]

Vykreslování od kolizí odděl (jestli si to myslel takhle).

Jinak jestli máš objekt složenej z více pohybujících se objektů, a každej má nějakej kvádr okolo sebe, tak by to šlo udělat takhle:

Vezmeš rohový body všech těch kvádrů, vynásobíš je světovou transformační maticí každýho toho objektu a zjistíš minima a maxima. Tím získáš osově zarovnaný kvádr. Kdybys chtěl osově nezarovnaný, tak ty bode ještě budeš muset transformovat do lokálních souřadnic kořene toho objektu (pomocí invertované světové transformační matice). Pak opět sebereš minima a maxima...

Jinak ale myslím, že to na kolize neni potřeba. Před test můžeš udělat pomocí koulí. Je to myslím rychlejší (i když to neni tak dokkonalá obálka), protože nemusíš tak náročně počítat osově nezarovnaný bounding box.

EDIT: Jestli si myslel samotný kolizní boxy, tak ty je dobrý rozmístit v nějakým editoru. Může to bejt i modeler co používají grafici (max, maya) s nějakým jednoduchým (skriptovaným) exporterem.
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory

[Juraj]

Tak jelikož moje matematika v 3D prostoru trochu pokulhává, potřeboval bych od Vás pomoct.

Potřebuj si vypočítat souřadnice např kvádru kolem vykresleného objektu, tak abych mohl testovat zda jsem náhodou neklik na daný objkt.

Osobně si myslím, že pro výpočet použiji nějaké body z world matice objectu, ale nevím jak dostat ty správné abych to mohl testovat při kliku na plátno.