Encontrar una esfera delimitadora mínima para un tronco

Tengo un triturado (pirámide truncada) y necesito calcular una esfera delimitadora para este tronco tan pequeño como sea posible. Puedo elegir que el centro esté justo en el centro del tronco y el radio sea la distancia a una de las esquinas "lejanas", pero eso generalmente deja bastante holgura alrededor del extremo estrecho del troncoEncontrar una esfera delimitadora mínima para un tronco

Esto parece una geometría simple, pero parece que no puedo resolverlo. ¿Algunas ideas?

Fuente

2010-02-03 Bob

Tal vez esto es una pregunta más adecuada para http://mathoverflow.net/ – synepis

Lo que se presente con respecto? OpenGL? –

No tiene nada que ver con OpenGL ni nada específico como eso. Solo necesito una esfera que encierra un tronco. – Bob

Probablemente esta no sea la respuesta que está buscando, pero podría calcular todos los verts del tronco y conectarlos a un algoritmo general de esfera mínima, como the miniball implementation.

Fuente

2010-02-03 19:43:26 tfinniga

La forma de hacerlo es encontrar una esfera que se ajuste a 4 puntos en su tronco. Si se trata de un tronco truncado (una pirámide truncada - mi mal estaba asumiendo un fristum cilíndrico), entonces obtienes dos puntos de las esquinas opuestas del cuadrante superior, y los otros dos del cuadrante inferior, desfasados con los dos primeros . Luego usa this para obtener tu esfera.

Fuente

2010-02-03 19:45:08 plinth

En realidad, la selección de puntos depende de la altura del tronco. Si es muy corto, todos los puntos pueden ser del mismo cuadrante (y en realidad solo necesita 3 puntos) – shoosh

¿Funciona esto para bases no cuadradas? –

El enlace está muerto (es una buena práctica copiar las partes importantes de una respuesta vinculada, supongo por este motivo :) – BjornW

Cualquier conjunto de cuatro puntos no coplanarios define una esfera. Suponiendo que está utilizando una pirámide de cuatro lados para su tronco, hay 70 conjuntos posibles de cuatro puntos. Pruebe las 70 esferas y vea cuál es la más pequeña.

Dado que su tronco probablemente tenga algunas simetrías, probablemente pueda elegir los cuatro puntos en las esquinas opuestas y usar la solución del zócalo.

Fuente

2010-02-03 19:46:24

La mayoría de los conjuntos de cuatro puntos no serán no coplanarios, y los que no lo serán necesariamente contiene todos los puntos. –

Necesita encontrar un punto en una línea "vertical" en el centro del tronco donde la distancia a un borde en la parte inferior y superior del tronco (suponiendo que sea simétrica) sea la misma.

resolver de tal manera que un punto en la parte inferior es Xb, Yb, Zb, un punto en la parte superior es Xt, Yt, Zt y la línea es un punto Xp, Yp, Zp más un vector Ax, By, Cz.

así resolver la ecuación

sqrt((Xb - (Xp + VAx))^2 + (Yb - (Yp + VBy))^2 + (Zb - (Zp + VCy))^2) = 
sqrt((Xt - (Xp + VAx))^2 + (Yt - (Yp + VBy))^2 + (Zt - (Zp + VCy))^2).

La única variable en la que hay V. escalar

Fuente

2010-02-03 19:56:26 patros

Sí, esto es lo que terminé haciendo. Resuelto justo después de preguntar, como de costumbre (debe apaciguar a los dioses del foro). Lo proyectó en 2D a lo largo del eje más corto, y luego simplemente estipuló que el radio de la esfera es la distancia a ambos vértices "lejano" y "cercano". El tipo de matemática se cayó de eso. – Bob

Si entiendo correctamente, esto es correcto, pero también existe la segunda posibilidad de que Anthony sugiera: es posible que puedas usar una esfera más pequeña moviendo el centro hacia el centro de la base, si el fusteño no es demasiado alto. – redtuna

Sí, si el punto está fuera del tronco, necesita la intersección de la línea y la parte inferior del trono. Olvidé mencionar eso. – patros

Bueno, hay http://www.cgafaq.info/wiki/Minimal_enclosing_sphere por supuesto (a través de Google).

Creo que hay dos posibilidades. Uno (si el tronco es muy plano) sería que los puntos opuestos de la base se vuelven puntos opuestos en la esfera. El otro (si el tronco es muy alto) sería que los puntos opuestos del tronco estarían en la esfera y descubrirías la esfera desde esos cuatro puntos (un punto en la base, uno opuesto al primero en la base, uno opuesto al primero en el cuadrado superior, uno adyacente al primero en el cuadrado superior).

Calcule la primera esfera. Si el frustum encaja en él, esa es tu respuesta. De lo contrario, la segunda esfera sería tu respuesta.

Fuente

2010-02-03 20:02:28

Buena observación de que hay 2 soluciones distintas a considerar. El centro de la esfera está en el centro de la base, a menos que un vértice superior del tronco esté más lejos que un vértice base desde ese punto. – phkahler

Estrictamente hablando (según this) la base del tronco puede ser cualquier polígono y, estrictamente hablando, ese polígono ni siquiera tiene que ser convexo. Dicho esto, para obtener una solución general al problema, creo que es posible que necesite usar (casi) todos los vértices como se sugirió anteriormente. Sin embargo, podría haber casos especiales cuya solución (tal como se sugirió anteriormente) solo requiera la comparación de un par de esferas. Me gusta el enlace de Anthony anterior: Megiddo proporciona una transformación que, según él, produce una solución en O (n) (!) Tiempo. No está mal !

Fuente

2010-02-03 22:50:47 Grembo

Existen varios algoritmos e implementaciones para este problema (ver también this post).

Para 2D y 3D, Gärtner's implementation es probablemente la más rápida.
Para dimensiones más altas (hasta 10.000, por ejemplo), consulte https://github.com/hbf/miniball, que es la implementación de un algoritmo por Gärtner, Kutz y Fischer (nota: soy uno de los coautores).
Para dimensiones muy, muy altas, core-set (aproximación) los algoritmos serán más rápidos.

En su aplicación particular, es posible que desee probar cualquiera de los dos primeros algoritmos. Ambos funcionan en O(n) con una constante muy pequeña y son numéricamente estables.

Fuente

2013-02-20 12:04:07 Hbf

Bueno, vamos a resolver con matemáticas.

Uso de la mano derecha Sistema de coordenadas Y (adelante es -Z eje), para tronco con ancho de vista w, altura h, cerca del plano n, plano lejano f, ángulo de visión del campo de visión X, entonces la esfera límite mínima es

k = sqrt(1+(h/w)^2) * tan⁡(fov/2) 

if(k^2 >= (f-n)/(f+n)) 
{ 
    C = (0, 0, -f) 
    R = f*k 
} 
else 
{ 
    C = (0, 0, -0.5 * (f+n) * (1+k^2)) 
    R = 0.5 * sqrt((f-n)^2 + 2*(f^2+n^2)*k^2 + (f+n)^2*k^4) 
}

C es el centro de la esfera, en el espacio de visión, y R es el radio.

puse detalles en mi blog si usted está interesado: https://lxjk.github.io/2017/04/15/Calculate-Minimal-Bounding-Sphere-of-Frustum.html

Fuente

2017-04-16 01:48:05 eric

Encontrar una esfera delimitadora mínima para un tronco

Respuesta

Cuestiones relacionadas