Pileus Git - ~andy/gtk/blob - gdk/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 "config.h"
  50 #include <gdkregion.h>
  51 #include "gdkregion-generic.h"
  52 #include "gdkpoly-generic.h"
  53 #include "gdkalias.h"
  54
  55 /*
  56  *     InsertEdgeInET
  57  *
  58  *     Insert the given edge into the edge table.
  59  *     First we must find the correct bucket in the
  60  *     Edge table, then find the right slot in the
  61  *     bucket.  Finally, we can insert it.
  62  *
  63  */
  64 static void
  65 InsertEdgeInET (EdgeTable          *ET,
  66                 EdgeTableEntry     *ETE,
  67                 int                 scanline,
  68                 ScanLineListBlock **SLLBlock,
  69                 int                *iSLLBlock)
  70 {
  71     EdgeTableEntry *start, *prev;
  72     ScanLineList *pSLL, *pPrevSLL;
  73     ScanLineListBlock *tmpSLLBlock;
  74
  75     /*
  76      * find the right bucket to put the edge into
  77      */
  78     pPrevSLL = &ET->scanlines;
  79     pSLL = pPrevSLL->next;
  80     while (pSLL && (pSLL->scanline < scanline))
  81     {
  82         pPrevSLL = pSLL;
  83         pSLL = pSLL->next;
  84     }
  85
  86     /*
  87      * reassign pSLL (pointer to ScanLineList) if necessary
  88      */
  89     if ((!pSLL) || (pSLL->scanline > scanline))
  90     {
  91         if (*iSLLBlock > SLLSPERBLOCK-1)
  92         {
  93             tmpSLLBlock =
  94                   (ScanLineListBlock *)g_malloc(sizeof(ScanLineListBlock));
  95             (*SLLBlock)->next = tmpSLLBlock;
  96             tmpSLLBlock->next = (ScanLineListBlock *)NULL;
  97             *SLLBlock = tmpSLLBlock;
  98             *iSLLBlock = 0;
  99         }
 100         pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
 101
 102         pSLL->next = pPrevSLL->next;
 103         pSLL->edgelist = (EdgeTableEntry *)NULL;
 104         pPrevSLL->next = pSLL;
 105     }
 106     pSLL->scanline = scanline;
 107
 108     /*
 109      * now insert the edge in the right bucket
 110      */
 111     prev = (EdgeTableEntry *)NULL;
 112     start = pSLL->edgelist;
 113     while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
 114     {
 115         prev = start;
 116         start = start->next;
 117     }
 118     ETE->next = start;
 119
 120     if (prev)
 121         prev->next = ETE;
 122     else
 123         pSLL->edgelist = ETE;
 124 }
 125 \f
 126 /*
 127  *     CreateEdgeTable
 128  *
 129  *     This routine creates the edge table for
 130  *     scan converting polygons.
 131  *     The Edge Table (ET) looks like:
 132  *
 133  *    EdgeTable
 134  *     --------
 135  *    |  ymax  |        ScanLineLists
 136  *    |scanline|-->------------>-------------->...
 137  *     --------   |scanline|   |scanline|
 138  *                |edgelist|   |edgelist|
 139  *                ---------    ---------
 140  *                    |             |
 141  *                    |             |
 142  *                    V             V
 143  *              list of ETEs   list of ETEs
 144  *
 145  *     where ETE is an EdgeTableEntry data structure,
 146  *     and there is one ScanLineList per scanline at
 147  *     which an edge is initially entered.
 148  *
 149  */
 150
 151 static void
 152 CreateETandAET (int                count,
 153                 const GdkPoint    *pts,
 154                 EdgeTable         *ET,
 155                 EdgeTableEntry    *AET,
 156                 EdgeTableEntry    *pETEs,
 157                 ScanLineListBlock *pSLLBlock)
 158 {
 159     const GdkPoint *top, *bottom;
 160     const 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(EdgeTableEntry *AET,
 244         EdgeTableEntry *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 (EdgeTableEntry *AET)
 292 {
 293     EdgeTableEntry *pWETE;
 294     int inside = 1;
 295     int isInside = 0;
 296
 297     AET->nextWETE = (EdgeTableEntry *)NULL;
 298     pWETE = AET;
 299     AET = AET->next;
 300     while (AET)
 301     {
 302         if (AET->ClockWise)
 303             isInside++;
 304         else
 305             isInside--;
 306
 307         if ((!inside && !isInside) ||
 308             ( inside &&  isInside))
 309         {
 310             pWETE->nextWETE = AET;
 311             pWETE = AET;
 312             inside = !inside;
 313         }
 314         AET = AET->next;
 315     }
 316     pWETE->nextWETE = (EdgeTableEntry *)NULL;
 317 }
 318 \f
 319 /*
 320  *     InsertionSort
 321  *
 322  *     Just a simple insertion sort using
 323  *     pointers and back pointers to sort the Active
 324  *     Edge Table.
 325  *
 326  */
 327
 328 static int
 329 InsertionSort (EdgeTableEntry *AET)
 330 {
 331     EdgeTableEntry *pETEchase;
 332     EdgeTableEntry *pETEinsert;
 333     EdgeTableEntry *pETEchaseBackTMP;
 334     int changed = 0;
 335
 336     AET = AET->next;
 337     while (AET)
 338     {
 339         pETEinsert = AET;
 340         pETEchase = AET;
 341         while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
 342             pETEchase = pETEchase->back;
 343
 344         AET = AET->next;
 345         if (pETEchase != pETEinsert)
 346         {
 347             pETEchaseBackTMP = pETEchase->back;
 348             pETEinsert->back->next = AET;
 349             if (AET)
 350                 AET->back = pETEinsert->back;
 351             pETEinsert->next = pETEchase;
 352             pETEchase->back->next = pETEinsert;
 353             pETEchase->back = pETEinsert;
 354             pETEinsert->back = pETEchaseBackTMP;
 355             changed = 1;
 356         }
 357     }
 358     return(changed);
 359 }
 360 \f
 361 /*
 362  *     Clean up our act.
 363  */
 364 static void
 365 FreeStorage (ScanLineListBlock *pSLLBlock)
 366 {
 367     ScanLineListBlock   *tmpSLLBlock;
 368
 369     while (pSLLBlock)
 370     {
 371         tmpSLLBlock = pSLLBlock->next;
 372         g_free (pSLLBlock);
 373         pSLLBlock = tmpSLLBlock;
 374     }
 375 }
 376
 377 /*
 378  *     Create an array of rectangles from a list of points.
 379  *     If indeed these things (POINTS, RECTS) are the same,
 380  *     then this proc is still needed, because it allocates
 381  *     storage for the array, which was allocated on the
 382  *     stack by the calling procedure.
 383  *
 384  */
 385 static int
 386 PtsToRegion (int         numFullPtBlocks,
 387              int         iCurPtBlock,
 388              POINTBLOCK *FirstPtBlock,
 389              GdkRegion  *reg)
 390 {
 391     GdkRegionBox *rects;
 392     GdkPoint *pts;
 393     POINTBLOCK *CurPtBlock;
 394     int i;
 395     GdkRegionBox *extents;
 396     int numRects;
 397
 398     extents = &reg->extents;
 399
 400     numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
 401
 402     GROWREGION(reg, numRects);
 403
 404     CurPtBlock = FirstPtBlock;
 405     rects = reg->rects - 1;
 406     numRects = 0;
 407     extents->x1 = G_MAXSHORT,  extents->x2 = G_MINSHORT;
 408
 409     for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
 410         /* the loop uses 2 points per iteration */
 411         i = NUMPTSTOBUFFER >> 1;
 412         if (!numFullPtBlocks)
 413             i = iCurPtBlock >> 1;
 414         for (pts = CurPtBlock->pts; i--; pts += 2) {
 415             if (pts->x == pts[1].x)
 416                 continue;
 417             if (numRects && pts->x == rects->x1 && pts->y == rects->y2 &&
 418                 pts[1].x == rects->x2 &&
 419                 (numRects == 1 || rects[-1].y1 != rects->y1) &&
 420                 (i && pts[2].y > pts[1].y)) {
 421                 rects->y2 = pts[1].y + 1;
 422                 continue;
 423             }
 424             numRects++;
 425             rects++;
 426             rects->x1 = pts->x;  rects->y1 = pts->y;
 427             rects->x2 = pts[1].x;  rects->y2 = pts[1].y + 1;
 428             if (rects->x1 < extents->x1)
 429                 extents->x1 = rects->x1;
 430             if (rects->x2 > extents->x2)
 431                 extents->x2 = rects->x2;
 432         }
 433         CurPtBlock = CurPtBlock->next;
 434     }
 435
 436     if (numRects) {
 437         extents->y1 = reg->rects->y1;
 438         extents->y2 = rects->y2;
 439     } else {
 440         extents->x1 = 0;
 441         extents->y1 = 0;
 442         extents->x2 = 0;
 443         extents->y2 = 0;
 444     }
 445     reg->numRects = numRects;
 446
 447     return(TRUE);
 448 }
 449
 450 /**
 451  * gdk_region_polygon:
 452  * @points: an array of #GdkPoint structs
 453  * @n_points: the number of elements in the @points array
 454  * @fill_rule: specifies which pixels are included in the region when the
 455  *     polygon overlaps itself.
 456  *
 457  * Creates a new #GdkRegion using the polygon defined by a
 458  * number of points.
 459  *
 460  * Returns: a new #GdkRegion based on the given polygon
 461  */
 462 GdkRegion *
 463 gdk_region_polygon (const GdkPoint *points,
 464                     gint            n_points,
 465                     GdkFillRule     fill_rule)
 466 {
 467     GdkRegion *region;
 468     EdgeTableEntry *pAET;   /* Active Edge Table       */
 469     int y;                  /* current scanline        */
 470     int iPts = 0;           /* number of pts in buffer */
 471     EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
 472     ScanLineList *pSLL;     /* current scanLineList    */
 473     GdkPoint *pts;          /* output buffer           */
 474     EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
 475     EdgeTable ET;                    /* header node for ET      */
 476     EdgeTableEntry AET;              /* header node for AET     */
 477     EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
 478     ScanLineListBlock SLLBlock;      /* header for scanlinelist */
 479     int fixWAET = FALSE;
 480     POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
 481     POINTBLOCK *tmpPtBlock;
 482     int numFullPtBlocks = 0;
 483
 484     region = gdk_region_new ();
 485
 486     /* special case a rectangle */
 487     if (((n_points == 4) ||
 488          ((n_points == 5) && (points[4].x == points[0].x) && (points[4].y == points[0].y))) &&
 489         (((points[0].y == points[1].y) &&
 490           (points[1].x == points[2].x) &&
 491           (points[2].y == points[3].y) &&
 492           (points[3].x == points[0].x)) ||
 493          ((points[0].x == points[1].x) &&
 494           (points[1].y == points[2].y) &&
 495           (points[2].x == points[3].x) &&
 496           (points[3].y == points[0].y)))) {
 497         region->extents.x1 = MIN(points[0].x, points[2].x);
 498         region->extents.y1 = MIN(points[0].y, points[2].y);
 499         region->extents.x2 = MAX(points[0].x, points[2].x);
 500         region->extents.y2 = MAX(points[0].y, points[2].y);
 501         if ((region->extents.x1 != region->extents.x2) &&
 502             (region->extents.y1 != region->extents.y2)) {
 503             region->numRects = 1;
 504             *(region->rects) = region->extents;
 505         }
 506         return(region);
 507     }
 508
 509     pETEs = g_new (EdgeTableEntry, n_points);
 510
 511     pts = FirstPtBlock.pts;
 512     CreateETandAET(n_points, points, &ET, &AET, pETEs, &SLLBlock);
 513     pSLL = ET.scanlines.next;
 514     curPtBlock = &FirstPtBlock;
 515
 516     if (fill_rule == GDK_EVEN_ODD_RULE) {
 517         /*
 518          *  for each scanline
 519          */
 520         for (y = ET.ymin; y < ET.ymax; y++) {
 521             /*
 522              *  Add a new edge to the active edge table when we
 523              *  get to the next edge.
 524              */
 525             if (pSLL != NULL && y == pSLL->scanline) {
 526                 loadAET(&AET, pSLL->edgelist);
 527                 pSLL = pSLL->next;
 528             }
 529             pPrevAET = &AET;
 530             pAET = AET.next;
 531
 532             /*
 533              *  for each active edge
 534              */
 535             while (pAET) {
 536                 pts->x = pAET->bres.minor_axis,  pts->y = y;
 537                 pts++, iPts++;
 538
 539                 /*
 540                  *  send out the buffer
 541                  */
 542                 if (iPts == NUMPTSTOBUFFER) {
 543                     tmpPtBlock = (POINTBLOCK *)g_malloc(sizeof(POINTBLOCK));
 544                     tmpPtBlock->next = NULL;
 545                     curPtBlock->next = tmpPtBlock;
 546                     curPtBlock = tmpPtBlock;
 547                     pts = curPtBlock->pts;
 548                     numFullPtBlocks++;
 549                     iPts = 0;
 550                 }
 551                 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
 552             }
 553             (void) InsertionSort(&AET);
 554         }
 555     }
 556     else {
 557         /*
 558          *  for each scanline
 559          */
 560         for (y = ET.ymin; y < ET.ymax; y++) {
 561             /*
 562              *  Add a new edge to the active edge table when we
 563              *  get to the next edge.
 564              */
 565             if (pSLL != NULL && y == pSLL->scanline) {
 566                 loadAET(&AET, pSLL->edgelist);
 567                 computeWAET(&AET);
 568                 pSLL = pSLL->next;
 569             }
 570             pPrevAET = &AET;
 571             pAET = AET.next;
 572             pWETE = pAET;
 573
 574             /*
 575              *  for each active edge
 576              */
 577             while (pAET) {
 578                 /*
 579                  *  add to the buffer only those edges that
 580                  *  are in the Winding active edge table.
 581                  */
 582                 if (pWETE == pAET) {
 583                     pts->x = pAET->bres.minor_axis,  pts->y = y;
 584                     pts++, iPts++;
 585
 586                     /*
 587                      *  send out the buffer
 588                      */
 589                     if (iPts == NUMPTSTOBUFFER) {
 590                         tmpPtBlock = (POINTBLOCK *)g_malloc(sizeof(POINTBLOCK));
 591                         tmpPtBlock->next = NULL;
 592                         curPtBlock->next = tmpPtBlock;
 593                         curPtBlock = tmpPtBlock;
 594                         pts = curPtBlock->pts;
 595                         numFullPtBlocks++;    iPts = 0;
 596                     }
 597                     pWETE = pWETE->nextWETE;
 598                 }
 599                 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
 600             }
 601
 602             /*
 603              *  recompute the winding active edge table if
 604              *  we just resorted or have exited an edge.
 605              */
 606             if (InsertionSort(&AET) || fixWAET) {
 607                 computeWAET(&AET);
 608                 fixWAET = FALSE;
 609             }
 610         }
 611     }
 612     FreeStorage(SLLBlock.next);
 613     (void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
 614     for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
 615         tmpPtBlock = curPtBlock->next;
 616         g_free (curPtBlock);
 617         curPtBlock = tmpPtBlock;
 618     }
 619     g_free (pETEs);
 620     return(region);
 621 }
 622
 623 #define __GDK_POLYREG_GENERIC_C__
 624 #include "gdkaliasdef.c"