Fastest way to draw a vertical line

This is a discussion on Fastest way to draw a vertical line within the Game Programming forums, part of the General Programming Boards category; I've been playing with drawing a vertical line quickly to an SDL Surface. You access a specific pixel in an ...

  1. #1
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254

    Fastest way to draw a vertical line

    I've been playing with drawing a vertical line quickly to an SDL Surface.
    You access a specific pixel in an SDL surface by doing the following:
    Code:
    ((unsigned int*)surface->pixels)[x + y*surface->pitch/4] = color;
    To draw a vertical line, I came up with the following code:
    Code:
    void draw_vl(SDL_Surface * surface, int x, int y, int height, unsigned int color)
    {
      unsigned int res = surface->pitch/4;
      unsigned int* fp, *cp = ((unsigned int*)surface->pixels) + x + y*res;
    
      for (fp = cp + height*res; cp <  fp; cp += res)
      {
        *cp = color;
      }
    }
    It seems fast, and I haven't been able to improve upon it. The thing is, after each *cp = color, we need to jump, etc., which from what I've heard is rather expensive CPUtime wise.

    I was thinking with a fixed maximum possible height, you could do something similar to the following (semi-pseudocode):

    Code:
    goto RATE_START + y*INSTRUCTIONS_PER_ITERATION
    
    RATE_START:
    *cp = color;
    cp += res;
    *cp = color;
    cp += res;
    *cp = color;
    ... Repeat 480 times (480 pixel tall image)
    This would remove any comparison checks (if cp < fp), and all jumps except one. I could use some sort of code generator, but I'm wondering if there is a cleaner way of doing this, or a simpler way of drawing lines that is faster than my current method?

    What is the fastest way to draw a vertical line?
    Programming Your Mom. http://www.dandongs.com/

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    You could always use/look at the source for SDL_gfx or SGE (search for them under the libraries section of libsdl.org).

    The way you have described sounds like a variation of Duff's Device, "spagetti code at its worst".
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    Thanks. SDL_gfx implements the vertical line function in pretty much the same way that I do (their function does boundary checking and various color checks, but the main section is the same). Duff's Device, as evil as it seems, looks like it could work. I'll test it out later and let you guys know if I manage to get it to work.
    Programming Your Mom. http://www.dandongs.com/

  4. #4
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    Code:
    void draw_vl(SDL_Surface * surface, int iPitch,int x, int y, int height, unsigned int color)
    {
      SETUP:
      __asm {
        push esi
        mov  esi,[surface]
        
        mov eax,y
        mov ebx,iPitch
        shr ebx,2
        mul eax
        add eax,x
        add esi,eax
      
        mov eax,color
        xor   ecx,ecx
        
       }
       PLOTPIXEL:
       asm __ {
        stosd
        inc ecx
        cmp ecx,height
        jb PLOTPIXEL
    
        pop esi
      }
    }
    No guarantees its faster. Besides I don't think drawing vertical lines is a bottleneck in the first place.

  5. #5
    Registered User
    Join Date
    Oct 2006
    Posts
    250
    Why do you want to optimize your line drawing routine? Is it a bottle neck in your code?

    As to Bubba's code, why do you compare with ecx? There are specialized instructions for performing a loop, such as 'loop' or the 'rep' prefix. At the least I'd suggest doing the following:

    void draw_vl(SDL_Surface * surface, int iPitch,int x, int y, int height, unsigned int color)
    {
    SETUP:
    __asm {
    push esi
    mov esi,[surface]

    mov eax,y
    mov ebx,iPitch
    shr ebx,2
    mul eax
    add eax,x
    add esi,eax

    mov eax,color
    mov ecx, height

    }
    PLOTPIXEL:
    asm __ {
    rep stosd

    pop esi
    }
    }

    Even then it's no guarantee that this code will run faster, as you'd have to consider such things as pipelining of instructions.

    My advice to CrazyNorman, just stick with your for loop, no point introducing needless bugs, without a good reason.

  6. #6
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    Just a matter of style. Neither method takes less or more cycles.

  7. #7
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Make sure your line drawing code is a real bottleneck first. You should profile the overall drawing code and check if this line drawing really takes up a substantial amount of time. Try turning on various optimizations and see how it goes; compilers have a notorious reputation for being able to optimize code much better than their human inventors (as they usually know the machine better). Just write straight code and expect your compiler to do its job well.

    Your second version looks even worse. If it is really faster on a particular machine, using suitable optimization switches (eg. funroll-loops on gcc) will make the compiler generate that same code (only for fixed-length unrollable loops of course). If it's slower on some machine (caches, pipelines, swap, whatever other factors can cause this) then the machine's compiler will just implement a straight loop. This is what compiler languages are really for, man -- abstraction.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    Well said jafet.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pointer and Polymorphism help.
    By Skyy in forum C++ Programming
    Replies: 29
    Last Post: 12-18-2008, 08:17 PM
  2. using GDI to draw round ended line
    By yongzai in forum Windows Programming
    Replies: 8
    Last Post: 01-11-2007, 10:04 AM
  3. Move the Caret to a line
    By TheDan in forum Windows Programming
    Replies: 3
    Last Post: 08-07-2005, 12:59 PM
  4. Trouble replacing line of file
    By Rpog in forum C Programming
    Replies: 4
    Last Post: 04-19-2004, 10:22 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21