sys/src/cmd/vnc/rlist.c

   1 #include "vnc.h"
   2 #include "vncs.h"
   3
   4 static int tot;
   5 static void rprint(Rlist*);
   6
   7 static void
   8 growrlist(Rlist *rlist, int n)
   9 {
  10         int old;
  11
  12         if(rlist->nrect+n <= rlist->maxrect)
  13                 return;
  14
  15         old = rlist->maxrect;
  16         while(rlist->nrect+n > rlist->maxrect){
  17                 if(rlist->maxrect == 0)
  18                         rlist->maxrect = 16;
  19                 else
  20                         rlist->maxrect *= 2;
  21         }
  22
  23         tot += rlist->maxrect - old;
  24         if(tot > 10000)
  25                 sysfatal("too many rectangles");
  26
  27         rlist->rect = realloc(rlist->rect, rlist->maxrect*sizeof(rlist->rect[0]));
  28         if(rlist->rect == nil)
  29                 sysfatal("realloc failed in growrlist");
  30 }
  31
  32 static void
  33 rappend(Rlist *rl, Rectangle r)
  34 {
  35         growrlist(rl, 1);
  36         rl->rect[rl->nrect++] = r;
  37 }
  38
  39 /* remove rectangle i from the list */
  40 static int
  41 rtrim(Rlist *r, int i)
  42 {
  43         if(i < 0 || i >= r->nrect)
  44                 return 0;
  45         if(i == r->nrect-1){
  46                 r->nrect--;
  47                 return 1;
  48         }
  49         r->rect[i] = r->rect[--r->nrect];
  50         return 1;
  51 }
  52
  53 static int
  54 rectadjacent(Rectangle r, Rectangle s)
  55 {
  56         return r.min.x<=s.max.x && s.min.x<=r.max.x &&
  57                r.min.y<=s.max.y && s.min.y<=r.max.y;
  58 }
  59
  60 /*
  61  * If s shares three edges with r, compute the
  62  * rectangle r - s and return 1.
  63  * Else return 0.
  64  */
  65 static int
  66 rectubr(Rectangle *r, Rectangle s)
  67 {
  68         if(r->min.y==s.min.y && r->max.y==s.max.y){
  69                 if(r->min.x == s.min.x){
  70                         r->min.x = s.max.x;
  71                         assert(r->max.x > r->min.x);
  72                         return 1;
  73                 }
  74                 if(r->max.x == s.max.x){
  75                         r->max.x = s.min.x;
  76                         assert(r->max.x > r->min.x);
  77                         return 1;
  78                 }
  79         }
  80         if(r->min.x==s.min.x && r->max.x==s.max.x){
  81                 if(r->min.y == s.min.y){
  82                         r->min.y = s.max.y;
  83                         assert(r->max.y > r->min.y);
  84                         return 1;
  85                 }
  86                 if(r->max.y == s.max.y){
  87                         r->max.y = s.min.y;
  88                         assert(r->max.y > r->min.y);
  89                         return 1;
  90                 }
  91         }
  92         return 0;
  93 }
  94
  95 /*
  96  * If s is a corner of r, remove s from r, yielding
  97  * two rectangles r and rr.  R holds the part with
  98  * smaller coordinates.
  99  */
 100 static int
 101 rectcornersubr(Rectangle *r, Rectangle s, Rectangle *rr)
 102 {
 103 #       define UPRIGHT(r) Pt((r).max.x, (r).min.y)
 104 #       define LOWLEFT(r) Pt((r).min.x, (r).max.y)
 105
 106         *rr = *r;
 107
 108         if(s.min.x == r->min.x){
 109                 if(s.min.y == r->min.y){  // upper left
 110                         *rr = Rpt(UPRIGHT(s), r->max);
 111                         *r = Rpt(LOWLEFT(s), LOWLEFT(*rr));
 112                         return 1;
 113                 }
 114                 if(s.max.y == r->max.y){ // lower left
 115                         *rr = Rpt(Pt(s.max.x, r->min.y), r->max);
 116                         *r = Rpt(r->min, UPRIGHT(s));
 117                         return 1;
 118                 }
 119         }
 120         if(s.max.x == r->max.x){
 121                 if(s.max.y == r->max.y){ // lower right
 122                         *rr = Rpt(Pt(s.min.x, r->min.y), UPRIGHT(s));
 123                         *r = Rpt(r->min, LOWLEFT(s));
 124                         return 1;
 125                 }
 126                 if(s.min.y == r->min.y){ // upper right
 127                         *rr = Rpt(LOWLEFT(s), r->max);
 128                         *r = Rpt(r->min, LOWLEFT(*rr));
 129                         return 1;
 130                 }
 131         }
 132         return 0;
 133 }
 134
 135 /*
 136  * If s is a band cutting r into two pieces, set r to one piece
 137  * and rr to the other.
 138  */
 139 static int
 140 recttridesubr(Rectangle *nr, Rectangle s, Rectangle *rr)
 141 {
 142         *rr = *nr;
 143         if((nr->min.x == s.min.x && nr->max.x == s.max.x) &&
 144             (nr->min.y < s.min.y && s.max.y < nr->max.y)){
 145                 nr->max.y = s.min.y;
 146                 rr->min.y = s.max.y;
 147                 return 1;
 148         }
 149
 150         if((nr->min.y == s.min.y && nr->max.y == s.max.y) &&
 151             (nr->min.x < s.min.x && s.max.x < nr->max.x)){
 152                 nr->max.x = s.min.x;
 153                 rr->min.x = s.max.x;
 154                 return 1;
 155         }
 156         return 0;
 157 }
 158
 159 void
 160 addtorlist(Rlist *rlist, Rectangle r)
 161 {
 162         int i, j;
 163         Rectangle ir, cr, rr;
 164         Rlist tmp;
 165
 166         if(r.min.x >= r.max.x || r.min.y >= r.max.y)
 167                 return;
 168
 169         memset(&tmp, 0, sizeof tmp);
 170         rappend(&tmp, r);
 171
 172         if(verbose > 5)
 173                 fprint(2, "region union add %R:\n", r);
 174
 175         combinerect(&rlist->bbox, r); // must do this first
 176         for(j = 0; j < tmp.nrect; j++){
 177                 r = tmp.rect[j];
 178
 179                 for(i=0; i < rlist->nrect; i++){
 180                         ir = rlist->rect[i];
 181
 182                         if(verbose > 5)
 183                                 fprint(2, "checking %R against %R\n", r, ir);
 184                         if(!rectadjacent(ir, r))
 185                                 continue;
 186
 187                         /* r is covered by ir? */
 188                         if(rectinrect(r, ir))
 189                                 break;
 190
 191                         /* r covers ir? */
 192                         if(rectinrect(ir, r)){
 193                                 rtrim(rlist, i);
 194                                 i--;
 195                                 continue;
 196                         }
 197
 198                         /* aligned and overlapping? */
 199                         if((ir.min.y == r.min.y && ir.max.y == r.max.y) ||
 200                         (ir.min.x == r.min.x && ir.max.x == r.max.x)){
 201                                 combinerect(&r, ir);
 202                                 rtrim(rlist, i);
 203                                 i--;
 204                                 continue;
 205                         }
 206
 207                         /* not aligned */
 208                         if(verbose > 5)
 209                                 fprint(2, "break up rect %R and %R\n", ir, r);
 210                         /* 2->2 breakup */
 211                         cr = ir;
 212                         if (!rectclip(&cr, r))  /* share only one point */
 213                                 continue;
 214
 215                         if(rectubr(&r, cr))
 216                                 continue;
 217
 218                         if(rectubr(&rlist->rect[i], cr))
 219                                 continue;
 220
 221                         /* 2 -> 3 breakup */
 222                         /* stride across */
 223                         if(recttridesubr(&r, cr, &rr)){
 224                                 rappend(&tmp, rr);
 225                                 continue;
 226                         }
 227
 228                         /* corner overlap */
 229                         if(rectcornersubr(&r, cr, &rr)){
 230                                 rappend(&tmp, rr);
 231                                 continue;
 232                         }
 233                         abort();
 234                 }
 235                 if(i == rlist->nrect)
 236                         rappend(rlist, r);
 237         }
 238         freerlist(&tmp);
 239         if(verbose > 5)
 240                 rprint(rlist);
 241 }
 242
 243 void
 244 freerlist(Rlist *r)
 245 {
 246         free(r->rect);
 247         tot -= r->maxrect;
 248         r->nrect = 0;
 249         r->maxrect = 0;
 250         r->rect = nil;
 251 }
 252
 253 static void
 254 rprint(Rlist *r)
 255 {
 256         int i;
 257
 258         fprint(2, "rlist %p:", r);
 259         for(i=0; i<r->nrect; i++)
 260                 fprint(2, " %R", r->rect[i]);
 261         fprint(2, "\n");
 262 }
 263
 264
 265 #ifdef REGION_DEBUG
 266
 267 int verbose = 10;
 268
 269 void main(int argc, char * argv[])
 270 {
 271         Rectangle r1 = Rect(0, 0, 300, 200);
 272         Rectangle r2 = Rect(100, 100, 400, 300);
 273         Rectangle r3 = Rect(200, 100, 500, 300);
 274         Region reg;
 275
 276         if(initdraw(0, 0, "vncviewer") < 0){
 277                 fprint(2, "%s: initdraw failed: %r\n", argv[0]);
 278                 exits("initdraw");
 279         }
 280         region_init(&reg);
 281         region_union(&reg, r1, r1);
 282         region_union(&reg, r2, r2);
 283         region_union(&reg, r3, r3);
 284 }
 285
 286 #endif