2 * ReactOS W32 Subsystem
3 * Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 ReactOS Team
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.
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.
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.
19 /* $Id: polyfill.c,v 1.3 2003/05/18 17:16:18 ea Exp $
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
30 #undef WIN32_LEAN_AND_MEAN
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>
40 #include <win32k/debug1.h>
42 #define PFILL_EDGE_ALLOC_TAG 0x45465044
45 ** This struct is used for book keeping during polygon filling routines.
47 typedef struct _tagPFILL_EDGE
49 /*Basic line information*/
61 /*Active Edge List information*/
69 /* The next edge in the Edge List*/
70 struct _tagPFILL_EDGE
* pNext
;
71 } PFILL_EDGE
, *PPFILL_EDGE
;
73 typedef PPFILL_EDGE PFILL_EDGE_LIST
;
75 static void DEBUG_PRINT_EDGELIST(PFILL_EDGE_LIST list
)
77 PPFILL_EDGE pThis
= list
;
80 DPRINT("List is NULL\n");
86 DPRINT("EDGE: (%d, %d) to (%d, %d)\n", pThis
->FromX
, pThis
->FromY
, pThis
->ToX
, pThis
->ToY
);
92 ** Hide memory clean up.
94 static void FASTCALL
POLYGONFILL_DestroyEdge(PPFILL_EDGE pEdge
)
103 static void FASTCALL
POLYGONFILL_DestroyEdgeList(PFILL_EDGE_LIST list
)
105 PPFILL_EDGE pThis
= 0;
106 PPFILL_EDGE pNext
= 0;
111 //DPRINT("Destroying Edge\n");
112 pNext
= pThis
->pNext
;
113 POLYGONFILL_DestroyEdge(pThis
);
120 ** This makes and initiaizes an Edge struct for a line between two points.
122 static PPFILL_EDGE FASTCALL
POLYGONFILL_MakeEdge(POINT From
, POINT To
)
124 PPFILL_EDGE rc
= (PPFILL_EDGE
)EngAllocMem(FL_ZERO_MEMORY
, sizeof(PFILL_EDGE
), PFILL_EDGE_ALLOC_TAG
);
128 //DPRINT("Making Edge: (%d, %d) to (%d, %d)\n", From.x, From.y, To.x, To.y);
129 //Now Fill the struct.
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
);
142 if (rc
->MinY
== To
.y
)
143 rc
->XIntercept
= To
.x
;
145 rc
->XIntercept
= From
.x
;
147 rc
->ErrorTermAdjDown
= rc
->dy
;
148 rc
->Direction
= (rc
->dx
< 0)?(-1):(1);
150 if (rc
->dx
>= 0) /*edge goes l to r*/
154 else/*edge goes r to l*/
156 rc
->ErrorTerm
= -rc
->dy
+1;
159 /*Now which part of the slope is greater?*/
163 rc
->ErrorTermAdjUp
= 0;
165 else if (rc
->dy
>= rc
->dx
)
168 rc
->ErrorTermAdjUp
= rc
->dx
;
172 rc
->XPerY
= rc
->dx
/ rc
->dy
;
173 rc
->ErrorTermAdjUp
= rc
->dx
% rc
->dy
;
181 ** My Edge comparison routine.
182 ** This is for scan converting polygon fill.
183 ** Fist sort by MinY, then Minx, then slope.
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).
189 ** Return Value Meaning
190 ** Negative integer element1 < element2
191 ** Zero element1 = element2
192 ** Positive integer element1 > element2
194 static INT FASTCALL
PFILL_EDGE_Compare(PPFILL_EDGE Edge1
, PPFILL_EDGE Edge2
)
196 //DPRINT("In PFILL_EDGE_Compare()\n");
197 if (Edge1
->MinY
== Edge2
->MinY
)
199 //DPRINT("In PFILL_EDGE_Compare() MinYs are equal\n");
200 if (Edge1
->MinX
== Edge2
->MinX
)
202 if (0 == Edge2
->dx
|| 0 == Edge1
->dx
)
204 return Edge1
->dx
- Edge2
->dx
;
208 return (Edge1
->dy
/Edge1
->dx
) - (Edge2
->dy
/Edge2
->dx
);
213 return Edge1
->MinX
- Edge2
->MinX
;
216 //DPRINT("In PFILL_EDGE_Compare() returning: %d\n",Edge1->MinY - Edge2->MinY);
217 return Edge1
->MinY
- Edge2
->MinY
;
223 ** Insert an edge into a list keeping the list in order.
225 static void FASTCALL
POLYGONFILL_ListInsert(PFILL_EDGE_LIST
*list
, PPFILL_EDGE NewEdge
)
228 if (0 != list
&& 0 != NewEdge
)
231 //DPRINT("In POLYGONFILL_ListInsert()\n");
233 ** First lets check to see if we have a new smallest value.
235 if (0 < PFILL_EDGE_Compare(pThis
, NewEdge
))
237 NewEdge
->pNext
= pThis
;
242 ** Ok, now scan to the next spot to put this item.
244 while (0 > PFILL_EDGE_Compare(pThis
, NewEdge
))
246 if (0 == pThis
->pNext
)
249 pThis
= pThis
->pNext
;
252 NewEdge
->pNext
= pThis
->pNext
;
253 pThis
->pNext
= NewEdge
;
254 //DEBUG_PRINT_EDGELIST(*list);
259 ** Create a list of edges for a list of points.
261 static PFILL_EDGE_LIST FASTCALL
POLYGONFILL_MakeEdgeList(PPOINT Points
, int Count
)
266 PPFILL_EDGE NextEdge
= 0;
268 if (0 != Points
&& 2 <= Count
)
270 //Establish the list with the first two points.
271 rc
= POLYGONFILL_MakeEdge(Points
[0],Points
[1]);
272 if (0 == rc
) return rc
;
274 for (CurPt
= 1; CurPt
< Count
; ++CurPt
,++SeqNum
)
276 if (CurPt
== Count
- 1)
278 NextEdge
= POLYGONFILL_MakeEdge(Points
[CurPt
],Points
[0]);
282 NextEdge
= POLYGONFILL_MakeEdge(Points
[CurPt
],Points
[CurPt
+ 1]);
286 POLYGONFILL_ListInsert(&rc
, NextEdge
);
290 DPRINT("Out Of MEMORY!! NextEdge = 0\n");
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
304 static void FASTCALL
POLYGONFILL_UpdateScanline(PPFILL_EDGE pEdge
, int Scanline
)
309 if (0 == pEdge
->dy
) return;
311 XCoord
= (Scanline
*pEdge
->dx
- pEdge
->FromY
*pEdge
->dx
)/pEdge
->dy
+ pEdge
->FromX
;
312 Coord
= XCoord
+ 0.5;
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
;
319 /*pEdge->XIntercept += pEdge->XPerY;
321 if ((pEdge->ErrorTerm += pEdge->ErrorTermAdjUp) > 0)
323 pEdge->XIntercept += pEdge->Direction;
324 pEdge->ErrorTerm -= pEdge->ErrorTermAdjDown;
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.
333 ** Note: once an edge is no longer active, it is deleted.
335 static void FASTCALL
POLYGONFILL_AECInsertInOrder(PFILL_EDGE_LIST
*list
, PPFILL_EDGE pEdge
)
338 PPFILL_EDGE pThis
= 0;
339 PPFILL_EDGE pPrev
= 0;
341 while(0 != pThis
&& !Done
)
343 /*pEdge goes before pThis*/
344 if (pThis
->XIntercept
> pEdge
->XIntercept
)
352 pPrev
->pNext
= pEdge
;
354 pEdge
->pNext
= pThis
;
358 pThis
= pThis
->pNext
;
363 ** This routine reorders the Active Edge collection (list) after all
364 ** the now inactive edges have been removed.
366 static void FASTCALL
POLYGONFILL_AECReorder(PFILL_EDGE_LIST
*AEC
)
368 PPFILL_EDGE pThis
= 0;
369 PPFILL_EDGE pPrev
= 0;
370 PPFILL_EDGE pTarg
= 0;
375 /*We are at the end of the list*/
376 if (0 == pThis
->pNext
)
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
)
385 pTarg
= pThis
->pNext
;
386 pThis
->pNext
= pTarg
->pNext
;
388 POLYGONFILL_AECInsertInOrder(AEC
, pTarg
);
390 else/*In order, advance pThis*/
393 pThis
= pThis
->pNext
;
399 ** This method updates the Active edge collection for the scanline Scanline.
401 static void STDCALL
POLYGONFILL_UpdateActiveEdges(int Scanline
, PFILL_EDGE_LIST
*GEC
, PFILL_EDGE_LIST
*AEC
)
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*/
409 while (0 != pThis
&& pThis
->MinY
<= Scanline
)
411 //DPRINT("Moving Edge to AEC\n");
412 /*Remove the edge from GEC and put it into AEC*/
413 if (pThis
->MinY
<= Scanline
)
415 /*Always peel off the front of the GEC*/
418 /*Now put this edge at the end of AEC*/
425 else if(0 == pAECLast
)
428 while(0 != pAECLast
->pNext
)
430 pAECLast
= pAECLast
->pNext
;
433 pAECLast
->pNext
= pThis
;
439 pAECLast
->pNext
= pThis
;
448 /*Now remove any edges in the AEC that are no longer active and Update the XIntercept in the AEC*/
452 /*First check to see if this item is deleted*/
453 if (pThis
->MaxY
<= Scanline
)
455 //DPRINT("Removing Edge from AEC\n");
456 if (0 == pPrev
)/*First element in the list*/
462 pPrev
->pNext
= pThis
->pNext
;
464 POLYGONFILL_DestroyEdge(pThis
);
466 else/*Otherwise, update the scanline*/
468 POLYGONFILL_UpdateScanline(pThis
, Scanline
);
472 if (0 == pPrev
)/*First element in the list*/
478 pThis
= pPrev
->pNext
;
481 /*Last re Xintercept order the AEC*/
482 POLYGONFILL_AECReorder(AEC
);
487 ** This method fills the portion of the polygon that intersects with the scanline
490 static void STDCALL
POLYGONFILL_FillScanLine(int ScanLine
, PFILL_EDGE_LIST ActiveEdges
, SURFOBJ
*SurfObj
, PBRUSHOBJ BrushObj
, MIX RopMode
, int OrigX
, int OrigY
)
494 int XInterceptOdd
,XInterceptEven
,ret
;
495 PPFILL_EDGE pThis
= ActiveEdges
;
501 XInterceptOdd
= pThis
->XIntercept
;
506 BoundRect
.top
= ScanLine
+ OrigY
- 1;
507 BoundRect
.bottom
= ScanLine
+ OrigY
+ 1;
508 BoundRect
.left
= XInterceptOdd
+ OrigX
- 2;
509 BoundRect
.right
= XInterceptEven
+ OrigX
;
511 XInterceptEven
= pThis
->XIntercept
;
512 DPRINT("Fill Line (%d, %d) to (%d, %d)\n",XInterceptOdd
- 1,ScanLine
,XInterceptEven
- 1,ScanLine
);
513 ret
= EngLineTo(SurfObj
,
516 XInterceptOdd
+ OrigX
- 1,
518 XInterceptEven
+ OrigX
- 1,
520 &BoundRect
, // Bounding rectangle
524 pThis
= pThis
->pNext
;
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
)
535 PFILL_EDGE_LIST list
= 0;
536 PFILL_EDGE_LIST ActiveEdges
= 0;
538 DPRINT("FillPolygon_ALTERNATE\n");
541 list
= POLYGONFILL_MakeEdgeList(Points
, Count
);
542 //DEBUG_PRINT_EDGELIST(list);
543 if (0 == list
) return FALSE
;
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
)
549 POLYGONFILL_UpdateActiveEdges(ScanLine
, &list
, &ActiveEdges
);
550 //DEBUG_PRINT_EDGELIST(ActiveEdges);
551 POLYGONFILL_FillScanLine(ScanLine
, ActiveEdges
, SurfObj
, BrushObj
, RopMode
, OrigX
, OrigY
);
554 //Free Edge List. If any are left.
555 POLYGONFILL_DestroyEdgeList(list
);
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
)
566 DPRINT("FillPolygon_WINDING\n");