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