ImagerPathImpl.mesa
Copyright © 1984, 1985 by Xerox Corporation. All rights reserved.
Doug Wyatt, November 11, 1985 4:31:55 pm PST
Michael Plass, November 6, 1985 10:40:48 am PST
DIRECTORY
Imager USING [Error],
ImagerPath USING [ArcToProc, ConicToProc, CurveToProc, LineToProc, MoveToProc, 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 Imager, ImagerTransformation, RealFns, Vector2
EXPORTS ImagerPath
~ BEGIN OPEN ImagerPath;
VEC: TYPE ~ Vector2.VEC;
Transformation: TYPE ~ ImagerTransformation.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 Imager.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;
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
conicTo[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);
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;
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, conicTo];
ArcToConics[pMid, PointOnCircle[0.25*theta0+0.75*theta2], p2, conicTo];
};
};
};
};
};
Filter:
PUBLIC
PROC[path: PathProc,
moveTo: MoveToProc ←, lineTo: LineToProc ←, curveTo: CurveToProc ←,
conicTo: ConicToProc ←
NIL, arcTo: ArcToProc ←
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;
};
};
path[move, line, curve, conic, arc];
IF first THEN NULL ELSE IF close#NIL THEN close[];
};
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;
};
RopeFromTrajectory: PROC[t: Trajectory, backward: BOOL ← FALSE] RETURNS[Rope.ROPE] ~ {
out: IO.STREAM ~ IO.ROS[];
PutReal: PROC[out: IO.STREAM, r: REAL] ~ { IO.PutF[out, "%g ", IO.real[r]] };
PutVec: PROC[out: IO.STREAM, p: VEC] ~ { PutReal[out, p.x]; PutReal[out, p.y] };
moveTo: PROC[p0: VEC] ~ {
PutVec[out, p0];
IO.PutRope[out, "MOVETO "];
};
lineTo: PROC[p1: VEC] ~ {
PutVec[out, p1];
IO.PutRope[out, "LINETO "];
};
curveTo: PROC[p1, p2, p3: VEC] ~ {
PutVec[out, p1];
PutVec[out, p2];
PutVec[out, p3];
IO.PutRope[out, "CURVETO "];
};
conicTo: PROC[p1, p2: VEC, r: REAL] ~ {
PutVec[out, p1];
PutVec[out, p2];
PutReal[out, r];
IO.PutRope[out, "CONICTO "];
};
arcTo: PROC[p1, p2: VEC] ~ {
PutVec[out, p1];
PutVec[out, p2];
IO.PutRope[out, "ARCTO "];
};
IF backward THEN MapTrajectoryBackward[t, moveTo, lineTo, curveTo, conicTo, arcTo]
ELSE MapTrajectory[t, moveTo, lineTo, curveTo, conicTo, arcTo];
RETURN[IO.RopeFromROS[out]];
};
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.