En los gráficos por computadora en 3D , los objetos sólidos generalmente se modelan mediante poliedros . Una cara de un poliedro es un polígono plano delimitado por segmentos de recta, llamados aristas . Las superficies curvas generalmente se aproximan mediante una malla poligonal . Los programas informáticos para dibujos lineales de objetos opacos deben poder decidir qué bordes o qué partes de los bordes están ocultos por un objeto mismo o por otros objetos, de modo que esos bordes puedan recortarse durante el renderizado . Este problema se conoce como eliminación de líneas ocultas .
La primera solución conocida al problema de las líneas ocultas fue ideada por LG Roberts [1] en 1963. Sin embargo, restringe severamente el modelo: requiere que todos los objetos sean convexos . Ruth A. Weiss de Bell Labs documentó su solución de 1964 a este problema en un artículo de 1965. [2] En 1966, Ivan E. Sutherland enumeró 10 problemas no resueltos en gráficos por computadora. [3] El problema número siete fue la "eliminación de líneas ocultas" . En términos de complejidad computacional , este problema fue resuelto por Frank Devai en 1986. [4]
Los modelos, por ejemplo en el diseño asistido por ordenador , pueden tener miles o millones de aristas. Por lo tanto, es crucial un enfoque de complejidad computacional que exprese los requisitos de recursos (como el tiempo y la memoria) en función del tamaño del problema. Los requisitos de tiempo son particularmente importantes en los sistemas interactivos.
Los tamaños del problema para la eliminación de líneas ocultas son el número total n de los bordes del modelo y el número total v de los segmentos visibles de los bordes. La visibilidad puede cambiar en los puntos de intersección de las imágenes de los bordes. Sea k el número total de puntos de intersección de las imágenes de los bordes. Tanto k = Θ( n 2 ) como v = Θ( n 2 ) en el peor de los casos, [4] pero normalmente v < k .
Los algoritmos de líneas ocultas publicados antes de 1984 [5] [6] [7] [8] dividen los bordes en segmentos de línea por los puntos de intersección de sus imágenes y luego prueban la visibilidad de cada segmento frente a cada cara del modelo. Suponiendo un modelo de una colección de poliedros con el límite de cada uno topológicamente equivalente a una esfera y con caras topológicamente equivalentes a discos, según la fórmula de Euler, hay Θ( n ) caras. Probar Θ( n 2 ) segmentos de línea contra Θ( n ) caras lleva Θ( n 3 ) tiempo en el peor de los casos. [4] El algoritmo de Appel [5] también es inestable, porque un error en la visibilidad se propagará a los puntos finales del segmento posterior. [9]
Ottmann y Widmayer [10] y Ottmann, Widmayer y Wood [11] propusieron algoritmos de línea oculta en tiempo O (( n + k ) log 2 n ). Luego Nurmi mejoró [12] el tiempo de ejecución a O (( n + k ) log n ). Estos algoritmos toman Θ( n 2 log 2 n ), respectivamente Θ( n 2 log n ) tiempo en el peor de los casos, pero si k es menor que cuadrático, pueden ser más rápidos en la práctica.
Cualquier algoritmo de líneas ocultas tiene que determinar la unión de Θ( n ) intervalos ocultos en n aristas en el peor de los casos. Como Ω( n log n ) es un límite inferior para determinar la unión de n intervalos, [13] parece que lo mejor que se puede esperar lograr es Θ( n 2 log n ) en el peor de los casos y, por lo tanto, el algoritmo de Nurmi es óptimo.
Sin embargo, el factor log n fue eliminado por Devai, [4] quien planteó el problema abierto de si existía el mismo límite superior óptimo O ( n 2 ) para la eliminación de la superficie oculta. Este problema fue resuelto por McKenna en 1987. [14]
Los algoritmos sensibles a intersecciones [10] [11] [12] se conocen principalmente en la literatura de geometría computacional. Los límites superiores cuadráticos también son apreciados por la literatura sobre gráficos por computadora: Ghali señala [15] que los algoritmos de Devai y McKenna "representan hitos en los algoritmos de visibilidad" , rompiendo una barrera teórica de O ( n 2 log n ) a O ( n 2 ) para procesar una escena de n aristas.
El otro problema abierto, planteado por Devai [4] , de si existe un algoritmo de línea oculta en tiempo O ( n log n + v ), donde v , como se señaló anteriormente, es el número de segmentos visibles, aún no está resuelto en el momento de escribir.
En 1988, Devai propuso [16] un algoritmo paralelo de tiempo O (log n ) que utiliza n 2 procesadores para el problema de líneas ocultas bajo el modelo de cálculo de máquina de acceso aleatorio paralelo (PRAM) de lectura concurrente y escritura exclusiva (CREW). Como el producto del número de procesador y el tiempo de ejecución es asintóticamente mayor que Θ ( n 2 ), la complejidad secuencial del problema, el algoritmo no es óptimo para el trabajo, pero demuestra que el problema de línea oculta está en la clase de complejidad. NC , es decir, se puede resolver en tiempo polilogarítmico utilizando un número polinómico de procesadores.
Se pueden utilizar algoritmos de superficie oculta para eliminar líneas ocultas, pero no al revés. Reif y Sen [17] propusieron un algoritmo de tiempo O (log 4 n ) para el problema de la superficie oculta, utilizando procesadores O (( n + v )/log n ) CREW PRAM para un modelo restringido de terrenos poliédricos, donde v es el tamaño de salida.
En 2011, Devai publicó [18] una superficie oculta en tiempo O (log n ) y un algoritmo de línea oculta en tiempo O (log n ) más simple. El algoritmo de superficie oculta, que utiliza n 2 /log n procesadores CREW PRAM, es óptimo para el trabajo.
El algoritmo de línea oculta utiliza n 2 procesadores PRAM exclusivos de lectura y escritura exclusiva (EREW). El modelo EREW es la variante de PRAM más cercana a las máquinas reales. El algoritmo de línea oculta funciona O ( n 2 log n ), que es el límite superior de los mejores algoritmos secuenciales utilizados en la práctica.
Cook, Dwork y Reischuk dieron un límite inferior Ω(log n ) para encontrar el máximo de n enteros que permiten infinitos procesadores de cualquier PRAM sin escrituras simultáneas. [19] Encontrar el máximo de n enteros es reducible en tiempo constante al problema de líneas ocultas utilizando n procesadores. Por lo tanto, el algoritmo de línea oculta es óptimo en el tiempo. [18]