![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to prim.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 40BSD / cmd / cifplot|
Return to prim.c CVS log | Up to [CSRG BSD Unix] / 40BSD / cmd / cifplot |
1.1 root 1: /*******************************************************************
2: * *
3: * File: CIFPLOT/prim.c *
4: * Written by Dan Fitzpatrick *
5: * copyright 1980 -- Regents of the University of California *
6: * *
7: ********************************************************************/
8:
9: #include <stdio.h>
10: #include "defs.h"
11: #include "globals.h"
12: #include "parser_defs.h"
13: #include "structs.h"
14: #include "out_structs.h"
15: #include "alloc.h"
16:
17: IMPORT GetQueue();
18: IMPORT PutQueue();
19: IMPORT PeekList();
20:
21: FORWARD real ECompare();
22:
23: AddEdges(xcurrent)
24: int xcurrent;
25: /* Add Edges from edge queue to active edge list */
26: {
27: int insert,i,Next;
28: register instance *p;
29: register edge *e;
30:
31: /*
32: p = (instance *) PeekHeap();
33: */
34: /* Next is the raster value of item on top of list */
35: /*
36: if(p==NIL) Next = Top;
37: else Next = CONVERT(p->min);
38: */
39: Next = xcurrent + 1;
40: NextEdge = NextUnAct;
41: for(i=0;i<UsedLayers;i++) {
42: insert = 0; /* insert is set to 1 if any edge has been inserted */
43: while( (EdgeQueue[i].QStart != NIL) &&
44: (((edge *) (EdgeQueue[i].QStart))->ix <= xcurrent) ) {
45: insert = 1;
46: /* Update the iy values if not valid */
47: if(Valid[i] != xcurrent) Validate(i,xcurrent);
48: e = (edge *) GetQueue(&(EdgeQueue[i]));
49: /* EdgeEnd[i] indicates when the next edge ends in layer i */
50: EdgeEnd[i] = MIN(EdgeEnd[i],e->ex);
51: PutList(e,&TempList,ECompare);
52: }
53: if(insert) {
54: MergeActives(i,&TempList);
55: /* change[i] is set to 1 if anything has changed in layer i */
56: change[i] = 1;
57: /* LastEdge indicates when the next edge ends for all layers */
58: LastEdge = MIN(LastEdge,EdgeEnd[i]);
59: /* Compute where the next edge intersection will occur on layer i */
60: Intersection(i,xcurrent);
61: }
62: /* Compute when the next edge will enter the active list for layer i */
63: if(EdgeQueue[i].QStart == NIL) EdgeStart[i] = NextUnAct;
64: else
65: EdgeStart[i] = ((edge *) (EdgeQueue[i].QStart))->ix;
66: /* NextEdge indicates when the next edge will become active */
67: NextEdge = MIN(NextEdge,EdgeStart[i]);
68: }
69: }
70:
71: RemoveEdges(xcurrent)
72: int xcurrent;
73: {
74: edge *e,*q;
75: int i;
76:
77: for(i=0;i<UsedLayers;i++)
78: /* For each layer check to see if time to remove edges */
79: if(xcurrent >= EdgeEnd[i]) {
80: for(e = (edge *) &(ActiveEdges[i]); e->Link != NIL; )
81: if(e->Link->ex <= xcurrent) {
82: /* If time to remove e->Link then unlink it. Record a change */
83: change[i] = 1;
84: q = e->Link;
85: e->Link = e->Link->Link;
86: /* If no more references to the PolyDesc then free it */
87: if(--(q->poly->refs) == 0) FreeDesc(q->poly);
88: FreeEdge(q);
89: }
90: else e=e->Link;
91: }
92: }
93:
94: Sort(xcurrent)
95: register xcurrent;
96: {
97: register int i;
98:
99: for(i=0;i<UsedLayers;i++) {
100: /* For each layer check to see if an intersection may
101: * have occured */
102: if(xcurrent >= EdgeIntersection[i]) {
103: /* Mark that a change has occured and update the y
104: * values in the active list */
105: if(Valid[i] != xcurrent) Validate(i,xcurrent);
106:
107: /* SortActive sets change[i] if anything was swapped */
108: SortActives(i);
109:
110: /* Compute where the next intersection will take place */
111: Intersection(i,xcurrent);
112: }
113: }
114: }
115:
116: Validate(i,xcurrent)
117: register int i;
118: int xcurrent;
119: /* Validate updates the y values of the elements in
120: * the active list for layer i */
121: {
122: register real diff;
123: register edge *e;
124:
125: diff = xcurrent - Valid[i];
126: for(e=(edge *) ActiveEdges[i].Link; e!=NIL; e=e->Link)
127: e->iy += diff*e->dy;
128: /* Valid[i] records the last update for layer i */
129: Valid[i] = xcurrent;
130: }
131:
132: Intersection(i,xcurrent)
133: int i,xcurrent;
134: /* Intersection calculates the next time to edges in the list cross */
135: {
136: register edge *e1,*e2;
137: register real diff; /* diff is the difference from the
138: * estimated next intersection and
139: * xcurrent (the current raster line) */
140:
141: e1 = (edge *) ActiveEdges[i].Link;
142: if(e1 == NIL || e1->Link == NIL) return;
143: /*
144: diff = MIN(EdgeIntersection[i],EdgeStart[i]) - xcurrent;
145: */
146: diff = Top - xcurrent;
147: for(e2=e1->Link; e2 != NIL && diff > 1.0;(e1 = e2, e2= e1->Link))
148: if( (e1->iy + e1->dy*diff) > (e2->iy + e2->dy*diff) ) {
149: /* Edges cross, compute intersection
150: * diff is reused as a temp but restored at end */
151: diff = e2->dy - e1->dy;
152: if(diff != 0.0) diff = (e1->iy - e2->iy)/diff;
153: }
154: EdgeIntersection[i] = MAX((int) (xcurrent + diff) - 1,xcurrent);
155: NextChange[i] = MIN(EdgeEnd[i],EdgeIntersection[i]);
156: NextChange[i] = MIN(NextChange[i],EdgeStart[i]);
157: }
158:
159: int *in;
160: real *it,*dt;
161:
162: ScanActives(xcurrent)
163: register int xcurrent;
164: {
165: register int i;
166: register edge *e;
167:
168: LastEdge = Top;
169: for(i=0; i<UsedLayers;i++) {
170: /* If change rescan active list, otherwise redraw from previous
171: * information by calling Draw */
172: if(change[i]) {
173: OutputTrap(i,xcurrent);
174: /* Update all the iy's */
175: if(Valid[i] != xcurrent) Validate(i,xcurrent);
176: /* Compute when next edge ends */
177: EdgeEnd[i] = Top;
178: in[i] = 0;
179:
180: for(e= (edge *) ActiveEdges[i].Link; e!=NIL; e=e->Link) {
181: if(e->poly->count == 0) {
182: e->poly->iy = e->iy;
183: e->poly->dy = e->dy;
184: if(in[e->poly->level]++ == 0) {
185: it[e->poly->level] = e->iy;
186: dt[e->poly->level] = e->dy;
187: if(extractor)
188: OutputExtEdge(e->iy,e->dy,e->poly->level,1);
189: }
190: }
191: if(0 == (e->poly->count += e->dir)) {
192: if(--in[e->poly->level] == 0) {
193: if(extractor)
194: OutputExtEdge(e->iy,e->dy,e->poly->level,0);
195: else
196: SendDisplay(it[e->poly->level],
197: dt[e->poly->level],
198: e->iy,e->dy,i);
199: }
200: }
201: EdgeEnd[i] = MIN(EdgeEnd[i],e->ex);
202: }
203: if(in[i]) {
204: fprintf(stderr,"in[%d] = %d\t",i,in[i]);
205: fprintf(stderr,"xcurrent = %d\n",xcurrent);
206: for(e=(edge *) ActiveEdges[i].Link;e!=NIL;e=e->Link) {
207: fprintf(stderr,"Edge %x: iy=%f, dy=%f, ix=%d, ex=%d;\n",e,e->iy,e->dy,e->ix,e->ex);
208: fprintf(stderr,"\t\tdir=%d, poly=%x\n",e->dir,e->poly);
209: }
210: Error("Bad Count in ScanActives",INTERNAL);
211: }
212: /* Reset change */
213: change[i] = 0;
214: NextChange[i] = MIN(EdgeEnd[i],EdgeIntersection[i]);
215: NextChange[i] = MIN(NextChange[i],EdgeStart[i]);
216: FinnishLine(i,xcurrent);
217: }
218: LastEdge = MIN(LastEdge,EdgeEnd[i]);
219: }
220: }
221:
222: InitScan() {
223: int i;
224: in = (int *) alloc(UsedLayers*sizeof(int));
225: it = (real *) alloc(UsedLayers*sizeof(real));
226: dt = (real *) alloc(UsedLayers*sizeof(real));
227: for(i=0; i<UsedLayers; i++) {
228: in[i] = 0;
229: }
230: }
231:
232: /*
233: DTest(i,xcurrent)
234: int i,xcurrent;
235: {
236: do {
237: Draw(i,xcurrent);
238: xcurrent++;
239: } while(xcurrent < NextChange[i]);
240: }
241: */
242:
243: real ECompare(a,b)
244: edge *a,*b;
245: {
246: return(a->iy - b->iy);
247: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.