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 along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
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
35 INT __cdecl
abs(INT nm
);
37 #define FILL_EDGE_ALLOC_TAG 0x45465044
40 ** This struct is used for book keeping during polygon filling routines.
42 typedef struct _tagFILL_EDGE
44 /*Basic line information*/
55 /*Active Edge List information*/
59 int XDirection
, YDirection
;
61 /* The next edge in the active Edge List*/
62 struct _tagFILL_EDGE
* pNext
;
65 typedef struct _FILL_EDGE_LIST
74 DEBUG_PRINT_ACTIVE_EDGELIST ( FILL_EDGE
* list
)
76 FILL_EDGE
* pThis
= list
;
79 DPRINT1("List is NULL\n");
85 //DPRINT1("EDGE: (%d, %d) to (%d, %d)\n", pThis->FromX, pThis->FromY, pThis->ToX, pThis->ToY);
86 DPRINT1("EDGE: [%d,%d]\n", pThis
->XIntercept
[0], pThis
->XIntercept
[1] );
91 #define DEBUG_PRINT_ACTIVE_EDGELIST(x)
95 ** Hide memory clean up.
100 POLYGONFILL_DestroyEdgeList(FILL_EDGE_LIST
* list
)
107 for ( i
= 0; i
< list
->Count
; i
++ )
109 if ( list
->Edges
[i
] )
110 EngFreeMem ( list
->Edges
[i
] );
112 EngFreeMem ( list
->Edges
);
119 ** This makes and initiaizes an Edge struct for a line between two points.
124 POLYGONFILL_MakeEdge(POINT From
, POINT To
)
126 FILL_EDGE
* rc
= (FILL_EDGE
*)EngAllocMem(FL_ZERO_MEMORY
, sizeof(FILL_EDGE
), FILL_EDGE_ALLOC_TAG
);
131 //DPRINT1("Making Edge: (%d, %d) to (%d, %d)\n", From.x, From.y, To.x, To.y);
132 //Now Fill the struct.
141 // lines that go up get walked backwards, so need to be offset
142 // by -1 in order to make the walk identically on a pixel-level
158 rc
->dx
= rc
->ToX
- rc
->FromX
;
159 rc
->dy
= rc
->ToY
- rc
->FromY
;
160 rc
->absdx
= abs(rc
->dx
);
161 rc
->absdy
= abs(rc
->dy
);
163 rc
->xmajor
= rc
->absdx
> rc
->absdy
;
165 rc
->ErrorMax
= max(rc
->absdx
,rc
->absdy
);
167 rc
->Error
+= rc
->ErrorMax
/ 2;
169 rc
->XDirection
= (rc
->dx
< 0)?(-1):(1);
173 //DPRINT("MakeEdge (%i,%i)->(%i,%i) d=(%i,%i) dir=(%i,%i) err=%i max=%i\n",
174 // From.x, From.y, To.x, To.y, rc->dx, rc->dy, rc->XDirection, rc->YDirection, rc->Error, rc->ErrorMax );
179 ** My Edge comparison routine.
180 ** This is for scan converting polygon fill.
181 ** First sort by MinY, then Minx, then slope.
183 ** This comparison will help us determine which
184 ** lines will become active first when scanning from
185 ** top (min y) to bottom (max y).
187 ** Return Value Meaning
188 ** Negative integer element1 < element2
189 ** Zero element1 = element2
190 ** Positive integer element1 > element2
195 FILL_EDGE_Compare(FILL_EDGE
* Edge1
, FILL_EDGE
* Edge2
)
197 int e1
= Edge1
->XIntercept
[0] + Edge1
->XIntercept
[1];
198 int e2
= Edge2
->XIntercept
[0] + Edge2
->XIntercept
[1];
205 ** Insert an edge into a list keeping the list in order.
210 POLYGONFILL_ActiveListInsert(FILL_EDGE
** activehead
, FILL_EDGE
* NewEdge
)
212 FILL_EDGE
*pPrev
, *pThis
;
213 //DPRINT1("In POLYGONFILL_ActiveListInsert()\n");
214 ASSERT ( activehead
&& NewEdge
);
217 NewEdge
->pNext
= NULL
;
218 *activehead
= NewEdge
;
222 ** First lets check to see if we have a new smallest value.
224 if (FILL_EDGE_Compare(NewEdge
, *activehead
) <= 0)
226 NewEdge
->pNext
= *activehead
;
227 *activehead
= NewEdge
;
231 ** Ok, now scan to the next spot to put this item.
235 while ( pThis
&& FILL_EDGE_Compare(pThis
, NewEdge
) < 0 )
238 pThis
= pThis
->pNext
;
242 NewEdge
->pNext
= pPrev
->pNext
;
243 pPrev
->pNext
= NewEdge
;
244 //DEBUG_PRINT_ACTIVE_EDGELIST(*activehead);
248 ** Create a list of edges for a list of points.
253 POLYGONFILL_MakeEdgeList(PPOINT Points
, int Count
)
256 FILL_EDGE_LIST
* list
= 0;
259 if ( 0 == Points
|| 2 > Count
)
262 list
= (FILL_EDGE_LIST
*)EngAllocMem(FL_ZERO_MEMORY
, sizeof(FILL_EDGE_LIST
), FILL_EDGE_ALLOC_TAG
);
266 list
->Edges
= (FILL_EDGE
**)EngAllocMem(FL_ZERO_MEMORY
, Count
*sizeof(FILL_EDGE
*), FILL_EDGE_ALLOC_TAG
);
270 memset ( list
->Edges
, 0, Count
* sizeof(FILL_EDGE
*) );
272 for ( CurPt
= 1; CurPt
< Count
; ++CurPt
)
274 e
= POLYGONFILL_MakeEdge ( Points
[CurPt
-1], Points
[CurPt
] );
278 // if a straight horizontal line - who cares?
282 list
->Edges
[list
->Count
++] = e
;
284 e
= POLYGONFILL_MakeEdge ( Points
[CurPt
-1], Points
[0] );
291 list
->Edges
[list
->Count
++] = e
;
296 DPRINT1("Out Of MEMORY!!\n");
297 POLYGONFILL_DestroyEdgeList ( list
);
303 ** This slow routine uses the data stored in the edge list to
304 ** calculate the x intercepts for each line in the edge list
305 ** for scanline Scanline.
306 **TODO: Get rid of this floating point arithmetic
311 POLYGONFILL_UpdateScanline(FILL_EDGE
* pEdge
, int Scanline
)
313 if ( 0 == pEdge
->dy
)
316 ASSERT ( pEdge
->FromY
<= Scanline
&& pEdge
->ToY
> Scanline
);
322 ASSERT ( pEdge
->y
== Scanline
);
324 // now shoot to end of scanline collision
325 steps
= (pEdge
->ErrorMax
-pEdge
->Error
-1)/pEdge
->absdy
;
328 // record first collision with scanline
330 pEdge
->x
+= steps
* pEdge
->XDirection
;
331 pEdge
->Error
+= steps
* pEdge
->absdy
;
332 ASSERT ( pEdge
->Error
< pEdge
->ErrorMax
);
333 pEdge
->XIntercept
[0] = min(x1
,pEdge
->x
);
334 pEdge
->XIntercept
[1] = max(x1
,pEdge
->x
);
338 pEdge
->XIntercept
[0] = pEdge
->x
;
339 pEdge
->XIntercept
[1] = pEdge
->x
;
342 // we should require exactly 1 step to step onto next scanline...
343 ASSERT ( (pEdge
->ErrorMax
-pEdge
->Error
-1) / pEdge
->absdy
== 0 );
344 pEdge
->x
+= pEdge
->XDirection
;
345 pEdge
->Error
+= pEdge
->absdy
;
346 ASSERT ( pEdge
->Error
>= pEdge
->ErrorMax
);
348 // now step onto next scanline...
349 pEdge
->Error
-= pEdge
->absdx
;
352 else // then this is a y-major line
354 pEdge
->XIntercept
[0] = pEdge
->x
;
355 pEdge
->XIntercept
[1] = pEdge
->x
;
357 pEdge
->Error
+= pEdge
->absdx
;
360 if ( pEdge
->Error
>= pEdge
->ErrorMax
)
362 pEdge
->Error
-= pEdge
->ErrorMax
;
363 pEdge
->x
+= pEdge
->XDirection
;
364 ASSERT ( pEdge
->Error
< pEdge
->ErrorMax
);
368 //DPRINT("Line (%d, %d) to (%d, %d) intersects scanline %d at (%d,%d)\n",
369 // pEdge->FromX, pEdge->FromY, pEdge->ToX, pEdge->ToY, Scanline, pEdge->XIntercept[0], pEdge->XIntercept[1] );
373 ** This method updates the Active edge collection for the scanline Scanline.
378 POLYGONFILL_BuildActiveList ( int Scanline
, FILL_EDGE_LIST
* list
, FILL_EDGE
** ActiveHead
)
382 ASSERT ( list
&& ActiveHead
);
384 for ( i
= 0; i
< list
->Count
; i
++ )
386 FILL_EDGE
* pEdge
= list
->Edges
[i
];
388 if ( pEdge
->FromY
<= Scanline
&& pEdge
->ToY
> Scanline
)
390 POLYGONFILL_UpdateScanline ( pEdge
, Scanline
);
391 POLYGONFILL_ActiveListInsert ( ActiveHead
, pEdge
);
397 ** This method fills the portion of the polygon that intersects with the scanline
403 POLYGONFILL_FillScanLineAlternate(
406 FILL_EDGE
* ActiveHead
,
411 FILL_EDGE
*pLeft
, *pRight
;
417 pRight
= pLeft
->pNext
;
420 while ( NULL
!= pRight
)
422 int x1
= pLeft
->XIntercept
[0];
423 int x2
= pRight
->XIntercept
[1];
427 BoundRect
.top
= ScanLine
;
428 BoundRect
.bottom
= ScanLine
+ 1;
430 BoundRect
.right
= x2
;
432 //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
433 IntEngLineTo(&psurf
->SurfObj
,
434 dc
->rosdc
.CombinedClip
,
440 &BoundRect
, // Bounding rectangle
443 pLeft
= pRight
->pNext
;
444 pRight
= pLeft
? pLeft
->pNext
: NULL
;
451 POLYGONFILL_FillScanLineWinding(
454 FILL_EDGE
* ActiveHead
,
459 FILL_EDGE
*pLeft
, *pRight
;
460 int x1
, x2
, winding
= 0;
466 BoundRect
.top
= ScanLine
;
467 BoundRect
.bottom
= ScanLine
+ 1;
470 winding
= pLeft
->YDirection
;
471 pRight
= pLeft
->pNext
;
474 // setup first line...
475 x1
= pLeft
->XIntercept
[0];
476 x2
= pRight
->XIntercept
[1];
479 pRight
= pLeft
->pNext
;
480 winding
+= pLeft
->YDirection
;
482 while ( NULL
!= pRight
)
484 int newx1
= pLeft
->XIntercept
[0];
485 int newx2
= pRight
->XIntercept
[1];
488 // check and see if this new line touches the previous...
489 if ( (newx1
>= x1
&& newx1
<= x2
)
490 || (newx2
>= x1
&& newx2
<= x2
)
491 || (x1
>= newx1
&& x1
<= newx2
)
492 || (x2
>= newx2
&& x2
<= newx2
)
495 // yup, just tack it on to our existing line
501 // nope - render the old line..
503 BoundRect
.right
= x2
;
505 //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
506 IntEngLineTo(&psurf
->SurfObj
,
507 dc
->rosdc
.CombinedClip
,
513 &BoundRect
, // Bounding rectangle
521 pRight
= pLeft
->pNext
;
522 winding
+= pLeft
->YDirection
;
524 // there will always be a line left-over, render it now...
526 BoundRect
.right
= x2
;
528 //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
529 IntEngLineTo(&psurf
->SurfObj
,
530 dc
->rosdc
.CombinedClip
,
536 &BoundRect
, // Bounding rectangle
540 //When the fill mode is ALTERNATE, GDI fills the area between odd-numbered and
541 //even-numbered polygon sides on each scan line. That is, GDI fills the area between the
542 //first and second side, between the third and fourth side, and so on.
544 //WINDING Selects winding mode (fills any region with a nonzero winding value).
545 //When the fill mode is WINDING, GDI fills any region that has a nonzero winding value.
546 //This value is defined as the number of times a pen used to draw the polygon would go around the region.
547 //The direction of each edge of the polygon is important.
560 FILL_EDGE_LIST
*list
= 0;
561 FILL_EDGE
*ActiveHead
= 0;
563 PDC_ATTR pdcattr
= dc
->pdcattr
;
565 (APIENTRY
*FillScanLine
)(
568 FILL_EDGE
* ActiveHead
,
573 //DPRINT("FillPolygon\n");
575 /* Create Edge List. */
576 list
= POLYGONFILL_MakeEdgeList(Points
, Count
);
577 /* DEBUG_PRINT_EDGELIST(list); */
581 if ( WINDING
== pdcattr
->jFillMode
)
582 FillScanLine
= POLYGONFILL_FillScanLineWinding
;
584 FillScanLine
= POLYGONFILL_FillScanLineAlternate
;
586 /* For each Scanline from BoundRect.bottom to BoundRect.top,
587 * determine line segments to draw
589 for ( ScanLine
= BoundRect
.top
; ScanLine
< BoundRect
.bottom
; ++ScanLine
)
591 POLYGONFILL_BuildActiveList(ScanLine
, list
, &ActiveHead
);
592 //DEBUG_PRINT_ACTIVE_EDGELIST(ActiveHead);
593 FillScanLine ( dc
, ScanLine
, ActiveHead
, psurf
, BrushObj
, RopMode
);
596 /* Free Edge List. If any are left. */
597 POLYGONFILL_DestroyEdgeList(list
);
612 FILL_EDGE_LIST
*list
= 0;
613 FILL_EDGE
*ActiveHead
= 0;
614 FILL_EDGE
*pLeft
, *pRight
;
617 //DPRINT("IntFillPolygon\n");
619 /* Create Edge List. */
620 list
= POLYGONFILL_MakeEdgeList(Points
, Count
);
621 /* DEBUG_PRINT_EDGELIST(list); */
625 /* For each Scanline from DestRect.top to DestRect.bottom, determine line segments to draw */
626 for ( ScanLine
= DestRect
.top
; ScanLine
< DestRect
.bottom
; ++ScanLine
)
628 POLYGONFILL_BuildActiveList(ScanLine
, list
, &ActiveHead
);
629 //DEBUG_PRINT_ACTIVE_EDGELIST(ActiveHead);
635 pRight
= pLeft
->pNext
;
638 while ( NULL
!= pRight
)
640 int x1
= pLeft
->XIntercept
[0];
641 int x2
= pRight
->XIntercept
[1];
645 LineRect
.top
= ScanLine
;
646 LineRect
.bottom
= ScanLine
+ 1;
650 IntEngBitBlt(&psurf
->SurfObj
,
653 dc
->rosdc
.CombinedClip
,
660 ROP4_FROM_INDEX(R3_OPINDEX_PATCOPY
));
662 pLeft
= pRight
->pNext
;
663 pRight
= pLeft
? pLeft
->pNext
: NULL
;
667 /* Free Edge List. If any are left. */
668 POLYGONFILL_DestroyEdgeList(list
);