src/PolyReg.c

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