Teoria dell'intersezione di Ray-box

Question

Desidero determinare il punto di intersezione tra un raggio e un riquadro. La casella è definita dalla sua coordinata min 3D e dalla sua coordinata 3D massima e il raggio è definito dalla sua origine e dalla direzione verso cui punta.

Attualmente, sto formando un piano per ogni faccia della scatola e sto incrociando il raggio con il piano. Se il raggio interseca il piano, allora controllo se il punto di intersezione si trova effettivamente sulla superficie della scatola. Se è così, controllo se è l'intersezione più vicina a questo raggio e restituisco l'intersezione più vicina.

Il modo posso controllare se il piano punto intersezione è sulla superficie scatola stessa è attraverso una funzione

bool PointOnBoxFace(R3Point point, R3Point corner1, R3Point corner2) 
{ 
    double min_x = min(corner1.X(), corner2.X()); 
    double max_x = max(corner1.X(), corner2.X()); 
    double min_y = min(corner1.Y(), corner2.Y()); 
    double max_y = max(corner1.Y(), corner2.Y()); 
    double min_z = min(corner1.Z(), corner2.Z()); 
    double max_z = max(corner1.Z(), corner2.Z()); 
    if(point.X() >= min_x && point.X() <= max_x && 
    point.Y() >= min_y && point.Y() <= max_y && 
    point.Z() >= min_z && point.Z() <= max_z) 
    return true; 

    return false; 
} 

dove corner1 è un angolo del rettangolo di quella scatola viso e corner2 è l'angolo opposto. La mia implementazione funziona la maggior parte del tempo ma a volte mi dà l'incrocio sbagliato. Si prega di vedere l'immagine:

L'immagine mostra raggi provenienti dall'occhio della fotocamera e che colpisce la superficie scatola. Gli altri raggi sono normali alla superficie della scatola. Si può vedere che l'un raggio in particolare (in realtà è il normale che si vede) esce dal "dietro" della scatola, mentre il normale dovrebbe venire dalla parte superiore della scatola. Questo sembra strano perché ci sono molti altri raggi che colpiscono correttamente la parte superiore della scatola.

Mi chiedevo se il modo in cui sto verificando se il punto di intersezione è sulla scatola è corretto o se dovrei usare qualche altro algoritmo.

Grazie.

Answer 1

Aumentare le cose con epsilon non è in realtà un ottimo modo per farlo, dato che ora hai un bordo di epsilon di dimensioni sul bordo della tua scatola attraverso il quale i raggi possono passare. Quindi ti libererai di questo strano insieme di errori (relativamente comuni) e finirai con un altro (più raro) insieme di strani errori.

Suppongo che tu stia già immaginando che il tuo raggio stia viaggiando ad una certa velocità lungo il suo vettore e trovi il tempo di intersezione con ciascun piano. Ad esempio, se si interseca l'aereo a x=x0 e il raggio sta andando in direzione (rx,ry,rz) da (0,0,0), il tempo di intersezione è t = x0/rx. Se t è negativo, ignoralo: stai andando dall'altra parte. Se lo t è zero, devi decidere come gestire quel caso speciale: se sei già su un aereo, lo rimbalzi o lo attraversi? Si potrebbe anche voler gestire rx==0 come un caso speciale (in modo da poter colpire il bordo della scatola).

In ogni caso, ora hai esattamente le coordinate in cui hai colpito quell'aereo: sono (t*rx , t*ry , t*rz). Ora puoi solo leggere se t*ry e t*rz si trovano all'interno del rettangolo in cui devono essere inseriti (ad esempio tra il minimo e il massimo per il cubo lungo quegli assi). Non testare la coordinata x perché sai già che lo hai colpito Anche in questo caso, devi decidere se/come gestire gli angoli colpire come caso speciale. Inoltre, ora puoi ordinare le tue collisioni con le varie superfici in base al tempo e scegliere il primo come punto di collisione.

Ciò consente di calcolare, senza ricorrere a fattori arbitrari epsilon, se e dove il raggio interseca il cubo, con la precisione possibile con l'aritmetica in virgola mobile.

quindi basta tre funzioni come quello che hai già: uno per testare se si colpisce entro yz supponendo che si colpisce x, e quelli corrispondenti per xz e xy assumendo che si colpisce y e z rispettivamente.

---

Edit: il codice inserito (verboso) mostrano come fare i test in modo diverso per ogni asse:

#define X_FACE 0 
#define Y_FACE 1 
#define Z_FACE 2 
#define MAX_FACE 4 

// true if we hit a box face, false otherwise 
bool hit_face(double uhit,double vhit, 
       double umin,double umax,double vmin,double vmax) 
{ 
    return (umin <= uhit && uhit <= umax && vmin <= vhit && vhit <= vmax); 
} 

// 0.0 if we missed, the time of impact otherwise 
double hit_box(double rx,double ry, double rz, 
       double min_x,double min_y,double min_z, 
       double max_x,double max_y,double max_z) 
{ 
    double times[6]; 
    bool hits[6]; 
    int faces[6]; 
    double t; 
    if (rx==0) { times[0] = times[1] = 0.0; } 
    else { 
    t = min_x/rx; 
    times[0] = t; faces[0] = X_FACE; 
    hits[0] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z); 
    t = max_x/rx; 
    times[1] = t; faces[1] = X_FACE + MAX_FACE; 
    hits[1] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z); 
    } 
    if (ry==0) { times[2] = times[3] = 0.0; } 
    else { 
    t = min_y/ry; 
    times[2] = t; faces[2] = Y_FACE; 
    hits[2] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z); 
    t = max_y/ry; 
    times[3] = t; faces[3] = Y_FACE + MAX_FACE; 
    hits[3] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z); 
    } 
    if (rz==0) { times[4] = times[5] = 0.0; } 
    else { 
    t = min_z/rz; 
    times[4] = t; faces[4] = Z_FACE; 
    hits[4] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y); 
    t = max_z/rz; 
    times[5] = t; faces[5] = Z_FACE + MAX_FACE; 
    hits[5] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y); 
    } 
    int first = 6; 
    t = 0.0; 
    for (int i=0 ; i<6 ; i++) { 
    if (times[i] > 0.0 && (times[i]<t || t==0.0)) { 
     first = i; 
     t = times[i]; 
    } 
    } 
    if (first>5) return 0.0; // Found nothing 
    else return times[first]; // Probably want hits[first] and faces[first] also.... 
} 

(ho scritto questo, non compilarlo, quindi attenzione di insetti.) (Edit: appena corretto un i ->first)

in ogni caso, il punto è che si trattano le tre direzioni separatamente e provare a vedere se l'impatto si è verificato all'interno della scatola destra (u, v). coordinate, dove (u, v) sono entrambi (x , y), (x, z) o (y, z) a seconda del piano che si preme.

Answer 2

Il codice sembra soddisfacente. Prova a trovare questo raggio particolare ed esegui il debugging.

Answer 3

MODIFICA: Ignora questa risposta (vedi i commenti sotto dove sono abbastanza convincentemente mostrato l'errore dei miei modi).

Si sta verificando se il punto si trova all'interno del volume, ma il punto si trova sulla periferia di quel volume, quindi è possibile che si trovi ad una distanza "infinitesimale" al di fuori del volume. Provare a crescere la casella da qualche piccolo Epsilon, ad esempio:

double epsilon = 1e-10; // Depends the scale of things in your code. 
double min_x = min(corner1.X(), corner2.X()) - epsilon; 
double max_x = max(corner1.X(), corner2.X()) + epsilon; 
double min_y = min(corner1.Y(), corner2.Y()) - epsilon; 
... 

Tecnicamente, il modo corretto per confrontare i numeri quasi-pari è quello di gettare le loro rappresentazioni bit per int e confrontare i numeri interi per qualche piccolo offset, ad esempio, in C :

#define EPSILON 10 /* some small int; tune to suit */ 
int almostequal(double a, double b) { 
    return llabs(*(long long*)&a - *(long long*)&b) < EPSILON; 
} 

Naturalmente, questo non è così facile in C#, ma forse la semantica non sicuri può ottenere lo stesso effetto. (Grazie a @Novox per i suoi commenti, che mi ha portato a un bel page spiegare questa tecnica in dettaglio.)

Answer 4

Potrebbe essere che che Ray finisce passando proprio attraverso il bordo della scatola? Errori di arrotondamento in virgola mobile potrebbero far sì che vengano persi sia dalla parte destra che da quella posteriore.

Answer 5

PointOnBoxFace deve essere un controllo bidimensionale anziché tridimensionale. Ad esempio, se stai provando contro il piano z = z_min, allora dovresti solo confrontare x e ai loro rispettivi confini. Hai già capito che la coordinata z è corretta. Probabilmente la precisione in virgola mobile ti fa inciampare mentre "ricontrolla" la terza coordinata.

Ad esempio, se z_min è 1.0, si prova prima contro quel piano. Si trova un punto di intersezione di (x, y, 0,999999999). Ora, anche se x e rientrano nei limiti, lo z non è del tutto corretto.