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: 1029 | Odgovora: 6 ]

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

Član broj: 28226
Poruke: 1402
212.62.47.*

ICQ: 246436949


Profil

icon Detektovanje sudara dva trougla u 3D prostoru17.09.2004. u 17:27

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.
DirectX na srpskom | GLScene na srpskom

There are only 10 types of people in this world; those who understand binary and those who don't.
17.09.2004. u 17:27 

bkaradzic
Branimir Karadžić
Titan Studios
Seattle, WA

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



Profil

icon Re: Detektovanje sudara dva trougla u 3D prostoru17.09.2004. u 18:53
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
17.09.2004. u 18:53 

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

Član broj: 28226
Poruke: 1402
212.62.47.*

ICQ: 246436949


Profil

icon Re: Detektovanje sudara dva trougla u 3D prostoru17.09.2004. u 19:00
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?
DirectX na srpskom | GLScene na srpskom

There are only 10 types of people in this world; those who understand binary and those who don't.
17.09.2004. u 19:00 

Reljam
Relja Markovic
Project Natal - Microsoft Game Studios
Seattle, WA

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

Sajt: www.linkedin.com/in/relja..


Profil

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

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

Član broj: 28226
Poruke: 1402
212.62.47.*

ICQ: 246436949


Profil

icon Re: Detektovanje sudara dva trougla u 3D prostoru17.09.2004. u 19:46
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 :)
DirectX na srpskom | GLScene na srpskom

There are only 10 types of people in this world; those who understand binary and those who don't.
17.09.2004. u 19:46 

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

Član broj: 28226
Poruke: 1402
212.62.47.*

ICQ: 246436949


Profil

icon Re: Detektovanje sudara dva trougla u 3D prostoru17.09.2004. u 19:58
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?
DirectX na srpskom | GLScene na srpskom

There are only 10 types of people in this world; those who understand binary and those who don't.
17.09.2004. u 19:58 

maxmagnus2
VA

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



Profil

icon Re: Detektovanje sudara dva trougla u 3D prostoru03.10.2004. u 11:12
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
03.10.2004. u 11:12 

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

[ Pregleda: 1029 | Odgovora: 6 ]

Postavi temu Odgovori

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