Unidad II Graficación 2D

Trazas de una Recta

Son los puntos donde la recta se intercepta con los planos principales de proyección; se denominan:

Traza vertical: punto donde la recta se intercepta con el plano vertical de proyección. Generalmente se designa con la letra (V).

Traza horizontal: punto donde la recta se intercepta con el plano horizontal de proyección. Generalmente se designa con la letra (H).

Trazas de una recta

Determinación de las Trazas de una Recta

Las trazas de una recta se determinan, en doble proyección ortogonal, interceptando sus proyecciones con la línea de tierra

Determinación de las trazas de una recta

Polinomio

1.- Algoritmo de Línea DDA

El analizador diferenciador digital (DDA - Digital Differential Analyzer) es un algoritmo de conversión de rastreo que se basa en el cálculo ya sea de Dy o Dx por medio de las ecuaciones (4) o (5).

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

Tomemos una línea con pendiente positiva, si la pendiente | m | £ 1, se hace el muestreo en x en intervalos unitarios (Dx = 1 y Dy = m dado que m = Dy / Dx) y se calcula cada valor sucesivo de y como:

(6) yk+1 = yk+ m

El subíndice toma valores enteros a partir de 1 y aumenta a razón de 1 hasta alcanzar el valor final. Ya que m puede ser cualquier número real entre 0 y 1, los valores calculados de y deben redondearse al entero más cercano.

Para líneas con una pendiente | m | > 1, se revierten las funciones de x y y, o sea, se realiza un muestreo de y en intervalos unitarios (Dy = 1 y Dx = 1/m dado que m = Dy / Dx) y se calcula cada valor sucesivo de x como:

(7) xk+1 = xk+ 1/m

Las ecuaciones (6) y (7) se basan en la suposición de que las líneas deben procesarse del extremo izquierdo al derecho.

Si este procesamiento se revierte, entonces Dx o Dy serian -1, y yk+1 = yk - m o xk+1 = xk - 1/m

El procedimiento completo de dibujo sería el siguiente:

void Line(Display* display, Window win, GC gc, int x0, int y0, int x1, int y1)

{

float x, y, xs, ys;

int dx, dy, steps;

dx = x1 - x0;

dy = y1 - y0;

/* se asigna el punto de donde se comenzara a dibujar la línea */

x = x0;

y = y0;

/* verificar si la pendiente es mayor de x o y, para luego asignarla a steps */

if (abs(dx) > abs(dy))

steps = abs(dx);

else

steps = abs(dy);

/* se divide por la pendiente mayor, para dar xs o ys igual a 1 (o -1) */

if (steps == 0) {

XDrawPoint(display,win,gc,round(x),round(y));

fprintf(stderr,”this line is a point”);

return;

}

xs = dx/steps;

ys = dy/steps;

/* se cicla uno a la vez hasta llegar al numero de steps máximo */

for (i = 0; i <= steps; i++)

{

XDrawPoint(display,win,gc,round(x),round(y)); /* round(x) -> x+0.5 */

x = x + xs;

y = y + ys;

}

}

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 puede provocar que las posiciones del pixel 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 y fraccionarias, de forma que todos los cálculos se reduzcan a operaciones de enteros.

2.- 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 está más cerca según la trayectoria de la línea.

Consideremos el proceso de conversión para líneas con pendiente positiva 0 < m < 1.

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 más a la trayectoria de la línea de rastreo.

Si suponemos que se debe desplegar el pixel en (xk,yk), a continuación se necesita decidir que pixel se debe desplegar en la columna xk+1.

Las alternativas son los pixeles (xk+1,yk), y (xk+1,yk+1).

Al realizar el muestreo en la posición xk+1 designamos la separación de pixeles verticales de la trayectoria de la línea matemática como d1 y d2.

La coordenada de y en la línea matemática en la posición de la columna de pixel xk+1 se calcula como

(10) y = m (xk + 1) + b

Entonces

d1 = y - yk = m (xk + 1) + b – yk         y    d2 = (yk + 1) - y = yk + 1 - m (xk + 1) – b

void LineBres(Display* display, Window win, GC gc, int x0, int y0, int x1, int y1)

{

int x, y, dx, dy, xend, p, incE, incNE;

dx = abs(x1 - x0);

dy = abs(y1 - y0);

p = 2*dy - dx;

incE = 2*dy;

incNE = 2*(dy-dx);

/* determinar que punto usar para empezar, cual para terminar */

if (x0 > x1) {

x = x1;

y = y1;

xend = x0;

}

else {

x = x0;

y = y0;

xend = x1;

}

/* se cicla hasta llegar al extremo de la línea */

while (x <= xend)

{

XDrawPoint(display,win,gc,x,y);

x = x + 1;

if (p < 0)

p = p + incE

else {

y = y + 1;

p = p + incNE;

}

}

}

3.- Algoritmos de Generación de Circunferencias

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 Pitarrosa en coordenadas cartesianas como

(24) (x - xc)2 + (y - yc) 2 = r2

 Algoritmo Básico

Se podría utilizar una ecuación para calcular la posición de los puntos de una circunferencia pasando a lo largo del eje de las x en pasos unitarios de xc - r a xc + r y calcular los valores correspondientes de y en cada posición como

(25)                 

Un método para dibujar el círculo es aprovechar la simetría de los cuadrantes, dibujando solo uno y trazando los puntos simétricos en los demás cuadrantes.

Para el primer cuadrante se incrementaría x de 0 a r en pasos de 1, resolviendo para cada y positiva.

El trazo para un círculo con radio de 10, centrado en (0,0), utilizando este algoritmo básico, se muestra a continuación:

x                                         (x,y)

0      100                   10               (0,10)

1       99                   9.95             (1,10)

2       96                   9.80             (2,10)

3       91                   9.54             (3,10)

4       84                   9.17             (4,9)

5       75                   8.66             (5,9)

6       64                   8                  (6,8)

7       51                   7.14             (7,7)

8       36                   6                  (8,6)

9      19                    4.36             (9,4)

10    0                      0                  (10,0)

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 0.

Al expresar la ecuación de la circunferencia en forma polar paramétrica, se obtiene el par de ecuaciones

(26) x = xc + r cos0, y = yc + r sin0

/* draw symmetry points */

XDrawPoint(display,win,gc,xc + x,yc + y);

XDrawPoint(display,win,gc,xc - x,yc + y);

XDrawPoint(display,win,gc,xc + x,yc - y);

XDrawPoint(display,win,gc,xc - x,yc - y);

XDrawPoint(display,win,gc,xc + y,yc + x);

XDrawPoint(display,win,gc,xc - y,yc + x);

XDrawPoint(display,win,gc,xc + y,yc - x);

XDrawPoint(display,win,gc,xc - y,yc - x);

}

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 + 1;

else {

y = y - 1;

p = p + 2*(x - y) + 1;

}

PlotPoint(xc,yc,x,y);

}

}