/prog/ - Line Drawing

Name: Anonymous 2011-12-27 13:41

Does anybody know a faster line-drawing algorithm? This is Bresenham's, C++.

void draw_line(SDL_Surface *screen, int x1, int y1, int x2, int y2, Uint8 color)

{

  /* Draw a line from (x1, y1) to (x2, y2) */

  int dy = y2 - y1;

  int dx = x2 - x1;

  int stepx;

  int stepy;



  if (dy < 0)

  {

    dy = -dy;

    stepy = -1;

  }

  else

  {

    stepy = 1;

  }



  if (dx < 0)

  {

    dx = -dx;

    stepx = -1;

  }

  else

  {

    stepx = 1;

  }



  dy <<= 1;

  dx <<= 1;



  set_pixel(screen, x1, y1, color); /* Draw first pixel  */



  if (dx > dy)

  {

    int fraction = dy - (dx >> 1);

    while (x1 != x2)

    {

      if (fraction >= 0)

      {

        y1 += stepy;

        fraction -= dx;

      }



      x1 += stepx;

      fraction += dy;

      set_pixel(screen, x1, y1, color);

    }

  }

  else

  {

    int fraction = dx - (dy >> 1);

    while (y1 != y2)

    {

      if (fraction >= 0)

      {

        x1 += stepx;

        fraction -= dy;

      }



      y1 += stepy;

      fraction += dx;

      set_pixel(screen, x1, y1, color);

    }

  }

}

I heard there were faster ones, but not sure.

Name: Anonymous 2011-12-27 14:01

>>1

that's the best one that I'm aware of. Unless you want to use da hardware if it is available to you.

Name: Anonymous 2011-12-27 14:42

Oh god I remember this shit. I hate graphics.

I believe there's a library called SDL_gfx or something that has a bunch of different primitives with different algorithms.

Name: Anonymous 2011-12-27 15:16

Don't do stupid crap like this:

  dy <<= 1;

  dx <<= 1;

Your compiler optimizes these for you.

Name: Anonymous 2011-12-27 16:26

>>4

There are times where there is a difference. << works, but if you use >> on negative numbers: from that and dy /= 2; For instance, if 2's complement is being used, and if dy = -5;

using 8 bit number to simplify:

5 = 00000101
-5 = ~5 + 1 = 11111010 + 1 = 11111011

-5 >> 1 = 11111101
-(-5 >> 1) = ~(-5 >> 1) + 1 = 00000010 + 1 = 00000011 = 3

So if 2's compliment is used, then -5 >> 1 == -3. The rounding went down to negative infinity. But -5 / 2 = -2, because rounding is supposed to go towards zero.

Name: Anonymous 2011-12-27 16:35

>>5
Uh... Yeah? I know how binary arithmetic works. dy can never be negative during the right shift in >>1, because of the (similarly OPTIMIZED) abs in the beginning of the procedure.

Name: Anonymous 2011-12-27 17:18

What is <<= anyways?

Name: Anonymous 2011-12-27 17:24

>>7
x <<= 1 ≡ x = x << 1

Name: Anonymous 2011-12-27 17:38

>>6
yeap, that's cool, but some compilers aren't smart enough to know that, and wont be able to implement dy /2 as dy >>1

Name: Anonymous 2011-12-27 17:39

>>9
meant to write dy >> 1, and it was turned into a >>1, wupsydaisy

Name: Anonymous 2011-12-27 18:08

>>9
Why on earth would you use such a shitty compiler?

Name: Anonymous 2011-12-27 18:25

x <<= 1

x << 1

x = x * 2^1

x = x * 2

x = 2x

Right?

Name: Anonymous 2011-12-27 18:44

>>12
x = x * 2^1
Why would you XOR it with 1?
Also, 2x is a syntax error.

Name: Anonymous 2011-12-27 18:55

x *= 2;
use gcc

Name: Anonymous 2011-12-27 19:00

is there any reason not to use x <<= 1? Sure *2 is optimized in pretty much every compiler available if optimizations are enable but why not to optimize it on every compiler?

Name: Anonymous 2011-12-27 19:23

>>15
It's just silly. You will get it when you grow out of your ``I'm so low-level I shit xors'' phase.

Name: Anonymous 2011-12-27 19:27

>>16
I find writing unoptimized code and hoping that your compiler will optimize it sillier. x<<=1 is pretty straight forward

Name: Anonymous 2011-12-27 19:49

>>17
It is straightforward when it is straightforward, i.e. when you mean a left shift of 1 bit.

Name: Anonymous 2011-12-27 19:50

>>17
Why stop there? Why not just rewrite the whole thing in METICULOUSLY HAND-OPTIMIZED ASSEMBLY to make sure that no chance to optimize is missed? Have you actually looked at the output produced by, say, gcc with -O3 from >>1? If, after that, you still think that replacing *2 by <<1 is an "optimization", we are talking about entirely different concepts.

Name: Anonymous 2011-12-27 19:55

Go dig up some Dr. Dobb's Journals from the early 90s. IIRC a semi-common way to optimize Bresenham's was to split it up into 8 different cases depending on slope.

Name: Anonymous 2011-12-27 19:55

>>19
>Why stop there?
Because <<1 is only 1 additional character and it won't take additional work/work to do it. Also if someone is suggesting a line drawing algorithm with no multiplication, it better not have multiplication in it.

Name: Anonymous 2011-12-27 20:02

>>16
LOL!

a.c

void f(int x) {

  x *= 2;

}

gcc -O0 -s -c a.c; cat a.s
14: sall -4(%rbp)

Name: Anonymous 2011-12-27 20:10

“I'm so low-level that I shit xors.” - /profag/

Name: Anonymous 2011-12-27 20:16

>>21
If someone is doing multiplication, it better only have addition in it.

Name: Anonymous 2011-12-27 20:17

There's a slightly faster one that produces slightly uglier lines. It involves precomputing the length of each 'run' so it doesn't have to be done inside the loop.

Name: Anonymous 2011-12-27 20:40

OPTIMIZED LINE DRAWING



glBegin(GL_LINES);

glVertex2f(x1,y1);

glVertex2f(x2,y2);

glEnd();

Name: Anonymous 2011-12-27 20:51

>>26
omg unoptimized immediate mode

Name: Anonymous 2011-12-27 20:51

>>26
glBegin considered obsolete.

Name: Anonymous 2011-12-27 20:57

>>27
>>28
the overhead for drawing 1 single line with 3.0+ standards would be worse than simply doing the old immediate mode

Name: Anonymous 2011-12-27 21:06

Vectorization and parallelization can make it much faster.

http://www.google.ca/url?sa=t&rct=j&q=simd%20line%20drawing&source=web&cd=1&ved=0CB8QFjAA&url=http%3A%2F%2Fsophia.javeriana.edu.co%2F~cbustaca%2FComputacion%2520Grafica%2FTemas%2Fprimitivas2D%2FPang1990.pdf&ei=S3n6TvS8DcXmiAL6o9SBDQ&usg=AFQjCNFP8Xztc3cmUniSGEJ-lQTW-b5qvQ&cad=rja

Name: Anonymous 2011-12-27 21:19

>>30
>javeriana.edu.co
Fuck off, ``coffee".

Name: Anonymous 2011-12-27 21:20

Why hasn't anyone mentioned Xiaolin Wu's algorithm yet?

Name: Anonymous 2011-12-27 21:42

>>32
FUCK YOUR CHINK SHIT

Name: Anonymous 2011-12-27 22:01

>>11

just sayin, sometimes you have to use shitty compilers. Also, some times you might know that the input tot he function will always be positive, but the compiler might have to solve some hard shit to prove it. Or maybe the values comes from an input file and you trust that the input will always be positive. Just sayin.

Name: Anonymous 2011-12-27 22:30

>>32
The question was about faster algorithms, not prettier lines.

Name: Anonymous 2011-12-27 22:59

>>35

FAST AND PRETTY_{^{FAST AND PRETTY}}^{_{^{fast and pretty}}}

Name: Anonymous 2011-12-28 1:22

. . . Just draw from both ends at once. Twice as fast, despite the overhead.

Name: Anonymous 2011-12-28 12:27

>>37 Now that's a good a idea. Thanks!

Line Drawing

1 Name: Anonymous 2011-12-27 13:41

2 Name: Anonymous 2011-12-27 14:01

3 Name: Anonymous 2011-12-27 14:42

4 Name: Anonymous 2011-12-27 15:16

5 Name: Anonymous 2011-12-27 16:26

6 Name: Anonymous 2011-12-27 16:35

7 Name: Anonymous 2011-12-27 17:18

8 Name: Anonymous 2011-12-27 17:24

9 Name: Anonymous 2011-12-27 17:38

10 Name: Anonymous 2011-12-27 17:39

11 Name: Anonymous 2011-12-27 18:08

12 Name: Anonymous 2011-12-27 18:25

13 Name: Anonymous 2011-12-27 18:44

14 Name: Anonymous 2011-12-27 18:55

15 Name: Anonymous 2011-12-27 19:00

16 Name: Anonymous 2011-12-27 19:23

17 Name: Anonymous 2011-12-27 19:27

18 Name: Anonymous 2011-12-27 19:49

19 Name: Anonymous 2011-12-27 19:50

20 Name: Anonymous 2011-12-27 19:55

21 Name: Anonymous 2011-12-27 19:55

22 Name: Anonymous 2011-12-27 20:02

23 Name: Anonymous 2011-12-27 20:10

24 Name: Anonymous 2011-12-27 20:16

25 Name: Anonymous 2011-12-27 20:17

26 Name: Anonymous 2011-12-27 20:40

27 Name: Anonymous 2011-12-27 20:51

28 Name: Anonymous 2011-12-27 20:51

29 Name: Anonymous 2011-12-27 20:57

30 Name: Anonymous 2011-12-27 21:06

31 Name: Anonymous 2011-12-27 21:19

32 Name: Anonymous 2011-12-27 21:20

33 Name: Anonymous 2011-12-27 21:42

34 Name: Anonymous 2011-12-27 22:01

35 Name: Anonymous 2011-12-27 22:30

36 Name: Anonymous 2011-12-27 22:59

37 Name: Anonymous 2011-12-28 1:22

38 Name: Anonymous 2011-12-28 12:27

Name: Anonymous 2011-12-27 13:41

Name: Anonymous 2011-12-27 14:01

Name: Anonymous 2011-12-27 14:42

Name: Anonymous 2011-12-27 15:16

Name: Anonymous 2011-12-27 16:26

Name: Anonymous 2011-12-27 16:35

Name: Anonymous 2011-12-27 17:18

Name: Anonymous 2011-12-27 17:24

Name: Anonymous 2011-12-27 17:38

Name: Anonymous 2011-12-27 17:39

Name: Anonymous 2011-12-27 18:08

Name: Anonymous 2011-12-27 18:25

Name: Anonymous 2011-12-27 18:44

Name: Anonymous 2011-12-27 18:55

Name: Anonymous 2011-12-27 19:00

Name: Anonymous 2011-12-27 19:23

Name: Anonymous 2011-12-27 19:27

Name: Anonymous 2011-12-27 19:49

Name: Anonymous 2011-12-27 19:50

Name: Anonymous 2011-12-27 19:55

Name: Anonymous 2011-12-27 19:55

Name: Anonymous 2011-12-27 20:02

Name: Anonymous 2011-12-27 20:10

Name: Anonymous 2011-12-27 20:16

Name: Anonymous 2011-12-27 20:17

Name: Anonymous 2011-12-27 20:40

Name: Anonymous 2011-12-27 20:51

Name: Anonymous 2011-12-27 20:51

Name: Anonymous 2011-12-27 20:57

Name: Anonymous 2011-12-27 21:06

Name: Anonymous 2011-12-27 21:19

Name: Anonymous 2011-12-27 21:20

Name: Anonymous 2011-12-27 21:42

Name: Anonymous 2011-12-27 22:01

Name: Anonymous 2011-12-27 22:30

Name: Anonymous 2011-12-27 22:59

Name: Anonymous 2011-12-28 1:22

Name: Anonymous 2011-12-28 12:27