Line drawing algorithm, anyone create one in spin?

Timothy D. Swieter · 2008-03-17 14:20

I have been working on my uOLED display driver (clocking data to the OLED from the Propeller) and the graphics driver (an 8-bit graphics engine).· Right now the display driver is working great.· It is written in ASM and the memory in the Prop is being written to the memory of the OLED in about 6ms per frame!
·
Now, I am trying to piece together some graphics drawing routines.· I am writing them in Spin first and then I will convert to a graphics engine in ASM.· The bitmap memory·color depth is·8-bit per pixel.· I have a plot pixel function working.· Next is a line algorithm.· I looked through the Hydra book and there were only a couple references, nothing major.· I also looked at the Black Art e-book on the Hydra CDROM and that helped a little.· I mostly did searches on Google for Bresenham to read more about his work.
·
Anyway, has anyone created a line drawing algorithm in Spin that works for all line slopes?· I have a partial line function working, but it only applies to slopes from -1 to 1 and sometimes I think it is still not right.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter

www.brilldea.com·- check out the uOLED-IOC, an I/O expansion for the uOLED-96-PROP
www.tdswieter.com

One little spark of imagination is all it takes for an idea to explode

OwenS · 2008-03-17 15:35

Slope drawing is gonna need some form of point arithmetic, whether it be fixed or floating point, else errors will accumulate and you won't get the line you want. Bressenham's algorithm is probably the best general line drawing algorithm, but it's by no means ideal: It needs a division, which is certainly not fast without ALU support

Phil Pilgrim (PhiPi) · 2008-03-17 18:17

Timothy,

Give this a try. It's a line drawing algorithm that uses no multiplies or divides and works for any pair of endpoints. I've transcribed it from an assembly routine and haven't tested it, so let me know if it doesn't work and I'll fix it.

pub drawline(x0, y0, x1, y1) | dx, dy, difx, dify, sx, sy, ds

'Draw a straight line from (x0, y0) to (x1, y1).

  difx := ||(x0 - x1)           'Number of pixels in X direciton.
  dify := ||(y0 - y1)           'Number of pixels in Y direction.
  ds := difx <# dify            'State variable change: smaller of difx and dify.
  sx := dify >> 1               'State variables: >>1 to split remainders between line ends.
  sy := difx >> 1
  dx := (x1 < x0) | 1           'X direction: -1 or 1
  dy := (y1 < y0) | 1           'Y direction: -1 or 1
  repeat (difx #> dify) + 1     'Number of pixels to draw is greater of difx and dify, plus one.
    drawpoint(x0, y0)           'Draw the current point.
    if ((sx -= ds) =< 0)        'Subtract ds from x state. =< 0 ?
      sx += dify                '  Yes: Increment state by dify.
      x0 += dx                  '       Move X one pixel in X direciton.
    if ((sy -= ds) =< 0)        'Subtract ds from y state. =< 0 ?
      sy += difx                '  Yes: Increment state by difx.
      y0 += dy                  '       Move Y one pixel in Y direction.

pub drawpoint(x, y)

'Your point-drawing routine.

-Phil

Jasper_M · 2008-03-17 18:44

Phil Pilgrim (PhiPi) said...
Timothy,

  dx := (x1 < x0) | 1           'X direction: -1 or 1
  dy := (y1 < y0) | 1           'Y direction: -1 or 1

Shouldn't those be


  dx := (x1 < x0) + 2           'X direction: -1 or 1
  dy := (y1 < y0) + 2           'Y direction: -1 or 1

Oops never mind

mpark · 2008-03-17 21:49

OwenS said...
Slope drawing is gonna need some form of point arithmetic, whether it be fixed or floating point, else errors will accumulate and you won't get the line you want. Bressenham's algorithm is probably the best general line drawing algorithm, but it's by no means ideal: It needs a division, which is certainly not fast without ALU support

Bresenham doesn't need division.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Michael Park

PS, BTW, and FYI:
To search the forum, use search.parallax.com (do not use the Search button).
Check out the Propeller Wiki: propeller.wikispaces.com/

Beau Schwabe · 2008-03-17 22:20

Timothy D. Swieter,

There is an ASM line function that should work for you from the VGA text and graphics demo... I derived this from the TV graphics demo, but if I remember correctly you must draw the line from BOTH end points to the center or continue to the opposite end once you have determined if the slope of the line is Vertically or Horizontally dominate.

http://forums.parallax.com/showthread.php?p=606957

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

JT Cook · 2008-03-17 23:35

I don't have a line drawing solution, I just had a quesion on the driver. Is it just an bit bitmap that then gets drawn to the OLED? Also how is the palette setup? Any screenshots you can post?

Timothy D. Swieter · 2008-03-17 23:40

Thank you guys for the quick response. I tried Phil's algorithm and it works. It looks very familiar after studying the Bresenham's algorithm. As I transisition my way into an ASM algorithm I will look into Beau's post and also dissect the Parallax Graphics ASM.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter

www.brilldea.com·- check out the uOLED-IOC, an I/O expansion for the uOLED-96-PROP
www.tdswieter.com

One little spark of imagination is all it takes for an idea to explode

Timothy D. Swieter · 2008-03-17 23:57

Hi JT -
In a couple days I will be making a post with further details about the OLED driver and the basic graphics engine (really just a set of routines at this point).· Yes, the memory is just bitmap memory.· The system is setup with an on-screen memory and an off-screen memory but in reality you could eliminate one and just have the graphics engine and display driver work in series (i.e. draw the image in memory and then update the OLED).·
There isn't a palette in the driver.· I am using the OLED in 8-bit mode which allows for 256 colors with 3-bits for R, 3-bits for G and 2-bits for blue.· There are some advance features of the OLED for grayscale and PWM adjustment, but I haven't messed with those.· In time maybe the display driver can be expanded.
Stay tuned for pics/video and·a further post.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter

www.brilldea.com·- check out the uOLED-IOC, an I/O expansion for the uOLED-96-PROP
www.tdswieter.com

One little spark of imagination is all it takes for an idea to explode

Timothy D. Swieter · 2008-03-18 01:56

Phil - do you happen to have a circle algorithm too? I will credit you in the functions I am creating.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter

www.brilldea.com·- check out the uOLED-IOC, an I/O expansion for the uOLED-96-PROP
www.tdswieter.com

One little spark of imagination is all it takes for an idea to explode

AndreL · 2008-03-18 02:46

The integer circle algorithm works in the same manner the line algorithm does, it basically evaluates a "decision" variable. In the circle case, its a 2nd order problem. Anyway, there are a zillion integer circle algorithms on internet, but the source of most of this is "Principles of interactive computer graphics", there is a section that covers these kind of digital differential analysis. I think I might have derived the algorithm in one of my graphics books, but I would have to look. Anyway, its 50 lines of code if that, and then it draw 1 qudrant or octant and you reflect the others. If you want a generalized elipse then its a little less optimized.

Andre'

Timothy D. Swieter · 2008-03-18 02:48

OK. After some Google searches I was started to get the feeling of more complicated alogirthm, that is why I asked here.

I will focus my attention on a couple other functions to finish before I post the code.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter

www.brilldea.com·- check out the uOLED-IOC, an I/O expansion for the uOLED-96-PROP
www.tdswieter.com

One little spark of imagination is all it takes for an idea to explode

Phil Pilgrim (PhiPi) · 2008-03-18 03:03

Timothy,

No, sorry, I don't have one handy. The assembly program that the line routine came from doesn't do circles.

-Phil

AndreL · 2008-03-18 03:41

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

Andre'

Timothy D. Swieter · 2008-03-18 04:28

Thanks Andre for the kick to Wikipedia.· I translated the algorithm found there into SPIN.· Here is the code:

'**************************************
PUB plotCircle(_x0, _y0, _radius, _color) | f, ddF_x, ddF_y, x, y
'**************************************
'' Plot a circle with center _x0,_y0 and radius _radius with the appropriate 8-bit color
''
''  _x0, _x1   - coordinate of the center of the circle
''  _radius    - radius, in pixels, of the circle
''  _color     - 8-bit color value (RRRGGGBB)
 
  f := 1 - _radius
  ddF_x := 0
  ddF_y := -2 * _radius
  x := 0
  y := _radius
  plotPixel(_x0, _y0 + _radius, _color)
  plotPixel(_x0, _y0 - _radius, _color)
  plotPixel(_x0 + _radius, _y0, _color)
  plotPixel(_x0 - _radius, _y0, _color)
 
  repeat while x < y
    if f>= 0
      y--
      ddF_y += 2
      f += ddF_y
 
    x++
    ddF_x += 2
    f += ddF_x + 1
    plotPixel(_x0 + x, _y0 + y, _color)
    plotPixel(_x0 - x, _y0 + y, _color)
    plotPixel(_x0 + x, _y0 - y, _color)
    plotPixel(_x0 - x, _y0 - y, _color)
    plotPixel(_x0 + y, _y0 + x, _color)
    plotPixel(_x0 - y, _y0 + x, _color)
    plotPixel(_x0 + y, _y0 - x, _color)
    plotPixel(_x0 - y, _y0 - x, _color)

The code works well for radi that are smaller, but as the circle expands to larger radi it begins to look more polygonish (8 sides).· I will have to read more about this.· I bet it has to deal with the simplifications and·the reflections.· For now though it will work to express the point of the 8-bit driver.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter

www.brilldea.com·- check out the uOLED-IOC, an I/O expansion for the uOLED-96-PROP
www.tdswieter.com

One little spark of imagination is all it takes for an idea to explode

Beau Schwabe · 2008-03-18 05:09

Timothy,

Would a generic sine/cosine algorithm work for drawing circles? or would that be too slow? You could cut it into quadrants so that the sine/cosine would only need to calculate for 1/4 of the circle and just translate the remaining 3/4 and that would speed it up a little bit.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

Gerry Keely · 2008-03-18 16:39

The SSD1331 driver has built-in line(register 0x21) and rectangle(register0x22) drawing routines

http://www.4dsystems.com.au/downloads/micro-OLED/uOLED-96-PROP/Docs/Pdf/SSD1331.pdf



Regards

Gerry

OwenS · 2008-03-18 21:02

mpark said...

OwenS said...

Slope drawing is gonna need some form of point arithmetic, whether it be fixed or floating point, else errors will accumulate and you won't get the line you want. Bressenham's algorithm is probably the best general line drawing algorithm, but it's by no means ideal: It needs a division, which is certainly not fast without ALU support

Bresenham doesn't need division.

Oops, yes. I never thought about that method of implementing it (I've been doing most of my graphics work on architectures with hardware divisors; In that case, division can be faster, depending on the speed of your divisor)

Timothy D. Swieter · 2008-03-18 23:58

Thank you guys for the responses.

Gerry - I realize the oled driver has built in drawing algorithms, but I am avoiding those. I created a display driver which clocks video memory into the OLED at 6ms per frame. I am not working on an 8-bit graphics driver to draw in the Propeller memory.

I did figure out a circle routine from another post in the forum, I think it was Paul Sr. I also added sprite ability and text ability. Again it is just a collection of SPIN routines at this time, so it isn't fast, but in time I hope to transfer to ASM. I am cooking up a small demo now and will post in a day or so.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter

www.brilldea.com·- check out the uOLED-IOC, an I/O expansion for the uOLED-96-PROP
www.tdswieter.com

One little spark of imagination is all it takes for an idea to explode

Timothy D. Swieter · 2008-03-19 12:40

I made a post in the Propeller forum regarding the uOLED-96-PROP display driver and SPIN graphics driver I am creating.· I didn't post the code yet, but soon I will.· For now there is demo program you can watch on YouTube or download via an EEPROM file.·

http://forums.parallax.com/showthread.php?p=716659

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter

www.brilldea.com·- check out the uOLED-IOC, an I/O expansion for the uOLED-96-PROP
www.tdswieter.com

One little spark of imagination is all it takes for an idea to explode

Timothy D. Swieter · 2008-03-22 11:54

I posted the code in the object exchange for the 8-bit ASM and graphics driver. Check the reference post above for further details.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter

www.brilldea.com·- check out the uOLED-IOC, an I/O expansion for the uOLED-96-PROP
www.tdswieter.com

One little spark of imagination is all it takes for an idea to explode

pharseid · 2008-04-09 21:16

· I once used Bresenham's algorithm to draw polygons too. I used an array with 2 columns and as many rows as the vertical height of the screen. I would consider the points of the polygon 2 at a time and write the x coordinate calculated by the algorithm into one element of the array (the y coordinate implied by the position in the array). When the whole polygon had been processed, I would then render the array doing a line fill for each pair of coordinates in the array (for the max and min Y coordinates of that polygon).

-phar

Lord Steve · 2008-04-17 20:39

In case anyone's interested.· Here's a SPIN Line drawer.· Works in all quadrants.· Works with byte-sized pixels.

PUB Line(x0, y0, x1, y1, color) | pScreen, dx, dy, major, minor, majorStep, minorStep, error, errorAdjust, errorStep

  pScreen := @screen + y0*SCREEN_WIDTH + x0

  dx := x1 - x0
  dy := y1 - y0

  if ||dx => ||dy
    major := ||dx
    minor := ||dy
    majorStep := 1
    if dx < 0
      majorStep := -1
    minorStep := SCREEN_WIDTH
    if dy < 0
      minorStep := -SCREEN_WIDTH
  else
    major := ||dy
    minor := ||dx
    majorStep := SCREEN_WIDTH
    if dy < 0
      majorStep := -SCREEN_WIDTH
    minorStep := 1
    if dx < 0
      minorStep := -1

  error := major
  errorAdjust := major << 1
  errorStep := minor << 1

  repeat major + 1
    byte[noparse][[/noparse]pScreen] := color
    pScreen += majorStep
    error += errorStep
    if error => errorAdjust
      error -= errorAdjust
      pScreen += minorStep

Line drawing algorithm, anyone create one in spin?

Comments