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 = { 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 = { 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 = { 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] 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. "OutlineImpl.mesa Copyright c 1984 by Xerox Corporation. All rights reserved. Last Changed: Maureen Stone December 17, 1984 3:09:02 pm PST Doug Wyatt, September 5, 1985 2:41:49 pm PDT Michael Plass, December 13, 1985 5:00:57 pm PST This scans over the client window: xStart, yStart, xPixels, yPixels. (xStart, yStart) is the lower left corner of the lower left pixel. (yStart, xPixels) is the upper right corner of the upper right pixel. h.border describes the color outside the window. 0 1 clockwise goes to 0123 in the code 3 2 0 1 clockwise goes to 0123 in the code 3 2 each case generates 2 or 4 transitions. However, each transition will --be seen exactly twice. So, only generate half the transitions each time 0 1 clockwise goes to 0123 in the code 3 2 Order of mathematical operations is important. Think of adjacent sets of 4 pixels. We will compute each transition twice and we need to match up adjacent endpoints of transition edges. If we always compute the intersection in the same order (light, dark), we can just compare for equality. cx: REAL _ imageX+ds; --shorthand for center point of cell cy: REAL _ imageY+ds; Find h.tValue between light and dark. distance from light Each case generates 1 or 2 transitions. We have cx, cy. All intesection points are computed as c-ds+trans[light,dark]. To save typing, trans includes the -ds. single dark pixel horizontal vertical single light pixel diagonal pixels (two transitions). assume separate black areas. we keep all the transitions for one scan line in a list of samples at the end of each scan line we add the collected samples to the edges this buffer solves the problem of "horizontal" edges next two procedures can assume that the lists are not empty when adding samples, may need to eliminate duplicate points head may be empty Κθ– "cedar" style˜codešœ™Kšœ Οmœ1™šžœžœ˜Kšœžœ˜ K˜*Kšžœ˜K˜—šžœžœ˜Kšœžœ˜ K˜*Kšžœ˜K˜—Kšžœ˜—šžœžœ˜Kšœ˜K˜*Kšœ/˜/Kšœ˜—K˜—šΠbnœžœ ˜*š £ œžœžœžœ žœ˜7šžœ(žœžœž˜Kšžœ˜ K˜—Kšžœ˜——…—*N@X