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

Detektovanje sudara dva trougla u 3D prostoru

[es] :: 3D programiranje :: Detektovanje sudara dva trougla u 3D prostoru

[ Pregleda: 2475 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

Član broj: 28226
Poruke: 1403
212.62.47.*

ICQ: 246436949


+10 Profil

icon Detektovanje sudara dva trougla u 3D prostoru17.09.2004. u 17:27 - pre 208 meseci
Koristim mesh-eve sa relativno malim brojem poligona pa razmisljam da napravim collision detect tako sto cu proveravati za (skoro) svaki trougao u oba mesha da li se seku i cim pronadjem da se seku znaci to je sudar :)

Da malo bolje objasnim ideju:

odredim bounding box za oba mesha

ako se bounding box jednog mesha ne sece sa bounding box-om drugog nema
potrebe da se dalje proverava jer se mesh-evi sigurno ne dodiruju

ako se bounding boxovi dodiruju odredim njihov presek i time dobijem
neki nov box koji cu od sad zvati samo kutija :)

na kraju uzimam trouglove iz prvog mesh-a ciji se bar jedan vertex nalaze
u kutiji (znamo sta je kutija) i odredjujem da li se seku sa trouglima drugog
mesh-a koji takodje imaju bar jedan vertex u kutiji.

Mislim da bi to trebalo da bude dovoljno brzo za mesh-eve sa malim brojem poligona. Jedini problem mi je sto ne znam kako da znam da li se dva trougla seku.
 
Odgovor na temu

bkaradzic
Branimir Karadžić
ArenaNet
Seattle, WA

Član broj: 14953
Poruke: 1630
*.pandemicstudios.com

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


+11 Profil

icon Re: Detektovanje sudara dva trougla u 3D prostoru17.09.2004. u 18:53 - pre 208 meseci
Citat:
Srki_82: Mislim da bi to trebalo da bude dovoljno brzo za mesh-eve sa malim brojem poligona. Jedini problem mi je sto ne znam kako da znam da li se dva trougla seku.


Evo ukratko jednostavno rešenje. Kažem jednostavno, jer je lako shvatljivo koliko i Bubble sort algoritam, ali je isto toliko i optimalno koliko i Bubble sort među algoritmima za sortiranje.

Prvo konstruišeš ravan na kojoj leži trougao A i proveriš da li su sve tačke trougla B ispred ili iza te ravni. Ako jesu onda presek ne postoji. Ako nisu onda izračunaš preseke svake ivice trougla B koja se seče sa ravni na kojoj leži trougao A. Onda konstruišeš ravan kroz segment između te dve tačke preseka normalnu na ravan na kojoj leži trougao A. I proveriš da li su sve tačke trougla A sa jedne ili druge strane te ravni. Ako jesu presek ne postoji. Ako nisu trebaš još da konstruišeš ravan kroz svaku ivicu trougla A normalnu na trougao A i proveriš da li su tačke preseka sa jedne ili druge strane svake ravni ivice. Ako se segment seče sa bilo kojom od ovih ravni presek postoji pa možeš prekinuti test čim pronađeš presek. Ako se ne seku onda ni preseka između trougla A i trougla B nema.

Evo jedno optimalnije rešenje:
http://www.ce.chalmers.se/old/staff/tomasm/pubs/tritri.pdf

Mada bilo bi bolje da koristiš hierarhijske bound box/sphere. Trougao-trougao presek se obično koristi kada je preciznost bitna. Za tvoju igru možeš čak da koristiš i bounding rectangles. ;)

Branimir

 
Odgovor na temu

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

Član broj: 28226
Poruke: 1403
212.62.47.*

ICQ: 246436949


+10 Profil

icon Re: Detektovanje sudara dva trougla u 3D prostoru17.09.2004. u 19:00 - pre 208 meseci
Planiram da koristim bounding rectangles za proveru da li je bombica nesto pogodila, da li je svemirski brod naisao na raketu i slicno, ali kad treba da detektujem sudar svemirskog broda sa terenom koji recimo izgleda ovako:
Code:

\
  \
    \
      \
        \
          \
            \

bilo bi glupo da se brod skuca u vazduh samo zato sto bounding box obuhvata i prazan prostor koji nije deo terena, zar ne? U ovom slucaju bih proveravao jedan trougao s jedne i mesh s druge strane. Mozda postoji neko optimalnije resenje za ovakve situacije?
 
Odgovor na temu

Reljam
Relja Markovic
San Francisco

Član broj: 531
Poruke: 1793
*.microsoft.com



+18 Profil

icon Re: Detektovanje sudara dva trougla u 3D prostoru17.09.2004. u 19:09 - pre 208 meseci
Za to mozes da koristis rectangle - triangle presek, mnogo je bolje nego da radis trougao - trougao.
 
Odgovor na temu

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

Član broj: 28226
Poruke: 1403
212.62.47.*

ICQ: 246436949


+10 Profil

icon Re: Detektovanje sudara dva trougla u 3D prostoru17.09.2004. u 19:46 - pre 208 meseci
Upravu si... dovoljno je da uradim samo jednu takvu proveru i dovoljno je da saznam da li trougao sece pravougaonik u kojem se nalazi brodic :)
Verovatno ce mi nekad trebati i jedan i drugi nacin, varovatno i jos po neki :)
 
Odgovor na temu

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

Član broj: 28226
Poruke: 1403
212.62.47.*

ICQ: 246436949


+10 Profil

icon Re: Detektovanje sudara dva trougla u 3D prostoru17.09.2004. u 19:58 - pre 208 meseci
Citao sam ovo i setio se nekih formulica i zadataka koje smo vezbali na informatici (onih koje nisam mogao nikako da resim)... kako da izracunam najmanje rastojanje izmedju dva trougla. Znaci ne izmedju centara trouglova nego ono gde su trouglovi najblizi?
 
Odgovor na temu

maxmagnus2
none
VA

Član broj: 3893
Poruke: 194
*.vdial.verat.net



Profil

icon Re: Detektovanje sudara dva trougla u 3D prostoru03.10.2004. u 11:12 - pre 207 meseci
Mozda je bolje raditi sa presekom dve piramide.
Naime, objekte izdelis na piramide pa gledas da li su se neke od njih dve presekle
tj da li je neko teme jednog tela uslo u drugo telo.
Da li je uslo resava ti jednacina V1+V2+V3+V4 >V. Zapremine novonastalih tela (V1,V2,V3,V4)
sacinjenih od stranica piramide i tacke koja je usla u to telo.
V je naravno zapremina piramide za koju proveravas da li je tacka u njoj.
Nacrtaj ovo i shvatices da je tako.
Naravno mora postojati mala tolerancija vezana za jednacinu.
Naime po njoj je tacka u telu ako je V1+V2+V3+V4 =V.
To je za 2d najlakse raditi proverom povrsina a za 3d proverom zapremina.
The sleeper has awaken
 
Odgovor na temu

[es] :: 3D programiranje :: Detektovanje sudara dva trougla u 3D prostoru

[ Pregleda: 2475 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

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