Cammina una linea tra due punti in uno spazio voxel 3D visitando tutte le celle

Question

Ho un problema di linea di vista che devo risolvere visitando tutte le celle possibili in uno spazio voxel 3D tra due punti (non allineati alla griglia) .

Ho considerato l'utilizzo di un algoritmo 3D Bresenham, ma salterà alcune celle.

Un'implementazione ingenua potrebbe essere quella di controllare i punti lungo la linea a una risoluzione superiore rispetto alla griglia voxel, ma speravo in una soluzione più intelligente.

Chiunque ha dei contatti?

Answer 1

fornito questo , o vedere: http://jsfiddle.net/wivlaro/mkaWf/6/

function visitAll(gx0, gy0, gz0, gx1, gy1, gz1, visitor) { 

    var gx0idx = Math.floor(gx0); 
    var gy0idx = Math.floor(gy0); 
    var gz0idx = Math.floor(gz0); 

    var gx1idx = Math.floor(gx1); 
    var gy1idx = Math.floor(gy1); 
    var gz1idx = Math.floor(gz1); 

    var sx = gx1idx > gx0idx ? 1 : gx1idx < gx0idx ? -1 : 0; 
    var sy = gy1idx > gy0idx ? 1 : gy1idx < gy0idx ? -1 : 0; 
    var sz = gz1idx > gz0idx ? 1 : gz1idx < gz0idx ? -1 : 0; 

    var gx = gx0idx; 
    var gy = gy0idx; 
    var gz = gz0idx; 

    //Planes for each axis that we will next cross 
    var gxp = gx0idx + (gx1idx > gx0idx ? 1 : 0); 
    var gyp = gy0idx + (gy1idx > gy0idx ? 1 : 0); 
    var gzp = gz0idx + (gz1idx > gz0idx ? 1 : 0); 

    //Only used for multiplying up the error margins 
    var vx = gx1 === gx0 ? 1 : gx1 - gx0; 
    var vy = gy1 === gy0 ? 1 : gy1 - gy0; 
    var vz = gz1 === gz0 ? 1 : gz1 - gz0; 

    //Error is normalized to vx * vy * vz so we only have to multiply up 
    var vxvy = vx * vy; 
    var vxvz = vx * vz; 
    var vyvz = vy * vz; 

    //Error from the next plane accumulators, scaled up by vx*vy*vz 
    // gx0 + vx * rx === gxp 
    // vx * rx === gxp - gx0 
    // rx === (gxp - gx0)/vx 
    var errx = (gxp - gx0) * vyvz; 
    var erry = (gyp - gy0) * vxvz; 
    var errz = (gzp - gz0) * vxvy; 

    var derrx = sx * vyvz; 
    var derry = sy * vxvz; 
    var derrz = sz * vxvy; 

    do { 
     visitor(gx, gy, gz); 

     if (gx === gx1idx && gy === gy1idx && gz === gz1idx) break; 

     //Which plane do we cross first? 
     var xr = Math.abs(errx); 
     var yr = Math.abs(erry); 
     var zr = Math.abs(errz); 

     if (sx !== 0 && (sy === 0 || xr < yr) && (sz === 0 || xr < zr)) { 
      gx += sx; 
      errx += derrx; 
     } 
     else if (sy !== 0 && (sz === 0 || yr < zr)) { 
      gy += sy; 
      erry += derry; 
     } 
     else if (sz !== 0) { 
      gz += sz; 
      errz += derrz; 
     } 

    } while (true); 
} 

Answer 2

Penso che 3d Bresenham sia la strada da percorrere, appena ottimizzato un po '. Come primo passo al problema, procedi come Bresenham, ma sii sospettoso quando stai per fare un passo, o hai appena fatto un passo, dato che questi sono i posti in cui la linea potrebbe passare attraverso altre celle.

Per semplicità, supponiamo che z è dominante, nel senso che z incrementi ogni passo. La domanda 3d Bresenham è: "quando incrementiamo/decrementiamo in x o ?" La risposta è quando l'errore accumulato in x raggiunge .5 o quando l'errore è y o entrambi.

Per il vostro caso, penso che è necessario disporre di una soglia secondaria che utilizza slopeY = deltaY/deltaZ per decidere se la linea è in procinto di attraversare in una cella vicina. Se stepZ è la modifica di z lungo la linea per ciascun pixel, un test come error > .5 - slopeY/stepZ dovrebbe indicare di ottenere celle su entrambi i lati della linea in . Un test simile ti dice se devi ottenere la cella in più in x. Se devi ottenere la cella in più in entrambe le xe y, allora devi ottenere la cella diagonale anche alla cella di Bresenham.

Se hai rilevato che si è aggiunto una cella y prima che l'incremento, non sarà aggiungere una cella dopo. Se non hai aggiunto una cella prima, dovrai farlo dopo, a meno che non ti sia capitato di passare attraverso un angolo della cella. Come gestisci ciò dipende dal tuo caso d'uso.

Questi sono i miei pensieri sul problema, non ho provato nulla, ma qualcosa del genere dovrebbe funzionare.

Answer 3

Per quanto mi ricordo l'algoritmo originale di Bresenham presuppone che il movimento lungo le diagonali sia consentito, nel tuo caso è logico impedirlo.

Ma l'idea principale è la stessa: per ogni voxel rispondi alla domanda "quali sono le prospettive?"

Ogni voxel ha 6 facce ciascuna che porta a un altro vicino. Basta controllare il centro di quale voxel è più vicino alla linea rispetto ad altri. Questo è il prossimo voxel.

Nota: questo presuppone che voxel ha la stessa dimensione lungo ogni asse, se questo non è il caso, è necessario calcolare la distanza modificato (ogni componente deve essere diviso per voxel lungo l'asse corrispondente)

Answer 4

Ecco un link pubblico a un recente porto di mia voxel ray da C++ in javascript:

https://github.com/jeremykentbgross/EmpathicCivGameEngine/blob/master/engine/public/scripts/Ray2D.js

Nota: la porta è attualmente in 2D su un quadtree (anziché 3D su un octtree), ma solo perché una dimensione è commentata per il mio motore javascript 2D. Funziona perfettamente con il mio motore 3D C++ (da dove l'ho effettuato il porting), quindi se rimuovi il commento dalle linee dell'asse Z funzionerà. Il file ha anche molti commenti in linea su come funziona la matematica.

È inoltre necessario fare riferimento a RayTracer2D.js (nella stessa directory) che utilizza il raggio per trovare tutti gli oggetti intersecati e i relativi punti di intersezione nell'ordine in cui vengono colpiti.

Per riferimento la struttura quad albero si sta tracciando attraverso è anche nella stessa cartella: QuadTree.js

Nota che si potrebbe anche traccia ray LOD inferiore è semplicemente limitando quanto in profondità si traversa in albero durante la traccia .

Spero che questo aiuti.