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