Pileus Git - ~andy/gtk/blob - gdk/linux-fb/mispans.c

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