Pileus Git - ~andy/gtk/blob - gdk/x11/gdkpolyreg-generic.c

   1 /* $TOG: PolyReg.c /main/15 1998/02/06 17:47:08 kaleb $ */
   2 /************************************************************************
   3
   4 Copyright 1987, 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 1987 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 /* $XFree86: xc/lib/X11/PolyReg.c,v 1.4 1998/10/03 08:41:21 dawes Exp $ */
  45
  46 #define LARGE_COORDINATE 1000000
  47 #define SMALL_COORDINATE -LARGE_COORDINATE
  48
  49 #include <gdkregion.h>
  50 #include "gdkregion-generic.h"
  51 #include "gdkpoly-generic.h"
  52
  53 /*
  54  *     InsertEdgeInET
  55  *
  56  *     Insert the given edge into the edge table.
  57  *     First we must find the correct bucket in the
  58  *     Edge table, then find the right slot in the
  59  *     bucket.  Finally, we can insert it.
  60  *
  61  */
  62 static void
  63 InsertEdgeInET(ET, ETE, scanline, SLLBlock, iSLLBlock)
  64     EdgeTable *ET;
  65     EdgeTableEntry *ETE;
  66     int scanline;
  67     ScanLineListBlock **SLLBlock;
  68     int *iSLLBlock;
  69 {
  70     EdgeTableEntry *start, *prev;
  71     ScanLineList *pSLL, *pPrevSLL;
  72     ScanLineListBlock *tmpSLLBlock;
  73
  74     /*
  75      * find the right bucket to put the edge into
  76      */
  77     pPrevSLL = &ET->scanlines;
  78     pSLL = pPrevSLL->next;
  79     while (pSLL && (pSLL->scanline < scanline))
  80     {
  81         pPrevSLL = pSLL;
  82         pSLL = pSLL->next;
  83     }
  84
  85     /*
  86      * reassign pSLL (pointer to ScanLineList) if necessary
  87      */
  88     if ((!pSLL) || (pSLL->scanline > scanline))
  89     {
  90         if (*iSLLBlock > SLLSPERBLOCK-1)
  91         {
  92             tmpSLLBlock =
  93                   (ScanLineListBlock *)g_malloc(sizeof(ScanLineListBlock));
  94             (*SLLBlock)->next = tmpSLLBlock;
  95             tmpSLLBlock->next = (ScanLineListBlock *)NULL;
  96             *SLLBlock = tmpSLLBlock;
  97             *iSLLBlock = 0;
  98         }
  99         pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
 100
 101         pSLL->next = pPrevSLL->next;
 102         pSLL->edgelist = (EdgeTableEntry *)NULL;
 103         pPrevSLL->next = pSLL;
 104     }
 105     pSLL->scanline = scanline;
 106
 107     /*
 108      * now insert the edge in the right bucket
 109      */
 110     prev = (EdgeTableEntry *)NULL;
 111     start = pSLL->edgelist;
 112     while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
 113     {
 114         prev = start;
 115         start = start->next;
 116     }
 117     ETE->next = start;
 118
 119     if (prev)
 120         prev->next = ETE;
 121     else
 122         pSLL->edgelist = ETE;
 123 }
 124 \f
 125 /*
 126  *     CreateEdgeTable
 127  *
 128  *     This routine creates the edge table for
 129  *     scan converting polygons.
 130  *     The Edge Table (ET) looks like:
 131  *
 132  *    EdgeTable
 133  *     --------
 134  *    |  ymax  |        ScanLineLists
 135  *    |scanline|-->------------>-------------->...
 136  *     --------   |scanline|   |scanline|
 137  *                |edgelist|   |edgelist|
 138  *                ---------    ---------
 139  *                    |             |
 140  *                    |             |
 141  *                    V             V
 142  *              list of ETEs   list of ETEs
 143  *
 144  *     where ETE is an EdgeTableEntry data structure,
 145  *     and there is one ScanLineList per scanline at
 146  *     which an edge is initially entered.
 147  *
 148  */
 149
 150 static void
 151 CreateETandAET(count, pts, ET, AET, pETEs, pSLLBlock)
 152     int count;
 153     GdkPoint *pts;
 154     EdgeTable *ET;
 155     EdgeTableEntry *AET;
 156     EdgeTableEntry *pETEs;
 157     ScanLineListBlock   *pSLLBlock;
 158 {
 159     GdkPoint *top, *bottom;
 160     GdkPoint *PrevPt, *CurrPt;
 161     int iSLLBlock = 0;
 162     int dy;
 163
 164     if (count < 2)  return;
 165
 166     /*
 167      *  initialize the Active Edge Table
 168      */
 169     AET->next = (EdgeTableEntry *)NULL;
 170     AET->back = (EdgeTableEntry *)NULL;
 171     AET->nextWETE = (EdgeTableEntry *)NULL;
 172     AET->bres.minor_axis = SMALL_COORDINATE;
 173
 174     /*
 175      *  initialize the Edge Table.
 176      */
 177     ET->scanlines.next = (ScanLineList *)NULL;
 178     ET->ymax = SMALL_COORDINATE;
 179     ET->ymin = LARGE_COORDINATE;
 180     pSLLBlock->next = (ScanLineListBlock *)NULL;
 181
 182     PrevPt = &pts[count-1];
 183
 184     /*
 185      *  for each vertex in the array of points.
 186      *  In this loop we are dealing with two vertices at
 187      *  a time -- these make up one edge of the polygon.
 188      */
 189     while (count--)
 190     {
 191         CurrPt = pts++;
 192
 193         /*
 194          *  find out which point is above and which is below.
 195          */
 196         if (PrevPt->y > CurrPt->y)
 197         {
 198             bottom = PrevPt, top = CurrPt;
 199             pETEs->ClockWise = 0;
 200         }
 201         else
 202         {
 203             bottom = CurrPt, top = PrevPt;
 204             pETEs->ClockWise = 1;
 205         }
 206
 207         /*
 208          * don't add horizontal edges to the Edge table.
 209          */
 210         if (bottom->y != top->y)
 211         {
 212             pETEs->ymax = bottom->y-1;  /* -1 so we don't get last scanline */
 213
 214             /*
 215              *  initialize integer edge algorithm
 216              */
 217             dy = bottom->y - top->y;
 218             BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
 219
 220             InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock);
 221
 222             if (PrevPt->y > ET->ymax)
 223                 ET->ymax = PrevPt->y;
 224             if (PrevPt->y < ET->ymin)
 225                 ET->ymin = PrevPt->y;
 226             pETEs++;
 227         }
 228
 229         PrevPt = CurrPt;
 230     }
 231 }
 232 \f
 233 /*
 234  *     loadAET
 235  *
 236  *     This routine moves EdgeTableEntries from the
 237  *     EdgeTable into the Active Edge Table,
 238  *     leaving them sorted by smaller x coordinate.
 239  *
 240  */
 241
 242 static void
 243 loadAET(AET, ETEs)
 244     EdgeTableEntry *AET, *ETEs;
 245 {
 246     EdgeTableEntry *pPrevAET;
 247     EdgeTableEntry *tmp;
 248
 249     pPrevAET = AET;
 250     AET = AET->next;
 251     while (ETEs)
 252     {
 253         while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
 254         {
 255             pPrevAET = AET;
 256             AET = AET->next;
 257         }
 258         tmp = ETEs->next;
 259         ETEs->next = AET;
 260         if (AET)
 261             AET->back = ETEs;
 262         ETEs->back = pPrevAET;
 263         pPrevAET->next = ETEs;
 264         pPrevAET = ETEs;
 265
 266         ETEs = tmp;
 267     }
 268 }
 269 \f
 270 /*
 271  *     computeWAET
 272  *
 273  *     This routine links the AET by the
 274  *     nextWETE (winding EdgeTableEntry) link for
 275  *     use by the winding number rule.  The final
 276  *     Active Edge Table (AET) might look something
 277  *     like:
 278  *
 279  *     AET
 280  *     ----------  ---------   ---------
 281  *     |ymax    |  |ymax    |  |ymax    |
 282  *     | ...    |  |...     |  |...     |
 283  *     |next    |->|next    |->|next    |->...
 284  *     |nextWETE|  |nextWETE|  |nextWETE|
 285  *     ---------   ---------   ^--------
 286  *         |                   |       |
 287  *         V------------------->       V---> ...
 288  *
 289  */
 290 static void
 291 computeWAET(AET)
 292     EdgeTableEntry *AET;
 293 {
 294     EdgeTableEntry *pWETE;
 295     int inside = 1;
 296     int isInside = 0;
 297
 298     AET->nextWETE = (EdgeTableEntry *)NULL;
 299     pWETE = AET;
 300     AET = AET->next;
 301     while (AET)
 302     {
 303         if (AET->ClockWise)
 304             isInside++;
 305         else
 306             isInside--;
 307
 308         if ((!inside && !isInside) ||
 309             ( inside &&  isInside))
 310         {
 311             pWETE->nextWETE = AET;
 312             pWETE = AET;
 313             inside = !inside;
 314         }
 315         AET = AET->next;
 316     }
 317     pWETE->nextWETE = (EdgeTableEntry *)NULL;
 318 }
 319 \f
 320 /*
 321  *     InsertionSort
 322  *
 323  *     Just a simple insertion sort using
 324  *     pointers and back pointers to sort the Active
 325  *     Edge Table.
 326  *
 327  */
 328
 329 static int
 330 InsertionSort(AET)
 331     EdgeTableEntry *AET;
 332 {
 333     EdgeTableEntry *pETEchase;
 334     EdgeTableEntry *pETEinsert;
 335     EdgeTableEntry *pETEchaseBackTMP;
 336     int changed = 0;
 337
 338     AET = AET->next;
 339     while (AET)
 340     {
 341         pETEinsert = AET;
 342         pETEchase = AET;
 343         while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
 344             pETEchase = pETEchase->back;
 345
 346         AET = AET->next;
 347         if (pETEchase != pETEinsert)
 348         {
 349             pETEchaseBackTMP = pETEchase->back;
 350             pETEinsert->back->next = AET;
 351             if (AET)
 352                 AET->back = pETEinsert->back;
 353             pETEinsert->next = pETEchase;
 354             pETEchase->back->next = pETEinsert;
 355             pETEchase->back = pETEinsert;
 356             pETEinsert->back = pETEchaseBackTMP;
 357             changed = 1;
 358         }
 359     }
 360     return(changed);
 361 }
 362 \f
 363 /*
 364  *     Clean up our act.
 365  */
 366 static void
 367 FreeStorage(pSLLBlock)
 368     ScanLineListBlock   *pSLLBlock;
 369 {
 370     ScanLineListBlock   *tmpSLLBlock;
 371
 372     while (pSLLBlock)
 373     {
 374         tmpSLLBlock = pSLLBlock->next;
 375         g_free (pSLLBlock);
 376         pSLLBlock = tmpSLLBlock;
 377     }
 378 }
 379
 380 /*
 381  *     Create an array of rectangles from a list of points.
 382  *     If indeed these things (POINTS, RECTS) are the same,
 383  *     then this proc is still needed, because it allocates
 384  *     storage for the array, which was allocated on the
 385  *     stack by the calling procedure.
 386  *
 387  */
 388 static int PtsToRegion(numFullPtBlocks, iCurPtBlock, FirstPtBlock, reg)
 389     int  numFullPtBlocks, iCurPtBlock;
 390     POINTBLOCK *FirstPtBlock;
 391     GdkRegion *reg;
 392 {
 393     GdkRegionBox *rects;
 394     GdkPoint *pts;
 395     POINTBLOCK *CurPtBlock;
 396     int i;
 397     GdkRegionBox *extents;
 398     int numRects;
 399
 400     extents = &reg->extents;
 401
 402     numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
 403
 404     reg->rects = g_renew (GdkRegionBox, reg->rects, numRects);
 405
 406     reg->size = numRects;
 407     CurPtBlock = FirstPtBlock;
 408     rects = reg->rects - 1;
 409     numRects = 0;
 410     extents->x1 = G_MAXSHORT,  extents->x2 = G_MINSHORT;
 411
 412     for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
 413         /* the loop uses 2 points per iteration */
 414         i = NUMPTSTOBUFFER >> 1;
 415         if (!numFullPtBlocks)
 416             i = iCurPtBlock >> 1;
 417         for (pts = CurPtBlock->pts; i--; pts += 2) {
 418             if (pts->x == pts[1].x)
 419                 continue;
 420             if (numRects && pts->x == rects->x1 && pts->y == rects->y2 &&
 421                 pts[1].x == rects->x2 &&
 422                 (numRects == 1 || rects[-1].y1 != rects->y1) &&
 423                 (i && pts[2].y > pts[1].y)) {
 424                 rects->y2 = pts[1].y + 1;
 425                 continue;
 426             }
 427             numRects++;
 428             rects++;
 429             rects->x1 = pts->x;  rects->y1 = pts->y;
 430             rects->x2 = pts[1].x;  rects->y2 = pts[1].y + 1;
 431             if (rects->x1 < extents->x1)
 432                 extents->x1 = rects->x1;
 433             if (rects->x2 > extents->x2)
 434                 extents->x2 = rects->x2;
 435         }
 436         CurPtBlock = CurPtBlock->next;
 437     }
 438
 439     if (numRects) {
 440         extents->y1 = reg->rects->y1;
 441         extents->y2 = rects->y2;
 442     } else {
 443         extents->x1 = 0;
 444         extents->y1 = 0;
 445         extents->x2 = 0;
 446         extents->y2 = 0;
 447     }
 448     reg->numRects = numRects;
 449
 450     return(TRUE);
 451 }
 452
 453 /*
 454  *     polytoregion
 455  *
 456  *     Scan converts a polygon by returning a run-length
 457  *     encoding of the resultant bitmap -- the run-length
 458  *     encoding is in the form of an array of rectangles.
 459  */
 460 GdkRegion *
 461 gdk_region_polygon(GdkPoint *Pts, gint Count, GdkFillRule rule)
 462 {
 463     GdkRegion *region;
 464     EdgeTableEntry *pAET;   /* Active Edge Table       */
 465     int y;                  /* current scanline        */
 466     int iPts = 0;           /* number of pts in buffer */
 467     EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
 468     ScanLineList *pSLL;     /* current scanLineList    */
 469     GdkPoint *pts;             /* output buffer           */
 470     EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
 471     EdgeTable ET;                    /* header node for ET      */
 472     EdgeTableEntry AET;              /* header node for AET     */
 473     EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
 474     ScanLineListBlock SLLBlock;      /* header for scanlinelist */
 475     int fixWAET = FALSE;
 476     POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
 477     POINTBLOCK *tmpPtBlock;
 478     int numFullPtBlocks = 0;
 479
 480     region = gdk_region_new ();
 481
 482     /* special case a rectangle */
 483     pts = Pts;
 484     if (((Count == 4) ||
 485          ((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&
 486         (((pts[0].y == pts[1].y) &&
 487           (pts[1].x == pts[2].x) &&
 488           (pts[2].y == pts[3].y) &&
 489           (pts[3].x == pts[0].x)) ||
 490          ((pts[0].x == pts[1].x) &&
 491           (pts[1].y == pts[2].y) &&
 492           (pts[2].x == pts[3].x) &&
 493           (pts[3].y == pts[0].y)))) {
 494         region->extents.x1 = MIN(pts[0].x, pts[2].x);
 495         region->extents.y1 = MIN(pts[0].y, pts[2].y);
 496         region->extents.x2 = MAX(pts[0].x, pts[2].x);
 497         region->extents.y2 = MAX(pts[0].y, pts[2].y);
 498         if ((region->extents.x1 != region->extents.x2) &&
 499             (region->extents.y1 != region->extents.y2)) {
 500             region->numRects = 1;
 501             *(region->rects) = region->extents;
 502         }
 503         return(region);
 504     }
 505
 506     pETEs = g_new (EdgeTableEntry, Count);
 507
 508     pts = FirstPtBlock.pts;
 509     CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
 510     pSLL = ET.scanlines.next;
 511     curPtBlock = &FirstPtBlock;
 512
 513     if (rule == GDK_EVEN_ODD_RULE) {
 514         /*
 515          *  for each scanline
 516          */
 517         for (y = ET.ymin; y < ET.ymax; y++) {
 518             /*
 519              *  Add a new edge to the active edge table when we
 520              *  get to the next edge.
 521              */
 522             if (pSLL != NULL && y == pSLL->scanline) {
 523                 loadAET(&AET, pSLL->edgelist);
 524                 pSLL = pSLL->next;
 525             }
 526             pPrevAET = &AET;
 527             pAET = AET.next;
 528
 529             /*
 530              *  for each active edge
 531              */
 532             while (pAET) {
 533                 pts->x = pAET->bres.minor_axis,  pts->y = y;
 534                 pts++, iPts++;
 535
 536                 /*
 537                  *  send out the buffer
 538                  */
 539                 if (iPts == NUMPTSTOBUFFER) {
 540                     tmpPtBlock = (POINTBLOCK *)g_malloc(sizeof(POINTBLOCK));
 541                     curPtBlock->next = tmpPtBlock;
 542                     curPtBlock = tmpPtBlock;
 543                     pts = curPtBlock->pts;
 544                     numFullPtBlocks++;
 545                     iPts = 0;
 546                 }
 547                 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
 548             }
 549             (void) InsertionSort(&AET);
 550         }
 551     }
 552     else {
 553         /*
 554          *  for each scanline
 555          */
 556         for (y = ET.ymin; y < ET.ymax; y++) {
 557             /*
 558              *  Add a new edge to the active edge table when we
 559              *  get to the next edge.
 560              */
 561             if (pSLL != NULL && y == pSLL->scanline) {
 562                 loadAET(&AET, pSLL->edgelist);
 563                 computeWAET(&AET);
 564                 pSLL = pSLL->next;
 565             }
 566             pPrevAET = &AET;
 567             pAET = AET.next;
 568             pWETE = pAET;
 569
 570             /*
 571              *  for each active edge
 572              */
 573             while (pAET) {
 574                 /*
 575                  *  add to the buffer only those edges that
 576                  *  are in the Winding active edge table.
 577                  */
 578                 if (pWETE == pAET) {
 579                     pts->x = pAET->bres.minor_axis,  pts->y = y;
 580                     pts++, iPts++;
 581
 582                     /*
 583                      *  send out the buffer
 584                      */
 585                     if (iPts == NUMPTSTOBUFFER) {
 586                         tmpPtBlock = (POINTBLOCK *)g_malloc(sizeof(POINTBLOCK));
 587                         curPtBlock->next = tmpPtBlock;
 588                         curPtBlock = tmpPtBlock;
 589                         pts = curPtBlock->pts;
 590                         numFullPtBlocks++;    iPts = 0;
 591                     }
 592                     pWETE = pWETE->nextWETE;
 593                 }
 594                 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
 595             }
 596
 597             /*
 598              *  recompute the winding active edge table if
 599              *  we just resorted or have exited an edge.
 600              */
 601             if (InsertionSort(&AET) || fixWAET) {
 602                 computeWAET(&AET);
 603                 fixWAET = FALSE;
 604             }
 605         }
 606     }
 607     FreeStorage(SLLBlock.next);
 608     (void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
 609     for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
 610         tmpPtBlock = curPtBlock->next;
 611         g_free (curPtBlock);
 612         curPtBlock = tmpPtBlock;
 613     }
 614     g_free (pETEs);
 615     return(region);
 616 }