• Author / Uploaded
• elvys

Citation preview

2015 TEXTO GUÍÍA RECOPÍLADO:

Programacioó n Graó fica

Sistemas e Informatica - F.N.I. Juan Gregorio Choque Uño 20/01/2015

1

2

Contenido INTRODUCCION A GRAFICAS POR COMPUTADORA....................................10 INTRODUCCION.................................................................................................................. 10 APUNTES DE LA HISTORIA................................................................................................... 11 APLICACIONES..................................................................................................................... 15 Entretenimiento.......................................................................................................................15 Diseño asistido por computador..............................................................................................16 Visualización cientifíca y médica..............................................................................................18 Simulación y entrenamiento....................................................................................................19 Gráficos de presentación.........................................................................................................20 Creaciones artísticas.................................................................................................................21 TECNOLOGÍAS DE SALIDA.................................................................................................... 22 Tecnología de Salida: Vectorial.................................................................................................22 Tecnología de Salida: Raster-Scan............................................................................................24 EL PROCESO DE OBTENCIÓN DE IMÁGENES..........................................................................27 P.O.I. Recorrido de la Escena....................................................................................................28 P.O.I. Transformación del Modelo............................................................................................29 P.O.I. Transformación de la Vista..............................................................................................29 P.O.I. Recortado........................................................................................................................30 P.O.I. Eliminación de Caras Ocultas..........................................................................................30 P.O.I. Proyección.......................................................................................................................31 P.O.I. Transformación del Dispositivo.......................................................................................32 P.O.I. Conversión al Raster........................................................................................................33 P.O.I. Iluminación......................................................................................................................33 P.O.I. Otras Operaciones...........................................................................................................34

PRIMITIVAS - RENDERING.................................................................................. 39 3

INTRODUCCIÓN.................................................................................................................. 39 PRIMITIVAS GRAFICAS......................................................................................................... 41 ESPECIFICACIÓN DE UNA DISCRETIZACION...........................................................................42 DIBUJO DE LÍNEAS RECTAS................................................................................................... 42 EL ALGORITMO MÁS SENCILLO................................................................................................44 ALGORITMO BÁSICO INCREMENTAL DDA................................................................................46 ALGORITMO DE BRESENHAM..................................................................................................50 ALGORITMO DEL PUNTO MEDIO.............................................................................................57 ALGORITMOS BASICOS PARA CIRCULOS...............................................................................62 ALGORITMO BÁSICO (COORDENADAS CARTESIANAS)............................................................62 COORDENADAS POLARES.........................................................................................................64 SIMETRÍA DE 8 LADOS..............................................................................................................66 ALGORITMO DEL PUNTO MEDIO.............................................................................................68 ALGORITMOS PARA ELIPSES................................................................................................ 74 ALGORITMO BASICO (Coordenadas Cartesianas)....................................................................75 ALGORITMO BASICO (Coordenadas Polares)...........................................................................76 ALGORITMO DEL PUNTO MEDIO.............................................................................................77

TRANSFORMACIONES GEOMETRICAS EN 2-D..............................................82 QUE ES UNA TRANSFORMACION?.......................................................................................82 TRANSFORMACION EN 2D................................................................................................... 83 TRASLACION.............................................................................................................................83 ESCALAMIENTO........................................................................................................................85 ROTACION.................................................................................................................................87 COORDENADAS HOMOGENEAS........................................................................................... 89 REPRESENTACION EN COORD. HOMOGENEAS........................................................................91 COMPOSICION DE TRANSFORMACIONES.............................................................................95

4

OTRAS TRANSFORMACIONES..............................................................................................96 TRANSFORMACIÓN VENTANA-ÁREA DE VISTA...................................................................100

VISION TRIDIMENSIONAL................................................................................ 108 COORDENADAS HOMOGENEAS......................................................................................... 108 SISTEMA DE LA MANO DERECHA.......................................................................................109 SISTEMA DE LA MANO IZQUIERDA.....................................................................................110 TRANSFORMACIONES EN 3D............................................................................................. 110 TRASLACIÓN DE UN CUERPO.................................................................................................110 ESCALACIÓN DE UN CUERPO.................................................................................................112 ROTACIÓN SOBRE UN EJE COORDENADO..............................................................................113 ROTACIÓN RESPECTO DEL EJE X.........................................................................................114 ROTACIÓN RESPECTO DEL EJE Y.........................................................................................116 ROTACIÓN RESPECTO DEL EJE Z.........................................................................................117 COMPOSICION DE TRANSFORMACIONES EN 3D.................................................................118

PROYECCIONES.................................................................................................... 121 QUE ES UNA PROYECCION?............................................................................................... 121 PROYECCIONES GEOMÉTRICAS PLANARES.........................................................................122 CLASIFICACIÓN DE LAS PROYECCIONES..............................................................................123 PROYECCIÓN EN PERSPECTIVA........................................................................................... 124 Matemáticas de las Proyecciones en Perspectiva..................................................................125 PROYECCIÓN PARALELA..................................................................................................... 127 Matemáticas de las Proyecciones Paralelas Ortogonales.....................................................128

5

Matemáticas de las Proyecciones Paralelas Oblicuas...........................................................130 Proyección CAVALLIER.......................................................................................................132 Proyección CABINET..........................................................................................................132

DETERMINACIÓN DE SUPERFICIES VISIBLES............................................137 SUPERFICIE VISIBLE........................................................................................................... 137 APROXIMACIONES............................................................................................................ 138 ALGORITMO DE PRECISIÓN DE OBJETO..............................................................................138 ALGORITMO DE PRECISIÓN DE IMAGEN.............................................................................139 DIFERENCIAS PRECISIÓN DE OBJETO VS PRECISIÓN DE IMAGEN.........................................140 CLASIFICACIÓN DE LOS ALGORITMOS................................................................................140 Algoritmo de z-buffer.............................................................................................................140 Algoritmo de A-buffer............................................................................................................143 Traza de rayos en superficies visibles.....................................................................................143 Algoritmo del pintor...............................................................................................................144 Árboles BSP............................................................................................................................146 Back-face culling.....................................................................................................................151

PROGRAMACION EN AUTOLISP......................................................................155 Comandos de programación.-............................................................................................ 159 Utilización de Listas.-......................................................................................................... 160 UTILIZACIÓN DE LAS FUNCIONES DEL TIPO GET..................................................................161 ESTRUCTURAS DE PROGRAMAS.-.......................................................................................164

Programación en DCL y AutoLISP.................................................................180 6

7

TEMA 1

8

9

INTRODUCCION A GRAFICAS POR COMPUTADORA OBJETIVOS El estudiante será capaz de distinguir las características de los dispositivos de salida Vectoriales y Raster. El estudiante conocerá los pasos a realizar para el proceso de obtención de una imagen.

CONTENIDO 

INTRODUCCION



APUNTES DE LA HISTORIA



APLICACIONES



TECNOLOGÍAS DE SALIDA



EL PROCESO DE OBTENCIÓN DE IMÁGENES

INTRODUCCION Lo que se verá en la materia: o o o o

“Imaging”: Cómo representar imágenes en 2D. “Modeling”: Cómo representar objetos en 3D y cómo construirlos “Animation”: Representación y control del cómo se pueden “mover” las cosas “Rendering”: Cómo construir imágenes en 2D a partir de modelos en 3D

10

APUNTES DE LA HISTORIA 1944: Computador Whirlwind (MIT) o o o o

Proyecto para entrenamiento en lanzamiento de bombas (líder: Jay Forrester) en tiempo real Primer computador con memoria de núcleo magnético T.R.C. para salida Impresora gráfica

1949: “Pistola de Luz” (Computador SAGE) o

SAGE: Semi-Automatic Ground Environment 11

o o o o o

Equivalente a cientos de estaciones de radares en USA y Canada Primera Red de Computadores a gran escala Operador dirigía acciones tocando con un “cañón luminoso” una pantalla Precursor del Lápiz de Luz Usa fotocelda

1956: TX-0 y TX-2 (MIT) o o o

Uso de transistores Terminal de Video Lápiz de Luz

1963: Sketchpad (tesis doctoral) o o o

Software para TX-2 Graficación Interactiva Estructuras de Datos Jerárquicas 12

o

Dispositivos de interacción(lápiz de luz)

o 1962: Society for Information Display (SID): Investigación, diseño, manufactura, aplicaciones y ventas de todo dispositivo de despliegue. 1963: DAC SYSTEM (General Motors) o o o o o

DAC: Design Augmented by Computers – primer sistema de dibujo para computador Software Interactivo gráfico para DAC-1 Usa Sketchpad Sistema comercial Uso en CAD y CAM (automóviles)

1964: Tableta gráfica (RAND Corp.)

13

1970: “Casco virtual”  

1º dispositivo de su género Ivan Sutherland

1972: “PONG” (ATARI) 

1º video-game computarizado 14



Versión comercial

1977: APPLE II (APPLE)  

Computador con texto y gráficos en la misma pantalla Computador personal

INICIOS DE LOS 80’  



Revolución de la microminiaturización de componentes Reducción gradual del costo del hardware o Procesadores o Memoria!!! o Monitores Popularidad de sistemas Raster

APLICACIONES Entretenimiento

–

Áreas o o

Cine: (Tron. Toy Story, etc) Televisión (Cortinillas, cabeceras, etc) 15

o

–

Juegos por computador

Técnicas o o o o

Animación Rendering Efectos especiales (ej. morphing) Interactividad

Diseño asistido por computador

16

–

CAD: Conjunto de herramientas gráficas que permiten diseñar prototipos y evaluarlos antes de ser construidos.

–

Áreas importantes: o o o o

– –

Diseño mecánico Arquitectura Circuitería eléctrica Circuitos impresos e integrados

Técnica habitual: diseño basado en primitivas constructivas. Otras posibilidades: o o o o o

Animaciones interactivas Sistemas multivista Presentación final realista Sugerencias constructivas Análisis del diseño con métodos de ingeniería u Conexión con el sistema de fabricación (CAM)

17

Visualización cientifíca y médica

–

Como característica común, el computador es usado para la visualización gráfica de gran cantidad de datos.

–

Áreas: o o o o o o

Medicina (Ej. Resonancias) Ingeniería (Ej. Esfuerzos en mecanismos) Física (Ej. Campos) Química (Ej. Interacción molecular) Matemáticas (Ej. Solución a ecuaciones) Topografía y oceanografía (Ej. Terrenos y corrientes) 18

–

Técnicas: o o o o

Codificación por color Curvas de nivel Visualización de volúmenes Generación de terrenos fractal

Simulación y entrenamiento

–

Áreas: o o o o

Simulación de conducción Simulación de procesos Entrenamiento Enseñanza

19

–

Técnicas: o o

–

Tiempo real Interactividad

Equipamiento: o

Generalmente se necesita un equipamiento específico para simular el objeto de entrenamiento (Ej. Simuladores de vuelo)

Gráficos de presentación

–

Uso de los gráficos para producción de ilustraciones de soporte a informes y trabajos. 20

–

Áreas de mayor uso: o o o o

–

Economía Estadística Matemáticas Administración y gestión

Técnicas principales: o o o o

Gráficos de línea Gráficos de barra Gráficos de tarta Superficies 3D

Creaciones artísticas

–

En este campo se producen imágenes con un fin artístico o comercial: o o o

–

Diseño de logotipos Bellas Artes Animaciones publicitarias

Técnicas y software: o o

Programas tipo “paintbrush” Programas de soporte a la animación 21

o o

Técnicas de tratamiento de imagen Técnicas de “rendering”

TECNOLOGÍAS DE SALIDA Tecnología de Salida: Vectorial Inicios: Uso de dispositivos Vectoriales (Caligráficos).

Se basan en la tecnología del Tubo de Rayos Catódicos (TRC o CRT)

22

El haz de electrones se mueve de acuerdo a comandos, de un punto a cualquier otro

23

Impacto del haz sobre el fósforo de la pantalla genera luz (no persistente) Requiere refrescamiento

Tecnología de Salida: Raster-Scan

• • •

El cañón emite electrones (cátodo). La intensidad del rayo se controla con la rejilla. El enfoque hace que los electrones describan una trayectoria convergente. 24

• • •

La deflexión hace apuntar el rayo a un punto de la pantalla. El rayo impacta contra el fósforo que emite luz. La emisión del fósforo decae rápidamente, por lo que se necesita un refresco del rayo sobre el punto.

Caracteristicas de la Tecnología de Salida: Raster-Scan

• • •

Usa TRC, Control de TRC diferente al vectorial Barrido continuado de electrones a superficie de despliegue (Modelo de TV) Barrido es “Discreto”: puntos en pantalla en vez de líneas llenas. De izquierda a derecha, y de arriba hacia abajo.

•

Lectura en el mismo orden que el despliegue

•

Señales de barrido en el TRC

25

• • • • •

No hay división de líneas impares y pares Fósforo de la pantalla con más persistencia Monitores de mejor calidad Monitor monocroma o Usa un tipo de fósforo Monitor color o Usa 3 distintos fósforos en pantalla o Composición de un pixel en color: tríada o stripe (tiras)

26

EL PROCESO DE OBTENCIÓN DE IMÁGENES

•

El proceso de obtención de imágenes se puede tratar desde dos puntos de vista:

•

o

La adquisición y tratamiento de una imagen para conseguir un modelo informático de la misma (tratamiento de imagen)

o

La representación gráfica en el computador del modelo informático de una imagen (síntesis de imagen)

El proceso de síntesis de una imagen (proceso de visualización) es el conjunto de operaciones (en 3D y en 2D) sobre un modelo informático de datos que resultan en una representación gráfica del mismo en un dispositivo físico de representación.

27

•

En general, se considera disponible: o Una descripción geométrica 3D de los objetos o Una descripción física asociada a los objetos o Un observador de la escena (conjunto de objetos) o Unas condiciones de iluminación o Un dispositivo físico de representación o Un objetivo a cumplir (realismo, rapidez, codificación por colores, etc.)

P.O.I. Recorrido de la Escena

•

La escena es el conjunto de objetos que se quieren representar además de su entorno (luces, observador, etc)

• •

La geometría de los objetos se describe con un modelo geométrico. El recorrido de la escena comprende los métodos de interrogación de las características de los objetos a visualizar.

• •

Sistema de coordenadas: sistema 3D particular de los objetos. Técnicas implicadas: 28

o o o o o

Modelado geométrico de superficies Modelado de sólidos Otros modelos (datos científicos, fractales, gramáticas, etc) Arquitecturas jerárquicas Algoritmos de recorrido e interrogación de estructuras de datos

P.O.I. Transformación del Modelo

•

Habitualmente es necesario colocar los objetos en la escena a partir de un sistema particular donde se definieron.

•

•

La transformación del modelo supone un cambio de sistema de coordenadas:

Técnicas implicadas: o Espacio afín (vectores y puntos) o Transformaciones afines (traslación, giro y escalado) o Matrices de transformación

P.O.I. Transformación de la Vista

• •

Toda visualización precisa de un observador. La transformación de la vista, una vez conocida la posición del observador, supone un cambio de coordenadas de la escena al sistema local de observación.

•

El sistema local de observación viene definido por el modelo de la vista.

29

•

Técnicas implicadas: o Modelado de la vista (cámara sintética, volumen de la vista, etc) o Transformaciones afines o Matrices de transformación

P.O.I. Recortado

•

El observador tiene un campo de visión determinado por el volumen de la vista. Lo que queda fuera del campo de visión debe ser eliminado de las posteriores operaciones: proceso de recortado.

•

En general, el recortado calcula la parte común entre dos entidades geométricas. En este caso, una de ellas es el volumen de la vista; la otra cada uno de los objetos.

•

Técnicas implicadas: o Cálculo de intersecciones o Criterios de interioridad o Concavidad y convexidad o Algoritmos de recortado de rectas o Algoritmos de recortado de polígonos

P.O.I. Eliminación de Caras Ocultas

•

En una escena, los objetos se tapan a sí mismos y entre sí, quedando siempre partes ocultas al observador.

•

Las partes ocultas deben ser eliminadas de posteriores operaciones: proceso de visibilidad. 30

•

El proceso de visibilidad es complejo, por lo que existen numerosas soluciones. Una clasificación simple: o Resolución del problema en el sistema de coordenadas de la escena o Resolución del problema apoyándose en el dispositivo (sistema de coordenadas de la imagen)

•

Técnicas implicadas: o Cálculo de normales o Ordenación o Algoritmos de visibilidad o Aceleración por coherencia

P.O.I. Proyección

• •

La representación en el dispositivo es en 2D, la escena está en 3D. La operación de paso de un sistema 3D a uno 2D se conoce como proceso de proyección.

•

La proyección de un punto 3D sobre un plano se calcula trazando una visual por el punto y calculando la intersección con el plano. 31

• •

Tipos de proyección: o Paralela: visuales paralelas o Perspectiva: visuales partiendo del observador (pto. de vista) Técnicas implicadas: o Sistemas proyectivos o Matrices de proyección o Transformación perspectiva-paralela

P.O.I. Transformación del Dispositivo

•

Los objetos proyectados están referidos a un sistema de coordenadas 2D procedente del de la vista.

•

Los objetos inscritos en un rectángulo del plano de proyecciones (ventana) se visualizarán en un rectángulo del dispositivo físico (marco).

•

El cambio de sistema de coordenadas del mundo real (vista) al del dispositivo se conoce como transformación del dispositivo.

•

Técnicas implicadas: o Cambio de sistemas de coordenadas 2D o Sistemas y transformaciones normalizados o Recortado en 2D o Isotropía y anisotropía o Ampliación (zoom) y deslizamiento

32

P.O.I. Conversión al Raster

•

Actualmente la representación de gráficos en un computador se realiza activando puntos discretos de una matriz: el raster.

• •

Las entidades gráficas a representar (primitivas) son de naturaleza continua. Al proceso de conversión de una entidad continua en un conjunto de puntos discretos se le denomina conversión al raster.

•

Técnicas implicadas: o Algoritmos de conversión de rectas o Algoritmos de conversión de curvas (circunferencias, elipses, etc) o Representación de texto gráfico o Relleno de áreas y polígonos o Técnicas de anti-aliasing

P.O.I. Iluminación

•

Conocidos los puntos que representan sobre el raster cada primitiva es necesario conocer el color que se debe asignar a cada punto.

•

El color depende de: o Las condiciones de iluminación del punto 3D sobre la superficie del objeto con el que se corresponde. o La forma (normal) de ese objeto en ese punto. 33

o o o

•

Las propiedades ópticas del material que está hecho. El acabado superficial (rugosidad). El color del objeto (del material o de la pintura).

Un modelo de iluminación tiene en cuenta todos los factores anteriores para calcular el color que se ve en ese punto,

•

Técnicas implicadas: o Modelos de iluminación y sombreado o Textura

P.O.I. Otras Operaciones

•

Interactividad

–

Generalmente, las aplicaciones de gráficos por computador deben responder a las acciones del usuario sobre la pantalla.

–

Una interacción comprende: o o o o

La acción del usuario: evento La comprensión del evento: mensaje La comunicación a la aplicación: rutina de respuesta (callback) La actualización del gráfico

•

Construcción del modelo

–

El modelo se construye: o o

–

A partir de una imagen real (adquisición) A partir de una idea (editor)

Los programas editores de modelos suelen estar integrados en aplicaciones de CAD.

•

Uso de librerías y herramientas 34

•

Todas las operaciones descritas se programan por medio de librerías gráficas (OpenGl, StarBase, etc.)

35

36

TEMA 2

37

38

PRIMITIVAS - RENDERING OBJETIVOS El estudiante será capaz de comprender los diferentes métodos de discretización. El estudiante podrá generar Líneas, circunferencias y elipses usando los algoritmos de generación de primitivas

CONTENIDO 

INTRODUCCIÓN



PRIMITIVAS GRAFICAS



ESPECIFICACIÓN DE UNA DISCRETIZACION



DIBUJO DE LÍNEAS RECTAS



ALGORITMOS BASICOS PARA CIRCULOS



ALGORITMOS PARA ELIPSES

INTRODUCCIÓN 

En los sistemas raster, las imágenes vienen definidas por la intensidad de sus pixels.

39





Los objetos presentes en la imagen se componen de primitivas simples (líneas, puntos) El sistema gráfico dibuja estas primitivas transformándolos en pixels -> Rasterización Los métodos de conversión deben ser lo más eficientes posible



La primitiva “Punto” es la más sencilla:



40

o o

Se coloca la intensidad deseada en la celda de memoria del frame buffer correspondiente Cuando el haz de electrones pase por esa línea horizontal (scan-line), emitirá al pasar por esa posición

C++ Builder, permite dibujar puntos en un lienzo, usando la instrucción Pixels void __fastcall TForm1::Button1Click(TObject *Sender) { Form1->Canvas->Pixels[10][10]=clBlue; }

 



A partir de este punto, se hará uso del modelo de dispositivo de raster. Para conseguir independencia de dispositivo, entonces, es necesario adoptar un conjunto de primitivas y establecer una serie de métodos que permitan representar dichas primitivas en nuestro dispositivo de raster satisfaciendo un conjunto de especificaciones. Convertir la imagen real a la imagen en la pantalla se denomina discretizacion.

PRIMITIVAS GRAFICAS 

Es muy difícil escoger un conjunto de primitivas graficas que sea adecuado para la presentación de todo tipo de entidades graficas. Sin embargo, el siguiente subconjunto en la práctica resulta suficiente: o Puntos.- Se especifican a partir de su localización y color.

41

o

o

o

Segmentos de recta.- Son esenciales para la mayor parte de las entidades. Se especifican a partir de un par de puntos que representan sus extremos. Circunferencias.- En algunos casos representar entidades curvadas con segmentos poligonales puede ser inadecuado o costoso, por lo que en la práctica las circunferencias o círculos se adoptan como primitivas. Se especifican con la posición de su centro y su radio. Polígonos.- Son indispensables para representar entidades sólidas. Se representan a partir de una secuencia de puntos que determina la poligonal de su perímetro.

ESPECIFICACIÓN DE UNA DISCRETIZACION 

Al elegir un método de discretizacion de una primitiva grafica, es indispensable contar con criterios que permitan evaluar y comparar las ventajas y desventajas de las distintas alternativas. Entre todas las especificaciones posibles, podemos mencionar las siguientes: o Apariencia.- Normalmente se espera que un segmento de recta tenga una “apariencia recta”, tampoco debe tener discontinuidades o puntos espureos, debe pasar por el primer y último puntos del segmento. o Simetría e invariancia geométrica.- Debe producir resultados equivalentes si se modifican algunas propiedades geométricas de la primitiva. Ejemplo no debe variar si dicho segmento se traslada o si es rotado, etc. o Simplicidad y velocidad de computo.- Los métodos tienden a no depender de estructuras complejas y a ser directamente implementadas en hardware especifico de baja complejidad

DIBUJO DE LÍNEAS RECTAS  

Para dibujar líneas rectas, habrá que calcular las posiciones intermedias entre los dos extremos Este problema no existía en las pantallas vectoriales o plotters 42

 



Sin embargo, las posiciones de los pixels son valores enteros, y los puntos obtenidos de la ecuación son reales -> existe un error (aliasing) A menor resolución, mayor es el efecto

Es necesario disponer de métodos para convertir primitivas en pixels de la forma más eficiente posible.

Consideraciones para el dibujo de rectas: 



Hay que calcular las coordenadas de los pixels que estén lo más cerca posible de una línea recta ideal, infinitamente delgada, superpuesta sobre la matriz de pixels. Las consideraciones que un buen algoritmo debe cumplir son: o La secuencia de pixels debe ser lo más recta posible o Las líneas deben dibujarse con el mismo grosor e intensidad independientemente de su inclinación o Las líneas deben dibujarse lo más rápido posible

EL ALGORITMO MÁS SENCILLO 43

•



La ecuación de una recta es y = mx + b o m es la pendiente o b es el corte con el eje y

Para cada valor de X desde x0 hasta x1, calculamos el valor de Y

• •

El algoritmo No es muy eficiente Cada paso requiere una multiplicación flotante, una suma y un redondeo

Dibuja una línea, usando la ecuación de la recta, solo para pendientes m d2 hay que pintar el pixel (xk+1, yk+1)

Si pk < 0  d1 < d2 hay que pintar el pixel (xk+1, yk)

52

•

La gran ventaja es que puede calcularse pk+1 a partir del anterior pk = 2 Δy xk - 2 Δx yk + c utilizando solamente ¡aritmética entera!.

En el paso k + 1, el parámetro de decisión se evalúa con base en la ecuación anterior como pk+1 = 2 Δy xk+1 - 2 Δx yk+1 + c Al sustraer la ecuación de la anterior pk obtenemos pk+1 - pk = 2 Δy xk+1 - 2 Δx yk+1 + c-2 Δy xk + 2 Δx yk - c pk+1 - pk = 2 Δy (xk+1 - xk) - 2 Δx( yk+1 - yk) Pero xk+1 = xk + 1, de manera que pk+1 = pk + 2 Δy – 2 Δx (yk+1 – yk) Donde el termino (yk+1 – yk) es 0 o 1, dependiendo del signo del parámetro pk.

Si pk > 0  d1 > d2 53

hay que pintar el pixel (xk+1, yk+1) entonces yk+1 = yk +1: pk+1 = pk + 2 Δy – 2 Δx (yk +1– yk) pk+1 = pk + 2 Δy – 2 Δx

Si pk < 0  d1 < d2 hay que pintar el pixel (xk+1, yk) encontes yk+1 = yk pk+1 = pk + 2 Δy – 2 Δx (yk – yk) pk+1 = pk + 2 Δy

•

El primer parámetro p0 se evalúa a partir de la ecuación pk 54

pk = Δx (2 (Δy / Δx) (xk + 1) - 2 yk + 2 b - 1) en la posición (x0,y0), sustituyendo con

b = y0 - m x0

y

m = Δy / Δx.

p0 = Δx (2( Δy / Δx)(x0 + 1) - 2 y0 + 2 (y0 - (Δy / Δx) x0) - 1) p0 = 2 Δy x0 + 2 Δy - 2 Δx y0 + 2 Δx y0 - 2 Δy x0 - Δx

•

donde se obtiene la siguiente ecuación: p0 = 2 Δy - Δx

• •

Si m > 1, intercambiamos las variables x e y Si m < 0, el cambio es similar

55

Dibuja un línea de un punto a otro usando el Algoritmo Bresenham void Bresenham(int x0, int y0, int x1, int y1) { int x, y, dx, dy, p; int incE, incNE, stepx, stepy; dx = (x1 - x0); dy = (y1 - y0); if (dy < 0) { dy = -dy; stepy = -1; } else stepy = 1; if (dx < 0) { dx = -dx; stepx = -1; } else stepx = 1; x = x0; y = y0; putpixel( x0, y0,BLUE);

56

if(dx>dy){ p = 2*dy - dx; incE = 2*dy; incNE = 2*(dy-dx); while (x != x1){ x = x + stepx; if (p < 0){ p = p + incE; } else { y = y + stepy; p = p + incNE; } putpixel( x, y,BLUE); } } else{ p = 2*dx - dy; incE = 2*dx; incNE = 2*(dx-dy); while (y != y1){ y = y + stepy; if (p < 0){ p = p + incE; } else { x = x + stepx; p = p + incNE; } putpixel( x, y,BLUE); } } }

ALGORITMO DEL PUNTO MEDIO

•

Bresenham, J.E. "Algorithm for Computer Control of a Digital Plotter". IBM Systems Journal, 4(1), 1965, 25-30. o Usa aritmética entera o Supone la pendiente (m) en el rango [0, 1] 57

o

•

• •

Parte del punto inferior-izquierdo al punto superior-derecho

Segmento de recta desde (x0, y0) a (xf, yf) o (x, y) : centro de un pixel o y + e : valor exacto de la ordenada de la recta o e : error (distancia) a la ordenada del pixel; e [-0.5, 0.5] o m : pendiente de la recta

Qué pixel pintar (x+1, y) o (x+1, y+1) ? Si y + e + m < y + 0.5 entonces se dibuja (x+1, y) o Para (x+1, y), el nuevo valor de ‘e’ será: o e = (y + e + m) – y o e = e+m

58

•

Si y + e + m >= y + 0.5 entonces se dibuja (x+1, y+1) o Para (x+1, y+1), el nuevo valor de ‘e’ será: o e = (y + e + m) – (y +1) o e = e + m -1

Algoritmo Punto Medio incio e = 0 y = y1 para x = x1 hasta x2 setPixel(x, y) si e + m < 0.5 e = e + m sino

59

y = y + 1 e = e + m –1 fin si fin para fin

•

Dado que m = dx / dy, entonces

e + m < 0.5 e + dy / dx < 0.5 / multiplicando por 2 * dx 2 * dx * e + 2 * dy < dx

•

Sustituyendo e * dx por e’, el test pasa a ser:

2(e’ + dy) < dx

•

Para la actualización del error tenemos:

ee+m ee+m-1

•

multiplicando por dx:

e * dx  e * dx + dy e * dx  e * dx + dy - dx

•

y sustituyendo e * dx por e’ :

e’  e’ + dy e’  e’ + dy - dx Algoritmo Punto Medio inicio

e’ = 0 y = y1 para x = x1 hasta x2 setPixel(x, y) si 2(e’ + dy) < dx e’ = e’ + dy sino

60

y = y + 1 e’ = e’ + dy –dx fin si fin para fin

Dibuja un línea de un punto a otro usando el Algoritmo Bresenham void PuntoMedio(int x0, int y0, int x1, int y1) { int x, y, dx, dy, p; int incE, incNE, stepx, stepy; dx = (x1 - x0); dy = (y1 - y0); if (dy < 0) { dy = -dy; stepy = -1; } else stepy = 1; if (dx < 0) { dx = -dx; stepx = -1; } else stepx = 1; x = x0; y = y0; putpixel( x0, y0,BLUE); if(dx>dy){ p = 0; incE = dy; incNE =(dy-dx); while (x != x1){ x = x + stepx; if (2*(p+dy) < dx){ p = p + incE; } else { y = y + stepy; p = p + incNE; } putpixel( x, y,BLUE); } } else{ p = 0; incE = dx;

61

incNE = (dx-dy); while (y != y1){ y = y + stepy; if (2*(p+dx) < dy){ p = p + incE; } else { x = x + stepx; p = p + incNE; } putpixel( x, y,BLUE); } }

}

ALGORITMOS BASICOS PARA CIRCULOS

•

Una circunferencia se define como un conjunto de puntos que se encuentran, en su totalidad, a una distancia r de una posición central (xc, yc).

•

Esta relación de distancia se expresa por medio del teorema de Pitagoras en coordenadas cartesianas como: (x - xc)2 + (y - yc) 2 = r2

ALGORITMO BÁSICO (COORDENADAS CARTESIANAS)

•

Círculo en el origen: X 2 + Y 2 = R 2

62

•

Se podría calcular para los puntos de una circunferencia a lo largo del eje x en pasos unitarios los valores correspondientes de y en cada posición como:

Algoritmo Coordenadas Cartesianas Funcion Circulo_cartesiana(int xc, yc, r) inicio y = R Para x= -r hasta r hacer y= sqrt(r*r-x*x) Pintar Pixel(x+xc, y+yc) Pintar Pixel(x+xc,-y+yc) x=x+1 Fin para fin

•

METODO INEFICIENTE o Se resuelve sólo 1/4 de círculo (SIMETRIA!!) o X se incrementa en 1 por cada paso o Y se obtiene de la ecuación del círculo:

63

o o o

Operaciones en Punto Flotante implicadas!! Contorno con brechas (X cercano a R) Dibujo de la circunferencia con huecos

Programa en C++ Builder usando Coordenadas Cartesianas void circulo_cartesiano(int xc, int yc, int r) { float x,y; for (x=-r;xCanvas->Pixels[x+xc][+y+yc]=clRed; Form1->Canvas->Pixels[x+xc][-y+yc]=clRed; }

}

COORDENADAS POLARES 

Otra manera de eliminar el espacio irregular consiste en calcular los puntos a



lo largo de la frontera circular utilizando las coordenadas polares r y . Al expresar la ecuación de la circunferencia en forma polar parametrica, se obtiene el par de ecuaciones



X = R COS 

64

 

 Y = R SEN  Donde:  varía entre 0º y 90º

No hay vacíos o brechas

Algoritmo Coordenadas Polares Funcion Circulo_polares(int xc, yc, r) inicio Para ang= 0 hasta 360 hacer x= r*cos(ang*3.141516/180) y= r*sin(ang*3.141516/180) Pintar Pixel(x+xc,-y+yc) ang = ang + 1.0/r Fin para fin

 

Método Ineficiente, por cálculos de Cos y Sen Para una frontera más continua, se puede establecer el tamaño de paso como 1/r. Esto hace que se tracen posiciones de pixel que están aproximadamente una unidad aparte

.

Programa en C++ Builder usando Coordenadas Polares void circulo_polar(int xc, int yc, int r) { float x,y,ang;

}

for (ang=0;angCanvas->Pixels[x+xc][+y+yc]=clRed; }

SIMETRÍA DE 8 LADOS 65



Consideración para ahorrar cálculos: o Aprovechar las simetrías de la circunferencia. Por cada punto hallado se pueden ubicar siete más. o En este caso la circunferencia está centrada en el origen, pero si no fuera así, basta con restarle a (x,y) las coordenadas del centro de la circunferencia, aplicar las simetrías y a los siete puntos sumarles las coordenadas del centro nuevamente.

Dado un punto de la Circunferencia, se pinta los 7 restantes por Simetria de los 8 lados SIMETRIA_8_LADOS(xc,yc,X,Y:integer); INICIO Pintar_Pixel ( X+xc, Y+yc); Pintar_Pixel ( Y+xc, X+yc); Pintar_Pixel ( Y+xc,-X+yc); Pintar_Pixel ( X+xc,-Y+yc); Pintar_Pixel (-X+xc,-Y+yc); Pintar_Pixel (-Y+xc,-X+yc); Pintar_Pixel (-Y+xc, X+yc); Pintar_Pixel (-X+xc, Y+yc); FIN



Sólo un segmento de 45 º se requiere para obtener el círculo completo 66



El valor de x que se requiere para obtener el círculo completo es desde 0 hasta llegar a y.

Programa en C++ Builder cono Coordenadas Cartesianas usando simetría de los 8 lados void simetria(int xc, int yc, int x, int y) { Form1->Canvas->Pixels[ x+xc][+y+yc]=clRed; Form1->Canvas->Pixels[ x+xc][-y+yc]=clRed; Form1->Canvas->Pixels[-x+xc][+y+yc]=clRed; Form1->Canvas->Pixels[-x+xc][-y+yc]=clRed; Form1->Canvas->Pixels[ y+xc][+x+yc]=clRed; Form1->Canvas->Pixels[ y+xc][-x+yc]=clRed; Form1->Canvas->Pixels[-y+xc][+x+yc]=clRed; Form1->Canvas->Pixels[-y+xc][-x+yc]=clRed;

} void circulo_cartesiano(int xc, int yc, int r) { float x,y; y=r; for (x=0;xCanvas->Pixels[ x+xc][+y+yc]=clRed; Form1->Canvas->Pixels[ x+xc][-y+yc]=clRed; Form1->Canvas->Pixels[-x+xc][+y+yc]=clRed; Form1->Canvas->Pixels[-x+xc][-y+yc]=clRed;

67

Form1->Canvas->Pixels[ y+xc][+x+yc]=clRed; Form1->Canvas->Pixels[ y+xc][-x+yc]=clRed; Form1->Canvas->Pixels[-y+xc][+x+yc]=clRed; Form1->Canvas->Pixels[-y+xc][-x+yc]=clRed;

} void circulo_polar(int xc, int yc, int r) { float x,y,ang; for (ang=0;ang 0  hay que pintar el pixel (xk+1, yk-1)  yk+1 = yk -1 reemplazando en pk+1 se tiene 71

pk+1 = pk + 2xk+1 + 1 + (( y k–1 ) 2–yk2) – (yk–1–yk) pk+1 = pk + 2xk+1 + 1 + (yk2–2yk+1 –yk2) – (yk–1–yk) pk+1 = pk + 2xk+1 –2yk+3

pk+1 = pk + 2xk –2yk+5 



Empezamos en el punto (0, R).

¿Cuánto vale p0?   



p0 = f (1, R- ½) = 12+ (R- ½) 2 -R2 p0 = 12+ R2 -2R ½ - ½ 2 -R2

p0 = 5/4 – R  no es entero!

Sin embargo, da igual. Podemos redondearlo, porque todos los incrementos son enteros, y sólo queremos utilizar el signo de pk, y no su valor

72

Dibuja una circunferencia con el Algoritmo del Punto Medio void CircleMidPoint(int xc, int yc, int r) { int x, y, p; x = 0; y = r; p = 1 - r; PlotPoint(xc,yc,x,y); /* se cicla hasta trazar todo un octante */ while (x < y) { x = x + 1; if (p < 0) p = p + 2*x + 3; else { y = y - 1; p = p + 2*(x - y) + 5; } PlotPoint(xc,yc,x,y); }

73

} Void Point( int xc, int yc, int x, int y) { Point(xc + x,yc + y); Point(xc - x,yc + y); Point(xc + x,yc - y); Point(xc - x,yc - y); Point(xc + y,yc + x); Point(xc - y,yc + x); Point(xc + y,yc - x); Point(,xc - y,yc - x); }

ALGORITMOS PARA ELIPSES 

Expresado de forma ambigua, una elipse es una circunferencia alargada.

 



 Una elipse se define como el conjunto de puntos en que la suma de las distancias desde dos posiciones fijas (focos) sea la misma para todos los puntos. Si las distancias de los dos focos desde cualquier punto P=(x,y) en la elipse se representan como d1 y d2, entonces la ecuación general de una elipse puede expresarse como

d1 + d2 = constante

74

ALGORITMO BASICO (Coordenadas Cartesianas) 

Las ecuaciones de la elipse se simplifican, en gran medida, si se orientan los ejes mayor y menor para alinearse con los ejes de las coordenadas, como se muestra en la siguiente figura.



El parámetro rx por convención designa el eje mayor y el parámetro ry designa el eje menor. La ecuación de la elipse puede expresarse en termino de las coordenadas del centro de la elipse y los parámetros rx y ry, como



Dibuja una Elipse con coordenadas cartesianas void elipse(int x0,int y0, int rx, int ry) { int x,y; for (x=-rx;xCanvas->Pixels[x+x0][y+y0]=clBlue; Form1->Canvas->Pixels[x+x0][-y+y0]=clBlue; }

75

}

ALGORITMO BASICO (Coordenadas Polares) 

 

Al utilizar las coordenadas polares r y , también es posible describir la elipse en posición estándar con las ecuaciones parametricas:

 x = xc + rx cos ß  y = yc + ry sin ß

Se puede aplicar consideraciones sobre la simetría para reducir aun mas los cálculos. Una elipse en posición estándar es simétrica entre cuadrantes, no es simétrica entre los dos octantes. De este modo que al calcular una posición de un píxel obtenemos por simetría las tres posiciones de los otros tres cuadrantes.

Dibuja una Elipse con coordenadas Polares void elipses(int x0,int y0, int rx, int ry) { int x,y; for (float ang=0;angCanvas->Pixels[x+x0][-y+y0]=clBlue;

76

}

}

ALGORITMO DEL PUNTO MEDIO  



El planteamiento que se utiliza aquí es similar a aquel empleado en el despliegue de una circunferencia. Dado los parámetros rx, ry, (xc, yc), se determina los puntos (x, y) para una elipse en posición estándar centrada en el origen y luego se altera los puntos, de modo que la elipse este centrada en (xc, yc). El método de punto medio para elipse se aplica a lo largo del primer cuadrante en dos partes, de acuerdo a una elipse con la pendiente rx < ry, como se muestra a continuación.

Dibuja una Elipse con el Algoritmo del Punto Medio void melipse(int xc,int yc,int rx,int ry, int color){ long double rx2 = rx * rx, ry2 = ry * ry; long double tworx2 = 2*rx2, twory2 = 2*ry2; long double p, x = 0, y = ry; long double px = 0, py = tworx2 * y;

77

puntose(xc,yc,x,y,color); //region 1 p=ceill( ry2 - ( rx2 * ry ) + ( 0.25 * rx2 ) ); while(px0){ y--; py-= tworx2 ; if(p>0) p+= rx2-py ; else{ x++; px+= twory2; p+= rx2-py+px; } puntose(xc,yc,x,y,color); } } void puntose(int xc,int yc,int x,int y, int c){ putpixel(xc+x,yc+y,c); putpixel(xc-x,yc+y,c); putpixel(xc+x,yc-y,c); putpixel(xc-x,yc-y,c); }

78

79

TEMA 3

80

81

TRANSFORMACIONES GEOMETRICAS EN 2-D OBJETIVOS El estudiante será capaz usar los diferentes algoritmos para la representación de gráficas en 2D. El estudiante será capaz realizar rotaciones, traslaciones y escalaciones en 2 D y representarlas en la pantalla.

CONTENIDO 

QUE ES UNA TRANSFORMACION?



COORDENADAS HOMOGENEAS



COMPOSICION DE TRANSFORMACIONES



OTRAS TRANSFORMACIONES



TRANSFORMACIÓN VENTANA-ÁREA DE VISTA

QUE ES UNA TRANSFORMACION?  



Una transformacion es una operacion que transforma o cambia una figura (line, drawing etc.) Hay varias formas basicas para cambiar una figura: o translacion (moving it) o rotacion (turning it round) o escalamiento (making it bigger or smaller). Hay otras: o Reflexion o Corte 82

C++ Builder, se hará uso de una vector para almacenar los datos de la imagen. int m=5; // numero de vertices float vert[10][3]={ { 0, 0, 0}, {100, 0, 1}, {100,100, 1}, { 0,100, 1}, { 0, 0, 1} }; void dibujar() { int xc=Form1->Width/2,yc=Form1->Height/2; int i; for(i=0;iCanvas->MoveTo(xc+vert[i][0],yc+vert[i][1]); else Form1->Canvas->LineTo(xc+vert[i][0],yc+vert[i][1]); } }

TRANSFORMACION EN 2D TRASLACION 83



Considere la flecha abajo. Podemos desear moverla desde la posición A a la posición B.



Podemos trasladar el punto (x, y) en el plano a las nuevas posiciones agregando cantidades de la traslación a las coordenadas de los puntos. Para cada punto P (x, y) que se moverá las unidades dx paralelas al eje de x y las unidades dy paralelas al eje de y, al nuevo punto P' (x', y'). La traducción tiene la forma siguiente:

84

X’ = Tx + X Y’ = Ty + Y

P’ = T + P Traslada los puntos al la nueva posición (dx,dy) void trasladar(float dx,float dy) { int i; for(i=0;i