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