Intersezioni e distanze
Daniele Marini
1
Perchè
• Il calcolo delle intersezioni di rette con
oggetti e di distanze è assai frequente,
occorre trovare soluzioni efficienti
• Si usano equazioni parametriche per
rappresentare rette e volumi di
contenimento (BV) per accelerare il calcolo
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 sfera: x2+y2+z2-r2=0
• dato il punto p si valuta se appartiene alla superficie
trovando gli zeri dell’equazione
– esplicite: f(u,v)=(fx(u,v),fy(u,v),fz(u,v))
• es sfera: f(,)=((r sin cos), (r sin sin), (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)
rx  x 0  ti
• Le componenti sono:
ry  y 0  tj
rz  z 0  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 estremi
amin , 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 che
passa per p si ottiene proiettando q su r e
valutando la norma:
w  ((q  p).d)  d
(q  p)  w
q

(q-p)-w
q-p
w
d
p
r
9
Intersezione con una sfera
• Caso più semplice di BV è la sfera
• Raggio in forma parametrica (vettore):
x  x 1  (x 2  x 1 )t  x 1  it
y  y 1  (y 2  y 1 )t  y 1  jt
z  z1  (z2  z1 )t  z1  kt
t  0,1
• Sfera con centro in (l,m,n) e raggio r:

(x  l) 2  (y  m) 2  (z  n) 2  r 2
10
(x2,y2,z2)
t>1
(x1,y1,z1)
0<t<1
t<0
• Sostituendo nell’equazione della sfera x,y,z
(vediamo solo x):
(x  l) 2  x 2  l 2  2lx
(x1  it) 2  l 2  2lx1  2lit
i 2 t 2  2i(x1  l)t  (x12  l 2  2lx1)
11
• la forma quadratica generale è quindi:
at 2  bt  c  0
con :
a  i2  j 2  k 2
b  2i(x1  l)  2i(y1  m)  2i(z1  n)
c  l 2  m 2  n 2  x12  y12  z12  2(lx1  ny1  mz1 )  r 2

• 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
12
coseni direttori !
• si ricava anche la normale alla sfera nel punto di
intersezione (tangenza):
x1  l y1  m z1  n 
n  
,
,

 r
r
r 

13
• 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
14
Rejection test
15
Intersezione raggio triangolo
(poligono)
• 3 passi:
– determinare il piano su cui giace il triangolo
– determinare l’intersezione piano-raggio
– valutare se l’intersezione 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
16
Intersezione raggio triangolo
17
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: n  v  w  (v2w3  v3w2 )i  (v1w1  v1w3 )j (v1w2  v2w1)k
• dove i,j,k sono i versori, quindi A,B,C sono:
A  v 2 w 3  v 3 w 2 
B  v 3 w1  v1w 3 

C  v1w 2  v 2 w1 
• D si ottiene sostituendo un vertice del poligono
nell’equazione (un punto che giace nel piano)

18
Intersezione raggio / piano
• si sostituisce x,y,z dalla equazione parametrica del
piano:
Ax  Ait  By  Bjt  Cz  Ckt  D  0
1
1
1
Ax1  By1  Cz1  t(Ai  Bj  Ck)  D  0
Ax1  By1  Cz1  D
t 
(Ai  Bj  Ck)
• 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
19
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
raggio
esterno
esterno
interno
interno
20
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°
21
• 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)
22
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
23
tnear
tfar
tnear
tfar
tnear
tnear
tfar
tfar
24