<> <> <> <> <> DIRECTORY Vector USING [VEC], Outline; OutlineImpl: CEDAR PROGRAM EXPORTS Outline = BEGIN OPEN Outline; InvalidID: PUBLIC SIGNAL = CODE; Abort: ERROR = CODE; Where: TYPE = {head, tail}; VEC: TYPE = Vector.VEC; ListSamples: TYPE = REF ListSamplesRec; ListSamplesRec: TYPE = RECORD[next: ListSamples, first, last: Sample]; Sample: TYPE = REF SampleRec; SampleRec: TYPE = RECORD[next: Sample, value: VEC]; ListHead: TYPE = REF ListHeadRec; ListHeadRec: TYPE = RECORD[first, last: ListSamples]; Data: TYPE = REF DataRec; DataRec: TYPE = RECORD [ edges: ListHead, --samples in edge order contours: ListHead, --samples in contour order transitions: ListHead, --samples for one scan line freeList: ListHead --freed empty lists from transitions ]; NewData: PROC RETURNS[d: Data] = { d _ NEW[DataRec]; d.edges _ NEW[ListHeadRec _ [first: NIL, last: NIL]]; d.contours _ NEW[ListHeadRec _ [first: NIL, last: NIL]]; d.transitions _ NEW[ListHeadRec _ [first: NIL, last: NIL]]; d.freeList _ NEW[ListHeadRec _ [first: NIL, last: NIL]]; }; ContourProc: TYPE = PROC [h: Handle, pts: ARRAY [0..4) OF INT, cx, cy: REAL]; OutlineEdge: PUBLIC PROC[h: Handle] RETURNS[nOutlines: INT] = { RETURN[Outline[h, ContourEdge]]}; OutlineBlackCenter: PUBLIC PROC[h: Handle] RETURNS[nOutlines: INT] = { RETURN[Outline[h, ContourBlackCenter]]}; OutlineBlackEdge: PUBLIC PROC[h: Handle] RETURNS[nOutlines: INT] = { RETURN[Outline[h, ContourBlackEdge]]}; GetOutline: PUBLIC PROC [data: REF, newPoint: PROC[x,y: REAL], id: INT] = { d: Data _ NARROW[data]; count: NAT _ 0; IF id <0 THEN SIGNAL InvalidID; FOR contour: ListSamples _ d.contours.first, contour.next UNTIL contour=NIL DO IF count=id THEN { FOR sa: Sample _ contour.first, sa.next UNTIL sa=NIL DO newPoint[sa.value.x,sa.value.y]; ENDLOOP; GOTO found; }; count _ count+1; ENDLOOP; SIGNAL InvalidID; --we never found it EXITS found => NULL; }; Outline: PROC [h: Handle, contourProc: ContourProc] RETURNS[nOutlines: INT] = { <> pts: ARRAY [0..4) OF INT; x,y, xEnd, yEnd: INT; h.data _ NewData[]; xEnd _ h.xStart+h.xPixels; yEnd _ h.yStart+h.yPixels; y _ h.yStart; DO x _ h.xStart; DO pts[0] _ IF x=h.xStart OR y=yEnd THEN h.border ELSE h.get[h.client,x-1,y]; pts[1] _ IF x=xEnd OR y=yEnd THEN h.border ELSE h.get[h.client,x,y]; pts[2] _ IF x=xEnd OR y=h.yStart THEN h.border ELSE h.get[h.client,x,y-1]; pts[3] _ IF x=h.xStart OR y=h.yStart THEN h.border ELSE h.get[h.client,x-1,y-1]; contourProc[h,pts,x,y ! Abort => GOTO aborted]; IF x>=xEnd THEN EXIT; x _ x+1; ENDLOOP; ProcessTransitionBuffer[NARROW[h.data]]; IF y>=yEnd THEN EXIT; y _ y+1; ENDLOOP; nOutlines _ MakeContours[NARROW[h.data]]; EXITS aborted => nOutlines _ -1; }; ContourBlackCenter: ContourProc = { <<0 1 clockwise goes to 0123 in the code>> <<3 2>> trans: PROC [dir: CARDINAL] = { SELECT dir FROM 01 => NewTransition[h,cx,cy,cx+1, cy]; 12 => NewTransition[h,cx+1,cy,cx+1,cy+1]; 23 => NewTransition[h,cx+1,cy+1,cx,cy+1]; 30 => NewTransition[h,cx, cy+1, cx,cy]; ENDCASE => ERROR; }; i,code, mask, count: CARDINAL _ 0; mask _ 10B; FOR i IN [0..4) DO IF pts[i]=h.tValue THEN {code _ code+mask; count _ count+1}; mask _ mask/2; ENDLOOP; IF count<2 OR count >3 THEN RETURN; --6 cases SELECT code FROM 12B, 5B => RETURN; --the 2 diagonals do not contribute 14B => trans[01]; --4 valid single transitions 11B => trans[30]; 6B => trans[12]; 3B => trans[23]; 16B => {trans[01]; trans[12]}; --4 valid double transitions 13B => {trans[30]; trans[23]}; --give them in left to right order 15B => {trans[30]; trans[01]}; 7B => {trans[23]; trans[12]}; ENDCASE => ERROR; }; ContourBlackEdge: ContourProc = { <<0 1 clockwise goes to 0123 in the code>> <<3 2>> path: PROC [dx0,dy0,dx1,dy1: REAL] = { --all paths go thru center IF dx1 < dx0 THEN { --make transitions in raster order NewTransition[h,cx,cy,cx+dx1,cy+dy1]; NewTransition[h,cx+dx0,cy+dy0,cx,cy]; } ELSE { NewTransition[h,cx+dx0,cy+dy0,cx,cy]; NewTransition[h,cx,cy,cx+dx1,cy+dy1]; }; }; i,code, mask: CARDINAL _ 0; mask _ 10B; FOR i IN [0..4) DO IF pts[i]=h.tValue THEN code _ code+mask; mask _ mask/2; ENDLOOP; <> SELECT code FROM 10b => path[-1,0,0,1]; --single black pixel 2 => path[1,0,0,-1]; 13b => path[1,0,0,1]; --single white pixel 16b => path[-1,0,0,-1]; 12b => {path[-1,0,0,1]; path[1,0,0,-1]}; --diagonal 3 => NewTransition[h,cx+1,cy,cx,cy]; --left 14b => NewTransition[h,cx-1,cy,cx,cy]; --right 11b => NewTransition[h,cx,cy, cx,cy+1]; --up 6b => NewTransition[h,cx,cy,cx,cy-1]; --down ENDCASE => RETURN; }; ContourEdge: ContourProc = { <<0 1 clockwise goes to 0123 in the code>> <<3 2>> <> ds: REAL _ 0.5; --halfway between the pixels <> <> NewT: PROC[x0,y0,x1,y1: REAL] = { NewTransition[h, cx+x0, cy+y0, cx+x1, cy+y1]; }; trans: PROC [light, dark: INT] RETURNS[d: REAL] = { <> d _ (pts[light] - h.tValue)/(pts[light]-pts[dark]); }; i,code, mask: CARDINAL _ 0; mask _ 10B; FOR i IN [0..4) DO IF pts[i]> SELECT code FROM <> 1b => NewT[+ds-trans[2,3], -ds, -ds, +ds-trans[0,3]]; --lower left 2b => NewT[+ds, ds-trans[1,2], -ds+trans[3,2], -ds]; --lower right 4b => NewT[-ds+trans[0,1],+ds, +ds, -ds+trans[2,1]]; --upper right 10b => NewT[-ds, -ds+trans[3,0], +ds-trans[1,0],+ds]; --upper left <> 3b => NewT[+ds,+ds-trans[1,2], -ds,+ds-trans[0,3]]; --right to left 14b => NewT[-ds,-ds+trans[3,0], +ds,-ds+trans[2,1]]; --left to right <> 6b => NewT[-ds+trans[0,1], +ds, -ds+trans[3,2], -ds]; --top to bottom 11b => NewT[+ds-trans[2,3], -ds, +ds-trans[1,0], +ds]; --bottom to top <> 7b => NewT[-ds+trans[0,1], +ds, -ds, +ds-trans[0,3]]; --upper left 16b => NewT[-ds, -ds+trans[3,0], -ds+trans[3,2],-ds]; --lower left 15b => NewT[+ds-trans[2,3], -ds, +ds, -ds+trans[2,1]]; --lower right 13b => NewT[+ds, +ds-trans[1,2], +ds-trans[1,0],+ds]; --upper right <> 5b => { NewT[-ds+trans[0,1], +ds,+ds,-ds+trans[2,1]]; --light dark NewT[+ds-trans[2,3],-ds,-ds,+ds-trans[0,3]]}; --dark light 12b => { NewT[-ds,-ds+trans[3,0],+ds-trans[1,0],+ds]; --dark light NewT[+ds,+ds-trans[1,2],-ds+trans[3,2],-ds]}; --light dark ENDCASE => RETURN; }; <> <> <> NewTransition: PROC[h: Handle, x0,y0,x1,y1: REAL] = { data: Data _ NARROW[h.data]; p0: VEC _ [x0,y0]; p1: VEC _ [x1,y1]; list: ListSamples; found: BOOLEAN _ FALSE; IF h.newEdge[h.client, x0, y0, x1, y1] THEN ERROR Abort; FOR list _ data.transitions.first, list.next UNTIL list=NIL DO IF list.last.value=p0 THEN { found _ TRUE; AddSample[p: p1, list: list, where: tail]; EXIT; }; IF list.first.value=p1 THEN { found _ TRUE; AddSample[p: p0, list: list, where: head]; EXIT; }; ENDLOOP; IF ~found THEN { list _ NewList[d: data, p: p0]; AddSample[p: p1, list: list, where: tail]; AppendList[head: data.transitions, list: list]; }; }; ProcessTransitionBuffer: PROC[d: Data] = { inTailOfEdge: PROC[p: VEC] RETURNS [found: BOOLEAN] = { FOR edge _ d.edges.first, edge _ edge.next UNTIL edge=NIL DO IF edge.last.value=p THEN RETURN[TRUE]; ENDLOOP; RETURN[FALSE]; }; inHeadOfEdge: PROC[p: VEC] RETURNS [found: BOOLEAN] = { FOR edge _ d.edges.first, edge _ edge.next UNTIL edge=NIL DO IF edge.first.value=p THEN RETURN[TRUE]; ENDLOOP; RETURN[FALSE]; }; edge, list: ListSamples; --set by in*OfEdge IF d.transitions.first=NIL THEN RETURN; --no transitions this scan line IF d.edges.first#NIL THEN --first set of transitions are all disjoint edges FOR list _ d.transitions.first, list.next UNTIL list=NIL DO IF inTailOfEdge[list.first.value] THEN AddListSamples[from: list, list: edge, where: tail] ELSE IF inHeadOfEdge[list.last.value] THEN AddListSamples[from: list, list: edge, where: head]; ENDLOOP; DO list _ RemoveFirst[head: d.transitions ! Empty => EXIT]; IF list.first#NIL THEN AppendList[head: d.edges, list: list] ELSE AppendList[head: d.freeList, list: list]; ENDLOOP; }; MakeContours: PROC[d: Data] RETURNS[INT]= { contour: ListSamples; allFound: SIGNAL = CODE; findRest: PROC = { edge: ListSamples _ d.edges.first; foundAny: BOOLEAN _ FALSE; UNTIL edge=NIL OR contour.first.value=contour.last.value DO IF edge.first.value=contour.last.value THEN { list: ListSamples _ edge; edge _ RemoveList[head: d.edges, list: list]; AddListSamples[from: list, list: contour, where: tail]; foundAny _ TRUE; } ELSE IF edge.last.value=contour.first.value THEN { list: ListSamples _ edge; edge _ RemoveList[head: d.edges, list: list]; AddListSamples[from: list, list: contour, where: head]; foundAny _ TRUE; } ELSE edge_edge.next; ENDLOOP; IF ~foundAny OR contour.first.value=contour.last.value THEN SIGNAL allFound; }; DO contour _ RemoveFirst[d.edges ! Empty=>EXIT]; DO findRest[! allFound => EXIT]; --adds pieces to contour ENDLOOP; IF contour.first.value=contour.last.value THEN contour.first _ contour.first.next; --remove duplicates AppendList[head: d.contours, list: contour]; ENDLOOP; RETURN[CountContours[d]]; }; CountEdges: PROC[d: Data] RETURNS[INT] = { count: NAT _ 0; FOR edge: ListSamples _ d.edges.first, edge.next UNTIL edge=NIL DO count _ count+1; ENDLOOP; RETURN[count]; }; CountContours: PROC[d: Data] RETURNS[INT] = { count: INT _ 0; FOR contour: ListSamples _ d.contours.first, contour.next UNTIL contour=NIL DO count _ count+1; ENDLOOP; RETURN[count]; }; NewList: PROC [d: Data, p: VEC] RETURNS [list: ListSamples] = { new: Sample _ NEW[SampleRec _ [NIL, p]]; list _ RemoveFirst[d.freeList ! Empty => {list _ NEW[ListSamplesRec]; CONTINUE};]; list.first _ list.last _ new; }; <> AddSample: PROC [p: VEC, list: ListSamples, where: Where] = { new: Sample _ NEW[SampleRec _ [NIL, p]]; IF where=head THEN {new.next _ list.first; list.first _ new} ELSE {list.last.next _ new; list.last _ new}; }; <> AddListSamples: PROC [from: ListSamples, list: ListSamples, where: Where] = { IF where = head THEN { IF from.last.value=list.first.value THEN from.last.next _ list.first.next --remove duplicate ELSE from.last.next _ list.first; list.first _ from.first; } ELSE { IF list.last.value=from.first.value THEN list.last.next _ from.first.next --remove duplicate ELSE list.last.next _ from.first; list.last _ from.last; }; from.first _ from.last _ NIL; --keep those reference counts down }; <> AppendList: PROC [head: ListHead, list: ListSamples] = { IF head.last=NIL THEN head.first _ list --first time ELSE head.last.next _ list; head.last _ list; }; Empty: SIGNAL=CODE; RemoveFirst: PROC [head: ListHead] RETURNS [first: ListSamples] = { IF head.first=NIL THEN SIGNAL Empty; first _ head.first; head.first _ head.first.next; IF head.first=NIL THEN head.last _ NIL; first.next _ NIL; RETURN[first]; }; RemoveList: PROC [head: ListHead, list: ListSamples] RETURNS[next: ListSamples] = { found: BOOLEAN _ FALSE; IF head.first=NIL THEN SIGNAL Empty; IF list=head.first THEN { found _ TRUE; head.first _ list.next; IF head.first=NIL THEN head.last_NIL; } ELSE { prev: ListSamples; FOR prev _ head.first, prev.next UNTIL prev.next=head.last DO IF prev.next=list THEN {found _ TRUE; prev.next _ list.next; EXIT}; ENDLOOP; IF list=head.last THEN {found _ TRUE; prev.next _ NIL; head.last _ prev} }; IF ~found THEN ERROR ELSE {next _ list.next; list.next _ NIL}; RETURN[next]; }; END.