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;
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];
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];
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] = {
returns the removed link so it can be erased
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]};
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 ← 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];
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;
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: 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];
};