DIRECTORY
CubicSplines,
PointDefs,
ImagerPixelMap USING [DeviceRectangle],
ImagerScanConverter,
ImagerPath USING [PathProc, MoveToProc, LineToProc, CurveToProc],
Cubic2 USING [Bezier, Split, Flat, CoeffsToBezier, Coeffs],
Vector2 USING [VEC, Add, Sub, Div, Square, Mul, Length],
Real USING [RoundI],
GriffinEncoding;
GriffinEncodingImpl: CEDAR PROGRAM
IMPORTS CubicSplines, Vector2, PointDefs, ImagerScanConverter, Real, Cubic2
EXPORTS GriffinEncoding
~ BEGIN OPEN GriffinEncoding;

VEC: TYPE = Vector2.VEC;
X: NAT _ PointDefs.X;
Y: NAT _ PointDefs.Y;
Mbb: TYPE = REF MbbRec;
MbbRec: TYPE = RECORD[minX, minY: REAL _ 10E6, maxX, maxY: REAL _ -10E6];
PointProc: TYPE = PROC [p: VEC] RETURNS[stop: BOOLEAN _ FALSE];


EncodeLinearLink: PUBLIC PROC[endpoints: PointDefs.ObjPtSequence] RETURNS[Link] = TRUSTED {
link: Link;
prev: VEC;
mbb: Mbb _ NEW[MbbRec];
link.bezier _ NEW[LinkSequence[endpoints.length-1]];
prev.x _ PointDefs.ObjValToScrVal[endpoints[0][X]];
prev.y _ PointDefs.ObjValToScrVal[endpoints[0][Y]];
UpdateMbb[[prev.x, prev.y], mbb];
FOR i: NAT IN [0..link.bezier.length) DO
b0, b1, b2, b3: VEC;
b0 _ prev;
b3.x _ PointDefs.ObjValToScrVal[endpoints[i+1][X]];
b3.y _ PointDefs.ObjValToScrVal[endpoints[i+1][Y]];
UpdateMbb[[b3.x,b3.y], mbb];
b1 _ Vector2.Div[Vector2.Add[Vector2.Add[b0,b0], b3],3.0];
b2 _ Vector2.Div[Vector2.Add[b1, b3],2.0];
link.bezier[i] _ [b0: b0, b1: b1, b2: b2, b3: b3];
prev _ b3;
ENDLOOP;
link.isLine _ TRUE;
[link.tl, link.br] _ TLBRFromMbb[mbb];
RETURN[link];
};
EncodeCubicLink: PUBLIC PROC[knots: PointDefs.ObjPtSequence, splineType: CubicSplines.SplineType] RETURNS[Link] = {
coeffs: CubicSplines.CoeffsSequence;
newKnots: PointDefs.ObjPtSequence _ NEW[PointDefs.ObjPtSequenceRec[knots.length]];
mbb: Mbb _ NEW[MbbRec];
link: Link;
FOR i: NAT IN [0..knots.length) DO
TRUSTED {newKnots[i] _ PointDefs.ObjToScrReal[knots[i]]};
ENDLOOP;
coeffs _ CubicSplines.MakeSpline[newKnots, splineType];
link.bezier _ NEW[LinkSequence[coeffs.length]];
FOR i: NAT IN [0..coeffs.length) DO
cfs: Cubic2.Coeffs _ [
c3: [coeffs[i].t3[X], coeffs[i].t3[Y]],
c2: [coeffs[i].t2[X], coeffs[i].t2[Y]],
c1: [coeffs[i].t1[X], coeffs[i].t1[Y]],
c0: [coeffs[i].t0[X], coeffs[i].t0[Y]]];
link.bezier[i] _ Cubic2.CoeffsToBezier[cfs];
ENDLOOP;
FOR i: NAT IN [0..link.bezier.length) DO
pointProc: PointProc = {UpdateMbb[[p.x,p.y], mbb]};
WalkCurve[link.bezier[i], pointProc, 1.0];
ENDLOOP;
link.isLine _ FALSE;
[link.tl, link.br] _ TLBRFromMbb[mbb];
RETURN[link];
};
EncodeEdge: PUBLIC PROC[links: LIST OF Link] RETURNS[EdgeEncoding] = {
mbb: Mbb _ NEW[MbbRec];
edge: EdgeEncoding _ NEW[EdgeEncodingRec];
FOR l: LIST OF Link _ links, l.rest UNTIL l=NIL DO
UpdateMbb[l.first.tl, mbb];
UpdateMbb[l.first.br, mbb];
ENDLOOP;
[edge.tl, edge.br] _ TLBRFromMbb[mbb];
edge.links _ links;
RETURN[edge];
};
AppendLink: PUBLIC PROC[edge: EdgeEncoding, link: Link] RETURNS[EdgeEncoding] = {
mbb: Mbb _ MbbFromTLBR[edge.tl, edge.br];
IF edge.links=NIL THEN edge.links _ LIST[link]
ELSE {
l: LIST OF Link;
FOR l _ edge.links, l.rest UNTIL l.rest=NIL DO ENDLOOP;
l.rest _ LIST[link];
};
UpdateMbb[link.tl, mbb];
UpdateMbb[link.br, mbb];
[edge.tl, edge.br] _ TLBRFromMbb[mbb];
RETURN[edge];
};
RemoveLastLink: PUBLIC PROC[edge: EdgeEncoding] RETURNS[Link] = {
mbb: Mbb _ NEW[MbbRec];
link: Link;
IF edge.links=NIL THEN ERROR;
IF edge.links.rest=NIL THEN {
link _ edge.links.first;
edge.links _ NIL;
}
ELSE {
prev: LIST OF Link _ edge.links;
FOR l: LIST OF Link _ edge.links, l.rest UNTIL l.rest=NIL DO prev _ l; ENDLOOP;
link _ prev.rest.first;
prev.rest _ NIL;
};
FOR l: LIST OF Link _ edge.links, l.rest UNTIL l=NIL DO
UpdateMbb[l.first.tl, mbb];
UpdateMbb[l.first.br, mbb];
ENDLOOP;
[edge.tl, edge.br] _ TLBRFromMbb[mbb];
RETURN[link];
};
EncodeArea: PUBLIC PROC[edge: EdgeEncoding] RETURNS[AreaEncoding] = {
pathProc: ImagerPath.PathProc = {WalkEdge[edge, moveTo, lineTo, curveTo]};
addRun: PROC [sMin, fMin: INTEGER, fSize: NAT] = {
area.runs[next] _ [x: sMin, y: fMin, w: fSize];
next _ next+1;
};
next: NAT _ 0;
bottom, width: INTEGER;
isRectangle: BOOLEAN _ TRUE;
db: ImagerScanConverter.DeviceRectangle _ [
sMin: Real.RoundI[edge.tl[X]-1], fMin: Real.RoundI[edge.br[Y]-1],
sSize: Real.RoundI[edge.br[X]-edge.tl[X]+1], fSize: Real.RoundI[edge.tl[Y]-edge.br[Y]+1]];
devicePath: ImagerScanConverter.DevicePath _ ImagerScanConverter.CreatePath[path: pathProc, clipBox: db];
area: AreaEncoding _ NEW[AreaEncodingRec[ImagerScanConverter.NumberOfRuns[devicePath]]];
ImagerScanConverter.ConvertToRuns[devicePath, addRun, db];
FOR i: NAT IN [next..area.length) DO
addRun[fMin: 0, sMin: 0, fSize: 0];
ENDLOOP;
area.tl _ edge.tl;
area.br _ edge.br;
isRectangle _ TRUE;
bottom _ area.runs[0].y;
width _ area.runs[0].w;
FOR i: NAT IN [0..area.length) DO
IF area.runs[i].y#bottom OR area.runs[i].w#width THEN {isRectangle _ FALSE; EXIT};
ENDLOOP;
area.isRectangle _ isRectangle;
RETURN[area];
};
UpdateMbb: PROC [pt: ScrRealPt, mbb: Mbb] ~ {
IF pt[X] > mbb.maxX THEN mbb.maxX _ pt[X];
IF pt[Y] > mbb.maxY THEN mbb.maxY _ pt[Y];
IF pt[X] < mbb.minX THEN mbb.minX _ pt[X];
IF pt[Y] < mbb.minY THEN mbb.minY _ pt[Y];
};
TLBRFromMbb: PROC [mbb: Mbb] RETURNS [tl, br: ScrRealPt] ~ {
tl _ [mbb.minX, mbb.maxY];
br _ [mbb.maxX, mbb.minY];
};
MbbFromTLBR: PROC [tl, br: ScrRealPt] RETURNS [Mbb] ~ {
mbb: Mbb _ NEW[MbbRec];
mbb^ _ [minX: tl[X], minY: br[Y], maxX: br[X], maxY: tl[Y]];
RETURN[mbb];
};
WalkEdge: PUBLIC PROC [edge: EdgeEncoding, moveTo: ImagerPath.MoveToProc, lineTo: ImagerPath.LineToProc, curveTo: ImagerPath.CurveToProc] ~ {
first: BOOLEAN _ TRUE;
FOR l: LIST OF Link _ edge.links, l.rest UNTIL l=NIL DO
link: Link _ l.first;
IF first THEN {moveTo[link.bezier[0].b0]; first _ FALSE};
IF link.isLine THEN FOR i: NAT IN [0..link.bezier.length) DO
lineTo[link.bezier[i].b3];
ENDLOOP
ELSE FOR i: NAT IN [0..link.bezier.length) DO
curveTo[link.bezier[i].b1, link.bezier[i].b2, link.bezier[i].b3];
ENDLOOP;
ENDLOOP;
};
WalkCurve: PROC [bezier: Cubic2.Bezier, proc: PointProc, tol: REAL] ~ {
subdivide: PROC[bezier: Cubic2.Bezier] RETURNS [quit: BOOLEAN] = {
quit _ FALSE;
IF Cubic2.Flat[bezier, tol] THEN {
WalkLine[bezier.b0, bezier.b3, proc, tol];
quit _ proc[bezier.b3];
RETURN[quit];
}
ELSE {
b1, b2: Cubic2.Bezier;
[b1,b2] _ Cubic2.Split[bezier];
IF NOT subdivide[b1] THEN [] _ subdivide[b2];
};
};
IF NOT proc[bezier.b0] THEN [] _ subdivide[bezier];
};
WalkLine: PROC [p0, p1: VEC, proc: PointProc, tol: REAL] ~ {
step: REAL _ tol/Vector2.Length[Vector2.Sub[p0,p1]];
alpha: REAL _ step;
pt: VEC;
IF NOT proc[p0] THEN UNTIL alpha > 1 DO
pt _ Vector2.Add[Vector2.Mul[p1,alpha],Vector2.Mul[p0,1-alpha]];
IF proc[pt] THEN EXIT;
alpha _ alpha+step;
ENDLOOP;
};
TranslateEdge: PUBLIC PROC[edge: EdgeEncoding, offset: ScrRealPt] = {
trans: VEC _ [offset[X], offset[Y]];
edge.tl _ [offset[X]+edge.tl[X], offset[Y]+edge.tl[Y]];
edge.br _ [offset[X]+edge.br[X], offset[Y]+edge.br[Y]];
FOR l: LIST OF Link _ edge.links, l.rest UNTIL l=NIL DO
l.first.tl _ [offset[X]+l.first.tl[X], offset[Y]+l.first.tl[Y]];
l.first.br _ [offset[X]+l.first.br[X], offset[Y]+l.first.br[Y]];
FOR i: NAT IN [0..l.first.bezier.length) DO
l.first.bezier[i].b0 _ Vector2.Add[l.first.bezier[i].b0, trans];
l.first.bezier[i].b1 _ Vector2.Add[l.first.bezier[i].b1, trans];
l.first.bezier[i].b2 _ Vector2.Add[l.first.bezier[i].b2, trans];
l.first.bezier[i].b3 _ Vector2.Add[l.first.bezier[i].b3, trans];
ENDLOOP;
ENDLOOP;
}; 
TranslateArea: PUBLIC PROC[area: AreaEncoding, offset: ScrRealPt] = {
intX: INTEGER _ Real.RoundI[offset[X]];
intY: INTEGER _ Real.RoundI[offset[Y]];
area.tl _ [offset[X]+area.tl[X], offset[Y]+area.tl[Y]];
area.br _ [offset[X]+area.br[X], offset[Y]+area.br[Y]];
FOR i: NAT IN [0..area.length) DO
area[i].x _ area[i].x+intX;
area[i].y _ area[i].y+intY;
ENDLOOP;
};
PointOnEdge: PUBLIC PROC[pt: ScrPt, edge: EdgeEncoding, tol: REAL] RETURNS[BOOLEAN] = {
found: BOOLEAN _ FALSE;
scrPt: VEC _ [pt[X], pt[Y]];
tolSq: REAL _ tol*tol;
hit: PointProc = {
IF Vector2.Square[Vector2.Sub[p, scrPt]] <= tolSq THEN found _ TRUE;
RETURN[found];
};
IF Cull[edge.tl, edge.br, pt] THEN RETURN[FALSE];
FOR l: LIST OF Link _ edge.links, l.rest UNTIL l=NIL DO
link: Link _ l.first;
IF Cull[link.tl, link.br, pt] THEN LOOP;
IF link.isLine THEN FOR i: NAT IN [0..link.bezier.length) DO
WalkLine[link.bezier[i].b0, link.bezier[i].b3, hit, tol/2.0];
IF found THEN EXIT;
ENDLOOP
ELSE FOR i: NAT IN [0..link.bezier.length) DO
WalkCurve[link.bezier[i], hit, tol/2.0];
IF found THEN EXIT;
ENDLOOP;
IF found THEN EXIT;
ENDLOOP;
RETURN[found];
}; 
Cull: PROC [tl, br: ScrRealPt, pt: ScrPt] RETURNS [outside: BOOLEAN] ~ {
IF pt[X] < tl[X] OR pt[X] > br[X] OR pt[Y] < br[Y] OR pt[Y] > tl[Y] THEN RETURN[TRUE]
ELSE RETURN[FALSE];
};
PointInArea: PUBLIC PROC[pt: ScrPt, area: AreaEncoding, tol: REAL] RETURNS[BOOLEAN] = {
IF Cull[area.tl, area.br, pt] THEN RETURN[FALSE];
FOR i: NAT IN [0..area.length) DO
IF ABS[pt[X]-area[i].x] > tol
OR pt[Y] < area[i].y-tol OR pt[Y] > area[i].y+area[i].w+tol THEN LOOP 
ELSE RETURN[TRUE];
ENDLOOP;
RETURN[FALSE];
};
PointForSelectToken: PUBLIC PROC[edge: EdgeEncoding] RETURNS[ScrPt] = {
pt: ScrPt;
pt[X] _ Real.RoundI[edge.links.first.bezier[0].b3.x];
pt[Y] _ Real.RoundI[edge.links.first.bezier[0].b3.y];
RETURN[pt];
};


END.
bGriffinEncodingImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
Written by:  Maureen Stone, September 23, 1985 2:06:26 pm PDT


ScrRealPt: TYPE = PointDefs.ScrRealPt;
ScrPt: TYPE = PointDefs.ScrPt;
EdgeEncoding: TYPE = REF EdgeEncodingRec;
EdgeEncodingRec: TYPE = RECORD [tl, br: ScrRealPt, links: LIST OF Link];
Link: TYPE = RECORD[tl, br: ScrRealPt, isLine: BOOLEAN _ FALSE, bezier: REF LinkSequence]; 
LinkSequence: TYPE = RECORD[bezier: SEQUENCE length: NAT OF Cubic2.Bezier]; 
AreaEncoding: TYPE = REF AreaEncodingRec;
AreaEncodingRec: TYPE = RECORD [tl, br: ScrRealPt, runs: SEQUENCE length: NAT OF Run];
Run: TYPE = RECORD[isRectangle: BOOLEAN _ FALSE, x, y: INTEGER, w: NAT];
returns the removed link so it can be erased
Associates f with y and s with x.
Fill out the rest of the record with null values
now check for rectangles

Κι˜
codešœΟk
œ™Kšœ
Οm
œ1™<Kš
œ=™=K™—š
	˜	Kš
œ
˜
Kš
œ
˜
Kšœœ˜'K˜Kšœœ1˜AKšœœ/˜;Kšœœœ&˜8Kšœœ
˜Kš
œ˜—K™Kšœ
˜"KšœD˜KKšœ˜Kšœœ
˜˜Kšœœœ
˜Kšœœ˜Kšœœ˜Kšœœœ˜Kš	œœœ
œœ
˜IKšΟn	œœœœœœœ˜?K˜Kšœœ™&Kšœœ™Kšœœœ™)Kš	œœœœ
œ™HKšœœœœœ
œ™[Kšœœœ	œ	œ
œ™LKšœœœ™)Kšœœœœ	œ
œ™VKš
œœœœœœœ™HK˜š
Ÿœœ
œ%œ	œ˜[K˜Kšœœ
˜
Jšœœ	˜Kšœœ#˜4Kš
œ3˜3Kš
œ3˜3Kš
œ!˜!šœœ
œ˜(Kšœœ
˜K˜
Kš
œ3˜3Kš
œ3˜3Kš
œ˜K˜:K˜*Kš
œ2˜2K˜
Kšœ
˜—Kšœœ
˜K˜&Kšœ˜
K˜—šŸœœFœ
˜sKš
œ$˜$Kšœ$œ+˜RJšœœ	˜K˜šœœ
œ˜"Kšœ2˜9Kšœ
˜—Kš
œ7˜7Kšœœ˜/šœœ
œ˜#˜K˜'K˜'K˜'K˜(—K˜,Kšœ
˜—šœœ
œ˜(Kš
œ3˜3K˜*Kšœ
˜—Kšœœ
˜K˜&Kšœ˜
K˜—š
Ÿ
œœœ
œœ˜FJšœœ	˜Jšœœ˜*šœœ
œœœ
˜2Jš
œ˜Jš
œ˜Jšœ
˜—J˜&J˜Jšœ˜
K˜—šŸ
œœ!œ˜QK˜)Kšœœ
œœ˜.šœ˜Kšœœ
œ˜Kš
œœœ
œ
œ
˜7Kšœ	œ˜K˜—K˜K˜Kš
œ&˜&Kšœ˜
K˜—šŸœœ
œœ
˜AK™,Kšœœ	˜K˜Kšœœ
œ
œ
˜šœœ
œ˜K˜Kšœ
œ
˜K˜
—šœ˜Kšœœ
œ˜ Kšœœ
œœœ
œœ
˜OK˜Kšœœ
˜K˜—šœœ
œœœ
˜7K˜K˜Kšœ
˜—Kš
œ&˜&Kšœ˜
K˜—šŸ
œœœ˜EK˜JK™!šœœœ	œ˜2K˜/K˜K˜—Kšœœ˜Kšœœ
˜Kšœ
œœ
˜š
œ+˜+Kš
œA˜AKš
œZ˜Z—Kš
œi˜iKšœœ@˜XK˜:K™0šœœ
œ˜$K˜#Kšœ
˜—K˜K˜K™Kšœœ
˜K˜K˜šœœ
œ˜!Kš
œœœœœ˜RKšœ
˜—Kš
œ˜Kšœ˜
K˜—šΠbn	œœ˜-Kšœœ˜*Kšœœ˜*Kšœœ˜*Kšœœ˜*K˜—šŸœœœ˜<K˜K˜K˜—šŸœœœ
˜7Kšœœ	˜K˜<Kšœ˜K˜—šŸœœx˜
Kšœœœ
˜šœœ
œœœ
˜7K˜Kšœœ%œ˜9šœ
œ
œœ
œ˜<Kš
œ˜Kš
˜—š	œ
œœ
œ˜-Kš
œA˜AKšœ
˜—Kšœ
˜—K˜—šΟb	œœ/œ˜Gšœœœœ˜BJšœœ
˜
šœœ˜"J˜*Jš
œ˜Jšœ˜
Jš
œ
˜
—šœ˜Jš
œ˜J˜Jšœ
œœ˜-J˜—J˜—Kšœ
œœ˜3K˜—š‘œœ
œœ˜<Kšœœ*˜4Kšœœ˜Kšœœ
˜šœœ˜'K˜@Kšœ
œ
œ
˜K˜Kšœ
˜—K˜—šŸ
œœ+˜EKšœœ˜$K˜7K˜7šœœ
œœœ
˜7K˜@K˜@šœœ
œ˜+K˜@K˜@K˜@K˜@Kšœ
˜—Kšœ
˜—Kš
œ˜—šŸ
œœ
œ+˜EKšœœ˜'Kšœœ˜'K˜7K˜7šœœ
œ˜!K˜K˜Kšœ
˜—K˜—š
Ÿœœ%œœ
œ˜WKšœœœ
˜Kšœœ˜Kšœœ˜˜Kšœ0œ	œ
˜DKšœ˜K˜—Kšœœ
œ
œ˜1šœœ
œœœ
˜7K˜Kšœœ
œ
˜(šœ
œ
œœ
œ˜<Kš
œ=˜=Kšœœ
œ
˜Kš
˜—š	œ
œœ
œ˜-Kš
œ(˜(Kšœœ
œ
˜Kšœ
˜—Kšœœ
œ
˜Kšœ
˜—Kšœ˜Kš
œ˜—šŸœœ œœ˜HKšœœœœœ
œ
œ
˜UKšœ
œ
œ˜K˜—š
Ÿœœ%œœ
œ˜WKšœœ
œ
œ˜1šœœ
œ˜!šœ
œ˜Kšœœ!œ
œ
˜F—Kšœ
œ
œ˜Kšœ
˜—Kšœ
œ˜K˜—šŸœœœ˜GK˜
Kš
œ5˜5Kš
œ5˜5Kšœ˜K˜—K˜—K˜šœ
˜K™——…—$3K