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

Triangle Box intersection question

[es] :: 3D programiranje :: Triangle Box intersection question

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

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

glorius
Damir Nikolic
C++ developer
SR

Član broj: 4366
Poruke: 428
212.200.193.*

ICQ: 208550327


+14 Profil

icon Triangle Box intersection question19.08.2008. u 22:16 - pre 152 meseci
Pokusavam da napravim BSP algoritam za renderovanje vecih terena.
Izgradio sam BSP Tree gde svaki node ima svoj bounding box i pomocu Frustuma odredjujem koji su Box-ovi u trenutku vidljivi.

Svaki box sadrzi odredjen broj trouglova koji bi trebali da se renderuju. Da bih svakom Box-u dodelio pripadajuci broj trouglova ( onih koji se seku sa Box-om ) pokusao sam da iskoristim algoritam za intersekciju Triangle-Box ( Moller - Graphics Gems III). Algoritam kaze da se uporedjivanje vrsi izmedju trougla i Box-a koji je predstavljen jedinicnim ortogonalnim vektorima ( trougao je u world koordinatnom sistemu, box je na origin-u sa jedinicnim duzinama stranica ). Nije problem da napravim da mi svaki Box bude sa istim width, height i length ( u smislu ako je duzina terena veca od sirine, opet cu nekako moci da ga popunim kockama identicnih stranica ) ali da te velicine budu 1 nikako ne odgovara mom ( pa i bilo cijem :) ) algoritmu.

Da li ovo znaci da cu morati, posto sam odredio da sirina, visina i duzina svakog box-a budu npr. po 5 jedinica, da skaliram trougao koji uporedjujem sa ovim boxom ( da podelim svaku komponentu svake tacke trougla sa 5 ) da bih mogao da iskoristim ovaj algoritam?

Jos jedan problem je u tome sto funkcija ( Moller ) prihvata samo trougao kao parametar. Da li to znaci da cu morati box da dovedem u origin koordinatnog sistema, tj. da sve tri tacke trougla transliram inverzno za vrednost udaljenosti box-a od origina?

Primer:

Funkcija prihvata samo koordinate tacaka trougla: TriMoller( Triangle )

Box: center = (1, 2, 3), nonUnitSize = width = length = height = 5;
Triangle: p1, p2, p3

1. prvo izvrsimo translaciju trougla inverzno poziciji centra box-a

p1' = p1 - center;
p2' = p2 - center;
p3' = p3 - center;

2. Izvrsimo skaliranje novodobijenih tacaka tako sto svaku tacku delimo sa nonUnitSize

p1'' = p1'/nonUnitSize ( naravno, ovde se svaka komponenta (x, y, z) deli sa nonUnitSize )
p2'' = p2'/nonUnitSize
p3'' = p3'/nonUnitSize

triangle(p1'', p2'', p3'')

TriMoller( triangle )

Nadam se da sam bio jasan onim ljudima koji su se sreli sa ovim problemom i videli ovu funkciju.
Mozda sam cak i sam sebi odgovorio na pitanje ali, ovo je malo slozeniji algoritam ( jedva cekam da proradi :) ) tako da mi je bilo kakva pomoc dobro dosla :)

EOF
 
Odgovor na temu

tosa
上海, 中国

Član broj: 1811
Poruke: 1339
58.32.235.*

ICQ: 14293955
Sajt: https://github.com/milost..


+46 Profil

icon Re: Triangle Box intersection question20.08.2008. u 02:28 - pre 152 meseci
Code:
int triBoxOverlap( float boxcenter[3], float boxhalfsize[3],float triverts[3][3] );

Ovo je zaglavlje funkcije sa ove adrese: http://www.cs.lth.se/home/Tomas_Akenine_Moller/code/tribox2.txt
Bez čitanja koda, pretpostavljam da možeš da pošalješ bilo kakav boks i trougao a da je jedino ograničenje
da su i boks i verteksi već transformisani - što je za teren više nego uobičajen scenario.
 
Odgovor na temu

glorius
Damir Nikolic
C++ developer
SR

Član broj: 4366
Poruke: 428
212.200.238.*

ICQ: 208550327


+14 Profil

icon Re: Triangle Box intersection question20.08.2008. u 07:19 - pre 152 meseci
Hej, odlicno!
Izgleda da je ona verzija koju sam ja nasao 'extremno' optimizovana posto stalno u tekstu govore o nekoj brzoj verziji i sta ti ja znam.
Hvala!
EOF
 
Odgovor na temu

tosa
上海, 中国

Član broj: 1811
Poruke: 1339
58.32.235.*

ICQ: 14293955
Sajt: https://github.com/milost..


+46 Profil

icon Re: Triangle Box intersection question20.08.2008. u 07:30 - pre 152 meseci
Usput, za bilo kakve intersekcije evo zgodne tabele sa referencama:
http://www.realtimerendering.com/intersections.html
 
Odgovor na temu

glorius
Damir Nikolic
C++ developer
SR

Član broj: 4366
Poruke: 428
212.200.238.*

ICQ: 208550327


+14 Profil

icon Re: Triangle Box intersection question20.08.2008. u 13:45 - pre 152 meseci
Super sajt! Hvala!

Inace, taj teren bi trebao da ima dosta poligona i da bude prilicno veliki. Pogled na njega bi bio kao u npr. Diablu sa ogranicenim maximalnim udaljenjem kamere od lika ( bez rotacije kamere, kao sto je uradjeno u Titan Quest-u, mislim da donosi manje konfuzije kod Diablo-likih RPG igara ). Mislio sam da preprocesiram visibility tako sto svaki cube nosi informacije i o okolnim cube-s koji su vidljivi ( sa maximalnim udaljenjem kamere - kamera ce moci da se zumira od i ka liku ) tako da ne moram posle da proracunavam koji cube-ovi su trenutno vidljivi pa da nalazim poligone i da ih pripremam za rendering vec da odmah imam listu poligona koja treba da se renderuje. Jos jedna optimizacija bi bila i sortiranje poligona po atributima i to bi moglo da se uradi u preprocessing delu.

Koliko je ovo dobra tehnika i da li postoje neki problemi ( koje ja trenutno ne vidim ) i da li je bolje koristiti ovu ili realtime tehniku ( zbog fleksibilnosti - opet, ne znam koja su ogranicenja ) , naravno, uzimajuci u obzir da kamera nece gledati ceo svet vec samo deo terena gde se nalazi lik.
EOF
 
Odgovor na temu

tosa
上海, 中国

Član broj: 1811
Poruke: 1339
58.32.235.*

ICQ: 14293955
Sajt: https://github.com/milost..


+46 Profil

icon Re: Triangle Box intersection question21.08.2008. u 03:23 - pre 152 meseci
Po meni, dosta je bolje koristiti neku varijaciju na temu ovoga što ti radiš jer real time tehnike
(pretpostavljam da pričaš o ROAM i sličnim algoritmima) zahtevaju da se dinamički update-uju verteks
baferi ili indeks baferi, ili u najgorem slučaju oba. Sa unapred definisanim listama poligona dosta
pojednostavljuješ stvari. Kao što si i sam primetio, manja je fleksibilnost statičkih bafera zato što
modifikacije terena postaju relativno skupe u odnosu na frejm-to-frejm cenu renderinga terena, mada je
kod dinamičkih algoritama ta cena konstantno veća. U suštini, ako nemaš mnogo modifikacija terena
ja bih preporučio statičke bafere i jednostavan vizibiliti.

Jedna stvar, pošto imaš gomilu kockica na mapi, dovoljno ti je da imaš sferu koja okružuje kameru, sa
radijusom koja je maksimalna vidljivost, i sve kockice koje su unutar sfere (skroz jeftin test) a nalaze
se ispred kamere (testiraš ugao) su vidljive. Mada je moguće da propuštam neki detalj...
 
Odgovor na temu

Filip Strugar
Filip Strugar
Leamington Spa, UK

Član broj: 9871
Poruke: 383
*.demon.co.uk.

Sajt: www.rebellion.co.uk


+1 Profil

icon Re: Triangle Box intersection question21.08.2008. u 13:06 - pre 152 meseci
Mozes i da pogledas lib za rendering terena na kome (ponekad...) raduckam. Free je, vecina source coda je downloadable & free.
Baziran je na statickim 'streamabilnim' baferima i mesh mip-mapping-u - prakticno sve teren podatke iskompajliras u jedan streamable file, i onda tvoj program/igra samo ucitava potrebne delove i prikazuje ih - CPU se ne koristi skoro uopste 'at runtime'.

Mozda se ne uklapa u ono sto tebi treba, ali niko ti ne brani da pokupis ideju tu i tamo :)

www.advantageterrain.com
 
Odgovor na temu

[es] :: 3D programiranje :: Triangle Box intersection question

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

Postavi temu Odgovori

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