He aquí una posible solución que he elaborado para el caso de que utilicemos un Frustum en lugar de un cono, que además ilumina un poco el caso de uso de mi problema. No está probado, pero estoy bastante seguro de que va a funcionar.
Intersección del Frustum Elipsoide
El problema consiste en una forma de refinar el raytracing en la que renderizamos una gran lista de pinceles 3D convexos (y he decidido empezar con los elipsoides, ya que son muy útiles) en la pantalla o en un mapa de sombras, sin ninguna estructura de aceleración preconcebida . ¿Cómo funciona? Bueno, si tuviéramos una forma de averiguar para una porción del frustro si contiene un cepillo, podríamos
- Empezar con una resolución muy baja
- Recoger una lista de elipsoides contenidos en cada baldosa, sacrificando los que no están contenidos o están totalmente ocluidos
- A continuación, subdividir cada azulejo en azulejos más pequeños y repetir
- Hasta que lleguemos a la resolución por píxel, entonces habremos terminado.
Y esto nos lleva al problema: queremos resolver un azulejo en la pantalla
- Si un elipsoide parametrizado arbitrariamente en el espacio del mundo se superpone a esta baldosa
- Cuál es el rango de profundidad cercano y lejano de la parte superpuesta (importante para la selección)
- Si el elipsoide cubre el azulejo completamente (ocluye su fondo completamente, también importante para la selección)
- Cuál es el rango de profundidad cercano y lejano de la porción que cubre por completo el azulejo (para que también podamos seleccionar los elipsoides superpuestos)
Ya ves que el problema es análogo al raytracing, pero estamos haciendo frustum tracing: en lugar de un rayo, extruimos y expandimos un rectángulo que forma una pirámide de 4 caras abiertas en el espacio, o más sencillo aún, cuatro planos. Los valores de profundidad que nos interesan están representados por planos paralelos al plano de la pantalla. Estos planos se cruzan en cada esquina del rectángulo para formar líneas de borde. Así que los participantes en este problema son:
- Un elipsoide
- Cuatro planos de pared de nuestro frustro
- Cuatro líneas de borde de nuestro frustro
- Un plano de la pantalla - cuyas posiciones queremos encontrar (exterior cerca/lejos, interior cerca/lejos)
Ahora el plano de la pantalla y el plano de la pared y las líneas de borde no están necesariamente dispuestos de forma simétrica y ortogonal, sino que pueden estar sesgados debido a la posición de la baldosa de la pantalla que nos interesa. Al principio, esto parece una complicación añadida, pero será útil que no tengamos aquí una invariante que nos parezca que hay que proteger (y en cambio obtengamos otra de la que nos beneficiaremos)
Caso 2D
Pasemos del espacio 3D al espacio 2D e intentemos resolver el problema allí. Ahora nuestro elipsoide es sólo una elipse, y nuestro frustum es simplemente una cuña formada por dos líneas que se originan en un punto de ojo (análogo a nuestros cuatro planos o cuatro líneas de borde - aquí se contraen a la misma cosa) y una línea de pantalla (análoga a nuestro plano de pantalla) dispuesta semi-ortogonalmente al punto de ojo.
Lo primero que podemos hacer para simplificar considerablemente el problema es escalar y rotar de forma no uniforme nuestro espacio del problema para convertir el elipsoide en un círculo unitario (análogo a la solución de trazado de rayos 3D que hace lo mismo). Esto sesgará aún más nuestra cuña, pero como ya estaba sesgada para empezar, nada cambió realmente para nosotros. Esta era la invariante de la que hablaba antes. Ahora estamos resolviendo el problema para un círculo unitario, y nuestra cuña sigue siendo una cuña, pero en el espacio de la elipse. Tendremos que guardar nuestra matriz de inclinación para más tarde para que podamos transformar nuestras líneas de solución de nuevo al espacio del mundo.
Terminamos con cuatro posibles arreglos de círculo y cuña:
A. Un círculo que cruza las dos líneas limítrofes - contenido, ocluido.
B. Círculo que cruza sólo una línea límite: contenido, no ocluido.
C. Un círculo que no cruza ninguna línea límite y que está a la izquierda de una línea y a la derecha de la otra - contenido, no ocluido.
D. Un círculo que no cruza ninguna línea límite y que está a la izquierda o a la derecha de ambas líneas límite: no está contenido, no está ocluido.
Para resolver estos predicados necesitamos varias ecuaciones analíticas, que están fácilmente disponibles:
- Una prueba de intersección línea / círculo que nos da un punto de entrada y salida (normalmente parametrizado como centro y ancho) si hay una intersección, y para cualquier caso nos dice si el centro del círculo está a la izquierda o a la derecha de la línea.
- Una prueba de intersección línea / línea que nos da el punto de intersección. Dos líneas nunca serán paralelas en nuestro problema, por lo que este caso no tiene que ser probado.
- Dada una recta y una circunferencia, calcula dos rectas paralelas a la recta original que limitan la circunferencia y los puntos de contacto donde las rectas y la circunferencia se tocan.
Con estas dos ecuaciones podemos deducir nuestras líneas cercanas y lejanas (que son paralelas a la línea de la pantalla).
- Para el caso C, nuestra línea cercana y lejana son simplemente las que delimitan el círculo. Hecho.
- Para el caso B, la línea cercana o lejana sólo limita el círculo si el punto de contacto está dentro de la cuña. En caso contrario, se cruza con los puntos de intersección cercanos o lejanos del círculo y la línea de la pared.
- El caso A es análogo al caso B, salvo que ahora tenemos dos puntos de intersección a considerar por línea si el punto de contacto está fuera de la cuña. En este caso elegimos el punto de intersección más cercano o más lejano entre cada par.
- Para el caso A, también tenemos que calcular el rango totalmente cubierto, formado por dos líneas de pantalla que se solapan con los puntos de intersección interiores. Ambas intersecciones de cada línea de pantalla con las líneas de pared deben estar dentro del círculo, o no tendremos un rango totalmente cubierto.
Después de esto, transformamos las líneas de vuelta al espacio del mundo, y ese es el caso 2D tratado.
Caso 3D
Añadamos una dimensión más y observemos. De forma análoga al caso 2D, podemos girar y escalar el elipsoide hasta convertirlo en una esfera unitaria. Nuestros planos de las paredes, las líneas de los bordes y el plano de la pantalla se transformarán en el espacio del elipsoide, y más tarde simplemente transformaremos nuestra solución de nuevo.
Estos son nuestros posibles casos en el espacio 3:
A. Una esfera que cruza todos los bordes de la pared - contenida, ocluida.
B. Una esfera que interseca uno o más planos de pared y está dentro del frustum - contenida, no ocluida.
C. Una esfera que no cruza ningún plano de pared y que está dentro del frustum - contenida, no ocluida.
D. Una esfera que no cruza ningún plano de pared y que está fuera del frustum: no está contenida, no está ocluida.
Estas son las ecuaciones analíticas que necesitamos para resolver todos los predicados, y de nuevo, todo esto es algo estándar:
- Una prueba de intersección esfera/plano que nos da los parámetros del círculo resultante incrustado en el espacio 3, y para cualquier caso nos dice en qué semiespacio está el centro de la esfera.
- Una prueba de intersección rayo / esfera que nos da el punto de entrada y salida si hay una intersección.
- Una prueba de intersección rayo/plano que nos da el punto de intersección. Rayo y plano nunca serán paralelos, por lo que este caso no tiene que ser probado.
- Dados un plano y una esfera, calcula dos planos paralelos al plano original que limiten la esfera, y los dos puntos de contacto en los que los planos y la esfera se tocan.
- Dados un plano y una circunferencia, calcula dos planos paralelos al plano original que limitan la circunferencia y el punto de contacto donde plano y circunferencia se tocan. Los planos de nuestra pantalla nunca serán paralelos al plano del círculo, por lo que no es necesario probar este caso.
Con estas ecuaciones podemos deducir nuestros planos cercano y lejano (que son paralelos al plano de la pantalla).
- Para el caso C, nuestros planos cercanos y lejanos son simplemente los que limitan la esfera. Hecho.
- Para los casos A y B, el plano cercano o lejano sólo limita la esfera si el punto de contacto está dentro del frustro. En caso contrario, limita el círculo si el punto de contacto está dentro de la cuña. En caso contrario, el plano se cruza con los puntos de intersección cercanos o lejanos de la esfera y el rayo de borde. Tenemos que recoger todas las intersecciones válidas dentro del frustum y elegir la más cercana/lejana para obtener nuestro rango final.
- Para el caso A, también tenemos que calcular el rango totalmente cubierto, formado por dos planos de la pantalla que se solapan con los puntos de intersección del borde interior. Las cuatro intersecciones de cada plano de la pantalla con los rayos de los bordes deben estar dentro de la esfera, o no tendremos un rango totalmente cubierto.
Después de esto, transformamos los planos de vuelta al espacio del mundo, y ya está todo hecho.
Limitaciones y advertencias
La solución no funcionará para elipsoides con una componente nula (disco) o infinita (cilindro de longitud infinita) porque no podemos transformarlos de nuevo en esferas unitarias (los discos harán que las paredes del frustro se vuelvan paralelas, los cilindros harán que se colapsen en un solo plano). Supongo que se podrían diseñar pruebas más robustas para esos casos, o intentar una solución para las cuádricas en general.
Tampoco cubrí ninguna prueba para elipsoides detrás del plano de la pantalla en la coordenada del ojo o para el caso cuando la coordenada del ojo está dentro del elipsoide. Estos casos también deben ser tratados.
Optimización
Una vez que el algoritmo está escrito, hay un montón de oportunidades para poner a cero o doblar los cálculos de los elementos duplicados/no utilizados, así que estoy bastante seguro de que se puede reducir a una pequeña solución que es completamente incomprensible sin este documento. Lo que me gusta de esta solución es que obtenemos un resultado analítico perfecto sin ninguna iteración, y eso debería traducirse en cientos de miles, si no millones, de pinceles de elipsoides por fotograma.
Generalización
Esta técnica también es válida para la proyección ortogonal sin ningún cambio.
No hay nada que desaconseje seguir este enfoque con primitivas convexas de escala no uniforme que no sean elipsoides, siempre que se disponga de pruebas de intersección/acotamiento de rayos y planos para la primitiva o una porción de ella. Las esferas son particularmente convenientes porque son invariantes a la rotación y sus cortes son siempre círculos. Los cubos producen rebanadas triangulares, cuadrilaterales y hexagonales. Los tetraedros producen cortes triangulares y cuadrilaterales. Los cilindros y los conos producen círculos y rebanadas hiperbólicas cubiertas.
No obstante, es útil saber que los cortes de una primitiva convexa también son siempre convexos.
¿Podría hacerse esto con estimadores de distancia con signo? Dado que nuestra primitiva es convexa, podemos utilizar newton-raphson más rápido para hacer converger un rayo a la superficie, en mi experiencia eso es menos de 7 iteraciones en promedio. Pero hay que idear nuevos estimadores de delimitación de planos que también funcionen con cortes 2D de un campo 3D, lo que para mí es un gran interrogante. Por otro lado, esta técnica también funcionaría con campos de distancia de escala no uniforme.
