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