Home

Papers

Reports

Projects

Code Fragments

Dissertations

Presentations

Posters

Proposals

Lectures given

Course notes

2. Bitmasks >>

1. Fixed Point Arithmetic & DDA's to draw Lines Werner Van Belle1 - werner@yellowcouch.org, werner.van.belle@gmail.com 1- Programming Technology Lab (PROG) Department of Computer Science (DINF) Vrije Universiteit Brussel (VUB); Pleinlaan 2; 1050 Brussel; Belgium Abstract :  In this exercise we look into fixed point arithmetic to draw lines fast and correct. This lecture was given in 1998-1999 and 1999-2000 Reference:  Werner Van Belle; Fixed Point Arithmetic & DDA's to draw Lines; Files: drawline3.c, drawline6.c, drawline1.c, drawline4.c, drawline5.c, drawline2.c

Praktisch

We werken onder linux, als taal wordt standaard C gebruikt. De vga library is een aangepaste svgalib. Om in te loggen: username: gfx, password: <none>. Onderstaande minimale C-code initialiseert een 320x200x256 grafische mode:

Compileren met: gcc init.c -lvga

#include "vga.h"
       void main(void) {vga_setmode(G320x200x256);}

In deze schermmode wordt elke pixel voorgesteld door 8 bits. (Dus een getal van 0 tot 255). Hoe een bepaalde pixelwaarde er in de praktijk uitwiet wordt bepaald door een vector die elke pixelwaarde mapt op een rood, groen en blauw waarde. Deze vector kan verandert worden met de functie setpalette.

vga_setpalette(int index,int rood,int groen,int blauw)

Rood, groen en blauw kunnen varieren van 0 tot 63.
Om bijvoorbeeld de achtergrondkleur van het scherm aan te passen naar blauw, gebruik men

vga_setpalette(0,0,0,63)

Deze kunnen we nu geleidelijk aan naar zwart laten uitfaden door

For(int I;I>=0; I--) vga_setpalette(0,0,0,I)

Oef 1: coordinaten

Eens deze schermmode geinitialiseerd is heeft men beschikking tot een grafisch geheugen waarbinnen men naar willekeur kan schrijven. Het adres van dit geheugen is te vinden in char *graph_mem. De memorymapping naar het scherm ziet er als volgt uit:

Schrijf een functie putpixel(int x, int y, int color) die een pixel van de kleur color op de gegeven plaats zet.

Oef 2: Tekenen van een lijn

De formule van een lijn tussen (x1,y1) en (x2,y2) is gegeven als volgt

Schrijf een functie drawline(float x1, float y1, float x2, float y2, int color) die een lijn tekent tussen de gegeven coordinaten. De lijn moet juist getekend worden in de 4 kwadranten.

Oef 3: Tekenen van een lijn: fixed point

Vroeger waren floating points vaak een last omdat de processor veel trager was in het omgaan met floating points dan met integers.

3.1: Verander in uw algoritme al de floats door integers en aanschouw het resultaat.

Het is duidelijk dat het algoritme fout gaat omdat de nauwkeurigheid van de bewerkingen te klein is. Bekijk het volgende:

Als we met integers werken en als y-waarde 2 pakken dan krijgen we als x-waarde 0. Om dit te vermijden verhogen we de nauwkeurigheid door de beide termen van de gelijkheid te vermenigvuldigen met een factor 10.

Als we nu nogmaals proberen x te berekenen zien we dat 10x=(20/6)*8=24. Dus dat x uiteindelijk gelijk is aan 2. Nog steeds fout maar toch al dichterbij. Door de nauwkeurigheid van de tussentijdse getallen voldoende op te drijven zullen we uiteindelijk een juist resultaat bekomen.

3.2: Pas dergelijke methode toe op de formule voor een lijn en integreer ze in het gegeven algoritme. Zorg dat de nauwkeurigheid zelf gekozen kan worden. De parameters doorgegeven aan putpixel en drawline blijven in schermcoordinaten uitgedrukt, de rest mag veranderen.

Oef 4: Tekenen van een lijn: DDA

Een nadeel aan het gegeven algoritme is het feit dat er vermenigvuldigingen in voorkomen. Vermenigvuldigingen vragen over het algemeen massas meer tijd dan optellingen en aftrekkingen.

De truc om deze te vermijden is dat we door af te leiden een groot aantal vermenigvuldigen verliezen. (De afgeleide van 10x is 10 zoals algemeen geweten). (Vandaar de naam DDA: Digital Diferential Analyzer)

In plaats van de y-waarde lijn te berekenen op gegeven x-coordinaten, starten we op coordinaat x1 en verhogen deze tot we aan x2 zitten. Parallel daarmee verhogen we y (gestart van y1) met de afgeleide van de rechte. Schrijf een lijnalgoritme, gebruik makend van floating points die gebruikt maakt van deze techniek.

Oef 5: DDA + Fixed Point

Schrijf een lijnalgoritme waarbij de nauwkeurigheid van de decimalen 8 bits is, dat door middel van een DDA herwerkt is naar een sneller algoritme en dat lijnen kan tekenen in de 4 kwadranten.

Solutions

DrawLine1

#include "vga.h"

/* floats, mathematisch */
void putpixel(int x, int y)
{
   graph_mem[x+y*0]=5;
   printf("%d,%d  ",x,y);
}

void drawline(int x1, int y1, int x2, int y2)
{
   float x,y,dx,dy,m;
   dx=x2-x1;
   dy=y2-y1;
   if (abs(dx)>abs(dy))
     {
	if (x1>x2)
	  {
	     drawline(x2,y2,x1,y1);
	     return;
	  }
	m=dy/dx;
	for(x=x1;x<x2;x++)
	  {
	     y=m*(x-x1)+y1;
	     putpixel(x,y);
	  }
     }
   else
     {
	if(y1>y2)
	  {
	     drawline(x2,y2,x1,y1);
	     return;
	  }
	m=dx/dy;
	for(y=y1;y<y2;y++)
	  {
	     x=m*(y-y1)+x1;
	     putpixel(x,y);
	  }
     }
}

void main(void)
{
   vga_setmode(G320x200x256);
   drawline(0,0,0,0);
   sleep(3);
   drawline(0,0,0,0);
   sleep(3);
   drawline(0,0,0,0);
   sleep(3);
   drawline(0,0,0,0);
   sleep(3);
}

DrawLine2

#include "vga.h"

/* int, mathematisch */
void putpixel(int x, int y)
{
   graph_mem[x+y*0]=5;
   printf("%d,%d  ",x,y);
}

void drawline(int x1, int y1, int x2, int y2, int detail)
{
   int x,y,dx,dy,m,q;
   dx=(x2-x1);
   dy=(y2-y1);
   if (abs(dx)>abs(dy))
     {
	if (x1>x2)
	  {
	     drawline(x2,y2,x1,y1,detail);
	     return;
	  }
	m=detail*dy/dx;
	q=y1*detail;
	for(x=x1;x<x2;x++)
	  {
	     y=m*(x-x1)+q;
	     putpixel(x,y/detail);
	  }
     }
   else
     {
	if(y1>y2)
	  {
	     drawline(x2,y2,x1,y1,detail);
	     return;
	  }
	m=detail*dx/dy;
	q=x1*detail;
	for(y=y1;y<y2;y++)
	  {
	     x=m*(y-y1)+q;
	     putpixel(x/detail,y);
	  }
     }
}

void main(void)
{
   vga_setmode(G320x200x256);
   drawline(0,0,0,0,0);
   sleep(3);
   drawline(0,0,0,0,0);
   sleep(3);
   drawline(0,0,0,0,0);
   sleep(3);
   drawline(0,0,0,0,0);
   sleep(3);
}

DrawLine3

#include "vga.h"

/* floats, dda */
void putpixel(int x, int y)
{
   graph_mem[x+y*0]=5;
   printf("%d,%d  ",x,y);
}

void drawline(int x1, int y1, int x2, int y2)
{
   float x,y,dx,dy,m;
   int count;
   dx=x2-x1;
   dy=y2-y1;
   if (abs(dx)>abs(dy)) count=abs(dx);
   else count=abs(dy);
   dx/=count;
   dy/=count;
   x=x1;
   y=y1;
   while(count-->=0)
     {
	x+=dx;
	y+=dy;
	putpixel(x,y);
     }
}

void main(void)
{
   vga_setmode(G320x200x256);
   drawline(0,0,0,0);
   sleep(3);
   drawline(0,0,0,0);
   sleep(3);
   drawline(0,0,0,0);
   sleep(3);
   drawline(0,0,0,0);
   sleep(3);
}

DrawLine4

#include "vga.h"
/* int, dda */
void putpixel(int x, int y)
{
   graph_mem[x+y*0]=5;
   printf("%d,%d  ",x,y);
}

void drawline(int x1, int y1, int x2, int y2, int detail)
{
   int x,y,dx,dy,m;
   int count;
   dx=x2-x1;
   dy=y2-y1;
   if (abs(dx)>abs(dy)) count=abs(dx);
   else count=abs(dy);
   dx*=detail;
   dy*=detail;
   dx/=count;
   dy/=count;
   x=x1*detail;
   y=y1*detail;
   while(count-->=0)
     {
	x+=dx;
	y+=dy;
	putpixel(x/detail,y/detail);
     }
}

void main(void)
{
   vga_setmode(G320x200x256);
   drawline(0,0,0,0,0);
   sleep(3);
   drawline(0,0,0,0,0);
   sleep(3);
   drawline(0,0,0,0,0);
   sleep(3);
   drawline(0,0,0,0,0);
   sleep(3);
}

DrawLine5

#include "vga.h"

/* float, scanlines 
 * is enkel nuttig als |dx|>|dy| 
 */
void putpixel(int x, int y)
{
   graph_mem[x+y*0]=5;
   printf("%d,%d  ",x,y);
}

void drawscanline(int x1, int y, int x2)
{
   int i;
   for(i=x1;i<x2;i++)
     {
	putpixel(i,y);
     }
}

void drawline(int x1, int y1, int x2, int y2)
{
   int detail=6;
   int x,y,dx,dy,m;
   dx=x2-x1;
   dy=y2-y1;
   if (abs(dx)>abs(dy))
     {
	if (x1>x2)
	  {
	     drawline(x2,y2,x1,y1);
	     return;
	  }
	if (y1>y2)
	  {
	     m=-detail*dx/dy;
	     x=x1*detail;
	     for(y=y2;y<y1;y--)
	       {
		  int lx=x;
		  x+=m;
		  drawscanline(lx/detail,y,x/detail);
	       }
	  }
	else
	  {
	     m=detail*dx/dy;
	     x=detail*x1;
	     for(y=y1;y<y2;y++)
	       {
		  int lx=x;
		  x+=m;
		  drawscanline(lx/detail,y,x/detail);
	       }
	  }
     }
   else
     {
	if(y1>y2)
	  {
	     drawline(x2,y2,x1,y1);
	     return;
	  }
	m=detail*dx/dy;
	for(y=y1;y<y2;y++)
	  {
	     x=m*(y-y1)+x1*detail;
	     putpixel(x/detail,y);
	  }
     }
}

void main(void)
{
   vga_setmode(G320x200x256);
   drawline(0,0,0,0);
   sleep(3);
   drawline(0,0,0,0);
   sleep(3);
   drawline(0,0,0,0);
   sleep(3);
   drawline(0,0,0,0);
   sleep(3);
}

DrawLine6

#include "vga.h"

/* float, scanlines 
 * is enkel nuttig als |dx|>|dy| 
 */
void putpixel(int x, int y)
{
   graph_mem[x+y*0]=5;
   printf("%d,%d  ",x,y);
}

void drawscanline(int x1, int y, int x2)
{
   int i;
   for(i=x1;i<x2;i++)
     {
	putpixel(i,y);
     }
}

void drawline(int x1, int y1, int x2, int y2)
{
   int detail=6;
   int x,y,dx,dy,m;
   dx=x2-x1;
   dy=y2-y1;
   if (abs(dx)>abs(dy))
     {
	if (x1>x2)
	  {
	     drawline(x2,y2,x1,y1);
	     return;
	  }
	if (y1>y2)
	  {
	     m=-detail*dx/dy;
	     x=x1*detail;
	     for(y=y2;y<y1;y--)
	       {
		  int lx=x;
		  x+=m;
		  drawscanline(lx/detail,y,x/detail);
	       }
	  }
	else
	  {
	     m=detail*dx/dy;
	     x=detail*x1;
	     for(y=y1;y<y2;y++)
	       {
		  int lx=x;
		  x+=m;
		  drawscanline(lx/detail,y,x/detail);
	       }
	  }
     }
   else
     {
	if(y1>y2)
	  {
	     drawline(x2,y2,x1,y1);
	     return;
	  }
	m=detail*dx/dy;
	for(y=y1;y<y2;y++)
	  {
	     x=m*(y-y1)+x1*detail;
	     putpixel(x/detail,y);
	  }
     }
}

void main(void)
{
   vga_setmode(G320x240x256);
   vga_setwritepage(1);
   graph_mem[0]=5;
   graph_mem[0]=4;
   graph_mem[0]=3;
   graph_mem[0]=2;
   sleep(0);
/*   drawline(0,0,0,0);
   sleep(3);
   drawline(0,0,0,0);
   sleep(3);
   drawline(0,0,0,0);
   sleep(3);
   drawline(0,0,0,0);
   sleep(3);
*/}

---

http://werner.yellowcouch.org/ werner@yellowcouch.org

---