Como posso encontrar a maior esfera que cabe dentro de um tronco?

Como você encontra a maior esfera que pode desenhar em perspectiva?

Visto de cima, seria o seguinte:

Adicionado: no frustum à direita, marquei quatro pontos sobre os quais acho que sabemos algo. Podemos projetar todos os oito cantos do frusum e os centros das extremidades próxima e longínqua. Portanto, sabemos os pontos 1, 3 e 4. Também sabemos que o ponto 2 é a mesma distância de 3 e 4 é de 3. Portanto, podemos calcular o ponto mais próximo da linha 1 ao 4 e ao ponto 2 para obter o Centro? Mas a matemática e o código reais me escapam.

Quero desenhar os modelos (que são aproximadamente esféricos e para os quais tenho uma esfera delimitadora de minibolas) o maior possível.

Atualização: tentei implementar a abordagem incircle-on-two -planes, conforme sugerido por bobobobo e 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;
}

Eu admito que estou voando; Estou tentando adaptar o código 2D , estendendo-o em 3 dimensões. Não calcula a esfera corretamente; o ponto central da esfera parece estar sempre na linha entre a câmera e a parte superior esquerda, e é muito grande (ou muito próximo). Existe algum erro óbvio no meu código? A abordagem, se corrigida, funciona?

Suponho que seu fustão é simétrico, pois seu desenho parece sugerir isso. Existem três restrições (duas se o seu frustum for 2D):

A. a esfera não pode ser maior que a distância entre os planos próximo e distante

Se Dé a distância mais próxima, a primeira restrição é simplesmente:

R ≤ D / 2

B. a esfera não pode crescer mais que os planos laterais

Agora, para a outra restrição, digamos que αseja o meio ângulo do frustum e La metade da largura do plano distante, conforme mostrado neste desenho:

A primeira fórmula é dada pela trigonometria no triângulo. O segundo vem da soma dos ângulos de um triângulo. O que nos dá a segunda restrição:

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

Se seu frustum for 3D, você terá uma terceira restrição com novos Le αvalores.

Resultado final

O Rvalor que você está procurando é o mindos três limites.

Como obter os parâmetros

Se você pode projetar o frustum na vista ou no espaço do mundo, pode calcular L, D e α da seguinte maneira, onde os Ppontos são do plano próximo e os Qpontos são do plano distante:

Setas significam vetores, "." é o produto escalar e || indica o comprimento de um vetor. Substitua Q2por Q3e P2com P3para obter L e α na dimensão vertical.

Em 2D: considere o tronco como um triângulo (2D)

Você então deseja encontrar o círculo do triângulo.

Como um problema 3D, você precisa encontrar a atmosfera de uma pirâmide quadrada.

Se eu tivesse a fórmula, imprimiria aqui, mas, infelizmente, não sei a fórmula.

A maior esfera possível deve tocar o plano longínquo (usando os termos para ver as frustrações aqui) bem no centro. Também tocaria nos planos superior / inferior ou esquerdo / direito, dependendo do ângulo de FoV menor. Devo dizer que não tenho uma prova matemática real para essas suposições, mas elas devem estar certas. Talvez alguém tenha uma idéia de como provar isso.

Uma esfera pode ser definida por seu ponto central e um raio. Cx e Cy são iguais ao centro do plano distante.

Cz e o raio podem ser obtidos resolvendo um sistema de equações com base nas premissas listadas acima.

T é um dos planos inferior / superior ou esquerdo / direito (veja acima) com t1, t2 e t3 como vetor normal normalizado e t4 como distância da origem. f é o centro do farplane.

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 é calculado inserindo cz neste: -fz + cz = r

Você pode obter todos os planos da Matriz de projeção que estiver usando. (Não é o ViewProjection neste caso)

depois você tem que mover a esfera para o espaço certo: C '= inverso (Exibir) * C

Estou tentando fazer algo semelhante e, no meu caso, a velocidade é mais crucial que a precisão, desde que a esfera não exista fora dos limites do frustum.

Se você calcular a menor distância entre os segmentos de linha (ou faces em 3d), a menor distância encontrada poderá ser usada como o diâmetro de um incircle / insphere que esteja totalmente dentro do frustum. A origem do incircle / insphere poderia simplesmente a média de todos os vértices (soma e divisão). Seria bastante rápido e também funcionaria para todos os tipos de poliedros convexos.

A única desvantagem é que o círculo ou esfera não será necessariamente o maior círculo ou insfera possível. Para um frustum com muito volume e uma borda muito curta, o círculo / esfera compartilharia muito menos espaço possível do frustum.

Outra ideia

Se você deseja a esfera de um frustum de vista 3D e tem a matriz de perspectiva usada para construir esse frustum, basta usar essa matriz na esfera de um cubo unitário, e essa deve ser uma esfera perfeita para o frustum. (O diâmetro da insfera de um cubo é o comprimento de uma das arestas do cubo, o centro é o meio do cubo, que é a média dos vértices do cubo)