CPCWiki forum

Hi folks.

Wow, has that much time passed since my last CPC project?!?!
I've been away from the scene a bit since I finished RUNCPC last year, but I guess that old itch never goes away...

One thing I've always wanted to do is mess around with drawing lines, and since cpcTelera doesn't yet have any line drawing functions, why not give it a go?
I managed to get a mode 0 Bresenham routine working quite easily, but got stuck for some time on modes 1 and 2.

Fortunately I found this wonderful article:
CPCRULEZ > CODING > SDCC TUT'S PAR STEPHBB75 > Dessiner en mode 1 (http://cpcrulez.fr/coding-crossdev_sdcc-04-dessiner_en_mode_1.htm)

With a bit of help from google translate, I was able to quickly add mode 1 & 2 to my little test program.
8)

The attached dsk contains a binary compiled from pure SDCC (in cpcTelera), and therefore is not as fast as it will ultimately become.
I think the line drawing speeds are useful as-is for non-game applications, but for real-time situations (like games) it is too slow.

I've got quite a lot left to do.
- optimised vertical / horizontal / perfect-diagonal routines
- line clipping
- conversion of critical routines to asm

Line clipping is a tricky one.
I've researched 4 different techniques, each with their own pros and cons, but I'm not sure I want to go with any of them.
In a game, lines will likely be relatively short, so it might be more efficient to simply rush through Bresenham's without the pixel plotting, until the x,y are on-screen.

We shall see...

For anyone interested, here is the first version of the main.c source.
It's not pretty, as it's just experimenting at the moment.
I'm particularly keen on improving mode 1 and 2 speeds, but I don't really know how to yet (though I've seen hints from others - TFM? - in the past that it may be possible to use bit-level operations to really speed up mode 2).

[EDIT] There are some more tests included now. If anyone is interested in the latest source code at any time, please feel free to ask.


#include <cpctelera.h>

#define SCR_VMEM (u8*)0xC000

#define MODE0_LIMIT 159
#define MODE1_LIMIT 319
#define MODE2_LIMIT 639

void runTest();
void populate_yAddress();

void drawLine(i16,i16,i16,i16);
void drawLineMode0(i16,i16,i16,i16);
void drawLineMode1(i16,i16,i16,i16);
void drawLineMode2(i16,i16,i16,i16);

void putPixelMode0(u8,u8);
void putPixelMode1(u16,u8);
void putPixelMode2(u16,u8);

u8 const g_palette[16]={
    0x00, // black
    0x1a, // brightWhite
    0x0d, // white
    0x12, // brightGreen
    0x06, // brightRed
    0x02, // brightBlue
    0x18, // brightYellow
    0x00, // black
    0x00, // black
    0x00, // black
    0x00, // black
    0x00, // black
    0x00, // black
    0x00, // black
    0x00, // black
    0x00, // black
};

u8 lineColour;

u8 lineMask0_1A,lineMask0_1B;
u8 lineMask0_2A,lineMask0_2B;
u8 lineMask0_4A,lineMask0_4B;
u8 lineMask0_8A,lineMask0_8B;

u8 lineMask1_1A,lineMask1_1B,lineMask1_1C,lineMask1_1D;
u8 lineMask1_2A,lineMask1_2B,lineMask1_2C,lineMask1_2D;

u8 lineMask2_1A,lineMask2_1B,lineMask2_1C,lineMask2_1D,lineMask2_1E,lineMask2_1F,lineMask2_1G,lineMask2_1H;

u8 mode;
u8 testRun;

u8* yAddress[200];

void main(void){
    cpct_disableFirmware();

    cpct_fw2hw(g_palette,16);
    cpct_setPalette(g_palette,16);
    cpct_setBorder(g_palette[2]);

    while(1){
        runTest();

        while(1){
            cpct_scanKeyboard();

            if (cpct_isKeyPressed(Key_Esc)){
                break;
            }
        }
    }
}

void runTest(){
    i16 x,y;

    u8* pscr;

    cpct_setVideoMode(1);
    cpct_clearScreen_f64(0x00);

    pscr=cpct_getScreenPtr(SCR_VMEM,0,0);
    cpct_drawStringM1("Please select the test to run.",pscr+80+2,1,0);
    cpct_drawStringM1("(A) mode 0",pscr+240+2,1,0);
    cpct_drawStringM1("(B) mode 1",pscr+320+2,1,0);
    cpct_drawStringM1("(C) mode 2",pscr+400+2,1,0);
    cpct_drawStringM1("After the test, press ESC",pscr+560+2,1,0);
    cpct_drawStringM1("to return to this screen.",pscr+640+2,1,0);
    cpct_drawStringM1("(X) other mode 0",pscr+800+2,1,0);

    while(1){
        cpct_scanKeyboard();

        if (cpct_isKeyPressed(Key_A)){
            mode=0;
            testRun=0;
            break;
        }
        else if (cpct_isKeyPressed(Key_B)){
            mode=1;
            testRun=1;
            break;
        }
        else if (cpct_isKeyPressed(Key_C)){
            mode=2;
            testRun=2;
            break;
        }
        else if (cpct_isKeyPressed(Key_X)){
            mode=0;
            testRun=3;
            break;
        }
    }

    cpct_setVideoMode(mode);
    cpct_clearScreen_f64(0x00);

    populate_yAddress();

    // eye #1

    y=10;

    if (testRun==0){
        lineColour=3;

        for (x=8;x<=152;x+=4){
            drawLine(x,10,152,y);
            y+=5;
        }
    }
    else if (testRun==1){
        lineColour=1;

        for (x=16;x<=304;x+=8){
            drawLine(x,10,304,y);
            y+=5;
        }
    }
    else if (testRun==2){
        lineColour=1;

        for (x=32;x<=608;x+=16){
            drawLine(x,10,608,y);
            y+=5;
        }
    }

    // eye #2

    if (testRun==0){
        lineColour=4;
        x=152;

        for (y=10;y<=190;y+=5){
            drawLine(152,y,x,190);
            x-=4;
        }
    }
    else if (testRun==1){
        lineColour=3;
        x=304;

        for (y=10;y<=190;y+=5){
            drawLine(304,y,x,190);
            x-=8;
        }
    }
    else if (testRun==2){
        lineColour=1;
        x=608;

        for (y=10;y<=190;y+=5){
            drawLine(608,y,x,190);
            x-=16;
        }
    }

    // eye #3

    y=190;

    if (testRun==0){
        lineColour=5;

        for (x=152;x>=8;x-=4){
            drawLine(x,190,8,y);
            y-=5;
        }
    }
    else if (testRun==1){
        lineColour=1;

        for (x=304;x>=16;x-=8){
            drawLine(x,190,16,y);
            y-=5;
        }
    }
    else if (testRun==2){
        lineColour=1;

        for (x=608;x>=32;x-=16){
            drawLine(x,190,32,y);
            y-=5;
        }
    }

    // eye #4

    if (testRun==0){
        lineColour=6;
        x=8;

        for (y=190;y>=10;y-=5){
            drawLine(8,y,x,10);
            x+=4;
        }
    }
    else if (testRun==1){
        lineColour=3;
        x=16;

        for (y=190;y>=10;y-=5){
            drawLine(16,y,x,10);
            x+=8;
        }
    }
    else if (testRun==2){
        lineColour=1;
        x=32;

        for (y=190;y>=10;y-=5){
            drawLine(32,y,x,10);
            x+=16;
        }
    }

    if (testRun==3){
        lineColour=3;

        for (y=10;y<=190;y+=4){
            drawLine(10,y,150,y);
        }

        cpct_clearScreen_f64(0x00);
        lineColour=4;

        for (x=10;x<=150;x+=4){
            drawLine(x,10,x,190);
        }

        cpct_clearScreen_f64(0x00);
        lineColour=5;

        for (y=10;y<=70;y+=3){
            drawLine(20,y,140,y+120);
        }

        cpct_clearScreen_f64(0x00);
        lineColour=6;

        for (y=190;y>=130;y-=3){
            drawLine(20,y,140,y-120);
        }
    }
}

void populate_yAddress(){
    u8 i;

    for (i=0;i<=199;i++){
        yAddress[i]=cpct_getScreenPtr(SCR_VMEM,0,i);
    }
}

void drawLine(i16 x1,i16 y1,i16 x2,i16 y2){
    if (mode==0)
        drawLineMode0(x1,y1,x2,y2);
    else if (mode==1)
        drawLineMode1(x1,y1,x2,y2);
    else if (mode==2)
        drawLineMode2(x1,y1,x2,y2);
}

void drawLineMode0(i16 x1,i16 y1,i16 x2,i16 y2){
    i16 xn,yn;
    i16 dx,dy;

    // if line is left-x-space, discard it

    if ((x1<0) && (x2<0))
        return;

    // if line is right-x-space, discard it

    if ((x1>MODE0_LIMIT) && (x2>MODE0_LIMIT))
        return;

    // if line is above-y-space, discard it

    if ((y1<0) && (y2<0))
        return;

    // if line is below-y-space, discard it

    if ((y1>199) && (y2>199))
        return;

    // determine colour masks for mode 0

    if (lineColour&1){
        lineMask0_1A=128;
        lineMask0_1B=64;
    }
    else{
        lineMask0_1A=0;
        lineMask0_1B=0;
    }

    if (lineColour&2){
        lineMask0_2A=8;
        lineMask0_2B=4;
    }
    else{
        lineMask0_2A=0;
        lineMask0_2B=0;
    }

    if (lineColour&4){
        lineMask0_4A=32;
        lineMask0_4B=16;
    }
    else{
        lineMask0_4A=0;
        lineMask0_4B=0;
    }

    if (lineColour&{
        lineMask0_8A=2;
        lineMask0_8B=1;
    }
    else{
        lineMask0_8A=0;
        lineMask0_8B=0;
    }

    // single pixel

    if ((x1==x2) && (y1==y2)){
        putPixelMode0(x1,y1);
        return;
    }

    // swap endpoints if necessary

    if (x1>x2){
        x1^=x2;
        x2^=x1;
        x1^=x2;

        y1^=y2;
        y2^=y1;
        y1^=y2;
    }

    dx=x2-x1;
    dy=y2-y1;

    // line going down?

    if (dy>=0){
        // gentle line?
        // octant 7/3

        if (dy<=dx){
            yn=dx>>1;

            // plot valid pixels

            for (x1=x1;x1<=x2;x1++){
                putPixelMode0(x1,y1);
                yn+=dy;

                if (yn>=dx){
                    yn-=dx;
                    y1++;
                }
            }
        }

        // steep line?
        // octant 6/2

        else{
            xn=dy>>1;

            for (y1=y1;y1<=y2;y1++){
                putPixelMode0(x1,y1);
                xn+=dx;

                if (xn>=dy){
                    xn-=dy;
                    x1++;
                }
            }
        }
    }

    // line going up?

    else{
        // gentle line?
        // octant 0/4

        if (-dy<=dx){
            yn=dx>>1;

            for (x1=x1;x1<=x2;x1++){
                putPixelMode0(x1,y1);
                yn+=-dy;

                if (yn>=dx){
                    yn-=dx;
                    y1--;
                }
            }
        }

        // steep line?
        // octant 1/5

        else{
            xn=-dy>>1;

            for (y1=y1;y1>=y2;y1--){
                putPixelMode0(x1,y1);
                xn+=dx;

                if (xn>=-dy){
                    xn-=-dy;
                    x1++;
                }
            }
        }
    }
}

void drawLineMode1(i16 x1,i16 y1,i16 x2,i16 y2){
    i16 xn,yn;
    i16 dx,dy;

    // if line is left-x-space, discard it

    if ((x1<0) && (x2<0))
        return;

    // if line is right-x-space, discard it

    if ((x1>MODE1_LIMIT) && (x2>MODE1_LIMIT))
        return;

    // if line is above-y-space, discard it

    if ((y1<0) && (y2<0))
        return;

    // if line is below-y-space, discard it

    if ((y1>199) && (y2>199))
        return;

    // determine colour masks for mode 1

    if (lineColour&1){
        lineMask1_1A=128;
        lineMask1_1B=64;
        lineMask1_1C=32;
        lineMask1_1D=16;
    }
    else{
        lineMask1_1A=0;
        lineMask1_1B=0;
        lineMask1_1C=0;
        lineMask1_1D=0;
    }

    if (lineColour&2){
        lineMask1_2A=8;
        lineMask1_2B=4;
        lineMask1_2C=2;
        lineMask1_2D=1;
    }
    else{
        lineMask1_2A=0;
        lineMask1_2B=0;
        lineMask1_2C=0;
        lineMask1_2D=0;
    }

    // single pixel

    if ((x1==x2) && (y1==y2)){
        putPixelMode1(x1,y1);
        return;
    }

    // swap endpoints if necessary

    if (x1>x2){
        x1^=x2;
        x2^=x1;
        x1^=x2;

        y1^=y2;
        y2^=y1;
        y1^=y2;
    }

    dx=x2-x1;
    dy=y2-y1;

    // line going down?

    if (dy>=0){
        // gentle line?
        // octant 7/3

        if (dy<=dx){
            yn=dx>>1;

            // plot valid pixels

            for (x1=x1;x1<=x2;x1++){
                putPixelMode1(x1,y1);
                yn+=dy;

                if (yn>=dx){
                    yn-=dx;
                    y1++;
                }
            }
        }

        // steep line?
        // octant 6/2

        else{
            xn=dy>>1;

            for (y1=y1;y1<=y2;y1++){
                putPixelMode1(x1,y1);
                xn+=dx;

                if (xn>=dy){
                    xn-=dy;
                    x1++;
                }
            }
        }
    }

    // line going up?

    else{
        // gentle line?
        // octant 0/4

        if (-dy<=dx){
            yn=dx>>1;

            for (x1=x1;x1<=x2;x1++){
                putPixelMode1(x1,y1);
                yn+=-dy;

                if (yn>=dx){
                    yn-=dx;
                    y1--;
                }
            }
        }

        // steep line?
        // octant 1/5

        else{
            xn=-dy>>1;

            for (y1=y1;y1>=y2;y1--){
                putPixelMode1(x1,y1);
                xn+=dx;

                if (xn>=-dy){
                    xn-=-dy;
                    x1++;
                }
            }
        }
    }
}

void drawLineMode2(i16 x1,i16 y1,i16 x2,i16 y2){
    i16 xn,yn;
    i16 dx,dy;

    // if line is left-x-space, discard it

    if ((x1<0) && (x2<0))
        return;

    // if line is right-x-space, discard it

    if ((x1>MODE2_LIMIT) && (x2>MODE2_LIMIT))
        return;

    // if line is above-y-space, discard it

    if ((y1<0) && (y2<0))
        return;

    // if line is below-y-space, discard it

    if ((y1>199) && (y2>199))
        return;

    // determine colour masks for mode 2

    if (lineColour&1){
        lineMask2_1A=128;
        lineMask2_1B=64;
        lineMask2_1C=32;
        lineMask2_1D=16;
        lineMask2_1E=8;
        lineMask2_1F=4;
        lineMask2_1G=2;
        lineMask2_1H=1;
    }
    else{
        lineMask2_1A=0;
        lineMask2_1B=0;
        lineMask2_1C=0;
        lineMask2_1D=0;
        lineMask2_1E=0;
        lineMask2_1F=0;
        lineMask2_1G=0;
        lineMask2_1H=0;
    }

    // single pixel

    if ((x1==x2) && (y1==y2)){
        putPixelMode2(x1,y1);
        return;
    }

    // swap endpoints if necessary

    if (x1>x2){
        x1^=x2;
        x2^=x1;
        x1^=x2;

        y1^=y2;
        y2^=y1;
        y1^=y2;
    }

    dx=x2-x1;
    dy=y2-y1;

    // line going down?

    if (dy>=0){
        // gentle line?
        // octant 7/3

        if (dy<=dx){
            yn=dx>>1;

            // plot valid pixels

            for (x1=x1;x1<=x2;x1++){
                putPixelMode2(x1,y1);
                yn+=dy;

                if (yn>=dx){
                    yn-=dx;
                    y1++;
                }
            }
        }

        // steep line?
        // octant 6/2

        else{
            xn=dy>>1;

            for (y1=y1;y1<=y2;y1++){
                putPixelMode2(x1,y1);
                xn+=dx;

                if (xn>=dy){
                    xn-=dy;
                    x1++;
                }
            }
        }
    }

    // line going up?

    else{
        // gentle line?
        // octant 0/4

        if (-dy<=dx){
            yn=dx>>1;

            for (x1=x1;x1<=x2;x1++){
                putPixelMode2(x1,y1);
                yn+=-dy;

                if (yn>=dx){
                    yn-=dx;
                    y1--;
                }
            }
        }

        // steep line?
        // octant 1/5

        else{
            xn=-dy>>1;

            for (y1=y1;y1>=y2;y1--){
                putPixelMode2(x1,y1);
                xn+=dx;

                if (xn>=-dy){
                    xn-=-dy;
                    x1++;
                }
            }
        }
    }
}

void putPixelMode0(u8 nX,u8 nY){
    u8* vram=yAddress[nY]+(nX>>1);
    u8 remainder=nX%2;

    if(remainder==0)
        *vram=((((*vram&85)|lineMask0_1A)|lineMask0_2A)|lineMask0_4A)|lineMask0_8A;
    else
        *vram=((((*vram&170)|lineMask0_1B)|lineMask0_2B)|lineMask0_4B)|lineMask0_8B;
}

void putPixelMode1(u16 nX,u8 nY){
    u8* vram=yAddress[nY]+(nX>>2);
    u8 remainder=nX-((nX>>2)<<2);

    if(remainder==0)
        *vram=((*vram&=119)|lineMask1_1A)|lineMask1_2A;
    else if(remainder==1)
        *vram=((*vram&=187)|lineMask1_1B)|lineMask1_2B;
    else if(remainder==2)
        *vram=((*vram&=221)|lineMask1_1C)|lineMask1_2C;
    else
        *vram=((*vram&=238)|lineMask1_1D)|lineMask1_2D;
}

void putPixelMode2(u16 nX,u8 nY){
    u8* vram=yAddress[nY]+(nX>>3);
    u8 remainder=nX-((nX>>3)<<3);

    if(remainder==0)
        *vram=(*vram&=127)|lineMask2_1A;
    else if(remainder==1)
        *vram=(*vram&=191)|lineMask2_1B;
    else if(remainder==2)
        *vram=(*vram&=223)|lineMask2_1C;
    else if(remainder==3)
        *vram=(*vram&=239)|lineMask2_1D;
    else if(remainder==4)
        *vram=(*vram&=247)|lineMask2_1E;
    else if(remainder==5)
        *vram=(*vram&=251)|lineMask2_1F;
    else if(remainder==6)
        *vram=(*vram&=253)|lineMask2_1G;
    else
        *vram=(*vram&=254)|lineMask2_1H;
}


Elite on BBC (not sure about CPC) used different line drawing methods depending on angle and length. You may find the same works good for you too.

In my unreleased rom game I drew lines and clipped them but the frame rate wasn't great (but then I was also doing some 3d calculations and the game stalled because of conversion between different coordinate systems and different fixed point representations).

I hope you do better :)

Interesting... I didn't know that about BBC Elite.

I've actually been wondering about your vector game - I've been looking forward to it for a long time.
Do you have any plans to revisit it?

Quote from: ervin on 13:07, 19 July 16
Interesting... I didn't know that about BBC Elite.

ELITE by David Braben (Frontier Developments) Game - coffee and tea (http://megaslides.com/doc/487819/elite-by-david-braben--frontier-developments--game)

Quote from: ervin on 13:07, 19 July 16
I've actually been wondering about your vector game - I've been looking forward to it for a long time.
Do you have any plans to revisit it?

Yes but later in the year.

Quote from: arnoldemu on 19:59, 19 July 16
ELITE by David Braben (Frontier Developments) Game - coffee and tea (http://megaslides.com/doc/487819/elite-by-david-braben--frontier-developments--game)
Yes but later in the year.

Excellent, really looking forward to seeing what you come up with.
8)

Alrighty, optimised routines for vertical, horizontal and 1:1 diagonal lines are done.
Now it's time to open the doors to the scary world of line clipping!
:o

Quick question for everyone...
Do you think that (0,0) should be at the top-left of the screen, or at the bottom-left (in terms of pixels)?

BASIC uses the bottom-left, so I'm inclined to go with that.
It's the opposite to what screen address calculations give, but it's trivial to adjust the y coordinates to work the same way as they do in BASIC.

[EDIT] Actually, I've decided to go with top-left. That seems to be generally accepted these days as the default origin.
8)

Quote from: ervin on 12:57, 19 July 16- conversion of critical routines to asm

Before converting critical routines to asm, you have to optimise the algorithm.


The heavy part is the call to PutPixel.


But before remove the PutPixel, you must do the full clipping to be sure every pixels you will write will be on screen


If you ensure to always draw from top to bottom, then you have only two cases:
- step down and sometimes go to the left
- step down and sometimes go the the right


So the PutPixel routine becomes:
- init: compute the starting adress on screen and the starting mask (with the current position in the byte, 0/1 in mode 0, 0/1/2/3 in mode 1, 0/1/2/3/4/5/6/7 in mode 2)
- routine1: put pixel to current adress / jump to next line OR shift color mask (it's the same thing to do in all video mode, shifting) and possibly DECrease current adress when the position in the byte exceed 1,3 or 7*

- routine2: put pixel to current adress / jump to next line OR shift color mask (it's the same thing to do in all video mode, shifting) and possibly INCrease current adress when the position in the byte exceed 1,3 or 7*


I suggest to use a counter decrementing for both routines -> faster, you do not have to compare either test zero after dec.


--- this will be a huge work! ---


Once you've optimized the critical part of the algorithm, you may get some additionnal speed improvement with a native assembly code.


Finally, you will also trade all the clumsy code like the swapping coordinates (i have not red all the source but this one is absolutely not clever)
x1^=x2; x2^=x1; x1^=x2 (...)  -> use a temporary variable tmp=x1;x1=x2;x2=tmp; cause it's faster, and in assembly (maybe with the compile code too) will not require a tmp variable but a temporary register and will NOT compute the XOR for nothing.

@roudoudou (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1714)
That's brilliant information and advice.
Thanks so much for all of that.
I'll study your suggestions and try to incorporate them.

Quote from: ervin on 06:10, 20 July 16
Quick question for everyone...
Do you think that (0,0) should be at the top-left of the screen, or at the bottom-left (in terms of pixels)?

BASIC uses the bottom-left, so I'm inclined to go with that.
It's the opposite to what screen address calculations give, but it's trivial to adjust the y coordinates to work the same way as they do in BASIC.

[EDIT] Actually, I've decided to go with top-left. That seems to be generally accepted these days as the default origin.
8)

I don't know because I noticed you weren't using the Firmware, the Graphics used in BASIC come from the Firmware, so when something else is implemented (e.g. @Executioner (http://www.cpcwiki.eu/forum/index.php?action=profile;u=17) Fast plot), all the graphical co-ordinates change.

I've made some progress with the suggestions above from roudoudou.
(I particularly like the idea of shifting/rotating the colour masks, even though it was very tricky to implement).

I've implemented several of the ideas into one case for mode 0 lines, and although there hasn't (yet) been much of a speed improvement, there are now far fewer variables in that code block. This means that it will be much easier to convert the C code into efficient asm code. Really looking forward to that part.

But I've got a lot of other cases left to put these ideas into, for all 3 screen modes...

Nice work, @ervin (http://www.cpcwiki.eu/forum/index.php?action=profile;u=82) . Line drawing is one feature that has already been requested for inclusion in CPCtelera (http://lronaldo.github.io/cpctelera), but it is tagged low priority (scheduled for CPCtelera (http://lronaldo.github.io/cpctelera) 2.0). However, if you continue developing it and want to contribute it to the present development branch, that would be great :D.

And, of course, if you used it to make a vector game inspired in Elite, that would awesome :D.

I'm not sure what Elite uses for it's vector graphics system, though apparantely Tankbusters is somehow using mode 3 to produce it's fast animation sequences. It's limited to 4 colours though.

Quote from: ronaldo on 09:09, 22 July 16
Nice work, @ervin (http://www.cpcwiki.eu/forum/index.php?action=profile;u=82) . Line drawing is one feature that has already been requested for inclusion in CPCtelera (http://lronaldo.github.io/cpctelera), but it is tagged low priority (scheduled for CPCtelera (http://lronaldo.github.io/cpctelera) 2.0). However, if you continue developing it and want to contribute it to the present development branch, that would be great :D .

And, of course, if you used it to make a vector game inspired in Elite, that would awesome :D .

It would be an absolute honour to have some of my code in cpctelera!
But I don't think my code is good enough...
We'll see how it goes.

Quote from: AMSDOS on 00:29, 23 July 16
I'm not sure what Elite uses for it's vector graphics system, though apparantely Tankbusters is somehow using mode 3 to produce it's fast animation sequences. It's limited to 4 colours though.

And let's not forget Dark Star and its sequel (Forbidden Planet?)!
They were phenomenal.

Quote from: AMSDOS on 00:29, 23 July 16
I'm not sure what Elite uses for it's vector graphics system, though apparantely Tankbusters is somehow using mode 3 to produce it's fast animation sequences. It's limited to 4 colours though.

If I remember it correctly, it was an ACU article explaining what had been done in TankBusters and described it as mode 3, but it wasnt the hardware mode 3, it was mode 0 using a variation on the split bitplanes/dual playfields to have two 2bpp/4 colour mode 0 displays on a single 16kb screen, with the screen flipping achieved by changing the appropriate colours rather than the screen base address.  It drew the new display in hidden inks, set them visible and hid the inks used in the previous frame, then drew up the next frame in the newly hidden inks and so on.

Quote from: Axelay on 16:05, 23 July 16

If I remember it correctly, it was an ACU article explaining what had been done in TankBusters and described it as mode 3, but it wasnt the hardware mode 3, it was mode 0 using a variation on the split bitplanes/dual playfields to have two 2bpp/4 colour mode 0 displays on a single 16kb screen, with the screen flipping achieved by changing the appropriate colours rather than the screen base address.  It drew the new display in hidden inks, set them visible and hid the inks used in the previous frame, then drew up the next frame in the newly hidden inks and so on.

Ah yes, I remember that article.
I had no idea what any of it meant back then, and to be honest I don't understand it much now either!
8)

Hi everyone.

Alrighty, work on clipping has begun.
Once all the clipping stuff is finished, I'll continue improving the code with the suggestions made by @roudoudou (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1714).

I've added a new download to the first post in this thread.

There are 6 tests available from the main menu.
Selecting a test will clear the screen and draw a box, which represents the test clipping region.
Moving the box around with the arrow keys will provide a "window" into the drawing underneath.

At the moment, I've got efficient clipping for lines which start/end completely to one side of the clipping region (i.e. left/right/above/below).
If a line fits that criteria, it is discarded instantly.

But the rest of the clipping is currently of the naive variety, where a pixel's (x,y) are checked, to see if the pixel is inside the clipping region.
This is HORRIBLY, UNBEARABLY SLOW, so I recommend running your emulator of choice at full speed.
(Big thanks to @Executioner (http://www.cpcwiki.eu/forum/index.php?action=profile;u=17) for adding the SHIFT+F3/SHIFT+F4 options to WinAPE!)

As I put in better clipping, these checks will be removed, which should make things a heck of a lot faster.
8)

Quote from: ervin on 12:21, 24 July 16
Ah yes, I remember that article.
I had no idea what any of it meant back then, and to be honest I don't understand it much now either!
8)

@Axelay (http://www.cpcwiki.eu/forum/index.php?action=profile;u=84) could probably clarify better than me, I've read their comments as Tankbusters is just using Mode 0, which makes more sense as Mode 3 seems to be too slow for flipping one set of colours for the other set, based on the Demonstrations I've seen of it, though since it's assembly anything from "Back in the Day" could probably be seriously optimized now. For Tankbusters I think what's happening is it's Mode 0 to give it 16 colours, for the series of Rotating Shapes for example, I'm imagining everything being draw up or deleted as black and then the relevant pen is set as Visible.


I wrote something like this when I was first started writing my own Assembly which I still have, but the code I have doesn't look correct. I would of made a Screen Pattern, which altered when the inks switched, overall it was a clever way of animating as a series of colour cycles.

Wow, this line-clipping stuff is tough!
So, so many cases I have to take into account, otherwise confusing, hard-to-solve crashes happen.

Making steady progress though...
Horizontal, vertical and 1:1 diagonals are now being drawn very quickly, and clipping nicely as well.
8)

All other lines also have endpoint clipping done.
Just starting-point clipping to go for these other lines.
And that's the toughest part of the clipping process!

Found a bad bug in the clipping of 1:1 diagonal lines.
Had me going nuts trying to find it!
But now that it's solved, I can move onto other ideas.

To fully test all the lines and clipping cases, I need to improve my testing techniques, which are too slow and take too long to set up.
I think what I should perhaps be doing is putting some lines on the screen (for example, perfect horizontals) and then letting the user move them around anywhere they like, including off the screen.
That way every line type will be testing against each clipping boundary.

I have to say, this is a very interesting and enjoyable project.
It's still running very slowly, being in pure C (apart from one asm function I wrote to rotate a byte), but I'm writing things in such a manner that conversion to asm should be relatively easy, and should result in huge speed gains.

Quote from: ervin on 13:00, 29 July 16
I have to say, this is a very interesting and enjoyable project.

I am enjoying reading your posts :)

Quote from: arnoldemu on 13:52, 29 July 16
I am enjoying reading your posts :)

Thanks!
Hopefully I don't get too wordy and start getting on peoples' nerves!
8)

Keep up the good work!  :)

Quote from: Tai on 15:13, 29 July 16
Keep up the good work!  :)

I will!
8)

I've now got a little testing routine that makes it much quicker to view the effects of having lines of different lengths being moved around the screen.
This should make all sorts of lines much quicker to test and complete clipping for.

I'm really looking forward to the optimisation phase.
I keep having to stop myself from being tempted to work on that prematurely!

I've now got the clipping working for lines in half the quadrants.
It's really cool seeing the lines not being drawn outside the clipping region.
I actually can't believe I've got it working; it's been quite tricky!
8)

Quote from: ervin on 14:11, 31 July 16
I've now got the clipping working for lines in half the quadrants.
It's really cool seeing the lines not being drawn outside the clipping region.
I actually can't believe I've got it working; it's been quite tricky!
8)

To check your clipping make the rectangle much smaller than the screen and draw lines that are inside, cross each of the sides (top, bottom, left and right), and cross top and bottom, cross left and right, and do the ones which cross left and top, left and bottom etc. Then also draw some outside.

Do all combinations and you can be sure you are clipping all correctly and that all cases in your code are working.

Thanks for those ideas.
8)

One thing which was tripping me up was lines which start and finish outside, and may or may not cross into the visible region.
For example, you might have the starting point to the left of the screen but vertically within screen bounds.
And the end point might be above the screen but within the horizontal screen bounds.
Depending on the angle, this line may or may not cross into the top-left corner of the screen.
Catching that was tricky, but I think I have it working!  :)

All clipping cases are now working successfully!!!
:o 8)

Lots of testing to do now, but it's looking good!
I'm absolutely chuffed right now!

Alrighty!
I've uploaded bres_2.zip to the first post in this thread.
It contains a number of mode 0 tests.

If you're interested, please download it and have a play.
Let me know if you find any problems.
;D

I recommend running it on an emulator at high-speed, as it's still very slow.

Quote from: ervin on 14:09, 01 August 16
Alrighty!
I've uploaded bres_2.zip to the first post in this thread.
It contains a number of mode 0 tests.

If you're interested, please download it and have a play.
Let me know if you find any problems.
;D

I recommend running it on an emulator at high-speed, as it's still very slow.

No really a problem, more an observation, to me the vertical lines were getting across the screen faster than the horizontal lines. Have you noticed that?

Quote from: AMSDOS on 10:54, 02 August 16

No really a problem, more an observation, to me the vertical lines were getting across the screen faster than the horizontal lines. Have you noticed that?

Actually yes, I did notice that earlier today, and I did some tests.
They are moving the same speed - the only conclusion I could come up with is that it's an illusion caused by the awful flickering!
:P

Quote from: ervin on 12:47, 02 August 16
Actually yes, I did notice that earlier today, and I did some tests.
They are moving the same speed - the only conclusion I could come up with is that it's an illusion caused by the awful flickering!
:P

Ok, wasn't sure if it was an illusion, or if the Line Drawing routine was slowly calculating the next point along the Horizontal Axis.

Just fixed a bad bug in the mode 1 drawLine routine... been stuck on it for a while.
Turned out I was rotating a byte the wrong way, when determining the next pixel mask.
Man, that was a tough one to solve!

I hate bugs like that.
They can really make you doubt yourself, and the project you're working on!

[EDIT] I've added double-buffering, so testing is now much more bearable.
No more evil flickering!
8)

 :doh:

With double-buffering, I didn't have much memory left for all the test code, and all the clipping/drawing code for modes 0,1 and 2.
So I had to bite the bullet and split the development into 3 projects, one for each mode.

So now we have bres0, bres1 and bres2.
It's a bit of a pain in the buttocks!

Ah well, at least I no longer have to worry about running out of memory...
(And it was very easy to split it up into multiple projects, so there's that, eh?)

A new file has been uploaded to the first post.
The dsk contains 3 programs: bres0, bres1 and bres2.

All of them are now feature complete.
All clipping cases are accounted for, and appear to be working correctly.
I've got double-buffering working as well.

All 3 programs draw an eye-shape with option A from the main menu.

Options B to J run different tests.
These are very slow due to full screen-clearing and buffer-swapping going on between each refresh.

However, my favourite part of development will now begin... optimisation!
Expect to see MAJOR speed increases in the coming weeks.
8)

Had a really great idea this morning (whilst taking a shower!).

Thus far, I've been checking the video page when moving the current video address up or down, in order to allow double-buffering to work "out of the box". Of course, this sort of check slows things down and complicates what should be a simple routine.

So, I thought I'd implement a remainder variable, which is incremented/decremented/reset appropriately anytime the y pixel position needs to change.
Much simpler, a bit faster, and also results in slightly smaller code.
It'll also be easier to convert to asm.

WIN!

[EDIT] The first round of optimisations has made it take 30% less time to draw the mode 0 eye.

Sorry I was following till I got to the point of the shower, after that I'm stumped  :'(  Could it be pseudocode or C (if possible), with screenshots?

Quote from: AMSDOS on 08:30, 05 August 16
Sorry I was following till I got to the point of the shower, after that I'm stumped  :'(  Could it be pseudocode or C (if possible), with screenshots?

I'm not sure I can explain this very well...
I've put some comments in which hopefully sort of describe what is going on.

// calculate remainderX for mode 0

remainderX=ux1%2;

// calculate remainderY

remainderY=uy1%8;

// calculate vram address for mode 0

vram=yAddress[uy1]+(ux1/2);

// prepare masks

for (i=0;i<remainderX;i++){
    lineMaskRotateRight();
    colourMaskRotateRight();
}

// determine the y-length of the line

len=uy2-uy1+1;

// draw the line

for (len;len!=0;len--){
    *vram=*vram&colourMask|lineMask;
    xn+=dx;

    if (xn>=dy){
        xn-=dy;

        if (remainderX==1){
            lineMaskRotateLeft();
            remainderX=0;
            vram++;
        }
        else{
            lineMaskRotateRight();
            remainderX++;
    }   

    colourMaskRotateRight();

    // increment vram y position

    if (remainderY==7){
        vram-=0x37B0;
        remainderY=0;
    }
    else{
        vram+=0x0800;
        remainderY++;
    }
}

Wasn't sure what ux1 or uy1 meant, to me they look like Screen Based variables for mapping out the screen?

Quote from: AMSDOS on 00:18, 06 August 16
Wasn't sure what ux1 or uy1 meant, to me they look like Screen Based variables for mapping out the screen?

Yes, they are unsigned variables:
0 <= ux1 <= 159 (mode 0)
0 <= uy1 <= 199

I use signed variables for all the clipping business, and then copy them to unsigned variables, to make the loop a bit more efficient.

Holy cow that was frustrating!
I've been stuck on one stupid little obscure bug for the last few days.

I had a situation where very long lines weren't clipping correctly, and then proceeding to trash parts of memory.
The solution... in ONE case, I had forgotten to change an 8-bit variable to 16-bit.
I had made the change in all other cases in the entire program, but this one little case had snuck under the radar.

When I solved it, it was like the heavens opened and light shone down on me.
(Like beating a particularly difficult boss in Dark Souls - like the Smelter Demon in DS2).
8)

Quote from: ervin on 01:24, 11 August 16
Holy cow that was frustrating!
I've been stuck on one stupid little obscure bug for the last few days.

I had a situation where very long lines weren't clipping correctly, and then proceeding to trash parts of memory.
The solution... in ONE case, I had forgotten to change an 8-bit variable to 16-bit.
I had made the change in all other cases in the entire program, but this one little case had snuck under the radar.

When I solved it, it was like the heavens opened and light shone down on me.
(Like beating a particularly difficult boss in Dark Souls - like the Smelter Demon in DS2).
8)

Always good to update your code under a new file in case something goes wrong. Because I write in the Emulator, I also keep a Text File to open in Notepad, which comes in handy when dealing in multiple files and have to deal in another part of the program.

Quote from: AMSDOS on 02:26, 11 August 16

Always good to update your code under a new file in case something goes wrong. Because I write in the Emulator, I also keep a Text File to open in Notepad, which comes in handy when dealing in multiple files and have to deal in another part of the program.

I keep lots of backups (using Dropbox), so that's covered.
8)

I write my code in Sublime Text - an absolutely outstanding text editor.

@ervin (http://www.cpcwiki.eu/forum/index.php?action=profile;u=82):

I put my cpctelera code through visual studio 2015 community edition's static analysis tools. I also run it through cppcheck.

Both of these may have picked up the problem.

I think it's definitely worth running static analysis a lot of issues can be found this way.

[ot]I haven't used Dropbox, just in case it got deleted by Hacker, but I always think worst case scenario with the net, the census hacking is just another "I'm not surprised". With all the advertising for it, the Bureau of Stats should of popped up a large banner "Census Night - Hackers Welcome!" [/ot]

Quote from: arnoldemu on 07:47, 11 August 16
@ervin (http://www.cpcwiki.eu/forum/index.php?action=profile;u=82):

I put my cpctelera code through visual studio 2015 community edition's static analysis tools. I also run it through cppcheck.

Both of these may have picked up the problem.

I think it's definitely worth running static analysis a lot of issues can be found this way.

That's a brilliant idea.
I should give it a go!

Optimisation is coming along very nicely.

The difficulty is making sure the optimisations are in-sync between the mode 0/1/2 versions of code.
(There are subtle differences, but general optimisations are pretty much the same).

Drawing the eye 3 times in mode 0 used to take 18 seconds (in pure SDCC), before I improved the masking and memory positioning routines.
Now, after a bunch of asm (and a bit of self-modifying code) it's down to around 7 seconds.
8)

The really awesome thing is that there are still *lots* more things I can do to the mode 0 code to make it much faster.

I've also (hopefully) ironed out all the issues with clipping - this took a few weeks, but I finally feel like things are all working correctly.

How many memory take your code ?

Quote from: Arnaud on 17:04, 15 August 16
How many memory take your code ?

I'm not sure how much RAM the drawing routines take up.
I've got the code inside of test programs at the moment, and the test routines themselves take up a lot of memory.

For example, the mode 0 program is currently 8,845 bytes, but a *very* large part of that is due to the testing routines.

[EDIT] I commented out a bunch of testing code, and it's now 6,858 bytes.
Which is too large in my opinion.
But there is still a *lot* of optimisation to do, so it will shrink a lot.

@ervin (http://www.cpcwiki.eu/forum/index.php?action=profile;u=82) whenever you compile a CPCtelera (http://lronaldo.github.io/cpctelera) project, the obj/ folder is generated. Inside you can find compiled assembly for all your code, with detailed information on sizes and performance. You can look into .map file, which has all the generated global symbols. Using it is really easy to calculate sizes of every function from the code or bigger blocks. You also can use individal .rel files which show their binary size in their header (they are text files).

Quote from: ronaldo on 20:13, 16 August 16
@ervin (http://www.cpcwiki.eu/forum/index.php?action=profile;u=82) whenever you compile a CPCtelera (http://lronaldo.github.io/cpctelera) project, the obj/ folder is generated. Inside you can find compiled assembly for all your code, with detailed information on sizes and performance. You can look into .map file, which has all the generated global symbols. Using it is really easy to calculate sizes of every function from the code or bigger blocks. You also can use individal .rel files which show their binary size in their header (they are text files).

Thanks @ronaldo (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1227).
That's really good to know.
8)

Optimisation of all the tight loops is nearly done now.

It takes around 5.2 seconds to draw the eye 3 times in mode 0, which I'm *very* happy with!
(It used to take 18!)
It will go under 5 seconds once finished.
8)

In mode 1, the eye takes 7.7 seconds to draw 3 times, while in mode 2 it takes 11.8 seconds.
However modes 1 and 2 are one step behind mode 0 in optimisation (though I am being very careful to make sure all optimisations are kept in sync between the 3 modes).

Clipping optimisation has come a long way as well, and clipping is very fast now.

Once the speed optimisation is done, it'll be time to work on size.
The generated binary is too big, but there are lots of things I can do to change that.

The mode 0 program is now down to 7,113 bytes (including test code).
A few days ago it was 8,845 bytes!
8)

Still got some more to do...

Alrighty, speed optimisation is pretty much done!
I may find minor things as I work on shrinking the program, but any further speed improvements I might discover probably won't be noticeable or measureable.

The following times represent the number of seconds to draw the eye 3 times.
Mode 0: 4.7
Mode 1: 6.4
Mode 2: 10.0

Very, very happy with the speed now!

Also, the size of the produced binaries continues to come down.
(Remember, the binaries also contain a lot of testing code).
Mode 0: 7,027 bytes
Mode 1: 7,063
Mode 2: 6,977

OOPS! I accidentally edited this post and erased everything in it!
The post that was here previously, mentioned a time of 4.4 seconds for the mode 0 eye to be drawn 3 times.

Alrighty, I changed the code around a bit, and removed some stuff that wasn't really needed.
The mode 0 binary is now down to 6,580 bytes, including test code.

But the really cool thing is that I found a couple more optimisations!
I had 3 little ideas over the weekend that I implemented carefully into one of the (4 main) routines.
And now the mode 0 eye is drawn 3 times in 3.9 seconds!!!

Now I need to put the same optimisations into the other 3 routines, and perhaps we'll get close to 1 second per-eye!
That would be mindblowing!
8)

I never imagined that I would figure out how to make it run anything like this fast!

[EDIT] Hmmm... apart from giving away the source code, I think I should start thinking about making a game with this...

[EDIT#2] Oh well... looks like 3.6 seconds (for drawing the mode 0 eye 3 times) is as fast as it will get. Still, it's *very* fast, so I'm chuffed.
Now it's time to apply 2 of these optimisations to the clipping routines.

Quote from: ervin on 01:52, 22 August 16
Alrighty, I changed the code around a bit, and removed some stuff that wasn't really needed.
The mode 0 binary is now down to 6,580 bytes, including test code.

But the really cool thing is that I found a couple more optimisations!
I had 3 little ideas over the weekend that I implemented carefully into one of the (4 main) routines.
And now the mode 0 eye is drawn 3 times in 3.9 seconds!!!

Now I need to put the same optimisations into the other 3 routines, and perhaps we'll get close to 1 second per-eye!
That would be mindblowing!
8)

I never imagined that I would figure out how to make it run anything like this fast!

Hi Ervin,
Do you have the compiled test code available somewhere? I could run it through my z80 profiler and provide results to help you with optimizations.

can we include this profiler into i.e. cpctelera toolchain ?

Quote from: Docent on 16:43, 23 August 16
Hi Ervin,
Do you have the compiled test code available somewhere? I could run it through my z80 profiler and provide results to help you with optimizations.

That sounds very interesting!
I'd love to see the results from something like that.
(I'm also very curious how such a profiler would work).

I've added a new download (bres_2.zip) to the first post in this thread.
8)

Quote from: ervin on 23:58, 23 August 16

That sounds very interesting!
I'd love to see the results from something like that.
(I'm also very curious how such a profiler would work).

I've added a new download (bres_2.zip) to the first post in this thread.
8)

Here's the result. I have to break it at #8041 after one loop. The numbers are in machine cycles, first goes the timing of  executing one instruction, followed by total execution time.
The obvious place for optimization is l85c7 - it is called 4800 times and consumes 96% of execution time. Inside it there are l9689 and l91f0 taking the major amount of time. Send me a cdb file generated by sdcc for this code and I'll generate more meaningful disassembly with source and names.
The disassembly is generated by The Profiler - call-graph profiler and debugging simulator. It basically simulates execution of each instruction of a cpu and during it tracks calls, generates labels and counts the execution time, memory accesses, coverage etc.
btw - the coverage is around 47%, so there is a lot of unused code inside.

Quote from: SRS on 19:45, 23 August 16
can we include this profiler into i.e. cpctelera toolchain ?

It is windows ui application only, so probably unlikely...

Quote from: Docent on 04:06, 25 August 16
Here's the result. I have to break it at #8041 after one loop. The numbers are in machine cycles, first goes the timing of  executing one instruction, followed by total execution time.
The obvious place for optimization is l85c7 - it is called 4800 times and consumes 96% of execution time. Inside it there are l9689 and l91f0 taking the major amount of time. Send me a cdb file generated by sdcc for this code and I'll generate more meaningful disassembly with source and names.
The disassembly is generated by The Profiler - call-graph profiler and debugging simulator. It basically simulates execution of each instruction of a cpu and during it tracks calls, generates labels and counts the execution time, memory accesses, coverage etc.
btw - the coverage is around 47%, so there is a lot of unused code inside.

Hmmm... very very interesting.
Thanks for taking the time to look into this.

The version I uploaded contains other tests, but access to them has been disabled while I concentrate on speeding up the routines used to draw the eye. That's probably why you only found 47% coverage.

Now, the routine that is called 4800 times... that's very likely the main drawLine routine, which goes on to call other routines (based on the octant the line sits in etc.)

The code called by drawLine is absolutely the busiest part of the code.
I've got it set to draw the eye 30 times per test, and each eye contains many dozens of lines.
So the bulk of the test is concerned with traversing Bresenham's algorithm.

Curious, what's a cdb file?
I'm not sure where to find it.

[EDIT] I found information about cdb files.
I'll hopefully have time tonight to generate a new DSK file, along with the CDB file.

Quote from: ervin on 05:02, 25 August 16
[EDIT] I found information about cdb files.
I'll hopefully have time tonight to generate a new DSK file, along with the CDB file.

Please just send the binary (or rel) and cdb file if possible - there is no need to put them on dsk, in such case I have to extract them back from dsk.

Quote from: ervin on 05:02, 25 August 16
[EDIT] I found information about cdb files.
I'll hopefully have time tonight to generate a new DSK file, along with the CDB file.

A DSK would be very nice! Thank you!  :)

Quote from: TFM on 15:13, 25 August 16

A DSK would be very nice! Thank you!  :)

To see how fast the mode 0 eye is drawn now, download bres_2.zip from the first post in this thread.
:)

Quote from: Docent on 13:41, 25 August 16
Please just send the binary (or rel) and cdb file if possible - there is no need to put them on dsk, in such case I have to extract them back from dsk.

Took a few moments to figure out how to create cdb files from cpctelera's build_config.mk file.
Anyway, the attached file contains the cdb, rel and bin files.

Quote from: ervin on 15:25, 25 August 16
To see how fast the mode 0 eye is drawn now, download bres_2.zip from the first post in this thread.
:)

That is really good! Now the CPC would have needed that for BASIC or for the demonstration tape/disc coming with the computer.  :)

Quote from: TFM on 15:35, 25 August 16

That is really good! Now the CPC would have needed that for BASIC or for the demonstration tape/disc coming with the computer.  :)

Thanks.
;D

I just wish I could make it a bit faster... I've taken it to the limit of my z80 abilities.

Quote from: ervin on 15:36, 25 August 16
I just wish I could make it a bit faster... I've taken it to the limit of my z80 abilities.

Did you try this ? for Mode 0 it is "enough"

http://www.edepot.com/lineex.html (http://www.edepot.com/lineex.html)


// Extremely Fast Line Algorithm Var E (Addition Fixed Point PreCalc ModeX) // Copyright 2001-2, By Po-Han Lin

// Freely useable in non-commercial applications as long as credits // to Po-Han Lin and link to [url=http://www.edepot.com]http://www.edepot.com[/url] is provided in // source code and can been seen in compiled executable. // Commercial applications please inquire about licensing the algorithms. // // Lastest version at [url=http://www.edepot.com/phl.html]Technology Depot[/url] // Note: This version is for small displays like on cell phones. // with 256x256 max resolution.  For displays up to 65536x65536 // please visit [url=http://www.edepot.com/linee.html]http://www.edepot.com/linee.html[/url] // used by myLine void myPixel(SURFACE* surface, int x,int y) { // PLOT x,y point on surface } // THE EXTREMELY FAST LINE ALGORITHM Variation E (Addition Fixed Point PreCalc Small Display) // Small Display (256x256) resolution. void myLine(SURFACE* surface, int x, int y, int x2, int y2) { bool yLonger=false; int shortLen=y2-y; int longLen=x2-x; if (abs(shortLen)>abs(longLen)) { int swap=shortLen; shortLen=longLen; longLen=swap; yLonger=true; } int decInc; if (longLen==0) decInc=0; else decInc = (shortLen << 8) / longLen; if (yLonger) { if (longLen>0) { longLen+=y; for (int j=0x80+(x<<8);y<=longLen;++y) { myPixel(surface,j >> 8,y); j+=decInc; } return; } longLen+=y; for (int j=0x80+(x<<8);y>=longLen;--y) { myPixel(surface,j >> 8,y); j-=decInc; } return; } if (longLen>0) { longLen+=x; for (int j=0x80+(y<<8);x<=longLen;++x) { myPixel(surface,x,j >> 8); j+=decInc; } return; } longLen+=x; for (int j=0x80+(y<<8);x>=longLen;--x) { myPixel(surface,x,j >> 8); j-=decInc; } }


Quote from: SRS on 18:22, 25 August 16
Did you try this ? for Mode 0 it is "enough"

http://www.edepot.com/lineex.html (http://www.edepot.com/lineex.html)

Code Select Expand


// Extremely Fast Line Algorithm Var E (Addition Fixed Point PreCalc ModeX) // Copyright 2001-2, By Po-Han Lin

// Freely useable in non-commercial applications as long as credits // to Po-Han Lin and link to [url=http://www.edepot.com]http://www.edepot.com[/url] is provided in // source code and can been seen in compiled executable. // Commercial applications please inquire about licensing the algorithms. // // Lastest version at [url=http://www.edepot.com/phl.html]Technology Depot[/url] // Note: This version is for small displays like on cell phones. // with 256x256 max resolution.  For displays up to 65536x65536 // please visit [url=http://www.edepot.com/linee.html]http://www.edepot.com/linee.html[/url] // used by myLine void myPixel(SURFACE* surface, int x,int y) { // PLOT x,y point on surface } // THE EXTREMELY FAST LINE ALGORITHM Variation E (Addition Fixed Point PreCalc Small Display) // Small Display (256x256) resolution. void myLine(SURFACE* surface, int x, int y, int x2, int y2) { bool yLonger=false; int shortLen=y2-y; int longLen=x2-x; if (abs(shortLen)>abs(longLen)) { int swap=shortLen; shortLen=longLen; longLen=swap; yLonger=true; } int decInc; if (longLen==0) decInc=0; else decInc = (shortLen << / longLen; if (yLonger) { if (longLen>0) { longLen+=y; for (int j=0x80+(x<<;y<=longLen;++y) { myPixel(surface,j >> 8,y); j+=decInc; } return; } longLen+=y; for (int j=0x80+(x<<;y>=longLen;--y) { myPixel(surface,j >> 8,y); j-=decInc; } return; } if (longLen>0) { longLen+=x; for (int j=0x80+(y<<;x<=longLen;++x) { myPixel(surface,x,j >>; j+=decInc; } return; } longLen+=x; for (int j=0x80+(y<<;x>=longLen;--x) { myPixel(surface,x,j >>; j-=decInc; } }


Hmmm... that's an interesting algorithm.
Looks very simple too.
Thanks!

I'll put together a test version shortly...

Quote from: ervin on 15:30, 25 August 16
Took a few moments to figure out how to create cdb files from cpctelera's build_config.mk file.
Anyway, the attached file contains the cdb, rel and bin files.

Thanks, here's the file.
Unfortunately, your cdb doesn't contain address bindings for telera calls - you probably need to compile it together to generate cdb with all symbols.
Also If you decide to make the source of main.c available, send it on and I'll generate profiling file in mixed c source/disassembly mode that is much easier to analyze.
I have a quick look at your code and there is some space for optimization left :)
In the main draw loop you do not use the AF' register. The following code in drawSteepLineDownMode0


l959d:
inc iy ;10T     715320T FD 23
exx ;4T     238440T D9
ld a,ixh ;0T     476880T DD 7C
dec a ;4T     238440T 3D
jr nz,l95b2 ;7/12T     598320T 20 0D
rlc c ;8T     234000T CB 01
inc hl ;6T     234000T 23
ld ixh,#00 ;0T     351000T DD 26 00
rrc b ;8T     234000T CB 08
exx ;4T     117000T D9
djnz l9572 ;8/13T     466320T 10 C2
jr l95c1 ;12T       2520T 18 0F
l95b2:
rrc c ;8T     242880T CB 09
inc ixh ;0T     242880T DD 24
rrc b ;8T     242880T CB 08
exx ;4T     121440T D9
djnz l9572 ;8/13T     485760T 10 B7

can be replaced with :

(old code commented out; you also need to setup a' earlier)
l959d:
inc iy ;10T     715320T FD 23
exx ;4T     238440T D9
ex af,af'                                    ;4T       238440T
; ld a,ixh ;0T     476880T DD 7C
dec a ;4T     238440T 3D
jr nz,l95b2 ;7/12T     598320T 20 0D
rlc c ;8T     234000T CB 01
inc hl ;6T     234000T 23
xor a                                        ;4T       117000T
; ld ixh,#00 ;0T     351000T DD 26 00
rrc b ;8T     234000T CB 08
l95ad:
ex af,af'                                    ;4T       117000T
exx ;4T     117000T D9
djnz l9572 ;8/13T     466320T 10 C2
jr l95c1 ;12T       2520T 18 0F
l95b2:
rrc c ;8T     242880T CB 09
inc a                                         ;4T               125440T
inc a                                         ;4T               125440T
; inc ixh ;0T     242880T DD 24
rrc b ;8T     242880T CB 08
jr l95ad                                     ;12T             364320T
; exx ;4T     121440T D9
; djnz l9572 ;8/13T     485760T 10 B7


you'll gain 590320 cycles and ~2% speedup of this routine. Applying this to drawSteepLineUpMode0, drawGentleLineUpMode0: and drawGentleLineDownMode0 can bring you up to 8% gain.
Perhaps discardLineMode0 and initMasksMode0 could be also moved out of the drawing loop?

Of course!!! I totally forgot about AF' !!!
Thanks for the tip.

Fabulous! Very happy with that suggestion!
I'll put those in shortly.

discardLine and initMasks are only run once per line; they aren't inside a loop per se, so I think they'll be ok.
However, I can probably make them a little more efficient, once the main tight loop(s) are finished.
8)

Quote from: ervin on 04:38, 28 August 16
Of course!!! I totally forgot about AF' !!!
Thanks for the tip.

Fabulous! Very happy with that suggestion!
I'll put those in shortly.

discardLine and initMasks are only run once per line; they aren't inside a loop per se, so I think they'll be ok.
However, I can probably make them a little more efficient, once the main tight loop(s) are finished.
8)

Also operations on ixl are expensive - you could try to replace it with a' for eg.

; setup a' earlier
l9572:
exx ;4T     757680T D9
ld a,(hl) ;7T    1515360T 7E
and b ;4T     757680T A0
or c ;4T     757680T B1
ld (hl),a ;7T    1515360T 77
ex af,af' ;4T 757680T
; ld a,ixl ;0T    1515360T DD 7D
cp #07 ;7T    1515360T FE 07
jr nz,l9589 ;7/12T    2178360T 20 0C
ld de,#c850 ;10T     284040T 11 50 C8
add hl,de ;11T     284040T 19
ld de,#0800 ;10T     284040T 11 00 08
xor a          ;4T         94680
; ld ixl,#00 ;0T     284040T DD 2E 00
jr l958c ;12T     284040T 18 03
l9589:
add hl,de ;11T    1989000T 19
inc a ;4T       663000
; inc ixl ;0T    1326000T DD 2C
l958c:
ex af,af' ;4T     757680T
exx ;4T     757680T D9


You'll get the main loop cost down by 852360 cycles, which is 5.5% of the main loop.
The best approach would be to completely replace operation on ixl with another register - for example replace de' with sp, and use it instead af' I suggested above. As sp is used later, replace it there with bc. This also require more changes in other parts of the loop - you'll need to replace djnz with another check, for example using a' or ixl as a loop counter.

for example:

; init de' to 7
l9572:
exx ;4T     757680T D9
ld a,(hl) ;7T    1515360T 7E
and b ;4T     757680T A0
or c ;4T     757680T B1
ld (hl),a ;7T    1515360T 77
ld a,d ;4T     757680T
cp e ;4T     757680T
; ld a,ixl ;0T    1515360T DD 7D
; cp #07 ;7T    1515360T FE 07
jr nz,l9589 ;7/12T    2178360T 20 0C
ld sp, #c850
; ld de,#c850 ;10T     284040T 11 50 C8
add hl,sp
; add hl,de ;11T     284040T 19
ld sp,#800
; ld de,#0800 ;10T     284040T 11 00 08
ld d,0 ;8T 189360
; ld ixl,#00 ;0T     284040T DD 2E 00
jr l958c ;12T     284040T 18 03
l9589:
add hl,sp
; add hl,de ;11T    1989000T 19
inc d ;4T 663000
; inc ixl ;0T    1326000T DD 2C
l958c:
exx ;4T     757680T D9
add hl,bc
; add hl,sp ;11T    2273040T 39
add hl,de ;11T    2273040T 19


This change will speed up this loop by 2367720 cycles - over 15%!

Another thing to do is branch optimization - try changing the code to not take the branch in main loop, for eg. replace


l9572:
exx ;4T     757680T D9
ld a,(hl) ;7T    1515360T 7E
and b ;4T     757680T A0
or c ;4T     757680T B1
ld (hl),a ;7T    1515360T 77
ld a,ixl ;0T    1515360T DD 7D
cp #07 ;7T    1515360T FE 07
jr nz,l9589 ;7/12T    2178360T 20 0C
ld de,#c850 ;10T     284040T 11 50 C8
add hl,de ;11T     284040T 19
ld de,#0800 ;10T     284040T 11 00 08
ld ixl,#00 ;0T     284040T DD 2E 00
jr l958c ;12T     284040T 18 03
l9589:
add hl,de ;11T    1989000T 19
inc ixl ;0T    1326000T DD 2C
l958c:


with

l9572:
exx ;4T     757680T D9
ld a,(hl) ;7T    1515360T 7E
and b ;4T     757680T A0
or c ;4T     757680T B1
ld (hl),a ;7T    1515360T 77
ld a,ixl ;0T    1515360T DD 7D
cp #07 ;7T    1515360T FE 07
jr z, nextblock
^^^
l9589:
add hl,de ;11T    1989000T 19
inc ixl ;0T    1326000T DD 2C
l958c:

...
nextblock
ld de,#c850 ;10T     284040T 11 50 C8
add hl,de ;11T     284040T 19
ld de,#0800 ;10T     284040T 11 00 08
ld ixl,#00 ;0T     284040T DD 2E 00
jr l958c ;12T     284040T 18 03


the cost of not taking the branch in jr is 7 cycles against 12 when the condition is met. In this case ixl is a counter from 0 to 7 so in your original code you are taking the branch 7 times and not taking 1. The total cost for one full iteration is 92 cpc cycles. When you invert the check the cost will be 68 cpc cycles - 27% gain! Only this small code reorganization will speed up your main loop by another ~2%

That's tremendous stuff!
Thank you!

Bear in mind all those timings are wrong for the CPC and optimizations that work on other machines may hurt performance on the CPC. It's better to base everything on NOP timing.

Page2 to the rescue to find proper timings:
http://wiki.octoate.de/lib/exe/fetch.php/amstradcpc:z80_cpc_timings_cheat_sheet.20131019.pdf (http://wiki.octoate.de/lib/exe/fetch.php/amstradcpc:z80_cpc_timings_cheat_sheet.20131019.pdf)

Quote from: andycadley on 19:41, 28 August 16
Bear in mind all those timings are wrong for the CPC and optimizations that work on other machines may hurt performance on the CPC. It's better to base everything on NOP timing.

its always good to check before giving false opinions :)
Of course you're wrong - while single instruction timing doesn't show adjusted cpc clocks cycles, the total sum supports wait states introduced by the gate array. Here's the excerpt from the posted source:

ld hl,#8045 ;10T         12T 21 45 80
ld b,(hl) ;7T          8T 46
                                                         ^^              ^^


btw: the way adjusted timing is displayed is configurable and I prefer to see the original instruction timing for single execution.

Alrighty, using suggestions from @Docent (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1534) has lead to a small but measurable speed improvement.

Before the EX AF,AF' implementation, it took 36 seconds to draw the eye 30 times in mode 0.
Now it takes 35.4 seconds!
Not a huge difference (about 1.6%), but I'll take it - every little bit counts!

Unfortunately the suggestion to flip the JR's lead to a *very* small slowdown, so I ended up not using that.
This slowdown is due to the flow of code... flipping the JR's would actually force an extra jump every 8th check.

Nonetheless, my program is now overall a bit faster, so I'm chuffed!

I've uploaded the latest version to the first post in this thread, as bres_3.zip.
It contains the dsk with the mode 0 executable, and also all the mode 0 source code (cpctelera/sdcc) for anyone interested.
It's a bit horrifying (due to the nasty optimisations that I've implemented), but oh well.

Test A draws the eye 30 times.
Tests B to J perform tests of each line routine against a clipping window. These tests use double-buffering, but without vsync so there is a little flickering.
Test K is an early version of pixel plotting! It works well, but is rather slow. Speeding up plotting will be my next focus, and the other routines will benefit a little bit as well, due to (hopefully) improved setup code for each line.

For tests B to K, you can use the cursor keys to move the lines around inside the clipping window.

Incidentally, test B looks like it is a plotting test, but it actually isn't - it's simply a line routine designed to draw a line that is only one pixel in size. Once the plotting routines (used in test K) are faster, I'll simply call the plot routine in the single pixel line routine (used in test B).

Another thing I need to get started on is to very carefully put the latest round of optimisations into the mode 1 and mode 2 code...
Quite frankly, that is kind of scary!

Guys, just a small heads up - there's a nice formatting command, [code ] - [/ code] (remove spaces) to make it all more readable:




   exx                  ;4T       757680T   D9
   ld a,(hl)               ;7T      1515360T   7E
   and b                  ;4T       757680T   A0
   or c                  ;4T       757680T   B1
   ld (hl),a               ;7T      1515360T   77
   ld a,ixl               ;0T      1515360T   DD 7D
   cp #07                  ;7T      1515360T   FE 07
   jr nz,l9589               ;7/12T      2178360T   20 0C
   ld de,#c850               ;10T       284040T   11 50 C8
   add hl,de               ;11T       284040T   19
   ld de,#0800               ;10T       284040T   11 00 08
   ld ixl,#00               ;0T       284040T   DD 2E 00
   jr l958c               ;12T       284040T   18 03
l9589:
   add hl,de               ;11T      1989000T   19
   inc ixl                  ;0T      1326000T   DD 2C
l958c:


with
l9572:
   exx                  ;4T       757680T   D9
   ld a,(hl)               ;7T      1515360T   7E
   and b                  ;4T       757680T   A0
   or c                  ;4T       757680T   B1
   ld (hl),a               ;7T      1515360T   77
   ld a,ixl               ;0T      1515360T   DD 7D
   cp #07                  ;7T      1515360T   FE 07
jr z, nextblock
^^^
l9589:
   add hl,de               ;11T      1989000T   19
   inc ixl                  ;0T      1326000T   DD 2C
l958c:


...
nextblock
    ld de,#c850               ;10T       284040T   11 50 C8
   add hl,de               ;11T       284040T   19
   ld de,#0800               ;10T       284040T   11 00 08
   ld ixl,#00               ;0T       284040T   DD 2E 00
   jr l958c               ;12T       284040T   18 03


@ervin (http://www.cpcwiki.eu/forum/index.php?action=profile;u=82):

first view at source recommendation: you may change labels like 00800$: to speaking labels like drawxy1:, would make it easier
to read and maintain.

More to come :)

Yep, I tried that, but SDCC wouldn't compile with such labels.
In fact the documentation says that asm labels must be in the form 00xxx$.
:(

Quote from: Gryzor on 13:19, 29 August 16
Guys, just a small heads up - there's a nice formatting command, [code ] - [/ code] (remove spaces) to make it all more readable:

Thanks for the tip - I updated my messages and they are much more readable now

Quote from: ervin on 23:33, 29 August 16
Yep, I tried that, but SDCC wouldn't compile with such labels.
In fact the documentation says that asm labels must be in the form 00xxx$.
:(

Now this is weired. Just tried it (/sdcc-3.5.5) and got this ASM (Part): See Label "neun" without errors in compile.


;src/main.c:393: void initMasksMode0()__naked{
;    ---------------------------------
; Function initMasksMode0
; ---------------------------------
_initMasksMode0::
;src/main.c:439: __endasm;
    ld    hl,#_colourMask
    ld    (hl),#0x55
    xor    a
    ld    hl,#_lineColour
    bit    0,(hl)
    jr    Z,neun
    ld    a,#0x80
     neun:
    bit    1,(hl)
    jr    Z,00901$
    set    3,a
     00901$:
    bit    2,(hl)
    jr    Z,00902$
    set    5,a
     00902$:
    bit    3,(hl)
    jr    Z,00903$
    set    1,a
     00903$:
    ld    (#_lineMask),a
    ret

That is indeed weird!
I don't know why that's happening...

Quote from: SRS on 21:15, 30 August 16
Now this is weired. Just tried it (/sdcc-3.5.5) and got this ASM (Part): See Label "neun" without errors in compile.

Code Select Expand

;src/main.c:393: void initMasksMode0()__naked{
;    ---------------------------------
; Function initMasksMode0
; ---------------------------------
_initMasksMode0::
;src/main.c:439: __endasm;
    ld    hl,#_colourMask
    ld    (hl),#0x55
    xor    a
    ld    hl,#_lineColour
    bit    0,(hl)
    jr    Z,neun
    ld    a,#0x80
     neun:
    bit    1,(hl)
    jr    Z,00901$
    set    3,a
     00901$:
    bit    2,(hl)
    jr    Z,00902$
    set    5,a
     00902$:
    bit    3,(hl)
    jr    Z,00903$
    set    1,a
     00903$:
    ld    (#_lineMask),a
    ret

You can use labels with more meaningful names between _asm/_endasm directives and it should work IF the compiler do not generate any temporary local labels for the function code before your asm code. Otherwise definition of your label will limit the scope of the temporary local compiler-generated label and the generated asm code wont assemble.
In other words - if you have a c-function, containing only assembly code, you can use normal label names in your code.
If you have a c function containing mixed c-source and asm, stick to label in the form of n$, where n<100.

Quote from: Docent on 04:52, 31 August 16
You can use labels with more meaningful names between _asm/_endasm directives and it should work IF the compiler do not generate any temporary local labels for the function code before your asm code. Otherwise definition of your label will limit the scope of the temporary local compiler-generated label and the generated asm code wont assemble.
In other words - if you have a c-function, containing only assembly code, you can use normal label names in your code.
If you have a c function containing mixed c-source and asm, stick to label in the form of n$, where n<100.

Ah, that makes sense.
Thanks.

Hi folks.

Alrighty, the mode 1 and 2 sources have both been updated with all the optimisations from the mode 0 code.
They are much faster now than they used to be.
8)

Some quick benchmarks (to draw the eye 30 times):
mode 0: 35.0 secs
mode 1: 48.7 secs
mode 2: 74.8 secs

Considering that mode 1 has twice as many pixels horizontally (compared with mode 0), and mode 2 has 4 times as many, those times are pretty good!

Also, line clipping has been sped up by around 13% in all 3 modes, thanks to a small (and laughably simple) idea I had while sitting in a taxi!

TO DO:
- speed up plotting (test K)
- shrink the binary file
- make a game with this stuff!

I've attached bres4.zip to the first post in this thread.
It contains 3 dsk files - one for each screen mode.

You can use the arrow keys to move lines around inside the clipping window in all tests except A.
This will demonstrate how the clipping looks.

Mode 0
https://www.dropbox.com/s/11dtwjf7076wdg2/eye0.png?raw=1 (https://www.dropbox.com/s/11dtwjf7076wdg2/eye0.png?raw=1)

Mode 1
https://www.dropbox.com/s/f2tpt4idg1ws57y/eye1.png?raw=1 (https://www.dropbox.com/s/f2tpt4idg1ws57y/eye1.png?raw=1)

Mode 2
https://www.dropbox.com/s/78szhub0uztfhg0/eye2.png?raw=1 (https://www.dropbox.com/s/78szhub0uztfhg0/eye2.png?raw=1)

I don't believe it... I just found another optimisation, which speeds up unclipped lines by at least 5%!

Latest times (to draw the eye 30 times):
mode 0: 32.3 secs
mode 1: 45.5
mode 2: 71.1

How are you doing it? Making dots, or composing lines out of short horizontal and vertical lines? I use the latter one.

Quote from: TFM on 18:02, 02 September 16
How are you doing it? Making dots, or composing lines out of short horizontal and vertical lines? I use the latter one.

Only out of dots.
I did briefly look into the segments technique, but didn't really understand it.

Hi folks.

Plotting is now nice and fast, and lines that are only one pixel long are now drawn using the plot routine.

There has been a nice side-effect of the improved plotting routine. The setup code for each line to be drawn has been sped up a *little* as a result of using code from the plot setup routine. It's not really noticeable, but is measurable when drawing the eye 30 times.

There are a couple more line setup optimisations to put in based on the plotting code, and I think they will make a measurable difference, but I think the speed is almost at the limit of my ability.
;D

Woohoo!!!
I've found an optimisation for the line clipping routines.
I've got some more testing to do, but if it works, the routines in question will be almost 15% faster!

BUT I'm more excited about an improvement in the line drawing routines, after applying a similar optimisation.
Drawing the (mode 0) eye 30 times now takes 30.2 seconds (5% speed improvement)! Almost down to 1 second per eye!
REALLY REALLY happy with that!
;D

i'm looking forward to play with your routines!

Quote from: roudoudou on 07:55, 09 September 16
i'm looking forward to play with your routines!

I'll be releasing the source code soon.
:)

Unfortunately it isn't commented very well at all, so the code is kind of useless for anyone else to learn from (especially after all the very low-level optimisation that makes the code very hard to follow).

Oh well, I guess the point is just to provide code that works (and hopefully works well)!

Hi folks.

Alrighty then!
I'm ready to release the source code, as well as the test program.

I'm *very* happy with the speed, and the size is good as well.

For anyone interested, please download the 3 files in the original post of this thread (bres0.zip, bres1.zip and bres2.zip).
They each contain source code, a CDT file and a DSK file.

In each of the 3 test programs:
- A draws the eye
- B to J draw various lines inside a clipping window (try the arrow keys!)
- K plots a bunch of pixels inside a clipping window (again, try the arrow keys!)

This little project is the culmination of something I've wanted to create for a very long time, and I'm tremendously happy with the results.

If anyone wants to use these plotting/drawing routines with CPCtelera, feel free!
8)

Enjoy!

Hi everyone.

Well, here it is.
The final version of my line drawing program.

The attachments in the original post have been updated to v1.1.
DSK, CDT and SDCC source files are included.

Changes in this version include:
- some minor optimisations
- new test [L] - a cube! (use the left/right arrow keys to spin the cube)

My 3D code isn't particularly great, so perhaps the 3D calculations aren't as fast as they could be, but the line drawing itself is very fast.
8)

It has been a great pleasure to work on this project, and I hope that someone out there finds my code useful.

Now it's time to work on something more modern!
Perhaps something for PC's, or smartphones... not sure yet.
Regardless, I've just bought the GameMaker package from Humble Bundle, and I'm *really* excited to dive in!

Great work, you really should Pull your code on CPCTelera Github.

Beside drawing line is an opened Issue :
Draw line · Issue #21 · lronaldo/cpctelera · GitHub (https://github.com/lronaldo/cpctelera/issues/21)

Quote from: Arnaud on 17:05, 22 September 16
Great work, you really should Pull your code on CPCTelera Github.

Beside drawing line is an opened Issue :
Draw line · Issue #21 · lronaldo/cpctelera · GitHub (https://github.com/lronaldo/cpctelera/issues/21)

Thanks Arnaud.

I'd *love* to add my code to cpctelera, but there are 2 reasons that I haven't yet:
- I don't know how to add it
- It's very messy code; not well commented at all (I was more concerned with as much low-level optimisation as possible, so the code stopped being neat and tidy)

If anyone else is interested in adding the code to cpctelera, please go ahead.
:)

Hi folks.

Just a quick update.

I've re-organised parts of the code, and also added some comments which should hopefully make this stuff easier to use.
Please see the first post of this thread for the new download.

If anyone wants to use this code, and runs into any trouble with it, please let me know, and I'll try to help out.
It's all very easy to use once you know what to do.
8)