Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Collision detection u 3D prostoru

[es] :: 3D programiranje :: Collision detection u 3D prostoru

[ Pregleda: 2945 | Odgovora: 3 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

PavleBgd
Pavle Joksimovic
Beograd

Član broj: 25177
Poruke: 112
*.eunet.yu.



Profil

icon Collision detection u 3D prostoru23.09.2006. u 14:54 - pre 213 meseci
Kako optimalno implementirati collision detection algoritme u 3D aplikaciji (ako se recimo koristi Quadtree/Octree scene managment) ? Da li za objekte(mesh-eve) koje napravite morate uvek da kreirate i koordinate za detekciju kolizije odn. bounding box oko objekta? Interesuje me za sada samo za najjednostavnije scene, posto sam se tek dohvatio ove teme :)
Kakav je ODE(i pogotovu OgreODE) za implementaciju svega navedenoga? Da li ga neko koristi? Ili je bolje sve napisati bez koriscenja neke slicne biblioteke?
 
Odgovor na temu

bkaradzic
Branimir Karadžić
ArenaNet
Seattle, WA

Član broj: 14953
Poruke: 1630
*.hsd1.ca.comcast.net.

Sajt: https://github.com/bkarad..


+11 Profil

icon Re: Collision detection u 3D prostoru23.09.2006. u 17:43 - pre 213 meseci
ODE ima ok koliziju i lako se integriše u neki postojeći engine. Što se tiče brzine sve zavisi šta konkretno radiš tj. koliko dinamičkih i statičkih objekata u sceni imaš.

Ako te zanima kolizija, i želiš više da naučiš o algoritmima, optimizaciji, itd. preporučujem ti ovu knjigu:
http://realtimecollisiondetection.net/

 
Odgovor na temu

dragansm
Dragan Smiljanic

Član broj: 38170
Poruke: 191
*.funcom.com.



Profil

icon Re: Collision detection u 3D prostoru23.09.2006. u 18:20 - pre 213 meseci
Predlazem ti upotrebu quadtree-a da bi efikasno pronasao koje objekte trebas da ukljucis u "jednom stepu" kretanja kontrolisanog ode-om. Drugim recima, fizicke objekte podeli u dve grupe... oni koji su u stabilnom stanju (neaktivni) i oni koji se krecu (aktivni) i upisi ta stanja u nodove u poslednjem nivou qt (listu svih fizickih objekata i broj aktivnih i neaktivinih). Ako AABBox zauzima vise nodova dodaj isti taj objekta u sve nodove u odgovarajucu grupu (akt/neak) kao i u listu. Zatim u parent node upisu broj aktivnih i neaktivnih objekata iz child nodova i tako sve dok ne dodjes do najstarijeg noda (TN). U njemu ces imati broj aktivnih i neaktivnih nodova (sto se fizike tice). Sad mozes brzo da nadjes da li postoji razlog da pokreces ODE u nekom frameu (ako je broj aktivnih objekata u TN = 0 fizika moze da kulira). Inace, ako je razlcit od nule, ispitas cetiri child noda koliko ima u svakom aktivnih i tako skaces po aktivnim nodovima sve dok ne dodjes do poslednjeg nivoa (BNs) odakle uzimas listu objekata. Za sve objekte iz BNs gde postoje aktivni objekt generisi parove (npr. ako u nekom aktivnom nodu iz BNs imas objekte A, B, C i npr. B je aktivan generisi parove AB, AC, BC. Ako susedni nod sadrzi objekte A, B, D generisi parove AB, AD, BD. Par AB vec postoji u listi pa ga ne treba dodati.
Ako nisi prestao da citas na pola sledi objasnjenje cemu sve ovo. ODE koristi ne bas tako savrsen sistem da proverava da li se preklapaju AABB za sve objekte mirovali oni ili ne... pa racunaj ako imas 400 objekata koliko je tu provera 400 + 399 + 398.... = 400*401/2. Upotrebom qt proveravas da li se AABB dva objekta seku samo u "blizini" aktivnih objekata. Nisam siguran da li su kasnije dodali hash strukturu koja radi slicnu stvar - da se izbegne iteracija reda o(N^2) - N broj objekata.
Nakon sve ove price tek imas listu kandidata za objekte koji su potencijalno u koliziji. Za sve objekte iz liste (AB, AC, BC, AD, BD,...) proveri da li im se seku AABB pa tek ako se seku AABB treba da primenis detaljan test kolizije i generisanje kolizionih tacaka. O tome mozes jako mnogo da nadjes ako nabavis Eriksonovu knjigu "Real-time colision detection". Mislim da je ODE-ov test kolizije debelo baziran na njoj.
Dakle, QT/OT mogu da ti koriste samo za nalazenje parova objekata koji su "blizu" ali nije efikasan nacin za generisanja kolizionih tacaka.
ODE je sam po sebi brz i ako ga dobro tviknes moze da bude stabilan - mislim da deo koji samo racuna kretanje objekata na osnovu polozaja, kontakta, jointa bla bla... Usko grlo je svakako nacin kako ces da implementiras CD izmedju dva objekta (ako ces da koristis samo kocke, tipa tetirs pojacan sa ODE-om onda ce ti biti dovoljno da koristis CD koja vec postoji u ODE-u, za sve preko toga najbolje da sam pises CD - po mogucnosti google->copy->paste.
Sam ODE "smo" naterali da se "vrti" na XBOX-u (uzasno spor hardver za danasnje pojmove jelte) u igri koja nazalost nikad nije ugledala svetlo dana [http://www.elitesecurity.org/t161748-0#1107304]
Inace, cela prica je cool ako je gravitacija nula (lepo za neku superdjuraizsvemiraigru).. ali ako hoces da ti objekti ne propadnu kroz podlogu moras jos dodatno za sve aktivne objekte da uradis test kolizije sa podlogom, a tu je opet lepo ako npr. koristi BSP ili vec kakvu god sturkutru kojim mozes brzo da pribavis prvo listu trouglova koje sece AABB objekta pa onda testiraj geometriju objekta vs lista "blizih" trouglova terena.
Moze ti takodje biti od koristi http://www.rowlhouse.co.uk/jiglib/ Koliko znam isti taj baja sad radi u Cryteku vec tamo na nekom Far Cry-u -- nikad cuo
 
Odgovor na temu

franticnick

Član broj: 19656
Poruke: 372
*.direct-adsl.nl.

Sajt: www.franticnick.com


+30 Profil

icon Re: Collision detection u 3D prostoru19.10.2006. u 23:44 - pre 212 meseci
Posto vec koristis Ogre3D mozda ti bude zanimljiv Scythe: http://www.physicseditor.com/

Neki od feature-a:

Citat:

Full source provided
Scythe comes with the loader source code that will load the .phs file format. From then on it is just a case of using the data you have been given to create the appropriate physics objects and entities.

Example demo
There is also a standalone demo that demonstrates loading the data into a game for the PhysX and Ogre engines. If you use a different graphics or physics engine then this code is easily adapted for your own use.

SDK
If you wish to use another custom format you can create an exporter with the SDK. Support for the PhysX and Collada formats will be added when permission comes from Ageia.

The physics file format
Scythe uses its own file format for physics entities, the .phs format. This references models externally instead of integrating them. While it means you need to pay attention to model paths, it leaves greater flexibility for editing models externally without affecting the physics file and allows for any model format to be used.

Model formats
While technically the .phs format is capable of using any model format you want, Scythe can only load models that it has a plugin for. The currently supported model formats are listed below, if your required fomat is not listed you can add support for it with the SDK.

Ogre .mesh
.3ds
Wavefront .obj

Physics engines
As Scythe exports to a proprietary format, it can be used by any physics engine. It is helpful however for Scythe's simulation mode to use your own physics engine, and to cater for variances in properties and settings across different engines. For this reason Scythe can support different physics engines, and you can add them yourself with the SDK. See the list of currently supported engines below.

 
Odgovor na temu

[es] :: 3D programiranje :: Collision detection u 3D prostoru

[ Pregleda: 2945 | Odgovora: 3 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.