Does anyone know, where to find a fast (assembler) clipping routine for 2D vectors?

I mean routine, that would change LINE (40,-10)-(-10,15) type of routine to LINE (20,0)-(0,10)

This sounds easy, but calculating accuracy is often a problem...

I suppose plotting the line (using bresenham line algo) until it hits the border is not an option? ^^;
I'm not very mathematically inclined, but after googling I found something about a "Cohen & Sutherland" algorithm.

This website (from Ian 'Elite' C G Bell) contains a lot of useful information for (game) programmers. It also has several sections on vectors. I didn't look, but something about vector clipping is bound to be mentioned over there. I guess

hmm. that site is a bit over-the-top concerning maths I think..

I've no assembly routine for that, I hope C can be useful.
1) let's say (xMin, yMin) and (xMax, yMax) are the limits of your "output window"

2) let's define clip codes to identify to which region a 2D point belongs to:

#define CLIP_NONE       ((char) 0x00)
#define CLIP_XL         ((char) 0x01)
#define CLIP_XH         ((char) 0x02)
#define CLIP_YL          ((char) 0x04)
#define CLIP_YH         ((char) 0x08)

3) let's say Pa(xa,ya) and Pb(xb,yb) your vector coordinates

4) call this function to retrieve the "region-code" for Pa and Pb, we get maska and maskb

char GetRegionCode(int x, int y)
{
    char clpMsk = CLIP_NONE;


                   if (x > xMax)
                        clpMsk |= CLIP_XH;
                    if (x < xMin)
                        clpMsk |= CLIP_XL;
                    if (y > yMax)
                        clpMsk |= CLIP_YH;
                    if (y < yMin)
                        clpMsk |= CLIP_YL;

                    return(clpMsk);
}

5) check if vector can be rejected or drawn without clipping

    if (maska | maskb)
    {
        if (maska & maskb)
        {
            /* vector can be safely rejected */
        }
        else
        {
            /* nothing can be safetly assumed: submit vector to clipping */
            if (maska)
                Pa is out, Pb in in
            else
                Pa is in, Pb is out
        }
    }
    else
    {
        /* vector can be safely drawn without clipping */
    }

6) clipping function for X axis (can be simply adapted for Y axis)

/*
    IN
        g_target = clipping limit
        g_x1 = xa
        g_y1 = ya
        g_x2 = xb
        g_y2 = yb

    OUT
        g_xm, g_ym

*/
void FndIS_X()
{
    static int xa, ya, xb, yb;
    static int m;
    static boolean stayIn, swap, useb;


    xa = g_x1;
    ya = g_y1;
    xb = g_x2;
    yb = g_y2;

    /* variable set a < variable set b, if necessary swap them */
    swap = FALSE;
    if (xa > xb)
        swap = TRUE;

    /* swap set di variabili */
    if (swap)
    {
        /* m = a */
        g_xm = xa;
        g_ym = ya;

        /* a = b */
        xa = xb;
        ya = yb;

        /* b = m */
        xb = g_xm;
        yb = g_ym;
    }

    useb = FALSE;
    if (g_target == xb)
        useb = TRUE;

    if (useb)
    {
        if (swap == FALSE)
        {
            g_xm = xb;
            g_ym = yb;
        }
        goto Quit;
    }

    for (stayIn = TRUE; stayIn; )
    {
        g_xm = (xa + xb) / 2;
        g_ym = (ya + yb) / 2;


        m = g_xm;

        if (m == g_target)
            break;
        else
        {
            if (m > g_target)
            {
                xb = g_xm;
                yb = g_ym;
            }
            else
            {
                xa = g_xm;
                ya = g_ym;
            }
        }
    }

Quit:
    /* g_xm, g_ym contain new vector vertex */
    ;
}

This pseudo code has not been compiled but is a simplified version of the clipping routine used in E3D so it should work.
Let me know if it is useful.

Ciao
MicroTech

Quote:

Does anyone know, where to find a fast (assembler) clipping routine for 2D vectors?

Are you using 8 or 16bit coordinates?

nah, not need to plot anything.....

you can do with calculating , from where are passing the line when cross the x or Y = 0, in order to do a cut.

Well, I don't know how he does his calculations. It may well be easier to do the actual clipping in 16bits anyways. It would probably increase accuracy...

well, maybe is a bit hard in assembler because got a DIV function... let me think

One will be
When the line go out of the screen on the left side, i mean X1 = -X . So is needed to calcutate the Y position when X is on its 0 value.

It is something like

stepY = (Y2-Y1) / (X2 - X1)

is necesary to do this operation in signed mode and in 16 bits.

So

Y_pos_IN_column0 = Y1 + stepY * (0-X1)

or something like that, and as you got a * and a / ... is hard to do in assembler, so is better to use fast bucles

Yes, I was thinking 16bit signed coordinates. Flyguille has same basic idea, that I came up when I was thinking this. The problem is, that you end up to very small numbers, that are not easy to divide or multibly.

I'm not sure, that I got all of the idea of MicroTech. (Sorry, I don't read C or Pascal) Anyway if I understand correctly, this routine goes trough the line. The idea of doing it this way might be useful on some cases, but if you are going to use long vectors, you need to get result in standard time or you want to use VDP for drawing the line, this is not a good method.

I was just hoping, that someone would have said, "Yes, I have one working code here in my Stupid Z80 tricks for abnormal geeks book, use this!"

well, well, well

if you think about the formulaa, you can do easyly some bucles..

look for fast DIV and MUL routines in the MAP website.
map.tni.nl

I always use the routines as suggested in 'Programming the Z80' by R. Zaks. Some of those routines are also on the site fly suggested. If you need a specific routine I'd be happy to look one up. IIRC it included 16bit divisions and multiplications.

Quotation from map.tni.nl:

Quote:

Well, that's it. Thanks go to mr. Rodnay Zaks (although I somehow really doubt he'll read this) for writing his book "Programming of the Z80", which lists the routines on which I based the ones above, or sometimes even shamelessly copied ^_^. If you have any suggestions for speed improvements, or know of another method which might be faster under certain conditions, please let me know.

Actually this task needs quite a custom DIV & MULT routines.

It needs 1/X routine, where X is 16bit number and where we don't need the actual result (as that is always 0) but 16bit reminder. (1/1 can be handled as special case)

Also in multibly we need to multibly two 16bit numbers to get a 32bit number, but we really don't need lower 16bits to anything.

you can adapt the routines on map.tni.nl for that.