/* polygon.c */ /************************************************************************* *** POLYGON DRAWING MODULE *** *** Date begun: 20/3/89. *** *** Last modified: 22/3/89. *** *************************************************************************/ #include #include #include #define POLY_PARENT 1 #include "polygon.h" /***** * The first step is to sort the edges of the polygon into the edge table * * NOTE: keep track of polygon extent, and if deltay or deltax <= 1 can * draw polygon just by drawing edges. * * NOTE: using the above optimization, we can leave horizontal lines out * of the edgetable, since they will be filled by their neighbors, and * no scanning will occur if the polygon is just one horizontal line. * * NOTE: line-crawling. The info I need is the (probably fractional) amount * to delta x when increasing y by one. This is the fraction dx/dy. To * determine the amount to crawl, have a count c start at 0. When * proceeding a scan-line, add dx to c. The x pos = initial x + c/dy. * Want to avoid the divide, so when proceeding a scan-line subtract * dy from c until another subtraction would make c -ve, and inc x with * every subtraction. * while (++scanline < end) { * c += ABS(dx); * while (c >= dy) {c-=dy; x+=SGN(dx);} * } * This doesn't handle lines ideally nicely. It works, but doesn't usually * split the line evenly. To adjust this one could initialize c to a * value dependent on dy and dx (another calculation) instead of zero. * * NOTE: handling equivalent points (non-maxima/non-minima equal vertices) * differently. When entering a scanline, and adding new entries to the AET, * check if the start point is equivalent to the current point of an ending * entry (ie: start x = other x, and other y = current scanline). If so, * remove the ending entry now. * * NOTE: when following lists. Usually have a previous element pointer, to * allow the prev elt->next to be repointed. If a straight element pointer * is used, then when the first element is being looked at, there is no * previous element, so its a special case. Can remove this special case if * I use a pointer to a pointer to the element type (eg: etpp), and init it * with the address of the master pointer to the list. Note also that the * master pointer cannot then be a register variable. * * NOTE: after timing this, there is a clear loss of speed when increasing * the height of the polygon than when increasing the width. * * NOTE: in general, only need to sort in two types of situation- * directly after adding new edges, * after the scanline following the addition of new edge, * so perhaps I can save some time by keeping track of this. This has some * some problems. Near vertical lines may stay in incorrect order, so when * one of the line jags, the edge list order will be incorrect. Since I * currently can draw lines forwards or backwards, and I expect most polys * to be convex (ie: only two edges in list at a time), this is OK. * * NOTE: the above cut 20000 µs off ranpoly 128 128 * * NOTE: removing old edges. I can tell in advance the next time I will * need to remove an edge, by keeping track of the miny when I sort the * activedgetable after adding edges. * * NOTE: can cut both ABS and SGN from inc edges loop by using an item 's' * in the edge structure to hold the sign, and store ABS(dx) in dx to start * with. * * NOTE: beginning the swing to the blitter, instead of Move & Draw. The * idea is to have a template plane of chip RAM which is used as follows: * clear rect in plane for polygon * scan polygon into rect * blit rect into rastport * * NOTE: while blitting away, I seem to have discovered that the fwm and * lwm are affected by printing (printf -> console (not Text())) and not * restored to 0xffff. * * NOTE: by way of a warning - remember not to lead CodeProbe into this * function. Its console's text will clash with my OwnBlitter() call. * * NOTE: the reduced sorting problem has arisen. The drawing section of * this function is now very large, as a lot of code is near duplicated * to handle the various cases of ordering. *****/ /* Global ETentry array to avoid dynamic allocation. Set maximum number * of edges to 10. The average polygon should require only 3 or 4. Remember * the point of this is as part of a 3D imaging package, where most faces * should be triangles or quadrilaterals. */ #define MAXET 10 ETentry edgetablearray[MAXET]; /* Where I get my storage */ #define IMPOSSIBLEY 1000; /* Hope this is large enough */ struct blitter *blitter = (struct blitter *)0xdff040L; struct template template; void scanpoly(rp,poly) /*=============================================*/ struct RastPort *rp; polygon *poly; { edge *ep; /* Follow polygon edge list */ ETentry *edgetable,*activedgetable; /* ET and AET */ int j,bit; unsigned short *rectaddress,*put,*put1,*put2,*put3; short minx,maxx,maxy,dx,dy; unsigned short temp,lmask,rmask; register ETentry *etnp,**etpp,*etcp,*etsp; /* Manipulate entry lists */ register short miny; /* Track poly extent */ register short scanline,sort; edgetable = NULL; etcp = &edgetablearray[0]; minx = MIN(poly->first->start[0],poly->first->end[0]); maxx = MAX(poly->first->start[0],poly->first->end[0]); miny = MIN(poly->first->start[1],poly->first->end[1]); maxy = MAX(poly->first->start[1],poly->first->end[1]); dx = maxx - minx; dy = maxy - miny; for (ep = poly->first; ep; ep = ep->next) { /* Add to ET */ /* Track dimensions */ minx = MIN(minx,ep->start[0]); minx = MIN(minx,ep->end[0]); maxx = MAX(maxx,ep->start[0]); maxx = MAX(maxx,ep->end[0]); miny = MIN(miny,ep->start[1]); miny = MIN(miny,ep->end[1]); maxy = MAX(maxy,ep->start[1]); maxy = MAX(maxy,ep->end[1]); dx = maxx - minx; dy = maxy - miny; /* Fill an edgetablearray entry */ if (ep->start[1] < ep->end[1]) { etcp->p[0] = ep->start[0]; etcp->p[1] = ep->start[1]; etcp->endy = ep->end[1]; /* Add bits to crawl along line */ etcp->c = 0; etcp->dy = ep->end[1] - ep->start[1]; etcp->dx = ep->end[0] - ep->start[0]; if ((etcp->s = SGN(etcp->dx)) < 0) etcp->dx = ABS(etcp->dx); } else if (ep->start[1] > ep->end[1]){ etcp->p[0] = ep->end[0]; etcp->p[1] = ep->end[1]; etcp->endy = ep->start[1]; /* Add bits to crawl along line */ etcp->c = 0; etcp->dy = ep->start[1] - ep->end[1]; etcp->dx = ep->start[0] - ep->end[0]; if ((etcp->s = SGN(etcp->dx)) < 0) etcp->dx = ABS(etcp->dx); } else continue; /* Next edge. This edge is horizontal */ /* Sort into ET - ignores prev pointers */ etnp = edgetable; etpp = &edgetable; while (etnp) { /* No need to sort on X, since AET will sort on X */ if (etcp->p[1] <= etnp->p[1]) { *etpp = etcp; etcp->next = etnp; break; } etpp = &(etnp->next); etnp = etnp->next; } /* Check if inserting at end of list */ if (!etnp) { *etpp = etcp; etcp->next = NULL; } etcp++; /* Increment by sizeof(ETentry) - next empty one */ } /* End for loop, all edges should now be in edgetable. Behaviour * undefined if edgetablearray overflows. */ if ((dx < 2) || (dy < 2)) { /* Just draw the edges in - problem clipping within a rasport! * Clipping to the edges of the rp is automatic, but what about a * rect within the rp? */ for (ep = poly->first; ep; ep = ep->next) { Move(rp,(int)ep->start[0],(int)ep->start[1]); Draw(rp,(int)ep->end[0],(int)ep->end[1]); } return; } /* Next step is to initialize the AET, and progress from the top of the * image to the bottom: * init AET, scanline * add first scanline's edges - sort on x * while (AET not empty && scanline valid) { * draw lines * remove ending edges * inc edges * inc scanline * add new edges from ET - sort on x * } */ /* Clear the template rectangle */ rectaddress = (unsigned short *)template.plane; rectaddress += miny << template.m1; rectaddress += miny << template.m2; put = rectaddress; /* Keep start address of line */ rectaddress += minx >> 4; maxy = miny; /* Store: miny gets re-used later */ lmask = (unsigned short)(dy + 1); /* h */ rmask = (unsigned short)((dx>>4) + 1); /* w */ temp = (lmask<<6)+rmask; lmask = (template.tmodulo - rmask) << 1; /* Modulo value */ OwnBlitter(); WaitBlit(); blitter->bltdpth = (unsigned short)((long)rectaddress >> 16); blitter->bltdptl = (unsigned short)((long)rectaddress & 0xffff); blitter->bltdmod = lmask; blitter->bltafwm = 0xffff; blitter->bltalwm = 0xffff; blitter->bltcon0 = 0x0100; /* 0000 0001 00000000 */ blitter->bltcon1 = 0x0000; /* 0000000000000000 */ blitter->bltsize = temp; /* TRIGGER!!!!!!!!! */ activedgetable = NULL; scanline = edgetable->p[1]; /* Add to AET */ while (edgetable && (edgetable->p[1] == scanline)) { etcp = edgetable; edgetable = edgetable->next; etcp->next = activedgetable; activedgetable = etcp; } /* Sort on X by refreshing list - insertion sort */ etcp = activedgetable; activedgetable = NULL; miny = IMPOSSIBLEY; while (etcp) { miny = MIN(miny,etcp->endy); /* Use to check edge removal */ etsp = etcp; etcp = etcp->next; etnp = activedgetable; etpp = &activedgetable; while (etnp) { if (etsp->p[0] < etnp->p[0]) { *etpp = etsp; etsp->next = etnp; break; } etpp = &(etnp->next); etnp = etnp->next; } if (!etnp) { *etpp = etsp; etsp->next = NULL; } } /* End sort */ sort = 1; /* Need to re-sort on next scanline */ while (activedgetable) { /* Scanline range ? */ /* Draw the lines. Check in case list has odd length. */ etcp = activedgetable; while (etcp) { if (etcp->next) { /* Determine start word */ put1 = put; put1 += ((int)etcp->p[0]) >> 4; put3 = put; put3 += ((int)etcp->next->p[0]) >> 4; if (put1 == put3) { /* Determine lmask */ if (etcp->p[0] <= etcp->next->p[0]) bit = ((int)etcp->p[0]) & 0xf; else bit = ((int)etcp->next->p[0]) & 0xf; bit = 15 - bit; lmask = 1 << bit; rmask = lmask--; lmask += rmask; /* Determine rmask */ if (etcp->p[0] <= etcp->next->p[0]) bit = ((int)etcp->next->p[0]) & 0xf; else bit = ((int)etcp->p[0]) & 0xf; bit = 15-bit; rmask = -1; dy = 1 << bit; rmask -= --dy; /* Plug them in */ lmask = lmask & rmask; lmask = lmask | *put1; *put1 = (unsigned short)lmask; } else if (put1 < put3) { /* Determine lmask */ bit = ((int)etcp->p[0]) & 0xf; bit = 15 - bit; lmask = 1 << bit; rmask = lmask--; lmask += rmask; /* Determine rmask */ bit = ((int)etcp->next->p[0]) & 0xf; bit = 15-bit; rmask = -1; dy = 1 << bit; rmask -= --dy; /* Plug in the values */ lmask = lmask | *put1; *put1 = (unsigned short)lmask; rmask = rmask | *put3; *put3 = (unsigned short)rmask; put2 = put1; put2++; if (put2 < put3) { dy = (short)((int)put3 - (int)put2); dy = dy >> 1; /* Width */ dy += 64; /* Height = 1 */ WaitBlit(); blitter->bltdpth = (unsigned short)((long)put2 >> 16); blitter->bltdptl = (unsigned short)((long)put2 & 0xffff); blitter->bltdmod = 0; blitter->bltadat = 0xffff; blitter->bltcon0 = 0x01f0; /* 0000 0001 10000000 */ blitter->bltcon1 = 0x0000; /* 0000000000000000 */ blitter->bltsize = (unsigned short)dy; /* GO!!! */ } } else { /* Determine lmask */ bit = ((int)etcp->next->p[0]) & 0xf; bit = 15 - bit; lmask = 1 << bit; rmask = lmask--; lmask += rmask; /* Determine rmask */ bit = ((int)etcp->p[0]) & 0xf; bit = 15-bit; rmask = -1; dy = 1 << bit; rmask -= --dy; /* Do the line */ lmask = lmask | *put3; *put3 = (unsigned short)lmask; rmask = rmask | *put1; *put1 = (unsigned short)rmask; put2 = put3; put2++; if (put2 < put1) { dy = (short)((int)put1 - (int)put2); dy = dy >> 1; /* Width */ dy += 64; /* Height = 1 */ WaitBlit(); blitter->bltdpth = (unsigned short)((long)put2 >> 16); blitter->bltdptl = (unsigned short)((long)put2 & 0xffff); blitter->bltdmod = 0; blitter->bltadat = 0xffff; blitter->bltcon0 = 0x01f0; /* 0000 0001 10000000 */ blitter->bltcon1 = 0x0000; /* 0000000000000000 */ blitter->bltsize = (unsigned short)dy; /* GO!!! */ } } etcp = etcp->next->next; } else etcp = NULL; } /* Remove 'old' edges */ if (miny <= scanline) { /* Shouldn't ever be less than */ miny = IMPOSSIBLEY; etpp = &activedgetable; for (etcp = activedgetable; etcp; etcp = etcp->next) { if (etcp->endy == scanline) { *etpp = etcp->next; } else { miny = MIN(miny,etcp->endy); etpp = &(etcp->next); } } } /* Increment edges - could improve the loop with assembler by using * two registers to sum dx and temporarily store s. Can do it in C * but best left to assembler */ etcp = activedgetable; /**** LPROF HOTSPOT ****/ while (etcp) { /**** LPROF HOTSPOT ****/ etcp->c += etcp->dx; /**** LPROF HOTSPOT ****/ while (etcp->c >= etcp->dy) { /**** LPROF HOTSPOT ****/ etcp->c -= etcp->dy; /**** LPROF HOTSPOT ****/ etcp->p[0] += etcp->s; /**** LPROF HOTSPOT ****/ } /**** LPROF HOTSPOT ****/ etcp = etcp->next; /**** LPROF HOTSPOT ****/ } /**** LPROF HOTSPOT ****/ /* Increment scanline */ scanline++; put += template.tmodulo; /* Add new entries, removing conflicting old entries */ while (edgetable && (edgetable->p[1] == scanline)) { sort = 2; etcp = edgetable; edgetable = edgetable->next; etcp->next = activedgetable; activedgetable = etcp; /* Kill old entries that aren't local maxima or minima */ etpp = &(etcp->next); for (etsp = activedgetable->next; etsp; etsp = etsp->next) { /* Same X ? Last scanline ? */ if ((etsp->p[0] == etcp->p[0]) && (etsp->endy == scanline)) { *etpp = etsp->next; /* Removes etsp from AET */ } else etpp = &(etsp->next); } } /* Sort on X by refreshing list - insertion sort */ if (sort) { sort--; etcp = activedgetable; activedgetable = NULL; miny = IMPOSSIBLEY; while (etcp) { miny = MIN(miny,etcp->endy); etsp = etcp; etcp = etcp->next; etnp = activedgetable; etpp = &activedgetable; while (etnp) { if (etsp->p[0] < etnp->p[0]) { *etpp = etsp; etsp->next = etnp; break; } etpp = &(etnp->next); etnp = etnp->next; } if (!etnp) { *etpp = etsp; etsp->next = NULL; } } /* End while (etcp) {} */ } /* End if (sort) */ } /* End while (activedgetable) {} */ /* REM: dx not altered since I last used it to calc a modulo */ rmask = (unsigned short)((dx>>4) + 1); /* w */ lmask = (template.tmodulo - rmask) << 1; /* Modulo value */ /* Blit template into rastport */ for (j = 0; j < rp->BitMap->Depth; j++) { put = (unsigned short *)(rp->BitMap->Planes[j]); put += maxy << template.m1; put += maxy << template.m2; put += minx >> 4; WaitBlit(); blitter->bltapth = (unsigned short)((long)rectaddress >> 16); blitter->bltaptl = (unsigned short)((long)rectaddress & 0xffff); blitter->bltcpth = (unsigned short)((long)put >> 16); blitter->bltcptl = (unsigned short)((long)put & 0xffff); blitter->bltdpth = (unsigned short)((long)put >> 16); blitter->bltdptl = (unsigned short)((long)put & 0xffff); blitter->bltdmod = lmask; blitter->bltamod = lmask; blitter->bltcmod = lmask; if (rp->FgPen & (char)(1 << j)) blitter->bltbdat = 0xffff; else blitter->bltbdat = 0x0000; /* (Let !a == A, etc) * Want d = ab + Ac * => d = ab(c + C) + Ac(b + B) * => d = abc + abC + Abc + ABc */ blitter->bltcon0 = 0x0bca; /* 0000 1011 1100,1010 */ blitter->bltcon1 = 0x0000; /* 0000000000000000 */ /* REM: temp not used since I last set it to rect dimensions */ blitter->bltsize = temp; /* TRIGGER!!!!!!!!! */ } DisownBlitter(); }