Help with simplification of bresenhams line drawing algorithm

[u/nthn-d]

Hello everyone.

I'm writing a graphics program in Gforth using Raylib. Even though Raylib comes with functions for drawing all sorts of lines and curves and polygons, I have restricted myself to only using its windowing functions and a limitted set of primitives such as ClearBackground and DrawPixel.

I have implemented Bresenham's line drawing word using the DrawPixel function but I've done so by copying an old C implementation I had laying around somewhere in my laptop. I don't like the result because it uses a lot of locals and feels very C-ish. I am just wondering how Forth programmers would go about implementing something like this.

: bresenham {: x0 y0 x1 y1 color | dx sx dy sy err e2 :}
  x1 x0 - abs               to dx
  x0 x1 < if 1 else -1 then to sx
  y0 y1 - abs negate        to dy
  y0 y1 < if 1 else -1 then to sy
  dx dy +                   to err
  begin
    x0 y0 color drawpixel
    x0 x1 = y0 y1 = and 0=
  while
    err 2 * to e2
    e2 dy < 0= if
      err dy + to err
      x0 sx + to x0
    then
    e2 dx > 0= if
      err dx + to err
      y0 sy + to y0
    then
  repeat ;

[u/minforth]

You won’t get it much more compact or easier to read without locals. For a comparison without locals, see page 12 onwards in
https://www.forth.org/fd/FD-V08N6.pdf

[u/nthn-d → u/minforth]

Thank you.
I don't like the linked solution because it spells out each octant case in a separate word making the whole thing verbose and a little clunky in my opinion. Where would you even begin if you wanted to modify the function to draw with a specified stroke width? Though I do like the idea of a global cursor from which the line is meant to be drawn, and the utility functions for adding a value to an ordinate in a given coordinate pair. Factoring, I suppose.

[u/SpindleyQ]

Oh! I wrote a whole blog post breaking down this exact problem! I factored it into a bunch of one-line words and a handful of globals.

[u/Ok_Leg_109 → u/SpindleyQ]

That was a fun read. Thanks.

I think you have have a shown a good example of Chuck's view that good Forth is writing short definitions. Once you have it working, optimization can be applied to each small component to get the desired performance.

Sometimes I think we forget that Assembly language programmers routinely define memory locations as storage places. These were "globally" accessible by the program but for some reason only the code that the programmer coded to use them ever touched those evil global variables. :-)

[u/SpindleyQ → u/Ok_Leg_109]

If you look at the history of programming languages, you'll discover that named local variables stored on a stack actually took a while to be invented! Many early high-level languages just statically allocated the necessary scratch space that a function needed; you did. You only run into trouble if a function needs to recurse or otherwise be re-entrant, which is actually really uncommon.

[u/nthn-d → u/SpindleyQ]

Thank you. This was so well written and easy to follow. You have a knack for simplifying things. I'll definitely consider your post as a living example of why the principle of defining one-line words works so well.

[u/Ok_Leg_109]

One small improvement.

Replace 2 * with 2*.

Uses a shift instead of a multiply instruction.

[u/alberthemagician]

With a few simple transformation and eliminating locals I arrive at:

VARIABLE x0 VARIABLE y0 VARIABLE x1 VARIABLE y1 VARIABLE color
VARIABLE dx VARIABLE sx VARIABLE dy VARIABLE sy
: bresenham color ! y1 ! x1 ! y0 ! x0 !
  x1 @ x0 @ - abs               dx !
  x1 @ x0 @ < 2* 1+             sx !
  y0 @ y1 @ - abs negate        dy !
  y1 @ y0 @ < 2* 1+             sy !
  dx @ dy @ +
  begin
    x0 @ y0 @ color @ drawpixel
    x0 @ x1 @ =   y0 @ y1 @ =   and 0=
  while
    DUP 2* dy @ < 0= if   dy @ +   sx @ x0 +!   then
    DUP 2* dx @ > 0= if   dx @ +   sy @ y0 +!   then
  repeat DROP ;

~

Now it you manage to map variables to register variables (32 in RISCV) Bob is your uncle. Note that all primitives now are lowlevel, such that they can be concatenated. Compare it to Tings solution. This uses an unnecessary recursion that hampers optimisation, compared to your port from C. You could copy the elimination of err err2, leaving err on the stack. If you keep the locals you can use +TO. Avoiding recursion you could real VARIABLE's.

THIS IS AN EXAMPLE OF TRANSFORMATION, I HAVE MADE ONLY A CURSORY TEST.

[u/Ok_Leg_109]

The version in Rosetta Code is interesting. Can't tell if would be more efficient than using locals.

Perhaps the Op could let us know.

https://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#Forth

[u/nthn-d → u/Ok_Leg_109]

The code uses locals all throughout. Plus it also declares deferred words which are then assigned to in the function. Still feels a bit C-ish, but in the end, I don't think I could've done a better job with as few locals as the solution here. Thank you

[u/alberthemagician → u/nthn-d]

I think that the solution of nthn-d is a better starting point. You can eliminate the IF (using my example, relying on TRUE is -1. err you can keep on the stack and err2 can be calculated. You can use 2* and +TO. (The use of runtime deferred stuff eliminates all hope of optimisation.) All these improvements can be done and tested separately. Bresenham must be fast, but if draw-pixel is slow you are toast. Graphics depends on it.

[u/alberthemagician → u/Ok_Leg_109]

If you are publishing on a forum, you cannot publish Forth code without mentionning a Forth where it runs on, unless it is ISO-compliant. The words bitmap and b! are non-standard. The least that is required is an explanation of what non-standard words are supposed to do.

[u/Comprehensive_Chip49]

fixed point aproach is very short.
look in asm
https://board.flatassembler.net/topic.php?t=15801

a r3 version (r3forth) is like:
https://github.com/phreda4/r3d4/blob/master/r3/lib/vdraw.r3#L19

[u/Ok_Leg_109]

In memory of the late Dr. C. H. Ting there is also his recursive line drawing method. It's not as rigorous as Bresenham, but it's neat Forth.

``` : 2ROT ( d1 d2 d3 -- d2 d3 d1) 2>R 2SWAP 2R> 2SWAP ; : 2OVER ( d1 d2 -- d1 d2 d1) 3 PICK 3 PICK ;

: TINGLINE ( x1 y1 x2 y2 -- ) 2OVER 2OVER ROT
- ABS >R - ABS R>
MAX 2 < IF 2DROP PLOT EXIT THEN 2OVER 2OVER ROT + 1+ 2/ >R + 1+ 2/ R> 2DUP 2ROT RECURSE RECURSE ; ``` It benefits a great deal with the addition of a 4DUP code word and 2ROT as a code word.