Los objetos sólidos generalmente se modelan mediante poliedros en una representación por computadora. Una cara de un poliedro es un polígono plano delimitado por segmentos de línea recta, llamados bordes. Las superficies curvas generalmente se aproximan mediante una malla poligonal. Los programas de computadora para dibujos lineales de objetos opacos deben poder decidir qué bordes o qué partes de los bordes están ocultos por un objeto en sí mismo o por otros objetos. 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 "eliminación de líneas ocultas" . En términos de complejidad computacional, este problema fue resuelto por Devai en 1986. [4]
Los modelos, por ejemplo, en diseño asistido por computadora, pueden tener miles o millones de bordes. Por lo tanto, un enfoque de complejidad computacional, que exprese los requisitos de recursos, como el tiempo y la memoria, como función del tamaño de los problemas, es crucial. Los requisitos de tiempo son particularmente importantes en los sistemas interactivos.
Los tamaños de los problemas 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 .
Algoritmos
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 there ( n ) caras. Probar Θ ( n 2 ) segmentos de línea contra Θ ( n ) caras toma Θ ( 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 de los segmentos posteriores. [9]
Ottmann y Widmayer [10] y Ottmann, Widmayer y Wood [11] propusieron algoritmos de línea oculta de 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, puede ser más rápido en la práctica.
Cualquier algoritmo de línea oculta tiene que determinar la unión de Θ ( n ) intervalos ocultos en n bordes 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 ) tiempo 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 de O ( n 2 ) para la eliminación de superficies ocultas. Este problema fue resuelto por McKenna en 1987. [14]
Los algoritmos sensibles a la intersección [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 bordes.
El otro problema abierto, planteado por Devai, [4] de si existe un algoritmo de línea oculta de tiempo O ( n log n + v ), donde v , como se señaló anteriormente, es el número de segmentos visibles, aún está sin resolver en el momento de la escritura.
Algoritmos paralelos
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 computación de máquina de acceso aleatorio paralelo (PRAM) de lectura simultánea 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 la 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.
Los algoritmos de superficie oculta se pueden utilizar para la eliminación de 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 CREW PRAM O (( n + v ) / log n ) para un modelo restringido de terrenos poliédricos, donde v es el tamaño de salida.
En 2011, Devai publicó [18] una superficie oculta de tiempo O (log n ) y un algoritmo de línea oculta más simple, también de tiempo O (log n ). El algoritmo de superficie oculta, que utiliza procesadores n 2 / log n CREW PRAM, es óptimo para el trabajo.
El algoritmo de línea oculta utiliza n 2 procesadores PRAM de lectura exclusiva y escritura exclusiva (EREW). El modelo EREW es la variante 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 se puede reducir en tiempo constante al problema de la línea oculta mediante el uso de n procesadores. Por lo tanto, el algoritmo de línea oculta es óptimo en el tiempo. [18]
Referencias
- ^ LG Roberts. Percepción mecánica de sólidos tridimensionales . Tesis de doctorado, Instituto de Tecnología de Massachusetts, 1963.
- ^ Ruth A. Weiss [ https://ohiostate.pressbooks.pub/app/uploads/sites/45/2017/09/bevision-weiss.pdf BE VISION, un paquete de programas IBM 7090 FORTRAN para dibujar vistas ortográficas de combinaciones de Superficies planas y cuadráticas]
- ^ IE Sutherland. Diez problemas sin resolver en infografía. Datamation , 12 (5): 22-27, 1966.
- ^ a b c d e F. Devai. Límites cuadráticos para eliminación de líneas ocultas. En Proc. 2nd Annual Symp. on Computational Geometry , SCG '86, págs. 269-275, Nueva York, NY, EE. UU., 1986.
- ^ a b A. Appel. La noción de invisibilidad cuantitativa y la representación mecánica de sólidos . En Proc. 22ª Conferencia Nacional , ACM '67, págs. 387–393, Nueva York, NY, EE. UU., 1967.
- ^ R. Galimberti y U. Montanari. Un algoritmo para la eliminación de líneas ocultas . Comun. ACM , 12 (4): 206–211, abril de 1969.
- ^ Cap. Hornung. Una aproximación a un algoritmo de línea oculta con cálculo mínimo . Computadoras y gráficos , 6 (3): 121-126, 1982.
- ^ PP Loutrel. Una solución al problema de las líneas ocultas de los poliedros dibujados por computadora . IEEE Trans. Comput ., 19 (3): 205–213, marzo de 1970.
- ^ JF Blinn. Invisibilidad fraccional. Computación IEEE. Grafico. Appl ., 8 (6): 77–84, noviembre de 1988.
- ^ a b Th. Ottmann y P. Widmayer. Resolver problemas de visibilidad mediante el uso de estructuras esqueléticas . En Proc. Fundamentos matemáticos de la informática , 1984 , págs. 459–470, Londres, Reino Unido, 1984. Springer-Verlag.
- ^ a b Th. Ottmann, P. Widmayer y D. Wood . Un algoritmo eficiente en el peor de los casos para la eliminación de líneas ocultas . Internat. J. Computer Mathematics , 18 (2): 93-119, 1985.
- ^ a b O. Nurmi. Un algoritmo de barrido de línea rápido para la eliminación de líneas ocultas . BIT , 25: 466–472, septiembre de 1985.
- ^ ML Fredman y B. Weide. Sobre la complejidad de calcular la medida de U [a i , b i ]. Comun. ACM , 21: 540–544, julio de 1978.
- ^ M. McKenna. Eliminación óptima de superficies ocultas en el peor de los casos. ACM Trans. Grafico. , 6: 19-28, enero de 1987.
- ^ Sh. Ghali. Un estudio de algoritmos prácticos de visibilidad del espacio de objetos . Notas del tutorial de SIGGRAPH, 1 (2), 2001.
- ^ F. Devai. Unalgoritmo de línea oculta exacta en tiempo paralelo O (log N ). Advances in Computer Graphics Hardware II , págs. 65–73, 1988.
- ^ JH Reif y S. Sen. Un eficiente algoritmo de eliminación de superficies ocultas sensibles a la salida y su paralelización . En Proc. 4th Annual Symp. on Computational Geometry , SCG '88, págs. 193–200, Nueva York, NY, EE. UU., 1988.
- ^ a b F. Devai. Un algoritmo de superficie oculta óptimo y su paralelización . En Computational Science and Its Applications , ICCSA 2011, volumen 6784 de Lecture Notes in Computer Science , págs. 17–29. Springer Berlín / Heidelberg, 2011.
- ^ S. Cook, C. Dwork y R. Reischuk. Límites de tiempo superior e inferior para máquinas de acceso aleatorio en paralelo sin escrituras simultáneas . SIAM J. Comput ., 15: 87–97, febrero de 1986.
enlaces externos
- La tesis de Patrick-Gilles Maillot , una extensión del algoritmo de dibujo de líneas de Bresenham para realizar la eliminación de líneas ocultas en 3D; también publicado en las actas del MICAD '87 sobre CAD / CAM y gráficos por computadora, página 591, ISBN 2-86601-084-1 .
- Vector Hidden Line Removal , un artículo de Walter Heger con una descripción más detallada (de los casos patológicos) y más citas.