test/areatest2_fillpoly.h

   1 #define georgchanges 1
   2
   3 #define X_FRACTION 2
   4
   5 static void mul_xcoords(void)
   6 {
   7     WORD i;
   8
   9     for(i = 0; i<= numpoints; i++)
  10     {
  11         points[i][0] *= X_FRACTION;
  12     }
  13 }
  14
  15 static void div_xcoords(void)
  16 {
  17     WORD i;
  18
  19     for(i = 0; i<= numpoints; i++)
  20     {
  21         points[i][0] /= X_FRACTION;
  22     }
  23 }
  24
  25 void LineInTmpRas(struct RastPort  * rp,
  26                   struct Rectangle * bounds,
  27                   UWORD              BytesPerRow,
  28                   UWORD              xleft,
  29                   UWORD              xright,
  30                   UWORD              y,
  31                   struct GfxBase   * GfxBase);
  32
  33
  34 struct BoundLine
  35 {
  36   UWORD StartIndex;
  37   UWORD EndIndex;
  38   UWORD LeftX;
  39   UWORD RightX;
  40    WORD DeltaX;
  41    WORD DeltaY;
  42    WORD Count;
  43    BOOL Valid;
  44    WORD incrE;
  45    WORD incrNE;
  46    WORD s1;
  47    WORD t;
  48    WORD horiz;
  49    WORD NLeftX;
  50    WORD NRightX;
  51 };
  52
  53 UWORD Include (UWORD lastused,
  54                UWORD lastindex,
  55                struct BoundLine * AreaBound,
  56                UWORD scan,
  57                UWORD * VctTbl)
  58 {
  59   while (lastused < lastindex &&
  60          VctTbl[AreaBound[lastused+1].StartIndex+1] == scan)
  61   {
  62 /*
  63     kprintf("including new one! ");
  64     kprintf("(%d,%d)-(%d,%d)\n",VctTbl[AreaBound[lastused+1].StartIndex],
  65                                 VctTbl[AreaBound[lastused+1].StartIndex+1],
  66                                 VctTbl[AreaBound[lastused+1].EndIndex],
  67                                 VctTbl[AreaBound[lastused+1].EndIndex]);
  68 */
  69     lastused++;
  70   }
  71   return lastused;
  72 }
  73
  74 void FillScan(UWORD StartIndex,
  75               UWORD EndIndex,
  76               struct BoundLine * AreaBound,
  77               UWORD scanline,
  78               struct RastPort * rp,
  79               struct Rectangle * bounds,
  80               UWORD BytesPerRow,
  81               struct GfxBase * GfxBase)
  82 {
  83   int i = StartIndex;
  84   int x1;
  85   while (i < EndIndex)
  86   {
  87     /* simply draw a line */
  88       while (FALSE == AreaBound[i].Valid)
  89       {
  90         i++;
  91         if (i > EndIndex) return;
  92       }
  93 #if georgchanges
  94       x1=(AreaBound[i].RightX + X_FRACTION / 2) / X_FRACTION;
  95 #else
  96       x1=AreaBound[i].RightX+1;
  97 #endif
  98
  99       while (FALSE == AreaBound[i+1].Valid)
 100       {
 101         i++;
 102         if (i > EndIndex) return;
 103       }
 104
 105       if (x1 <= AreaBound[i+1].LeftX-1)
 106       {
 107         LineInTmpRas(rp,
 108                      bounds,
 109                      BytesPerRow,
 110                      x1,
 111 #if georgchanges
 112                      AreaBound[i+1].LeftX / X_FRACTION,
 113 #else
 114                      AreaBound[i+1].LeftX-1,
 115 #endif
 116                      scanline,
 117                      GfxBase);
 118       }
 119
 120     i+=2;
 121   }
 122 }
 123
 124
 125 void XSort(UWORD StartIndex,
 126            UWORD EndIndex,
 127            struct BoundLine * AreaBound)
 128 {
 129   /* a simple bubble sort */
 130   struct BoundLine tmpAreaBound;
 131   int i = StartIndex+1;
 132
 133   //kprintf("%d,%d\n",StartIndex,EndIndex);
 134
 135 //kprintf("%d  ",AreaBound[StartIndex].LeftX);
 136
 137   while (i <= EndIndex)
 138   {
 139     if (AreaBound[i].LeftX < AreaBound[i-1].LeftX)
 140     {
 141       /* The one at index i needs to go more to smaller indices */
 142       int i2 = i;
 143       //kprintf("sorting!!\n");
 144       tmpAreaBound = AreaBound[i];
 145       while (TRUE)
 146       {
 147         AreaBound[i2] = AreaBound[i2-1];
 148         i2--;
 149         if (i2 == StartIndex ||
 150             AreaBound[i2-1].LeftX <= tmpAreaBound.LeftX )
 151         {
 152           AreaBound[i2] = tmpAreaBound;
 153           break;
 154         }
 155       }
 156     }
 157     i++;
 158     //kprintf("%d  ",AreaBound[i].LeftX);
 159
 160   }
 161   //kprintf("\n");
 162 }
 163
 164
 165 UWORD UpdateXValues(UWORD StartIndex,
 166                     UWORD EndIndex,
 167                     UWORD scan,
 168                     struct BoundLine * AreaBound,
 169                     UWORD * VctTbl)
 170 {
 171   int i = StartIndex;
 172   BOOL foundvalid = FALSE;
 173
 174   while (i <= EndIndex)
 175   {
 176     /* Test whether this one is still to be considered */
 177     // CHANGED <= to <
 178     if ( VctTbl[AreaBound[i].EndIndex+1] <=  scan ||
 179          AreaBound[i].Valid == FALSE )
 180     {
 181 /*
 182 if (AreaBound[i].Valid == FALSE)
 183   kprintf ("already marked as invalid! ");
 184 else
 185   kprintf("marking %d as anvalid! ",i);
 186 kprintf("(%d,%d)-(%d,%d)\n",VctTbl[AreaBound[i].StartIndex],
 187                             VctTbl[AreaBound[i].StartIndex+1],
 188                             VctTbl[AreaBound[i].EndIndex],
 189                             VctTbl[AreaBound[i].EndIndex+1]);
 190 */
 191       AreaBound[i].Valid = FALSE;
 192       if (FALSE == foundvalid)
 193         StartIndex += 1;
 194     } else {
 195       /* It is still to be considered!! */
 196       foundvalid = TRUE;
 197       /* calculate the new x-coordinates for the new line */
 198       if (0 == AreaBound[i].DeltaX)
 199       {
 200         /* a vertical line !!! easy!! */
 201         i++;
 202         continue;
 203       }
 204
 205       AreaBound[i].RightX += AreaBound[i].NRightX;
 206       AreaBound[i].LeftX  += AreaBound[i].NLeftX;
 207       AreaBound[i].NRightX = 0;
 208       AreaBound[i].NLeftX  = 0;
 209       /*
 210        * If we're moving more in the horizontal
 211        * than in the vertical, then the line
 212        * has a pure horizontal component which I
 213        * must take care of by not painting over it.
 214        * This means that on a y coordinate the line
 215        * can go from the LeftX to the RightX.
 216        */
 217       if (1 == AreaBound[i].horiz) {
 218         /*
 219          * More towards the horizontal than down
 220          */
 221         if (AreaBound[i].s1 > 0) {
 222           AreaBound[i].LeftX  = AreaBound[i].RightX;
 223         } else {
 224           AreaBound[i].RightX = AreaBound[i].LeftX;
 225         }
 226       }
 227
 228
 229       while (1) {
 230         if (AreaBound[i].Count <= 0) {
 231           AreaBound[i].Count += AreaBound[i].incrE;
 232           if (1 == AreaBound[i].t) {
 233             if (AreaBound[i].s1 > 0) {
 234               /*
 235                * Towards right
 236                */
 237               AreaBound[i].RightX++;
 238             } else {
 239               /*
 240                * Towards left
 241                */
 242               AreaBound[i].LeftX--;
 243             }
 244           } else {
 245             /*
 246              * Going to next Y coordinate
 247              */
 248             break;
 249           }
 250         } else {
 251           AreaBound[i].Count += AreaBound[i].incrNE;
 252           /*
 253            * Going to next Y coordinate
 254            */
 255           if (AreaBound[i].s1 > 0) {
 256             /*
 257              * Towards right
 258              */
 259             AreaBound[i].NRightX = 1;
 260           } else {
 261             /*
 262              * Towards left
 263              */
 264             AreaBound[i].NLeftX = -1;
 265           }
 266           break;
 267         }
 268       } /* while (1) */
 269
 270       /*
 271        * If we're going more vertical than horizontal
 272        * then the left and right are always the same.
 273        */
 274       if (0 == AreaBound[i].horiz) {
 275         if (AreaBound[i].s1 > 0) {
 276         /*
 277           AreaBound[i].RightX += AreaBound[i].NRightX;
 278           AreaBound[i].NRightX = 0;
 279          */
 280           AreaBound[i].LeftX  = AreaBound[i].RightX;
 281         } else {
 282         /*
 283           AreaBound[i].LeftX += AreaBound[i].NLeftX;
 284           AreaBound[i].NLeftX = 0;
 285          */
 286           AreaBound[i].RightX = AreaBound[i].LeftX;
 287         }
 288       }
 289     }
 290     i++;
 291   }
 292
 293   return StartIndex;
 294 }
 295
 296 /* functions for filling of the RastPort */
 297 BOOL areafillpolygon(struct RastPort  * rp,
 298                      struct Rectangle * bounds,
 299                      UWORD              first_idx,
 300                      UWORD              last_idx,
 301                      ULONG              BytesPerRow,
 302                      struct GfxBase *   GfxBase)
 303 {
 304   int i, c;
 305   UWORD StartEdge = 1;
 306   UWORD EndEdge = 1;
 307   WORD LastIndex;
 308   UWORD ymin;
 309   UWORD LastEdge = last_idx - first_idx + 1; // needed later on. Don't change!!
 310 #if 0
 311   struct AreaInfo * areainfo = rp->AreaInfo;
 312   UWORD * StartVctTbl = &areainfo->VctrTbl[first_idx * 2];
 313 #else
 314   UWORD * StartVctTbl = (UWORD *)points;
 315 #endif
 316
 317   UWORD scan;
 318   struct BoundLine tmpAreaBound;
 319   struct BoundLine * AreaBound =
 320         (struct BoundLine *) AllocMem(sizeof(struct BoundLine) * LastEdge,
 321                                       MEMF_CLEAR);
 322
 323   if (NULL == AreaBound)
 324    return FALSE;
 325
 326 #if georgchanges
 327 mul_xcoords();
 328 #endif
 329
 330   /* first clear the buffer of the temporary rastport as far as necessary  */
 331
 332   memset(rp->TmpRas->RasPtr,
 333          0,
 334          BytesPerRow * (bounds->MaxY - bounds->MinY + 1));
 335
 336
 337 #if 0
 338   kprintf("first: %d, last: %d\n",first_idx,last_idx);
 339   kprintf("(%d,%d)-(%d,%d)\n",bounds->MinX,bounds->MinY,
 340                               bounds->MaxX,bounds->MaxY);
 341   kprintf("width: %d, bytesperrow: %d\n",bounds->MaxX - bounds->MinX + 1,
 342                                          BytesPerRow);
 343 #endif
 344
 345   /* I need a list of sorted indices that represent the lines of the
 346   ** polygon. Horizontal lines don't go into that list!!!
 347   ** The lines are sorted by their start-y coordinates.
 348   */
 349
 350   i = -1;
 351   c = 0;
 352
 353   /* process all points of the polygon */
 354   while (c < (LastEdge-1)*2)
 355   {
 356     int i2;
 357     /* is the next one starting point of a horizontal line??? If yes,
 358        then skip it */
 359
 360     //kprintf("current idx for y: %d, next idx for y: %d\n",c+1,c+3);
 361
 362     if (StartVctTbl[c+1] == StartVctTbl[c+3])
 363     {
 364       //kprintf("Found horizontal Line!!\n");
 365       c+=2;
 366       continue;
 367     }
 368
 369     /* which coordinate of this line has the lower y value */
 370     if (StartVctTbl[c+1] < StartVctTbl[c+3])
 371     {
 372       tmpAreaBound.StartIndex = c;
 373       tmpAreaBound.EndIndex   = c+2;
 374       ymin = StartVctTbl[c+1];
 375     }
 376     else
 377     {
 378       tmpAreaBound.StartIndex = c+2;
 379       tmpAreaBound.EndIndex   = c;
 380       ymin = StartVctTbl[c+3];
 381     }
 382
 383
 384 #if 0
 385     kprintf("line: (%d,%d)-(%d,%d)  ",StartVctTbl[c],
 386                                       StartVctTbl[c+1],
 387                                       StartVctTbl[c+2],
 388                                       StartVctTbl[c+3]);
 389     kprintf("miny: %d\n",ymin);
 390 #endif
 391     i2 = 0;
 392     /*
 393     ** search for the place where to put this entry into the sorted
 394     ** (increasing start y-coordinates) list
 395     */
 396     if (i > -1)
 397     {
 398       while (TRUE)
 399       {
 400
 401 //kprintf("ymin: %d< %d?\n",ymin,StartVctTbl[AreaBound[i2].StartIndex+1]);
 402
 403         if (ymin < StartVctTbl[AreaBound[i2].StartIndex+1])
 404         {
 405           int i3 = i+1;
 406           /* found the place! */
 407           while (i3 > i2)
 408           {
 409
 410 //kprintf("moving!\n");
 411
 412             AreaBound[i3].StartIndex = AreaBound[i3-1].StartIndex;
 413             AreaBound[i3].EndIndex   = AreaBound[i3-1].EndIndex;
 414             i3--;
 415           }
 416           AreaBound[i2].StartIndex = tmpAreaBound.StartIndex;
 417           AreaBound[i2].EndIndex   = tmpAreaBound.EndIndex;
 418           break;
 419         }
 420         i2++;
 421         if (i2 > i)
 422         {
 423
 424 //kprintf("at end!\n");
 425
 426           AreaBound[i+1].StartIndex = tmpAreaBound.StartIndex;
 427           AreaBound[i+1].EndIndex   = tmpAreaBound.EndIndex;
 428           break;
 429         }
 430       }
 431     }
 432     else /* first one to insert into list */
 433     {
 434       AreaBound[0].StartIndex = tmpAreaBound.StartIndex;
 435       AreaBound[0].EndIndex   = tmpAreaBound.EndIndex;
 436     }
 437     c += 2;
 438     i++;
 439   }
 440
 441   LastIndex = i;
 442   i = 0;
 443
 444
 445   {
 446     int i2 = 0;
 447     while (i2 <= LastIndex)
 448     {
 449 #if 0
 450       kprintf("%d.: index %d (%d,%d)-(%d,%d)\n",i2,AreaBound[i2].StartIndex,
 451                                StartVctTbl[AreaBound[i2].StartIndex],
 452                                StartVctTbl[AreaBound[i2].StartIndex+1],
 453                                StartVctTbl[AreaBound[i2].EndIndex],
 454                                StartVctTbl[AreaBound[i2].EndIndex+1]);
 455 #endif
 456       i2++;
 457     }
 458   }
 459
 460
 461   while (i <= LastIndex)
 462   {
 463     int StartIndex = AreaBound[i].StartIndex;
 464     int EndIndex   = AreaBound[i].EndIndex;
 465
 466     if ((StartVctTbl[EndIndex] - StartVctTbl[StartIndex]) > 0) {
 467       AreaBound[i].s1 = 1;
 468     } else {
 469       AreaBound[i].s1 = -1;
 470     }
 471
 472     AreaBound[i].DeltaX = abs(StartVctTbl[EndIndex] -
 473                               StartVctTbl[StartIndex]);
 474
 475     AreaBound[i].DeltaY = abs(StartVctTbl[EndIndex+1] -
 476                               StartVctTbl[StartIndex+1]);
 477
 478     if (AreaBound[i].DeltaX > AreaBound[i].DeltaY) {
 479       AreaBound[i].horiz = 1;
 480     }
 481
 482
 483     if (AreaBound[i].DeltaX < AreaBound[i].DeltaY) {
 484       WORD d = AreaBound[i].DeltaX;
 485       AreaBound[i].DeltaX = AreaBound[i].DeltaY;
 486       AreaBound[i].DeltaY = d;
 487       AreaBound[i].t = 0;
 488     } else {
 489       AreaBound[i].t = 1;
 490     }
 491
 492     AreaBound[i].Count =  (AreaBound[i].DeltaY * 2) - AreaBound[i].DeltaX;
 493     AreaBound[i].incrE  =  AreaBound[i].DeltaY * 2;
 494     AreaBound[i].incrNE = (AreaBound[i].DeltaY - AreaBound[i].DeltaX) * 2;
 495
 496     AreaBound[i].LeftX = AreaBound[i].RightX = StartVctTbl[StartIndex];
 497     AreaBound[i].Valid = TRUE;
 498     i++;
 499   }
 500
 501   /* indexlist now contains i+1 indices into the vector table.
 502      Either the coordinate at the index as declared in the indexlist
 503      contains the lower y value or the following coordinate */
 504
 505   scan = bounds->MinY;
 506
 507   LastIndex = i;
 508
 509   StartEdge = 0;
 510   EndEdge = Include(1, LastIndex, AreaBound, scan, StartVctTbl);
 511   StartEdge = UpdateXValues(StartEdge, EndEdge, scan, AreaBound, StartVctTbl);
 512
 513   while (scan < bounds->MaxY)
 514   {
 515     XSort(StartEdge, EndEdge, AreaBound);
 516
 517     if (scan > bounds->MinY)
 518       FillScan(StartEdge,
 519                EndEdge,
 520                AreaBound,
 521                scan,
 522                rp,
 523                bounds,
 524                BytesPerRow,
 525                GfxBase);
 526
 527
 528 #if 0
 529     kprintf("scanline: %d   StartEdge: %d, EndEdge: %d\n",scan,StartEdge,EndEdge);
 530
 531     {
 532       int x = StartEdge;
 533       while (x <= EndEdge)
 534       {
 535         if (TRUE == AreaBound[x].Valid)
 536         {
 537           kprintf("(%d,%d)-(%d,%d) currently at: Left: %d Right: %d\n",
 538                       StartVctTbl[AreaBound[x].StartIndex],
 539                       StartVctTbl[AreaBound[x].StartIndex+1],
 540                       StartVctTbl[AreaBound[x].EndIndex],
 541                       StartVctTbl[AreaBound[x].EndIndex+1],
 542                       AreaBound[x].LeftX,
 543                       AreaBound[x].RightX);
 544         }
 545         else
 546           kprintf("invalid\n");
 547         x++;
 548       }
 549     }
 550 #endif
 551
 552     scan++;
 553     EndEdge = Include(EndEdge, LastIndex, AreaBound, scan, StartVctTbl);
 554     StartEdge = UpdateXValues(StartEdge, EndEdge, scan, AreaBound, StartVctTbl);
 555
 556 //    kprintf("StartEdge: %d, EndEdge: %d\n",StartEdge,EndEdge);
 557
 558   }
 559
 560   FreeMem( AreaBound, sizeof(struct BoundLine) * LastEdge);
 561
 562                             BltPattern(
 563                                rp,
 564                                rp->TmpRas->RasPtr,
 565                                bounds->MinX,
 566                                bounds->MinY,
 567                                bounds->MaxX,
 568                                bounds->MaxY,
 569                                BytesPerRow
 570                             );
 571
 572 #if georgchanges
 573 div_xcoords();
 574 #endif
 575                             if  (rp->Flags & AREAOUTLINE)
 576                             {
 577                                 SetAPen(rp, GetOutlinePen(rp));
 578                             }
 579
 580                             Move(rp, points[0][0], points[0][1]);
 581                             PolyDraw(rp, numpoints + 1, (UWORD *)points);
 582
 583
 584   return TRUE;
 585 }
 586
 587 void LineInTmpRas(struct RastPort  * rp,
 588                   struct Rectangle * bounds,
 589                   UWORD              BytesPerRow,
 590                   UWORD              xleft,
 591                   UWORD              xright,
 592                   UWORD              y,
 593                   struct GfxBase   * GfxBase)
 594 {
 595   UWORD  index;
 596   UWORD  NumPixels;
 597   WORD   PixelMask;
 598   UWORD  PixelMask2;
 599   UWORD * RasPtr = (WORD *)rp->TmpRas->RasPtr;
 600   ULONG  shift;
 601
 602 //kprintf("(%d/%d) to (%d/%d)\n",xleft,y,xright,y);
 603
 604   /* adjust the coordinates */
 605   xleft  -= bounds->MinX;
 606   xright -= bounds->MinX;
 607   y      -= bounds->MinY;
 608
 609   //kprintf("line from %d to %d y = %d\n",xleft,xright,y);
 610
 611   if (xleft > xright) return;
 612   /*
 613     an algorithm that tries to minimize the number of accesses to the
 614     RasPtr
 615   */
 616
 617   /* Fill the first word */
 618   PixelMask = 0x8000;
 619
 620   /* determine the number of pixels to set at the beginning */
 621   NumPixels = xright - xleft + 1;
 622   if (NumPixels > 16)
 623     NumPixels = 16;
 624
 625   /* create enough pixels */
 626   PixelMask >>= (NumPixels - 1);
 627
 628   index = (y * (BytesPerRow >> 1)) + (xleft >> 4);
 629   /* Adjust the pixelmask so we hit the very first pixel  */
 630   PixelMask2 = PixelMask & 0xffff;
 631   if (0 != (shift = (xleft & 0x0f))) {
 632     PixelMask2 >>= shift;
 633   }
 634
 635 #if (AROS_BIG_ENDIAN == 0)
 636   /* Endianess conversion*/
 637   PixelMask2 = PixelMask2 << 8 | PixelMask2 >> 8;
 638 #endif
 639   RasPtr[index] |= PixelMask2;
 640 //kprintf("%x (left)\n",PixelMask2);
 641
 642   index++;
 643
 644   xleft = xleft + (16 - shift);
 645
 646   if ((xright - xleft) < 16)
 647     goto fillright;
 648
 649   /* fill the middle with 0xffff's */
 650   while ((xleft + 15) < xright)
 651   {
 652     RasPtr[index] = (WORD)0xffff;
 653     index++;
 654     xleft += 16;
 655   }
 656
 657 fillright:
 658   if (xleft <= xright)
 659   {
 660     PixelMask = 0x8000;
 661     /* Create enough pixels - one pixel is already there! */
 662     if (0 != (shift = (xright - xleft + 0))) {
 663       PixelMask >>= shift;
 664     }
 665
 666     PixelMask2 = PixelMask & 0xffff;
 667
 668 #if (AROS_BIG_ENDIAN == 0)
 669     /* Endianess conversion*/
 670     PixelMask2 = PixelMask2 << 8 | PixelMask2 >> 8;
 671 #endif
 672
 673     RasPtr[index] |= PixelMask2;
 674 //kprintf("%x (right)\n",PixelMask2);
 675   }
 676
 677 }
 678
 679
 680 void MyFillPolygon(struct RastPort *rp, WORD points[][2], WORD numpoints)
 681 {
 682     struct Rectangle bounds;
 683     WORD i;
 684     ULONG bpr;
 685
 686     points[numpoints][0] = points[0][0];
 687     points[numpoints][1] = points[0][1];
 688
 689     bounds.MinX = bounds.MinY = 32767;
 690     bounds.MaxX = bounds.MaxY = -32768;
 691
 692     for(i = 0; i <= numpoints; i++)
 693     {
 694         if (points[i][0] < bounds.MinX) bounds.MinX = points[i][0];
 695         if (points[i][1] < bounds.MinY) bounds.MinY = points[i][1];
 696         if (points[i][0] > bounds.MaxX) bounds.MaxX = points[i][0];
 697         if (points[i][1] > bounds.MaxY) bounds.MaxY = points[i][1];
 698     }
 699
 700     bpr = (((bounds.MaxX - bounds.MinX + 1) + 15) & ~15) / 8;
 701
 702 kprintf("Myfillpolygon: bpr %d bounds %d,%d - %d,%d\n",
 703 bpr, bounds.MinX, bounds.MinY, bounds.MaxX, bounds.MaxY);
 704
 705     areafillpolygon(rp, &bounds, 0, numpoints, bpr, GfxBase);
 706
 707 }
 708
 709