ImagerPathImpl.mesa
Copyright Ó 1984, 1985, 1986, 1988, 1990, 1991 by Xerox Corporation. All rights reserved.
Doug Wyatt, November 11, 1985 4:31:55 pm PST
Michael Plass, May 28, 1993 12:37 pm PDT
Russ Atkinson (RRA) July 3, 1991 3:41 pm PDT
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;
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];>>
m ¬ 4.0E+6/RealFns.SqRt[v.x*v.x + v.y*v.y];
Not so big that later calls on ArcToConics will overflow.
Reduced from 1.0E+9 by MFP (March 8, 1990) - when we hit this case it leads to a HUGE circle; if the device space is of the order of 10^5 pixels, the center should end up 25 pages away, which ought to be pretty similar in appearance to a center at infinity.
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]};
This is needed to prevent confusion about minus zero.
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] ~ {
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.