CubicPathsImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Written by: Maureen Stone August 5, 1985 8:49:21 pm PDT
Kurlander August 15, 1986 10:08:11 am PDT
DIRECTORY
CubicPaths,
Imager USING [Rectangle, VEC],
ImagerPath USING [MoveToProc, CurveToProc],
ImagerTransformation USING [Transform, Transformation],
CubicSplines USING [CoeffsSequence, X, Y],
Vector2 USING [Square, Sub, Add, Length, Mul],
CubicPathsExtras,
Cubic2;
CubicPathsImpl: CEDAR PROGRAM
IMPORTS Cubic2, ImagerTransformation, Vector2
EXPORTS CubicPaths, CubicPathsExtras
~ BEGIN OPEN CubicPaths;
VEC: TYPE = Imager.VEC;
X: NAT = CubicSplines.X;
Y: NAT = CubicSplines.Y;
PointProc: TYPE = PROC [p: VEC] RETURNS[stop: BOOLEAN ← FALSE];
Path: TYPE = RECORD[bounds: Imager.Rectangle, cubics: REF PathSequence];
PathSequence: TYPE = RECORD[bezier: SEQUENCE length: NAT OF Cubic2.Bezier];
PathFromCubic: PUBLIC PROC[coeffs: CubicSplines.CoeffsSequence] RETURNS[Path] = {
path: Path ← NEW[PathRec];
path.cubics ← NEW[PathSequence[coeffs.length]];
FOR i: NAT IN [0..coeffs.length) DO
cfs: Cubic2.Coeffs ← [
c3: [coeffs[i].t3[X], coeffs[i].t3[Y]],
c2: [coeffs[i].t2[X], coeffs[i].t2[Y]],
c1: [coeffs[i].t1[X], coeffs[i].t1[Y]],
c0: [coeffs[i].t0[X], coeffs[i].t0[Y]]];
path.cubics[i] ← Cubic2.CoeffsToBezier[cfs];
ENDLOOP;
UpdateBounds[path];
RETURN[path];
};
EnumeratePath: PUBLIC PROC [
path: Path, moveTo: ImagerPath.MoveToProc, curveTo: ImagerPath.CurveToProc] = {
moveTo[path.cubics[0].b0];
FOR i: NAT IN [0..path.cubics.length) DO
curveTo[path.cubics[i].b1, path.cubics[i].b2, path.cubics[i].b3];
ENDLOOP;
};
WalkPath: PUBLIC PROC[path: Path, tol: REAL, proc: PointProc] = {
subdivide: PROC[bezier: Cubic2.Bezier] RETURNS [quit: BOOLEAN]= {
quit ← FALSE;
IF Cubic2.Flat[bezier, tol] THEN {
len: REAL ← Vector2.Length[Vector2.Sub[bezier.b0, bezier.b3]];
IF len > 0 THEN {
step: REAL ← tol/len;
alpha: REAL ← step;
pt: VEC;
UNTIL alpha > 1 DO
pt ← Vector2.Add[Vector2.Mul[bezier.b3,alpha],Vector2.Mul[bezier.b0,1-alpha]];
IF proc[pt] THEN {quit ← TRUE; EXIT};
alpha ← alpha+step;
ENDLOOP;
}
ELSE quit ← proc[bezier.b3];
RETURN[quit]}
ELSE {
b1, b2: Cubic2.Bezier;
[b1,b2] ← Cubic2.Split[bezier];
IF NOT subdivide[b1] THEN [] ← subdivide[b2];
};
};
IF NOT proc[path.cubics[0].b0] THEN FOR i: NAT IN [0..path.cubics.length) DO
[] ← subdivide[path.cubics[i]];
ENDLOOP;
};
PointOnPath: PUBLIC PROC[pt: VEC, path: Path, tol: REAL] RETURNS[BOOLEAN] = {
tolSq: REAL ← tol*tol;
found: BOOLEAN ← FALSE;
hit: PointProc = {
IF Vector2.Square[Vector2.Sub[p, pt]] <= tolSq THEN found ← TRUE;
RETURN[found];
};
IF pt.x < path.bounds.x OR pt.y < path.bounds.y OR pt.x>(path.bounds.x+path.bounds.w)
OR pt.y > (path.bounds.y+path.bounds.h) THEN RETURN[FALSE]
ELSE WalkPath[path, tol, hit];
RETURN[found];
};
TranslatePath: PUBLIC PROC[path: Path, offset: VEC] = {
FOR i: NAT IN [0..path.cubics.length) DO
path.cubics[i].b0 ← Vector2.Add[offset, path.cubics[i].b0];
path.cubics[i].b1 ← Vector2.Add[offset, path.cubics[i].b1];
path.cubics[i].b2 ← Vector2.Add[offset, path.cubics[i].b2];
path.cubics[i].b3 ← Vector2.Add[offset, path.cubics[i].b3];
ENDLOOP;
path.bounds.x ← path.bounds.x+offset.x;
path.bounds.y ← path.bounds.y+offset.y;
};
TransformPath: PUBLIC PROC[path: Path, tranformation: ImagerTransformation.Transformation] = {
pt: VEC ← [path.bounds.x, path.bounds.y];
FOR i: NAT IN [0..path.cubics.length) DO
path.cubics[i].b0 ← ImagerTransformation.Transform[tranformation, path.cubics[i].b0];
path.cubics[i].b1 ← ImagerTransformation.Transform[tranformation, path.cubics[i].b1];
path.cubics[i].b2 ← ImagerTransformation.Transform[tranformation, path.cubics[i].b2];
path.cubics[i].b3 ← ImagerTransformation.Transform[tranformation, path.cubics[i].b3];
ENDLOOP;
UpdateBounds[path];
};
UpdateBounds: PUBLIC PROC[path: Path] = {
minX, minY: REAL ← 10E6;
maxX, maxY: REAL ← -10E6;
pointProc: PointProc = {
IF p.x > maxX THEN maxX ← p.x;
IF p.y > maxY THEN maxY ← p.y;
IF p.x < minX THEN minX ← p.x;
IF p.y < minY THEN minY ← p.y;
};
WalkPath[path, 1.0, pointProc];
path.bounds ← [x: minX, y: minY, w: maxX-minX, h: maxY-minY];
};
CubicPathsExtras all below plus made UpdateBounds Public
ClosestPoint: PUBLIC PROC[pt: VEC, path: Path] RETURNS[VEC] = {
closest: VEC ← path.cubics[0].b0;
minD: REAL ← 10E6;
test: PointProc = {
thisD: REAL ← Vector2.Square[Vector2.Sub[p, pt]];
IF thisD < minD THEN {closest ← p; minD ← thisD};
};
WalkPath[path, 1.0, test];
RETURN[closest];
};
CopyPath: PUBLIC PROC[path: Path] RETURNS[Path] = {
new: Path ← NEW[PathRec];
new.cubics ← NEW[PathSequence[path.cubics.length]];
FOR i: NAT IN [0..path.cubics.length) DO
new.cubics[i] ← path.cubics[i];
ENDLOOP;
new.bounds ← path.bounds;
RETURN[new];
};
ReversePath: PUBLIC PROC[path: Path] = { --reverses it in place
last: NAT ← path.cubics.length-1;
FOR i: NAT IN [0..path.cubics.length/2) DO
temp: Cubic2.Bezier ← path.cubics[i];
path.cubics[i] ← path.cubics[last-i];
path.cubics[last-i] ← temp;
ENDLOOP;
FOR i: NAT IN [0..path.cubics.length) DO
temp: VEC ← path.cubics[i].b0;
path.cubics[i].b0 ← path.cubics[i].b3;
path.cubics[i].b3 ← temp;
temp ← path.cubics[i].b1;
path.cubics[i].b1 ← path.cubics[i].b2;
path.cubics[i].b2 ← temp;
ENDLOOP;
};
END.