16/PCGPE10/BRES.TXT

   1 \r
   2                ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿\r
   3                ³ Bresenham's Line and Circle Algorithms ³\r
   4                ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
   5 \r
   6                  Written for the PC-GPE by Mark Feldman\r
   7             e-mail address : u914097@student.canberra.edu.au\r
   8                              myndale@cairo.anu.edu.au\r
   9 \r
  10              ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿\r
  11              ³      THIS FILE MAY NOT BE DISTRIBUTED     ³\r
  12              ³ SEPARATE TO THE ENTIRE PC-GPE COLLECTION. ³\r
  13              ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
  14 \r
  15 \r
  16 ÚÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\r
  17 ³ Disclaimer ³\r
  18 ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
  19 \r
  20 I assume no responsibility whatsoever for any effect that this file, the\r
  21 information contained therein or the use thereof has on you, your sanity,\r
  22 computer, spouse, children, pets or anything else related to you or your\r
  23 existance. No warranty is provided nor implied with this information.\r
  24 \r
  25 ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\r
  26 ³ Introduction ³\r
  27 ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
  28 \r
  29 Bresenham is a pretty smart cookie (note the use of the word "is", last I\r
  30 heard he was still working for IBM). This file contains the algorithms he\r
  31 developped for drawing lines and circles on a pixelated display system\r
  32 such as the VGA.\r
  33 \r
  34 ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\r
  35 ³ Line Algorithm ³\r
  36 ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
  37 \r
  38 The basic algorithm works for lines which look like this:\r
  39 \r
  40 \r
  41       o-------                         ¿\r
  42      p1       --------                 ³ deltay\r
  43                       -------      p2  ³\r
  44                              -------o  Ù\r
  45 \r
  46       ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
  47                   deltax\r
  48 \r
  49 where p1 = (x1,y1),\r
  50       p2 = (x2, y2),\r
  51       x and y are both increasing from p1 to p2,\r
  52       deltax = x2 - x1,\r
  53       deltay = y2 - y1 and\r
  54       deltax >= deltay.\r
  55 \r
  56 All other types of lines can be derived from this type. I'll get to this\r
  57 bit later.\r
  58 \r
  59 First you need to perform the following intialisation:\r
  60 \r
  61 x = x1\r
  62 y = y1\r
  63 d = (2 * deltay) - deltax\r
  64 \r
  65 x is the current x location, you will add 1 to this variable after every\r
  66 pixel you draw until all pixels have been drawn.\r
  67 y is the current y location. The decision variable is used to determine\r
  68 when to add 1 to this value. d is the decision variable which will be used\r
  69 to keep a track of what to do.\r
  70 \r
  71 Now you loop across the screen from x1 to x2 and for each loop perform the\r
  72 following operations for each pixel :\r
  73 \r
  74 PutPixel(x, y);  { Draw a pixel at the current point }\r
  75 if d < 0 then\r
  76     d := d + (2 * deltay)\r
  77 else\r
  78   begin\r
  79     d := d + 2 * (deltay - deltax);\r
  80     y := y + 1;\r
  81   end;\r
  82 x := x + 1;\r
  83 \r
  84 It's that simple!\r
  85 \r
  86 ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\r
  87 ³ Speeding Up The Line Algorithm ³\r
  88 ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
  89 \r
  90 There are several useful techniques for speeding up Bresenhams line\r
  91 algorithm.\r
  92 \r
  93 For starters, notice that all multiplications are by 2. This can be\r
  94 performed with a simple shift left instruction (Shl in Pascal, << in C).\r
  95 \r
  96 Next notice that the values you add to the decision variable do not change\r
  97 throughout the loop, so they can be precalculated beforehand.\r
  98 \r
  99 One property of lines is that they are symetrical about their mid-points,\r
 100 and we can use this property to speed up the algorithm. Store two x and y\r
 101 values, (xa, ya) and (xb, yb). Have each pair start on either end of the\r
 102 line. For each pass through the loop you draw the pixel at both points, add\r
 103 1 to xa and subtract one from xb. When d >= 0 add 1 to ya and subtract one\r
 104 from yb. You then only need to loop until xa = xb.\r
 105 \r
 106 It's also obvious that if the decision variable becomes the same value\r
 107 it was when it was initialised, then the rest of the line is just\r
 108 copies of the line you have already drawn up to that point. You might be\r
 109 able to speed the algorithm up by keeping an array of how y has been\r
 110 modified and then use this array if the line starts repeating itself. If\r
 111 you are using the Intel registers to store all values then you probably\r
 112 wouldn't get much of a speed increase (in fact it could slow it down), but\r
 113 it would probably be useful for thing like linear texture mapping (discussed\r
 114 below). I've never actually tried implementing this technique, and I would\r
 115 like to hear the results if anyone does.\r
 116 \r
 117 Above all remember that these optimisations will only significantly speed\r
 118 up the line drawing algorithm if the whole thing is done in assembly. A\r
 119 profile of the example program at the end of this file showed that 40% of\r
 120 CPU time was spent in the slow PutPixel routine I was using, the loop\r
 121 mechanics and testing the sign of the decision variable.\r
 122 \r
 123 ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\r
 124 ³ Other Uses for the Line Algorithm ³\r
 125 ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
 126 \r
 127 A line can be represented by the equation y = mx + c, where\r
 128 m = deltay / deltax. Note that this is a version of the standard linear\r
 129 equation ax + bx + c = 0. There are many algorithms which use this equation.\r
 130 \r
 131 One good use for the bresenham line algorithm is for quickly drawing filled\r
 132 concave polygons (eg triangles). You can set up an array of minimum and\r
 133 maximum x values for every horizontal line on the screen. You then use\r
 134 bresenham's algorithm to loop along each of the polygon's sides, find where\r
 135 it's x value is on every line and adjust the min and max values accordingly.\r
 136 When you've done it for every line you simply loop down the screen drawing\r
 137 horizontal lines between the min and max values for each line.\r
 138 \r
 139 Another area is in linear texture mapping (see the PC-GPE article on texture\r
 140 mapping). This method involves taking a string of bitmap pixels and\r
 141 stretching them out (or squashing them in) to a line of pixels on the screen.\r
 142 Typically you would draw a vertical line down the screen and use Bresenhams\r
 143 to calculate which bitmap pixel should be drawn at each screen pixel.\r
 144 \r
 145 ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\r
 146 ³ Circle Algorithm ³\r
 147 ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
 148 \r
 149 Circles have the property of being highly symetrical, which is handy\r
 150 when it comes to drawing them on a display screen.\r
 151 \r
 152       |y          (This diagram is supposed to be a circle, try viewing\r
 153       |           it in 50 line mode).\r
 154   \ ..... /\r
 155    .  |  .        We know that there are 360 degrees in a circle. First we\r
 156   . \ | / .       see that a circle is symetrical about the x axis, so\r
 157   .  \|/  .       only the first 180 degrees need to be calculated. Next\r
 158 --.---+---.--     we see that it's also symetrical about the y axis, so now\r
 159   .  /|\  . x     we only need to calculate the first 90 degrees. Finally\r
 160   . / | \ .       we see that the circle is also symetrical about the 45\r
 161    .  |  .        degree diagonal axis, so we only need to calculate the\r
 162   / ..... \       first 45 degrees.\r
 163       |\r
 164       |\r
 165 \r
 166 Bresenhams circle algorithm calculates the locations of the pixels in the\r
 167 first 45 degrees. It assumes that the circle is centered on the origin. So\r
 168 for every pixel (x,y) it calculates we draw a pixel in each of the 8 octants\r
 169 of the circle :\r
 170 \r
 171 PutPixel(CenterX + X, Center Y + Y)\r
 172 PutPixel(CenterX + X, Center Y - Y)\r
 173 PutPixel(CenterX - X, Center Y + Y)\r
 174 PutPixel(CenterX - X, Center Y - Y)\r
 175 PutPixel(CenterX + Y, Center Y + X)\r
 176 PutPixel(CenterX + Y, Center Y - X)\r
 177 PutPixel(CenterX - Y, Center Y + X)\r
 178 PutPixel(CenterX - Y, Center Y - X)\r
 179 \r
 180 So let's get into the actual algorithm. Given a radius for the circle\r
 181 we perform this initialisation:\r
 182 \r
 183 d := 3 - (2 * RADIUS)\r
 184 x := 0\r
 185 y := RADIUS\r
 186 \r
 187 Now for each pixel we do the following operations:\r
 188 \r
 189 Draw the 8 circle pixels\r
 190 if d < 0 then\r
 191     d := d + (4 * x) + 6\r
 192 else\r
 193   begin\r
 194     d := d + 4 * (x - y) + 10\r
 195     y := y - 1;\r
 196   end;\r
 197 \r
 198 And we keep doing this until x = y. Note that the values added to the\r
 199 decision variable in this algorithm (x and y) are constantly changing, so\r
 200 we cannot precalculate them. The muliplications however are by 4, and we\r
 201 can accomplish this by shifting left twice.\r
 202 \r
 203 \r
 204 ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\r
 205 ³ A Pascal General Line Procedure ³\r
 206 ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ\r
 207 \r
 208 The basic bresenham line algorithm can be modified to handle all types of\r
 209 lines. In this section assume that deltax = abs(x2 - x1) and\r
 210 deltay = abs(y2 - y1).\r
 211 \r
 212 First let's take lines where deltax >= deltay. Now if x1 > x2 then you will\r
 213 need to subtract 1 from x for every pass through the loop. Similarly if y1 >\r
 214 y2 then you will be also need to subtract 1 from y for every pass through the\r
 215 loop where d < 0.\r
 216 \r
 217 Lines where deltax < deltay can be handled the same way, you just swap all\r
 218 the deltax's and deltay's around.\r
 219 \r
 220 The fastest method of handling all cases is to write a custom routine for\r
 221 each of the 8 line types:\r
 222 \r
 223 1) x1 <= x2, y1 <= y2, deltax >= deltay\r
 224 2) x1 <= x2, y1 <= y2, deltax <  deltay\r
 225 3) x1 <= x2, y1 >  y2, deltax >= deltay\r
 226 4) x1 <= x2, y1 >  y2, deltax <  deltay\r
 227 5) x1 >  x2, y1 <= y2, deltax >= deltay\r
 228 6) x1 >  x2, y1 <= y2, deltax <  deltay\r
 229 7) x1 >  x2, y1 >  y2, deltax >= deltay\r
 230 8) x1 >  x2, y1 >  y2, deltax <  deltay\r
 231 \r
 232 This will give you the fastest results, but will also make your code 8\r
 233 times larger! Alternatively you can declare a few extra variables and\r
 234 use a common inner loop for all lines:\r
 235 \r
 236 numpixels = number of pixels to draw\r
 237           = deltax if deltax >= deltay or\r
 238           = deltay if deltax < deltay\r
 239 dinc1 = the amount to add to d when d < 0\r
 240 dinc2 = the amount to add to d when d >= 0\r
 241 xinc1 = the amount to add to x when d < 0\r
 242 xinc2 = the amount to add to x when d >= 0\r
 243 yinc1 = the amount to add to y when d < 0\r
 244 yinc2 = the amount to add to y when d >= 0\r
 245 \r
 246 The following is a simple example program which uses this technique:\r
 247 \r
 248 \r
 249 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\r
 250 \r
 251 {\r
 252 \r
 253 BRESLINE.PAS - A general line drawing procedure.\r
 254                By Mark Feldman\r
 255 \r
 256 This is a very simple implementation of bresenhams' line algorithm with\r
 257 no optimisations. It can draw about 6000 random lines a second in mode 13h\r
 258 on my 486SX33 with sloooooow Paradise Extended VGA.\r
 259 \r
 260 }\r
 261 \r
 262 procedure Line(x1, y1, x2, y2 : integer; color : byte);\r
 263 var i, deltax, deltay, numpixels,\r
 264     d, dinc1, dinc2,\r
 265     x, xinc1, xinc2,\r
 266     y, yinc1, yinc2 : integer;\r
 267 begin\r
 268 \r
 269   { Calculate deltax and deltay for initialisation }\r
 270   deltax := abs(x2 - x1);\r
 271   deltay := abs(y2 - y1);\r
 272 \r
 273   { Initialize all vars based on which is the independent variable }\r
 274   if deltax >= deltay then\r
 275     begin\r
 276 \r
 277       { x is independent variable }\r
 278       numpixels := deltax + 1;\r
 279       d := (2 * deltay) - deltax;\r
 280       dinc1 := deltay Shl 1;\r
 281       dinc2 := (deltay - deltax) shl 1;\r
 282       xinc1 := 1;\r
 283       xinc2 := 1;\r
 284       yinc1 := 0;\r
 285       yinc2 := 1;\r
 286     end\r
 287   else\r
 288     begin\r
 289 \r
 290       { y is independent variable }\r
 291       numpixels := deltay + 1;\r
 292       d := (2 * deltax) - deltay;\r
 293       dinc1 := deltax Shl 1;\r
 294       dinc2 := (deltax - deltay) shl 1;\r
 295       xinc1 := 0;\r
 296       xinc2 := 1;\r
 297       yinc1 := 1;\r
 298       yinc2 := 1;\r
 299     end;\r
 300 \r
 301   { Make sure x and y move in the right directions }\r
 302   if x1 > x2 then\r
 303     begin\r
 304       xinc1 := - xinc1;\r
 305       xinc2 := - xinc2;\r
 306     end;\r
 307   if y1 > y2 then\r
 308     begin\r
 309       yinc1 := - yinc1;\r
 310       yinc2 := - yinc2;\r
 311     end;\r
 312 \r
 313   { Start drawing at <x1, y1> }\r
 314   x := x1;\r
 315   y := y1;\r
 316 \r
 317   { Draw the pixels }\r
 318   for i := 1 to numpixels do\r
 319     begin\r
 320       PutPixel(x, y, color);\r
 321       if d < 0 then\r
 322         begin\r
 323           d := d + dinc1;\r
 324           x := x + xinc1;\r
 325           y := y + yinc1;\r
 326         end\r
 327       else\r
 328         begin\r
 329           d := d + dinc2;\r
 330           x := x + xinc2;\r
 331           y := y + yinc2;\r
 332         end;\r
 333     end;\r
 334 end;\r
 335 \r
 336 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\r
 337 \r
 338 \r
 339 \r
 340 \r
 341 \r
 342 \r
 343 Note that if you are writing a line routine for mode 13h (for example) you\r
 344 can speed it up by converting the inner loop to assembly and including\r
 345 mode 13h specific code. This portion of the above routine works the same but\r
 346 the <x, y> values are stored in a single variable (screen) which holds the\r
 347 memory address of the current pixel, screeninc1 and screeninc2 are the\r
 348 update values for screen.\r
 349 \r
 350 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\r
 351 \r
 352 var screen : word;\r
 353     screeninc1, screeninc2 : integer;\r
 354      .\r
 355      .\r
 356      .\r
 357   { Start drawing at <x1, y1> }\r
 358   screen := word(y1) * 320 + x1;\r
 359   screeninc1 := yinc1 * 320 + xinc1;\r
 360   screeninc2 := yinc2 * 320 + xinc2;\r
 361 \r
 362   { Draw the pixels }\r
 363   asm\r
 364 \r
 365     { Use as many registers as are available }\r
 366     push $A000\r
 367     pop es\r
 368     mov di, screen\r
 369     mov dx, d\r
 370     mov al, color\r
 371     mov cx, numpixels\r
 372     mov bx, dinc1\r
 373 \r
 374     @bres1:\r
 375 \r
 376     { Draw the current pixel and compare the decision variable to 0 }\r
 377     mov es:[di], al\r
 378     cmp dx, 0\r
 379     jnl @bres2\r
 380 \r
 381     { D < 0 }\r
 382     add dx, bx { bx = dinc1 }\r
 383     add di, screeninc1\r
 384     jmp @bres3\r
 385 \r
 386     @bres2:\r
 387 \r
 388     { D >= 0 }\r
 389     add dx, dinc2\r
 390     add di, screeninc2\r
 391 \r
 392     @bres3:\r
 393 \r
 394     loop @bres1\r
 395   end;\r
 396 \r
 397 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ\r
 398 \r
 399 \r