OutlineImpl:
CEDAR PROGRAM
IMPORTS
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] = {
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.
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;
each case generates 2 or 4 transitions. However, each transition will
--be seen exactly twice. So, only generate half the transitions each time
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
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.
ds: REAL ← 0.5; --halfway between the pixels
cx: REAL ← imageX+ds; --shorthand for center point of cell
cy: REAL ← imageY+ds;
trans:
PROC [light, dark:
INT]
RETURNS[d:
REAL] = {
Find h.tValue between light and dark, then offset by -ds
d ← (pts[light] - h.tValue)/(pts[light]-pts[dark])-ds;
};
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;
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.
SELECT code
FROM
single dark pixel
1b => NewTransition[h,cx+trans[2,3], cy-ds, cx-ds, cy+trans[0,3]]; --lower left
2b => NewTransition[h,cx+ds, cy+trans[1,2], cx+trans[3,2], cy-ds]; --lower right
4b => NewTransition[h,cx+trans[0,1],cy+ds, cx+ds, cy+trans[2,1]]; --upper right
10b => NewTransition[h,cx-ds, cy+trans[3,0],cx+trans[1,0],cy+ds]; --upper left
horizontal
3b => NewTransition[h,cx+ds,cy+trans[1,2], cx-ds,cy+trans[0,3]]; --right to left
14b => NewTransition[h,cx-ds,cy+trans[3,0], cx+ds,cy+trans[2,1]]; --left to right
vertical
6b => NewTransition[h,cx+trans[0,1], cy+ds, cx+trans[3,2], cy-ds]; --top to bottom
11b => NewTransition[h,cx+trans[2,3], cy-ds, cx+trans[1,0], cy+ds]; --bottom to top
single light pixel
7b => NewTransition[h,cx+trans[0,1], cy+ds, cx-ds, cy+trans[0,3]]; --upper left
16b => NewTransition[h,cx-ds, cy+trans[3,0], cx+trans[3,2],cy-ds]; --lower left
15b => NewTransition[h,cx+trans[2,3], cy-ds, cx+ds, cy+trans[2,1]]; --lower right
13b => NewTransition[h,cx+ds, cy+trans[1,2], cx+trans[1,0],cy+ds]; --upper right
diagonal pixels (two transitions). assume separate black areas.
5b => {
NewTransition[h,cx+trans[0,1], cy+ds,cx+ds,cy+trans[2,1]]; --light dark
NewTransition[h,cx+trans[2,3],cy-ds,cx-ds,cy+trans[0,3]]}; --dark light
12b => {
NewTransition[h,cx-ds,cy+trans[3,0],cx+trans[1,0],cy+ds]; --dark light
NewTransition[h,cx+ds,cy+trans[1,2],cx+trans[3,2],cy-ds]}; --light dark
ENDCASE => RETURN;
};
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
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�ge.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;
};
next two procedures can assume that the lists are not empty
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};
};
when adding samples, may need to eliminate duplicate points
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
};
head may be empty
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.