2D vector clipping

Page 1/2
| 2

By NYYRIKKI

Enlighted (5939)

NYYRIKKI's picture

23-07-2004, 11:28

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...

Login or register to post comments

By anonymous

incognito ergo sum (116)

anonymous's picture

23-07-2004, 14:45

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.

By snout

Ascended (15187)

snout's picture

23-07-2004, 14:48

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 ;)

By MicroTech

Champion (385)

MicroTech's picture

23-07-2004, 14:55

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

By wolf_

Ambassador_ (9971)

wolf_'s picture

23-07-2004, 14:55

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

By Sonic_aka_T

Enlighted (4130)

Sonic_aka_T's picture

23-07-2004, 20:10


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

Are you using 8 or 16bit coordinates?

By flyguille

Prophet (3028)

flyguille's picture

23-07-2004, 21:14

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.

By Sonic_aka_T

Enlighted (4130)

Sonic_aka_T's picture

23-07-2004, 21:19

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...

By flyguille

Prophet (3028)

flyguille's picture

23-07-2004, 21:44

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

By NYYRIKKI

Enlighted (5939)

NYYRIKKI's picture

23-07-2004, 22:27

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!" Smile

By flyguille

Prophet (3028)

flyguille's picture

23-07-2004, 23:10

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

Page 1/2
| 2