Loading

Alison's New App is now available on iOS and Android! Download Now

Study Reminders
Support
Text Version

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Hola y bienvenidos a la conferencia número 26 en el curso de Computer Graphics, continuaremos nuestra discusión en el conducto de gráficos. Para una rápida recapitulación, vamos a pasar por las etapas.
Por lo tanto, ya hemos discutido la primera etapa que es la representación de objetos, la transformación de modelado de segunda etapa, la iluminación de tercera etapa, la cuarta etapa de visualización de la tubería, y la única etapa que queda es la conversión de la quinta etapa de exploración. Actualmente estamos debatiendo la quinta etapa.
En la última conferencia, hablamos de renderización de líneas, que es parte de la quinta etapa. Y ahí hablamos de un enfoque muy intuitivo, así como de un enfoque ligeramente mejorado que son los métodos DDA. Hoy continuaremos nuestra discusión sobre la representación de líneas, en la que hablaremos de un enfoque aún mejor. Y también vamos a discutir la representación de círculos.
Ahora, antes de entrar en la discusión sobre un mejor enfoque de representación de líneas, vamos a recapitular rápidamente lo que hemos visto en la conferencia anterior sobre la representación de líneas.
Así que la idea era mapear una descripción de viewport a una cuadrícula de píxeles. Eso es, por supuesto, el objetivo de la quinta etapa.
Para hacer eso, el enfoque más simple es simplemente redondear las coordenadas reales a los números enteros más cercanos, que son píxeles, por ejemplo, de (2.3, 2.6) a (2, 3). Ahora, esto es bueno para los puntos, pero para trazar líneas o círculos u otras formas primitivas, esto puede no ser bueno.
¿Y para la línea de lo que hicimos? Por lo tanto, primero asumimos que un segmento de línea se define por los puntos finales. Y nuestro objetivo es mapear todos los puntos que están en la línea a los píxeles adecuados.
El enfoque sencillo que hemos discutido es que primero correlacionamos los puntos finales con los píxeles, entonces empezamos con un punto final que está teniendo los valores de coordenadas x e y y, a continuación, trabajamos los valores de coordenada y para las coordenadas x sucesivas, donde las coordenadas x difieren en 1 porque estamos hablando de cuadrículas de píxeles. Y entonces, este y los valores que calculamos se correlacionan con el entero más cercano obteniendo así los píxeles.
Ahora, este enfoque tiene dos problemas. Primero, requerimos la multiplicación que es una operación de coma flotante. Y en segundo lugar, requerimos de redondeo que también es una operación de coma flotante. Ahora, estas operaciones de coma flotante son computacionalmente caras y pueden dar como resultado una renderización más lenta de las líneas.
Para mejorar, hemos debatido un enfoque incremental. Allí no fuimos para la multiplicación, en cambio usamos la adición. Así que para calcular y, simplemente añadimos este valor m al valor actual, o para calcular x, nueva x, simplemente añadimos este valor de 1 por m al valor x actual. Ahora cuándo elegir si computar x o y, eso depende de la pendiente. Así que si el valor m está dentro de este rango, entonces computamos y dado x, de lo contrario, calculamos x dado y usando la ecuación de línea.
Ahora, la DDA puede reducir algunas operaciones de coma flotante como hemos comentado, particularmente las multiplicaciones. Sin embargo, todavía requiere otras operaciones de coma flotante, es decir, adiciones y redondeo. Por lo tanto, todavía no es completamente eficiente por decirlo así, y requerimos un mejor enfoque. Uno de ellos es el algoritmo de Bresenham.
Ahora, esta es una forma eficiente de escanear segmentos de línea de conversión y vamos a discutir el algoritmo suponiendo que m para estar dentro de estos rangos. Eso significa que nos concentraremos en la computación y el valor dado el valor x.
Ahora, intentemos entender la situación. Supongamos, este es el punto real en la línea y nos estamos moviendo a lo largo de la dirección x, la posición actual es dada por este punto (xk, yk). Ahora, el punto real de la línea es un número real de número de coma flotante, por lo que tenemos que correlacionarlo con el punto de cuadrícula de píxeles más cercano.
Ahora, hay dos candidatos potenciales para eso, uno es este píxel o el pixel candidato superior que es (xk + 1, yk + 1), y el otro es el píxel candidato más bajo que es (xk + 1, yk), y tenemos que elegir 1 de esos. ¿Cómo elegir eso?
Nuestro objetivo es elegir un píxel que esté más cerca con respecto al otro píxel a la línea original. Así que entre estos dos píxeles, tenemos que decidir cuál está más cerca de la línea original y elegir ese píxel.
Denotemos por dupper, la distancia del píxel (xk + 1), (yk + 1) de la línea que es el pixel candidato superior de la línea como se muestra aquí. De forma similar, d inferior indica la distancia del píxel candidato inferior de la línea.
Ahora, en (xk + 1), que es en estos puntos y se da por esta expresión usando la ecuación de la línea, donde m es la pendiente. Entonces podemos decir que d upper puede ser dado por ((yk + 1)-y), que es este valor menos este valor y, que se da aquí o esta expresión.
Del mismo modo, dlower también se puede dar como y menos yk. Como puedes ver aquí, este es el valor y y este es el valor de yk. Así que sustituir la y de esta ecuación, puede obtener esta expresión. Ahora, hagamos algún truco matemático en estas expresiones.
Pero antes de eso, debemos tener en cuenta que si la diferencia es menor que 0 entonces el píxel inferior está más cerca y lo elegimos, de lo contrario, elegimos el pixel superior. La distancia entre los valores y aquí, aquí, y aquí; las dos distancias que hemos usado en expresar dupper y dminer. Si la diferencia es menor que 0, entonces elegimos el píxel inferior porque ese punto está más cerca de la línea, de lo contrario, elegimos el pixel superior.
Ahora, vamos a sustituir m con esta relación, Δy/Δx, donde Δy es la diferencia de coordenadas y entre los puntos finales y Δx es la diferencia de coordenadas x entre los puntos finales. Y luego reorganizamos y reemplazamos esta expresión por c, que es un término constante. Como puedes ver aquí, todas son constantes.
Entonces, ¿qué obtenemos? Este término para ser igual a este término, ambos lados hemos multiplicado por Δx y reemplazamos m por estas expresiones. Reacomodando y expandiendo, obtenemos esto, luego reemplazamos este término constante aquí con c para obtener esta expresión. Esta es una simple manipulación de los términos.
Ahora, denotamos el lado izquierdo por pk, lo llamamos un parámetro de decisión para el paso kth. Ahora, este parámetro se utiliza para decidir la cercanía de un píxel a la línea. Ahora, su signo será el mismo que el del signo de la diferencia dmind-dupper.
Así, si pknate 0, entonces este píxel inferior está más cerca de la línea y lo elegimos, de lo contrario, elegimos el pixel superior.
Así que eso está en el paso k. Ahora, en el paso k + 1 que es el siguiente paso, obtenemos pk + 1. Ahora, eso es esencialmente dado por esta expresión donde reemplazamos a xk con xk + 1 y yk con yk + 1. Estos dos términos lo reemplazamos con el siguiente término. Entonces tomamos una diferencia entre los dos, pk + 1-pk, que nos da esta expresión.
Ahora, sabemos porque estamos lidiando con una cuadrícula de píxeles que xk + 1 es esencialmente xk + 1. Así que podemos reorganizar y reescribir la expresión como pk + 1 = pk + 2Δy-{este término}. Eso significa que la variable de decisión en el paso k + 1th es dada por la variable de decisión en el paso kth más un término; este y ese término.
Ahora, si pk < 0, que es el píxel inferior está más cerca, entonces establecemos ykp + 1 = yk, de lo contrario, establecemos yk + 1 = yk + 1. Por lo tanto, basado en el signo de pk, este término se convierte en 0 o 1. Así que puedes ver la importancia física de esta figura. Así que si pk < 0 que significa en la etapa actual, el pixel más bajo está más cerca. Eso significa que hemos elegido este.
Luego en la siguiente etapa, tenemos que elegir yk + 1 = yk que es el píxel más bajo. Si ese no es el caso, entonces tenemos que elegir yk + 1 = yk + 1 que es el pixel superior. Así que dependiendo del signo de pk, este término yk + 1-yk resulta ser 0 o 1. Si pk < 0 entonces es 0; si pkraw 0 entonces es 1.
Así que, donde empezamos, entonces tenemos que decidir sobre el primer parámetro de decisión y que llamamos p0, que se da por dos veces delta y menos delta x. Este valor lo calculamos y luego seguimos.
Así que el algoritmo general se da aquí. Primero calculamos estas diferencias entre los puntos finales y el primer parámetro de decisión. Entonces vamos dentro de un bucle hasta llegar al punto final. Empezamos con un punto final y hasta que alcancemos el otro punto final, continuamos en el bucle.
Ahora, si p < 0, establecemos esa diferencia para ser 0 y luego actualizar p como p + 2Δy. Si p≥ 0, se actualiza p como se indica en esta expresión y luego se añade el valor x-y correspondiente en el conjunto de píxeles que es la salida del algoritmo. Por lo tanto, dependiendo del valor de decisión, elegimos un píxel y lo añadimos al conjunto de píxeles.
Ahora, aquí suponemos que m está dentro de este rango. Cuando m está fuera de este rango, tenemos que modificar este algoritmo pero eso es una modificación menor. Así que puedes probarlo tú mismo.
Entonces, ¿cuál es la ventaja de este algoritmo? Aquí si nota, estamos eligiendo los píxeles en cada paso dependiendo del signo del parámetro de decisión, y el parámetro de decisión se calcula por completo con operaciones de entero por lo que no hay ninguna operación de coma flotante.
Por lo tanto, hemos eliminado todas las operaciones de coma flotante; adiciones, redondeo, así como multiplicaciones que son una enorme mejora porque, en realidad, necesitamos hacer un gran número de líneas en un corto lapso de tiempo, un lapso de tiempo muy corto. Así que allí este ahorro es sustancial. Hay incluso mejores enfoques, pero no vamos a discutir más sobre ellos.
Ahora, intentemos entender el algoritmo en términos de un ejemplo.
Continuaremos con nuestro ejemplo que hemos introducido en la conferencia anterior. Así que este es el segmento de línea dado, estos son los puntos finales ya mapeados y nuestro trabajo es averiguar los píxeles intermedios que corresponden a los puntos de la línea.
Así que empezaremos con la informática Δx, Δy, y la p inicial. A continuación, se inicia con un punto final y se añade a la lista de píxeles, el punto final.
Ahora, hemos calculado que p es 1, que es ≥0. Así que aquí, el píxel superior está más cerca que significa que elegimos este. Añadimos esto y actualizamos p con la expresión para ser -3, y (3, 3) se añade a la cuadrícula. Ahora, este no es el punto final, todavía no hemos llegado al punto final por lo que continuaremos.
En la segunda ejecución, comprobamos que p es -3, que ≤0. Así que en el segundo caso, se elige el píxel inferior y actualizamos p de nuevo, para ser 3, añadir este píxel inferior a la lista de salida y comprobar si hemos llegado al punto final. Como aún no hemos llegado seguimos el bucle. Y de esta manera, seguimos recibiendo otros puntos.
Así que en la siguiente etapa, p= 3 > 0. Así que elegimos el píxel superior, añadir este a la lista de píxeles de salida, continuar el bucle ya que todavía estamos para llegar al punto final.
Entonces encontramos p a ser -1, menos de 0. Así que elegimos el píxel inferior, añadimos el píxel a la lista de salida, y ahora, vemos que hemos llegado al otro punto final. Así que paramos el bucle y añadimos el otro punto final a la lista. Ese es nuestro último paso.
Así que, por fin, ¿cuáles son los puntos que obtenemos? Estos son los píxeles que obtenemos siguiendo los pasos del algoritmo de Bresenham. Ahora, puede compararlo con los métodos anteriores que utilizamos. Sin embargo, mientras compartas, debes tener en cuenta el número de operaciones de coma flotante que evitamos porque esa es la ventaja. Así que si encuentras que tanto los conjuntos como todos los conjuntos que hemos encontrado antes son los mismos que no es un problema porque nos salvamos en términos de cómputo.
Así que, con eso, terminamos nuestra discusión sobre la conversión de las líneas de exploración. Así que aprendimos tres cosas; primero, empezamos con un enfoque simple, encontramos sus problemas, entonces discutimos un enfoque mejorado que es el enfoque de DDA. Y luego, finalmente discutimos un enfoque aún mejor, el algoritmo de trazado de la línea de Bresenham, que elimina todas las operaciones de coma flotante. Ahora nos movemos para escanear la conversión de otra forma primitiva que es círculo.
Inicialmente, asumiremos que el círculo está centrado en el origen con radio r y su ecuación se da por x2 + y2 = r2. Todos conocemos esta ecuación. Ahora, en el enfoque simple, ¿el enfoque más intuitivo y sencillo que hacemos? Resolvemos para y después de cada incremento de la unidad de x en la cuadrícula de píxeles mediante el uso de la ecuación.
Claramente, aquí tenemos un montón de cálculos, cálculos de coma flotante, que implican raíz cuadrada y multiplicaciones porque r no necesita ser entero. Así que esto es ineficiente. También es posible que tengamos que redondear los valores calculados, que es la adición de otras operaciones de coma flotante y los píxeles que obtenemos pueden no generar un círculo suave porque puede haber una brecha entre los puntos reales y los píxeles elegidos después de redondear.
Así que sufre de muchos problemas y requerimos una mejor solución.
Intentemos pasar por una de esas soluciones, que se llama el algoritmo de punto medio.
Ahora, este algoritmo explota una interesante propiedad de círculo que se llama simetría de ocho vías. Ahora, ¿qué es esta propiedad?
Si nos fijamos en esta figura, veremos que este es el origen y el círculo está alrededor del origen, podemos dividir el círculo en 8 cuadrantes, estos son los cuadrantes. Y si determinamos un punto en cualquier cuadrante decir este punto, entonces podemos determinar otros siete puntos en el círculo que pertenecen a los siete cuadrantes sin muchos cálculos.
Así que si este punto es (x, y), entonces podemos decir que este punto será (y, x), será (y, -x). Este será (x, -y), este será (-x, -y), este será (-y, -x), este será (-y, x), y éste será (-x, y). Así que esto lo podemos determinar inmediatamente sin ningún otro cálculo.
Podemos explotar esta propiedad en la conversión de escaneo de círculo y calculando un punto en un cuadrante y luego utilizar ese punto para derivar los otros siete puntos en el círculo. Eso significa que determinamos un píxel, y a partir de ahí determinamos los otros siete píxeles. Así que en lugar de determinar los píxeles a través de la computación ocho veces, lo hacemos una vez y los otros siete cálculos de tiempo que ahorramos.
Ahora, veamos cómo determinar un píxel para un cuadrante dado. Supongamos que hemos determinado un píxel (xk, yk); este es un cuadrante del círculo dado. Ahora, el siguiente píxel debería ser este o este. De nuevo, podemos llamarlos píxel de candidato superior y píxel candidato más bajo. Y en este caso, tenga en cuenta que vamos hacia abajo a lo largo de esta dirección, por las líneas de exploración, y nuestro objetivo es elegir un píxel que esté más cerca del círculo. Ahora, ¿cómo decidimos cuál de estos dos píxeles candidatos está más cerca del círculo?
De nuevo, vamos por algún truco matemático.
Ahora, la ecuación de círculo, podemos reorganizar de esta manera, f (x, y) = x2 + y2-r2, esta es la ecuación de círculo que podemos reafirmar de esta manera.
Ahora, esta función la podemos evaluar como se muestra aquí. Es decir, si (x, y) < 0, si el punto (x, y) está dentro del círculo; es 0 si está en el círculo, y será mayor que 0 si el punto está fuera del círculo. Esto lo sabemos por geometría.
Entonces, podemos evaluar la función en el punto medio de los dos píxeles candidatos. Eso significa en (xk + 1, yk-½). Tenga en cuenta que esto es yk, así que punto medio será este punto que es yk-½ y será xk + 1 que será la nueva coordenada x. Ahora, esta será nuestra variable de decisión pk después de k steps. Así que intentemos ver cómo se ve esta variable.
Así que esencialmente, calculamos esta función en el punto (xk + 1, yk-½), que es el punto medio entre los dos píxeles candidatos, y la mitad porque esta es la distancia de la unidad, por lo que la mitad o el punto medio será la mitad de esta distancia de la unidad.
Por lo tanto, pk será el valor de la función en este punto. Ahora, si ampliamos la función con estas coordenadas, entonces obtenemos esta expresión que es la expresión para pk.
Ahora, si pk < 0 significa que, la función se evalúa como menor que 0. Entonces sabemos por las propiedades geométricas que el punto medio está dentro del círculo. Eso significa que el pixel candidato superior estará más cerca del límite del círculo. Así que elegimos (xk + 1, yk). Si ese no es el caso, entonces elegimos el otro píxel candidato que es (xk + 1, yk-1).
Tenga en cuenta que vamos por las líneas de exploración, por lo que la próxima y coordenada será yk-1. Porque en ese caso, el punto medio está fuera y este píxel candidato más bajo está más cerca del límite.
Ahora, veamos la expresión para la variable de decisión en el siguiente paso que es pk más 1. Así que aquí, nuestro nuevo punto será xk + 1 + 1, incremento por 1, y yk + 1-½, que después de la expansión se verá así.
Ahora, podemos ampliarlo más y luego reorganizar para obtener una expresión simplificada que es pk + 1 es el valor de decisión actual más este término.
Ahora, yk + 1 es yk si pk es menos de 0 que ya hemos visto. Así que en ese caso, pk + 1 será pk + 2, xk + 3. Ahora, si pk mayor que 0 entonces yk + 1 será yk-1 que también hemos visto. Entonces el término pk + 1 se convertirá en algo así.
Como puede ver estas son todas las operaciones de entero y elegimos los píxeles basados en un enfoque incremental que está calculando el siguiente parámetro de decisión del valor actual y que también evitando las operaciones de coma flotante.
Sin embargo, esto no es necesario porque aquí, el parámetro de decisión inicial o la variable de decisión implica la operación de coma flotante. Y tenemos que tener en cuenta que a diferencia del algoritmo de Bresenham, aunque, la expresión para calcular la siguiente variable de decisión no implica ninguna operación de coma flotante aparentemente, pero cuando empezamos con tal vez un valor de coma flotante y entonces eso quedará. Así que aquí no estamos eliminando completamente las operaciones de coma flotante, sino que las estamos reduciendo significativamente.
Entonces, ¿cuál es el algoritmo completo? Primero calculamos la primera variable de decisión y elegimos la primera o el punto de partida. Ahora, un punto que hemos elegido, entonces usando la simetría podemos añadir otros cuatro puntos o píxeles.
Ahora, cuando el parámetro de decisión es menor que 0, actualizamos el parámetro de esta manera y conseguimos que el píxel se añada al conjunto de píxeles. Cuando el parámetro de decisión es mayor que 0, entonces actualizamos el parámetro de decisión de esta manera y obtenemos este punto como el nuevo píxel. Y luego añadimos el nuevo píxel a la lista de píxeles más añadimos los siete puntos simétricos utilizando la propiedad simétrica y la seguimos hasta llegar al final del cuadrante.
Así es como funciona el algoritmo de punto medio. Como ha señalado, si vamos por un enfoque simple, requerimos una gran cantidad de operaciones de coma flotante, multiplicaciones, raíz cuadrada, que evitamos por este algoritmo de punto medio.
Ahora aquí, por supuesto, puede ser notado que el algoritmo asume que el círculo está centrado en el origen y requerimos alguna modificación cuando estamos asumiendo círculos que tiene su centro en cualquier lugar arbitrario. Pero esa modificación menor no vamos a entrar en los detalles, puedes probarlo tú mismo.
Ahora, intentemos entender mejor este algoritmo en términos de un ejemplo ilustrativo.
Comencemos con el supuesto de que tenemos un círculo con radio r para ser 2.7 que significa un número real. Ahora, vamos a ejecutar el algoritmo para averiguar los píxeles que debemos elegir para representar el círculo.
La primera etapa es el cálculo p, que es 5/4-r, que nos da este valor. Y empezamos con este punto redondeando r a 3 y nos llega este punto como el primer punto de nuestra lista, primer pixel. Y en base a este primer píxel, añadimos otros cuatro píxeles en la lista de salida. A continuación, entramos en el bucle principal.
Así que tenemos p < 0, entonces actualizamos p según la expresión para p < 0 y luego, obtener este nuevo valor de píxel. Con eso, añadimos ocho píxeles a la lista de salida (1, 3), (3, 1) (3, -1) (1, -3), y así sucesivamente. Dado que todavía no hemos llegado al final del bucle, seguimos con el bucle.
En la segunda ejecución de bucle, tenemos p> 0. Así que usamos la expresión para actualizar p y obtenemos el nuevo valor y decidimos en este nuevo píxel, basado en que elegimos los ocho píxeles como se muestra aquí. Ahora, hemos llegado al final del bucle, se alcanza la condición de terminación así que paramos. Así que entonces al final lo que conseguimos.
Aquí se muestran 20 píxeles. Una cosa que puedes notar es que hay algunos pixeles que se repiten. Por ejemplo, (2, 2) se producen dos veces; (-2, -2) se han producido dos veces; (2, -2) se han producido dos veces. Así que esta repetición está ahí al final de la ejecución del algoritmo.
Estas entradas duplicadas, tenemos que eliminar. Por lo tanto, antes de la representación, realizamos más comprobaciones y procesos en la lista de salida para eliminar dichas entradas duplicadas. Así que el algoritmo puede darnos una lista que tiene entradas duplicadas, tenemos que realizar algunas comprobaciones antes de utilizar esos píxeles para representar el círculo para evitar duplicaciones. Así que eso es lo que hacemos para hacer círculo.
Así que hemos aprendido a hacer línea, hemos aprendido a hacer círculo. En ambos casos, nuestro objetivo era mapear desde valores de números reales a cuadrículas de píxeles. Y nuestro objetivo era hacerlo sin implicar operaciones de coma flotante en la medida de lo posible porque, en aplicaciones prácticas, necesitamos rendir estas formas con mucha frecuencia. Y allí, si hay demasiadas operaciones de coma flotante, entonces la velocidad a la que podemos rendirnos puede desacelerarnos dándonos la percepción de una imagen distorsionada o parpadeos que no son bienvenidos.
En la próxima clase, discutiremos más sobre la representación de otras cosas. Cualquier cosa que hayamos discutido hoy, puede ser encontrada en este libro.
Puedes pasar por el capítulo 9, sección 9.1.2 y 9.2 para obtener los detalles sobre los temas que hoy cubrimos. Así que nos reuniremos en la próxima conferencia. Hasta entonces, gracias y adiós.