1 /*
2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS Win32k subsystem
4 * PURPOSE: Various Polygon Filling routines for Polygon()
5 * FILE: win32ss/gdi/ntgdi/polyfill.c
6 * PROGRAMER: Mark Tempel
7 */
8
9 #include <win32k.h>
10
11 #define NDEBUG
12 #include <debug.h>
13
14 #define FILL_EDGE_ALLOC_TAG 0x45465044
15
16 /*
17 ** This struct is used for book keeping during polygon filling routines.
18 */
19 typedef struct _tagFILL_EDGE
20 {
21 /* Basic line information */
22 int FromX;
23 int FromY;
24 int ToX;
25 int ToY;
26 int dx;
27 int dy;
28 int absdx, absdy;
29 int x, y;
30 int xmajor;
31
32 /* Active Edge List information */
33 int XIntercept[2];
34 int Error;
35 int ErrorMax;
36 int XDirection, YDirection;
37
38 /* The next edge in the active Edge List */
39 struct _tagFILL_EDGE * pNext;
40 } FILL_EDGE;
41
42 typedef struct _FILL_EDGE_LIST
43 {
44 int Count;
45 FILL_EDGE** Edges;
46 } FILL_EDGE_LIST;
47
48 #if 0
49 static
50 void
51 DEBUG_PRINT_ACTIVE_EDGELIST ( FILL_EDGE* list )
52 {
53 FILL_EDGE* pThis = list;
54 if (0 == list)
55 {
56 DPRINT1("List is NULL\n");
57 return;
58 }
59
60 while(0 != pThis)
61 {
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] );
64 pThis = pThis->pNext;
65 }
66 }
67 #else
68 #define DEBUG_PRINT_ACTIVE_EDGELIST(x)
69 #endif
70
71 /*
72 ** Hide memory clean up.
73 */
74 static
75 void
76 FASTCALL
POLYGONFILL_DestroyEdgeList(FILL_EDGE_LIST * list)77 POLYGONFILL_DestroyEdgeList(FILL_EDGE_LIST* list)
78 {
79 int i;
80
81 if (list)
82 {
83 if (list->Edges)
84 {
85 for (i = 0; i < list->Count; i++)
86 {
87 _PRAGMA_WARNING_SUPPRESS(__WARNING_USING_UNINIT_VAR)
88 if (list->Edges[i])
89 EngFreeMem(list->Edges[i]);
90 }
91
92 EngFreeMem(list->Edges);
93 }
94
95 EngFreeMem(list);
96 }
97 }
98
99 /*
100 ** This makes and initializes an Edge struct for a line between two points.
101 */
102 static
103 FILL_EDGE*
104 FASTCALL
POLYGONFILL_MakeEdge(POINT From,POINT To)105 POLYGONFILL_MakeEdge(POINT From, POINT To)
106 {
107 FILL_EDGE* rc = (FILL_EDGE*)EngAllocMem(FL_ZERO_MEMORY, sizeof(FILL_EDGE), FILL_EDGE_ALLOC_TAG);
108
109 if (0 == rc)
110 return NULL;
111
112 //DPRINT1("Making Edge: (%d, %d) to (%d, %d)\n", From.x, From.y, To.x, To.y);
113 // Now fill the struct.
114 if ( To.y < From.y )
115 {
116 rc->FromX = To.x;
117 rc->FromY = To.y;
118 rc->ToX = From.x;
119 rc->ToY = From.y;
120 rc->YDirection = -1;
121
122 // Lines that go up get walked backwards, so need to be offset
123 // by -1 in order to make the walk identically on a pixel-level
124 rc->Error = -1;
125 }
126 else
127 {
128 rc->FromX = From.x;
129 rc->FromY = From.y;
130 rc->ToX = To.x;
131 rc->ToY = To.y;
132 rc->YDirection = 1;
133
134 rc->Error = 0;
135 }
136
137 rc->x = rc->FromX;
138 rc->y = rc->FromY;
139 rc->dx = rc->ToX - rc->FromX;
140 rc->dy = rc->ToY - rc->FromY;
141 rc->absdx = abs(rc->dx);
142 rc->absdy = abs(rc->dy);
143
144 rc->xmajor = rc->absdx > rc->absdy;
145
146 rc->ErrorMax = max(rc->absdx,rc->absdy);
147
148 rc->Error += rc->ErrorMax / 2;
149
150 rc->XDirection = (rc->dx < 0)?(-1):(1);
151
152 rc->pNext = 0;
153
154 //DPRINT("MakeEdge (%i,%i)->(%i,%i) d=(%i,%i) dir=(%i,%i) err=%i max=%i\n",
155 // From.x, From.y, To.x, To.y, rc->dx, rc->dy, rc->XDirection, rc->YDirection, rc->Error, rc->ErrorMax );
156
157 return rc;
158 }
159 /*
160 ** My Edge comparison routine.
161 ** This is for scan converting polygon fill.
162 ** First sort by MinY, then Minx, then slope.
163 **
164 ** This comparison will help us determine which
165 ** lines will become active first when scanning from
166 ** top (min y) to bottom (max y).
167 **
168 ** Return Value Meaning
169 ** Negative integer element1 < element2
170 ** Zero element1 = element2
171 ** Positive integer element1 > element2
172 */
173 static
174 INT
175 FASTCALL
FILL_EDGE_Compare(FILL_EDGE * Edge1,FILL_EDGE * Edge2)176 FILL_EDGE_Compare(FILL_EDGE* Edge1, FILL_EDGE* Edge2)
177 {
178 int e1 = Edge1->XIntercept[0] + Edge1->XIntercept[1];
179 int e2 = Edge2->XIntercept[0] + Edge2->XIntercept[1];
180
181 return e1 - e2;
182 }
183
184
185 /*
186 ** Insert an edge into a list keeping the list in order.
187 */
188 static
189 void
190 FASTCALL
POLYGONFILL_ActiveListInsert(FILL_EDGE ** activehead,FILL_EDGE * NewEdge)191 POLYGONFILL_ActiveListInsert(FILL_EDGE** activehead, FILL_EDGE* NewEdge )
192 {
193 FILL_EDGE *pPrev, *pThis;
194 //DPRINT1("In POLYGONFILL_ActiveListInsert()\n");
195 ASSERT(activehead && NewEdge);
196
197 if (!*activehead)
198 {
199 NewEdge->pNext = NULL;
200 *activehead = NewEdge;
201 return;
202 }
203 /*
204 ** First lets check to see if we have a new smallest value.
205 */
206 if (FILL_EDGE_Compare(NewEdge, *activehead) <= 0)
207 {
208 NewEdge->pNext = *activehead;
209 *activehead = NewEdge;
210 return;
211 }
212
213 /*
214 ** Ok, now scan to the next spot to put this item.
215 */
216 pThis = *activehead;
217 pPrev = NULL;
218 while ( pThis && FILL_EDGE_Compare(pThis, NewEdge) < 0 )
219 {
220 pPrev = pThis;
221 pThis = pThis->pNext;
222 }
223
224 ASSERT(pPrev);
225 NewEdge->pNext = pPrev->pNext;
226 pPrev->pNext = NewEdge;
227 //DEBUG_PRINT_ACTIVE_EDGELIST(*activehead);
228 }
229
230 /*
231 ** Create a list of edges for a list of points.
232 */
233 static
234 FILL_EDGE_LIST*
235 FASTCALL
POLYGONFILL_MakeEdgeList(PPOINT Points,int Count)236 POLYGONFILL_MakeEdgeList(PPOINT Points, int Count)
237 {
238 int CurPt = 0;
239 FILL_EDGE_LIST* list = 0;
240 FILL_EDGE* e = 0;
241
242 if (0 == Points || 2 > Count)
243 return 0;
244
245 list = (FILL_EDGE_LIST*)EngAllocMem(FL_ZERO_MEMORY, sizeof(FILL_EDGE_LIST), FILL_EDGE_ALLOC_TAG);
246 if ( 0 == list )
247 goto fail;
248 list->Count = 0;
249 list->Edges = (FILL_EDGE**)EngAllocMem(FL_ZERO_MEMORY, Count*sizeof(FILL_EDGE*), FILL_EDGE_ALLOC_TAG);
250 if ( !list->Edges )
251 goto fail;
252
253 memset(list->Edges, 0, Count * sizeof(FILL_EDGE*));
254
255 for (CurPt = 1; CurPt < Count; ++CurPt)
256 {
257 e = POLYGONFILL_MakeEdge ( Points[CurPt-1], Points[CurPt] );
258 if (!e)
259 goto fail;
260
261 // If a straight horizontal line - who cares?
262 if (!e->absdy)
263 EngFreeMem(e);
264 else
265 list->Edges[list->Count++] = e;
266 }
267 e = POLYGONFILL_MakeEdge ( Points[CurPt-1], Points[0] );
268 if ( !e )
269 goto fail;
270
271 if (!e->absdy)
272 EngFreeMem(e);
273 else
274 list->Edges[list->Count++] = e;
275 return list;
276
277 fail:
278
279 DPRINT1("Out Of MEMORY!!\n");
280 POLYGONFILL_DestroyEdgeList ( list );
281 return 0;
282 }
283
284
285 /*
286 ** This slow routine uses the data stored in the edge list to
287 ** calculate the x intercepts for each line in the edge list
288 ** for scanline Scanline.
289 **TODO: Get rid of this floating point arithmetic
290 */
291 static
292 void
293 FASTCALL
POLYGONFILL_UpdateScanline(FILL_EDGE * pEdge,int Scanline)294 POLYGONFILL_UpdateScanline(FILL_EDGE* pEdge, int Scanline)
295 {
296 if (0 == pEdge->dy)
297 return;
298
299 ASSERT(pEdge->FromY <= Scanline && pEdge->ToY > Scanline);
300
301 if (pEdge->xmajor)
302 {
303 int steps;
304
305 ASSERT(pEdge->y == Scanline);
306
307 // Now shoot to end of scanline collision
308 steps = (pEdge->ErrorMax-pEdge->Error-1)/pEdge->absdy;
309 if (steps)
310 {
311 // Record first collision with scanline
312 int x1 = pEdge->x;
313 pEdge->x += steps * pEdge->XDirection;
314 pEdge->Error += steps * pEdge->absdy;
315 ASSERT ( pEdge->Error < pEdge->ErrorMax );
316 pEdge->XIntercept[0] = min(x1,pEdge->x);
317 pEdge->XIntercept[1] = max(x1,pEdge->x);
318 }
319 else
320 {
321 pEdge->XIntercept[0] = pEdge->x;
322 pEdge->XIntercept[1] = pEdge->x;
323 }
324
325 // We should require exactly 1 step to step onto next scanline...
326 ASSERT((pEdge->ErrorMax-pEdge->Error-1) / pEdge->absdy == 0);
327 pEdge->x += pEdge->XDirection;
328 pEdge->Error += pEdge->absdy;
329 ASSERT(pEdge->Error >= pEdge->ErrorMax);
330
331 // Now step onto next scanline...
332 pEdge->Error -= pEdge->absdx;
333 pEdge->y++;
334 }
335 else // Then this is a y-major line
336 {
337 pEdge->XIntercept[0] = pEdge->x;
338 pEdge->XIntercept[1] = pEdge->x;
339
340 pEdge->Error += pEdge->absdx;
341 pEdge->y++;
342
343 if (pEdge->Error >= pEdge->ErrorMax)
344 {
345 pEdge->Error -= pEdge->ErrorMax;
346 pEdge->x += pEdge->XDirection;
347 ASSERT ( pEdge->Error < pEdge->ErrorMax );
348 }
349 }
350
351 //DPRINT("Line (%d, %d) to (%d, %d) intersects scanline %d at (%d,%d)\n",
352 // pEdge->FromX, pEdge->FromY, pEdge->ToX, pEdge->ToY, Scanline, pEdge->XIntercept[0], pEdge->XIntercept[1] );
353 }
354
355 /*
356 * This method updates the Active edge collection for the scanline Scanline.
357 */
358 static
359 void
360 APIENTRY
POLYGONFILL_BuildActiveList(int Scanline,FILL_EDGE_LIST * list,FILL_EDGE ** ActiveHead)361 POLYGONFILL_BuildActiveList(
362 int Scanline,
363 FILL_EDGE_LIST* list,
364 FILL_EDGE** ActiveHead)
365 {
366 int i;
367
368 ASSERT(list && ActiveHead);
369 *ActiveHead = 0;
370 for (i = 0; i < list->Count; i++)
371 {
372 FILL_EDGE* pEdge = list->Edges[i];
373 ASSERT(pEdge);
374 if (pEdge->FromY <= Scanline && pEdge->ToY > Scanline)
375 {
376 POLYGONFILL_UpdateScanline(pEdge, Scanline);
377 POLYGONFILL_ActiveListInsert(ActiveHead, pEdge);
378 }
379 }
380 }
381
382 /*
383 ** This method fills the portion of the polygon that intersects with the scanline
384 ** Scanline.
385 */
386 static
387 void
388 APIENTRY
POLYGONFILL_FillScanLineAlternate(PDC dc,int ScanLine,FILL_EDGE * ActiveHead,SURFACE * psurf,BRUSHOBJ * BrushObj,MIX RopMode)389 POLYGONFILL_FillScanLineAlternate(
390 PDC dc,
391 int ScanLine,
392 FILL_EDGE* ActiveHead,
393 SURFACE *psurf,
394 BRUSHOBJ *BrushObj,
395 MIX RopMode )
396 {
397 FILL_EDGE *pLeft, *pRight;
398
399 if (!ActiveHead)
400 return;
401
402 pLeft = ActiveHead;
403 pRight = pLeft->pNext;
404 ASSERT(pRight);
405
406 while (NULL != pRight)
407 {
408 int x1 = pLeft->XIntercept[0];
409 int x2 = pRight->XIntercept[1];
410 if (x2 > x1)
411 {
412 RECTL BoundRect;
413 BoundRect.top = ScanLine;
414 BoundRect.bottom = ScanLine + 1;
415 BoundRect.left = x1;
416 BoundRect.right = x2;
417
418 //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
419 IntEngLineTo(&psurf->SurfObj,
420 (CLIPOBJ *)&dc->co,
421 BrushObj,
422 x1,
423 ScanLine,
424 x2,
425 ScanLine,
426 &BoundRect, // Bounding rectangle
427 RopMode); // MIX
428 }
429 pLeft = pRight->pNext;
430 pRight = pLeft ? pLeft->pNext : NULL;
431 }
432 }
433
434 static
435 void
436 APIENTRY
POLYGONFILL_FillScanLineWinding(PDC dc,int ScanLine,FILL_EDGE * ActiveHead,SURFACE * psurf,BRUSHOBJ * BrushObj,MIX RopMode)437 POLYGONFILL_FillScanLineWinding(
438 PDC dc,
439 int ScanLine,
440 FILL_EDGE* ActiveHead,
441 SURFACE *psurf,
442 BRUSHOBJ *BrushObj,
443 MIX RopMode )
444 {
445 FILL_EDGE *pLeft, *pRight;
446 int x1, x2, winding = 0;
447 RECTL BoundRect;
448
449 if (!ActiveHead)
450 return;
451
452 BoundRect.top = ScanLine;
453 BoundRect.bottom = ScanLine + 1;
454
455 pLeft = ActiveHead;
456 winding = pLeft->YDirection;
457 pRight = pLeft->pNext;
458 ASSERT(pRight);
459
460 // Setup first line...
461 x1 = pLeft->XIntercept[0];
462 x2 = pRight->XIntercept[1];
463
464 pLeft = pRight;
465 pRight = pLeft->pNext;
466 winding += pLeft->YDirection;
467
468 while ( NULL != pRight )
469 {
470 int newx1 = pLeft->XIntercept[0];
471 int newx2 = pRight->XIntercept[1];
472 if ( winding )
473 {
474 // Check and see if this new line touches the previous...
475 if ((newx1 >= x1 && newx1 <= x2) ||
476 (newx2 >= x1 && newx2 <= x2) ||
477 (x1 >= newx1 && x1 <= newx2) ||
478 (x2 >= newx2 && x2 <= newx2))
479 {
480 // Yup, just tack it on to our existing line
481 x1 = min(x1,newx1);
482 x2 = max(x2,newx2);
483 }
484 else
485 {
486 // Nope - render the old line..
487 BoundRect.left = x1;
488 BoundRect.right = x2;
489
490 //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
491 IntEngLineTo(&psurf->SurfObj,
492 (CLIPOBJ *)&dc->co,
493 BrushObj,
494 x1,
495 ScanLine,
496 x2,
497 ScanLine,
498 &BoundRect, // Bounding rectangle
499 RopMode); // MIX
500
501 x1 = newx1;
502 x2 = newx2;
503 }
504 }
505
506 pLeft = pRight;
507 pRight = pLeft->pNext;
508 winding += pLeft->YDirection;
509 }
510
511 // There will always be a line left-over, render it now...
512 BoundRect.left = x1;
513 BoundRect.right = x2;
514
515 //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
516 IntEngLineTo(&psurf->SurfObj,
517 (CLIPOBJ *)&dc->co,
518 BrushObj,
519 x1,
520 ScanLine,
521 x2,
522 ScanLine,
523 &BoundRect, // Bounding rectangle
524 RopMode); // MIX
525 }
526
527 // When the fill mode is ALTERNATE, GDI fills the area between odd-numbered and
528 // even-numbered polygon sides on each scan line. That is, GDI fills the area between the
529 // first and second side, between the third and fourth side, and so on.
530
531 // WINDING Selects winding mode (fills any region with a nonzero winding value).
532 // When the fill mode is WINDING, GDI fills any region that has a nonzero winding value.
533 // This value is defined as the number of times a pen used to draw the polygon would go around the region.
534 // The direction of each edge of the polygon is important.
535
536 BOOL
537 APIENTRY
FillPolygon(PDC dc,SURFACE * psurf,BRUSHOBJ * BrushObj,MIX RopMode,CONST PPOINT Points,int Count,RECTL BoundRect)538 FillPolygon(
539 PDC dc,
540 SURFACE *psurf,
541 BRUSHOBJ *BrushObj,
542 MIX RopMode,
543 CONST PPOINT Points,
544 int Count,
545 RECTL BoundRect )
546 {
547 FILL_EDGE_LIST *list = 0;
548 FILL_EDGE *ActiveHead = 0;
549 int ScanLine;
550 PDC_ATTR pdcattr = dc->pdcattr;
551 void
552 (APIENTRY *FillScanLine)(
553 PDC dc,
554 int ScanLine,
555 FILL_EDGE* ActiveHead,
556 SURFACE *psurf,
557 BRUSHOBJ *BrushObj,
558 MIX RopMode);
559
560 //DPRINT("FillPolygon\n");
561
562 /* Create Edge List. */
563 list = POLYGONFILL_MakeEdgeList(Points, Count);
564 /* DEBUG_PRINT_EDGELIST(list); */
565 if (NULL == list)
566 return FALSE;
567
568 if (WINDING == pdcattr->jFillMode)
569 FillScanLine = POLYGONFILL_FillScanLineWinding;
570 else /* Default */
571 FillScanLine = POLYGONFILL_FillScanLineAlternate;
572
573 /* For each Scanline from BoundRect.bottom to BoundRect.top,
574 * determine line segments to draw
575 */
576 for (ScanLine = BoundRect.top; ScanLine < BoundRect.bottom; ++ScanLine)
577 {
578 POLYGONFILL_BuildActiveList(ScanLine, list, &ActiveHead);
579 //DEBUG_PRINT_ACTIVE_EDGELIST(ActiveHead);
580 FillScanLine(dc, ScanLine, ActiveHead, psurf, BrushObj, RopMode);
581 }
582
583 /* Free Edge List. If any are left. */
584 POLYGONFILL_DestroyEdgeList(list);
585
586 return TRUE;
587 }
588
589 BOOL FASTCALL
IntFillPolygon(PDC dc,SURFACE * psurf,BRUSHOBJ * BrushObj,CONST PPOINT Points,int Count,RECTL DestRect,POINTL * BrushOrigin)590 IntFillPolygon(
591 PDC dc,
592 SURFACE *psurf,
593 BRUSHOBJ *BrushObj,
594 CONST PPOINT Points,
595 int Count,
596 RECTL DestRect,
597 POINTL *BrushOrigin)
598 {
599 FILL_EDGE_LIST *list = 0;
600 FILL_EDGE *ActiveHead = 0;
601 FILL_EDGE *pLeft, *pRight;
602 int ScanLine;
603
604 //DPRINT("IntFillPolygon\n");
605
606 /* Create Edge List. */
607 list = POLYGONFILL_MakeEdgeList(Points, Count);
608 /* DEBUG_PRINT_EDGELIST(list); */
609 if (NULL == list)
610 return FALSE;
611
612 /* For each Scanline from DestRect.top to DestRect.bottom, determine line segments to draw */
613 for (ScanLine = DestRect.top; ScanLine < DestRect.bottom; ++ScanLine)
614 {
615 POLYGONFILL_BuildActiveList(ScanLine, list, &ActiveHead);
616 //DEBUG_PRINT_ACTIVE_EDGELIST(ActiveHead);
617
618 if (!ActiveHead)
619 {
620 POLYGONFILL_DestroyEdgeList(list);
621 return FALSE;
622 }
623
624 pLeft = ActiveHead;
625 pRight = pLeft->pNext;
626 ASSERT(pRight);
627
628 while (NULL != pRight)
629 {
630 int x1 = pLeft->XIntercept[0];
631 int x2 = pRight->XIntercept[1];
632
633 if (x2 > x1)
634 {
635 RECTL LineRect;
636 LineRect.top = ScanLine;
637 LineRect.bottom = ScanLine + 1;
638 LineRect.left = x1;
639 LineRect.right = x2;
640
641 IntEngBitBlt(&psurf->SurfObj,
642 NULL,
643 NULL,
644 (CLIPOBJ *)&dc->co,
645 NULL,
646 &LineRect,
647 NULL,
648 NULL,
649 BrushObj,
650 BrushOrigin,
651 ROP4_FROM_INDEX(R3_OPINDEX_PATCOPY));
652 }
653
654 pLeft = pRight->pNext;
655 pRight = pLeft ? pLeft->pNext : NULL;
656 }
657 }
658
659 /* Free Edge List. If any are left. */
660 POLYGONFILL_DestroyEdgeList(list);
661
662 return TRUE;
663 }
664
665 /* EOF */
666