Espacio Afin

Tarea2

Antes de hablar sobre el espacio afin, es estrictamente necesario abordar el concepto de espacio vectorial.

Espacio vectorial

• Un espacio vectorial se compone de escalares y vectores.

• Definimos las operaciones de suma (escalar y vectorial) y multiplicación escalar y escalar-vector

• Son operaciones cerradas: sumar dos vectores o multiplicar escalares por vectores nos dan otros vectores

• Además, existen elementos neutro e inverso.

• La multiplicación escalar-vector es distributiva respecto a la suma de escalares y a la suma de vectores

Ejemplos: vectores geométricos, grupos o tuplas de reales en Rⁿ

Otros conceptos de interés:

• Combinación lineal de vectores

• Independencia lineal

• Dimensión del espacio vectorial

• Bases de un espacio vectorial

• Representación de vectores en función de una base: coordenadas

• Cambio de coordenadas (atención a la relación entre cambio de bases y cambio de coordenadas; se basan en la transformación inversa)

Espacios afines

Los espacios vectoriales carecen de conceptos como posición y distancia (tenemos vectores, con magnitud y dirección, pero no están fijos a un punto).

Tampoco podemos definir un origen.

En los espacios afines nos aparece otra entidad: los “puntos”

Por tanto, en un espacio afín tenemos:

– Escalares

– Vectores: nos definen direcciones y desplazamientos

– Puntos, que nos especifican posiciones en el espacio

En un espacio afín podremos definir sistemas de referencia asociados a un origen concreto.

Definimos dos operaciones nuevas:

• Substracción de puntos P-Q: origina el vector v que va de Q a P

• Adición punto-vector: en el caso anterior, P = Q + v

• No está definida la suma de puntos (aunque sí algo que podemos considerar como un tipo especial de suma que llamaremos suma afín)

• Ahora podremos definir una base en el espacio afín, constituida por un origen O y una base del espacio vectorial asociado. En ella tanto puntos como vectores podrán ser representados (teniendo representaciones únicas)

Sistemas de referencia (espacio afín)

Necesitamos un punto (O, origen) y una base del espacio vectorial (i, j y k)

Cada punto y vector tiene una representación única. Por ejemplo, para 3D:

• Vectores: v = x . i + y . j + z . k (i, j y k son vectores unitarios en las direcciones de los ejes X, Y y Z)

• Puntos: P = a . v + O = a x . i + a y . j + a z . k + O

• Se pueden utilizar sus coordenadas, que para el vector v serían (x, y, z, 0), y para el punto P, (a x, a y, a z, 1)

NOTA: representamos un punto 3D por 4 coordenadas

• Se pueden tomar los vectores como equivalentes a un punto en el infinito (lo estudiaremos al ver las coordenadas homogéneas)

• Podemos definir sistemas de referencia de mano derecha y de mano izquierda.

Espacios euclídeos

Necesitamos todavía otros conceptos, como los de distancia y ortogonalidad.

Para ello, definimos el producto escalar de vectores:

u . v = | u | . | v | . cos (ө)

(ө: ángulo formado por u y v )

Propiedades del producto escalar:

• Conmutativa y asociativa (respecto a la suma de vectores y

multiplicación por un escalar)

• Si v ≠ 0, v . v > 0; 0 . 0 = 0

• Si u, v ≠ 0 y u . v = 0, ambos vectores son ortogonales

• El producto escalar nos permite calcular la distancia entre dos puntos (mediante el producto escalar del vector que los une) y el ángulo entre dos vectores.

El producto escalar nos permite:

• Calcular la distancia entre dos puntos (mediante el producto escalar del vector que los une) y el ángulo entre dos vectores

• Descomponer un vector u en sus componentes paralela y ortogonal a otro v (si tomamos un vector unitario en la dirección de v, su producto escalar con u nos da la proyección de u sobre v y su diferencia con u, nos da su componente ortogonal a v

• Hallar la mínima distancia entre un punto y una recta (podemos descomponer el vector que une el punto en cuestión con cualquiera de los de la recta en la componente normal al vector colineal con la recta)

Otros conceptos

• Producto vectorial de dos vectores: Nos permite obtener otro vector normal al plano definido por los otros dos

Módulo: | u x v | = | u | . | v | . sen (ө)

Dirección: perpendicular al plano definido por u y v

Sentido: regla del “sacacorchos”

• Sumas afines. Representación de segmentos y polígonos convexos

• Envolturas convexas

• Ecuaciones de líneas y planos

• Tratamiento de otras primitivas 3D (líneas y superficies curvas)

Transformaciones en el espacio afín 2D

Sistema de referencia en 2D:

Puntos y vectores: se representan mediante dos o tres coordenadas:

• P: (x, y, 1) o bien (x, y)

• v: (x, y, 0) o bien (x, y)

Proyecciones Geométricas

Tarea 3

Elementos de una proyección

La proyección de un objeto esta definido por:

o Rayos de proyección, llamados proyectores, que emanan del centro de proyección (COP) o punto de referencia de proyección (PRP), pasando a través de cada punto del objeto.

o El plano de proyección que es intersectado por los proyectores.

o El centro de proyección puede estar a una distancia finita o infinita del plano de proyección.

o Observación: El COP corresponde al centro del lente en la cámara, o en el ojo, y en los sistemas de gráfica por computadora, es el origen del marco de la cámara

Clasificación

Paralelas:

Ortográficas: elevación superior, frontal y lateral.

Axonométricas: Isometricas, Dimetricas y Trimetricas.

Oblicuas: Cabinet, Cavalier.

Perspectiva. Dependiendo del número de puntos de fuga tenemos:

De 1 punto.

De 2 puntos.

De 3 puntos.

Proyecciones Planares

La clase de proyecciones tratadas aquí se conocen como proyecciones geométricas planas, ya que la proyección es sobre un plano y no sobre una superficie curva, y usa proyectores rectos y no curvos. Muchas proyecciones cartográficas no son planas o geométricas, como el mapa del mundo.

Proyecciones paralelas

Ventajas:

Reproduce vistas de distintos lados del objeto.

Preserva dimensiones y ángulos relativos al objeto.

Desventaja: No proporciona el verdadero aspecto del objeto.

La distancia entre el centro de proyección y el plano de proyección no es finita.

Imagen

Proyecciones Ortogonales

• Ocurre cuando la dirección de proyección es perpendicular al plano de proyección

• Proporciona las vistas: laterales, frontales y superior (CAD).

Proyecciones oblicuas

• La dirección de proyección no es perpendicular al plano de proyección.

Proyecciones en perspectiva

La distancia entre el centro de proyección y el plano de proyección es finita.

Muestra un efecto visual realista salvo factores de escalamiento.

Son las mas usadas en computación gráfica.

Proyecciones en perspectiva

La elección adecuada del plano y centro de proyección puede facilitarnos mucho los cálculos.

Todas las rectas se cortan en un punto fuera del plano de proyección.

En las proyecciones perspectivas las rectas en la dirección de proyección son tales que pasan todas por un punto fijo que llamaremos centro de proyección

Las proyecciones en perspectiva producen vistas más realistas pero en general no mantienen las distancias ni los ángulos relativos.

Este tipo de proyección es la más usada en dibujo artístico.

Fustrum

El Frustrum se define como una piramide semi definita, siendo su base un poligono rectangular.

Ella define que es lo que partes se iran a visualizar desde la cámara, esto se denomina de Volumen de Visualización.

Puntos de fuga

Existe varios puntos de fuga en una escena, estas aparecen cuando las rectas paralelas convergen en un punto.

Si el punto de fuga se encuentra en uno de los ejes cartesianos, entonces se denomina de punto de fuga principal

• Perspectiva de un punto de fuga (vanishing point).

Perspectiva de dos puntos de fuga

Perspectiva de tres puntos de fuga

Reporte de las presentacione sobre Modelos de Color e Ilumniación 9

RADIOSIDAD

• La síntesis de imágenes realistas es un campo de la informática gráfica.

• Objetivo: simular las propiedades ópticas y físicas de la luz, para obtener imágenes realistas de una escena virtual, de tal modo, que un observador no pueda distinguir entre la imagen real y la virtual.

Características:
o Trata con reflexiones difusas ideales (no permite modelar efectos ópticos)
o toda la energía recibida es reflejada (salvo aquella que se absorbe) por igual a lo largo de toda la superficie del objeto a tratar
Resultados:
o Mucha calidad
o innecesario recalcular la iluminación de la escena al cambio de cámara
o Muy caro
o Sensible a cambios de posición o forma de objetos

Aplicaciones:
Videojuegos
• Películas generadas por ordenador (total o parcialmente)
• Diseño de edificios
• Decoración
• Diseño de mobiliario
• Estudios de impacto en diseño de interiores y diseño ambiental
• Diseño de luminarias y predicción de sus propiedades
• Ingeniería civil: posicionamiento de luminarias
• Realismo para sistemas de realidad virtual

Descripción general del proceso

• El concepto básico determina la cantidad de energía que sale de una superficie, esto se deberá tanto a la energía propia que emita como a la que refleje procedente de otros puntos. Si consideramos esta energía por unidad de superficie tenemos lo que se llama Radiosidad
• Consideraciones que vamos a hacer para establecer un modelo computacional que nos permita determinar la Radiosidad en la escena:
• – Todos los objetos son reflectores difusos perfectos.
• – La escena esta descompuesta en superficies o patches, y el problema será encontrar la radiosidad (Bi) asociado a cada uno de ellos.
• – La radiosidad corresponde con el equilibrio energético de la escena
• Consecuencias:
• – No existen reflexiones especulares.
• – Las fuentes se consideran extensas.
• – Se realiza solo un balance energético.

Reporte de las presentacione sobre Modelos de Color e Ilumniación 8

TRAZADO DE RAYOS

Técnica que nos permite visualizar mundos en 3D

Se puede describir generalmente de la siguiente forma:
Tira un rayo por cada píxel de la pantalla y lo hace rebotar por toda la escena una cantidad determinada de veces.
El rayo es un vector que se interfecta con los objetos de la escena.
El algoritmo básico tiene que comprobar la intersección con todos los objetos de la escena y de los objetos intersectados se elige el que más cerca del punto de visión o de la cámara.
Cuando un rayo interfecta en un objeto, el rayo rebota en varios más y esos a su vez van a seguir rebotando en otros objetos, hasta una profundidad que nosotros especifiquemos.

Reporte de las presentacione sobre Modelos de Color e Ilumniación 7

ILUMINACIÓN GLOBAL

Es una técnica que trata de emular el comportamiento natural de la luz, a través de diversos algoritmos.

A diferencia de la iluminación local, en la que el objeto debe estar directamente iluminado por alguna fuente de luz y por consiguiente proyectar una sombra, en la realidad cuando un rayo de luz choca con un objeto puede pasar que el rayo es reflejado o que sea absorbido por el objeto, dependiendo del material de dicho objeto.

El modelo de iluminación global normalmente utiliza como parámetros de entrada las características físicas de los materiales de los que están hechos los objetos, las luces presentes en la escena, y los mecanismos de interacción entre objetos y luces que es calculado por una serie de algoritmos afines como ray casting, ray tracing, radiosity y photon map.

Se analiza también la cantidad de luz que recibe el objeto proveniente de otros objetos. Esto es lo que permite representar superficies tales como espejos o cristales.

El color e intensidad de un punto de un objeto se calcula en base a la luz que recibe directamente dicho objeto procedente de las fuentes, la luz que le llega indirectamente resultante de la reflexión y refracción en otros objetos de la escena, y la luz que emite el propio objeto.
En la ecuación de renderizado se expresa la luz que es transferida de un punto a otro en términos de la intensidad emitida del primero al segundo y también en términos de la luz emitida desde todos los puntos que se refleja en el primero y llega al segundo.

El proceso desde la representación de los objetos hasta los algoritmos de Iluminación Global es el siguiente:

La primera etapa genera modelos de los objetos, es decir los representa matemáticamente o por medio de aristas, vértices y polígonos.

Después se selecciona una escena y se aplican proyecciones para transformar la vista tridimensional en una vista bidimensional.


Luego se determinan las superficies que serán visibles al observador usando otros algoritmos.

Y por ultimo, el color que se asigna a cada píxel de la proyección de una superficie visible es una función de la luz reflejada y transmitida por los objetos y se determina con los métodos de iluminación Global (Ray Tracing o Radiosity).

Reporte de las presentacione sobre Modelos de Color e Ilumniación 6

ILUMINACIÓN DE BLINN

Environment mapping

Método para simular reflexiones especulares con pocos cálculos desarrollado por James Blinn.

En 1978 Blinn propuso la técnica conocida como bump mapping. Consiste en usar la textura no para dibujar el color de los puntos del objeto, sino para darle apariencia rugosa. Usaba, sobre un objeto definido, una imagen en escala de grises en la que los colores claros significaban protuberancias y los oscuros huecos.

El método de Blinn es:
· Un método de sombreado de uso general.
· Es una variación del método de sombreado de Pong.
· En este método, los brillos aparecen más redondeados.
· Se pueden obtener brillos con ángulos bajos.

Reporte de las presentacione sobre Modelos de Color e Ilumniación 5

MÉTODO DE ILUMINACIÓN DE PHONG

Se venía abordando el tema sin precisar un poco en algunos aspectos que se manejan normalmente, así pues me parece bien comenzar por citar dichos aspectos.

Reflexión especular

o La luz que llega al objeto rebota en una dirección concreta con una intensidad bastante alta.
o A medida que nos alejamos de la dirección del vector que rebota vemos menos esta reflexión.
o La forma de modelar este efecto se hace siguiendo las fórmulas de Phong.
Cada objeto tiene:
© Su color especular (OS)
© Su constante de reflexión especular (KS)
© Un exponente de reflexión (n).

Reflexiones de luz:

Reflexión difusa

La luz que llega al objeto rebota pero con menor intensidad que la especular y se difumina por su superficie.
Para modelar la reflexión difusa se usa la fórmula de Lambert (mucho más sencilla que la de Phong!).

Absorción

· La absorción es la parte de la luz que se “queda” en el objeto.
· Un objeto transparente no absorbe nada, un semitransparente sólo absorbe una parte de la luz y uno opaco la absorbe totalmente.
· La absorción se modela simplemente con una constante para cada objeto.

Transmisión y refracción

· La transmisión consiste en que la luz pasa a través de un objeto transparente y sale por el otro lado.
· La refracción es el fenómeno que se produce cuando la luz cambia de medio por el que viaja.
· Por ejemplo cuando la luz va por el aire y entra en el agua de una piscina, parece que el fondo está más cerca.

Luz Indirecta
La luz indirecta es la que emiten los objetos que rodean al que estamos estudiando.
La luz emitida por otros objetos no es que sean fuentes de luz, se trata de reflexiones.
Este tipo de efecto NO es modelable mediante raytracing y se requieren técnicas más avanzadas como la radiosidad para poder ver este efecto.

Finalmente con lo expuesto anteriormente resulta más comprensible el funcionamiento del algoritmo.

Algoritmo de Pong
El método Phong para iluminación local fue desarrollado por Bui Tuong Phong
Puede producir cierto grado de realismo en objetos tridimensionales combinando tres elementos: luz difusa, especular y ambiental para cada punto en una superficie.
Emplea muchas suposiciones, como por ejemplo:

v Que todas las luces son puntos.
v Solo una superficie geométrica es considerada
v Solo modelos locales de difusa y especular.
v Colores especulares son los mismos que los colores de luz y el ambiente es constante y global.

Por último es necesario mencionar que:

v En lugar de interpolar las intensidades como Gouraud , lo que hace Phong es interpolar las normales para cada punto de la superficie.

v Con este método es con el que se consiguen resultados mas realistas, pero tiene el inconveniente de que necesita realizar entre 6 y 7 veces mas cálculos que para el método de Gouraud.

Reporte de las presentacione sobre Modelos de Color e Ilumniación 4

SOMBREADO GOURAUD

Este tema me fue asignado para presentarlo, así pues puedo decir que ya se ha hablado con anterioridad de lo que es un modelo de iluminación, aunque en lo personal me parece conveniente recordarlo de manera general y simplificada sin ahondar en especificaciones las cuales pueden ser consultadas en las presentaciones anteriores.

Introducción

• Entendemos por modelo de iluminación el cálculo de la intensidad de cada punto de la escena
• En el cálculo de la intensidad de un punto intervienen:
– El tipo e intensidad de la fuente de luz
– El material del objeto
– La orientación del objeto con respecto a la luz
• Fuentes puntuales o puntos de luz:
– No tienen dimensión
– No tienen dirección (emiten de forma radial)
– Consideramos que una luz es puntual si su dimensión es muy pequeña comparada con la de los objetos de la escena
– Ejemplos: sol, bombillas...
• Fuente de luz distribuidas:
– Tienen dimensión
– Tienen dirección
– Ejemplos: focos, tubos de luz...
Sombreado

El sombreado o visualización de polígonos es la asignación de intensidades a cada punto de los polígonos que forman un objeto.

¿En qué consiste el sombrado Gouraud?

Usando los colores de cada normal de vértice como limitante de los valores, se interpola el color linealmente para cada cara del polígono.

La cualidad más sobresaliente es que el proceso de interpolación es rápido.
Desventajas
• No suele representar la luz especular
– en la interpolación los máximos siempre están en los vértices
– la luz especular intensa afecta a un área pequeña




• El modelo local puede no ser coherente
– emitir más luz de la que se recibe
• En coordenadas de vista las distancias en “x” e “y” no son lineales respecto a “z”
• Contorno poligonal
– Se soluciona con mallas más detalladas
– Superficies paramétricas

Reporte de las presentacione sobre Modelos de Color e Ilumniación3

FLAT SHADING (Iluminación Plana)

Consistente en asignar un color uniforme a cada polígono, esto se consigue aplicando el color sobre la normal de cada polígono.

Características

o El modelo representa la superficie real sin ser una aproximación de una superficie curva.
o La luz incide con un ángulo que es igual para toda la superficie.
o El observador está en el infinito o los polígonos son muy pequeños
o Está basada en la suposición de que la luz se refleja uniformemente en todas direcciones.

El algoritmo de manera general consiste:
Calcular el vector normal de la superficie (polígono) que queremos iluminar
Calcular el ángulo de incidencia (theta)
Calcular la intensidad de reflexión




Ventajas

• Es muy rápido ya que solamente se calcula la iluminación una vez por polígono.
• Podría usarse para bocetos en baja calidad.
• Da resultados bastante buenos para figuras con caras planas.

Desventajas

o La superficie del objeto tendrá una apariencia "cuadriculada" ; sobre todo en escenas con puntos de luz en las que la intensidad del color depende de la orientación con respecto al punto de luz.

Reportes de las presentaciones sobre Modelos de Color e Ilumniación2

ILUMINACIÓN LOCAL.

Los modelos de iluminación simples tratan sobre la luz que refleja un punto de la superficie de un objeto. Es luz que proviene de una fuente de luz, refleja en el objeto en un punto y va al observador.

Dado un punto, a partir de algunos datos básicos (el color del punto, su ubicación en el espacio, la normal a la superficie en ese punto, la ubicación de la fuente de luz), se calcula cuánta luz refleja hacia el observador, lo cual determina el color de ese punto en la imagen a ser generada.

Como en el medio real, se puede encontrar:

Luminarias de forma y distribución espectral arbitraria
Diferentes tipos de superficies
Composiciones de escenarios complejas

En el trabajo presentado “Iluminación Local” se plantea como dificultad el aspecto de que la luz que llega a un determinado punto del espacio depende de todas los objetos que componen la escena.

Clasificación de luz

Por lo anterior se debe determinar la energía luminosa que llega a un punto en una dirección.
A continuación se hace una clasificación de la luz.

La luz se divide en 3 tipos:
Ambiente, difusa y especular.

Los objetos reflejan estos 3 tipos de forma independiente.

Me parece necesario citar las características de la anterior clasificación.

Luz ambiente

La luz ambiental es aquella que no proviene de una dirección concreta, incide sobre todas las partes del objeto por igual

Luz difusa

La luz difusa es la que proviene de una dirección particular y es reflejada en todas direcciones (de manera direccional) .
Afecta a aquellas partes del objeto en las que la luz incide.

Luz especular

¢ La luz especular procede de una dirección concreta y se refleja en una única dirección.

¢ Produce brillos intensos.

¢ Las reflexiones especulares son normalmente del mismo color que la fuente de luz.

¢ La intensidad de la luz especular reflejada depende de:
— La longitud de onda de la luz incidente
— El ángulo de la luz incidente
— Las características del material

¢ La reflexión especular depende de la posición del observador.


Características de la iluminación local

Ø Describe cómo las superficies reflejan o transmiten la luz.
Ø Calcula la intensidad, el color y la distribución de la luz rebotada una única vez.
Ø Sombreado sólo tiene en cuenta fuentes de luz existentes en la escena. No reflexiones entre los objetos.
Ø Interacción de las superficies con la luz. Algunas superficies.
Ø Bloquean la luz, provocando sombras arrojadas sobre otras superficies.
Ø Son brillantes, reflejando y reflejándose sobre otras superficies.
Ø Son transparentes, permitiendo ver otras superficies a través de ellas.
Ø Reflejan luz sobre otras
Ø Calcular solamente la componente de fuentes emisoras (iluminación directa)
Ø Caracterización de fuentes:
– Dirección de emisión
– Intensidad
– Color



Un modelo de iluminación completo contempla las procedencias como causas de la intensidad luminosa observada en un punto:

Fuentes de luz – Objetos
La iluminación local utiliza modelos empíricos de iluminación.
Modelo de iluminación

Combinación de los modelos de iluminación ambiental, difusa y especular.

Reportes de las presentaciones sobre Modelos de Color e Ilumniación

Modelo de luz de Lambert

Principalmente utilizado en técnicas de renderización como radiosidad y trazado de rayos


El modelo de lamber se aplica realmente cuando el angulo de incidencia y el angulo de reflexión son pequeños (relativo a superficies normales)
La modificación del investigador Wolf a las Leyes de Lambert debe ser utilizado en los algoritmos de visión por ordenador (por ejemplo, la forma de sombreado).
El modelo de lambert puede proveer una aproximación muy inadecuada para la reflactancia de los cuerpos mientras que el brillo de una superficie lambertiana es independiente de la vista de dirección.
El modelo ha sido desarrollado para la reflactancia de los cuerpos de superficies asperas.
El modelo cuenta para geometría compleja y fenómenos radiométricos tales como el enmascaramiento, sombreado e interreflexiones entre facetas.
La calidad de la renderizacion de las imágenes depende sobre una gran extensión de la precisión del modelo de reflantancia usado.
La reflexión de una superficie puede ser en términos generales en dos categorías:
· Reflactancia de la superficie que toma el lugar en la interferencia entre dos medios con diferentes índices reflectivos.
· Reflactancia del cuerpo que es debido es debido ala dispersión de la superficie

Comparación entre algoritmos de rasterización de líneas

A continuación no se describirán los métodos, simplemente se harán algunas observaciones en cuanto a estos, tratando de hacer evidentes algunas características.

El analizador diferenciador digital (DDA - Digital Differential Analyzer) es un algoritmo de conversión de rastreo que se basa en el calculo ya sea de y o x

Se efectúa un muestreo de la línea en intervalos unitarios en una coordenada y se determina los valores enteros correspondientes mas próximos a la trayectoria de la línea para la otra coordenada.

El problema con este algoritmo es que se debe redondear números flotantes a enteros y hacer operaciones sobre números flotantes , lo cual toma tiempo.

Para líneas largas, la acumulación de errores de redondeo en adiciones sucesivas del incremento de punto flotante pueden provocar que las posiciones del píxel calculadas se desvíen de la trayectoria real de la línea.

Se puede mejorar el desempeño del algoritmo al separar los incrementos m y 1/m en partes enteras fraccionarias, de forma que todos los cálculos se reduzcan a operaciones de enteros.

Algoritmo de Línea Bresenham Básico

Un algoritmo preciso y efectivo para la generación de líneas de rastreo, desarrollado por Bresenham (1965), convierte mediante rastreo las líneas utilizando solo cálculos incrementales con enteros que se pueden adaptar para desplegar también curvas.

El algoritmo busca cual de dos pixeles es el que esta mas cerca según la trayectoria de la línea.

Consideremos el proceso de conversion para líneas con pendiente positiva 0 < m <>

Las posiciones de pixel a lo largo de la trayectoria de una línea se determinan al efectuar un muestreo de x en intervalos unitarios.

Si se inicia desde el extremo izquierdo (x0,y0) de una línea determinada, se pasa a cada columna sucesiva y se traza el pixel cuyo valor de y se aproxima mas a la trayectoria de la línea de rastreo.

En resumen, los pasos son:

1. Se capturan los dos extremos de la línea y se almacena el extremo izquierdo en (x0,y0).

2. Se carga (x0,y0) en el bufer de estructura, o sea, se traza el primer punto.

3. Se calculan las constantes y, x, 2y, 2y-2x, y se obtiene el valor inicial para el parámetro de decisión

como p0 = 2 y - x.

4. En cada xk a lo largo de la línea, que inicia en k = 0, se efectúa la prueba siguiente: si pk <>

que se debe trazar es (xk+1,yk) y pk +1 = pk + 2 y. De otro modo, el siguiente punto en trazarse es (xk+1,yk+1)

y pk +1 = pk + 2 y - 2x.

5. Se repite el paso 4 otras x veces.

El algoritmo de Bresenham se generaliza para líneas con una pendiente arbitraria al considerar la simetría entre los diversos octantes y cuadrantes del plano de xy.

Para una línea con una pendiente m > 1, intercambiamos las funciones de las direcciones de x y y, o sea, pasamos a lo largo de y en pasos unitarios y calculamos los valores sucesivos de x que se aproximan mas a la trayectoria de la línea.

Si la posición inicial para una línea con una pendiente positiva es el extremo derecho, tanto x como y disminuyen conforme pasamos de derecha a izquierda.

Con el fin de asegurarnos de que los mismos pixeles se tracen sin que importe el extremo en que se comienza, se seleccionara el pixel superior (o inferior) cuando se pase exactamente en el medio (d1 = d2).

En el caso de pendientes negativas, los procedimientos son similares excepto que ahora, una coordenada decrece conforme la otra aumenta.

Por ultimo, es posible manejar los casos especiales por separado.

Las líneas horizontales (y = 0), las líneas verticales (x = 0) y las diagonales | y | = | x | se pueden cargar en forma directa sin procesarlas mediante el algoritmo para el trazo de líneas.

Algoritmo de Punto Medio para la Línea o algoritmo de Bresenham para enteros

.

Para líneas y círculos de enteros, la formulación de punto medio, se reduce a la formulación de Bresenham y por lo tanto se generan los mismos pixeles.

Bresenham (1977) mostró que este algoritmo de línea y circulo de enteros proveen la mejor aproximación a líneas y círculos verdaderos al minimizar el error (distancia) a las primitivas reales.

Kappel (1985) discute los efectos de varios ¡criterios de error.

Se asume que la pendiente de la línea es entre 0 y 1.

Otras pendientes se pueden manejar como reflexiones sobre ejes principales.

Se define a (x0,y0) como el extremo inferior izquierdo y (x1,y1) como el extremo superior derecho.

La línea se representa con una función implícita (esta representación se extiende muy bien para la formulación decírculos) con coeficientes A, B, y C:

f(x,y) = Ax + By + C = 0