Jak szybko znaleźć, czy punkt jest zasłonięty w złożonej scenie?

Question

Mam złożoną scenę 3D, w której muszę wyświetlać elementy HTML na podstawie współrzędnych 3D. (Po prostu umieszczam na wierzchu tag div i umieszczam go w CSS.) Muszę jednak częściowo go ukryć (np. Uczynić go przezroczystym), gdy współrzędne 3D są zasłonięte przez model (lub sformułowane w inny sposób, gdy nie jest widoczny w aparacie). Modele te mogą mieć setki tysięcy twarzy i potrzebuję sposobu, aby dowiedzieć się, czy jest zasłonięty, a który jest wystarczająco szybki, aby można go było uruchamiać wiele razy na sekundę.

Obecnie używam Three.js wbudowanej raytracerze, z następującego kodu:

// 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 

Jest to jednak bardzo powolny (liczba klatek spada z 50 fps do 8 kl./s) tych złożone modele. Szukałem lepszych sposobów, aby to zrobić, ale jak dotąd nie znalazłem w tym przypadku żadnej dobrej pracy.

Czy istnieją lepsze, bardziej skuteczne sposoby sprawdzenia, czy punkt jest widoczny lub zasłonięty przez modele w scenie?

Answer 1

Nie znam żadnej naprawdę szybkiej drogi, ale masz kilka opcji. Nie wiem wystarczająco dużo o pliku three.js, aby powiedzieć, jak to zrobić z tą biblioteką, ale ogólnie mówiąc o WebGL ...

Jeśli możesz używać WebGL 2.0, możesz użyć zapytań o okluzję. To sprowadza się do:

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); 
} 

Pamiętaj jednak, że wynik zapytania jest dostępny tylko kilka klatek później.

Jeśli WebGl 2.0 nie jest opcją, powinieneś prawdopodobnie narysować scenę do bufora ramki, w której załączasz własną teksturę, aby użyć jej zamiast zwykłego bufora z. Istnieje rozszerzenie, aby używać właściwych tekstur głębi (more details here), ale tam, gdzie nie jest to możliwe, zawsze można cofnąć się do rysowania sceny za pomocą modułu cieniującego, który wyświetla głębokość każdego piksela.

Następnie można użyć gl.ReadPixels() na fakturze głębi. Ponownie, pamiętaj o opóźnieniu transferu GPU-> CPU, które zawsze będzie znaczące.

Powiedziawszy to wszystko, w zależności od tego, jak wyglądają obiekty DOM, znacznie łatwiej i szybciej można przekształcić obiekty DOM w teksturę i narysować tę teksturę za pomocą kwadratu jako części sceny 3d.

Answer 2

Przyjmę, że treść pożądanych znaczników html jest danymi stron trzecich, takimi jak obraz lub element iframe, i nie można ich używać z webgl, więc musi to być znacznik html i nie może być sprite.

Istnieje książka kucharska do obliczeń na GPU. Powtórz każdą zmianę sceny. Niestety nie mogę tego zrobić dla Three.js (nie znam silnika).

Etap 1 Konstrukt widzialność obrazu z etykietkami

Tworzenie zbioru (a) wskaźnik bufora zawierającego wielkości Znaczniki, identyfikatory bramek (Int liczb od 0) i pozycji znacznika.

Tworzenie bufora renderowania i nowego programu WebGL, który będzie używany do renderowania do niego. Shadery tego programu będą renderować uproszczoną scenę, w tym "cienie tagów". Teraz uproszczony algorytm dla modułu cieniującego jest następujący: dla dowolnego obiektu renderuj biały kolor. Z wyjątkiem tagu, renderuj kolor na podstawie identyfikatora tagu.

Jeśli twój bieżący program ma mgły, przezroczyste obiekty, mapy wysokości lub pewną logikę proceduralną, może być również zawarty w modułach cieniowania (zależy, czy może on obejmować znacznik, czy nie).

Wynik może wyglądać tak (ale to nie jest ważne):

Jeśli kolor jest inna niż biały, istnieje znacznik. (Zakładając, że mam tylko 3 znaczniki, a następnie moje kolory # 000000, # 010000, # 020000, które wyglądają jak czarny, ale nie jest.)

Stage 2, Collect przejrzystości danych o znacznikach w obrazie

Potrzebujemy innego programu WebGL i renderbuffer. Wyrenderujemy punkty w buforze renderowania, każdy punkt ma jeden piksel i znajduje się obok siebie. Punkty reprezentują znaczniki. Będziemy więc potrzebować bufora tablicowego z pozycjami znaczników (i identyfikatorami znaczników, ale można to wydedukować w shaderze). Łączymy również tekstury z poprzedniego etapu.

Teraz kod wierzchołkowego modułu cieniującego wykona następujące czynności, w oparciu o atrybut identyfikatora znacznika, ustawi położenie punktu. Następnie oblicza przezroczystość z wyszukiwaniem tekstury, pseudokod:

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); 

Pozycja punktu i przezroczystość zostaną wprowadzone jako zmienne w stosunku do FS. FS będzie renderował niektóre kolory w oparciu o przezroczystość (na przykład biała dla pełnej widoczności, czarna dla niewidoczna i odcienie szarości dla częściowej widoczności).

Rezultatem tego etapu jest obraz, w którym każdy piksel przedstawia jeden znacznik, a kolor piksela oznacza przezroczystość znacznika. W zależności od tego, ile tagów posiadasz, niektóre piksele mogą nic nie oznaczać i mają wartość clearColor. Pozycja pikseli odpowiada identyfikatorowi tagu.

Stage 3, odczyt wartości z javascript

Aby odczytać dane z powrotem używać readPixels (lub może korzystać texImage2D?). Simple way to do it.

Następnie używa się forloop na podstawie identyfikatorów znaczników i zapisuje dane z tablicy maszynowej na przykład na komputerze stanu javascript. Teraz masz wartości przezroczystości w javascript i możesz zmieniać wartości CSS.

Pomysły

W etapie 1, zmniejszając rozmiar renderbuffer spowoduje znaczny wzrost wydajności (to obniża także tekstura wyszukiwań w etapie 2) z prawie zero kosztów.

Jeśli korzystasz z readPixels bezpośrednio po etapie 1 i próbujesz odczytać dane z ekranu za pomocą javascript, nawet jeśli używasz renderbuffer tylko o wielkości 320 * 200px, js musi wykonać tyle iteracji co rozdzielczość. Więc jeśli scena zmieni się co chwilę, to po prostu pusty forloop:

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 na moim komputerze. Ale na etapie 2 musisz wykonać tylko tyle powtórzeń, ile tagów w widocznym obszarze. (Dla 50 znaczników może to być 3000 * 60).

Największy problem, jaki widzę, to złożoność implementacji.

Węzłem tej techniki jest readpixel i wyszukiwanie tekstur. Możesz rozważyć nie wywołanie etapu 3 z prędkością FPS, ale zamiast tego z wolniejszą predefiniowaną prędkością.

Answer 3

Zakładając, że twoje położenie div jest zsynchronizowane z podstawową sceną 3D, powinieneś być w stanie zapytać o piksel just one za pomocą readPixels "pod" div.

Ponownie zakładając, że kontrolujesz geometrię, czy nie byłoby możliwym hackem dodanie koloru "poza kontekstem" (lub wartości alfa) do tekstury, w której element div pokryje i przetestuje?

W przypadku braku tekstury zmodyfikuj geometrię, aby "otoczyć" pojedynczy wierzchołek w granicach nadrzędnego elementu div i nadać mu równoważny kolor "poza kontekstem" lub wartość alfa, aby dostarczyć moduł cieniujący fragmentu.

Answer 4

Here in this answer znaleźć piękny przykład stosując THREE.Frustum aby wykryć, czy obiekty są widoczne:

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); 

nie wiem, czy to daje wydajność jesteś po mimo. Może możesz przetestować, aby zobaczyć, jak działa i zostawić komentarz ze swoimi ustaleniami dla innych, którzy tutaj kończą szukając podobnego rozwiązania.