AnteriorPosterior

Ampliación 2: Gráficos sin BGI (3)

  Curso: Curso de Pascal, por Nacho Cabanes

Curso de Pascal. Ampliación 2: Gráficos sin BGI (3)

Vimos cómo cambiar a un cierto modo gráfico y como dibujar un punto de dos formas: a través de la BIOS como método general, y accediendo a la memoria de video en el caso particular del modo 320x200 en 256 colores de las tarjetas VGA y MCGA.

Hoy vamos a ver cómo dibujar líneas y otras figuras sencillas.

Supongo que casi todos los que nos paseamos por aquí tenemos el suficiente nivel en matemáticas como para pensar una forma de dibujar una recta: aplicando la ecuación de la recta "tal cual".  La recta que pasa por dos puntos (x1,y1) (x2,y2) tiene como ecuación:

   x-x1      y-y1
 ------- = -------
  x2-x1     y2-y1

que podríamos recolocar para escribir una variable en función de la otra.  Por ejemplo, y en función de x:

           y2-y1
 y = y1 + ------- (x-x1)
           x2-x1
 

Esto funciona, claro.  Pero se puede optimizar mucho.  ¿Por qué?  Porque para cada calcular la coordenada y de cada punto estamos haciendo 3 restas, una suma, una multiplicación y una división.  La suma y la resta son "menos malas" ;-)  pero la multiplicación y aun más la división son operaciones lentas.

La primera mejora "casi evidente" viene si nos damos cuenta de que realmente no hay tal división:

    y2-y1          Conocemos y2, y1, x2, x1 => Esta división siempre
   -------         vale lo mismo => es una constante.
    x2-x1

Lo hemos convertido en algo parecido a:

 y = y1 + c (x-x1)

Pero aun así nos queda la multiplicación, y esta no se ve tan claro la forma de eliminarla...

 ¡ Pero para eso están los inteligentes matemáticos, que se estrujan el coco por nosotros !   :-)

Así es: existen algoritmos incrementales, que emplean sumas en vez de multiplicaciones.  Posiblemente el más usado sea el de Bresenham, que es el que voy a poner a continuación:

 (Esta rutina no es mía, es de dominio público y está tomada de los
 SWAG, unas recopilaciones muy interesantes de fuentes de Pascal; en
 concreto, esta colaboración es de Sean Palmer, que yo apenas he
 comentado y poco más).




 
{Línea, por algoritmo de Bresenham}
 
procedure linea(x, y, x2, y2 : integer);

var
  d,
  dx, dy,             { Salto total según x e y }
  ai, bi,

  xi, yi              { Incrementos: +1 ó -1, según se recorra }
          : integer;
begin
  if (x < x2) then    { Si las componentes X están ordenadas }

  begin
    xi := 1;          { Incremento +1 }
    dx := x2 - x;     { Espacio total en x }

  end
  else                { Si no están ordenadas }
  begin
    xi := - 1;        { Increm. -1 (hacia atrás) }

    dx := x - x2;     { y salto al revés (negativo) }
  end;
  if (y < y2) then    { Análogo para las componentes Y }

  begin
    yi := 1;
    dy := y2 - y;
  end

  else
  begin
    yi := - 1;
    dy := y - y2;
  end;
  plot(x, y);         { Dibujamos el primer punto }

  if dx > dy then     { Si hay más salto según x que según y }
  begin               { (recta más cerca de la horizontal) }
    ai := (dy - dx) * 2;   { Variables auxiliares del algoritmo }

    bi := dy * 2;          { ai y bi no varían; d comprueba cuando }
    d  := bi - dx;         { debe cambiar la coordenada y }

    repeat
      if (d >= 0) then     { Comprueba si hay que avanzar según y }
      begin

        y := y + yi;       { Incrementamos Y como deba ser (+1 ó -1) }
        d := d + ai;       { y la variable de control }

      end
      else
        d := d + bi;       { Si no varía y, d sí lo hace según bi }
      x := x + xi;         { Incrementamos X como corresponda }

      plot(x, y);          { Dibujamos el punto }
    until (x = x2);   { Se repite hasta alcanzar el final }

  end
  else                { Si hay más salto según y que según x }
  begin               { (más vertical), todo similar }
    ai := (dx - dy) * 2;
    bi := dx * 2;
    d  := bi - dy;
    repeat

      if (d >= 0) then
      begin
        x := x + xi;
        d := d + ai;
      end

      else
        d := d + bi;
      y := y + yi;
      plot(x, y);
    until (y = y2);
  end;

end; 
 


 

En este algoritmo, que está expresado de forma genérica, basta sustituir el "Plot(x,y)" por nuestra propia rutina de dibujo de puntos, como el PonPixel(x,y,color).

Por si alguien se ha dado cuenta de que en este algoritmo hay una multiplicación de todas formas (por 2, en la definición de ai y bi), y que puede realmente no haber ahorro, esto no es cierto del todo...

¿Por qué?   Pues porque las mutiplicaciones por múltiplos de dos se pueden codificar como "desplazamientos" o "rotaciones" de bits, en este caso SHL 1.  De hecho, esto lo hace automáticamente el compilador de TP7 en muchos casos.

Y aun así, se trata simplemente de que se vea el algoritmo.  Porque a nadie se le escapa que x*2 es lo mismo que x+x, y esta última operación puede ser más rápida, pero también menos legible.

Por cierto, las órdenes como   x := x + xi   se pueden escribir también mediante la orden "incrementar":  inc(x,xi), lo que además ayuda al compilador a generar un código más eficiente.


Para curiosos que quieran experimentar un poco, el siguiente algoritmo (también una contribución de Sean Palmer) dibuja una elipse rellena (o un círculo, claro):

 
{filled ellipse}
procedure disk(xc,  yc,  a,  b : integer);

var
  x, y      : integer;
  aa, aa2,
  bb, bb2,

  d, dx, dy : longint;
begin
  x   := 0;
  y   := b;
  aa  := longint(a) * a;
  aa2 := 2 * aa;
  bb  := longint(b) * b;
  bb2 := 2 * bb;
  d   := bb - aa * b + aa div 4;
  dx  := 0;
  dy  := aa2 * b;
  vLin(xc, yc - y, yc + y);
  while (dx < dy) do

  begin
    if (d > 0) then
    begin
      dec(y);
      dec(dy, aa2);
      dec(d, dy);
    end;
    inc(x);
    inc(dx, bb2);
    inc(d, bb + dx);
    vLin(xc - x, yc - y, yc + y);
    vLin(xc + x, yc - y, yc + y);
  end;
  inc(d, (3 * (aa - bb) div 2 - (dx + dy)) div 2);
  while (y >= 0) do

  begin
    if (d < 0) then
    begin
      inc(x);
      inc(dx, bb2);
      inc(d, bb + dx);
      vLin(xc - x, yc - y, yc + y);
      vLin(xc + x, yc - y, yc + y);
    end;
    dec(y);
    dec(dy, aa2);
    inc(d, aa - dy);
  end;

end; 
 


 

Comentarios: Este procedimiento está transcrito tal y como aparecía en los SWAG.  Que cada uno lo estudie por su cuenta si quiere y se atreve. Sólo un par de pistas: INC incrementa una variable y DEC la decrementa. VLIN (x,y1,y2) es un procedimiento que nosotros no hemos definido -deberes, JeJe- y que dibuja una línea vertical entre los puntos (x,y1) y (x,y2).

¿Y por qué se usa VLIN en vez del procedimiento anterior para dibujar líneas?  Pues por rapidez: normalmente lo más rápido es dibujar una línea horizontal, ya que todos los puntos se encuentran seguidos en la memoria de pantalla. El siguiente caso es el de una línea vertical: cada punto está 320 bytes después del anterior en la memoria de pantalla.  En el caso general, estos incrementos varían, y hay que usar algoritmos más genéricos y más difíciles de optimizar.

Algunas optimizaciones.

No quiero meterme de lleno en rotaciones y similares.  Al fin y al cabo, esto no es un curso de programación gráfica, sino un tema más de un curso de Pascal que tampoco pretende ser tan profundo como pueda serlo un libro.  Mi intención es más abrir las puertas, para que quien luego quiera adentrarse más lo tenga medianamente fácil.

Pero considero que hay aspectos importantes en la programación y que a veces no se tienen en cuenta.

Vamos a empezar por hacer un programita que haga rotar una línea, como si fueran una aguja de un reloj.  Para ello aprovecharemos parte de lo que vimos en el apartado anterior y parte de éste, ya aplicado...

 {--------------------------}
 {  Ejemplo en Pascal:      }
 {                          }

 {    Líneas que rotan, en  }
 {    memoria de pantalla:  }
 {    Versión para TP7      }
 {    GRB3.PAS              }
 {                          }
 {  Este fuente procede de  }

 {  CUPAS, curso de Pascal  }
 {  por Nacho Cabanes       }
 {                          }
 {  Comprobado con:         }
 {    - Turbo Pascal 7.0    }
 {--------------------------}

 
 program GrB3;
 
 uses dos, crt;                 { Usaremos interrupciones,
                                  keypressed y delay }
 
 const NumPuntos = 10000;       { Número de puntos que dibujaremos }

 
 var
   regs: registers;            { Para acceder a los registros, claro }
   bucle: real;                { Para bucles, claro }

   tecla: char;                { La tecla que se pulse }
 
 procedure ModoPantalla( modo: byte );
                               { Cambia a un modo dado }

 begin
   regs.ah := 0;               { Función 0 }
   regs.al := modo;            { El modo indicado }

   intr($10,regs);             { Interrupción de video }
 end;
 
 procedure PonPixel(x,y: word; color: byte);      { Dibuja Pixel }

 begin
   Mem[$A000 : y * 320 + x] := color;
 end;

 
 procedure Linea(x, y, x2, y2 : word; color: byte);
 var

   d,
   dx, dy,             { Salto total según x e y }
   ai, bi,

   xi, yi              { Incrementos: +1 ó -1, según se recorra }
           : integer;
 begin
   if (x < x2) then    { Si las componentes X están ordenadas }

   begin
     xi := 1;          { Incremento +1 }
     dx := x2 - x;     { Espacio total en x }

   end
   else                { Si no están ordenadas }
   begin
     xi := - 1;        { Increm. -1 (hacia atrás) }

     dx := x - x2;     { y salto al revés (negativo) }
   end;
   if (y < y2) then    { Análogo para las componentes Y }

   begin
     yi := 1;
     dy := y2 - y;
   end

   else
   begin
     yi := - 1;
     dy := y - y2;
   end;
   PonPixel(x, y,color);   { Dibujamos el primer punto }

   if dx > dy then     { Si hay más salto según x que según y }
   begin               { (recta más cerca de la horizontal) }
     ai := (dy - dx) * 2;   { Variables auxiliares del algoritmo }

     bi := dy * 2;          { ai y bi no varían; d comprueba cuando }
     d  := bi - dx;         { debe cambiar la coordenada y }

     repeat
       if (d >= 0) then     { Comprueba si hay que avanzar según y }
       begin

         y := y + yi;       { Incrementamos Y (+1 ó -1) }
         d := d + ai;       { y la variable de control }

       end
       else
         d := d + bi;       { Si no varía y, d sí lo hace según bi }
       x := x + xi;         { Incrementamos X como corresponda }

       PonPixel(x, y, color);          { Dibujamos el punto }
     until (x = x2);   { Se repite hasta alcanzar el final }

   end
   else                { Si hay más salto según y que según x }
   begin               { (más vertical), todo similar }
     ai := (dx - dy) * 2;
     bi := dx * 2;
     d  := bi - dy;
     repeat

       if (d >= 0) then
       begin
         x := x + xi;
         d := d + ai;
       end

       else
         d := d + bi;
       y := y + yi;
       PonPixel(x, y, color);
     until (y = y2);
   end;
 end;

 
 begin
   ModoPantalla($13);    { Modo 320x200x256 }
   bucle := 0;           { Empezamos en 0 __RADIANES__ }

   repeat
     linea(160,100,      { Línea desde el centro de la pantalla }
       160 + round(60*cos(bucle)),  { Extremo en un círculo }

       100 + round(40*sin(bucle)),
       0);                          { Color negro (borrar) }

     bucle := bucle + 0.1;          { Siguiente posición }
 
     linea(160,100,       { Otra línea, pero ahora blanca }

       160 + round(60*cos(bucle)), 100 + round(40*sin(bucle)),

       15);
     delay(25);           { Esperamos 25 milisegundos }
   until keyPressed;      { Seguimos hasta que se pulse una tecla }
   tecla := ReadKey;      { Quitamos esa tecla del buffer del teclado }

   ModoPantalla(3);       { Y volvemos a modo texto }
 end.
 



Esa combinación de radio*cos(angulo) y radio*sin(angulo) es la que nos da las coordenadas de cada punto de una circunferencia de cierto radio, es la que se suele usar para calcular rotaciones en el plano con un cierto radio.  No necesitamos gran velocidad, y de hecho hemos puesto un retardo de 25 milisegundos entre línea y línea.




La versión para TMT de este programita sería:

 {--------------------------}
 {  Ejemplo en Pascal:      }
 {                          }

 {    Líneas que rotan, en  }
 {    memoria de pantalla:  }
 {    Versión para TMT      }
 {    GRB3T.PAS             }
 {                          }
 {  Este fuente procede de  }

 {  CUPAS, curso de Pascal  }
 {  por Nacho Cabanes       }
 {                          }
 {  Comprobado con:         }
 {    - Tmt Pascal Lt 1.00  }
 {--------------------------}

 
 program GrB3;
 
 uses dos, crt, use32;          { Usaremos interrupciones,
                                  keypressed y delay }

 
 const NumPuntos = 10000;       { Número de puntos que dibujaremos }
 
 var
   regs: registers;            { Para acceder a los registros, claro }

   bucle: real;                { Para bucles, claro }
   pantalla: array [0..199,0..319]  of byte

     absolute $A0000;          { Pues la pantalla ;-) }
 
   tecla: char;                { La tecla que se pulse }
 
 procedure ModoPantalla( modo: byte );
                               { Cambia a un modo dado }

 begin
   regs.ah := 0;               { Función 0 }
   regs.al := modo;            { El modo indicado }

   intr($10,regs);             { Interrupción de video }
 end;
 
 procedure PonPixel(x,y: word; color: byte);      { Dibuja Pixel }

 begin
   Pantalla[y, x] := color;
 end;
 
 procedure Linea(x, y, x2, y2 : word; color: byte);
 var

   d,
   dx, dy,             { Salto total según x e y }
   ai, bi,

   xi, yi              { Incrementos: +1 ó -1, según se recorra }
           : integer;
 begin
   if (x < x2) then    { Si las componentes X están ordenadas }

   begin
     xi := 1;          { Incremento +1 }
     dx := x2 - x;     { Espacio total en x }

   end
   else                { Si no están ordenadas }
   begin
     xi := - 1;        { Increm. -1 (hacia atrás) }

     dx := x - x2;     { y salto al revés (negativo) }
   end;
   if (y < y2) then    { Análogo para las componentes Y }

   begin
     yi := 1;
     dy := y2 - y;
   end

   else
   begin
     yi := - 1;
     dy := y - y2;
   end;
   PonPixel(x, y,color);   { Dibujamos el primer punto }

   if dx > dy then     { Si hay más salto según x que según y }
   begin               { (recta más cerca de la horizontal) }
     ai := (dy - dx) * 2;   { Variables auxiliares del algoritmo }

     bi := dy * 2;          { ai y bi no varían; d comprueba cuando }
     d  := bi - dx;         { debe cambiar la coordenada y }

     repeat
       if (d >= 0) then     { Comprueba si hay que avanzar según y }
       begin

         y := y + yi;       { Incrementamos Y (+1 ó -1) }
         d := d + ai;       { y la variable de control }

       end
       else
         d := d + bi;       { Si no varía y, d sí lo hace según bi }
       x := x + xi;         { Incrementamos X como corresponda }

       PonPixel(x, y, color);          { Dibujamos el punto }
     until (x = x2);   { Se repite hasta alcanzar el final }

   end
   else                { Si hay más salto según y que según x }
   begin               { (más vertical), todo similar }
     ai := (dx - dy) * 2;
     bi := dx * 2;
     d  := bi - dy;
     repeat

       if (d >= 0) then
       begin
         x := x + xi;
         d := d + ai;
       end

       else
         d := d + bi;
       y := y + yi;
       PonPixel(x, y, color);
     until (y = y2);
   end;
 end;

 
 begin
   ModoPantalla($13);    { Modo 320x200x256 }
   bucle := 0;           { Empezamos en 0 __RADIANES__ }

   repeat
     linea(160,100,      { Línea desde el centro de la pantalla }
       160 + round(60*cos(bucle)),  { Extremo en un círculo }

       100 + round(40*sin(bucle)),
       0);                          { Color negro (borrar) }

     bucle := bucle + 0.1;          { Siguiente posición }
     linea(160,100,       { Otra línea, pero ahora blanca }

       160 + round(60*cos(bucle)), 100 + round(40*sin(bucle)),

       15);
     delay(25);           { Esperamos 25 milisegundos }
   until keyPressed;      { Seguimos hasta que se pulse una tecla }
   tecla := ReadKey;      { Quitamos esa tecla del buffer del teclado }

   ModoPantalla(3);       { Y volvemos a modo texto }
 end. 
 

(Sólo cambia la forma de acceder a la pantalla y el procedimiento "PonPixel).


Pero imaginad que estamos rotando una figura complicada, con cientos de puntos, y que además no trabajamos en el plano, sino en el espacio, con lo que tenemos rotaciones en torno a tres ejes (teneis un ejemplo después de la ampliación 5: ensamblador desde Turbo Pascal que, dicho sea de paso, cuenta cómo corregir un fallo del algoritmo que he puesto antes para dibujar líneas).

Si experimentais, incluso complicando este ejemplillo, vereis que a medida que aumenta la complejidad de lo que hay que rotar, se va haciendo más evidente la lentitud de este método.

Se diría que las demos que a todos nos asombran no pueden estar hechas así, ¿verdad?  Pues el truco se llama tablas.  Nada más y nada menos. En vez de calcular cada pasada el coseno de 10 grados, se calcula una vez este valor al principio del programa y se guarda en un ARRAY, con lo cual no accederemos como "cos(10)" sino como "coseno[10]".

Esa es la primera mejora, pero aun hay más.  Multiplicar por números reales es lento, así que la segunda mejora que se nos puede ocurrir es trabajar con números enteros.  ¿Pero cómo, si el seno y el coseno van de 0 a 1?  Pues multiplicándolos por 100 o 256, por ejemplo, antes de guardarlos en nuestro array.  Al fin y al cabo, en nuestra pantalla todas las coordenadas son enteras.  Basta tenerlo en cuenta a la hora de multiplicar por el radio para que no se nos salga de la pantalla... ;-) Además, es mejor usar números como 256 o 128 que 100 o 200.  ¿Por qué? Por lo que ya hemos comentado antes: las multiplicaciones y divisiones por múltiplos de dos se pueden expresar como rotaciones de bits (SHL y SHR), mucho más rápidas que una multiplicación en general.

(Hay un ejemplo de todo esto como ampliación al curso: entre los fuentes de ejemplo, hablando de rotaciones en 3D).

 Y eso de las tablas se usa en más de una ocasión cuando queremos optimizar rutinas gráficas.  Algo tan sencillo como nuestro "PonPixel" contiene una multiplicación.  ¿Y si dibujamos 50.000 puntos, hacemos 50.000 multiplicaciones?  Se puede evitar con un nuevo array, de modo que en vez de hacer "y*320" se escriba "Por320[y]".

Incluso efectos cómo ese de una lente o una bola de cristal que pasa por encima de un dibujo, y se ve a través suyo el fondo deformado, suelen estar basados en tablas para mayor rapidez...

Pero todo eso y más lo dejo para que jugueis.  En el próximo apartado vemos un poco cómo manejar la paleta de colores, y damos por terminada la parte del curso relativa a gráficos.
 

Actualizado el: 09-07-2009 16:50

AnteriorPosterior