<> <> <> <<>> DIRECTORY ImagerPath USING [Outline, OutlineRep, PathProc, Trajectory, TrajectoryList, TrajectoryRep], ImagerTransformation USING [Transform, Transformation], RealFns USING [ArcTanDeg, CosDeg, SinDeg, SqRt], Vector2 USING [Add, Cross, Dot, Square, Sub, VEC]; ImagerPathImpl: CEDAR PROGRAM IMPORTS ImagerTransformation, RealFns, Vector2 EXPORTS ImagerPath ~ BEGIN VEC: TYPE ~ Vector2.VEC; PathProc: TYPE ~ ImagerPath.PathProc; threshold: REAL _ 0.01; fourThirds: REAL _ 4.0/3.0; ConicToCurves: PUBLIC PROC[p0, p1, p2: VEC, r: REAL, curve: PROC[p1, p2, p3: VEC]] ~ { IF NOT (r IN [0.0..1.0]) THEN ERROR; 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)]; curve[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, curve]; ConicToCurves[p, p21, p2, rNew, curve]; }; }; ArcToConics: PUBLIC PROC[p0, p1, p2: VEC, conic: PROC[p1, p2: VEC, r: REAL]] ~ { 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 conic[Add[p0,p], Add[c,p], r]; conic[Add[p1,p], p1, r]; conic[Sub[p1,p], Sub[c,p], r]; conic[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 { <> conic[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); conic[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, conic]; ArcToConics[pMid, PointOnCircle[0.25*theta0+0.75*theta2], p2, conic]; }; }; }; }; }; Transform: PUBLIC PROC[pathProc: PathProc, pathData: REF, m: ImagerTransformation.Transformation _ NIL, moveTo: PROC[p: VEC], lineTo: PROC[p1: VEC], curveTo: PROC[p1, p2, p3: VEC], conicTo: PROC[p1, p2: VEC, r: REAL] _ NIL, close: PROC _ NIL ] ~ { p0: VEC _ [0, 0]; first: BOOL _ TRUE; move: 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; }; line: PROC[p1: VEC] ~ { IF first THEN move[p0]; IF m=NIL THEN lineTo[p1] ELSE lineTo[m.Transform[p1]]; p0 _ p1; }; curve: PROC[p1, p2, p3: VEC] ~ { IF first THEN move[p0]; IF m=NIL THEN curveTo[p1, p2, p3] ELSE curveTo[m.Transform[p1], m.Transform[p2], m.Transform[p3]]; p0 _ p3; }; conic: PROC[p1, p2: VEC, r: REAL] ~ { IF conicTo=NIL THEN ConicToCurves[p0, p1, p2, r, curve] ELSE { IF first THEN move[p0]; IF m=NIL THEN conicTo[p1, p2, r] ELSE conicTo[m.Transform[p1], m.Transform[p2], r]; p0 _ p2; }; }; arc: PROC[p1, p2: VEC] ~ { ArcToConics[p0, p1, p2, conic] }; pathProc[pathData, move, line, curve, conic, arc]; IF first THEN NULL ELSE IF close#NIL THEN close[]; }; Filter: PUBLIC PROC[pathProc: PathProc, pathData: REF, moveTo: PROC[p: VEC] _, lineTo: PROC[p1: VEC] _, curveTo: PROC[p1, p2, p3: VEC] _ NIL, conicTo: PROC[p1, p2: VEC, r: REAL] _ NIL, arcTo: PROC[p1, p2: VEC] _ NIL, close: PROC _ NIL ] ~ { p0: VEC _ [0, 0]; Eq: PROC[a, b: VEC] RETURNS[BOOL] ~ INLINE { RETURN[a.x=b.x AND a.y=b.y] }; first: BOOL _ TRUE; move: PROC[p: VEC] ~ { IF first THEN first _ FALSE ELSE IF close#NIL THEN close[]; moveTo[p]; p0 _ p; }; line: PROC[p1: VEC] ~ { IF first THEN move[p0]; IF Eq[p1, p0] THEN NULL ELSE lineTo[p1]; p0 _ p1; }; curve: PROC[p1, p2, p3: VEC] ~ { n: NAT _ 3; -- count position changes IF first THEN move[p0]; IF Eq[p0, p1] THEN n _ n-1; IF Eq[p1, p2] THEN n _ n-1; IF Eq[p2, p3] THEN n _ n-1; IF n=0 THEN NULL ELSE IF n=1 THEN line[p3] ELSE curveTo[p1, p2, p3]; p0 _ p3; }; conic: PROC[p1, p2: VEC, r: REAL] ~ { IF conicTo=NIL THEN ConicToCurves[p0, p1, p2, r, curve] ELSE { n: NAT _ 2; -- count position changes IF first THEN move[p0]; IF Eq[p0, p1] THEN n _ n-1; IF Eq[p1, p2] THEN n _ n-1; IF n=0 THEN NULL ELSE IF n=1 THEN line[p2] ELSE conicTo[p1, p2, r]; p0 _ p2; }; }; arc: PROC[p1, p2: VEC] ~ { IF arcTo=NIL THEN ArcToConics[p0, p1, p2, conic] ELSE { n: NAT _ 2; -- count position changes IF first THEN move[p0]; IF Eq[p0, p1] THEN n _ n-1; IF Eq[p1, p2] THEN n _ n-1; IF n=0 THEN NULL ELSE IF n=1 THEN line[p2] ELSE arcTo[p1, p2]; p0 _ p2; }; }; pathProc[pathData, move, line, curve, conic, arc]; IF first THEN NULL ELSE IF close#NIL THEN close[]; }; Trajectory: TYPE ~ ImagerPath.Trajectory; TrajectoryRep: TYPE ~ ImagerPath.TrajectoryRep; <> <> <> <> < [], -- begin new trajectory at lp>> < [], -- straight line, endpoints [prev.lp, lp]>> < [p1, p2: VEC], -- cubic curve, Bezier control points [prev.lp, p1, p2, lp]>> < [p1: VEC, r: REAL], -- conic curve, control points [prev.lp, p1, lp]>> < [p1: VEC], -- arc of a circle, control points [prev.lp, p1, lp]>> <> <<];>> LastPoint: PUBLIC PROC[t: Trajectory] RETURNS[VEC] ~ { RETURN[t.lp]; }; <<>> MoveTo: PUBLIC PROC[p: VEC] RETURNS[Trajectory] ~ { RETURN[NEW[TrajectoryRep[move] _ [prev: NIL, lp: p, variant: move[]]]]; }; <<>> LineTo: PUBLIC PROC[t: Trajectory, p: VEC] RETURNS[Trajectory] ~ { RETURN[NEW[TrajectoryRep[line] _ [prev: t, lp: p, variant: line[]]]]; }; <<>> LineToX: PUBLIC PROC[t: Trajectory, x: REAL] RETURNS[Trajectory] ~ { RETURN[NEW[TrajectoryRep[line] _ [prev: t, lp: [x, t.lp.y], variant: line[]]]]; }; <<>> LineToY: PUBLIC PROC[t: Trajectory, y: REAL] RETURNS[Trajectory] ~ { RETURN[NEW[TrajectoryRep[line] _ [prev: t, lp: [t.lp.x, y], variant: line[]]]]; }; <<>> CurveTo: PUBLIC PROC[t: Trajectory, p1, p2, p3: VEC] RETURNS[Trajectory] ~ { RETURN[NEW[TrajectoryRep[curve] _ [prev: t, lp: p3, variant: curve[p1, p2]]]]; }; ConicTo: PUBLIC PROC[t: Trajectory, p1, p2: VEC, r: REAL] RETURNS[Trajectory] ~ { RETURN[NEW[TrajectoryRep[conic] _ [prev: t, lp: p2, variant: conic[p1, r]]]]; }; ArcTo: PUBLIC PROC[t: Trajectory, p1, p2: VEC] RETURNS[Trajectory] ~ { RETURN[NEW[TrajectoryRep[arc] _ [prev: t, lp: p2, variant: arc[p1]]]]; }; MapTrajectory: PUBLIC PathProc ~ { <> <> end: Trajectory ~ NARROW[pathData]; moveTo[end.lp]; FOR t: Trajectory _ end, 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; }; MapTrajectoryForward: PathProc ~ { end: Trajectory ~ NARROW[pathData]; MapUpTo: PROC[t: Trajectory] ~ { IF t.prev#NIL THEN MapUpTo[t.prev]; WITH t 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 }; MapUpTo[end]; }; TrajectoryList: TYPE ~ ImagerPath.TrajectoryList; <> MapTrajectoryList: PUBLIC PathProc ~ { head: TrajectoryList ~ NARROW[pathData]; FOR list: TrajectoryList _ head, list.rest UNTIL list=NIL DO MapTrajectory[list.first, moveTo, lineTo, curveTo, conicTo, arcTo]; ENDLOOP; }; Outline: TYPE ~ ImagerPath.Outline; OutlineRep: TYPE ~ ImagerPath.OutlineRep; OutlineFromTrajectory: PUBLIC PROC[t: Trajectory] RETURNS[Outline] ~ { RETURN[NEW[OutlineRep _ [pathProc: MapTrajectory, pathData: t]]]; }; OutlineFromTrajectoryList: PUBLIC PROC[list: TrajectoryList] RETURNS[Outline] ~ { RETURN[NEW[OutlineRep _ [pathProc: MapTrajectoryList, pathData: list]]]; }; MapOutline: PUBLIC PathProc ~ { outline: Outline ~ NARROW[pathData]; outline.pathProc[outline, moveTo, lineTo, curveTo, conicTo, arcTo]; }; TransformToOutline: PUBLIC PROC[pathProc: PathProc, pathData: REF, m: ImagerTransformation.Transformation _ NIL] RETURNS[Outline] ~ { t: Trajectory _ NIL; list: TrajectoryList _ NIL; move: PROC[p: VEC] ~ { t _ MoveTo[p] }; line: PROC[p: VEC] ~ { t _ LineTo[t, p] }; 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] }; close: PROC ~ { list _ CONS[t, list] }; Transform[pathProc, pathData, m, move, line, curve, conic, close]; RETURN[OutlineFromTrajectoryList[list]]; }; END.