DIRECTORY
Cubic2 USING [Bezier, Coeffs, CoeffsToBezier, Flat, Split],
CubicSplines USING [Coeffs, CoeffsSequence, MakeSpline, SplineType],
GriffinEncoding USING [AreaEncoding, AreaEncodingRec, EdgeEncoding, EdgeEncodingRec, Link, LinkSequence, ScrPt, ScrRealPt],
GriffinPoint USING [ObjPtSequence, ObjPtSequenceRec, ObjToScrReal, ObjValToScrVal, X, Y],
ImagerPath USING [CurveToProc, LineToProc, MoveToProc, PathProc],
ImagerScanConverter USING [ConvertToRuns, CreatePath, DevicePath, DeviceRectangle, NumberOfRuns],
Real USING [RoundI],
Vector2 USING [Add, Div, Length, Mul, Square, Sub, VEC];
GriffinEncodingImpl:
CEDAR
PROGRAM
IMPORTS Cubic2, CubicSplines, GriffinPoint, ImagerScanConverter, Real, Vector2
EXPORTS GriffinEncoding = BEGIN OPEN GriffinEncoding;
VEC: TYPE = Vector2.VEC;
X: NAT ← GriffinPoint.X;
Y: NAT ← GriffinPoint.Y;
MbBox: TYPE = RECORD[minX, minY: REAL ← 10E6, maxX, maxY: REAL ← -10E6];
PointProc: TYPE = PROC [p: VEC] RETURNS [stop: BOOLEAN ← FALSE];
ScrRealPt: TYPE = GriffinPoint.ScrRealPt;
ScrPt: TYPE = GriffinPoint.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];
EncodeLinearLink:
PUBLIC
PROC [endpoints: GriffinPoint.ObjPtSequence]
RETURNS [Link] =
TRUSTED {
link: Link;
prev: VEC;
mbb: MbBox ← [];
IF endpoints.length = 1
THEN {
-- make a dot
point: VEC ← [x: GriffinPoint.ObjValToScrVal[endpoints[0][X]], y: GriffinPoint.ObjValToScrVal[endpoints[0][Y]]];
link.bezier ← NEW[LinkSequence[1]];
link.bezier[0] ← [b0: point, b1: point, b2: point, b3: point]; --single point degenerate spline
mbb ← UpdateMbb[[point.x, point.y], mbb];
}
ELSE {
link.bezier ← NEW[LinkSequence[endpoints.length-1]];
prev.x ← GriffinPoint.ObjValToScrVal[endpoints[0][X]];
prev.y ← GriffinPoint.ObjValToScrVal[endpoints[0][Y]];
mbb ←UpdateMbb[[prev.x, prev.y], mbb];
FOR i:
NAT
IN [0..link.bezier.length)
DO
b0, b1, b2, b3: VEC;
b0 ← prev;
b3.x ← GriffinPoint.ObjValToScrVal[endpoints[i+1][X]];
b3.y ← GriffinPoint.ObjValToScrVal[endpoints[i+1][Y]];
mbb ← 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: GriffinPoint.ObjPtSequence, splineType: CubicSplines.SplineType]
RETURNS [Link] = {
coeffs: CubicSplines.CoeffsSequence;
newKnots: GriffinPoint.ObjPtSequence ← NEW[GriffinPoint.ObjPtSequenceRec[knots.length]];
mbb: MbBox ← [];
link: Link;
FOR i:
NAT
IN [0..knots.length)
DO
TRUSTED {newKnots[i] ← GriffinPoint.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 = {mbb ← 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: MbBox ← [];
edge: EdgeEncoding ← NEW[EdgeEncodingRec];
FOR l:
LIST
OF Link ← links, l.rest
UNTIL l=
NIL
DO
mbb ← UpdateMbb[l.first.tl, mbb];
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: MbBox ← MbbFromTLBR[edge.tl, edge.br];
IF edge.links=
NIL
THEN edge.links ←
LIST[link]
FOR l ← edge.links, l.rest UNTIL l.rest=NIL DO ENDLOOP;
l.rest ← LIST[link];
};
mbb ← UpdateMbb[link.tl, mbb];
mbb ← UpdateMbb[link.br, mbb];
[edge.tl, edge.br] ← TLBRFromMbb[mbb];
RETURN[edge];
};
RemoveLastLink:
PUBLIC
PROC [edge: EdgeEncoding]
RETURNS [Link] = {
returns the removed link so it can be erased
mbb: MbBox ← [];
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
mbb ← UpdateMbb[l.first.tl, mbb];
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]};
Associates f with y and s with x.
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 ← FALSE;
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];
Fill out the rest of the record with null values
FOR i:
NAT
IN [next..area.length)
DO
addRun[fMin: 0, sMin: 0, fSize: 0];
ENDLOOP;
area.tl ← edge.tl;
area.br ← edge.br;
IF area.length#0
THEN {
now check for rectangles
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: GriffinEncoding.ScrRealPt, mbb: MbBox]
RETURNS [newMbb: MbBox] = {
newMbb.maxX ← MAX[mbb.maxX, pt[X]];
newMbb.maxY ← MAX[mbb.maxY, pt[Y]];
newMbb.minX ← MIN[mbb.minX, pt[X]];
newMbb.minY ← MIN[mbb.minY, pt[Y]];
};
TLBRFromMbb:
PROC [mbb: MbBox]
RETURNS [tl, br: GriffinEncoding.ScrRealPt] ~ {
tl ← [mbb.minX, mbb.maxY];
br ← [mbb.maxX, mbb.minY];
};
MbbFromTLBR:
PROC [tl, br: GriffinEncoding.ScrRealPt]
RETURNS [MbBox] ~ {
RETURN[ [minX: tl[X], minY: br[Y], maxX: br[X], maxY: tl[Y]] ];
};
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 bezier.b0 = bezier.b1
AND bezier.b0 = bezier.b2
AND bezier.b0 = bezier.b3
THEN {
[] ← proc[bezier.b0]; RETURN;}; --degenerate curve
IF NOT proc[bezier.b0] THEN [] ← subdivide[bezier];
};
WalkLine:
PROC [p0, p1:
VEC, proc: PointProc, tol:
REAL] ~ {
step, alpha: REAL;
pt: VEC;
IF p0=p1 THEN {[] ← proc[p0]; RETURN}; --degenerate line
step ← alpha ← tol/Vector2.Length[Vector2.Sub[p0, p1]];
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: GriffinEncoding.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: GriffinEncoding.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: GriffinEncoding.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: GriffinEncoding.ScrRealPt, pt: GriffinEncoding.ScrPt]
RETURNS [
BOOLEAN] = {
RETURN[pt[X]<tl[X] OR pt[X]>br[X] OR pt[Y]<br[Y] OR pt[Y]>tl[Y]];
};
PointInArea:
PUBLIC
PROC [pt: GriffinEncoding.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 [GriffinEncoding.ScrPt] = {
pt: GriffinEncoding.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];
};