1

Intersezioni e distanze

Daniele Marini

2

Perchè

• Il calcolo delle intersezioni di rette con oggetti e di distanze è assai frequente, occorre trovare soluzioni efficienti

3

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 sincos), (r sinsin), (r cos))

4

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 ∈ −∞,+∞( )

5

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

6

• 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

7

Bounding sphere

• Si utilizza anche la sfera come volume di contenimento

• Lo studio delle intersezioni con i BV è essenziale per l’efficienza

8

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

9

• 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

r

q

pdq-p

w(q-p)-w

10

Intersezione con una sfera

• Caso più semplice di BV è la 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 sfera 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

• 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 = 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):

€

n =x1 − 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 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

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)

€

n = v×w = (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