reactos/subsystems/win32/win32k/objects/polyfill.c

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