fb4ef5ddff422e6ddb8ee3695d73ab47f0f5d039 kent Tue May 27 10:44:56 2014 -0700 Adding Jim Kent copyright notices to a few files that needed it. diff --git src/lib/mgPolygon.c src/lib/mgPolygon.c index ce31e44..61c7ef6 100644 --- src/lib/mgPolygon.c +++ src/lib/mgPolygon.c @@ -1,436 +1,438 @@ /* mgPolygon - stuff to draw polygons in memory. This code dates * back to 1984, was used in the Aegis Animator for the Atari ST. * It was an exceedingly speed critical routine for that program. * For us it may be overkill, but the major speed tweak - the special * case for convex polygons - is only 1/3 of the module, so I'm leaving * it in. I've lightly adapted the code to current conventions, but * you can still see some relics in the local and static variable names of - * other coding conventions. */ + * other coding conventions. + * This file is copyright 1984-2002 Jim Kent, but license is hereby + * granted for all use - public, private or commercial. */ #include "common.h" #include "bits.h" #include "memgfx.h" #include "gfxPoly.h" void mgDrawPolyOutline(struct memGfx *mg, struct gfxPoly *poly, Color color) /* Draw a singe pixel line around polygon. */ { struct gfxPoint *a, *b, *end; a = end = poly->ptList; b = a->next; for (;;) { mgDrawLine(mg, a->x, a->y, b->x, b->y, color); a = b; b = b->next; if (a == end) break; } } /* ----- Stuff for convex polygons that may contain crossing lines ----- * This code works by allocating a bitmap big enough to hold the polygon * and drawing lines on the bitmap in a special fashion, and then * scanning the bitmap to connect together the dots with horizontal lines. */ #define UPDIR 1 #define DOWNDIR 0 static UBYTE *on_off_buf; /* Our bitplane. */ static int pxmin, pxmax, pymin, pymax; /* Bounds of polygon. */ static void find_pminmax(struct gfxPoly *poly) { struct gfxPoint *pointpt; int i; pointpt = poly->ptList; pxmin = pxmax = pointpt->x; pymin = pymax = pointpt->y; pointpt = pointpt->next; i = poly->ptCount; while (--i > 0) { if (pxmin > pointpt->x) pxmin = pointpt->x; if (pxmax < pointpt->x) pxmax = pointpt->x; if (pymin > pointpt->y) pymin = pointpt->y; if (pymax < pointpt->y) pymax = pointpt->y; pointpt = pointpt->next; } } static void xor_pt(int bpr, int x, int y) /* Xor in a bit at given location. */ { UBYTE rot; rot = ((unsigned)0x80) >> (x&7); on_off_buf[ bpr*y + (x>>3) ] ^= rot; } static void y_xor_line(int bpr, int x1, int y1, int x2, int y2) /* Xor in a line onto on_off_buf, only plotting when we hit a new y-value. */ { UBYTE *imagept = on_off_buf; UBYTE rot; int duty_cycle; int delta_x, delta_y; int dots; int swap; if (x1 > x2) { swap = x1; x1 = x2; x2 = swap; swap = y1; y1 = y2; y2 = swap; } delta_y = y2-y1; delta_x = x2-x1; rot = ((unsigned)0x80) >> (x1&7); imagept += bpr*y1 + (x1>>3); if (delta_y < 0) { delta_y = -delta_y; bpr = -bpr; } duty_cycle = (delta_x - delta_y)/2; *(imagept) ^= rot; if (delta_x < delta_y) { dots = delta_y; while (--dots >= 0) { *(imagept) ^= rot; duty_cycle += delta_x; /* update duty cycle */ imagept += bpr; if (duty_cycle > 0) { duty_cycle -= delta_y; rot >>= 1; if (rot == 0) { imagept++; rot = 0x80; } } } } else { dots = delta_x; while (--dots >= 0) { duty_cycle -= delta_y; /* update duty cycle */ if (duty_cycle < 0) { *(imagept) ^= rot; duty_cycle += delta_x; imagept += bpr; } rot >>= 1; if (rot == 0) { imagept++; rot = 0x80; } } } } static void drawAfterOnOff(struct memGfx *mg, Color color, int bpr, int width, int height) /* Examine bitmap and draw horizontal lines between set bits. */ { UBYTE *linept = on_off_buf; int y; for (y=0; y<height; ++y) { int start = 0; int end; for (;;) { start = bitFindSet(linept, start, width); if (start >= width) break; end = bitFindSet(linept, start+1, width); mgLineH(mg, y+pymin, start+pxmin, end+pxmin, color); start = end+1; } linept += bpr; } } static void fillConcave(struct memGfx *mg, struct gfxPoly *poly, Color color) /* Draw concave polygon */ { struct gfxPoint *pointpt; int x,y; int ox,oy; int lastdir; int i; int bpr; /* Bytes per row */ int width, height; long size; find_pminmax(poly); if (pymin==pymax) /*Complex code can't cope with trivial case*/ { mgLineH(mg, pymin, pxmin, pxmax,color); return; } width = pxmax - pxmin + 1; height = pymax - pymin + 1; bpr = ((width+7)>>3); size = (long)bpr*height; if ((on_off_buf = needMem(size)) == NULL) return; pointpt = poly->ptList; x = pointpt->x; y = pointpt->y; do { pointpt = pointpt->next; ox = pointpt->x; oy = pointpt->y; } while (oy == y); if (oy>y) lastdir = UPDIR; else lastdir = DOWNDIR; i = poly->ptCount; while (--i >= 0) { pointpt = pointpt->next; x = pointpt->x; y = pointpt->y; if (y!=oy) { y_xor_line(bpr,ox-pxmin,oy-pymin,x-pxmin,y-pymin); if (y>oy) if (lastdir == UPDIR) xor_pt(bpr,ox-pxmin,oy-pymin); else lastdir = UPDIR; else if (lastdir == DOWNDIR) xor_pt(bpr,ox-pxmin,oy-pymin); else lastdir = DOWNDIR; } ox = x; oy = y; } drawAfterOnOff(mg, color, bpr, width, height); freez(&on_off_buf); return; } /* ---- This section of code is for convex, polygons. It's faster. ---- */ #ifdef SOME_OFF_BY_ONE_PROBLEMS static int *xdda_ebuf(int *ebuf, int x1, int y1, int x2, int y2) /* Calculate the x-positions of a line from x1,y1 to x2/y2 */ { int incx, incy; int x; int duty_cycle; int delta_x, delta_y; int dots; delta_y = y2-y1; delta_x = x2-x1; incx = incy = 1; x = x1; if (delta_y < 0) { delta_y = -delta_y; incy = -1; } if (delta_x < 0) { delta_x = -delta_x; incx = -1; } duty_cycle = (delta_x - delta_y)/2; if (delta_x >= delta_y) { int lasty = y1-1; dots = delta_x+1; while (--dots >= 0) { if (lasty != y1) { *ebuf++ = x1; lasty = y1; } duty_cycle -= delta_y; x1 += incx; if (duty_cycle < 0) { duty_cycle += delta_x; /* update duty cycle */ y1+=incy; } } } else { dots = delta_y+1; while (--dots >= 0) { *ebuf++ = x1; duty_cycle += delta_x; y1+=incy; if (duty_cycle > 0) { duty_cycle -= delta_y; /* update duty cycle */ x1 += incx; } } } return(ebuf); } #endif /* SOME_OFF_BY_ONE_PROBLEMS */ #ifdef CONVEX_OPTIMIZATION int *fill_ebuf(struct gfxPoint *thread, int count, int *ebuf) /* Make list of x coordinates for a couple of lines. Assumes that * the y coordinates are monotonic. Ebuf needs to be as big as the * total height of thread. Returns next free space in ebuf. */ { int x, y, ox, oy; int i; ox = thread->x; oy = thread->y; for (i=0; i<count; ++i) { thread = thread->next; x = thread->x; y = thread->y; if (y!=oy) ebuf = xdda_ebuf(ebuf,ox,oy,x,y) - 1; ox = x; oy = y; } return(ebuf+1); } static void blast_hlines(struct memGfx *mg, int *thread1, /* List of start X positions. */ int *thread2, /* Backwards list of end positions. */ int y, /* Y position. */ int count, /* Number of horizontal lines to draw. */ Color color) /* Color. */ /* Draw a whole bunch of horizontal lines. */ { int x1, x2; thread2 += count; while (--count >= 0) { x1 = *thread1++; x2 = *(--thread2); if (x1 > x2) mgLineH(mg, y, x2, x1, color); else mgLineH(mg, y, x1, x2, color); y += 1; } } void mgDrawPolyFilled(struct memGfx *mg, struct gfxPoly *poly, Color color) /* Draw filled polygon, possibly with outline in a seperate color. */ { struct gfxPoint *p; struct gfxPoint *np; struct gfxPoint *peak; struct gfxPoint *valley; int highy; int i; int pcount; int lasty; peak = p = poly->ptList; i = poly->ptCount; highy = p->y; pcount = 0; while (--i > 0) { p = p->next; if (p->y <= highy) { peak = p; highy = p->y; } } p = peak; np = p->next; i = poly->ptCount; while (--i >= 0) { if (np->y < p->y) { int totalHeight; int *thread1, *thread2; valley = p; p = np; np = np->next; while (--i >= 0) { if (np->y > p->y) { fillConcave(mg, poly, color); return; /*sorry its concave*/ } p = np; np = np->next; } totalHeight = valley->y - highy + 1; AllocArray(thread1, totalHeight); AllocArray(thread2, totalHeight); fill_ebuf(peak, pcount, thread1); pcount = fill_ebuf(valley, poly->ptCount - pcount, thread2) - thread2; blast_hlines(mg, thread1, thread2, highy, pcount, color); freeMem(thread1); freeMem(thread2); return; } pcount++; p = np; np = np->next; } return; /*all points of poly have same y value */ } #endif /* CONVEX_OPTIMIZATION */ void mgDrawPoly(struct memGfx *mg, struct gfxPoly *poly, Color color, boolean filled) /* Draw polygon, possibly filled in color. */ { if (filled) fillConcave(mg, poly, color); // mgDrawPolyFilled(mg, poly, color); mgDrawPolyOutline(mg, poly, color); }