op public repos

Blame

Date:: Wed Apr 14 19:54:10 2004 UTC
Message:: Add graph, plot
Actions:: History | Blob | Raw File
  1 4314729d 2004-04-14 devnull /*
  2 4314729d 2004-04-14 devnull  * fill -- polygon tiler
  3 4314729d 2004-04-14 devnull  * Updating the edgelist from scanline to scanline could be quicker if no
  4 4314729d 2004-04-14 devnull  * edges cross:  we can just merge the incoming edges.  If the scan-line
  5 4314729d 2004-04-14 devnull  * filling routine were a parameter, we could do textured
  6 4314729d 2004-04-14 devnull  * polygons, polyblt, and other such stuff.
  7 4314729d 2004-04-14 devnull  */
  8 4314729d 2004-04-14 devnull #include "mplot.h"
  9 4314729d 2004-04-14 devnull typedef enum{
 10 4314729d 2004-04-14 devnull 	Odd=1,
 11 4314729d 2004-04-14 devnull 	Nonzero=~0
 12 4314729d 2004-04-14 devnull }Windrule;
 13 4314729d 2004-04-14 devnull typedef struct edge Edge;
 14 4314729d 2004-04-14 devnull struct edge{
 15 4314729d 2004-04-14 devnull 	Point p;	/* point of crossing current scan-line */
 16 4314729d 2004-04-14 devnull 	int maxy;	/* scan line at which to discard edge */
 17 4314729d 2004-04-14 devnull 	int dx;		/* x increment if x fraction<1 */
 18 4314729d 2004-04-14 devnull 	int dx1;	/* x increment if x fraction>=1 */
 19 4314729d 2004-04-14 devnull 	int x;		/* x fraction, scaled by den */
 20 4314729d 2004-04-14 devnull 	int num;	/* x fraction increment for unit y change, scaled by den */
 21 4314729d 2004-04-14 devnull 	int den;	/* x fraction increment for unit x change, scaled by num */
 22 4314729d 2004-04-14 devnull 	int dwind;	/* increment of winding number on passing this edge */
 23 4314729d 2004-04-14 devnull 	Edge *next;	/* next edge on current scanline */
 24 4314729d 2004-04-14 devnull 	Edge *prev;	/* previous edge on current scanline */
 25 4314729d 2004-04-14 devnull };
 26 4314729d 2004-04-14 devnull static void insert(Edge *ep, Edge **yp){
 27 4314729d 2004-04-14 devnull 	while(*yp && (*yp)->p.x<ep->p.x) yp=&(*yp)->next;
 28 4314729d 2004-04-14 devnull 	ep->next=*yp;
 29 4314729d 2004-04-14 devnull 	*yp=ep;
 30 4314729d 2004-04-14 devnull 	if(ep->next){
 31 4314729d 2004-04-14 devnull 		ep->prev=ep->next->prev;
 32 4314729d 2004-04-14 devnull 		ep->next->prev=ep;
 33 4314729d 2004-04-14 devnull 		if(ep->prev)
 34 4314729d 2004-04-14 devnull 			ep->prev->next=ep;
 35 4314729d 2004-04-14 devnull 	}
 36 4314729d 2004-04-14 devnull 	else
 37 4314729d 2004-04-14 devnull 		ep->prev=0;
 38 4314729d 2004-04-14 devnull }
 39 4314729d 2004-04-14 devnull static void polygon(int cnt[], double *pts[], Windrule w, int v){
 40 4314729d 2004-04-14 devnull 	Edge *edges, *ep, *nextep, **ylist, **eylist, **yp;
 41 4314729d 2004-04-14 devnull 	Point p, q, p0, p1, p10;
 42 4314729d 2004-04-14 devnull 	int i, dy, nbig, y, left, right, wind, nwind, nvert;
 43 4314729d 2004-04-14 devnull 	int *cntp;
 44 4314729d 2004-04-14 devnull 	double **ptsp, *xp;
 45 4314729d 2004-04-14 devnull 	nvert=0;
 46 4314729d 2004-04-14 devnull 	for(cntp=cnt;*cntp;cntp++) nvert+=*cntp;
 47 4314729d 2004-04-14 devnull 	edges=(Edge *)malloc(nvert*sizeof(Edge));
 48 4314729d 2004-04-14 devnull 	if(edges==0){
 49 4314729d 2004-04-14 devnull 	NoSpace:
 50 4314729d 2004-04-14 devnull 		fprintf(stderr, "polygon: no space\n");
 51 4314729d 2004-04-14 devnull 		exits("malloc failed");
 52 4314729d 2004-04-14 devnull 	}
 53 4314729d 2004-04-14 devnull 	ylist=(Edge **)malloc(Dy(screen->r)*sizeof(Edge *));
 54 4314729d 2004-04-14 devnull 	if(ylist==0) goto NoSpace;
 55 4314729d 2004-04-14 devnull 	eylist=ylist+Dy(screen->r);
 56 4314729d 2004-04-14 devnull 	for(yp=ylist;yp!=eylist;yp++) *yp=0;
 57 4314729d 2004-04-14 devnull 	ep=edges;
 58 4314729d 2004-04-14 devnull 	for(cntp=cnt,ptsp=pts;*cntp;cntp++,ptsp++){
 59 4314729d 2004-04-14 devnull 		p.x=SCX((*ptsp)[*cntp*2-2]);
 60 4314729d 2004-04-14 devnull 		p.y=SCY((*ptsp)[*cntp*2-1]);
 61 4314729d 2004-04-14 devnull 		nvert=*cntp;
 62 4314729d 2004-04-14 devnull 		for(xp=*ptsp,i=0;i!=nvert;xp+=2,i++){
 63 4314729d 2004-04-14 devnull 			q=p;
 64 4314729d 2004-04-14 devnull 			p.x=SCX(xp[0]);
 65 4314729d 2004-04-14 devnull 			p.y=SCY(xp[1]);
 66 4314729d 2004-04-14 devnull 			if(p.y==q.y) continue;
 67 4314729d 2004-04-14 devnull 			if(p.y<q.y){
 68 4314729d 2004-04-14 devnull 				p0=p;
 69 4314729d 2004-04-14 devnull 				p1=q;
 70 4314729d 2004-04-14 devnull 				ep->dwind=1;
 71 4314729d 2004-04-14 devnull 			}
 72 4314729d 2004-04-14 devnull 			else{
 73 4314729d 2004-04-14 devnull 				p0=q;
 74 4314729d 2004-04-14 devnull 				p1=p;
 75 4314729d 2004-04-14 devnull 				ep->dwind=-1;
 76 4314729d 2004-04-14 devnull 			}
 77 4314729d 2004-04-14 devnull 			if(p1.y<=screen->r.min.y) continue;
 78 4314729d 2004-04-14 devnull 			if(p0.y>=screen->r.max.y) continue;
 79 4314729d 2004-04-14 devnull 			ep->p=p0;
 80 4314729d 2004-04-14 devnull 			if(p1.y>screen->r.max.y)
 81 4314729d 2004-04-14 devnull 				ep->maxy=screen->r.max.y;
 82 4314729d 2004-04-14 devnull 			else
 83 4314729d 2004-04-14 devnull 				ep->maxy=p1.y;
 84 4314729d 2004-04-14 devnull 			p10=subpt(p1, p0);
 85 4314729d 2004-04-14 devnull 			if(p10.x>=0){
 86 4314729d 2004-04-14 devnull 				ep->dx=p10.x/p10.y;
 87 4314729d 2004-04-14 devnull 				ep->dx1=ep->dx+1;
 88 4314729d 2004-04-14 devnull 			}
 89 4314729d 2004-04-14 devnull 			else{
 90 4314729d 2004-04-14 devnull 				p10.x=-p10.x;
 91 4314729d 2004-04-14 devnull 				ep->dx=-(p10.x/p10.y); /* this nonsense rounds toward zero */
 92 4314729d 2004-04-14 devnull 				ep->dx1=ep->dx-1;
 93 4314729d 2004-04-14 devnull 			}
 94 4314729d 2004-04-14 devnull 			ep->x=0;
 95 4314729d 2004-04-14 devnull 			ep->num=p10.x%p10.y;
 96 4314729d 2004-04-14 devnull 			ep->den=p10.y;
 97 4314729d 2004-04-14 devnull 			if(ep->p.y<screen->r.min.y){
 98 4314729d 2004-04-14 devnull 				dy=screen->r.min.y-ep->p.y;
 99 4314729d 2004-04-14 devnull 				ep->x+=dy*ep->num;
100 4314729d 2004-04-14 devnull 				nbig=ep->x/ep->den;
101 4314729d 2004-04-14 devnull 				ep->p.x+=ep->dx1*nbig+ep->dx*(dy-nbig);
102 4314729d 2004-04-14 devnull 				ep->x%=ep->den;
103 4314729d 2004-04-14 devnull 				ep->p.y=screen->r.min.y;
104 4314729d 2004-04-14 devnull 			}
105 4314729d 2004-04-14 devnull 			insert(ep, ylist+(ep->p.y-screen->r.min.y));
106 4314729d 2004-04-14 devnull 			ep++;
107 4314729d 2004-04-14 devnull 		}
108 4314729d 2004-04-14 devnull 	}
109 4314729d 2004-04-14 devnull 	left = 0;
110 4314729d 2004-04-14 devnull 	for(yp=ylist,y=screen->r.min.y;yp!=eylist;yp++,y++){
111 4314729d 2004-04-14 devnull 		wind=0;
112 4314729d 2004-04-14 devnull 		for(ep=*yp;ep;ep=nextep){
113 4314729d 2004-04-14 devnull 			nwind=wind+ep->dwind;
114 4314729d 2004-04-14 devnull 			if(nwind&w){	/* inside */
115 4314729d 2004-04-14 devnull 				if(!(wind&w)){
116 4314729d 2004-04-14 devnull 					left=ep->p.x;
117 4314729d 2004-04-14 devnull 					if(left<screen->r.min.x) left=screen->r.min.x;
118 4314729d 2004-04-14 devnull 				}
119 4314729d 2004-04-14 devnull 			}
120 4314729d 2004-04-14 devnull 			else if(wind&w){
121 4314729d 2004-04-14 devnull 				right=ep->p.x;
122 4314729d 2004-04-14 devnull 				if(right>=screen->r.max.x) right=screen->r.max.x;
123 4314729d 2004-04-14 devnull #define BART_BUG_FIXED	/* what goes on here?? -rob */
124 4314729d 2004-04-14 devnull #ifdef BART_BUG_FIXED
125 4314729d 2004-04-14 devnull 				if(right>left)
126 4314729d 2004-04-14 devnull 					line(screen, Pt(left, y), Pt(right, y), Endsquare, Endsquare, 0, getcolor(v), ZP);
127 4314729d 2004-04-14 devnull #else
128 4314729d 2004-04-14 devnull 				if(right>left){
129 4314729d 2004-04-14 devnull 					switch(v){
130 4314729d 2004-04-14 devnull 					default:
131 4314729d 2004-04-14 devnull 						segment(&screen, Pt(left, y), Pt(right, y),
132 4314729d 2004-04-14 devnull 							~0, D&~S);
133 4314729d 2004-04-14 devnull 						segment(&screen, Pt(left, y), Pt(right, y),
134 4314729d 2004-04-14 devnull 							v, f);
135 4314729d 2004-04-14 devnull 						break;
136 4314729d 2004-04-14 devnull 					case 0:
137 4314729d 2004-04-14 devnull 						segment(&screen, Pt(left, y), Pt(right, y),
138 4314729d 2004-04-14 devnull 							~0, D&~S);
139 4314729d 2004-04-14 devnull 						break;
140 4314729d 2004-04-14 devnull 					case 3:
141 4314729d 2004-04-14 devnull 						segment(&screen, Pt(left, y), Pt(right, y),
142 4314729d 2004-04-14 devnull 							v, f);
143 4314729d 2004-04-14 devnull 						break;
144 4314729d 2004-04-14 devnull 					}
145 4314729d 2004-04-14 devnull 				}
146 4314729d 2004-04-14 devnull #endif
147 4314729d 2004-04-14 devnull 			}
148 4314729d 2004-04-14 devnull 			wind=nwind;
149 4314729d 2004-04-14 devnull 			nextep=ep->next;
150 4314729d 2004-04-14 devnull 			if(++ep->p.y!=ep->maxy){
151 4314729d 2004-04-14 devnull 				ep->x+=ep->num;
152 4314729d 2004-04-14 devnull 				if(ep->x>=ep->den){
153 4314729d 2004-04-14 devnull 					ep->x-=ep->den;
154 4314729d 2004-04-14 devnull 					ep->p.x+=ep->dx1;
155 4314729d 2004-04-14 devnull 				}
156 4314729d 2004-04-14 devnull 				else
157 4314729d 2004-04-14 devnull 					ep->p.x+=ep->dx;
158 4314729d 2004-04-14 devnull 				insert(ep, yp+1);
159 4314729d 2004-04-14 devnull 			}
160 4314729d 2004-04-14 devnull 		}
161 4314729d 2004-04-14 devnull 	}
162 4314729d 2004-04-14 devnull 	free((char *)edges);
163 4314729d 2004-04-14 devnull 	free((char *)ylist);
164 4314729d 2004-04-14 devnull }
165 4314729d 2004-04-14 devnull void fill(int num[], double *ff[]){
166 4314729d 2004-04-14 devnull 	polygon(num, ff, Odd, e1->foregr);
167 4314729d 2004-04-14 devnull }