Eliminación de líneas ocultas: Revelando lo invisible: secretos de la visión por computadora

Por Fouad Sabry

¿Qué es la eliminación de líneas ocultas?

Los objetos sólidos normalmente se modelan como poliedros en el campo de los gráficos tridimensionales por computadora. Dentro de un poliedro, una cara es un polígono plano rodeado por segmentos de línea recta a los que se hace referencia como aristas. Cuando se intenta imitar superficies curvas, normalmente se utiliza una malla poligonal. Es necesario que los programas de computadora que se utilizan para crear dibujos lineales de objetos opacos tengan la capacidad de determinar si los bordes o secciones de los bordes están ocultos por el objeto mismo o por otros objetos. Esto permite recortar los bordes durante el proceso de renderizado. La dificultad en cuestión se conoce como eliminación de líneas ocultas.

Cómo se beneficiará

(I) Información y validaciones sobre los siguientes temas:

Capítulo 1: Eliminación de líneas ocultas

Capítulo 2: Algoritmo de Painter

Capítulo 3: Geometría computacional

Capítulo 4: Ray casting

Capítulo 5: Determinación de la superficie oculta

Capítulo 6: Ubicación del punto

Capítulo 7: Árbol de expansión mínimo euclidiano

Capítulo 8: Problema de la galería de arte

Capítulo 9: Representación de alto rango dinámico

Capítulo 10: Esqueleto recto

(II) Respondiendo las principales preguntas del público sobre la eliminación de líneas ocultas .

(III) Ejemplos del mundo real sobre el uso de la eliminación de líneas ocultas en muchos campos.

Para quién es este libro

Profesionales, estudiantes de pregrado y posgrado, entusiastas, aficionados y aquellos que quieran ir más allá del conocimiento o la información básica para cualquier tipo de eliminación de líneas ocultas.

 

 

• Idioma: Español
• Editorial: Mil Millones De Conocimientos [Spanish]
• Fecha de lanzamiento: 5 may 2024

Vista previa del libro

Capítulo 1: Eliminación de líneas ocultas

En los gráficos por ordenador en 3D, los poliedros se utilizan normalmente para modelar cosas sólidas. Una cara de un poliedro es un polígono plano delimitado por aristas, que son segmentos de línea recta. Normalmente, se utiliza una malla poligonal para representar superficies curvas. Para recortar aristas durante el renderizado, los programas informáticos para dibujos lineales de objetos opacos deben ser capaces de determinar qué aristas o partes de aristas están oscurecidas por un elemento o por otros objetos. Este problema se conoce como eliminación de líneas ocultas.

Roberts desarrolló la primera solución conocida para el problema de la línea oculta. Ivan E. Sutherland destacó diez problemas no resueltos en los gráficos por computadora en 1966.

En el diseño asistido por ordenador, por ejemplo, los modelos pueden tener miles o millones de aristas. Por lo tanto, es esencial utilizar un método de complejidad computacional que exprese los requisitos de recursos (como el tiempo y la memoria) en función del tamaño de los problemas. Especialmente importantes son las limitaciones de tiempo para los sistemas interactivos.

Los tamaños problemáticos para la eliminación de líneas ocultas son el número n de aristas del modelo y el número v de los segmentos visibles de las aristas.

En los lugares de cruce de las imágenes de los bordes, la visibilidad puede cambiar.

Sea k el número total de sitios donde se cruzan las imágenes de las aristas.

Tanto k = Θ(n2) como v = Θ(n2) en el peor de los casos, pero típicamente v k.

Antes de 1984, los algoritmos de línea oculta publicados por Ottmann y Widmayer y Wood proponían algoritmos de línea oculta de tiempo O((n + k) log2 n).

A continuación, Nurmi mejoró el tiempo de ejecución a O((n + k) log n).

Estos algoritmos tardan Θ(n2 log2 n), respectivamente Θ(n2 log n) tiempo en el peor de los casos, si k es menor que cuadrático, sin embargo, pueden ser más rápidos en realidad.

Cualquier algoritmo de línea oculta 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, parece que lo mejor que se puede esperar lograr es Θ(n2 log n) en el peor de los casos, por lo que el algoritmo de Nurmi es el mejor.

Sin embargo, el factor log n fue eliminado por Devai, que los métodos de Devai y McKenna son hitos en los algoritmos de visibilidad, rompiendo una barrera teórica de O(n2 log n) a O(n2) para procesar una escena de n aristas.

La otra cuestión pendiente, presentada por Devai, de si existe un  algoritmo de línea oculta en el tiempo O(n log n + v), donde v, como ya se ha dicho, es el número de segmentos visibles, seguía sin respuesta en el momento de escribir este artículo.

En 1988 Devai propuso un algoritmo paralelo de tiempo O(log n) utilizando procesadores n2 para el problema de la línea oculta bajo la lectura concurrente, Modelo de computación usando máquina de acceso aleatorio paralelo (PRAM) de escritura exclusiva (CREW).

Como el producto del número de procesador y el tiempo de ejecución es asintóticamente mayor que Θ(n2), la complicación secuencial del problema, el algoritmo es ineficiente, sin embargo, demuestra que el problema de la línea oculta pertenece a la clase de dificultad NC, es decir, se puede resolver utilizando un número polinómico de procesadores en tiempo polilogarítmico.

Sin embargo, los algoritmos de superficie oculta se pueden usar para eliminar líneas ocultas, no al revés.

Reif y Sen propusieron un algoritmo de tiempo O(log⁴ 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 la cantidad de salida.

En 2011, Devai publicó un  algoritmo de superficie oculta de tiempo O(log n) y otro más fácil, también de tiempo O(log n).

El algoritmo de superficie oculta, que utiliza procesadores n2/log n CREW PRAM, es el mejor en términos de eficiencia.

El algoritmo de línea oculta utiliza procesadores PRAM de lectura exclusiva n2 y EREW (escritura exclusiva).

EREW es el tipo de PRAM más similar a las máquinas reales.

El algoritmo de línea oculta hace que O(n2 log n) funcione, ¿Cuál es el límite superior de los algoritmos secuenciales más efectivos en uso?.

Cook, Dwork y Reischuk dieron un límite inferior de Ω(log n) para encontrar el máximo de n enteros, lo que permite un número infinito de procesadores de cualquier PRAM sin escrituras simultáneas.

{Fin del capítulo 1}

Capítulo 2: Algoritmo de Painter

El algoritmo del pintor (también algoritmo de ordenación por profundidad y relleno de prioridad) es un algoritmo para la determinación de la superficie visible en gráficos por ordenador 3D que funciona sobre una base polígono por polígono en lugar de píxel por píxel, por fila o región por región utilizando técnicas adicionales de eliminación de superficies ocultas.

En 1972, mientras los tres trabajaban en CADCentre, Martin Newell, Richard Newell y Tom Sancha presentaron por primera vez el algoritmo del pintor como una solución básica al problema de la determinación de la superficie oculta.

El algoritmo de Painter funciona conceptualmente de la siguiente manera:

Ordena cada polígono según su profundidad

Coloque cada polígono desde el más distante hasta el más cercano.

Ordenar polígonos por profundidad

Para cada polígono p:

Para cada píxel que cubre p :

Pintar P.Color en el píxel

La complejidad temporal del algoritmo del pintor depende en gran medida del mecanismo de clasificación utilizado para organizar los polígonos. Asumiendo la técnica de clasificación más eficiente, la peor complejidad del enfoque del pintor es O(n log n + m*n), donde n es el número de