Come trovare rapidamente se un punto è oscurato in una scena complessa?

Question

Ho una scena 3D complessa che ho bisogno di visualizzare gli elementi HTML in cima, in base a una coordinata 3D. (Sto semplicemente sovrapponendo un tag div in alto e posizionandolo con CSS.) Tuttavia, ho anche bisogno di nasconderlo parzialmente (ad esempio renderlo trasparente) quando la coordinata 3D è oscurata da un modello (o formulata in un altro modo, quando non è visibile nella fotocamera). Questi modelli possono avere centinaia di migliaia di facce e ho bisogno di un modo per scoprire se è oscurato e abbastanza veloce da essere eseguito molte volte al secondo.

Attualmente, sto usando di Three.js built-in raytracer, con il seguente codice:

// pos = vector with (normalized) x, y coordinates on canvas 
// dir = vector from camera to target point 

const raycaster = new THREE.Raycaster(); 
const d = dir.length(); // distance to point 
let intersects = false; 
raycaster.setFromCamera(pos, camera); 
const intersections = raycaster.intersectObject(modelObject, true); 
if (intersections.length > 0 && intersections[0].distance < d) 
    intersects = true; 

// if ray intersects at a point closer than d, then the target point is obscured 
// otherwise it is visible 

Tuttavia, questo è molto lento (frame rate scende da 50 fps a 8 fps) su queste modelli complessi. Ho cercato modi migliori per farlo, ma finora non ho trovato nessuno che funzioni bene in questo caso.

Esistono modi migliori e più efficaci per scoprire se un punto è visibile o oscurato dai modelli nella scena?

Answer 1

Non sono a conoscenza di un modo veramente rapido, ma avete alcune opzioni. Non so abbastanza su three.js per dirti come farlo con quella libreria, ma parlando di WebGL in generale ...

Se è possibile utilizzare WebGL 2.0, è possibile utilizzare le query di occlusione. Questo si riduce a

var query = gl.createQuery(); 
gl.beginQuery(gl.ANY_SAMPLES_PASSED, query); 
// ... draw a small quad at the specified 3d position ... 
gl.endQuery(gl.ANY_SAMPLES_PASSED); 
// some time later, typically a few frames later (after a fraction of a second) 
if (gl.getQueryParameter(query, gl.QUERY_RESULT_AVAILABLE)) 
{ 
    gl.getQueryParameter(query, gl.QUERY_RESULT); 
} 

Nota, tuttavia, che il risultato della query è disponibile solo per alcuni fotogrammi successivi.

Se WebGl 2.0 non è un'opzione, è probabile che si debba disegnare la scena su un framebuffer, in cui si allega la propria trama da utilizzare al posto del normale buffer z. C'è un'estensione per usare le trame di profondità appropriate (more details here), ma dove ciò non è possibile si potrebbe sempre tornare a disegnare la scena con uno shader di frammenti che emette la profondità di ciascun pixel.

È quindi possibile utilizzare gl.ReadPixels() sulla trama della profondità. Ancora una volta, essere consapevoli della latenza per il trasferimento della CPU -> CPU, sarà sempre significativo.

Detto questo, a seconda di come appaiono i tuoi oggetti DOM, potrebbe essere molto più facile e veloce rendere i tuoi oggetti DOM in una texture e disegnare quella texture usando un quad come parte della scena 3d.

Answer 2

Assumerò che il contenuto dei tag html desiderati sono dati di terze parti come immagine o iframe e non può essere utilizzato con Webgl, quindi deve essere tag html e non può essere sprite.

C'è un libro di cucina per il calcolo della GPU. Ripeti ogni volta che cambia la scena. Mi dispiace, non posso farlo per Three.js (non so il motore).

Fase 1, costruire un'immagine con tag visibilità

Create array (e index) tampone contenente dimensione dei tag html, ID di tag (int numeri da 0) e posizioni tag.

Creare il renderbuffer e il nuovo programma WebGL, che verrà utilizzato per il rendering in esso. Gli shader di questo programma renderanno la scena semplificata includendo le "ombre dei tag". Ora segue l'algoritmo semplificato per lo shader di frammenti: per ogni oggetto viene visualizzato il colore bianco. Tranne che per il tag, renderizza il colore in base all'ID del tag.

Se il tuo programma corrente ha nebbia, oggetti trasparenti, mappe di altezza o qualche logica procedurale, potrebbe essere contenuto anche negli shader (dipende se può coprire o meno tag).

Risultato potrebbe essere la seguente (ma non è importante):

Se il colore è diverso poi bianco, c'è tag. (Supponendo che ho solo 3 i tag, quindi i miei colori sono # 000000, # 010000, # 020000, che tutti guardano come il nero, ma non lo è.)

Piano 2, Raccogliere dati sulla trasparenza circa i tag di immagine

Abbiamo bisogno di un altro programma WebGL e renderbuffer. Renderizzeremo i punti in renderbuffer, ogni punto è grande un pixel ed è uno accanto all'altro. I punti rappresentano i tag. Quindi avremo bisogno di un buffer di array con posizioni di tag (e tag ID, ma questo può essere dedotto nello shader). Inoltre leghiamo la trama dalla fase precedente.

Ora il codice di vertex shader verrà seguito, in base all'attributo tag ID, imposterà la posizione del punto. Poi si calcola la trasparenza con la ricerca di texture, pseudocodice:

attribute vec3 tagPosition; 
attribute float tagId; 

float calculateTransparency(vec2 tagSize, vec2 tagPosition) { 
    float transparency = 0; 
    for(0-tagSize.x+tagPosition.x) { 
     for(0-tagSize.y+tagPosition.y) { 
      if(textureLookup == tagId) transparency++; // notice that texture lookup is used only for area where tag could be 
     } 
    } 
    return transparency/totalSize; 
} 

vec2 tagSize2d = calculateSize(tagPosition); 
float transparency = calculateTransparency(tagSize2d, tagPosition.xy); 

posizione del punto e la trasparenza entrerà come variabile a FS. FS renderà alcuni colori basati sulla trasparenza (ad esempio, il bianco per il pieno visibile, il nero per l'invisibile e le sfumature di grigio per il visibile parziale).

Il risultato di questa fase è l'immagine, in cui ogni pixel presenta un tag e il colore del pixel è la trasparenza del tag. A seconda del numero di tag che hai, alcuni pixel potrebbero non significare nulla e hanno il valore clearColor. La posizione dei pixel corrisponde al tag ID.

Piano 3, leggere i valori con javascript

Per leggere i dati indietro utilizzano readPixels (o potrebbero utilizzare texImage2D?). Simple way to do it.

Quindi si utilizza forloop basato su ID tag e si scrivono i dati dall'array tipizzato sulla macchina a stati javascript, ad esempio. Ora hai i valori di trasparenza in javascript e puoi modificare i valori CSS.

Idea

Nella fase 1, riducendo le dimensioni del renderbuffer causeranno sensibile incremento delle prestazioni (abbassa anche ricerche trama nello stadio 2) con costi quasi nulli.

Se si utilizza readPixels direttamente dopo la fase 1 e si tenta di leggere i dati dalla schermata con javascript, anche se si utilizza renderbuffer solo 320 * 200px di grandi dimensioni, js deve eseguire il numero di iterazioni della risoluzione. Quindi, nel caso in scena cambierà ogni momento, poi basta forloop vuoto:

var time = Date.now(); 
for(var i=0;i<320*200*60;i++) { // 64000*60 times per second 
} 
console.log(Date.now() - time); 

tooks ~ 4100ms sulla mia macchina. Ma con lo stage 2, devi fare solo tante iterazioni quante sono le tag nell'area visibile. (Per 50 tag potrebbe essere 3000 * 60).

Il problema più grande che vedo è la complessità dell'implementazione.

Il collo di bottiglia di questa tecnica è readpixel e ricerche di texture. Potresti considerare di non chiamare la fase 3 alla velocità FPS, ma invece di una velocità predefinita più lenta.

Answer 3

Supponendo che il posizionamento div sia sincronizzato con la scena 3D sottostante, si dovrebbe essere in grado di interrogare just one pixel con readPixels "sotto" il proprio div.

Sempre supponendo di avere il controllo della geometria, non sarebbe un trucco praticabile aggiungere semplicemente un colore "fuori contesto" (o valore alfa) nella trama in cui il div si coprirà e testerà contro di esso?

In caso di assenza di trame, modificare la geometria per "circondare" un singolo vertice entro i limiti del div sovrastante e dargli un equivalente colore o valore alfa "fuori contesto" per fornire allo shader del frammento.

Answer 4

Here in this answer si trova un bel esempio usando il THREE.Frustum per rilevare se gli oggetti sono visibili:

var frustum = new THREE.Frustum(); 
var cameraViewProjectionMatrix = new THREE.Matrix4(); 
camera.updateMatrixWorld(); 
camera.matrixWorldInverse.getInverse(camera.matrixWorld); 
cameraViewProjectionMatrix.multiplyMatrices(camera.projectionMatrix, camera.matrixWorldInverse); 
frustum.setFromMatrix(cameraViewProjectionMatrix); 

visible = frustum.intersectsObject(object); 

Non sono sicuro se questo vi darà le prestazioni siete dopo però. Forse puoi provare per vedere come funziona e lasciare un commento con le tue scoperte per gli altri che finiscono qui alla ricerca di una soluzione simile.