<> <> <> <> <<>> DIRECTORY II USING [Error], IIPath USING [ArcToProc, ConicToProc, CurveToProc, LineToProc, MoveToProc, Outline, OutlineRep, PathProc, Trajectory, TrajectoryList, TrajectoryRep], IITransformation USING [Transform, Transformation], Real USING [FScale], RealFns USING [ArcTanDeg, CosDeg, SinDeg, SqRt], Vector2 USING [Add, Cross, Dot, Square, Sub, VEC]; IIPathImpl: CEDAR PROGRAM IMPORTS II, IITransformation, Real, RealFns, Vector2 EXPORTS IIPath ~ BEGIN OPEN IIPath; VEC: TYPE ~ Vector2.VEC; Transformation: TYPE ~ IITransformation.Transformation; threshold: REAL _ 0.01; fourThirds: REAL _ 4.0/3.0; ConicToCurves: PUBLIC PROC[p0, p1, p2: VEC, r: REAL, curveTo: CurveToProc] ~ { IF NOT (r IN [0.0..1.0]) THEN ERROR II.Error[[$specification, "The ratio r in conic specification must be in [0..1]"]]; IF ABS[r-0.5]<=threshold 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] ~ { RETURN[Square[Sub[a, b]]] }; IF p0 = p2 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 _ 1.0E+9/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] ~ { 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]}; <> <> <> < 0.0 THEN tolerance ELSE defaultTolerance;>> <<
>> <<};>> <<>> 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] ~ { list: LIST OF Trajectory _ NIL; size: NAT _ 0; action: PROC[t: Trajectory] ~ { list _ CONS[t, list]; size _ size+1 }; TrajectoriesFromPath[path, m, action]; outline _ NEW[OutlineRep[size] _ [oddWrap: oddWrap, seq: ]]; FOR i: NAT DECREASING IN[0..size) DO outline[i] _ list.first; list _ list.rest ENDLOOP; }; END.