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