tkacik@rphroy.UUCP (Tom Tkacik) (10/19/89)
This is a demo program that generates moire patterns using lines or circles. I wrote it to test out some line and circle algorithms. It is in the public domain, with the hope that someone can use the code in real programs :-). Thomas Tkacik rphroy!kyzyl!tkacik #--------------------------------CUT HERE------------------------------------- #! /bin/sh # # This is a shell archive. Save this into a file, edit it # and delete all lines above this comment. Then give this # file to sh by executing the command "sh file". The files # will be extracted into the current directory owned by # you with default permissions. # # The files contained herein are: # # -rw-r--r-- 1 tkacik users 744 Oct 18 23:42 Makefile # -rw-r--r-- 1 tkacik users 949 Oct 18 23:44 README # -rw-r--r-- 1 tkacik users 6068 Oct 18 23:25 line.c # -rw-r--r-- 1 tkacik users 1128 Oct 18 23:04 moire.6 # -rw-r--r-- 1 tkacik users 7168 Oct 18 22:23 moire.c # -rw-r--r-- 1 tkacik users 959 Oct 18 21:43 moire.h # echo 'x - Makefile' if test -f Makefile; then echo 'shar: not overwriting Makefile'; else sed 's/^X//' << '________This_Is_The_END________' > Makefile X# X# If you have gcc uncomment the following two lines X#CC = gcc X#GNULIB = /usr/local/lib/gcc-gnulib X XNAME = moire XDIR = /usr/games XSRC = moire.c line.c XOBJ = moire.o line.o XLDFLAGS = -s /lib/crt0s.o /lib/shlib.ifile X X$(NAME): $(OBJ) X $(LD) $(LDFLAGS) $(OBJ) $(GNULIB) -o moire X Xinstall: X mv $(NAME) $(DIR)/$(NAME) X chgrp bin $(DIR)/$(NAME) X chown bin $(DIR)/$(NAME) X Xlint: $(SRC) X lint -x -u $(SRC) X X# use gcc as a version of lint (for ANSI C compatability) X# because the standard include files use #sccs X# do not be pedantic about pre-processing Xpedantic: $(SRC) X gcc -ansi -E moire.c > junk.c X gcc -ansi -pedantic -S junk.c X gcc -ansi -E line.c > junk.c X gcc -ansi -pedantic -S junk.c X rm junk.c junk.s X X Xcleanup: X rm -f $(OBJ) moire ________This_Is_The_END________ if test `wc -c < Makefile` -ne 744; then echo 'shar: Makefile was damaged during transit (should have been 744 bytes)' fi fi ; : end of overwriting check echo 'x - README' if test -f README; then echo 'shar: not overwriting README'; else sed 's/^X//' << '________This_Is_The_END________' > README XI wrote this demo program in an attempt at line and circle generation. X XLine drawing is done using Bresenham's line algorithm. XCircles are drawn using a modification to Bresenham's circle algorithm Xso that they appear round. I use an aspect ratio of 3/2. XI had to generalize Bresenham's circle algorithm to generate the Xellipses. Getting it right was very tricky. XTo make it worse, I tried to make it more efficient by performing Xstrength reduction on the code. The result, is that the algorithm Xis not easy to follow. The meak of heart are should not try to Xmodify it. X XThe lines and circles are first drawn to an array in memory, and Xthen wrastop() is used to copy it to the screen. It would be faster Xto draw directly to the video memory, (but I have not made the Xhardware modification necessary to do so). X XThis code is placed in the public domain, with the hope it can be used Xin real programs :-). X XThomas Tkacik X<rphroy!kyzyl!tkacik> ________This_Is_The_END________ if test `wc -c < README` -ne 949; then echo 'shar: README was damaged during transit (should have been 949 bytes)' fi fi ; : end of overwriting check echo 'x - line.c' if test -f line.c; then echo 'shar: not overwriting line.c'; else sed 's/^X//' << '________This_Is_The_END________' > line.c X/* X * line.c X * written by Thomas Tkacik kyzyl!tkacik X * X * This code is submitted to the public domain X * You may do with it what you wish X */ X X#include <sys/window.h> X#include <stdio.h> X X#define SHORTS 45 /* shorts per row */ X#define WIDTH SHORTS*16 X#define HEIGHT 12*25 /* user lines */ X#define SCREEN_SHORTS SHORTS*HEIGHT /* number of shorts on screen */ X X#define abs(x) (((x)>0)?(x):(-x)) X#define sign(x) (((x)>=0)?1:-1) X Xunsigned short screen[HEIGHT][SHORTS]; /* what's on the screen */ X X/* X * display prints out all of the new changes X */ X Xvoid Xdisplay(wn, x, y, width, height) Xint wn, x, y, width, height; X{ X /* if wrastop fails just keep going */ X /* do not bother printing an error message */ X /* it will work the next time */ X X (void)wrastop(wn,screen[0],SHORTS*2,0,0,x,y,x,y,width,height, X SRCSRC,DSTSRC,0); X} X X/* X * clearmem the entire screen image in memory X */ X Xvoid Xclearmem() X{ X register int i; X register unsigned short *scrpt; X X scrpt = screen[0]; X for(i=0; i < HEIGHT*SHORTS; i++) X *(scrpt++) = 0; X} X X X/* X * dot if the given point is on the screen X * change its value (xor it with 1) X */ X Xvoid Xdot(x, y) Xregister int x, y; X{ X if((x>=0) && (y>=0) && (x<WIDTH) && (y<HEIGHT)) X screen[y][x>>4] ^= 1<<(x & 0xf); X} X X/* X * draw a line between two points using bresenham's algorithm X * the starting point is drawn but not the end point X */ X Xvoid Xline(x1, y1, x2, y2) Xregister int x1, y1; X int x2, y2; X{ X register short error, delta_x, delta_y; X register short y_gt_x = 0; /* assume delta_x > delta_y */ X short i; X int sign_x, sign_y; X X X delta_x = x2 - x1; /* algorithm wants 2*deltas */ X delta_y = y2 - y1; X X sign_x = sign(delta_x); /* used for determining direction */ X sign_y = sign(delta_y); X X delta_x = abs(delta_x); X delta_y = abs(delta_y); X X if(delta_y>delta_x) { X x2 = y1; /* swap x1 and y1 */ X y1 = x1; X x1 = x2; X X x2 = delta_y; /* swap delta_x and delta_y */ X delta_y = delta_x; X delta_x = x2; X X x2 = sign_y; /* swap sign_x and sign_y */ X sign_y = sign_x; X sign_x = x2; X X y_gt_x = 1; /* delta_y > delta_x! */ X } X X delta_y *= 2; /* delta_y is only used as 2*delta_y */ X error = delta_y - delta_x; /* actually 2*delta_y-delta_x */ X X for(i=0; i < delta_x; i++) { X if(y_gt_x) /* if so then swap on plotting pixels */ X dot(y1,x1); /* turn on pixel */ X else X dot(x1,y1); X X if(error >= 0) { X y1 += sign_y; X error += (delta_y - 2*delta_x); X } else { X error += delta_y; X } X X x1 += sign_x; X } X} X X/* X * circle will draw a circle centered at the specified point X * and with the specified radius using a slightly modified X * version of bresenham's circle algorithm X * X * this routine is made so that the circles appear to be round X * X * r is the width of the circle in pixels X * the height will be calculated X * X */ X X#define AX 2 /* aspect ratio is AX/AY */ X#define AY 3 X#define AX2 (AX*AX) X#define AY2 (AY*AY) X Xvoid Xcircle(x, y, r) Xint x, y, r; X{ X register int error, delta_x, delta_y; X register int x1, y1; X X x1 = 0; X y1 = r; X error = AX2 + AY2 - (2*AY2*r); X X while(y1>=0) { X dot(x+x1,y+y1); X dot(x-x1,y+y1); X dot(x+x1,y-y1); X dot(x-x1,y-y1); X X delta_x = 2*(error - AX2*x1) - AX2; X delta_y = 2*(error + AY2*y1) - AY2; X X if((error < 0) && (delta_y <= 0)) { X x1++; X error += (2*AX2*x1 + AX2); X } else if((error > 0) && (delta_x > 0)) { X y1--; X error += (AY2 - 2*AY2*y1); X } else { X x1++; X y1--; X error += 2*AX2*x1 - 2*AY2*y1 + AX + AY; X } X } X} X X/* X * draw an ellipse with center at x,y X * and major and minor axes axis_x and axis_y X * X * a generalization of bresenham's circle algorithm is used X * X * I have made the code harder to understand by performing X * strength reduction so fewer multiplies are required X * being replaced with additions X * (more could be done, but then too many registers are needed) X * X * Gcc does a nice job of using registers X * X */ X Xvoid Xellipse(x, y, axis_x, axis_y) Xregister int x, y; Xint axis_x, axis_y; X{ X register int x1, y1, delta_x, delta_y; X int dx, dy, error, axis_x2, axis_y2; X short x_gt_y; /* is axis_x > axis_y */ X X /* check for the degenerate cases */ X if((axis_x == 0) && (axis_y == 0)) { X dot(x, y); X return; X } X else if(axis_x == 0) { X line(x, y-axis_y, x, y+axis_y); X dot(x, y+axis_y); /* line does not do the endpoint */ X return; X } X else if(axis_y == 0) { X line(x-axis_x, y, x+axis_x, y); X dot(x+axis_x, y); /* line does not do the endpoint */ X return; X } X X /* make axis_y the larger of axis_x and axis_y */ X X x_gt_y = 0; X X if(axis_y < axis_x) { X axis_x ^= axis_y; /* swap axis_x and axis_y */ X axis_y ^= axis_x; X axis_x ^= axis_y; X X x_gt_y = 1; /* axis_y < axis_x! */ X } X X /* initialize error term and counters */ X X x1 = 0; X y1 = axis_y; X axis_x2 = axis_x * axis_x; X axis_y2 = axis_y * axis_y; X dx = axis_y2; X dy = axis_x2 * (1 - 2*axis_y); X error = axis_x2 + axis_y2 - (2*axis_x2*axis_y); X X /* first do the two end points */ X /* because we draw all four quadrants */ X /* the end points will get drawn twice, erasing them */ X /* they get done now so that they only get drawn once */ X if(x_gt_y) { X dot(x, y + axis_x); X dot(x, y - axis_x); X } else { X dot(x + axis_x, y); X dot(x - axis_x, y); X } X X /* draw the rest of the ellipse */ X X while(y1 > 0) { X if(x1 > 0) { X if(x_gt_y) { /* were x and y switched */ X dot(x + y1, y + x1); X dot(x - y1, y + x1); X dot(x + y1, y - x1); X dot(x - y1, y - x1); X } else { X dot(x + x1, y + y1); X dot(x - x1, y + y1); X dot(x + x1, y - y1); X dot(x - x1, y - y1); X } X } else { /* for very skinny ellipses */ X if(x_gt_y) { X dot(x + y1, y); X dot(x - y1, y); X } else { X dot(x, y + y1); X dot(x, y - y1); X } X } X X delta_x = 2*(error - axis_y2*x1) - axis_y2; X delta_y = 2*(error + axis_x2*y1) - axis_x2; X X if((error<0) && (delta_y<=0)) { X x1 += 1; X dx += 2*axis_y2; X error += dx; X } else if((error>0) && (delta_x>0)) { X y1 -= 1; X dy += 2*axis_x2; X error += dy; X } else { X x1 += 1; X y1 -= 1; X dx += 2*axis_y2; X dy += 2*axis_x2; X error += dx + dy; X } X } X} X ________This_Is_The_END________ if test `wc -c < line.c` -ne 6068; then echo 'shar: line.c was damaged during transit (should have been 6068 bytes)' fi fi ; : end of overwriting check echo 'x - moire.6' if test -f moire.6; then echo 'shar: not overwriting moire.6'; else sed 's/^X//' << '________This_Is_The_END________' > moire.6 X.\" .TH MAHJONGG 6 "1 August 1988" X.TH MOIRE 6 X.SH NAME Xmoire \- Create moire patterns X.SH SYNOPSIS X.B /usr/games/moire X[ \fB-lcxvb\fR ] [ \fB-n \fI###\fR ] X.SH DESCRIPTION X.I Moire Xcreates moire patterns by bouncing lines around a window. XCircles, crosses or flying vees can also be used. XBy default, 100 lines are used, but this can also be any number less than 100. XMoire opens a bordered window when it begins, and allows this window to Xbe moved or resized. XIt is also possible to have \fImoire\fR run in a full screen window without Xa border. XThis allows moire to replace the background pattern, Xwith other windows in front. X.SH OPTIONS X.IP \fB\-l XGenerate moire patterns with lines. XThis is the default. X.IP \fB\-c XGenerate moire patterns with circles. X.IP \fB\-x XGenerate moire patterns with crosses. X.IP \fB\-v XGenerate moire patterns with vees. X.IP \fB\-b XRun \fImoire\fR in a full screen borderless window. X.IP \fB\-n \fI#\fR XStart with \fI#\fR number of lines, circles, or crosses. X.SH FILES X/usr/games/moire executable X.SH AUTHOR XThomas Tkacik X.br X<rphroy!kyzyl!tkacik> X.SH BUGS XThat's not a bug, it's a feature! ________This_Is_The_END________ if test `wc -c < moire.6` -ne 1128; then echo 'shar: moire.6 was damaged during transit (should have been 1128 bytes)' fi fi ; : end of overwriting check echo 'x - moire.c' if test -f moire.c; then echo 'shar: not overwriting moire.c'; else sed 's/^X//' << '________This_Is_The_END________' > moire.c X/* X * moire.c X * written by Thomas Tkacik kyzyl!tkacik X * X * This code is submitted to the public domain X * You may do with it what you wish X */ X X#include <stdio.h> X#include <termio.h> X#include <sys/signal.h> X#include <tam.h> X#include <kcodes.h> X#include <sys/window.h> X#include <fcntl.h> X#include "moire.h" X X/* the number of lines to keep */ Xint num_lines = DEFLINE; X X/* the end points of each line */ Xstruct points { X short x1,y1; X short x2,y2; X} lines[MAXLINE],increment; X X/* the bounding box */ Xstruct rect { X unsigned short xmin,ymin; X unsigned short xmax,ymax; X} border; X X/* window structure */ Xstruct uwdata win; X X/* window discriptor */ Xint wn; X X/* terminal status */ Xstruct termio termstat; X Xint Xmain(argc, argv) Xint argc; Xchar **argv; X{ X int c, errflg = 0; /* for use with getopt() */ X extern int optind; X extern char *optarg; X X int bordered = BORDERED; /* bordered or borderless window */ X int type = LINE; X X while((c = getopt(argc, argv, "lcxvbn:")) != EOF) { X switch(c) { X case 'n': X num_lines = atoi(optarg); X if(num_lines > MAXLINE) X num_lines = MAXLINE; X break; X case 'l': X type = LINE; X break; X case 'x': X type = CROSS; X break; X case 'c': X type = CIRCLE; X break; X case 'v': X type = VEE; X break; X case 'b': X bordered = BORDERLESS; X break; X default: X errflg = 1; X } X } X if(errflg == 1) { X (void)fprintf(stderr,"Usage: %s [-lxc] [-b] [-n #]\n", argv[0]); X exit(1); X } X X /* initialize the window */ X X initialize(bordered); X X moire(type); X X return(0); X} X X/* X * initialize the window and signals X */ X Xvoid Xinitialize(bordered) Xint bordered; X{ X /* start with a clean window */ X X (void)close(0); X (void)close(1); X (void)close(2); X wn = open("/dev/window", O_RDWR ); X (void)dup(wn); X (void)dup(wn); X X /* initialize the tam routines */ X winit(); X X /* can only be run on the unixpc screen */ X if(iswind()==0) { X (void)fprintf(stderr, "must use bitmapped screen\n"); X wexit(1); X } X X /* open the moire window */ X X if(bordered == BORDERED) { X if((wn = wcreate(1,0,18,76, BORDRESIZE)) == -1) { X (void)fprintf(stderr, X "could not open window wn = %d\n",wn); X wexit(1); X } X } else { X if((wn = wcreate(1,0,24,80, NBORDER)) == -1) { X (void)fprintf(stderr, X "could not open window wn = %d\n",wn); X wexit(1); X } X } X X /* label the moire window */ X wlabel(wn, "Moire"); X wuser(wn, "Moire"); X X /* turn off the cursor */ X wputs(wn,"\033[=1C"); X X /* enable interrupts */ X /* set the interrupt character to control-c */ X X (void)ioctl(wn, TCGETA, &termstat); X termstat.c_lflag |= ISIG; X termstat.c_cc[0] = CNTL_C; X (void)ioctl(wn, TCSETA, &termstat); X X /* determine the initial window size */ X X (void)ioctl(wn,WIOCGETD,&win); X border.xmin = 1; X border.ymin = 1; X border.xmax = win.uw_width; X border.ymax = win.uw_height; X X /* clear the memory image of the screen */ X clearmem(); X X /* set up signals */ X X (void)signal(SIGHUP, leave); X (void)signal(SIGINT, leave); X (void)signal(SIGQUIT, leave); X (void)signal(SIGWIND, resize); X} X X/* X * generate the moire patterns X */ X Xvoid Xmoire(type) Xint type; X{ X int i, j; X void srand48(); X long time(); X X /* initialize the random number generator */ X X srand48((long)getpid() + time((long *)0)); X X /* set the first line */ X X lines[0].x1 = 2; X lines[0].y1 = 2; X lines[0].x2 = 2; X lines[0].y2 = 2; X X /* set the increment values */ X X increment.x1 = newinc(2,4,0); X increment.y1 = newinc(3,5,0); X increment.x2 = newinc(4,7,1); X increment.y2 = newinc(3,6,1); X X /* draw the first line */ X X draw(0, type); X X /* draw the rest of the lines before deleting any */ X X for(i = 1; i < num_lines; i++) { X update(i,i-1); X draw(i, type); X } X X /* now delete and add lines */ X X j = num_lines - 1; X i = 0; X for(;;) { X if(i >= num_lines) X i = 0; X X /* erase old line */ X draw(i, type); X X /* find new line */ X update(i,j); X X /* draw new line */ X draw(i, type); X X j = i; X i += 1; X } X} X X/* X * find the coordinates of the next line X * given the previous line X * check if it should bounce off a wall X */ X Xvoid Xupdate(i,j) Xint i,j; X{ X /* calculate new x1 */ X X lines[i].x1 = lines[j].x1 + increment.x1; X if(lines[i].x1 >= border.xmax) { X increment.x1 = -newinc(2,4,0); X lines[i].x1 = 2*border.xmax-lines[i].x1; X } X if(lines[i].x1 <= 0) { X increment.x1 = newinc(2,4,0); X lines[i].x1 = -lines[i].x1; X } X X /* calculate new y1 */ X X lines[i].y1 = lines[j].y1 + increment.y1; X if(lines[i].y1 >= border.ymax) { X increment.y1 = -newinc(3,5,0); X lines[i].y1 = 2*border.ymax-lines[i].y1; X } X if(lines[i].y1 <= 0) { X increment.y1 = newinc(3,5,0); X lines[i].y1 = -lines[i].y1; X } X X /* calculate new x2 */ X X lines[i].x2 = lines[j].x2 + increment.x2; X if(lines[i].x2 >= border.xmax) { X increment.x2 = -newinc(4,7,1); X lines[i].x2 = 2*border.xmax-lines[i].x2; X } X if(lines[i].x2 <= 0) { X increment.x2 = newinc(4,7,1); X lines[i].x2 = -lines[i].x2; X } X X /* calculate new y2 */ X X lines[i].y2 = lines[j].y2 + increment.y2; X if(lines[i].y2 >= border.ymax) { X increment.y2 = -newinc(3,6,1); X lines[i].y2 = 2*border.ymax-lines[i].y2; X } X if(lines[i].y2 <= 0) { X increment.y2 = newinc(3,6,1); X lines[i].y2 = -lines[i].y2; X } X} X X/* X * Xor the line to the in memory screen X * and then display it on the moire window X */ X Xvoid Xdraw(i, type) Xint i; Xint type; X{ X int xmin, ymin, xmax, ymax; X int xmean, ymean; X X xmin = lines[i].x1; X ymin = lines[i].y1; X xmax = lines[i].x2; X ymax = lines[i].y2; X X /* make sure that min really is smaller than max */ X X if(xmin > xmax) { X xmin = xmax; X xmax = lines[i].x1; X } X if(ymin > ymax) { X ymin = ymax; X ymax = lines[i].y1; X } X X /* find the center of the cross or circle */ X X xmean = (xmin + xmax) / 2; X ymean = (ymin + ymax) / 2; X X X /* draw or erase pattern to/from the internal image */ X /* because line xor's the line onto the screen image */ X /* if it is already there, it will be erased */ X X switch(type) { X case LINE: X line(xmin, ymin, xmax, ymax); X break; X case CROSS: X line(xmean, ymin, xmean, ymax); X line(xmin, ymean, xmax, ymean); X break; X case CIRCLE: X ellipse(xmean, ymean, abs(xmax-xmin)/2, abs(ymax-ymin)/2); X break; X case VEE: X line(xmin, ymin, xmean, ymax); X line(xmean, ymax, xmax, ymin); X break; X } X X /* is the line still visible -- the screen may now be smaller */ X X if((xmin < border.xmax-1) && (ymin < border.ymax-1)) { X X /* display the smallest region containing the new line */ X X if(xmax > border.xmax-1) X xmax = border.xmax-1; X if(ymax > border.ymax-1) X ymax = border.ymax-1; X X display(wn, xmin, ymin, xmax-xmin+1, ymax-ymin+1); X } X} X X/* X * get a new increment value X */ X Xint Xnewinc(least, range, even) Xint least, range, even; X{ X return(((int)(least + drand48()*range) & ~1) + even); X} X X/* X * resize is called whenever the window size is changed X */ X Xint Xresize() X{ X /* determine new window size */ X X (void)ioctl(wn,WIOCGETD,&win); X X border.xmax = win.uw_width; X border.ymax = win.uw_height; X X /* reset signal trap */ X X (void)signal(SIGWIND, resize); X return 0; X} X X/* X * exit the program X */ X Xint Xleave() X{ X wdelete(wn); X wexit(0); X X return 0; X} X ________This_Is_The_END________ if test `wc -c < moire.c` -ne 7168; then echo 'shar: moire.c was damaged during transit (should have been 7168 bytes)' fi fi ; : end of overwriting check echo 'x - moire.h' if test -f moire.h; then echo 'shar: not overwriting moire.h'; else sed 's/^X//' << '________This_Is_The_END________' > moire.h X/* X * moire.h X * written by Thomas Tkacik tetnix!tet X * X * This code is submitted to the public domain X * You may do with it what you wish X */ X X#define MAXLINE 100 /* maximum number of lines that may appear */ X#define DEFLINE 60 /* default number that will appear */ X#define MAXHEIGHT 248 /* maximum height of screen in pixels */ X#define MAXWIDTH 685 /* maximum width of screen in pixels */ X X#define LINE 0 X#define CROSS 1 X#define CIRCLE 2 X#define VEE 3 X#define BORDERED 0 X#define BORDERLESS 1 X X#define CNTL_C '\003' /* Control C */ X X#define min(x,y) ((x)<(y)?(x):(y)) X Xextern void display(); Xextern void clearmem(); Xextern void dot(); Xextern void line(); Xextern void circle(); Xextern void ellipse(); X Xextern void initialize(); Xextern void moire(); Xextern void update(); Xextern void draw(); Xextern int newinc(); Xextern int resize(); Xextern int leave(); X Xextern int (*signal())(); Xextern int ioctl(); Xextern void exit(); Xextern double drand48(); X ________This_Is_The_END________ if test `wc -c < moire.h` -ne 959; then echo 'shar: moire.h was damaged during transit (should have been 959 bytes)' fi fi ; : end of overwriting check exit 0 -- Tom Tkacik GM Research Labs, Warren MI 48090 uunet!edsews!rphroy!megatron!tkacik Work Ph: (313)986-1442 "If you can't stand the bugs, stay out of the roach-motel." Ron Guilmette