<<>> <> <> <> <> <> <<>> DIRECTORY Imager USING [Error], ImagerPath USING [ArcToProc, ConicToProc, CurveToProc, LineToProc, MoveToProc, Outline, OutlineRep, PathProc, Trajectory, TrajectoryList, TrajectoryRep], ImagerTransformation USING [Transform, Transformation], Real USING [FScale], RealFns USING [ArcTanDeg, CosDeg, SinDeg, SqRt], RealInline USING [IsValid], Vector2 USING [Add, Cross, Dot, Square, Sub, VEC]; ImagerPathImpl: CEDAR PROGRAM IMPORTS Imager, ImagerTransformation, Real, RealFns, RealInline, Vector2 EXPORTS ImagerPath ~ BEGIN OPEN ImagerPath; VEC: TYPE ~ Vector2.VEC; Transformation: TYPE ~ ImagerTransformation.Transformation; fourThirds: REAL ~ 1.333333; ConicToCurves: PUBLIC PROC [p0, p1, p2: VEC, r: REAL, curveTo: CurveToProc] ~ { IF NOT RealInline.IsValid[r] OR r < 0.0 OR r > 1.0 THEN ERROR Imager.Error[[$bounds, "The ratio r in conic specification must be in [0..1]"]]; IF r IN [0.4641..0.533] -- allows a relative error of about 0.1%; allows arcs of up to 60 degrees to come through as one piece THEN { f: REAL ~ fourThirds*r; p01: VEC ~ [p0.x+f*(p1.x-p0.x), p0.y+f*(p1.y-p0.y)]; p21: VEC ~ [p2.x+f*(p1.x-p2.x), p2.y+f*(p1.y-p2.y)]; curveTo[p01, p21, p2]; } ELSE { m: VEC ~ [(p0.x+p2.x)*0.5, (p0.y+p2.y)*0.5]; p: VEC ~ [m.x+r*(p1.x-m.x), m.y+r*(p1.y-m.y)]; p01: VEC ~ [p0.x+r*(p1.x-p0.x), p0.y+r*(p1.y-p0.y)]; p21: VEC ~ [p2.x+r*(p1.x-p2.x), p2.y+r*(p1.y-p2.y)]; rNew: REAL ~ MIN[1.0/(1.0+RealFns.SqRt[2.0*(1-r)]), 0.99999]; ConicToCurves[p0, p01, p, rNew, curveTo]; ConicToCurves[p, p21, p2, rNew, curveTo]; }; }; ArcToConics: PUBLIC PROC [p0, p1, p2: VEC, conicTo: ConicToProc] ~ { OPEN Vector2; DistSqr: PROC [a, b: VEC] RETURNS [REAL] ~ INLINE { RETURN[Square[Sub[a, b]]] }; IF (p0.x = p2.x) AND (p0.y = p2.y) THEN { c: VEC ~ [(p0.x+p1.x)*0.5, (p0.y+p1.y)*0.5]; -- center of the circle v: VEC ~ [p0.x-c.x, p0.y-c.y]; -- vector from center to p0 p: VEC ~ [-v.y, v.x]; -- v rotated by +90 degrees r: REAL ~ RealFns.SqRt[2.0]-1.0; -- conic ratio for a 90 degree arc conicTo[Add[p0,p], Add[c,p], r]; conicTo[Add[p1,p], p1, r]; conicTo[Sub[p1,p], Sub[c,p], r]; conicTo[Sub[p2,p], p2, r]; } ELSE { sgn: REAL ~ IF Cross[Sub[p1,p0], Sub[p2,p0]] >= 0 THEN 1.0 ELSE -1.0; <> distProd: REAL ~ RealFns.SqRt[DistSqr[p0,p1]*DistSqr[p2,p1]]; IF distProd = 0 THEN { <> conicTo[p1,p2,0.5]; } ELSE { dot: REAL ~ Dot[Sub[p0,p1], Sub[p2,p1]]; cos: REAL ~ -dot/distProd; <> IF cos>=0.5 THEN { tan: REAL ~ Cross[Sub[p0,p1], Sub[p2,p1]]/dot; m: VEC ~ [(p0.x+p2.x)*0.5, (p0.y+p2.y)*0.5]; p: VEC ~ [tan*(m.y-p0.y)+m.x, tan*(p0.x-m.x)+m.y]; r: REAL ~ cos/(1.0+cos); conicTo[p, p2, r]; } ELSE { m1: VEC ~ [(p0.x+p1.x)*0.5, (p0.y+p1.y)*0.5]; -- midpoint of segment from p0 to p1 v1: VEC ~ [m1.y-p0.y, p0.x-m1.x]; -- direction vector of perpendicular bisector a1: REAL ~ v1.y; b1: REAL ~ -v1.x; c1: REAL ~ a1*m1.x+b1*m1.y; <> m2: VEC ~ [(p0.x+p2.x)*0.5, (p0.y+p2.y)*0.5]; v2: VEC ~ [m2.y-p0.y, p0.x-m2.x]; a2: REAL ~ v2.y; b2: REAL ~ -v2.x; c2: REAL ~ a2*m2.x+b2*m2.y; det: REAL ~ a1*b2-a2*b1; Center: PROC RETURNS [VEC] ~ INLINE { <<*** Possible side effect on p1 in degenerate case>> IF det = 0 OR ABS[det] < ABS[a1*b2]*0.000005 THEN { <> v: VEC ¬ Add[v1, v2]; m: REAL; IF DistSqr[v1, v2] > v.x*v.x + v.y*v.y THEN v ¬ Sub[v1, v2]; <> m ¬ 4.0E+6/RealFns.SqRt[v.x*v.x + v.y*v.y]; <> <> p1 ¬ [2.0*m*v.x, 2.0*m*v.y]; RETURN [[m*v.x, m*v.y]]; } ELSE RETURN [[(c1*b2-c2*b1)/det, (a1*c2-a2*c1)/det]]; }; center: VEC ~ Center[]; theta0: REAL ~ RealFns.ArcTanDeg[p0.y-center.y, p0.x-center.x]; theta1: REAL ¬ RealFns.ArcTanDeg[p1.y-center.y, p1.x-center.x]; theta2: REAL ¬ RealFns.ArcTanDeg[p2.y-center.y, p2.x-center.x]; WHILE theta1 - theta0 < 0 DO theta1 ¬ theta1 + 360 ENDLOOP; WHILE theta2 - theta0 < 0 DO theta2 ¬ theta2 + 360 ENDLOOP; IF theta2 < theta1 THEN {theta1 ¬ theta1 - 360; theta2 ¬ theta2 - 360}; IF (theta1 - theta0)*(theta2 - theta0) < 0 THEN ERROR ELSE { radius: REAL ¬ RealFns.SqRt[DistSqr[center, p0]]; PointOnCircle: PROC [theta: REAL] RETURNS [VEC] ~ INLINE { RETURN [[center.x+radius*RealFns.CosDeg[theta], center.y+radius*RealFns.SinDeg[theta]]] }; pMid: VEC ¬ PointOnCircle[(theta0+theta2)*0.5]; ArcToConics[p0, PointOnCircle[0.75*theta0+0.25*theta2], pMid, conicTo]; ArcToConics[pMid, PointOnCircle[0.25*theta0+0.75*theta2], p2, conicTo]; }; }; }; }; }; Half: PROC [r: REAL] RETURNS [REAL] ~ INLINE { RETURN [Real.FScale[r, -1]] }; Mid: PROC [p, q: VEC] RETURNS [VEC] ~ INLINE { RETURN [[Half[p.x+q.x], Half[p.y+q.y]]] }; Eq: PROC [a, b: VEC] RETURNS [BOOL] ~ INLINE {RETURN [a.x=b.x AND a.y=b.y]}; <> Transform: PUBLIC PROC [path: PathProc, m: Transformation ¬ NIL, moveTo: MoveToProc ¬, lineTo: LineToProc ¬, curveTo: CurveToProc ¬, conicTo: ConicToProc ¬ NIL, arcTo: ArcToProc ¬ NIL, close: PROC ¬ NIL] ~ { first: BOOL ¬ TRUE; p0: VEC ¬ [0, 0]; -- in path's coordinates, not transformed TransformMoveTo: PROC [p: VEC] ~ { IF first THEN first ¬ FALSE ELSE { IF close#NIL THEN close[] }; IF m=NIL THEN moveTo[p] ELSE moveTo[m.Transform[p]]; p0 ¬ p; }; TransformLineTo: PROC [p1: VEC] ~ { IF first THEN TransformMoveTo[p0]; IF m=NIL THEN lineTo[p1] ELSE lineTo[m.Transform[p1]]; p0 ¬ p1; }; TransformCurveTo: PROC [p1, p2, p3: VEC] ~ { IF first THEN TransformMoveTo[p0]; IF m=NIL THEN curveTo[p1, p2, p3] ELSE curveTo[m.Transform[p1], m.Transform[p2], m.Transform[p3]]; p0 ¬ p3; }; TransformConicTo: PROC [p1, p2: VEC, r: REAL] ~ { IF conicTo=NIL THEN GOTO Curves; IF first THEN TransformMoveTo[p0]; IF m=NIL THEN conicTo[p1, p2, r] ELSE conicTo[m.Transform[p1], m.Transform[p2], r]; p0 ¬ p2; EXITS Curves => ConicToCurves[p0, p1, p2, r, TransformCurveTo]; }; TransformArcTo: PROC [p1, p2: VEC] ~ { IF arcTo=NIL THEN GOTO Conics; IF m#NIL THEN GOTO Conics; -- in general, can't just transform control points <<-- could test for special cases of m here (uniform scaling, for example)>> IF first THEN TransformMoveTo[p0]; arcTo[p1, p2]; p0 ¬ p2; EXITS Conics => ArcToConics[p0, p1, p2, TransformConicTo]; }; path[moveTo: TransformMoveTo, lineTo: TransformLineTo, curveTo: TransformCurveTo, conicTo: TransformConicTo, arcTo: TransformArcTo]; IF first THEN NULL ELSE { IF close#NIL THEN close[] }; }; LastPoint: PUBLIC PROC [t: Trajectory] RETURNS [VEC] ~ { RETURN[t.lp]; }; <<>> MoveTo: PUBLIC PROC [p: VEC] RETURNS [Trajectory] ~ { RETURN[NEW[TrajectoryRep[move] ¬ [ prev: NIL, length: 1, lp: p, variant: move[]]]]; }; <<>> LineTo: PUBLIC PROC [t: Trajectory, p1: VEC] RETURNS [Trajectory] ~ { RETURN[NEW[TrajectoryRep[line] ¬ [ prev: t, length: t.length+1, lp: p1, variant: line[]]]]; }; <<>> LineToX: PUBLIC PROC [t: Trajectory, x: REAL] RETURNS [Trajectory] ~ { RETURN[NEW[TrajectoryRep[line] ¬ [ prev: t, length: t.length+1, lp: [x, t.lp.y], variant: line[]]]]; }; <<>> LineToY: PUBLIC PROC [t: Trajectory, y: REAL] RETURNS [Trajectory] ~ { RETURN[NEW[TrajectoryRep[line] ¬ [ prev: t, length: t.length+1, lp: [t.lp.x, y], variant: line[]]]]; }; <<>> CurveTo: PUBLIC PROC [t: Trajectory, p1, p2, p3: VEC] RETURNS [Trajectory] ~ { RETURN[NEW[TrajectoryRep[curve] ¬ [ prev: t, length: t.length+1, lp: p3, variant: curve[p1, p2]]]]; }; ConicTo: PUBLIC PROC [t: Trajectory, p1, p2: VEC, r: REAL] RETURNS [Trajectory] ~ { RETURN[NEW[TrajectoryRep[conic] ¬ [ prev: t, length: t.length+1, lp: p2, variant: conic[p1, r]]]]; }; ArcTo: PUBLIC PROC [t: Trajectory, p1, p2: VEC] RETURNS [Trajectory] ~ { RETURN[NEW[TrajectoryRep[arc] ¬ [ prev: t, length: t.length+1, lp: p2, variant: arc[p1]]]]; }; MapTrajectory: PUBLIC PROC [trajectory: Trajectory, moveTo: MoveToProc, lineTo: LineToProc, curveTo: CurveToProc, conicTo: ConicToProc, arcTo: ArcToProc] ~ { Map: PROC [trajectory: Trajectory, length: INT] ~ { max: NAT ~ 16; array: ARRAY[0..max) OF Trajectory; size: NAT ~ MIN[length, max]; n: INT ~ IF length>size THEN length/size ELSE 1; rem: INT ~ length-n*size; t: Trajectory ¬ trajectory; FOR i: NAT IN[0..size) DO array[i] ¬ t; THROUGH [0..n) DO t ¬ t.prev ENDLOOP; ENDLOOP; IF rem>0 THEN Map[t, rem]; IF n>1 THEN FOR i: NAT DECREASING IN[0..size) DO Map[array[i], n] ENDLOOP ELSE FOR i: NAT DECREASING IN[0..size) DO WITH array[i] SELECT FROM t: REF TrajectoryRep[move] => moveTo[t.lp]; t: REF TrajectoryRep[line] => lineTo[t.lp]; t: REF TrajectoryRep[curve] => curveTo[t.p1, t.p2, t.lp]; t: REF TrajectoryRep[conic] => conicTo[t.p1, t.lp, t.r]; t: REF TrajectoryRep[arc] => arcTo[t.p1, t.lp]; ENDCASE => ERROR; -- unknown variant ENDLOOP; }; Map[trajectory, trajectory.length]; }; MapTrajectoryBackward: PUBLIC PROC [trajectory: Trajectory, moveTo: MoveToProc, lineTo: LineToProc, curveTo: CurveToProc, conicTo: ConicToProc, arcTo: ArcToProc] ~ { moveTo[trajectory.lp]; FOR t: Trajectory ¬ trajectory, t.prev UNTIL t.prev=NIL DO p0: VEC ~ t.prev.lp; WITH t SELECT FROM t: REF TrajectoryRep[move] => ERROR; -- should have had t.prev=NIL t: REF TrajectoryRep[line] => lineTo[p0]; t: REF TrajectoryRep[curve] => curveTo[t.p2, t.p1, p0]; t: REF TrajectoryRep[conic] => conicTo[t.p1, p0, t.r]; t: REF TrajectoryRep[arc] => arcTo[t.p1, p0]; ENDCASE => ERROR; -- unknown variant ENDLOOP; }; <> <> <> <> <> <> <> <<};>> <> <> <> <<};>> <> <> <> <> <> <<};>> <> <> <> <> <> <<};>> <> <> <> <> <<};>> <> <> <> <> <<};>> <<>> MapTrajectoryList: PUBLIC PROC [trajectoryList: TrajectoryList, moveTo: MoveToProc, lineTo: LineToProc, curveTo: CurveToProc, conicTo: ConicToProc, arcTo: ArcToProc] ~ { FOR list: TrajectoryList ¬ trajectoryList, list.rest UNTIL list=NIL DO MapTrajectory[list.first, moveTo, lineTo, curveTo, conicTo, arcTo]; ENDLOOP; }; MapOutline: PUBLIC PROC [outline: Outline, moveTo: MoveToProc, lineTo: LineToProc, curveTo: CurveToProc, conicTo: ConicToProc, arcTo: ArcToProc] ~ { FOR i: NAT IN [0..outline.size) DO MapTrajectory[outline[i], moveTo, lineTo, curveTo, conicTo, arcTo]; ENDLOOP; }; TrajectoriesFromPath: PUBLIC PROC [path: PathProc, m: Transformation ¬ NIL, action: PROC [Trajectory]] ~ { t: Trajectory ¬ NIL; move: PROC [p: VEC] ~ { t ¬ MoveTo[p] }; line: PROC [p1: VEC] ~ { t ¬ LineTo[t, p1] }; curve: PROC [p1, p2, p3: VEC] ~ { t ¬ CurveTo[t, p1, p2, p3] }; conic: PROC [p1, p2: VEC, r: REAL] ~ { t ¬ ConicTo[t, p1, p2, r] }; arc: PROC [p1, p2: VEC] ~ { t ¬ ArcTo[t, p1, p2] }; close: PROC ~ { action[t] }; Transform[path, m, move, line, curve, conic, arc, close]; }; TrajectoryListFromPath: PUBLIC PROC [path: PathProc, m: Transformation ¬ NIL] RETURNS [list: TrajectoryList ¬ NIL] ~ { tail: TrajectoryList ¬ NIL; action: PROC [t: Trajectory] ~ { new: TrajectoryList ~ CONS[t, NIL]; IF tail=NIL THEN list ¬ new ELSE tail.rest ¬ new; tail ¬ new; }; TrajectoriesFromPath[path, m, action]; }; OutlineFromPath: PUBLIC PROC [path: PathProc, oddWrap: BOOL ¬ FALSE, m: Transformation ¬ NIL] RETURNS [outline: Outline ¬ NIL] ~ { head: LIST OF Trajectory ¬ NIL; tail: LIST OF Trajectory ¬ NIL; size: NAT ¬ 0; action: PROC [t: Trajectory] ~ { IF size < frontSize THEN front[size] ¬ t ELSE { new: LIST OF Trajectory ¬ LIST[t]; IF tail = NIL THEN head ¬ new ELSE tail.rest ¬ new; tail ¬ new; }; size ¬ size+1; }; front: ARRAY [0..frontSize) OF Trajectory ¬ ALL[NIL]; frontSize: NAT = 40; TrajectoriesFromPath[path, m, action]; outline ¬ NEW[OutlineRep[size]]; outline.oddWrap ¬ oddWrap; size ¬ MIN[size, frontSize]; FOR i: NAT IN [0..size) DO outline[i] ¬ front[i] ENDLOOP; WHILE head # NIL DO tail ¬ head.rest; head.rest ¬ NIL; outline[size] ¬ head.first; head.first ¬ NIL; size ¬ size + 1; head ¬ tail; ENDLOOP; }; END.