Line routine - Second attempt

Here you can ask questions or provide insights about how to use efficiently 6502 assembly code on the Oric.
User avatar
Dbug
Site Admin
Posts: 4437
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Line routine - Second attempt

Post by Dbug »

Since the version of LineBench I uploaded the other day was some old attempt made when I was working on ULA Paint, I decided to work a bit and clean up the code.

The previous version had a score of 856 to draw 440 line (2275 for the BASIC ROM routine), the new one is down to 822, while using quite a lot less memory (less intermediate code and tables).

You can find it here:
http://www.defence-force.org/ftp/forum/ ... ench-2.zip

Don't hesitate to participate by giving suggestion, and even better provide a faster version.

Ideally we are looking for two kind of "faster" versions:
- The faster one that does not use too much memory (good for games)
- The insanely faster one that can gobble half of the memory (usable for demo records and stuff like that)

Have fun !
User avatar
Dbug
Site Admin
Posts: 4437
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Post by Dbug »

And here is a new version.

The last published was down to 822, Twilighte took a look and managed to reduce it to nearly 800, and since I had a day off, I spent some time on the code today, both optimizing even more the code down to 793 (yeah, we are under 800 !), plus additional code path for totaly vertical and totaly horizontal lines.

You can find it here:
http://www.defence-force.org/ftp/forum/ ... ench-3.zip

I'm still open for all suggestions and optimisations. A faster line routine is good for everybody :)
User avatar
waskol
Flight Lieutenant
Posts: 414
Joined: Wed Jun 13, 2007 8:20 pm
Location: FRANCE, Paris

Post by waskol »

I will have a look to those pieces of code. :wink:
highwayman
Flying Officer
Posts: 148
Joined: Fri Oct 12, 2007 8:08 pm

Post by highwayman »

Q:

about drawing circles.
is it my memory failing, or was the atmos rom *way* faster than the original 1.0?
User avatar
Dbug
Site Admin
Posts: 4437
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Post by Dbug »

No idea, but whatever the speed it's possible to do WAY better, can even handle clipping while still being at least twice faster :)
User avatar
waskol
Flight Lieutenant
Posts: 414
Joined: Wed Jun 13, 2007 8:20 pm
Location: FRANCE, Paris

Post by waskol »

I can't remember where I got this code but it was supposed to be very very fast. I wonder if it could be adapted in oric asm, with all the screen optimizations you can usually do (you know the tables), pecause the curset function is soooo slow.

Code: Select all

#include <lib.h>

#define setpix(x,y) curset(x,y,2)

void lineTwoStep(int x0, int y0, int x1, int y1)
    {   
        int i,dx,dy,stepx, stepy,length,extras,incr1,incr2,c,d;
         
        dy = y1 - y0;
        dx = x1 - x0;
        
        if (dy < 0) { dy = -dy;  stepy = -1; } else { stepy = 1; }
        if (dx < 0) { dx = -dx;  stepx = -1; } else { stepx = 1; }
        
        setpix(x0,y0);
        setpix(x1,y1);
        if (dx > dy) {
            length = (dx - 1) >> 2;
            extras = (dx - 1) & 3;
            incr2 = (dy << 2) - (dx << 1);
            if (incr2 < 0) {
                c = dy << 1;
                incr1 = c << 1;
 
                d =  incr1 - dx;
                
                for (i = 0; i < length; i++) {
                    x0 += stepx;
                    x1 -= stepx;
                    if (d < 0) {              // Pattern:
                        setpix(x0,y0);        //
                        x0+=stepx;            //
                        setpix(x0,y0);        //  x o o
                        setpix(x1,y1);        //
                        setpix(x1,y1);
                        x1 -= stepx;
                        d += incr1;
                    } else {
                        if (d < c) {			// Pattern:
                            setpix(x0,y0);		//      
                            x0+= stepx;               //
                            y0 += stepy;              //      o
                            setpix(x0,y0);		//  x o
                            setpix(x1,y1);		//
                            x1-=stepx;
                            y1 -= stepy;
                            setpix(x1,y1);
                        } else {
                            y0+=stepy;
                            setpix(x0,y0);		// Pattern:
                            x0 += stepx;              //
                            setpix(x0,y0);		//    o o 
                            y1 -= stepy;              //  x  
                            setpix(x1,y1);			
                            x1-=stepx;
                            setpix(x1,y1);			
                        }
                        d+=incr2;
                    }
                }
                if (extras > 0) {
                    if (d < 0) {
                        x0+=stepx;
                        setpix(x0,y0);
                        if (extras > 1) {x0+=stepx; setpix(x0,y0);}
                        if (extras > 2) {x1-=stepx; setpix(x1,y1);}
                    } else
                    if (d < c) {
                        x0+=stepx;
                        setpix(x0,y0);
                        if (extras > 1) {x0+=stepx; y0+=stepy; setpix(x0,y0);}
                        if (extras > 2) {x1-=stepx; setpix(x1,y1);}
                    } else {
                        x0+=stepx; 
                        y0+=stepy;
                        setpix(x0,y0);
                        if (extras > 1) {x0+=stepx;setpix(x0,y0);}
                        if (extras > 2) {x1-=stepx; y1-=stepy; setpix(x1,y1);}
                    }
                }
            } else {
                c = (dy - dx) << 1;
                incr1 = c << 1;
                d =  incr1 + dx;
                
                for (i = 0; i < length; i++) {
                    x0 += stepx;
                    x1 -= stepx;
                    if (d > 0) {  
                        y0 += stepy;
                        setpix(x0,y0);		
                        x0+=stepx;              // Pattern:
                        y0+=stepy;              //
                        setpix(x0,y0);		//      o
                        y1 -= stepy;            //    o
                        setpix(x1,y1);		//  x	
                        x1-= stepx;
                        y1 -= stepy;
                        setpix(x1,y1);		
                        d += incr1;
                    } else {
                        if (d < c) {
                            setpix(x0,y0);
                            x0 += stepx;	      // Pattern:
                            y0 += stepy;        //
                            setpix(x0,y0);      //      o
                            setpix(x1, y1);     //  x o
                            x1 -= stepx;
                            y1 -= stepy;
                            setpix(x1,y1);       
                        } else {
                            y0 += stepy;
                            setpix(x0,y0);   			// Pattern:
                            x0 += stepx;
                            setpix(x0,y0);   			//    o o
                            y1 -= stepy;                    //  x
                            setpix(x1,y1);			
                            x1 -= stepx;
                            setpix(x1,y1);			
                        }
                        d += incr2;
                    }
                }
                if (extras > 0) {
                    if (d > 0) {
                        x0 += stepx;
                        y0 += stepy;
                        setpix(x0,y0);   
                        if (extras > 1) {x0+=stepx; y0+=stepy; setpix(x0,y0);}
                        if (extras > 2) {x1-=stepx; y1-=stepy; setpix(x1,y1);}
                    } else
                    if (d < c) {
                        x0 += stepx;
                        setpix(x0,y0);
                        if (extras > 1) {x0+=stepx; y0+=stepy; setpix(x0,y0);}
                        if (extras > 2) {x1-=stepx; setpix(x1,y1);}
                    } else {
                        x0 += stepx;
                        y0 += stepy;
                        setpix(x0,y0);
                        if (extras > 1) {x0+=stepx; setpix(x0,y0);}
                        if (extras > 2) {
                            if (d > c)
                                {x1-=stepx; y1-=stepy; setpix(x1,y1);}
                            else
                                {x1-=stepx; setpix(x1,y1);}
                        }
                    }
                }
            }
        } else {
            length = (dy - 1) >> 2;
            extras = (dy - 1) & 3;
            incr2 = (dx << 2) - (dy << 1);
            if (incr2 < 0) {
                c = dx << 1;
                incr1 = c << 1;
                d =  incr1 - dy;
                
                for (i = 0; i < length; i++) {
                    y0 += stepy;
                    y1 -= stepy;
                    if (d < 0) {
                        setpix(x0,y0);
                        y0 += stepy;
                        setpix(x0,y0);
                        setpix(x1,y1);
                        y1 -= stepy; 
                        setpix(x1,y1);
                        d += incr1;
                    } else {
                        if (d < c) {
                            setpix(x0, y0);
                            x0 += stepx;
                            y0 += stepy;
                            setpix(x0,y0);
                            setpix(x1,y1);
                            x1 -= stepx;
                            y1 -= stepy;
                            setpix(x1,y1);
                        } else {
                            x0 += stepx;
                            setpix(x0,y0);
                            y0 += stepy;
                            setpix(x0,y0);
                            x1 -= stepx; setpix(x1,y1);
                            y1 -= stepy; setpix(x1,y1);
                        }
                        d+=incr2;
                    }
                }
                if (extras > 0) {
                    if (d < 0) {
                        y0+=stepy; setpix( x0, y0);
                        if (extras > 1) {y0+=stepy; setpix(x0,y0);}
                        if (extras > 2) {y1-=stepy; setpix(x1,y1);}
                    } else
                    if (d < c) {
                        y0+=stepy; setpix(x0,y0);
                        if (extras > 1) {x0+=stepx; y0+=stepy; setpix(x0,y0);}
                        if (extras > 2) {y1-=stepy;setpix(x1,y1);}
                    } else {
                        x0+=stepx; y0+=stepy; setpix(x0,y0);
                        if (extras > 1) {y0 += stepy;setpix(x0,y0);}
                        if (extras > 2) {x1-=stepx; y1-=stepy; setpix(x1,y1);}
                    }
                }
            } else {
                c = (dx - dy) << 1;
                incr1 = c << 1;
                d =  incr1 + dy;
                
                for (i = 0; i < length; i++) {
                    y0 += stepy;
                    y1 -= stepy;
                    if (d > 0) {
                        x0+=stepx; setpix(x0,y0);
                        x0+=stepx; y0+=stepy; setpix(x0,y0);
                        x1-=stepy; setpix(x1,y1);
                        x1-=stepx; y1-=stepy; setpix(x1,y1);
                        d+=incr1;
                    } else {
                        if (d < c) {
                            setpix(x0,y0);
                            x0+=stepx; y0+=stepy; setpix(x0,y0);
                            setpix(x1,y1);
                            x1-=stepx, y1-=stepy; setpix(x1,y1);
                        } else {
                            x0+=stepx; setpix(x0,y0);
                            y0+=stepy; setpix(x0,y0);
                            x1-=stepy; setpix(x1,y1);
                            y1-=stepy; setpix(x1,y1);
                        }
                        d += incr2;
                    }
                }
                if (extras > 0) {
                    if (d > 0) {
                        x0+=stepx; y0+=stepy; setpix(x0,y0);
                        if (extras > 1) {x0+=stepx; y0+=stepy; setpix(x0,y0);}
                        if (extras > 2) {x1-=stepx, y1-=stepy; setpix(x1,y1);}
                    } else
                    if (d < c) {
                        y0+=stepy; setpix(x0,y0);
                        if (extras > 1) {x0+=stepx; y0+=stepy; setpix(x0,y0);}
                        if (extras > 2) {y1-=stepy; setpix(x1,y1);}
                    } else {
                        x0+=stepx; y0+=stepy; setpix(x0,y0);
                        if (extras > 1) {y0+=stepy; setpix(x0,y0);}
                        if (extras > 2) {
                            if (d > c)
                                {x1-=stepx, y1-=stepy; setpix(x1,y1);}
                            else
                                {y1-=stepy; setpix(x1,y1);}

                        }
                    }
                }
            }
        }
    }
That's something I have adapted from a code found on internet.
You can give it a try, it is way faster than Bresnham algorithm.
User avatar
Dbug
Site Admin
Posts: 4437
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Post by Dbug »

Found the original explanation here, with the same source code:
http://cs.unc.edu/~mcmillan/comp136/Lecture6/Lines.html
User avatar
waskol
Flight Lieutenant
Posts: 414
Joined: Wed Jun 13, 2007 8:20 pm
Location: FRANCE, Paris

Post by waskol »

Dbug wrote:Found the original explanation here, with the same source code:
http://cs.unc.edu/~mcmillan/comp136/Lecture6/Lines.html
yes, that's this one ! :P

Otherelse, I some ideas in order to improve it a little bit (to avoid the oric curset function). If you don't mind I will try to use your optimization tables.
User avatar
Dbug
Site Admin
Posts: 4437
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Post by Dbug »

As a matter of fact, the "plot pixel" or whatever similar routine... should be used only for the sole purpose of drawing one single pixel on screen.

For anything else composed of more than one pixel, the pixel plotting should be inlined in the rest of the code, else just the fact of plotting pixels will use most of the cpu time.

Just for reference, if you add ONE nop (or useless CLC/SEC) in the current line routine in the benchmark, the time taken will jump up by about "30" units.

Imagine the cost of a single JSR/RTS to the plot routine :)
User avatar
Dbug
Site Admin
Posts: 4437
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Post by Dbug »

After the discussions about 1337, decided to take a look at 8 bit Bresenham implementations. The version in C= Hacking is very buggy - actually it does not even assemble I believe -

So the last published was down to 796 units, the new code is now down to 676. Not impressive I know, but possibly the setup code could be improved. I'm not quite sure how I could improve the inner loops.

I moved the location of the code now we have a Subversion server, you can find the latest code here:
http://miniserve.defence-force.org/svn/ ... linebench/

So Chema, could you try to integrate that one in 1337 and tell us if it improves the framerate in any perceivable way?

And as last time, I'm still open for all suggestions and optimisations: A faster line routine is good for everybody :)
User avatar
Chema
Game master
Posts: 3013
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Post by Chema »

Dbug wrote: So Chema, could you try to integrate that one in 1337 and tell us if it improves the framerate in any perceivable way?
Ok I integrated into the shipdemo test program and it improves the time in 1 "unit" of 1/100ths of second. This is quite a constant value, but most noticeable in some models, where there are more and longer lines to draw.

Would need a more accurate timing to be sure, but this could be a good first approximation.

I think, however, there are some "artifacts", some extra pixels at the end of some lines and even a single pixel in the middle of a line which is drawn 1 pixel up. This only happens sometimes.

Would a method for "crunching" all the pixels in a single scan and plot them with only one sta improve this even further?

Cheers
User avatar
Dbug
Site Admin
Posts: 4437
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Post by Dbug »

For the artefacts, would be nice if you could give me some set of coordinates I can test with.

I also published a new version, which goes from 676 to now 644 :)

For the chunking, I guess it could be doable by adding some metaflags in the _TableBit6Reverse table, have to think about it.
User avatar
Iapetus
Flying Officer
Posts: 135
Joined: Thu Mar 19, 2009 10:47 pm

Post by Iapetus »

wow from 856 to 644 is a huge leap, well done Dbug, I am sure you can still improve this :)

Continue the good work :D
JamesD
Flight Lieutenant
Posts: 358
Joined: Tue Nov 07, 2006 7:38 am

Post by JamesD »

Algarbi wrote:wow from 856 to 644 is a huge leap, well done Dbug, I am sure you can still improve this :)

Continue the good work :D
He still has to fix the artifacts so that might go up a few cycles but it's definitely a nice gain. I think more savings is certainly possible but the more you save, the more effort required to get those savings.

I think the only significant improvement will be in devising a way to calculate/write all pixels for a byte in one shot, possibly reducing the number of OR operations with screen memory.

I played with the idea of calculating how many horizontal bits you write for each x. Then you just perform a table lookup of the bits and OR the byte with the screen destination. However, tables of possible bit patterns is a problem since the size of the table increases by 1 each time you add a horizontal pixel. (see bit pattern tables below). There may also be a different number of pixels per byte depending on the current x value, so I didn't really figure out a practical way to do this except for horizontal lines where I don't need to perform as many lookups.


10000000
01000000
00100000
00010000
00001000
00000100
00000010
00000001

10000000
11000000
01100000
00110000
00011000
00001100
00000110
00000011
00000001

10000000
11000000
11100000
01110000
00111000
00011100
00001110
00000111
00000011
00000001

10000000
11000000
11100000
11110000
01111000
00111100
00011110
00001111
00000111
00000011
00000001

etc...



To do this for horizontal lines you still have to draw the ends of the line separately but everything in between is just a loop writing bytes with all pixels set. And the ends can potentially be done with a lookup but it requires a table for each end. This offers a bigger gain on the CoCo/MC-10 where there are 8 pixels / byte in hi-res, the CPUs have 16 bit index registers, and the screen layout makes for easy math. I'm not sure about the Oric with the 6502, 6 pixels / byte, and it's screen layout.


Basic algorithm on CoCo is something like this (not exactly 100% C but you'll get the idea):

Code: Select all

#define BYTESPERLINE 32
#define PIXELSPERBYTE 8

If X2 < X1 then swap points
if X2 -X1 < PIXELSPERBYTE + 1   then special case because less than 2 bytes involved

; note that shifts work well for the math on this screen layout
; if you have to use preincrement then subtract one at end of following line
; calculate starting address of first byte
Address = ScreenBase + (Y * BYTESPERLINE) + (X1 / PIXELSPERBYTE )  

; lookup pixels to set and write leftmost byte
*(Address++) |=  (*(LeftTable + (X1 & 7))) ; set bits in left byte
 I =(X2-X1-2)

;loop for middle bytes/pixels if needed (test takes place before a write)
DO 
 *(Address++) = 255   ; 255 = set all bits on middle bytes
WHILE (I-- > 0)

; lookup pixels to set and write rightmost byte
*(Address++) |=  (*(RightTable + (X2 & 7)))  ; set bits in right byte
CoCo tables:
; Left end of horizontal line
11111111
01111111
00111111
00011111
00001111
00000111
00000011
00000001

; Right end of horizontal line
10000000
11000000
11100000
11110000
11111000
11111100
11111110
11111111

Oric version would have smaller tables due to less pixels / byte. Attribute bits would need to be set to what you want to use.
The math however might be ugly unless you can just lookup values... which I think I used anyway as it was faster.
; Left end of horizontal line
00111111
00011111
00001111
00000111
00000011
00000001

; Right end of horizontal line
00100000
00110000
00111000
00111100
00111110
00111111

I hope I'm making sense here but it's late, I'm tired, and that might be the formula for chocolate milk for all I know.


Just an FYI, the C64 version of Elite doesn't draw circles with a normal circle routine. It looks like it's drawing 4 lines / quarter since lines are a probably a little faster.

<edit>
Notice the last three bits of the X represent the pixel number within a byte and the top bits represent the byte number on a given screen line on the CoCo.

The tables can overlap by a byte is you put the right table first and the left table second. It saves a byte.
User avatar
thrust26
Officer Cadet
Posts: 49
Joined: Wed Jan 27, 2010 7:34 pm
Location: Düsseldorf, Germany

Post by thrust26 »

JamesD wrote:I think the only significant improvement will be in devising a way to calculate/write all pixels for a byte in one shot, possibly reducing the number of OR operations with screen memory.
Steve Judd has developed a quite brilliant routine (C=Hacking, ussue 10) for exactly this, which works without any tables in the inner loop.

Code: Select all

        initialize x, dx, etc.
        xold = x
        take a step in x: LSR X
        have we hit the end of a column?  If so, then plot and check on y
        is it time to take a step in y?
        if not, take another step in x
        if it is, then let a=x EOR xold
                       plot a into the buffer
                       let xold=x
        keep on going until we're finished
It saves a lot of time for lines where dX > 2 * dY on the C64 the Atari 2600 (~33% saving there). Maybe it can somehow be adapted for the Oric?
Have fun!
thrust26
Post Reply