Jak mogę znaleźć największą kulę, która mieści się w obszarze ściętym?

Jak znaleźć największą kulę, którą możesz narysować w perspektywie?

Patrząc z góry, wyglądałoby to tak:

Dodano: na frustum po prawej stronie zaznaczyłem cztery punkty, o których chyba coś wiemy. Możemy odsunąć wszystkie osiem rogów frusum i środki bliskich i dalekich krańców. Znamy więc punkty 1, 3 i 4. Wiemy również, że punkt 2 jest w tej samej odległości od 3, co 4 od 3. Tak więc możemy obliczyć najbliższy punkt na liniach od 1 do 4 do punktu 2, aby uzyskać Centrum? Ale faktyczna matematyka i kod mi ucieka.

Chcę narysować modele (które są w przybliżeniu sferyczne i dla których mam kulę ograniczającą miniballę) tak duże, jak to możliwe.

Aktualizacja: Próbowałem wdrożyć podejście z okrążeniem na dwóch płaszczyznach, jak zasugerowali bobobobo i Nathan Reed :

function getFrustumsInsphere(viewport,invMvpMatrix) {
    var midX = viewport[0]+viewport[2]/2,
        midY = viewport[1]+viewport[3]/2,
        centre = unproject(midX,midY,null,null,viewport,invMvpMatrix),
        incircle = function(a,b) {
            var c = ray_ray_closest_point_3(a,b);
            a = a[1]; // far clip plane
            b = b[1]; // far clip plane
            c = c[1]; // camera
            var A = vec3_length(vec3_sub(b,c)),
                B = vec3_length(vec3_sub(a,c)),
                C = vec3_length(vec3_sub(a,b)),
                P = 1/(A+B+C),
                x = ((A*a[0])+(B*a[1])+(C*a[2]))*P,
                y = ((A*b[0])+(B*b[1])+(C*b[2]))*P,
                z = ((A*c[0])+(B*c[1])+(C*c[2]))*P;
            c = [x,y,z]; // now the centre of the incircle
            c.push(vec3_length(vec3_sub(centre[1],c))); // add its radius
            return c;
        },
        left = unproject(viewport[0],midY,null,null,viewport,invMvpMatrix),
        right = unproject(viewport[2],midY,null,null,viewport,invMvpMatrix),
        horiz = incircle(left,right),
        top = unproject(midX,viewport[1],null,null,viewport,invMvpMatrix),
        bottom = unproject(midX,viewport[3],null,null,viewport,invMvpMatrix),
        vert = incircle(top,bottom);
    return horiz[3]<vert[3]? horiz: vert;
}

Przyznaję, że to uskrzydlam; Próbuję dostosować kod 2D , rozszerzając go na 3 wymiary. Nie oblicza poprawnie insphere; punkt środkowy kuli wydaje się zawsze znajdować się na linii między kamerą a lewym górnym rogu, a jej kula jest za duża (lub za blisko). Czy w moim kodzie są jakieś oczywiste błędy? Czy podejście, jeśli jest ustalone, działa?

Zakładam, że twoje ścięcie jest symetryczne, ponieważ twój rysunek wydaje się to sugerować. Istnieją trzy ograniczenia (dwa, jeśli twoje frustum jest 2D):

A. kula nie może być większa niż odległość między bliską i daleką płaszczyzną

Jeśli odległość Djest bliska, pierwszym ograniczeniem jest po prostu:

R ≤ D / 2

B. kula nie może rosnąć szerzej niż płaszczyzny boczne

Teraz, jeśli chodzi o inne ograniczenie, powiedzmy, że αjest to pół-kąt ścięcia i Ljest to połowa szerokości odległej płaszczyzny, jak pokazano na tym rysunku:

Pierwszy wzór podaje trygonometria w trójkącie. Drugi pochodzi z sumy kątów trójkąta. Co daje nam drugie ograniczenie:

R ≤ L tan((π - 2α) / 4)

Jeśli twoje frustum to 3D, będziesz mieć trzecie ograniczenie z nowymi Li αwartościami.

Ostateczny wynik

RWartość szukasz jest minz trzech granic.

Jak uzyskać parametry

Jeśli możesz odsunąć frustum w widoku lub przestrzeni świata, możesz obliczyć L, D i α w następujący sposób, w którym Ppunkty są z bliskiej płaszczyzny, a Qpunkty z dalekiej płaszczyzny:

Strzałki oznaczają wektory „.” jest iloczynem kropkowym, a || wskazuje długość wektora. Wymień Q2się Q3i P2ze P3uzyskać L i a w wymiarze pionowym.

W 2D: rozważ frustum jako trójkąt (2D)

Następnie chcesz znaleźć koło trójkąta.

Jako problem 3D musisz znaleźć inspirującą piramidę opartą na kwadracie.

Gdybym miał wzór, wydrukowałbym go tutaj, ale niestety nie znam wzoru.

Największa Możliwa Sfera powinna dotknąć dalekiej płaszczyzny (używając tutaj terminów odnoszących się do widoków) bezpośrednio na środku. Dotykałby także górnej / dolnej lub lewej / prawej płaszczyzny, w zależności od tego, który kąt FoV jest mniejszy. Muszę powiedzieć, że nie mam faktycznego matematycznego dowodu na te założenia, ale powinny mieć rację. Może ktoś ma pomysł, jak to udowodnić.

Sferę można zdefiniować na podstawie jej punktu środkowego i promienia. Cx i Cy są takie same jak środek dalekiej płaszczyzny.

Cz i promień można uzyskać przez rozwiązanie układu równań opartego na wyżej wymienionych założeniach.

T jest jedną z płaszczyzn dolnej / górnej lub lewej / prawej (patrz wyżej) z t1, t2 i t3 jako znormalizowanym wektorem normalnym, a t4 jako odległości od początku. f jest środkiem dalekiej płaszczyzny.

t1 * cx + t2 * cy + t3 * cz - t4 = r

-fz + cz = r

t1 * cx + t2 * cy + t3 * cz - t4 = -fz + cz

t1 * cx + t2 * cy + fz - t2 = + cz - t3 * cz

t1 * cx + t2 * cy - fz - t2 = cz * (1 - t3)

cz = (t1 * cx + t2 * cy - fz - t2) / (1 - t3)

r jest następnie obliczane przez wstawienie do tego cz: -fz + cz = r

Wszystkie płaszczyzny można uzyskać z używanej macierzy projekcji. (W tym przypadku nie ViewProjection)

następnie musisz przesunąć kulę w odpowiednie miejsce: C '= inverse (View) * C

Próbuję zrobić coś podobnego, aw moim przypadku prędkość jest ważniejsza niż dokładność, o ile kula nie istnieje poza granicami frustum.

Jeśli obliczysz najkrótszą odległość między odcinkami linii (lub ścianami w 3D), najkrótszą znalezioną odległość można wykorzystać jako średnicę koła / insphere, która leży całkowicie w obrębie ściętej ścianki. Początek incircle / insphere może po prostu uśrednić wszystkie wierzchołki (suma i podział). Byłoby to dość szybkie i działałoby również dla wszystkich rodzajów wypukłych wielościanów.

Jedyną wadą jest to, że okrąg lub kula niekoniecznie będzie największym możliwym okrążeniem lub insphere możliwym. Dla frustum z dużą objętością i jedną bardzo krótką krawędzią okrąg / kula dzieliłaby znacznie mniej miejsca na ścięcia niż to możliwe.

Inny pomysł

Jeśli chcesz uzyskać inspirujący widok 3D z frustum i masz macierz perspektywiczną użytą do skonstruowania tego fragmentu, możesz po prostu użyć tej matrycy na insphere kostki jednostkowej, co powinno być idealną insphere dla tego fragmentu. (Średnica insphere sześcianu to długość jednej z krawędzi sześcianu, środek to środek sześcianu, który jest średnią jego wierzchołków)