2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS Win32k subsystem
4 * PURPOSE: Various Polygon Filling routines for Polygon()
5 * FILE: subsystems/win32/win32k/objects/polyfill.c
6 * PROGRAMER: Mark Tempel
14 #define FILL_EDGE_ALLOC_TAG 0x45465044
17 ** This struct is used for book keeping during polygon filling routines.
19 typedef struct _tagFILL_EDGE
21 /* Basic line information */
32 /* Active Edge List information */
36 int XDirection
, YDirection
;
38 /* The next edge in the active Edge List */
39 struct _tagFILL_EDGE
* pNext
;
42 typedef struct _FILL_EDGE_LIST
51 DEBUG_PRINT_ACTIVE_EDGELIST ( FILL_EDGE
* list
)
53 FILL_EDGE
* pThis
= list
;
56 DPRINT1("List is NULL\n");
62 //DPRINT1("EDGE: (%d, %d) to (%d, %d)\n", pThis->FromX, pThis->FromY, pThis->ToX, pThis->ToY);
63 DPRINT1("EDGE: [%d,%d]\n", pThis
->XIntercept
[0], pThis
->XIntercept
[1] );
68 #define DEBUG_PRINT_ACTIVE_EDGELIST(x)
72 ** Hide memory clean up.
77 POLYGONFILL_DestroyEdgeList(FILL_EDGE_LIST
* list
)
84 for ( i
= 0; i
< list
->Count
; i
++ )
87 EngFreeMem ( list
->Edges
[i
] );
89 EngFreeMem ( list
->Edges
);
96 ** This makes and initiaizes an Edge struct for a line between two points.
101 POLYGONFILL_MakeEdge(POINT From
, POINT To
)
103 FILL_EDGE
* rc
= (FILL_EDGE
*)EngAllocMem(FL_ZERO_MEMORY
, sizeof(FILL_EDGE
), FILL_EDGE_ALLOC_TAG
);
108 //DPRINT1("Making Edge: (%d, %d) to (%d, %d)\n", From.x, From.y, To.x, To.y);
109 // Now fill the struct.
118 // Lines that go up get walked backwards, so need to be offset
119 // by -1 in order to make the walk identically on a pixel-level
135 rc
->dx
= rc
->ToX
- rc
->FromX
;
136 rc
->dy
= rc
->ToY
- rc
->FromY
;
137 rc
->absdx
= abs(rc
->dx
);
138 rc
->absdy
= abs(rc
->dy
);
140 rc
->xmajor
= rc
->absdx
> rc
->absdy
;
142 rc
->ErrorMax
= max(rc
->absdx
,rc
->absdy
);
144 rc
->Error
+= rc
->ErrorMax
/ 2;
146 rc
->XDirection
= (rc
->dx
< 0)?(-1):(1);
150 //DPRINT("MakeEdge (%i,%i)->(%i,%i) d=(%i,%i) dir=(%i,%i) err=%i max=%i\n",
151 // From.x, From.y, To.x, To.y, rc->dx, rc->dy, rc->XDirection, rc->YDirection, rc->Error, rc->ErrorMax );
156 ** My Edge comparison routine.
157 ** This is for scan converting polygon fill.
158 ** First sort by MinY, then Minx, then slope.
160 ** This comparison will help us determine which
161 ** lines will become active first when scanning from
162 ** top (min y) to bottom (max y).
164 ** Return Value Meaning
165 ** Negative integer element1 < element2
166 ** Zero element1 = element2
167 ** Positive integer element1 > element2
172 FILL_EDGE_Compare(FILL_EDGE
* Edge1
, FILL_EDGE
* Edge2
)
174 int e1
= Edge1
->XIntercept
[0] + Edge1
->XIntercept
[1];
175 int e2
= Edge2
->XIntercept
[0] + Edge2
->XIntercept
[1];
182 ** Insert an edge into a list keeping the list in order.
187 POLYGONFILL_ActiveListInsert(FILL_EDGE
** activehead
, FILL_EDGE
* NewEdge
)
189 FILL_EDGE
*pPrev
, *pThis
;
190 //DPRINT1("In POLYGONFILL_ActiveListInsert()\n");
191 ASSERT ( activehead
&& NewEdge
);
194 NewEdge
->pNext
= NULL
;
195 *activehead
= NewEdge
;
199 ** First lets check to see if we have a new smallest value.
201 if (FILL_EDGE_Compare(NewEdge
, *activehead
) <= 0)
203 NewEdge
->pNext
= *activehead
;
204 *activehead
= NewEdge
;
208 ** Ok, now scan to the next spot to put this item.
212 while ( pThis
&& FILL_EDGE_Compare(pThis
, NewEdge
) < 0 )
215 pThis
= pThis
->pNext
;
219 NewEdge
->pNext
= pPrev
->pNext
;
220 pPrev
->pNext
= NewEdge
;
221 //DEBUG_PRINT_ACTIVE_EDGELIST(*activehead);
225 ** Create a list of edges for a list of points.
230 POLYGONFILL_MakeEdgeList(PPOINT Points
, int Count
)
233 FILL_EDGE_LIST
* list
= 0;
236 if ( 0 == Points
|| 2 > Count
)
239 list
= (FILL_EDGE_LIST
*)EngAllocMem(FL_ZERO_MEMORY
, sizeof(FILL_EDGE_LIST
), FILL_EDGE_ALLOC_TAG
);
243 list
->Edges
= (FILL_EDGE
**)EngAllocMem(FL_ZERO_MEMORY
, Count
*sizeof(FILL_EDGE
*), FILL_EDGE_ALLOC_TAG
);
247 memset ( list
->Edges
, 0, Count
* sizeof(FILL_EDGE
*) );
249 for ( CurPt
= 1; CurPt
< Count
; ++CurPt
)
251 e
= POLYGONFILL_MakeEdge ( Points
[CurPt
-1], Points
[CurPt
] );
255 // If a straight horizontal line - who cares?
259 list
->Edges
[list
->Count
++] = e
;
261 e
= POLYGONFILL_MakeEdge ( Points
[CurPt
-1], Points
[0] );
268 list
->Edges
[list
->Count
++] = e
;
273 DPRINT1("Out Of MEMORY!!\n");
274 POLYGONFILL_DestroyEdgeList ( list
);
280 ** This slow routine uses the data stored in the edge list to
281 ** calculate the x intercepts for each line in the edge list
282 ** for scanline Scanline.
283 **TODO: Get rid of this floating point arithmetic
288 POLYGONFILL_UpdateScanline(FILL_EDGE
* pEdge
, int Scanline
)
290 if ( 0 == pEdge
->dy
)
293 ASSERT ( pEdge
->FromY
<= Scanline
&& pEdge
->ToY
> Scanline
);
299 ASSERT ( pEdge
->y
== Scanline
);
301 // Now shoot to end of scanline collision
302 steps
= (pEdge
->ErrorMax
-pEdge
->Error
-1)/pEdge
->absdy
;
305 // Record first collision with scanline
307 pEdge
->x
+= steps
* pEdge
->XDirection
;
308 pEdge
->Error
+= steps
* pEdge
->absdy
;
309 ASSERT ( pEdge
->Error
< pEdge
->ErrorMax
);
310 pEdge
->XIntercept
[0] = min(x1
,pEdge
->x
);
311 pEdge
->XIntercept
[1] = max(x1
,pEdge
->x
);
315 pEdge
->XIntercept
[0] = pEdge
->x
;
316 pEdge
->XIntercept
[1] = pEdge
->x
;
319 // We should require exactly 1 step to step onto next scanline...
320 ASSERT ( (pEdge
->ErrorMax
-pEdge
->Error
-1) / pEdge
->absdy
== 0 );
321 pEdge
->x
+= pEdge
->XDirection
;
322 pEdge
->Error
+= pEdge
->absdy
;
323 ASSERT ( pEdge
->Error
>= pEdge
->ErrorMax
);
325 // Now step onto next scanline...
326 pEdge
->Error
-= pEdge
->absdx
;
329 else // Then this is a y-major line
331 pEdge
->XIntercept
[0] = pEdge
->x
;
332 pEdge
->XIntercept
[1] = pEdge
->x
;
334 pEdge
->Error
+= pEdge
->absdx
;
337 if ( pEdge
->Error
>= pEdge
->ErrorMax
)
339 pEdge
->Error
-= pEdge
->ErrorMax
;
340 pEdge
->x
+= pEdge
->XDirection
;
341 ASSERT ( pEdge
->Error
< pEdge
->ErrorMax
);
345 //DPRINT("Line (%d, %d) to (%d, %d) intersects scanline %d at (%d,%d)\n",
346 // pEdge->FromX, pEdge->FromY, pEdge->ToX, pEdge->ToY, Scanline, pEdge->XIntercept[0], pEdge->XIntercept[1] );
350 * This method updates the Active edge collection for the scanline Scanline.
355 POLYGONFILL_BuildActiveList ( int Scanline
, FILL_EDGE_LIST
* list
, FILL_EDGE
** ActiveHead
)
359 ASSERT ( list
&& ActiveHead
);
361 for ( i
= 0; i
< list
->Count
; i
++ )
363 FILL_EDGE
* pEdge
= list
->Edges
[i
];
365 if ( pEdge
->FromY
<= Scanline
&& pEdge
->ToY
> Scanline
)
367 POLYGONFILL_UpdateScanline ( pEdge
, Scanline
);
368 POLYGONFILL_ActiveListInsert ( ActiveHead
, pEdge
);
374 ** This method fills the portion of the polygon that intersects with the scanline
380 POLYGONFILL_FillScanLineAlternate(
383 FILL_EDGE
* ActiveHead
,
388 FILL_EDGE
*pLeft
, *pRight
;
394 pRight
= pLeft
->pNext
;
397 while ( NULL
!= pRight
)
399 int x1
= pLeft
->XIntercept
[0];
400 int x2
= pRight
->XIntercept
[1];
404 BoundRect
.top
= ScanLine
;
405 BoundRect
.bottom
= ScanLine
+ 1;
407 BoundRect
.right
= x2
;
409 //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
410 IntEngLineTo(&psurf
->SurfObj
,
417 &BoundRect
, // Bounding rectangle
420 pLeft
= pRight
->pNext
;
421 pRight
= pLeft
? pLeft
->pNext
: NULL
;
428 POLYGONFILL_FillScanLineWinding(
431 FILL_EDGE
* ActiveHead
,
436 FILL_EDGE
*pLeft
, *pRight
;
437 int x1
, x2
, winding
= 0;
443 BoundRect
.top
= ScanLine
;
444 BoundRect
.bottom
= ScanLine
+ 1;
447 winding
= pLeft
->YDirection
;
448 pRight
= pLeft
->pNext
;
451 // Setup first line...
452 x1
= pLeft
->XIntercept
[0];
453 x2
= pRight
->XIntercept
[1];
456 pRight
= pLeft
->pNext
;
457 winding
+= pLeft
->YDirection
;
459 while ( NULL
!= pRight
)
461 int newx1
= pLeft
->XIntercept
[0];
462 int newx2
= pRight
->XIntercept
[1];
465 // Check and see if this new line touches the previous...
466 if ( (newx1
>= x1
&& newx1
<= x2
)
467 || (newx2
>= x1
&& newx2
<= x2
)
468 || (x1
>= newx1
&& x1
<= newx2
)
469 || (x2
>= newx2
&& x2
<= newx2
)
472 // Yup, just tack it on to our existing line
478 // Nope - render the old line..
480 BoundRect
.right
= x2
;
482 //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
483 IntEngLineTo(&psurf
->SurfObj
,
490 &BoundRect
, // Bounding rectangle
498 pRight
= pLeft
->pNext
;
499 winding
+= pLeft
->YDirection
;
501 // There will always be a line left-over, render it now...
503 BoundRect
.right
= x2
;
505 //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
506 IntEngLineTo(&psurf
->SurfObj
,
513 &BoundRect
, // Bounding rectangle
517 // When the fill mode is ALTERNATE, GDI fills the area between odd-numbered and
518 // even-numbered polygon sides on each scan line. That is, GDI fills the area between the
519 // first and second side, between the third and fourth side, and so on.
521 // WINDING Selects winding mode (fills any region with a nonzero winding value).
522 // When the fill mode is WINDING, GDI fills any region that has a nonzero winding value.
523 // This value is defined as the number of times a pen used to draw the polygon would go around the region.
524 // The direction of each edge of the polygon is important.
537 FILL_EDGE_LIST
*list
= 0;
538 FILL_EDGE
*ActiveHead
= 0;
540 PDC_ATTR pdcattr
= dc
->pdcattr
;
542 (APIENTRY
*FillScanLine
)(
545 FILL_EDGE
* ActiveHead
,
550 //DPRINT("FillPolygon\n");
552 /* Create Edge List. */
553 list
= POLYGONFILL_MakeEdgeList(Points
, Count
);
554 /* DEBUG_PRINT_EDGELIST(list); */
558 if ( WINDING
== pdcattr
->jFillMode
)
559 FillScanLine
= POLYGONFILL_FillScanLineWinding
;
561 FillScanLine
= POLYGONFILL_FillScanLineAlternate
;
563 /* For each Scanline from BoundRect.bottom to BoundRect.top,
564 * determine line segments to draw
566 for ( ScanLine
= BoundRect
.top
; ScanLine
< BoundRect
.bottom
; ++ScanLine
)
568 POLYGONFILL_BuildActiveList(ScanLine
, list
, &ActiveHead
);
569 //DEBUG_PRINT_ACTIVE_EDGELIST(ActiveHead);
570 FillScanLine ( dc
, ScanLine
, ActiveHead
, psurf
, BrushObj
, RopMode
);
573 /* Free Edge List. If any are left. */
574 POLYGONFILL_DestroyEdgeList(list
);
589 FILL_EDGE_LIST
*list
= 0;
590 FILL_EDGE
*ActiveHead
= 0;
591 FILL_EDGE
*pLeft
, *pRight
;
594 //DPRINT("IntFillPolygon\n");
596 /* Create Edge List. */
597 list
= POLYGONFILL_MakeEdgeList(Points
, Count
);
598 /* DEBUG_PRINT_EDGELIST(list); */
602 /* For each Scanline from DestRect.top to DestRect.bottom, determine line segments to draw */
603 for ( ScanLine
= DestRect
.top
; ScanLine
< DestRect
.bottom
; ++ScanLine
)
605 POLYGONFILL_BuildActiveList(ScanLine
, list
, &ActiveHead
);
606 //DEBUG_PRINT_ACTIVE_EDGELIST(ActiveHead);
612 pRight
= pLeft
->pNext
;
615 while ( NULL
!= pRight
)
617 int x1
= pLeft
->XIntercept
[0];
618 int x2
= pRight
->XIntercept
[1];
622 LineRect
.top
= ScanLine
;
623 LineRect
.bottom
= ScanLine
+ 1;
627 IntEngBitBlt(&psurf
->SurfObj
,
637 ROP4_FROM_INDEX(R3_OPINDEX_PATCOPY
));
639 pLeft
= pRight
->pNext
;
640 pRight
= pLeft
? pLeft
->pNext
: NULL
;
644 /* Free Edge List. If any are left. */
645 POLYGONFILL_DestroyEdgeList(list
);