<> <> <> <> <<>> 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]; <> <> <> <> <> <> <> <> <> 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] ELSE { l: LIST OF 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] = { <> 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]}; <> 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]; <> 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 { <> 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]br[X] 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]; }; END.