Subversion Repositories planix.SVN

#include "vnc.h"
#include "vncs.h"

static int tot;
static void rprint(Rlist*);

static void
growrlist(Rlist *rlist, int n)
{
        int old;

        if(rlist->nrect+n <= rlist->maxrect)
                return;

        old = rlist->maxrect;
        while(rlist->nrect+n > rlist->maxrect){
                if(rlist->maxrect == 0)
                        rlist->maxrect = 16;
                else
                        rlist->maxrect *= 2;
        }

        tot += rlist->maxrect - old;
        if(tot > 10000)
                sysfatal("too many rectangles");

        rlist->rect = realloc(rlist->rect, rlist->maxrect*sizeof(rlist->rect[0]));
        if(rlist->rect == nil)
                sysfatal("realloc failed in growrlist");
}

static void
rappend(Rlist *rl, Rectangle r)
{
        growrlist(rl, 1);
        rl->rect[rl->nrect++] = r;
}

/* remove rectangle i from the list */
static int
rtrim(Rlist *r, int i)
{
        if(i < 0 || i >= r->nrect)
                return 0;
        if(i == r->nrect-1){
                r->nrect--;
                return 1;
        }
        r->rect[i] = r->rect[--r->nrect];
        return 1;
}

static int
rectadjacent(Rectangle r, Rectangle s)
{
        return r.min.x<=s.max.x && s.min.x<=r.max.x &&
               r.min.y<=s.max.y && s.min.y<=r.max.y;
}

/*
 * If s shares three edges with r, compute the
 * rectangle r - s and return 1.
 * Else return 0.
 */
static int
rectubr(Rectangle *r, Rectangle s)
{
        if(r->min.y==s.min.y && r->max.y==s.max.y){
                if(r->min.x == s.min.x){
                        r->min.x = s.max.x;
                        assert(r->max.x > r->min.x);
                        return 1;
                }
                if(r->max.x == s.max.x){
                        r->max.x = s.min.x;
                        assert(r->max.x > r->min.x);
                        return 1;
                }
        }
        if(r->min.x==s.min.x && r->max.x==s.max.x){
                if(r->min.y == s.min.y){
                        r->min.y = s.max.y;
                        assert(r->max.y > r->min.y);
                        return 1;
                }
                if(r->max.y == s.max.y){
                        r->max.y = s.min.y;
                        assert(r->max.y > r->min.y);
                        return 1;
                }
        }
        return 0;
}

/*
 * If s is a corner of r, remove s from r, yielding
 * two rectangles r and rr.  R holds the part with
 * smaller coordinates.
 */
static int
rectcornersubr(Rectangle *r, Rectangle s, Rectangle *rr)
{
#       define UPRIGHT(r) Pt((r).max.x, (r).min.y)
#       define LOWLEFT(r) Pt((r).min.x, (r).max.y)

        *rr = *r;

        if(s.min.x == r->min.x){  
                if(s.min.y == r->min.y){  // upper left
                        *rr = Rpt(UPRIGHT(s), r->max);
                        *r = Rpt(LOWLEFT(s), LOWLEFT(*rr));
                        return 1;
                }
                if(s.max.y == r->max.y){ // lower left
                        *rr = Rpt(Pt(s.max.x, r->min.y), r->max);
                        *r = Rpt(r->min, UPRIGHT(s));
                        return 1;
                }
        }
        if(s.max.x == r->max.x){
                if(s.max.y == r->max.y){ // lower right
                        *rr = Rpt(Pt(s.min.x, r->min.y), UPRIGHT(s));
                        *r = Rpt(r->min, LOWLEFT(s));
                        return 1;
                }
                if(s.min.y == r->min.y){ // upper right
                        *rr = Rpt(LOWLEFT(s), r->max);
                        *r = Rpt(r->min, LOWLEFT(*rr));
                        return 1;
                }
        }
        return 0;
}

/*
 * If s is a band cutting r into two pieces, set r to one piece
 * and rr to the other.
 */
static int
recttridesubr(Rectangle *nr, Rectangle s, Rectangle *rr)
{
        *rr = *nr;
        if((nr->min.x == s.min.x && nr->max.x == s.max.x) &&
            (nr->min.y < s.min.y && s.max.y < nr->max.y)){
                nr->max.y = s.min.y;
                rr->min.y = s.max.y;
                return 1;
        }

        if((nr->min.y == s.min.y && nr->max.y == s.max.y) &&
            (nr->min.x < s.min.x && s.max.x < nr->max.x)){
                nr->max.x = s.min.x;
                rr->min.x = s.max.x;
                return 1;
        }
        return 0;
}

void
addtorlist(Rlist *rlist, Rectangle r)
{
        int i, j;
        Rectangle ir, cr, rr;
        Rlist tmp;

        if(r.min.x >= r.max.x || r.min.y >= r.max.y)
                return;

        memset(&tmp, 0, sizeof tmp);
        rappend(&tmp, r);
        
        if(verbose > 5)
                fprint(2, "region union add %R:\n", r);

        combinerect(&rlist->bbox, r); // must do this first
        for(j = 0; j < tmp.nrect; j++){
                r = tmp.rect[j];

                for(i=0; i < rlist->nrect; i++){
                        ir = rlist->rect[i];

                        if(verbose > 5)
                                fprint(2, "checking %R against %R\n", r, ir);
                        if(!rectadjacent(ir, r))
                                continue;

                        /* r is covered by ir? */
                        if(rectinrect(r, ir))
                                break;

                        /* r covers ir? */
                        if(rectinrect(ir, r)){
                                rtrim(rlist, i);
                                i--;
                                continue;
                        }

                        /* aligned and overlapping? */
                        if((ir.min.y == r.min.y && ir.max.y == r.max.y) ||
                        (ir.min.x == r.min.x && ir.max.x == r.max.x)){
                                combinerect(&r, ir);
                                rtrim(rlist, i);
                                i--;
                                continue;
                        }

                        /* not aligned */ 
                        if(verbose > 5)
                                fprint(2, "break up rect %R and %R\n", ir, r);
                        /* 2->2 breakup */
                        cr = ir;
                        if (!rectclip(&cr, r))  /* share only one point */
                                continue;

                        if(rectubr(&r, cr))
                                continue;

                        if(rectubr(&rlist->rect[i], cr))
                                continue;

                        /* 2 -> 3 breakup */
                        /* stride across */
                        if(recttridesubr(&r, cr, &rr)){
                                rappend(&tmp, rr);
                                continue;
                        }

                        /* corner overlap */
                        if(rectcornersubr(&r, cr, &rr)){
                                rappend(&tmp, rr);
                                continue;
                        }
                        abort();
                }
                if(i == rlist->nrect)
                        rappend(rlist, r);
        }
        freerlist(&tmp);
        if(verbose > 5)
                rprint(rlist);
}

void
freerlist(Rlist *r)
{
        free(r->rect);
        tot -= r->maxrect;
        r->nrect = 0;
        r->maxrect = 0;
        r->rect = nil;
}

static void
rprint(Rlist *r)
{
        int i;

        fprint(2, "rlist %p:", r);
        for(i=0; i<r->nrect; i++)
                fprint(2, " %R", r->rect[i]);
        fprint(2, "\n");
}


#ifdef REGION_DEBUG

int verbose = 10;

void main(int argc, char * argv[])
{
        Rectangle r1 = Rect(0, 0, 300, 200);
        Rectangle r2 = Rect(100, 100, 400, 300);
        Rectangle r3 = Rect(200, 100, 500, 300);
        Region reg;

        initdraw(0, 0, "vncviewer");
        region_init(&reg);
        region_union(&reg, r1, r1);
        region_union(&reg, r2, r2);
        region_union(&reg, r3, r3);
}

#endif