home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / MCGA#03.ZIP / LESSON03.TXT < prev    next >
Encoding:
Text File  |  1992-06-11  |  7.9 KB  |  235 lines
  1.                            MCGA Graphics Tutorial
  2.                                  Lesson #3
  3.                                 by Jim Cook
  4.  
  5. As promised, the topic of today's lesson is line drawing.  There are
  6. many ways to approach line drawing, and we will end up with what is
  7. possibly the fastest non-assembly line drawing routine.  But, to get
  8. there we must start at the beginning.
  9. Remember:  no pain, no gain!
  10.  
  11. First of all, we will concentrate on the point-slope form of an equation.
  12. Dust off that algebra book and open to page 137.  Where (X1,Y1) and (X2,Y2)
  13. are the endpoints of a line segment, any point (X,Y) on the line can be
  14. represented by the equation:
  15.  
  16.                 Y - Y1   Y2 - Y1
  17.                 ------ = _______
  18.                 X - X1   X2 - X1
  19.  
  20. We are going to turn this into the following procedure:
  21.  
  22.            Procedure LineEqu (X1,Y1,X2,Y2:Integer;Color:Byte);
  23.            var
  24.              Slope  :  Real;
  25.              D,X,Y  :  Integer;
  26.            begin
  27.              If (X1 = X2) or (Y1 = Y2) then Exit;
  28.              If X1 > X2 then begin
  29.                D  := X1;
  30.                X1 := X2;
  31.                X2 := D;
  32.                D  := Y1;
  33.                Y1 := Y2;
  34.                Y2 := D;
  35.                end;
  36.              Slope := (Y2-Y1)/(X2-X1);
  37.              If Abs(Y2-Y1) > Abs(X2-X1) then begin
  38.                Slope := (X2-X1)/(Y2-Y1);
  39.                For Y := Y1 to X2 do
  40.                  SetPixel (Trunc(Slope*(Y-Y1)+X1),Y,Color);
  41.                end
  42.              Else begin
  43.                Slope := (Y2-Y1)/(X2-X1);
  44.                For X := X1 to X2 do
  45.                  SetPixel (X,Trunc(Slope*(X-X1)+Y1),Color);
  46.                end;
  47.            end;
  48.  
  49. This is kinda straight forward.  I just want to make a couple comments
  50. on the code.  The first line of code checks for a vertical or horizontal
  51. line.  If this case presents itself, we don't draw the line, because of
  52. the danger of a zero value in the slope formula, and a potential
  53. division by zero error. We also make the loop draw by X or by Y increments
  54. to eliminate gaps in our lines.  You can make the '>' in the If-Then
  55. statement into a '<' to see what I mean.  These problems are too meaningless
  56. to fix, because this algorithm produces a measely 165 lines per second
  57. on my computer (386 33mhz).
  58.  
  59. Now is the time to Enter stage left, J. E. Bresenham, who in 1965
  60. produced an elegant solution to avoid all of this computational nonsense.
  61. Bresenham developed a method of determining what pixel the line was
  62. closer to.  This is achieved by creating a decision variable and two
  63. incremental/decremental variables which see-saws both sides of the line.
  64. Trace through the following line procedure to get a full appreciation
  65. of the algorithm:
  66.  
  67.            Procedure LineIndiv (X1,Y1,X2,Y2:Integer;Color:Byte);
  68.            var
  69.              X,Y,
  70.              YIncr,
  71.              D,DX,DY,
  72.              AIncr,BIncr :  Integer;
  73.              Ofs         :  Word;
  74.            begin
  75.              If X1 > X2 then begin
  76.                D  := X1;
  77.                X1 := X2;
  78.                X2 := D;
  79.                D  := Y1;
  80.                Y1 := Y2;
  81.                Y2 := D;
  82.                end;
  83.              If Y2 > Y1 then YIncr :=  1
  84.                         else YIncr := -1;
  85.              DX := X2 - X1;
  86.              DY := Abs (Y2-Y1);
  87.              D := 2 * DY - DX;
  88.              AIncr := 2 * (DY - DX);
  89.              BIncr := 2 * DY;
  90.  
  91.              X := X1;
  92.              Y := Y1;
  93.              SetPixel (X,Y,Color);
  94.  
  95.              For X := X1 + 1 to X2 do begin
  96.                If D >= 0 then begin
  97.                  Inc (Y,YIncr);
  98.                  Inc (D,AIncr);
  99.                  end
  100.                Else Inc (D,BIncr);
  101.                SetPixel (X,Y,Color);
  102.                end;
  103.            end;
  104.  
  105. Notice that once the variables are set up, the only math taking place
  106. is subtration and/or addition.  There is however, one catch;  we are
  107. calling SetPixel to set each point on the line and this procedure
  108. contains a multiplication.  The speed of an average line with this
  109. routine is 1000 lines per second.  That's six times faster than the
  110. line equation method.
  111.  
  112. Let's take a look at the final? evolution:
  113.  
  114.            Procedure Line (X1,Y1,X2,Y2:Integer;Color:Byte);
  115.            var
  116.              I,
  117.              YIncr,
  118.              D,DX,DY,
  119.              AIncr,BIncr :  Integer;
  120.              Ofs         :  Word;
  121.            begin
  122.             If X1 > X2 then begin
  123.                D  := X1;
  124.                X1 := X2;
  125.                X2 := D;
  126.                D  := Y1;
  127.                Y1 := Y2;
  128.                Y2 := D;
  129.                end;
  130.              If Y2 > Y1 then YIncr :=  320
  131.                         else YIncr := -320;
  132.              DX := X2 - X1;
  133.              DY := Abs (Y2-Y1);
  134.              D := 2 * DY - DX;
  135.              AIncr := 2 * (DY - DX);
  136.              BIncr := 2 * DY;
  137.  
  138.              Ofs := Word(Y1) * 320 + Word(X1);
  139.  
  140.              Mem [$A000:Ofs] := Color;
  141.  
  142.              For I := X1 + 1 to X2 do begin
  143.                If D >= 0 then begin
  144.                  Inc (Ofs,YIncr);
  145.                  Inc (D,AIncr);
  146.                  end
  147.                Else Inc (D,BIncr);
  148.                Inc (Ofs);
  149.                Mem [$A000:Ofs] := Color;
  150.                end;
  151.            end;
  152.  
  153. There we have it, an extremely fast line drawing algorithm, all coded in
  154. Turbo Pascal.  We may do this in assembly if the need for speed drives
  155. us to it.  When doing animation, speed is paramount, so we probably will
  156. implement this is assembly.  The benchmark, by the way, is a whopping 1820
  157. lines per second.  Here is a program to test each routine for speed:
  158.  
  159.          Program MCGATest;
  160.          uses
  161.            Crt,Dos,Lib03;
  162.          var
  163.            Stop,
  164.            Start  :  LongInt;
  165.            Regs   :  Registers;
  166.            PicBuf :  Pointer;
  167.  
  168.          Function Tick : LongInt;
  169.          begin
  170.            Regs.ah := 0;
  171.            Intr ($1A,regs);
  172.            Tick := Regs.cx shl 16 + Regs.dx;
  173.          end;
  174.  
  175.          Procedure ShowAndTell (S:String);
  176.          var
  177.            Ch     :  Char;
  178.          begin
  179.            Repeat Until Keypressed;
  180.            While Keypressed do Ch := Readkey;
  181.            TextMode (3);
  182.            WriteLn (S);
  183.            WriteLn ('Routine took ',(Stop-Start)/18.2:4:3,' seconds!');
  184.            Write   ('or an average of ');
  185.            WriteLn (1000/((Stop-Start)/18.2)):6:1,' lines per second.');
  186.            While KeyPressed do Ch := Readkey;
  187.            Repeat Until Keypressed;
  188.            While Keypressed do Ch := Readkey;
  189.          end;
  190.  
  191.          Procedure Control;
  192.          var
  193.            I :  Integer;
  194.          begin
  195.            SetGraphMode ($13);
  196.            Start := Tick;
  197.            For I := 1 to 1000 do
  198.              LineEqu (Random (320),Random (200),
  199.                       Random (320),Random(200),Random(256));
  200.            Stop := Tick;
  201.            ShowAndTell ('Equation of a line...');
  202.            SetGraphMode ($13);
  203.            Start := Tick;
  204.            For I := 1 to 1000 do
  205.              LineIndiv (Random (320),Random (200),
  206.                         Random (320),Random(200),Random(256));
  207.            Stop := Tick;
  208.            ShowAndTell ('Bresenhan''s algorithm, addressing each pixel individually...');
  209.            SetGraphMode ($13);
  210.            Start := Tick;
  211.            For I := 1 to 1000 do
  212.              Line (Random (320),Random (200),
  213.                    Random (320),Random(200),Random(256));
  214.            Stop := Tick;
  215.            ShowAndTell ('Bresenhan''s algorithm, incremental addressing each pixel...');
  216.          end;
  217.  
  218.          Procedure Init;
  219.          begin
  220.            Randomize;
  221.          end;
  222.  
  223.          Begin
  224.            Init;
  225.            Control;
  226.          End.
  227.  
  228. Hope you are enjoying the series, and I'm looking forward to reading
  229. your comments.  Next installment, we will look at the special case
  230. lines, vertical and horizontal.  These lines can be highly optimized,
  231. and of course we will do that whenever possible.
  232.  
  233. hack on
  234. jim  
  235.