Added more controller IDs.
[AROS.git] / rom / graphics / areafill.c
blob0ad8b3a2b25a1f83bdd33abfae8a17516a3a505c
1 /*
2 Copyright © 1995-2001, The AROS Development Team. All rights reserved.
3 $Id$
5 Desc: Area support functions
6 Lang: english
7 */
9 #include <proto/alib.h>
10 #include <exec/types.h>
11 #include <exec/memory.h>
12 #include <proto/graphics.h>
13 #include <proto/exec.h>
14 #include <graphics/rastport.h>
15 #include <graphics/gfx.h>
16 #include <graphics/gfxbase.h>
17 #include <string.h>
18 #include <stdlib.h>
20 #include <aros/debug.h>
22 #include "graphics_intern.h"
25 The algorithm was taken from:
26 Computer Graphics
27 A programming approach, 2n edition
28 Steven Harrington
29 Xerox Corp.
31 pages 79-91.
34 The algorithm that follows the borderlines has to go hand in hand
35 with the algorithm that draws the line, such that no parts are
36 filled that aren't supposed to be filled.
39 void LineInTmpRas(struct RastPort * rp,
40 struct Rectangle * bounds,
41 UWORD BytesPerRow,
42 UWORD xleft,
43 UWORD xright,
44 UWORD y,
45 struct GfxBase * GfxBase);
48 struct BoundLine
50 UWORD StartIndex;
51 UWORD EndIndex;
52 UWORD LeftX;
53 UWORD RightX;
54 WORD DeltaX;
55 WORD DeltaY;
56 WORD Count;
57 BOOL Valid;
58 WORD incrE;
59 WORD incrNE;
60 WORD s1;
61 WORD t;
62 WORD horiz;
63 WORD NLeftX;
64 WORD NRightX;
67 UWORD Include (UWORD lastused,
68 UWORD lastindex,
69 struct BoundLine * AreaBound,
70 UWORD scan,
71 UWORD * VctTbl)
73 while (lastused < lastindex &&
74 VctTbl[AreaBound[lastused+1].StartIndex+1] == scan)
77 kprintf("including new one! ");
78 kprintf("(%d,%d)-(%d,%d)\n",VctTbl[AreaBound[lastused+1].StartIndex],
79 VctTbl[AreaBound[lastused+1].StartIndex+1],
80 VctTbl[AreaBound[lastused+1].EndIndex],
81 VctTbl[AreaBound[lastused+1].EndIndex]);
83 lastused++;
85 return lastused;
88 void FillScan(UWORD StartIndex,
89 UWORD EndIndex,
90 struct BoundLine * AreaBound,
91 UWORD scanline,
92 struct RastPort * rp,
93 struct Rectangle * bounds,
94 UWORD BytesPerRow,
95 struct GfxBase * GfxBase)
97 int i = StartIndex;
98 int x1;
99 while (i < EndIndex)
101 /* simply draw a line */
102 while (!AreaBound[i].Valid)
104 i++;
105 if (i > EndIndex) return;
107 x1=AreaBound[i].RightX+1;
109 while (!AreaBound[i+1].Valid)
111 i++;
112 if (i > EndIndex) return;
115 if (x1 <= AreaBound[i+1].LeftX-1)
117 LineInTmpRas(rp,
118 bounds,
119 BytesPerRow,
121 AreaBound[i+1].LeftX-1,
122 scanline,
123 GfxBase);
126 i+=2;
131 void XSort(UWORD StartIndex,
132 UWORD EndIndex,
133 struct BoundLine * AreaBound)
135 /* a simple bubble sort */
136 struct BoundLine tmpAreaBound;
137 int i = StartIndex+1;
139 //kprintf("%d,%d\n",StartIndex,EndIndex);
141 //kprintf("%d ",AreaBound[StartIndex].LeftX);
143 while (i <= EndIndex)
145 if (AreaBound[i].LeftX < AreaBound[i-1].LeftX)
147 /* The one at index i needs to go more to smaller indices */
148 int i2 = i;
149 //kprintf("sorting!!\n");
150 tmpAreaBound = AreaBound[i];
151 while (TRUE)
153 AreaBound[i2] = AreaBound[i2-1];
154 i2--;
155 if (i2 == StartIndex ||
156 AreaBound[i2-1].LeftX <= tmpAreaBound.LeftX )
158 AreaBound[i2] = tmpAreaBound;
159 break;
163 i++;
164 //kprintf("%d ",AreaBound[i].LeftX);
167 //kprintf("\n");
171 UWORD UpdateXValues(UWORD StartIndex,
172 UWORD EndIndex,
173 UWORD scan,
174 struct BoundLine * AreaBound,
175 UWORD * VctTbl)
177 int i = StartIndex;
178 BOOL foundvalid = FALSE;
180 while (i <= EndIndex)
182 /* Test whether this one is still to be considered */
183 // CHANGED <= to <
184 if ( VctTbl[AreaBound[i].EndIndex+1] <= scan ||
185 !AreaBound[i].Valid )
188 if (!AreaBound[i].Valid)
189 kprintf ("already marked as invalid! ");
190 else
191 kprintf("marking %d as anvalid! ",i);
192 kprintf("(%d,%d)-(%d,%d)\n",VctTbl[AreaBound[i].StartIndex],
193 VctTbl[AreaBound[i].StartIndex+1],
194 VctTbl[AreaBound[i].EndIndex],
195 VctTbl[AreaBound[i].EndIndex+1]);
197 AreaBound[i].Valid = FALSE;
198 if (!foundvalid)
199 StartIndex += 1;
200 } else {
201 /* It is still to be considered!! */
202 foundvalid = TRUE;
203 /* calculate the new x-coordinates for the new line */
204 if (0 == AreaBound[i].DeltaX)
206 /* a vertical line !!! easy!! */
207 i++;
208 continue;
211 AreaBound[i].RightX += AreaBound[i].NRightX;
212 AreaBound[i].LeftX += AreaBound[i].NLeftX;
213 AreaBound[i].NRightX = 0;
214 AreaBound[i].NLeftX = 0;
216 * If we're moving more in the horizontal
217 * than in the vertical, then the line
218 * has a pure horizontal component which I
219 * must take care of by not painting over it.
220 * This means that on a y coordinate the line
221 * can go from the LeftX to the RightX.
223 if (1 == AreaBound[i].horiz) {
225 * More towards the horizontal than down
227 if (AreaBound[i].s1 > 0) {
228 AreaBound[i].LeftX = AreaBound[i].RightX;
229 } else {
230 AreaBound[i].RightX = AreaBound[i].LeftX;
235 while (1) {
236 if (AreaBound[i].Count <= 0) {
237 AreaBound[i].Count += AreaBound[i].incrE;
238 if (1 == AreaBound[i].t) {
239 if (AreaBound[i].s1 > 0) {
241 * Towards right
243 AreaBound[i].RightX++;
244 } else {
246 * Towards left
248 AreaBound[i].LeftX--;
250 } else {
252 * Going to next Y coordinate
254 break;
256 } else {
257 AreaBound[i].Count += AreaBound[i].incrNE;
259 * Going to next Y coordinate
261 if (AreaBound[i].s1 > 0) {
263 * Towards right
265 AreaBound[i].NRightX = 1;
266 } else {
268 * Towards left
270 AreaBound[i].NLeftX = -1;
272 break;
274 } /* while (1) */
277 * If we're going more vertical than horizontal
278 * then the left and right are always the same.
280 if (0 == AreaBound[i].horiz) {
281 if (AreaBound[i].s1 > 0) {
283 AreaBound[i].RightX += AreaBound[i].NRightX;
284 AreaBound[i].NRightX = 0;
286 AreaBound[i].LeftX = AreaBound[i].RightX;
287 } else {
289 AreaBound[i].LeftX += AreaBound[i].NLeftX;
290 AreaBound[i].NLeftX = 0;
292 AreaBound[i].RightX = AreaBound[i].LeftX;
296 i++;
299 return StartIndex;
302 /* functions for filling of the RastPort */
303 BOOL areafillpolygon(struct RastPort * rp,
304 struct Rectangle * bounds,
305 UWORD first_idx,
306 UWORD last_idx,
307 ULONG BytesPerRow,
308 struct GfxBase * GfxBase)
310 int i, c;
311 UWORD StartEdge = 1;
312 UWORD EndEdge = 1;
313 WORD LastIndex;
314 UWORD ymin;
315 UWORD LastEdge = last_idx - first_idx + 1; // needed later on. Don't change!!
316 struct AreaInfo * areainfo = rp->AreaInfo;
317 UWORD * StartVctTbl = &areainfo->VctrTbl[first_idx * 2];
318 UWORD scan;
319 struct BoundLine tmpAreaBound;
320 struct BoundLine * AreaBound =
321 (struct BoundLine *) AllocMem(sizeof(struct BoundLine) * LastEdge,
322 MEMF_CLEAR);
324 if (NULL == AreaBound)
325 return FALSE;
327 /* first clear the buffer of the temporary rastport as far as necessary */
329 memset(rp->TmpRas->RasPtr,
331 BytesPerRow * (bounds->MaxY - bounds->MinY + 1));
334 kprintf("first: %d, last: %d\n",first_idx,last_idx);
335 kprintf("(%d,%d)-(%d,%d)\n",bounds->MinX,bounds->MinY,
336 bounds->MaxX,bounds->MaxY);
337 kprintf("width: %d, bytesperrow: %d\n",bounds->MaxX - bounds->MinX + 1,
338 BytesPerRow);
340 /* I need a list of sorted indices that represent the lines of the
341 ** polygon. Horizontal lines don't go into that list!!!
342 ** The lines are sorted by their start-y coordinates.
345 i = -1;
346 c = 0;
348 /* process all points of the polygon */
349 while (c < (LastEdge-1)*2)
351 int i2;
352 /* is the next one starting point of a horizontal line??? If yes,
353 then skip it */
355 kprintf("current idx for y: %d, next idx for y: %d\n",c+1,c+3);
357 if (StartVctTbl[c+1] == StartVctTbl[c+3])
359 // kprintf("Found horizontal Line!!\n");
360 c+=2;
361 continue;
364 /* which coordinate of this line has the lower y value */
365 if (StartVctTbl[c+1] < StartVctTbl[c+3])
367 tmpAreaBound.StartIndex = c;
368 tmpAreaBound.EndIndex = c+2;
369 ymin = StartVctTbl[c+1];
371 else
373 tmpAreaBound.StartIndex = c+2;
374 tmpAreaBound.EndIndex = c;
375 ymin = StartVctTbl[c+3];
379 kprintf("line: (%d,%d)-(%d,%d) ",StartVctTbl[c],
380 StartVctTbl[c+1],
381 StartVctTbl[c+2],
382 StartVctTbl[c+3]);
383 kprintf("miny: %d\n",ymin);
385 i2 = 0;
387 ** search for the place where to put this entry into the sorted
388 ** (increasing start y-coordinates) list
390 if (i > -1)
392 while (TRUE)
395 kprintf("ymin: %d< %d?\n",ymin,StartVctTbl[AreaBound[i2].StartIndex+1]);
397 if (ymin < StartVctTbl[AreaBound[i2].StartIndex+1])
399 int i3 = i+1;
400 /* found the place! */
401 while (i3 > i2)
404 kprintf("moving!\n");
406 AreaBound[i3].StartIndex = AreaBound[i3-1].StartIndex;
407 AreaBound[i3].EndIndex = AreaBound[i3-1].EndIndex;
408 i3--;
410 AreaBound[i2].StartIndex = tmpAreaBound.StartIndex;
411 AreaBound[i2].EndIndex = tmpAreaBound.EndIndex;
412 break;
414 i2++;
415 if (i2 > i)
418 kprintf("at end!\n");
420 AreaBound[i+1].StartIndex = tmpAreaBound.StartIndex;
421 AreaBound[i+1].EndIndex = tmpAreaBound.EndIndex;
422 break;
426 else /* first one to insert into list */
428 AreaBound[0].StartIndex = tmpAreaBound.StartIndex;
429 AreaBound[0].EndIndex = tmpAreaBound.EndIndex;
431 c += 2;
432 i++;
435 LastIndex = i;
436 i = 0;
440 int i2 = 0;
441 while (i2 <= LastIndex)
443 kprintf("%d.: index %d (%d,%d)-(%d,%d)\n",i2,AreaBound[i2].StartIndex,
444 StartVctTbl[AreaBound[i2].StartIndex],
445 StartVctTbl[AreaBound[i2].StartIndex+1],
446 StartVctTbl[AreaBound[i2].EndIndex],
447 StartVctTbl[AreaBound[i2].EndIndex+1]);
448 i2++;
453 while (i <= LastIndex)
455 int StartIndex = AreaBound[i].StartIndex;
456 int EndIndex = AreaBound[i].EndIndex;
458 if ((StartVctTbl[EndIndex] - StartVctTbl[StartIndex]) > 0) {
459 AreaBound[i].s1 = 1;
460 } else {
461 AreaBound[i].s1 = -1;
464 AreaBound[i].DeltaX = abs(StartVctTbl[EndIndex] -
465 StartVctTbl[StartIndex]);
467 AreaBound[i].DeltaY = abs(StartVctTbl[EndIndex+1] -
468 StartVctTbl[StartIndex+1]);
470 if (AreaBound[i].DeltaX > AreaBound[i].DeltaY) {
471 AreaBound[i].horiz = 1;
475 if (AreaBound[i].DeltaX < AreaBound[i].DeltaY) {
476 WORD d = AreaBound[i].DeltaX;
477 AreaBound[i].DeltaX = AreaBound[i].DeltaY;
478 AreaBound[i].DeltaY = d;
479 AreaBound[i].t = 0;
480 } else {
481 AreaBound[i].t = 1;
484 AreaBound[i].Count = (AreaBound[i].DeltaY * 2) - AreaBound[i].DeltaX;
485 AreaBound[i].incrE = AreaBound[i].DeltaY * 2;
486 AreaBound[i].incrNE = (AreaBound[i].DeltaY - AreaBound[i].DeltaX) * 2;
488 AreaBound[i].LeftX = AreaBound[i].RightX = StartVctTbl[StartIndex];
489 AreaBound[i].Valid = TRUE;
490 i++;
493 /* indexlist now contains i+1 indices into the vector table.
494 Either the coordinate at the index as declared in the indexlist
495 contains the lower y value or the following coordinate */
497 scan = bounds->MinY;
499 LastIndex = i;
501 StartEdge = 0;
502 EndEdge = Include(1, LastIndex, AreaBound, scan, StartVctTbl);
503 StartEdge = UpdateXValues(StartEdge, EndEdge, scan, AreaBound, StartVctTbl);
505 while (scan < bounds->MaxY)
507 XSort(StartEdge, EndEdge, AreaBound);
509 if (scan > bounds->MinY)
510 FillScan(StartEdge,
511 EndEdge,
512 AreaBound,
513 scan,
514 rp,
515 bounds,
516 BytesPerRow,
517 GfxBase);
520 kprintf("scanline: %d StartEdge: %d, EndEdge: %d\n",scan,StartEdge,EndEdge);
523 int x = StartEdge;
524 while (x <= EndEdge)
526 if (AreaBound[x].Valid)
528 kprintf("(%d,%d)-(%d,%d) currently at: Left: %d Right: %d\n",
529 StartVctTbl[AreaBound[x].StartIndex],
530 StartVctTbl[AreaBound[x].StartIndex+1],
531 StartVctTbl[AreaBound[x].EndIndex],
532 StartVctTbl[AreaBound[x].EndIndex+1],
533 AreaBound[x].LeftX,
534 AreaBound[x].RightX);
536 else
537 kprintf("invalid\n");
538 x++;
542 scan++;
543 EndEdge = Include(EndEdge, LastIndex, AreaBound, scan, StartVctTbl);
544 StartEdge = UpdateXValues(StartEdge, EndEdge, scan, AreaBound, StartVctTbl);
546 kprintf("StartEdge: %d, EndEdge: %d\n",StartEdge,EndEdge);
550 FreeMem( AreaBound, sizeof(struct BoundLine) * LastEdge);
552 return TRUE;
556 void areafillellipse(struct RastPort * rp,
557 struct Rectangle * bounds,
558 UWORD * CurVctr,
559 ULONG BytesPerRow,
560 struct GfxBase * GfxBase)
562 /* the ellipse drawing algorithm is taken from DrawEllipse() */
563 LONG x = CurVctr[2], y = 0; /* ellipse points */
565 /* intermediate terms to speed up loop */
566 LONG t1 = CurVctr[2] * CurVctr[2], t2 = t1 << 1, t3 = t2 << 1;
567 LONG t4 = CurVctr[3] * CurVctr[3], t5 = t4 << 1, t6 = t5 << 1;
568 LONG t7 = CurVctr[2] * t5, t8 = t7 << 1, t9 = 0;
569 LONG d1 = t2 - t7 + (t4 >> 1); /* error terms */
570 LONG d2 = (t1 >> 1) - t8 + t5;
572 memset(rp->TmpRas->RasPtr,
573 0x00,
574 BytesPerRow * (bounds->MaxY - bounds->MinY + 1) );
576 kprintf("filled bytes: %d\n",BytesPerRow * (bounds->MaxY - bounds->MinY + 1));
578 kprintf("Filling ellipse with center at (%d,%d) and radius in x: %d and in y: %d\n",
579 CurVctr[0],CurVctr[1],CurVctr[2],CurVctr[3]);
581 while (d2 < 0 && y < CurVctr[3])
583 /* draw 2 lines using symmetry */
584 if (x > 1)
586 LineInTmpRas(rp,
587 bounds,
588 BytesPerRow,
589 CurVctr[0] - x + 1,
590 CurVctr[0] + x - 1,
591 CurVctr[1] - y,
592 GfxBase);
594 LineInTmpRas(rp,
595 bounds,
596 BytesPerRow,
597 CurVctr[0] - x + 1,
598 CurVctr[0] + x - 1,
599 CurVctr[1] + y,
600 GfxBase);
603 y++; /* always move up here */
604 t9 = t9 + t3;
605 if (d1 < 0) /* move straight up */
607 d1 = d1 + t9 + t2;
608 d2 = d2 + t9;
610 else
612 x--;
613 t8 = t8 - t6;
614 d1 = d1 + t9 + t2 - t8;
615 d2 = d2 + t9 + t5 - t8;
619 do /* rest of the right quadrant */
621 /* draw 2 lines using symmetry */
623 x--; /* always move left here */
624 t8 = t8 - t6;
625 if (d2 < 0) /* move up and left */
627 if (x > 1)
629 LineInTmpRas(rp,
630 bounds,
631 BytesPerRow,
632 CurVctr[0] - x + 1,
633 CurVctr[0] + x - 1,
634 CurVctr[1] - y,
635 GfxBase);
637 LineInTmpRas(rp,
638 bounds,
639 BytesPerRow,
640 CurVctr[0] - x + 1,
641 CurVctr[0] + x - 1,
642 CurVctr[1] + y,
643 GfxBase);
645 else
646 break;
648 y ++;
649 t9 = t9 + t3;
650 d2 = d2 + t9 + t5 - t8;
652 else /* move straight left */
654 d2 = d2 + t5 - t8;
656 } while ( x > 0 && y < CurVctr[3] );
660 ** Draw a horizontal line into a temporary rastport.
663 void LineInTmpRas(struct RastPort * rp,
664 struct Rectangle * bounds,
665 UWORD BytesPerRow,
666 UWORD xleft,
667 UWORD xright,
668 UWORD y,
669 struct GfxBase * GfxBase)
671 ULONG index;
672 UWORD NumPixels;
673 WORD PixelMask;
674 UWORD PixelMask2;
675 UWORD * RasPtr = (WORD *)rp->TmpRas->RasPtr;
676 ULONG shift;
678 //kprintf("(%d/%d) to (%d/%d)\n",xleft,y,xright,y);
680 /* adjust the coordinates */
681 xleft -= bounds->MinX;
682 xright -= bounds->MinX;
683 y -= bounds->MinY;
685 //kprintf("line from %d to %d y = %d\n",xleft,xright,y);
687 if (xleft > xright) return;
689 an algorithm that tries to minimize the number of accesses to the
690 RasPtr
693 /* Fill the first word */
694 PixelMask = 0x8000;
696 /* determine the number of pixels to set at the beginning */
697 NumPixels = xright - xleft + 1;
698 if (NumPixels > 16)
699 NumPixels = 16;
701 /* create enough pixels */
702 PixelMask >>= (NumPixels - 1);
704 index = (y * (BytesPerRow >> 1)) + (xleft >> 4);
705 /* Adjust the pixelmask so we hit the very first pixel */
706 PixelMask2 = PixelMask & 0xffff;
707 if (0 != (shift = (xleft & 0x0f))) {
708 PixelMask2 >>= shift;
711 #if (AROS_BIG_ENDIAN == 0)
712 /* Endianess conversion*/
713 PixelMask2 = PixelMask2 << 8 | PixelMask2 >> 8;
714 #endif
715 RasPtr[index] |= PixelMask2;
716 //kprintf("%x (left)\n",PixelMask2);
718 index++;
720 xleft = xleft + (16 - shift);
722 if ((xright - xleft) < 16)
723 goto fillright;
725 /* fill the middle with 0xffff's */
726 while ((xleft + 15) < xright)
728 RasPtr[index] = (WORD)0xffff;
729 index++;
730 xleft += 16;
733 fillright:
734 if (xleft <= xright)
736 PixelMask = 0x8000;
737 /* Create enough pixels - one pixel is already there! */
738 if (0 != (shift = (xright - xleft + 0))) {
739 PixelMask >>= shift;
742 PixelMask2 = PixelMask & 0xffff;
744 #if (AROS_BIG_ENDIAN == 0)
745 /* Endianess conversion*/
746 PixelMask2 = PixelMask2 << 8 | PixelMask2 >> 8;
747 #endif
749 RasPtr[index] |= PixelMask2;
750 //kprintf("%x (right)\n",PixelMask2);
756 void areaclosepolygon(struct AreaInfo *areainfo)
758 /* Note: the caller must make sure, that this
759 function is only called if areainfo->Count > 0
760 and that there is place for one vector
761 (areainfo->Count < areainfo->MaxCount) */
763 if ( areainfo->FlagPtr[-1] == AREAINFOFLAG_DRAW )
765 if ((areainfo->VctrPtr[-1] != areainfo->FirstY) ||
766 (areainfo->VctrPtr[-2] != areainfo->FirstX))
768 areainfo->Count++;
769 areainfo->VctrPtr[0] = areainfo->FirstX;
770 areainfo->VctrPtr[1] = areainfo->FirstY;
771 areainfo->FlagPtr[0] = AREAINFOFLAG_CLOSEDRAW;
773 areainfo->VctrPtr = &areainfo->VctrPtr[2];
774 areainfo->FlagPtr++;
776 else
778 areainfo->FlagPtr[-1] = AREAINFOFLAG_CLOSEDRAW;