Fast Line drawing

Go To Last Post
10 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi,

I'm looking for a algorithm to draw line in a array of 256x256, it must be a very fast algorithm and I must draw one point on 5 points to speed up this function, I will be please if someone can share this knowledge with me.

PS: No float.

Thanks

Yours truly,
Sylvain Bissonnette
www.microsyl.com

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I guess you already know about:

http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm @ Wikipedia

This page has some fun tools on it:

http://www.cs.unc.edu/~mcmillan/...

(and a benchmarking program that compares the speed of different algorithms)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I know how to draw 8 pixels horizontally eight times faster than the regular bresenham line draw.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

I know how to draw 8 pixels horizontally eight times faster than the regular bresenham line draw.

Then just rotate that line.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I don't understand your point "draw 8 pixels and rotate that line"

Yours truly,
Sylvain Bissonnette
www.microsyl.com

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Bob was teasing, in that typically drawing a horizontal (and/or vertical) line segment of 8 bits/one byte is often >>the<< primitive--the way you output to a graphics LCD. Thus, that can set 8 points at once, instead of 8 draw-a-point primitives.

Then, I was also teasing, as rotation is usually painful in terms of clocks although some shortcuts can be done. In very coarse terms, the result of rotating a line segment and then mapping it to a discrete grid of points (pixels?) is analogous to the Bresenham result.

If outputting a line segment is the only thing you need to do, then indeed start with a Bresenham search. That may give you links to "improved Bresenham" or the like.

For general work, I'd suggest starting with one of the Foley-vanDam books. But it has been some years since I did serious low-level graphics work.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

sylvain.bissonne wrote:
I don't understand your point "draw 8 pixels and rotate that line"

They're joking... Bob was referring to simply writing a byte out with all bits set, which will generate 8 pixels at once of a straight line. [this of course will require that the bitmap is arranged horizontally, and that it is indeed 1 bit per pixel] Lee was then joking that you can just rotate that to get a faster result. [note that what Bob proposes is actually a common optimization used for the "special case" lines to increase performance of a line routine]

Stick with Cliff's suggestion, and start with Bresenham. The arrangement of the memory for your display may reveal some optimization's [and challenges] in obtaining an optimal line drawing routine.

Possible optimization's:
Try and do away with directly using the LCD's frame buffer on the LCD controller chip... use a local copy, as Read-Modify-Write routines to/from LCD memory is going to be relatively slow. Then you simply "blit" the local framebuffer to the LCD to refresh the display. [you only need to do this when changes are made, the LCD's framebuffer will take care of the rest]

Also as one byte contains multiple pixels, you can cache the current working byte and only write it out, and read in the next one when you advance to the next memory location. [effective for both local, and remote framebuffes]

Instead of calculating the bit position each time, keep the last used mask, and then shift left/right by one as necessary. [you will never move more than one pixel at a time]

[edit]Lee beat me to it

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yes, Bresenham is the way to go.

How it works? Think y=k*x+b, with k<1 and x goes between end points x0 and x1 in while/for loop. k is just not stored as float, but as k=a/b, where a and b are two integers, and better yet, a=y1-y0 and b=x1-x0.

Then the multiply operation is just an addition for every x pixel in for loop.

If need to draw k>1, then rotate the line so that you draw on y axis instead of x. Of course actual coordinates do not matter since you have x increment and y increment which can be combined as address increment if one address indexes a single pixel.

If you do the math, you can do the same thing to circles, Bresenham has an algorithm for this too.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Jepael wrote:
If you do the math, you can do the same thing to circles, Bresenham has an algorithm for this too.

A common misnomer, Bresenham did not invent the mid-point circle [or ellipse, as it is the same] algorithm. [though the algorithm is based on Bresenham's work with lines]

http://en.wikipedia.org/wiki/Mid...

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I know but many sources name it as the Bresenham circle algorithm, and I learned it by that name in my youth. Sorry for confusing anyone.