#1 calcolare bounding box

ciao, dato un post recente in cui si parlava dell'importanza di avere strumenti di debug che disegnino i frustum e i boundingbox
vorrei fare in modo di integrare questa features nel mini engine che sto facendo

in particolare pensavo ad un metodo

computeBox(vec3f *points, vec3f axis[3])

che prende 3 assi su cui orientare il box, e tutti i punti di un oggetto. dati questi parte da un cubo di dimensioni 0-0-0 allineato agli assi, cicla su ogni punto e si allarga per comprenderlo..

esistono modi migliori? (sicuramente..)

#2 RE: calcolare bounding box

L'operazione del calcolo del bounding volume direi che al 99.9% è un operazione fatta nei tool. E alla fine fine i vertici te li devi scorrere.

Piuttosto... curiosita' chi ti dice quali sono gli assi migliori da passare come parametro?

Poi...perche' assumi che i vertici del modello siano tali da avere 0,0,0 come centro (puo' essere che si... puo' essere che no... dipende dal modellatore). Se allarghi il cubo, e' come se considerassi il punto 0,0,0 come un vertice appartenente al modello (molto meglio partire dal primo vertice valido).

Se vuoi che le lunghezze siano rispetto agli assi passati come argomento inoltre dovrai fare una proiezione dei vertici, non potrai allargare la box con un semplice "if (x > max.x) max.x = x" perche' un test del genere funzionerebbe solo se si vuole fare una AABB. Te lo dico siccome parli di un generico allargare e non mi e' chiaro se hai pensato a questo fatto. Se si, ignora pure.

#3 RE: calcolare bounding box

dipende sempre se è AABB, allora lo devi fare "preventivamente" cercando x e y massimi
e mettendo come centro la media dei vertici.....

però ecco poi non conviene molto (a mio parere) per oggetti dinamici, perchè il calcolo se pur semplice è molto dispendioso, se si usa invece un BOX OBB, allora inizialmente calcoli il bur. box e poi gli applichi la stessa matrice del modello in real time, il che è molto più veloce, il problema è che con le OBB devi usare il teorema dei assi separati (loooool lo so rinomino.... in italiano o pseudo italiano)

che non è semplicissimo e neanche velocissimo ....
inoltre non so, se ti serve per vedere se sanno nello schermo, non so come puoi fare per vedere se sono visibili......


forse crei un box OBB grosso quanto back screen e lungo fino al front screen, e poi cracchi con obb,
... per velocità applichi ad ogni oggetto una spera e prima controlli quella...prima del obb

sfera = centro: media dei vertici, raggio: max(vertici)

#4 RE: calcolare bounding box

Citazione: Te lo dico siccome parli di un generico allargare e non mi e' chiaro se hai pensato a questo fatto. Se si, ignora pure.

ehehhehe hai fatto proprio bene
confondevo il boundigbox con un aabb e pensavo che gli assi di allineamento fossero un parametro del bounding box.. invece di boundingbox ce ne sono infiniti e il "migliore" è il più piccolo fra tutti i possibili aabb..

beh direi che mi limiterò a calcolarmi l'aabb (partendo dal punto medio e allagandolo con un if come quello scritto da tx77) e la sfera con la formula di Gabriele

comunque per quanto riguarda la proiezione beh non ci avevo proprio pensato però sarebbe da calcolare di ogni punto la proiezione sui tre assi e poi prendere di questi nuovi punti proiettati i massimi giusto?

beh interessante ma per ora oltre a qualche collision detection non ci vedo troppi sviluppi e per impratichirmi un po' penso gli aabb mi bastino e avanzino

ma una domanda molto ingenua tutti voi che fate indigames da un bel po' per queste cose vi siete scritti tutti librerie vostre o usate chessò engine come.. beh cosa c'è in giro che fa questo genere di cose? box2d forse?

#5 RE: calcolare bounding box

(27-04-2011 23:10)pykint ha scritto:  beh direi che mi limiterò a calcolarmi l'aabb (partendo dal punto medio e allagandolo con un if come quello scritto da tx77) e la sfera con la formula di Gabriele

Non vedo la necessita' di mettere in ballo punti medi e sfere..
AABB = bounding box allineato a gli assi (dell'oggetto)... il piu' semplice che c'e'. Ed e' individuato dalla coppia di coordinate: min(vertici), max(vertici)


Questo bounding box basta per fare operazioni semplici quali il culling per il rendering.

Se invece si hanno piu' oggetti che devono interagire in uno spazio comune (as esempio World-Space o WS).

Allora il bbox (rozzo ma veloce) si calcola cosi':
1) Generare 8 vertici del box individuato da bboxLS.min/max
2) Trasformare gli 8 vertici da local-space a world-space
3) Calcolare boxWS.min/max facendo min/max degli 8 vertici appena trasformati

..gli OBB invece non li consiglio.. troppe rogne per un box (^^;)

#6 RE: calcolare bounding box

non ho capito il punto 3, a cosa servirebbe?

#7 RE: calcolare bounding box

(28-04-2011 8:49)morgoth90 ha scritto:  non ho capito il punto 3, a cosa servirebbe?

Dal momento che hai precalcolato il min-max dei vertici in local space se devi testare se il tuo oggetto è dentro o fuori da un frustum in world space devi applicare agli 8 spigoli della tua AABB la matrice di trasformazione dell'oggetto.
Cosi facendo ricavi 8 vertici in world space orientati arbitrariamente nello spazio. Poi per il test frustum vs AABB devi rifare la AABB e la fai solo sugli 8 punti appena ricavati.
Non puoi testare una AABB "ruotata" perche' per gli oggetti dinamici nessuno ti dice che e' ancora una AABB (e cmq. anche se rimanesse allineata agli assi, hai calcolato prima una AABB in local space quindi devi come minimo traslare).

#8 RE: calcolare bounding box

(28-04-2011 9:45)Tx77 ha scritto:  

(28-04-2011 8:49)morgoth90 ha scritto:  non ho capito il punto 3, a cosa servirebbe?

Dal momento che hai precalcolato il min-max dei vertici in local space se devi testare se il tuo oggetto è dentro o fuori da un frustum in world space devi applicare agli 8 spigoli della tua AABB la matrice di trasformazione dell'oggetto.
Cosi facendo ricavi 8 vertici in world space orientati arbitrariamente nello spazio. Poi per il test frustum vs AABB devi rifare la AABB e la fai solo sugli 8 punti appena ricavati.
Non puoi testare una AABB "ruotata" perche' per gli oggetti dinamici nessuno ti dice che e' ancora una AABB (e cmq. anche se rimanesse allineata agli assi, hai calcolato prima una AABB in local space quindi devi come minimo traslare).

una domanda sciocca, AABB in 3D come la confronto con lo schermo?

Perché non è che devo vedere i singoli punti sullo schermo, può capitare che AABB box sia enorme e i 8 punti siano fuori dallo schermo ma non il modello, dovrei fare una cosa del genere: Asse X e Y come fosse un AABB normale, mente asse Z >= 0 ???
(pia ignoranza XD)

#9 RE: calcolare bounding box

molto utile cercare di risolvere queste cose da soli ma alla fin fine sono problemi "risolti" e c'e' un bordello di letteratura a riguardo. Conviene studiare metodi esistenti per non reinventare l'acqua calda o perdere troppo tempo su strade sbagliate.
Tanto per esempio questa pagina e' ottima e riporta un algoritmo e anche potenziali ottimizzazioni nel caso dei quadtree/octree.

#10 RE: calcolare bounding box

Per l'OBB c'e' questo metodo:
http://citeseer.ist.psu.edu/viewdoc/down...1&type=pdf
Non c'e' da spaventarsi per il calcolo degli autovalori, come invece dicono qui ("hard work")
http://www.gamedev.net/topic/149413-comp...n-obb-how/
perche' si tratta di una matrice 3x3!

#11 RE: calcolare bounding box

ecco che non vi seguo

premetto limitando il campo: a me serve il box (aa bb o b che sia) per fare: collision detection poco accurato (intersezione box-box), mouse picking (intersezione box-ray), poco altro (per ora).

normalmente io un oggetto per ora lo disegno così:

dove obj.position e obj.dimension sono vec3f, obj.points e obj.normals sono array di vec3f e cosìvia

fin qui ok, gli aabb minmax (chiamiamoli così) li faccio e mi sembra mi bastino.
e sono il localspace perchè sono sotto al translate, obj.points sono normalizzati fra 0 e 1.

a cosa mi servirebbero queste coordinate in world space?
perchè nel passo 3 ricalcoli i minmax? non basta avere gli 8 vertici in world space? lo fai per allinearli di nuovo con gli assi?

per fare culling se ho i box aabb non mi basta fare l'intersezione fra aabb-oggetto e cubo di frustum?

#12 RE: calcolare bounding box

li ricalcola perchè si presume che il corpo sia stato ruotato invalidando così l'AABB. Teoricamente potresti calcolarti l'AABB dei verti in worldspace ma dovresti farlo ad ogni ciclo di update (o comunque quando il corpo cambia orientazione) quindi è preferibile calcolarsi l'AABB in local space (che non cambia più) e ad ogni update calcolarsi l'AABB in world space MA in questo caso si tratta solo di 8 vertici

edit:

forse è meglio un'immagine:



sulla sinistra l'AABB in local space (rettangolo rosso)
sulla destra come vedi l'AABB viene trasformato in world space (rettangolo blu) ---> ps non è più un AABB
quindi viene ricalcolato l'AABB in world space (rettangolo arancione)

#13 RE: calcolare bounding box

(28-04-2011 13:45)CdrJameson ha scritto:  Per l'OBB c'e' questo metodo:
http://citeseer.ist.psu.edu/viewdoc/down...1&type=pdf

E' un classico, ma forse overkill, perche' va addirittura a creare un albero di OBB.

Citazione:Non c'e' da spaventarsi per il calcolo degli autovalori, come invece dicono qui ("hard work")
http://www.gamedev.net/topic/149413-comp...n-obb-how/
perche' si tratta di una matrice 3x3!

Interessante, ma visto che parte con il calcolo di un convex hull, si vede che c'e' un bel po di lavoro da fare (tanto vale fermarsi al convex hull ?).

Personalmente sono arrivato alla conclusione che OBB e' troppo lavoro.. specie al giorno d'oggi, dove mandare un oggetto in piu' (falso positivo) alla scheda video non e' la fine del mondo.

Ovviamente poi dipende tutto dall'applicazione specifica.
Se si hanno tanti modelli relativamente piccoli, l'AABB funziona bene. Se invece si hanno modelli molto grandi e non strutturati, allora la soluzione che cacola OBB tree da una "vertex/poly soup" comuncia ad essere piu' importante (e possibilmente tanto altro lavoro di processing della geometria: partizioni, ottimizzazioni, semplificazioni).

..ma generalmente nel game dev ci si aspetta modelli gia' abbastanza spezzettati e semplificati da parte dei modellatori.

---

(28-04-2011 14:05)hurricane86 ha scritto:  

RIP ! 8)

(sara' Giotto che si rivolta nella tomba ? ehehe)

#14 RE: calcolare bounding box

(28-04-2011 14:47)TheCrib ha scritto:  RIP ! 8)
(sara' Giotto che si rivolta nella tomba ? ehehe)

ahahahah
in realtà doveva essere una spada

#15 RE: calcolare bounding box

beh comunque l'immagine ha chiarito perfettamente : D grazie!

rimane comunque il dubbio che con il box blu si fanno un sacco di cose: collisioni, picking etc.. a che serve calcolarsi quello arancione?

e per andare da quello rosso a quello blu come faccio? la risposta è sicuramente: per passare da localspace a worldspace applichi la stessa matrice di trasformazione del modello ma..
se le rotazioni le faccio con dei glrotate.. come la tiro fuori la matrice? con glGetDoublev (GL_MODELVIEW_MATRIX) ?
e una volta che ho quella e ho gli 8 punti.. ?