Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Drawing a line - faster

  1. Apr 30, 2014 #1

    Edi

    User Avatar

    First year learning programming here.
    I am trying to write a line drawing algorithm that would be, perhaps, faster than algorithms used today (that would be nice, if I would turn out to be smart and accomplish something nice) so I wrote this piece of code (currently it only draws lines where difference in y is larger than diff in x, but thats just a manner of toppling everything to its side, so to speak :) ):
    Code (Text):
    procedure TForm1.Brezenhem(x1, y1, x2, y2: integer);
    var Pn, dx, dy, xn, yn, xi, yi,i,j, yprev, sign:integer;
    var dyddx:single;
    var start, stop, elap: cardinal;
    begin

     start:=GetTickCount; i:=0;
    while (i<200) do
    begin

       image1.canvas.Pen.color:=RGB(150,0,255);  // mmm, Lilac - such a great color :)
    if (x2-x1<0) then Pn:=-1  else Pn:=1;
    dx:=x2-x1+Pn;
    dy:=y2-y1;
                 if abs(dy)>abs(dx) then
        begin
    xi:=x1;
    dyddx:=dy/ dx;
       if (y2>y1) then sign:=1 else sign:=-1;
    yprev:=y1-sign;
          while(xi<>x1+dx) do  // main loop starts here. "x1" (and y1) is the center of the canvas.
          begin
          yn:=y1+round(dyddx*(xi+Pn-x1));
            {
                j:=0;
                while (j<abs(yprev-yn))  do
                    begin
                       image1.Canvas.pixels[xi, yn-j*sign]:=RGB(255,200,0);
                       j:=j+1;
                    end;  
              }
                                j:=abs(yprev-yn);
                                image1.canvas.MoveTo(xi,yn);
                                image1.canvas.LineTo(xi,yn-j*sign);
          xi:=xi+Pn;
          yprev:=yn;
          end;
         end;

       i:=i+1;
       end;
       stop:=GetTickCount;
       elap:=stop-start;
       edit1.Text:=IntToStr(elap);
       end;
    The idea behind this code is this:
    I simply divide difference in y axis with diff x and I get a number of pixels to draw in y axis per one iteration of x axis (as a real value that is rounded). And it works.

    But there are some things bothering me:
    First I tried running it without the .lineTo, but with the commented-out loop of canvas.pixels and it was about as fast as Brezenhem.
    Then i commented the loop out and added the .lineTo part (to only draw the vertical line) - now it works something like 6 times faster then Brezenhem (depending at the angle of the line) - thats quite interesting.
    As someone explained to me - the .lineto function is optimized at assembler level, thats why it is faster.. is that right?
    If I optimize my simple canvas.pixels vertical line loop at assembler level, it would work even faster than now, because there would only be that simple loop, not the whole, optimized, whatever is hiding under .lineTo, wouldnt it? ( But I have no idea how to do that yet)


    What is the fastest line algorithm used in games and visual programs? (every 3D model is made from triangles which are drawn using line algorithms)

    If i get the fastest algorithm and write it in a code, it still would need to be optimized in assembler lever to really get its speed.. or what?
    The optimization in assembler really confused me.
     
    Last edited: Apr 30, 2014
  2. jcsd
  3. Apr 30, 2014 #2

    DavidSnider

    User Avatar
    Gold Member

    Last edited: Apr 30, 2014
  4. Apr 30, 2014 #3

    DrGreg

    User Avatar
    Science Advisor
    Gold Member

    This looks like Delphi code to me, if my memory is correct. The problem is that when you modify image1.Canvas.pixels[x, y] you're not directly drawing to the screen, you're executing a whole lot of Delphi library code (and your operating system's API). Whereas image1.canvas.MoveTo() and image1.canvas.LineTo() are executed less frequently and therefore with less overhead. The time taken isn't due to the calculations, it's due to the overhead of calling functions.

    As DavidSnider pointed out, fast games can achieve their speed by getting the GPU to draw the line rather than working out the individual pixels in the CPU.
     
  5. May 1, 2014 #4

    jim mcnamara

    User Avatar

    Staff: Mentor

    FWIW: the Bresenham line drawing algorithm and others like you see at in the comparison at edepot, have to be modified by a software engineer to fit a particular environment. So what you see there is based on a PIII chip. Different cpus will do better or worse with the identical code and software libraries.

    If you want a lot of speed, consider FORTRAN or C.

    An example of software engineering is the discussion (not about line drawing, rather the basics of what your cpu architecture does for and against you because of memory):

    http://www.akkadia.org/drepper/cpumemory.pdf Note: most of this article, though 7 years old, is still very relevant.
     
  6. Jun 2, 2014 #5

    Edi

    User Avatar

    Ok, but what exactly makes the GPU faster at drawing a line? The pixels are still calculated somehow, aren't they?
     
  7. Jun 2, 2014 #6

    Borek

    User Avatar

    Staff: Mentor

    Yes, but GPU is specialized, so can do the operations faster relying on hardware implementation.
     
  8. Jun 2, 2014 #7

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    To modify and expand on what Borek said:

    1. The GPU processor is optimized to handle its calculations in vector or other parallel form, which is different from how the main CPU is designed.

    2. The GPU is also equipped with a certain amount of the fastest memory (faster than the computer's RAM), which is located close to the GPU to reduce access time further. This memory is dedicated to the GPU and is not shared by the computer's RAM.

    3. And finally, the GPU is relieved of having to manage the running of the rest of the computer like the CPU must, and thus most of its processing cycles are dedicated to drawing and managing images.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook