win32ss/gdi/ntgdi/polyfill.c

   1 /*
   2  * COPYRIGHT:         See COPYING in the top level directory
   3  * PROJECT:           ReactOS Win32k subsystem
   4  * PURPOSE:           Various Polygon Filling routines for Polygon()
   5  * FILE:              win32ss/gdi/ntgdi/polyfill.c
   6  * PROGRAMER:         Mark Tempel
   7  */
   8
   9 #include <win32k.h>
  10
  11 #define NDEBUG
  12 #include <debug.h>
  13
  14 #define FILL_EDGE_ALLOC_TAG 0x45465044
  15
  16 /*
  17 ** This struct is used for book keeping during polygon filling routines.
  18 */
  19 typedef struct _tagFILL_EDGE
  20 {
  21     /* Basic line information */
  22     int FromX;
  23     int FromY;
  24     int ToX;
  25     int ToY;
  26     int dx;
  27     int dy;
  28     int absdx, absdy;
  29     int x, y;
  30     int xmajor;
  31
  32     /* Active Edge List information */
  33     int XIntercept[2];
  34     int Error;
  35     int ErrorMax;
  36     int XDirection, YDirection;
  37
  38     /* The next edge in the active Edge List */
  39     struct _tagFILL_EDGE * pNext;
  40 } FILL_EDGE;
  41
  42 typedef struct _FILL_EDGE_LIST
  43 {
  44     int Count;
  45     FILL_EDGE** Edges;
  46 } FILL_EDGE_LIST;
  47
  48 #if 0
  49 static
  50 void
  51 DEBUG_PRINT_ACTIVE_EDGELIST ( FILL_EDGE* list )
  52 {
  53     FILL_EDGE* pThis = list;
  54     if (0 == list)
  55     {
  56         DPRINT1("List is NULL\n");
  57         return;
  58     }
  59
  60     while(0 != pThis)
  61     {
  62         //DPRINT1("EDGE: (%d, %d) to (%d, %d)\n", pThis->FromX, pThis->FromY, pThis->ToX, pThis->ToY);
  63         DPRINT1("EDGE: [%d,%d]\n", pThis->XIntercept[0], pThis->XIntercept[1] );
  64         pThis = pThis->pNext;
  65     }
  66 }
  67 #else
  68 #define DEBUG_PRINT_ACTIVE_EDGELIST(x)
  69 #endif
  70
  71 /*
  72 **  Hide memory clean up.
  73 */
  74 static
  75 void
  76 FASTCALL
  77 POLYGONFILL_DestroyEdgeList(FILL_EDGE_LIST* list)
  78 {
  79     int i;
  80
  81     if (list)
  82     {
  83         if (list->Edges)
  84         {
  85             for (i = 0; i < list->Count; i++)
  86             {
  87                 _PRAGMA_WARNING_SUPPRESS(__WARNING_USING_UNINIT_VAR)
  88                 if (list->Edges[i])
  89                     EngFreeMem(list->Edges[i]);
  90             }
  91
  92             EngFreeMem(list->Edges);
  93         }
  94
  95         EngFreeMem(list);
  96     }
  97 }
  98
  99 /*
 100 ** This makes and initializes an Edge struct for a line between two points.
 101 */
 102 static
 103 FILL_EDGE*
 104 FASTCALL
 105 POLYGONFILL_MakeEdge(POINT From, POINT To)
 106 {
 107     FILL_EDGE* rc = (FILL_EDGE*)EngAllocMem(FL_ZERO_MEMORY, sizeof(FILL_EDGE), FILL_EDGE_ALLOC_TAG);
 108
 109     if (0 == rc)
 110         return NULL;
 111
 112     //DPRINT1("Making Edge: (%d, %d) to (%d, %d)\n", From.x, From.y, To.x, To.y);
 113     // Now fill the struct.
 114     if ( To.y < From.y )
 115     {
 116         rc->FromX = To.x;
 117         rc->FromY = To.y;
 118         rc->ToX = From.x;
 119         rc->ToY = From.y;
 120         rc->YDirection = -1;
 121
 122         // Lines that go up get walked backwards, so need to be offset
 123         // by -1 in order to make the walk identically on a pixel-level
 124         rc->Error = -1;
 125     }
 126     else
 127     {
 128         rc->FromX = From.x;
 129         rc->FromY = From.y;
 130         rc->ToX = To.x;
 131         rc->ToY = To.y;
 132         rc->YDirection = 1;
 133
 134         rc->Error = 0;
 135     }
 136
 137     rc->x = rc->FromX;
 138     rc->y = rc->FromY;
 139     rc->dx   = rc->ToX - rc->FromX;
 140     rc->dy   = rc->ToY - rc->FromY;
 141     rc->absdx = abs(rc->dx);
 142     rc->absdy = abs(rc->dy);
 143
 144     rc->xmajor = rc->absdx > rc->absdy;
 145
 146     rc->ErrorMax = max(rc->absdx,rc->absdy);
 147
 148     rc->Error += rc->ErrorMax / 2;
 149
 150     rc->XDirection = (rc->dx < 0)?(-1):(1);
 151
 152     rc->pNext = 0;
 153
 154     //DPRINT("MakeEdge (%i,%i)->(%i,%i) d=(%i,%i) dir=(%i,%i) err=%i max=%i\n",
 155     //  From.x, From.y, To.x, To.y, rc->dx, rc->dy, rc->XDirection, rc->YDirection, rc->Error, rc->ErrorMax );
 156
 157     return rc;
 158 }
 159 /*
 160 ** My Edge comparison routine.
 161 ** This is for scan converting polygon fill.
 162 ** First sort by MinY, then Minx, then slope.
 163 **
 164 ** This comparison will help us determine which
 165 ** lines will become active first when scanning from
 166 ** top (min y) to bottom (max y).
 167 **
 168 ** Return Value Meaning
 169 ** Negative integer element1 < element2
 170 ** Zero element1 = element2
 171 ** Positive integer element1 > element2
 172 */
 173 static
 174 INT
 175 FASTCALL
 176 FILL_EDGE_Compare(FILL_EDGE* Edge1, FILL_EDGE* Edge2)
 177 {
 178     int e1 = Edge1->XIntercept[0] + Edge1->XIntercept[1];
 179     int e2 = Edge2->XIntercept[0] + Edge2->XIntercept[1];
 180
 181     return e1 - e2;
 182 }
 183
 184
 185 /*
 186 ** Insert an edge into a list keeping the list in order.
 187 */
 188 static
 189 void
 190 FASTCALL
 191 POLYGONFILL_ActiveListInsert(FILL_EDGE** activehead, FILL_EDGE* NewEdge )
 192 {
 193     FILL_EDGE *pPrev, *pThis;
 194     //DPRINT1("In POLYGONFILL_ActiveListInsert()\n");
 195     ASSERT(activehead && NewEdge);
 196
 197     if (!*activehead)
 198     {
 199         NewEdge->pNext = NULL;
 200         *activehead = NewEdge;
 201         return;
 202     }
 203     /*
 204     ** First lets check to see if we have a new smallest value.
 205     */
 206     if (FILL_EDGE_Compare(NewEdge, *activehead) <= 0)
 207     {
 208         NewEdge->pNext = *activehead;
 209         *activehead = NewEdge;
 210         return;
 211     }
 212
 213     /*
 214     ** Ok, now scan to the next spot to put this item.
 215     */
 216     pThis = *activehead;
 217     pPrev = NULL;
 218     while ( pThis && FILL_EDGE_Compare(pThis, NewEdge) < 0 )
 219     {
 220         pPrev = pThis;
 221         pThis = pThis->pNext;
 222     }
 223
 224     ASSERT(pPrev);
 225     NewEdge->pNext = pPrev->pNext;
 226     pPrev->pNext = NewEdge;
 227     //DEBUG_PRINT_ACTIVE_EDGELIST(*activehead);
 228 }
 229
 230 /*
 231 ** Create a list of edges for a list of points.
 232 */
 233 static
 234 FILL_EDGE_LIST*
 235 FASTCALL
 236 POLYGONFILL_MakeEdgeList(PPOINT Points, int Count)
 237 {
 238     int CurPt = 0;
 239     FILL_EDGE_LIST* list = 0;
 240     FILL_EDGE* e = 0;
 241
 242     if (0 == Points || 2 > Count)
 243         return 0;
 244
 245     list = (FILL_EDGE_LIST*)EngAllocMem(FL_ZERO_MEMORY, sizeof(FILL_EDGE_LIST), FILL_EDGE_ALLOC_TAG);
 246     if ( 0 == list )
 247         goto fail;
 248     list->Count = 0;
 249     list->Edges = (FILL_EDGE**)EngAllocMem(FL_ZERO_MEMORY, Count*sizeof(FILL_EDGE*), FILL_EDGE_ALLOC_TAG);
 250     if ( !list->Edges )
 251         goto fail;
 252
 253     memset(list->Edges, 0, Count * sizeof(FILL_EDGE*));
 254
 255     for (CurPt = 1; CurPt < Count; ++CurPt)
 256     {
 257         e = POLYGONFILL_MakeEdge ( Points[CurPt-1], Points[CurPt] );
 258         if (!e)
 259             goto fail;
 260
 261         // If a straight horizontal line - who cares?
 262         if (!e->absdy)
 263             EngFreeMem(e);
 264         else
 265             list->Edges[list->Count++] = e;
 266     }
 267     e = POLYGONFILL_MakeEdge ( Points[CurPt-1], Points[0] );
 268     if ( !e )
 269         goto fail;
 270
 271     if (!e->absdy)
 272         EngFreeMem(e);
 273     else
 274         list->Edges[list->Count++] = e;
 275     return list;
 276
 277 fail:
 278
 279     DPRINT1("Out Of MEMORY!!\n");
 280     POLYGONFILL_DestroyEdgeList ( list );
 281     return 0;
 282 }
 283
 284
 285 /*
 286 ** This slow routine uses the data stored in the edge list to
 287 ** calculate the x intercepts for each line in the edge list
 288 ** for scanline Scanline.
 289 **TODO: Get rid of this floating point arithmetic
 290 */
 291 static
 292 void
 293 FASTCALL
 294 POLYGONFILL_UpdateScanline(FILL_EDGE* pEdge, int Scanline)
 295 {
 296     if (0 == pEdge->dy)
 297         return;
 298
 299     ASSERT(pEdge->FromY <= Scanline && pEdge->ToY > Scanline);
 300
 301     if (pEdge->xmajor)
 302     {
 303         int steps;
 304
 305         ASSERT(pEdge->y == Scanline);
 306
 307         // Now shoot to end of scanline collision
 308         steps = (pEdge->ErrorMax-pEdge->Error-1)/pEdge->absdy;
 309         if (steps)
 310         {
 311             // Record first collision with scanline
 312             int x1 = pEdge->x;
 313             pEdge->x += steps * pEdge->XDirection;
 314             pEdge->Error += steps * pEdge->absdy;
 315             ASSERT ( pEdge->Error < pEdge->ErrorMax );
 316             pEdge->XIntercept[0] = min(x1,pEdge->x);
 317             pEdge->XIntercept[1] = max(x1,pEdge->x);
 318         }
 319         else
 320         {
 321             pEdge->XIntercept[0] = pEdge->x;
 322             pEdge->XIntercept[1] = pEdge->x;
 323         }
 324
 325         // We should require exactly 1 step to step onto next scanline...
 326         ASSERT((pEdge->ErrorMax-pEdge->Error-1) / pEdge->absdy == 0);
 327         pEdge->x += pEdge->XDirection;
 328         pEdge->Error += pEdge->absdy;
 329         ASSERT(pEdge->Error >= pEdge->ErrorMax);
 330
 331         // Now step onto next scanline...
 332         pEdge->Error -= pEdge->absdx;
 333         pEdge->y++;
 334     }
 335     else // Then this is a y-major line
 336     {
 337         pEdge->XIntercept[0] = pEdge->x;
 338         pEdge->XIntercept[1] = pEdge->x;
 339
 340         pEdge->Error += pEdge->absdx;
 341         pEdge->y++;
 342
 343         if (pEdge->Error >= pEdge->ErrorMax)
 344         {
 345             pEdge->Error -= pEdge->ErrorMax;
 346             pEdge->x += pEdge->XDirection;
 347             ASSERT ( pEdge->Error < pEdge->ErrorMax );
 348         }
 349     }
 350
 351     //DPRINT("Line (%d, %d) to (%d, %d) intersects scanline %d at (%d,%d)\n",
 352     //        pEdge->FromX, pEdge->FromY, pEdge->ToX, pEdge->ToY, Scanline, pEdge->XIntercept[0], pEdge->XIntercept[1] );
 353 }
 354
 355 /*
 356  * This method updates the Active edge collection for the scanline Scanline.
 357  */
 358 static
 359 void
 360 APIENTRY
 361 POLYGONFILL_BuildActiveList(
 362     int Scanline,
 363     FILL_EDGE_LIST* list,
 364     FILL_EDGE** ActiveHead)
 365 {
 366     int i;
 367
 368     ASSERT(list && ActiveHead);
 369     *ActiveHead = 0;
 370     for (i = 0; i < list->Count; i++)
 371     {
 372         FILL_EDGE* pEdge = list->Edges[i];
 373         ASSERT(pEdge);
 374         if (pEdge->FromY <= Scanline && pEdge->ToY > Scanline)
 375         {
 376             POLYGONFILL_UpdateScanline(pEdge, Scanline);
 377             POLYGONFILL_ActiveListInsert(ActiveHead, pEdge);
 378         }
 379     }
 380 }
 381
 382 /*
 383 ** This method fills the portion of the polygon that intersects with the scanline
 384 ** Scanline.
 385 */
 386 static
 387 void
 388 APIENTRY
 389 POLYGONFILL_FillScanLineAlternate(
 390     PDC dc,
 391     int ScanLine,
 392     FILL_EDGE* ActiveHead,
 393     SURFACE *psurf,
 394     BRUSHOBJ *BrushObj,
 395     MIX RopMode )
 396 {
 397     FILL_EDGE *pLeft, *pRight;
 398
 399     if (!ActiveHead)
 400         return;
 401
 402     pLeft = ActiveHead;
 403     pRight = pLeft->pNext;
 404     ASSERT(pRight);
 405
 406     while (NULL != pRight)
 407     {
 408         int x1 = pLeft->XIntercept[0];
 409         int x2 = pRight->XIntercept[1];
 410         if (x2 > x1)
 411         {
 412             RECTL BoundRect;
 413             BoundRect.top = ScanLine;
 414             BoundRect.bottom = ScanLine + 1;
 415             BoundRect.left = x1;
 416             BoundRect.right = x2;
 417
 418             //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
 419             IntEngLineTo(&psurf->SurfObj,
 420                          (CLIPOBJ *)&dc->co,
 421                          BrushObj,
 422                          x1,
 423                          ScanLine,
 424                          x2,
 425                          ScanLine,
 426                          &BoundRect,  // Bounding rectangle
 427                          RopMode);    // MIX
 428         }
 429         pLeft = pRight->pNext;
 430         pRight = pLeft ? pLeft->pNext : NULL;
 431     }
 432 }
 433
 434 static
 435 void
 436 APIENTRY
 437 POLYGONFILL_FillScanLineWinding(
 438     PDC dc,
 439     int ScanLine,
 440     FILL_EDGE* ActiveHead,
 441     SURFACE *psurf,
 442     BRUSHOBJ *BrushObj,
 443     MIX RopMode )
 444 {
 445     FILL_EDGE *pLeft, *pRight;
 446     int x1, x2, winding = 0;
 447     RECTL BoundRect;
 448
 449     if (!ActiveHead)
 450         return;
 451
 452     BoundRect.top = ScanLine;
 453     BoundRect.bottom = ScanLine + 1;
 454
 455     pLeft = ActiveHead;
 456     winding = pLeft->YDirection;
 457     pRight = pLeft->pNext;
 458     ASSERT(pRight);
 459
 460     // Setup first line...
 461     x1 = pLeft->XIntercept[0];
 462     x2 = pRight->XIntercept[1];
 463
 464     pLeft = pRight;
 465     pRight = pLeft->pNext;
 466     winding += pLeft->YDirection;
 467
 468     while ( NULL != pRight )
 469     {
 470         int newx1 = pLeft->XIntercept[0];
 471         int newx2 = pRight->XIntercept[1];
 472         if ( winding )
 473         {
 474             // Check and see if this new line touches the previous...
 475             if ((newx1 >= x1 && newx1 <= x2) ||
 476                 (newx2 >= x1 && newx2 <= x2) ||
 477                 (x1 >= newx1 && x1 <= newx2) ||
 478                 (x2 >= newx2 && x2 <= newx2))
 479             {
 480                 // Yup, just tack it on to our existing line
 481                 x1 = min(x1,newx1);
 482                 x2 = max(x2,newx2);
 483             }
 484             else
 485             {
 486                 // Nope - render the old line..
 487                 BoundRect.left = x1;
 488                 BoundRect.right = x2;
 489
 490                 //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
 491                 IntEngLineTo(&psurf->SurfObj,
 492                              (CLIPOBJ *)&dc->co,
 493                              BrushObj,
 494                              x1,
 495                              ScanLine,
 496                              x2,
 497                              ScanLine,
 498                              &BoundRect,  // Bounding rectangle
 499                              RopMode);    // MIX
 500
 501                 x1 = newx1;
 502                 x2 = newx2;
 503             }
 504         }
 505
 506         pLeft = pRight;
 507         pRight = pLeft->pNext;
 508         winding += pLeft->YDirection;
 509     }
 510
 511     // There will always be a line left-over, render it now...
 512     BoundRect.left = x1;
 513     BoundRect.right = x2;
 514
 515     //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
 516     IntEngLineTo(&psurf->SurfObj,
 517                  (CLIPOBJ *)&dc->co,
 518                  BrushObj,
 519                  x1,
 520                  ScanLine,
 521                  x2,
 522                  ScanLine,
 523                  &BoundRect,  // Bounding rectangle
 524                  RopMode);    // MIX
 525 }
 526
 527 // When the fill mode is ALTERNATE, GDI fills the area between odd-numbered and
 528 // even-numbered polygon sides on each scan line. That is, GDI fills the area between the
 529 // first and second side, between the third and fourth side, and so on.
 530
 531 // WINDING Selects winding mode (fills any region with a nonzero winding value).
 532 // When the fill mode is WINDING, GDI fills any region that has a nonzero winding value.
 533 // This value is defined as the number of times a pen used to draw the polygon would go around the region.
 534 // The direction of each edge of the polygon is important.
 535
 536 BOOL
 537 APIENTRY
 538 FillPolygon(
 539     PDC dc,
 540     SURFACE *psurf,
 541     BRUSHOBJ *BrushObj,
 542     MIX RopMode,
 543     CONST PPOINT Points,
 544     int Count,
 545     RECTL BoundRect )
 546 {
 547     FILL_EDGE_LIST *list = 0;
 548     FILL_EDGE *ActiveHead = 0;
 549     int ScanLine;
 550     PDC_ATTR pdcattr = dc->pdcattr;
 551     void
 552     (APIENTRY *FillScanLine)(
 553         PDC dc,
 554         int ScanLine,
 555         FILL_EDGE* ActiveHead,
 556         SURFACE *psurf,
 557         BRUSHOBJ *BrushObj,
 558         MIX RopMode);
 559
 560     //DPRINT("FillPolygon\n");
 561
 562     /* Create Edge List. */
 563     list = POLYGONFILL_MakeEdgeList(Points, Count);
 564     /* DEBUG_PRINT_EDGELIST(list); */
 565     if (NULL == list)
 566         return FALSE;
 567
 568     if (WINDING == pdcattr->jFillMode)
 569         FillScanLine = POLYGONFILL_FillScanLineWinding;
 570     else /* Default */
 571         FillScanLine = POLYGONFILL_FillScanLineAlternate;
 572
 573     /* For each Scanline from BoundRect.bottom to BoundRect.top,
 574      * determine line segments to draw
 575      */
 576     for (ScanLine = BoundRect.top; ScanLine < BoundRect.bottom; ++ScanLine)
 577     {
 578         POLYGONFILL_BuildActiveList(ScanLine, list, &ActiveHead);
 579         //DEBUG_PRINT_ACTIVE_EDGELIST(ActiveHead);
 580         FillScanLine(dc, ScanLine, ActiveHead, psurf, BrushObj, RopMode);
 581     }
 582
 583     /* Free Edge List. If any are left. */
 584     POLYGONFILL_DestroyEdgeList(list);
 585
 586     return TRUE;
 587 }
 588
 589 BOOL FASTCALL
 590 IntFillPolygon(
 591     PDC dc,
 592     SURFACE *psurf,
 593     BRUSHOBJ *BrushObj,
 594     CONST PPOINT Points,
 595     int Count,
 596     RECTL DestRect,
 597     POINTL *BrushOrigin)
 598 {
 599     FILL_EDGE_LIST *list = 0;
 600     FILL_EDGE *ActiveHead = 0;
 601     FILL_EDGE *pLeft, *pRight;
 602     int ScanLine;
 603
 604     //DPRINT("IntFillPolygon\n");
 605
 606     /* Create Edge List. */
 607     list = POLYGONFILL_MakeEdgeList(Points, Count);
 608     /* DEBUG_PRINT_EDGELIST(list); */
 609     if (NULL == list)
 610         return FALSE;
 611
 612     /* For each Scanline from DestRect.top to DestRect.bottom, determine line segments to draw */
 613     for (ScanLine = DestRect.top; ScanLine < DestRect.bottom; ++ScanLine)
 614     {
 615         POLYGONFILL_BuildActiveList(ScanLine, list, &ActiveHead);
 616         //DEBUG_PRINT_ACTIVE_EDGELIST(ActiveHead);
 617
 618         if (!ActiveHead)
 619         {
 620             POLYGONFILL_DestroyEdgeList(list);
 621             return FALSE;
 622         }
 623
 624         pLeft = ActiveHead;
 625         pRight = pLeft->pNext;
 626         ASSERT(pRight);
 627
 628         while (NULL != pRight)
 629         {
 630             int x1 = pLeft->XIntercept[0];
 631             int x2 = pRight->XIntercept[1];
 632
 633             if (x2 > x1)
 634             {
 635                 RECTL LineRect;
 636                 LineRect.top = ScanLine;
 637                 LineRect.bottom = ScanLine + 1;
 638                 LineRect.left = x1;
 639                 LineRect.right = x2;
 640
 641                 IntEngBitBlt(&psurf->SurfObj,
 642                              NULL,
 643                              NULL,
 644                              (CLIPOBJ *)&dc->co,
 645                              NULL,
 646                              &LineRect,
 647                              NULL,
 648                              NULL,
 649                              BrushObj,
 650                              BrushOrigin,
 651                              ROP4_FROM_INDEX(R3_OPINDEX_PATCOPY));
 652             }
 653
 654             pLeft = pRight->pNext;
 655             pRight = pLeft ? pLeft->pNext : NULL;
 656         }
 657     }
 658
 659     /* Free Edge List. If any are left. */
 660     POLYGONFILL_DestroyEdgeList(list);
 661
 662     return TRUE;
 663 }
 664
 665 /* EOF */