mi/mispans.c

   1 /***********************************************************
   2
   3 Copyright 1989, 1998  The Open Group
   4
   5 Permission to use, copy, modify, distribute, and sell this software and its
   6 documentation for any purpose is hereby granted without fee, provided that
   7 the above copyright notice appear in all copies and that both that
   8 copyright notice and this permission notice appear in supporting
   9 documentation.
  10
  11 The above copyright notice and this permission notice shall be included in
  12 all copies or substantial portions of the Software.
  13
  14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  17 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  18 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  19 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  20
  21 Except as contained in this notice, the name of The Open Group shall not be
  22 used in advertising or otherwise to promote the sale, use or other dealings
  23 in this Software without prior written authorization from The Open Group.
  24
  25 Copyright 1989 by Digital Equipment Corporation, Maynard, Massachusetts.
  26
  27                         All Rights Reserved
  28
  29 Permission to use, copy, modify, and distribute this software and its
  30 documentation for any purpose and without fee is hereby granted,
  31 provided that the above copyright notice appear in all copies and that
  32 both that copyright notice and this permission notice appear in
  33 supporting documentation, and that the name of Digital not be
  34 used in advertising or publicity pertaining to distribution of the
  35 software without specific, written prior permission.
  36
  37 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  38 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  39 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  40 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  41 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  42 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  43 SOFTWARE.
  44
  45 ******************************************************************/
  46
  47 #ifdef HAVE_DIX_CONFIG_H
  48 #include <dix-config.h>
  49 #endif
  50
  51 #include "misc.h"
  52 #include "pixmapstr.h"
  53 #include "gcstruct.h"
  54 #include "mispans.h"
  55
  56 /*
  57
  58 These routines maintain lists of Spans, in order to implement the
  59 ``touch-each-pixel-once'' rules of wide lines and arcs.
  60
  61 Written by Joel McCormack, Summer 1989.
  62
  63 */
  64
  65 void
  66 miInitSpanGroup(SpanGroup * spanGroup)
  67 {
  68     spanGroup->size = 0;
  69     spanGroup->count = 0;
  70     spanGroup->group = NULL;
  71     spanGroup->ymin = MAXSHORT;
  72     spanGroup->ymax = MINSHORT;
  73 }                               /* InitSpanGroup */
  74
  75 #define YMIN(spans) (spans->points[0].y)
  76 #define YMAX(spans)  (spans->points[spans->count-1].y)
  77
  78 static void
  79 miSubtractSpans(SpanGroup * spanGroup, Spans * sub)
  80 {
  81     int i, subCount, spansCount;
  82     int ymin, ymax, xmin, xmax;
  83     Spans *spans;
  84     DDXPointPtr subPt, spansPt;
  85     int *subWid, *spansWid;
  86     int extra;
  87
  88     ymin = YMIN(sub);
  89     ymax = YMAX(sub);
  90     spans = spanGroup->group;
  91     for (i = spanGroup->count; i; i--, spans++) {
  92         if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) {
  93             subCount = sub->count;
  94             subPt = sub->points;
  95             subWid = sub->widths;
  96             spansCount = spans->count;
  97             spansPt = spans->points;
  98             spansWid = spans->widths;
  99             extra = 0;
 100             for (;;) {
 101                 while (spansCount && spansPt->y < subPt->y) {
 102                     spansPt++;
 103                     spansWid++;
 104                     spansCount--;
 105                 }
 106                 if (!spansCount)
 107                     break;
 108                 while (subCount && subPt->y < spansPt->y) {
 109                     subPt++;
 110                     subWid++;
 111                     subCount--;
 112                 }
 113                 if (!subCount)
 114                     break;
 115                 if (subPt->y == spansPt->y) {
 116                     xmin = subPt->x;
 117                     xmax = xmin + *subWid;
 118                     if (xmin >= spansPt->x + *spansWid || spansPt->x >= xmax) {
 119                         ;
 120                     }
 121                     else if (xmin <= spansPt->x) {
 122                         if (xmax >= spansPt->x + *spansWid) {
 123                             memmove(spansPt, spansPt + 1,
 124                                     sizeof *spansPt * (spansCount - 1));
 125                             memmove(spansWid, spansWid + 1,
 126                                     sizeof *spansWid * (spansCount - 1));
 127                             spansPt--;
 128                             spansWid--;
 129                             spans->count--;
 130                             extra++;
 131                         }
 132                         else {
 133                             *spansWid = *spansWid - (xmax - spansPt->x);
 134                             spansPt->x = xmax;
 135                         }
 136                     }
 137                     else {
 138                         if (xmax >= spansPt->x + *spansWid) {
 139                             *spansWid = xmin - spansPt->x;
 140                         }
 141                         else {
 142                             if (!extra) {
 143                                 DDXPointPtr newPt;
 144                                 int *newwid;
 145
 146 #define EXTRA 8
 147                                 newPt =
 148                                     (DDXPointPtr) realloc(spans->points,
 149                                                           (spans->count +
 150                                                            EXTRA) *
 151                                                           sizeof(DDXPointRec));
 152                                 if (!newPt)
 153                                     break;
 154                                 spansPt = newPt + (spansPt - spans->points);
 155                                 spans->points = newPt;
 156                                 newwid =
 157                                     (int *) realloc(spans->widths,
 158                                                     (spans->count +
 159                                                      EXTRA) * sizeof(int));
 160                                 if (!newwid)
 161                                     break;
 162                                 spansWid = newwid + (spansWid - spans->widths);
 163                                 spans->widths = newwid;
 164                                 extra = EXTRA;
 165                             }
 166                             memmove(spansPt + 1, spansPt,
 167                                     sizeof *spansPt * (spansCount));
 168                             memmove(spansWid + 1, spansWid,
 169                                     sizeof *spansWid * (spansCount));
 170                             spans->count++;
 171                             extra--;
 172                             *spansWid = xmin - spansPt->x;
 173                             spansWid++;
 174                             spansPt++;
 175                             *spansWid = *spansWid - (xmax - spansPt->x);
 176                             spansPt->x = xmax;
 177                         }
 178                     }
 179                 }
 180                 spansPt++;
 181                 spansWid++;
 182                 spansCount--;
 183             }
 184         }
 185     }
 186 }
 187
 188 void
 189 miAppendSpans(SpanGroup * spanGroup, SpanGroup * otherGroup, Spans * spans)
 190 {
 191     int ymin, ymax;
 192     int spansCount;
 193
 194     spansCount = spans->count;
 195     if (spansCount > 0) {
 196         if (spanGroup->size == spanGroup->count) {
 197             spanGroup->size = (spanGroup->size + 8) * 2;
 198             spanGroup->group = (Spans *)
 199                 realloc(spanGroup->group, sizeof(Spans) * spanGroup->size);
 200         }
 201
 202         spanGroup->group[spanGroup->count] = *spans;
 203         (spanGroup->count)++;
 204         ymin = spans->points[0].y;
 205         if (ymin < spanGroup->ymin)
 206             spanGroup->ymin = ymin;
 207         ymax = spans->points[spansCount - 1].y;
 208         if (ymax > spanGroup->ymax)
 209             spanGroup->ymax = ymax;
 210         if (otherGroup && otherGroup->ymin < ymax && ymin < otherGroup->ymax) {
 211             miSubtractSpans(otherGroup, spans);
 212         }
 213     }
 214     else {
 215         free(spans->points);
 216         free(spans->widths);
 217     }
 218 }                               /* AppendSpans */
 219
 220 void
 221 miFreeSpanGroup(SpanGroup * spanGroup)
 222 {
 223     free(spanGroup->group);
 224 }
 225
 226 static void
 227 QuickSortSpansX(DDXPointRec points[], int widths[], int numSpans)
 228 {
 229     int x;
 230     int i, j, m;
 231     DDXPointPtr r;
 232
 233 /* Always called with numSpans > 1 */
 234 /* Sorts only by x, as all y should be the same */
 235
 236 #define ExchangeSpans(a, b)                                 \
 237 {                                                           \
 238     DDXPointRec         tpt;                                \
 239     int                 tw;                                 \
 240                                                             \
 241     tpt = points[a]; points[a] = points[b]; points[b] = tpt;    \
 242     tw = widths[a]; widths[a] = widths[b]; widths[b] = tw;  \
 243 }
 244
 245     do {
 246         if (numSpans < 9) {
 247             /* Do insertion sort */
 248             int xprev;
 249
 250             xprev = points[0].x;
 251             i = 1;
 252             do {                /* while i != numSpans */
 253                 x = points[i].x;
 254                 if (xprev > x) {
 255                     /* points[i] is out of order.  Move into proper location. */
 256                     DDXPointRec tpt;
 257                     int tw, k;
 258
 259                     for (j = 0; x >= points[j].x; j++) {
 260                     }
 261                     tpt = points[i];
 262                     tw = widths[i];
 263                     for (k = i; k != j; k--) {
 264                         points[k] = points[k - 1];
 265                         widths[k] = widths[k - 1];
 266                     }
 267                     points[j] = tpt;
 268                     widths[j] = tw;
 269                     x = points[i].x;
 270                 }               /* if out of order */
 271                 xprev = x;
 272                 i++;
 273             } while (i != numSpans);
 274             return;
 275         }
 276
 277         /* Choose partition element, stick in location 0 */
 278         m = numSpans / 2;
 279         if (points[m].x > points[0].x)
 280             ExchangeSpans(m, 0);
 281         if (points[m].x > points[numSpans - 1].x)
 282             ExchangeSpans(m, numSpans - 1);
 283         if (points[m].x > points[0].x)
 284             ExchangeSpans(m, 0);
 285         x = points[0].x;
 286
 287         /* Partition array */
 288         i = 0;
 289         j = numSpans;
 290         do {
 291             r = &(points[i]);
 292             do {
 293                 r++;
 294                 i++;
 295             } while (i != numSpans && r->x < x);
 296             r = &(points[j]);
 297             do {
 298                 r--;
 299                 j--;
 300             } while (x < r->x);
 301             if (i < j)
 302                 ExchangeSpans(i, j);
 303         } while (i < j);
 304
 305         /* Move partition element back to middle */
 306         ExchangeSpans(0, j);
 307
 308         /* Recurse */
 309         if (numSpans - j - 1 > 1)
 310             QuickSortSpansX(&points[j + 1], &widths[j + 1], numSpans - j - 1);
 311         numSpans = j;
 312     } while (numSpans > 1);
 313 }                               /* QuickSortSpans */
 314
 315 static int
 316 UniquifySpansX(Spans * spans, DDXPointRec * newPoints, int *newWidths)
 317 {
 318     int newx1, newx2, oldpt, i, y;
 319     DDXPointRec *oldPoints;
 320     int *oldWidths;
 321     int *startNewWidths;
 322
 323 /* Always called with numSpans > 1 */
 324 /* Uniquify the spans, and stash them into newPoints and newWidths.  Return the
 325    number of unique spans. */
 326
 327     startNewWidths = newWidths;
 328
 329     oldPoints = spans->points;
 330     oldWidths = spans->widths;
 331
 332     y = oldPoints->y;
 333     newx1 = oldPoints->x;
 334     newx2 = newx1 + *oldWidths;
 335
 336     for (i = spans->count - 1; i != 0; i--) {
 337         oldPoints++;
 338         oldWidths++;
 339         oldpt = oldPoints->x;
 340         if (oldpt > newx2) {
 341             /* Write current span, start a new one */
 342             newPoints->x = newx1;
 343             newPoints->y = y;
 344             *newWidths = newx2 - newx1;
 345             newPoints++;
 346             newWidths++;
 347             newx1 = oldpt;
 348             newx2 = oldpt + *oldWidths;
 349         }
 350         else {
 351             /* extend current span, if old extends beyond new */
 352             oldpt = oldpt + *oldWidths;
 353             if (oldpt > newx2)
 354                 newx2 = oldpt;
 355         }
 356     }                           /* for */
 357
 358     /* Write final span */
 359     newPoints->x = newx1;
 360     *newWidths = newx2 - newx1;
 361     newPoints->y = y;
 362
 363     return (newWidths - startNewWidths) + 1;
 364 }                               /* UniquifySpansX */
 365
 366 static void
 367 miDisposeSpanGroup(SpanGroup * spanGroup)
 368 {
 369     int i;
 370     Spans *spans;
 371
 372     for (i = 0; i < spanGroup->count; i++) {
 373         spans = spanGroup->group + i;
 374         free(spans->points);
 375         free(spans->widths);
 376     }
 377 }
 378
 379 void
 380 miFillUniqueSpanGroup(DrawablePtr pDraw, GCPtr pGC, SpanGroup * spanGroup)
 381 {
 382     int i;
 383     Spans *spans;
 384     Spans *yspans;
 385     int *ysizes;
 386     int ymin, ylength;
 387
 388     /* Outgoing spans for one big call to FillSpans */
 389     DDXPointPtr points;
 390     int *widths;
 391     int count;
 392
 393     if (spanGroup->count == 0)
 394         return;
 395
 396     if (spanGroup->count == 1) {
 397         /* Already should be sorted, unique */
 398         spans = spanGroup->group;
 399         (*pGC->ops->FillSpans)
 400             (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE);
 401         free(spans->points);
 402         free(spans->widths);
 403     }
 404     else {
 405         /* Yuck.  Gross.  Radix sort into y buckets, then sort x and uniquify */
 406         /* This seems to be the fastest thing to do.  I've tried sorting on
 407            both x and y at the same time rather than creating into all those
 408            y buckets, but it was somewhat slower. */
 409
 410         ymin = spanGroup->ymin;
 411         ylength = spanGroup->ymax - ymin + 1;
 412
 413         /* Allocate Spans for y buckets */
 414         yspans = malloc(ylength * sizeof(Spans));
 415         ysizes = malloc(ylength * sizeof(int));
 416
 417         if (!yspans || !ysizes) {
 418             free(yspans);
 419             free(ysizes);
 420             miDisposeSpanGroup(spanGroup);
 421             return;
 422         }
 423
 424         for (i = 0; i != ylength; i++) {
 425             ysizes[i] = 0;
 426             yspans[i].count = 0;
 427             yspans[i].points = NULL;
 428             yspans[i].widths = NULL;
 429         }
 430
 431         /* Go through every single span and put it into the correct bucket */
 432         count = 0;
 433         for (i = 0, spans = spanGroup->group;
 434              i != spanGroup->count; i++, spans++) {
 435             int index;
 436             int j;
 437
 438             for (j = 0, points = spans->points, widths = spans->widths;
 439                  j != spans->count; j++, points++, widths++) {
 440                 index = points->y - ymin;
 441                 if (index >= 0 && index < ylength) {
 442                     Spans *newspans = &(yspans[index]);
 443
 444                     if (newspans->count == ysizes[index]) {
 445                         DDXPointPtr newpoints;
 446                         int *newwidths;
 447
 448                         ysizes[index] = (ysizes[index] + 8) * 2;
 449                         newpoints = (DDXPointPtr) realloc(newspans->points,
 450                                                           ysizes[index] *
 451                                                           sizeof(DDXPointRec));
 452                         newwidths =
 453                             (int *) realloc(newspans->widths,
 454                                             ysizes[index] * sizeof(int));
 455                         if (!newpoints || !newwidths) {
 456                             int i;
 457
 458                             for (i = 0; i < ylength; i++) {
 459                                 free(yspans[i].points);
 460                                 free(yspans[i].widths);
 461                             }
 462                             free(yspans);
 463                             free(ysizes);
 464                             free(newpoints);
 465                             free(newwidths);
 466                             miDisposeSpanGroup(spanGroup);
 467                             return;
 468                         }
 469                         newspans->points = newpoints;
 470                         newspans->widths = newwidths;
 471                     }
 472                     newspans->points[newspans->count] = *points;
 473                     newspans->widths[newspans->count] = *widths;
 474                     (newspans->count)++;
 475                 }               /* if y value of span in range */
 476             }                   /* for j through spans */
 477             count += spans->count;
 478             free(spans->points);
 479             spans->points = NULL;
 480             free(spans->widths);
 481             spans->widths = NULL;
 482         }                       /* for i thorough Spans */
 483
 484         /* Now sort by x and uniquify each bucket into the final array */
 485         points = malloc(count * sizeof(DDXPointRec));
 486         widths = malloc(count * sizeof(int));
 487         if (!points || !widths) {
 488             int i;
 489
 490             for (i = 0; i < ylength; i++) {
 491                 free(yspans[i].points);
 492                 free(yspans[i].widths);
 493             }
 494             free(yspans);
 495             free(ysizes);
 496             free(points);
 497             free(widths);
 498             return;
 499         }
 500         count = 0;
 501         for (i = 0; i != ylength; i++) {
 502             int ycount = yspans[i].count;
 503
 504             if (ycount > 0) {
 505                 if (ycount > 1) {
 506                     QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount);
 507                     count += UniquifySpansX
 508                         (&(yspans[i]), &(points[count]), &(widths[count]));
 509                 }
 510                 else {
 511                     points[count] = yspans[i].points[0];
 512                     widths[count] = yspans[i].widths[0];
 513                     count++;
 514                 }
 515                 free(yspans[i].points);
 516                 free(yspans[i].widths);
 517             }
 518         }
 519
 520         (*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE);
 521         free(points);
 522         free(widths);
 523         free(yspans);
 524         free(ysizes);           /* use (DE)xalloc for these? */
 525     }
 526
 527     spanGroup->count = 0;
 528     spanGroup->ymin = MAXSHORT;
 529     spanGroup->ymax = MINSHORT;
 530 }