subsys/win32k/objects/polyfill.c

   1 /*
   2  * COPYRIGHT:         See COPYING in the top level directory
   3  * PROJECT:           ReactOS kernel
   4  * PURPOSE:           Various Polygon Filling routines for Polygon()
   5  * FILE:              subsys/win32k/objects/polyfill.c
   6  * PROGRAMER:         Mark Tempel
   7  * REVISION HISTORY:
   8  *                 21/2/2003: Created
   9  */
  10
  11 #undef WIN32_LEAN_AND_MEAN
  12 #include <windows.h>
  13 #include <ddk/ntddk.h>
  14 #include <win32k/fillshap.h>
  15 #include <win32k/dc.h>
  16 #include <win32k/pen.h>
  17 #include <include/object.h>
  18
  19 #define NDEBUG
  20 #include <win32k/debug1.h>
  21
  22 #define PFILL_EDGE_ALLOC_TAG 0x45465044
  23
  24 /*
  25 ** This struct is used for book keeping during polygon filling routines.
  26 */
  27 typedef struct _tagPFILL_EDGE
  28 {
  29     /*Basic line information*/
  30         int FromX;
  31         int FromY;
  32         int ToX;
  33         int ToY;
  34         int dx;
  35         int dy;
  36         int MinX;
  37         int MaxX;
  38         int MinY;
  39         int MaxY;
  40
  41     /*Active Edge List information*/
  42     int XIntercept;
  43     int ErrorTerm;
  44     int ErrorTermAdjUp;
  45     int ErrorTermAdjDown;
  46     int XPerY;
  47     int Direction;
  48
  49     /* The next edge in the Edge List*/
  50         struct _tagPFILL_EDGE * pNext;
  51 } PFILL_EDGE, *PPFILL_EDGE;
  52
  53 typedef PPFILL_EDGE     PFILL_EDGE_LIST;
  54
  55 static void DEBUG_PRINT_EDGELIST(PFILL_EDGE_LIST list)
  56 {
  57     PPFILL_EDGE pThis = list;
  58     if (0 == list)
  59     {
  60         DPRINT("List is NULL\n");
  61         return;
  62     }
  63
  64     while(0 != pThis)
  65     {
  66         DPRINT("EDGE: (%d, %d) to (%d, %d)\n", pThis->FromX, pThis->FromY, pThis->ToX, pThis->ToY);
  67         pThis = pThis->pNext;
  68     }
  69 }
  70
  71 /*
  72 **  Hide memory clean up.
  73 */
  74 static void POLYGONFILL_DestroyEdge(PPFILL_EDGE pEdge)
  75 {
  76     if (0 != pEdge)
  77         EngFreeMem(pEdge);
  78 }
  79
  80 /*
  81 ** Clean up a list.
  82 */
  83 static void POLYGONFILL_DestroyEdgeList(PFILL_EDGE_LIST list)
  84 {
  85     PPFILL_EDGE pThis = 0;
  86     PPFILL_EDGE pNext = 0;
  87
  88     pThis = list;
  89     while (0 != pThis)
  90     {
  91         //DPRINT("Destroying Edge\n");
  92         pNext = pThis->pNext;
  93         POLYGONFILL_DestroyEdge(pThis);
  94         pThis = pNext;
  95     }
  96
  97 }
  98
  99 /*
 100 ** This makes and initiaizes an Edge struct for a line between two points.
 101 */
 102 static PPFILL_EDGE POLYGONFILL_MakeEdge(POINT From, POINT To)
 103 {
 104     PPFILL_EDGE rc = (PPFILL_EDGE)EngAllocMem(FL_ZERO_MEMORY, sizeof(PFILL_EDGE), PFILL_EDGE_ALLOC_TAG);
 105
 106     if (0 != rc)
 107     {
 108         //DPRINT("Making Edge: (%d, %d) to (%d, %d)\n", From.x, From.y, To.x, To.y);
 109         //Now Fill the struct.
 110             rc->FromX = From.x;
 111             rc->FromY = From.y;
 112             rc->ToX = To.x;
 113             rc->ToY = To.y;
 114
 115             rc->dx   = To.x - From.x;
 116             rc->dy   = To.y - From.y;
 117         rc->MinX = MIN(To.x, From.x);
 118             rc->MaxX = MAX(To.x, From.x);
 119             rc->MinY = MIN(To.y, From.y);
 120             rc->MaxY = MAX(To.y, From.y);
 121
 122         if (rc->MinY == To.y)
 123             rc->XIntercept = To.x;
 124         else
 125             rc->XIntercept = From.x;
 126
 127         rc->ErrorTermAdjDown = rc->dy;
 128         rc->Direction   = (rc->dx < 0)?(-1):(1);
 129
 130         if (rc->dx >= 0) /*edge goes l to r*/
 131         {
 132             rc->ErrorTerm   = 0;
 133         }
 134         else/*edge goes r to l*/
 135         {
 136             rc->ErrorTerm = -rc->dy +1;
 137         }
 138
 139         /*Now which part of the slope is greater?*/
 140         if (rc->dy == 0)
 141         {
 142             rc->XPerY = 0;
 143             rc->ErrorTermAdjUp = 0;
 144         }
 145         else if (rc->dy >= rc->dx)
 146         {
 147             rc->XPerY = 0;
 148             rc->ErrorTermAdjUp = rc->dx;
 149         }
 150         else
 151         {
 152             rc->XPerY = rc->dx / rc->dy;
 153             rc->ErrorTermAdjUp = rc->dx % rc->dy;
 154         }
 155
 156         rc->pNext = 0;
 157     }
 158     return rc;
 159 }
 160 /*
 161 ** My Edge comparison routine.
 162 ** This is for scan converting polygon fill.
 163 ** Fist sort by MinY, then Minx, then slope.
 164 **
 165 ** This comparison will help us determine which
 166 ** lines will become active first when scanning from
 167 ** top (min y) to bottom (max y).
 168 **
 169 ** Return Value Meaning
 170 ** Negative integer element1 < element2
 171 ** Zero element1 = element2
 172 ** Positive integer element1 > element2
 173 */
 174 static INT PFILL_EDGE_Compare(PPFILL_EDGE Edge1, PPFILL_EDGE Edge2)
 175 {
 176     //DPRINT("In PFILL_EDGE_Compare()\n");
 177         if (Edge1->MinY == Edge2->MinY)
 178     {
 179         //DPRINT("In PFILL_EDGE_Compare() MinYs are equal\n");
 180         if (Edge1->MinX == Edge2->MinX)
 181         {
 182             if (0 == Edge2->dx || 0 == Edge1->dx)
 183             {
 184                 return Edge1->dx - Edge2->dx;
 185             }
 186             else
 187             {
 188                 return (Edge1->dy/Edge1->dx) - (Edge2->dy/Edge2->dx);
 189             }
 190         }
 191         else
 192         {
 193             return Edge1->MinX - Edge2->MinX;
 194         }
 195     }
 196     //DPRINT("In PFILL_EDGE_Compare() returning: %d\n",Edge1->MinY - Edge2->MinY);
 197     return Edge1->MinY - Edge2->MinY;
 198
 199 }
 200
 201
 202 /*
 203 ** Insert an edge into a list keeping the list in order.
 204 */
 205 static void POLYGONFILL_ListInsert(PFILL_EDGE_LIST *list, PPFILL_EDGE NewEdge)
 206 {
 207     PPFILL_EDGE pThis;
 208     if (0 != list && 0 != NewEdge)
 209     {
 210         pThis = *list;
 211         //DPRINT("In POLYGONFILL_ListInsert()\n");
 212         /*
 213         ** First lets check to see if we have a new smallest value.
 214         */
 215         if (0 < PFILL_EDGE_Compare(pThis, NewEdge))
 216         {
 217             NewEdge->pNext = pThis;
 218             *list = NewEdge;
 219             return;
 220         }
 221         /*
 222         ** Ok, now scan to the next spot to put this item.
 223         */
 224         while (0 > PFILL_EDGE_Compare(pThis, NewEdge))
 225         {
 226             if (0 == pThis->pNext)
 227                 break;
 228
 229             pThis = pThis->pNext;
 230         }
 231
 232         NewEdge->pNext = pThis->pNext;
 233         pThis->pNext = NewEdge;
 234         //DEBUG_PRINT_EDGELIST(*list);
 235     }
 236 }
 237
 238 /*
 239 ** Create a list of edges for a list of points.
 240 */
 241 static PFILL_EDGE_LIST  POLYGONFILL_MakeEdgeList(PPOINT Points, int Count)
 242 {
 243         int CurPt = 0;
 244         int SeqNum = 0;
 245     PPFILL_EDGE rc = 0;
 246     PPFILL_EDGE NextEdge = 0;
 247
 248         if (0 != Points && 2 <= Count)
 249         {
 250         //Establish the list with the first two points.
 251                 rc = POLYGONFILL_MakeEdge(Points[0],Points[1]);
 252                 if (0 == rc) return rc;
 253
 254                 for (CurPt = 1; CurPt < Count; ++CurPt,++SeqNum)
 255                 {
 256                     if (CurPt == Count - 1)
 257             {
 258                 NextEdge = POLYGONFILL_MakeEdge(Points[CurPt],Points[0]);
 259             }
 260             else
 261             {
 262                 NextEdge = POLYGONFILL_MakeEdge(Points[CurPt],Points[CurPt + 1]);
 263             }
 264             if (0 != NextEdge)
 265             {
 266                 POLYGONFILL_ListInsert(&rc, NextEdge);
 267             }
 268             else
 269             {
 270                 DPRINT("Out Of MEMORY!! NextEdge = 0\n");
 271             }
 272                 }
 273         }
 274         return rc;
 275 }
 276
 277
 278 /*
 279 ** This slow routine uses the data stored in the edge list to
 280 ** calculate the x intercepts for each line in the edge list
 281 ** for scanline Scanline.
 282 **TODO: Get rid of this floating point arithmetic
 283 */
 284 static void POLYGONFILL_UpdateScanline(PPFILL_EDGE pEdge, int Scanline)
 285 {
 286
 287     int Coord = 0;
 288     float XCoord = 0;
 289     if (0 == pEdge->dy) return;
 290
 291     XCoord = (Scanline*pEdge->dx - pEdge->FromY*pEdge->dx)/pEdge->dy + pEdge->FromX;
 292     Coord = XCoord + 0.5;
 293
 294     //DPRINT("Line (%d, %d) to (%d, %d) intersects scanline %d at %d\n",
 295     //        pEdge->FromX, pEdge->FromY, pEdge->ToX, pEdge->ToY, Scanline, Coord);
 296     pEdge->XIntercept = Coord;
 297
 298
 299     /*pEdge->XIntercept += pEdge->XPerY;
 300
 301     if ((pEdge->ErrorTerm += pEdge->ErrorTermAdjUp) > 0)
 302     {
 303         pEdge->XIntercept += pEdge->Direction;
 304         pEdge->ErrorTerm -= pEdge->ErrorTermAdjDown;
 305     }*/
 306 }
 307
 308 /*
 309 ** This routine removes an edge from the global edge list and inserts it into
 310 ** the active edge list (preserving the order).
 311 ** An edge is considered Active if the current scanline intersects it.
 312 **
 313 ** Note: once an edge is no longer active, it is deleted.
 314 */
 315 static void POLYGONFILL_AECInsertInOrder(PFILL_EDGE_LIST *list, PPFILL_EDGE pEdge)
 316 {
 317     BOOL Done = FALSE;
 318     PPFILL_EDGE pThis = 0;
 319     PPFILL_EDGE pPrev = 0;
 320     pThis = *list;
 321     while(0 != pThis && !Done)
 322     {
 323         /*pEdge goes before pThis*/
 324         if (pThis->XIntercept > pEdge->XIntercept)
 325         {
 326             if (*list == pThis)
 327             {
 328                 *list = pEdge;
 329             }
 330             else
 331             {
 332                 pPrev->pNext = pEdge;
 333             }
 334             pEdge->pNext = pThis;
 335             Done = TRUE;
 336         }
 337         pPrev = pThis;
 338         pThis = pThis->pNext;
 339     }
 340 }
 341
 342 /*
 343 ** This routine reorders the Active Edge collection (list) after all
 344 ** the now inactive edges have been removed.
 345 */
 346 static void POLYGONFILL_AECReorder(PFILL_EDGE_LIST *AEC)
 347 {
 348     PPFILL_EDGE pThis = 0;
 349     PPFILL_EDGE pPrev = 0;
 350     PPFILL_EDGE pTarg = 0;
 351     pThis = *AEC;
 352
 353     while (0 != pThis)
 354     {
 355         /*We are at the end of the list*/
 356         if (0 == pThis->pNext)
 357         {
 358             return;
 359         }
 360
 361         /*If the next item is out of order, pull it from the list and
 362         re-insert it, and don't advance pThis.*/
 363         if (pThis->XIntercept > pThis->pNext->XIntercept)
 364         {
 365             pTarg = pThis->pNext;
 366             pThis->pNext = pTarg->pNext;
 367             pTarg->pNext = 0;
 368             POLYGONFILL_AECInsertInOrder(AEC, pTarg);
 369         }
 370         else/*In order, advance pThis*/
 371         {
 372             pPrev = pThis;
 373             pThis = pThis->pNext;
 374         }
 375     }
 376
 377 }
 378 /*
 379 ** This method updates the Active edge collection for the scanline Scanline.
 380 */
 381 static void POLYGONFILL_UpdateActiveEdges(int Scanline, PFILL_EDGE_LIST *GEC, PFILL_EDGE_LIST *AEC)
 382 {
 383     PPFILL_EDGE pThis = 0;
 384     PPFILL_EDGE pAECLast = 0;
 385     PPFILL_EDGE pPrev = 0;
 386     DPRINT("In POLYGONFILL_UpdateActiveEdges() Scanline: %d\n", Scanline);
 387     /*First scan through GEC and look for any edges that have become active*/
 388     pThis = *GEC;
 389     while (0 != pThis && pThis->MinY <= Scanline)
 390     {
 391         //DPRINT("Moving Edge to AEC\n");
 392         /*Remove the edge from GEC and put it into AEC*/
 393         if (pThis->MinY <= Scanline)
 394         {
 395             /*Always peel off the front of the GEC*/
 396             *GEC = pThis->pNext;
 397
 398             /*Now put this edge at the end of AEC*/
 399             if (0 == *AEC)
 400             {
 401                 *AEC = pThis;
 402                 pThis->pNext = 0;
 403                 pAECLast = pThis;
 404             }
 405             else if(0 == pAECLast)
 406             {
 407                 pAECLast = *AEC;
 408                 while(0 != pAECLast->pNext)
 409                 {
 410                     pAECLast = pAECLast->pNext;
 411                 }
 412
 413                 pAECLast->pNext = pThis;
 414                 pThis->pNext = 0;
 415                 pAECLast = pThis;
 416             }
 417             else
 418             {
 419                 pAECLast->pNext = pThis;
 420                 pThis->pNext = 0;
 421                 pAECLast = pThis;
 422
 423             }
 424         }
 425
 426         pThis = *GEC;
 427     }
 428     /*Now remove any edges in the AEC that are no longer active and Update the XIntercept in the AEC*/
 429     pThis = *AEC;
 430     while (0 != pThis)
 431     {
 432         /*First check to see if this item is deleted*/
 433         if (pThis->MaxY <= Scanline)
 434         {
 435             //DPRINT("Removing Edge from AEC\n");
 436             if (0 == pPrev)/*First element in the list*/
 437             {
 438                 *AEC = pThis->pNext;
 439             }
 440             else
 441             {
 442                 pPrev->pNext = pThis->pNext;
 443             }
 444             POLYGONFILL_DestroyEdge(pThis);
 445         }
 446         else/*Otherwise, update the scanline*/
 447         {
 448             POLYGONFILL_UpdateScanline(pThis, Scanline);
 449             pPrev = pThis;
 450         }
 451         /*List Upkeep*/
 452         if (0 == pPrev)/*First element in the list*/
 453         {
 454             pThis = *AEC;
 455         }
 456         else
 457         {
 458             pThis = pPrev->pNext;
 459         }
 460     }
 461     /*Last re Xintercept order the AEC*/
 462     POLYGONFILL_AECReorder(AEC);
 463
 464 }
 465
 466 /*
 467 ** This method fills the portion of the polygon that intersects with the scanline
 468 ** Scanline.
 469 */
 470 static void POLYGONFILL_FillScanLine(int ScanLine, PFILL_EDGE_LIST ActiveEdges, SURFOBJ *SurfObj, PBRUSHOBJ BrushObj, MIX RopMode, int OrigX, int OrigY)
 471 {
 472     BOOL OnOdd = TRUE;
 473     RECTL BoundRect;
 474     int XInterceptOdd,XInterceptEven,ret;
 475     PPFILL_EDGE pThis = ActiveEdges;
 476
 477     while (0 != pThis)
 478     {
 479         if (OnOdd)
 480         {
 481             XInterceptOdd = pThis->XIntercept;
 482             OnOdd = FALSE;
 483         }
 484         else
 485         {
 486             BoundRect.top = ScanLine + OrigY - 1;
 487             BoundRect.bottom = ScanLine + OrigY + 1;
 488             BoundRect.left = XInterceptOdd + OrigX - 2;
 489             BoundRect.right = XInterceptEven + OrigX;
 490
 491             XInterceptEven = pThis->XIntercept;
 492             DPRINT("Fill Line (%d, %d) to (%d, %d)\n",XInterceptOdd - 1,ScanLine ,XInterceptEven - 1,ScanLine );
 493             ret = EngLineTo(SurfObj,
 494                                                 NULL, // ClipObj,
 495                                                 BrushObj,
 496                                                 XInterceptOdd + OrigX - 1,
 497                                                 ScanLine + OrigY,
 498                                                 XInterceptEven + OrigX - 1,
 499                                                 ScanLine + OrigY,
 500                                                 &BoundRect, // Bounding rectangle
 501                                                 RopMode); // MIX
 502             OnOdd = TRUE;
 503         }
 504         pThis = pThis->pNext;
 505     }
 506 }
 507
 508 //ALTERNATE Selects alternate mode (fills the area between odd-numbered and even-numbered
 509 //polygon sides on each scan line).
 510 //When the fill mode is ALTERNATE, GDI fills the area between odd-numbered and
 511 //even-numbered polygon sides on each scan line. That is, GDI fills the area between the
 512 //first and second side, between the third and fourth side, and so on.
 513 BOOL FillPolygon_ALTERNATE(SURFOBJ *SurfObj, PBRUSHOBJ BrushObj, MIX RopMode, CONST PPOINT Points, int Count, RECTL BoundRect, int OrigX, int OrigY)
 514 {
 515         PFILL_EDGE_LIST list = 0;
 516     PFILL_EDGE_LIST ActiveEdges = 0;
 517     int ScanLine;
 518         DPRINT("FillPolygon_ALTERNATE\n");
 519
 520         //Create Edge List.
 521         list = POLYGONFILL_MakeEdgeList(Points, Count);
 522         //DEBUG_PRINT_EDGELIST(list);
 523     if (0 == list) return FALSE;
 524
 525         //For each Scanline from BoundRect.bottom to BoundRect.top,
 526         //determine line segments to draw
 527         for (ScanLine = BoundRect.top + 1; ScanLine < BoundRect.bottom ; ++ScanLine)
 528         {
 529         POLYGONFILL_UpdateActiveEdges(ScanLine, &list, &ActiveEdges);
 530         //DEBUG_PRINT_EDGELIST(ActiveEdges);
 531         POLYGONFILL_FillScanLine(ScanLine, ActiveEdges, SurfObj, BrushObj, RopMode, OrigX, OrigY);
 532         }
 533
 534         //Free Edge List. If any are left.
 535         POLYGONFILL_DestroyEdgeList(list);
 536
 537         return TRUE;
 538 }
 539
 540 //WINDING Selects winding mode (fills any region with a nonzero winding value).
 541 //When the fill mode is WINDING, GDI fills any region that has a nonzero winding value.
 542 //This value is defined as the number of times a pen used to draw the polygon would go around the region.
 543 //The direction of each edge of the polygon is important.
 544 BOOL FillPolygon_WINDING(SURFOBJ *SurfObj, PBRUSHOBJ BrushObj,MIX RopMode, CONST PPOINT Points, int Count, RECTL BoundRect, int OrigX, int OrigY)
 545 {
 546         DPRINT("FillPolygon_WINDING\n");
 547         return FALSE;
 548 }