Return to prim.c CVS log

Up to [CSRG BSD Unix] / 41BSD / cmd / cifplot

Annotation of 41BSD/cmd/cifplot/prim.c, revision 1.1

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.