Known fast line algorithms ?

[Heaven/TQA]

Pete... the fastes div routines I am aware of are at codebase64.org

[peteym5]

When I did further analysis of the line drawing slope math, I am not sure if doing division will actually help. Even the fastest table driven routine won't help.

 

Exploring other ideals is still an ongoing process.

[Heaven/TQA]

not sure if it was already discussed but did someone checked not Bresenham but Wu instead?

 

http://www.edepot.com/lined.html

 

not the "antialising" issue with Wu but the rest. The Link contains several comparissions of line algorithm with speed comparisons on PC.

Edited January 2, 2015 by Heaven/TQA

[matosimi]

I just found out that eru's routine is faulty. It has issue with DOWN RIGHT RIGHT lines. It is easy to see when you set starting point of each line to center of screen:

 

 

...I also turned off black lines to see it properly. There is also something wrong in opposite quadrant, but it is not that obvious...

 

Proof: drawto15.xex

 

Btw, it would be nice to if someone could fix it, I have no energy to study how it works...

Edited March 1, 2015 by matosimi

[matosimi]

...it was not that hard:

 

 

line 200 was missing

 

result:

 

 

Source and XEX binary:

erudraw(fixed).zip

[NorthWay]

Exiting my lurk&stealth mode I'd like to suggest a few things here.

 

The first one I have been twisting my brain to remember and have googled in vain. I am pretty sure there was a write-up of an algorithm in old venerable BYTE magazine, probably around 1990 give or take a year, that did plot two pixels at once by using the inherent characteristic that you knew that compared to the first pixel the next pixel could only occupy one of three neighbouring positions.

UPDATE:

This one seems to be along the same lines https://smartech.gatech.edu/bitstream/handle/1853/3632/93-22.pdf

 

The second one is the other version of Bresenham which you can find a reference to here http://www.phatcode.net/res/224/files/html/ch36/36-01.html

Edited March 17, 2015 by NorthWay

[Heaven/TQA]

Eru made mistake?

 

http://www.edepot.com/algorithm.html

[peteym5]

I opened the books on my routine again this week. One thing I had an ideal is modifying the slope math and where it branches if it is not time to change the row or column. The theory is instead of branching ahead to the instruction that counts down the pixel length of line is to branch back into the loop until it is time to change row or column. Then count down the number of times the routine needs to change the row or column instead. Early tests look promising. It knocks off 5 clock cycles inside the loop unless in needs to do the row/column change. It is slightly faster. I will be testing it with double and quad instances later.

linetest03s.xex

[+Stephen]

I opened the books on my routine again this week. One thing I had an ideal is modifying the slope math and where it branches if it is not time to change the row or column. The theory is instead of branching ahead to the instruction that counts down the pixel length of line is to branch back into the loop until it is time to change row or column. Then count down the number of times the routine needs to change the row or column instead. Early tests look promising. It knocks off 5 clock cycles inside the loop unless in needs to do the row/column change. It is slightly faster. I will be testing it with double and quad instances later.

That's cool.

[fox]

For my Bresenham routine see mocap/mocap.asx in http://numen.scene.pl/download/numen_src.zip

[Bryan]

Would it ever be beneficial to change methods depending on the line? Obviously 90's would be easy to special case, but could you make it where some percentage of the lines can use a cheating method?

[JamesD]

Would it ever be beneficial to change methods depending on the line? Obviously 90's would be easy to special case, but could you make it where some percentage of the lines can use a cheating method?

He's already using different code based on slope.

[peteym5]

90s, you can remove the slope calculations and is much faster. I already used routines called "HOZLINE", and "VRTLINE" in several games. I have different versions for drawing lines of pixels and lines of characters (tiles). Drawing horizontal and vertical characters is the method of my "Secretum Labyrinth" games compact 100s of rooms into a small amount of memory. Just need data for the start position, character, and how many characters to go.

 

I successfully tested the new way of branching and it slightly sped things up. Still no where near what would be needed if you want many shapes moving around a game to make "Star Wars" arcade like games move much faster. The Double Instance version works somewhat, Quad Instance just ran into too many issues so I ended up abandoning that procedure.

Edited May 11, 2016 by peteym5

[Mariano DM]

BTW.
My December project. a rotating cube with fast line algorithm. uses DrSid's implementation. it still needs double buffer

https://github.com/marianodominguez/8bit-samples/tree/master/cc65/simple_graph/src
 

 

[tebe]

3d_shortreal.obx 3d_shortreal.pas 3d_shortreal_opt.obx 3d_shortreal_opt.pas

[ClausB]

I can post the line drawing routine from SubLogic's FS1, if there's interest. It builds each byte before writing to RAM, saving many read-or-write cycles on shallow lines.

Edited December 17, 2023 by ClausB

[pirx]

that's a neat idea, surely worth sharing.

here is the draw algo used in scorch: https://github.com/pkali/scorch_src/blob/master/grafproc.asm

it does more than drawing, it also does collisions and length measurement, but is (to my surprise) quite well commented.

[ClausB]

On 12/16/2023 at 12:18 AM, Mariano DM said:

BTW.
My December project. a rotating cube with fast line algorithm. uses DrSid's implementation. it still needs double buffer

https://github.com/marianodominguez/8bit-samples/tree/master/cc65/simple_graph/src
 

 

If you calculate all the endpoints before clearing the screen and drawing the lines, then it would be easier to judge the line drawing speed. Might not even need double buffering then. FS1 does just that and gets by without a double buffer.

Edited December 23, 2023 by ClausB

[ClausB]

Here is the line plotter from SubLogic's A2-FS1, adapted to the Atari. It runs in ANTIC modes F (GR.8), E (GR.15), or D (GR.7) with a restriction: It draws up to 160 horizontal pixels of 2 bits each, so that is half-resolution in GR.8, or only COLOR 3 in GR.15 or 7.

 

The attached ATR includes FS1LINE.OBJ assembled at $7D00, plus LINETEST.BAS which plots 150 random lines in GR.8 and measures the plot speed minus the BASIC overhead. Ads in the day claimed a speed of 150 lines per second. I'm getting 250 on average! Don't know how that compares to other routines here, but it sounds pretty fast.

 

 

FS1line.asm FS1LINE.ATR

Edited January 2 by ClausB

[ClausB]

BTW those two examples of self-modifying code were present in FS1, but in different forms.

1. The addition or subtraction to the screen pointer was more complex for the A2, given its non-contiguous memory map.

2. The screen clear loop had hard-coded addresses but the loop branch condition was modified. Avoiding zero page indirect addressing saves about 7000 cycles.

[pirx]

a cursory eye scan says it could be speeded up a lot. overall gain on building full bytes does not seem to be very high, but the idea itself is neat.  

[+Stephen]

3 hours ago, pirx said:

a cursory eye scan says it could be speeded up a lot. overall gain on building full bytes does not seem to be very high, but the idea itself is neat.  

Any ballpark idea of how many lines per second can be drawn - assume a 256 byte (narrow mode) hi-res screen.  It would seem that 64 pixel long lines could be a decent compromise since you'll quickly fill the screen with lines of that size.

[ClausB]

I first ran LINETEST drawing within a 140x96 area, which is what A2-FS1 uses, and got around 400 lines per second.

[tebe]

fast draw by Eru ($49 scanlines)

A2-FS1 ($52 scanlines)

 

FS1line_v0 (mads version, original)

FS1line_v1 (mads version, improvement)

 

fastLine_eru.obx fastLine_eru.pas FS1line_v0.asm FS1line_v1.asm FS1line_v1.obx

[ClausB]

16 minutes ago, tebe said:

fast draw by Eru ($49 scanlines)

A2-FS1 ($52 scanlines)

What are these numbers? Some kind of speed measurement?

 

The added code in front of PLOTL appears unnecessary, since the original code checks direction and swaps with BCC L1C3E.