Post on 02-May-2015
1
Intersezioni e distanze
Daniele Marini
2
Definizioni utili
• Raggio r(t) semiretta dotata di origine e direzione (solitamente la direzione è normalizzata)
• Superfici: implicite e esplicite– implicite: f(p)=0 - es: x2+y2+z2-r2=0
• dato il punto p si valuta se appartiene alla superficie risolvendo l’equazione (se =0)
– esplicite: f(u,v)=(fx(u,v),fy(u,v),fz(u,v)) - es: f()=((r sincos), (r sinsin), (r cos))
3
Rette
• Dato un punto p =(x0,y0,z0) per cui passa la retta, la sua forma parametrica è: r(t)=p+td dove d è la direzione (vettore normalizzato) e t il parametro, per t>0 abbiamo una semiretta (tipicamente il raggio)
• Le componenti sono:
rx x0 ti
ry y0 tj
rz z0 tk
t ,
4
Bounding volume
• Si definiscono tre tipi di bounding volumes: AABB, OBB, k-DOP
• AABB: axis aligned bounding box, un parallelepipedo con le facce parallele ai piani coordinati, si definisce con due valori estremiamin , amax
amin
amax
5
• OBB: oriented bounding box è un AABB ruotato rispetto agli assi principali, si può definire con un centro e tre vettori normalizzati che descrivono le direzioni dei lati
• k-DOP: discrete oriented polytope, definito da k/2 vettori normalizzati con associati due valori scalari per definire una porzione di piano; in pratica definiscono un poliedro
6
Bounding sphere
• Si utilizza anche la sfera come volume di contenimento
• Lo studio delle intersezioni con i BV è essenziale per l’efficienza
7
Intersecare rette
• Usato in ray tracing / ray casting
• Usato per calcolare collisioni
• Il raggio è una semiretta, con direzione data, e un punto di applicazione– la retta è specificata con coseni direttori e un
punto da cui passa
8
• La distanza di un punto q dalla retta r si ottiene proiettando q su r e valutando la norma:
w((q p).d)d
(q p) w
r
q
pdq-p
w(q-p)-w
9
Intersezione con segmenti
• Segmento per due punti (vettore):
• Il calcolo della intersezione di un raggio con tutti gli oggetti di una scena può essere molto costoso, si riduce sfruttando boundig volumes
• Caso più semplice di BV è la sfera
v(x2 x1, y2 y1,z2 z1)
10
Intersezione con una sfera
• Raggio in forma parametrica (vettore):
• Sfera con centro in (l,m,n) e raggio r:
x x1 (x2 x1)t x1 it
y y1 (y2 y1)t y1 jt
z z1 (z2 z1)t z1 kt
t 0,1
(x l)2 (y m)2 (z n)2 r2
11
(x1,y1,z1)
(x2,y2,z2)
0<t<1
t<0
t>1
• Sostituendo nell’equazione della circonferenza x,y,z (vediamo solo x):
(x l)2 x 2 l2 2lx
(x1 it)2 l2 2lx1 2lit
i2t 2 2i(x1 l)t (x12 l2 2lx1)
12
• a forma quadratica generale è quindi:
at2 bt c 0
con :
a i2 j 2 k 2
b 2i(x1 l) 2i(y1 m) 2i(z1 n)
c l2 m2 n2 x12 y1
2 z12 2(lx1 ny1 mz1) r2
• da risolvere come equazione di II grado; se il determinate è <0 non ci sono intersezioni, se =0 il vettore è tangente, se >0 due intersezioni, e le radici t1,t2 danno il punto di entrata e di uscita del raggio
• i,j,k sono le differenze (x2-x1) ecc. non sono coseni direttori !
13
• si ricava anche la normale alla sfera nel punto di intersezione (tangenza):
nx1 l
r,y1 m
r,z1 n
r
14
• per accelerare il calcolo si valuta prima il test di rifiuto rejection test
• le intersezioni “dietro” non interessano• si valuta il vettore origine_raggio-centro_sfera, se ne calcola il
modulo c2, se < r2 l’origine è interna alla sfera– il raggio interseca certamente, se ci interessa solo questo si termina
(es: picking) altrimenti si procede)
• si calcola la proiezione del vettore sul raggio, se <0 e se l’origine è esterna allora la sfera è dietro al raggio e si termina
• altrimenti si calcola la distanza al quadrato dal centro sfera alla proiezione del vettore sul raggio m2 se > r2 il raggio non colpisce la sfera altrimenti si calcola l’intersezione
15
Rejection test
16
Intersezione raggio triangolo (poligono)
• 3 passi:– determinare il piano su cui giace il triangolo– determinare l’intersezione piano-raggio– valutare se e’ interna al triangolo (poligono)
• usata anche per clipping, i raggi in questo caso sono i bordi del poligono e il piano è uno dei piani del frustum di visione; trovate tutte le intersezioni si genera un nuovo poligono
17
Intersezione raggio triangolo
18
Determinare il piano
• equazione del piano: Ax+By+Cz+D=0• A,B,C sono le componenti della normale al piano• il prodotto vettore tra due vettori identifica la normale• dati due lati V, W del triangolo calcoliamo la normale:• dove i,j,k sono i versori, quindi A,B,C sono:
• D si ottiene sostituendo un vertice del poligono nell’equazione (un punto che giace nel piano)
nvw(v2w3 v3w2)i (v1w1 v1w3)j (v1w2 v2w1)k
A v2w3 v3w2 B v3w1 v1w3 C v1w2 v2w1
19
Intersezione raggio / piano
• si sostituisce x,y,z dalla equazione parametrica del piano:
• se t<0 il raggio è nel semispazio che non contiene il poligono
• se il denominatore = 0 raggio e piano sono paralleli; per verificare se il raggio è nel semispazio che non contiene il poligono basta testare il segno del numeratore: se > 0 è esterno
Ax1 Ait By1 Bjt Cz1 Ckt D 0
Ax1 By1 Cz1 t(Ai Bj Ck) D 0
t Ax1 By1 Cz1 D
(Ai Bj Ck)
20
Casi negativi• raggio esterno al semispazio che contiene il
poligono: t<0
• raggio parallelo al piano del poligono: denominatore = 0 – nel semispazio esterno al poligono: numeratore
>0
interno interno
esternoesterno
raggio
21
Test di appartenenza del punto
• nei casi “positivi” si verifica se l’intersezione col piano cade nel poligono (triangolo)
• metodo diretto: se interno la somma degli angoli dal punto ai vertici è 360°
22
• Il metodo diretto è costoso, se il punto è su un bordo dà errore, non si può valutare se il poligono è orientato “back face” rispetto alla direzione del raggio (può interessare solo la prima intersezione con un poliedro)
23
Intersezione con OBB
• si considerano a turno coppie di piani paralleli determinando tnear e tfar
• si conserva nel confronto tnear maggiore e tfar minore
• se il massimo tnear è maggiore del minimo tfar non c’è intersezione
24
tnear
tnear tnear
tfartnear
tfar
tfar
tfar