ImagerPathImpl.mesa
Copyright © 1984, Xerox Corporation. All rights reserved.
Doug Wyatt, November 8, 1984 10:06:20 am PST
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;
positive if arc is counterclockwise
distProd: REAL ~ RealFns.SqRt[DistSqr[p0,p1]*DistSqr[p2,p1]];
IF distProd = 0
THEN {
p1 coincides with p0 or p2 - shame, shame
conic[p1,p2,0.5];
}
ELSE {
dot: REAL ~ Dot[Sub[p0,p1], Sub[p2,p1]];
cos:
REAL ~ -dot/distProd;
cos of 1/2 the angle subtended by the arc
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;
a1*x + b1*y = c1 is the equation of the perpendicular bisector
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 {
The determinant is zero, or the calculation has lost most of its significant digits; in this case the points are practically collinear, but p1 is not between the other two. Pick as the center a point way out in the boonies, but in the right direction.
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];
Not so big that later calls on ArcToConics will overflow.
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;
RECORD[
prev: Trajectory, -- link to preceding trajectory
lp: VEC, -- the last point
variant: SELECT tag: * FROM
move => [], -- begin new trajectory at lp
line => [], -- straight line, endpoints [prev.lp, lp]
curve => [p1, p2: VEC], -- cubic curve, Bezier control points [prev.lp, p1, p2, lp]
conic => [p1: VEC, r: REAL], -- conic curve, control points [prev.lp, p1, lp]
arc => [p1: VEC], -- arc of a circle, control points [prev.lp, p1, lp]
ENDCASE
];
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 ~ {
Maps the Trajectory backward, starting with the most recently added segment.
Avoids the procedure calls and possible deep recursion in MapTrajectoryForward (below).
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;
LIST OF Trajectory;
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.