-- AreaPathImpl.mesa
-- Last changed by Doug Wyatt, September 15, 1980 4:45 PM

DIRECTORY
Path,
AreaPath,
Vector USING [Vec, Sub, Eq, Cross],
Cubic USING [Coeffs, Bezier, CoeffsToBezier, BezierPolygon],
Area USING [Handle],
Poly USING [Handle, New, Put, NewArea, Free, NewRec],
Pipe USING [Handle, Put, Free],
Reducer USING [Handle, Pairing, NewReducer, Vertex, NewBoundary, Generate, Free],
Boxer USING [Handle, New, Put, Rectangle, Free],
Clipper USING [Handle, NewPipe],
Memory USING [zone];

AreaPathImpl: PROGRAM
IMPORTS Vector,Cubic,Poly,Pipe,Reducer,Boxer,Clipper,Memory
EXPORTS AreaPath SHARES Path = {
OPEN Path;

zone: UNCOUNTED ZONE = Memory.zone;

Sense: TYPE = {none, positive, negative};
Count: TYPE = {one, two, more};

Data: PUBLIC TYPE = RECORD [
oddEven: BOOLEAN,
pathClosed: BOOLEAN,
convex,boundary: BOOLEAN,
sense: Sense,
count: Count,
front,back: PathNodeRef,
xturns,yturns: CARDINAL,
v1,v2,v3: Vector.Vec,
boxer: Boxer.Handle
];
DataRef: TYPE = LONG POINTER TO Data;

bufSize: CARDINAL=4;
-- only 3 needed, but index MOD 4 uses masking and is much faster

PathNode: TYPE = RECORD [
fLink,bLink: PathNodeRef ← NIL,
data: SELECT Type: * FROM
Vertex => [vrtx: Vector.Vec],
Cubic => [cbc: Cubic.Bezier],
Boundary => [],
ENDCASE
];
PathNodeRef: TYPE = LONG POINTER TO PathNode;

procs: LONG POINTER TO READONLY Procs = zone.NEW[Procs = [
EnterPoint: CEnterPoint,
EnterCubic: CEnterCubic,
Close: CClose,
Boundary: CBoundary,
Generate: CGenerate,
Free: CFree
]];

-- Procedure for creating an AreaPath object

New: PUBLIC PROCEDURE[oddEven: BOOLEAN] RETURNS[Handle] = {
d: DataRef = zone.NEW[Data ← [
oddEven: oddEven,
pathClosed: TRUE, convex: TRUE, boundary: FALSE,
sense: none, count: one, front: NIL, back: NIL,
xturns: 0, yturns: 0, v1: [0,0], v2: [0,0], v3: [0,0],
boxer: Boxer.New[]
]];
RETURN[zone.NEW[Object ← [procs: procs, data: LOOPHOLE[d]]]];
};

-- Operations on an AreaPath

NewPathNode: PROC[d: DataRef, p: PathNodeRef] = INLINE {
b: PathNodeRef=d.back;
IF b=NIL THEN d.front←d.back←p
ELSE { b.fLink←d.back←p; p.bLink←b };
};

NewVec: PROC[d: DataRef, v: Vector.Vec] = INLINE {
CheckConvex[d,v];
Boxer.Put[d.boxer,v];
};

CEnterPoint: PROCEDURE[self: Handle, v: POINTER TO Vector.Vec] = {
d: DataRef=LOOPHOLE[self.data];
w: Vector.Vec=v↑;
NewPathNode[d,zone.NEW[Vertex PathNode ← [data: Vertex[w]]]];
NewVec[d,w]; d.pathClosed←FALSE;
};

CEnterCubic: PROCEDURE[self: Handle, c: POINTER TO Cubic.Coeffs] = {
d: DataRef=LOOPHOLE[self.data];
b: Cubic.Bezier←Cubic.CoeffsToBezier[c↑];
NewPathNode[d,zone.NEW[Cubic PathNode ← [data: Cubic[b]]]];
NewVec[d,b.b0]; NewVec[d,b.b1]; NewVec[d,b.b2]; NewVec[d,b.b3];
d.pathClosed←FALSE;
};

CClose: PROCEDURE[self: Handle] = {
d: DataRef=LOOPHOLE[self.data];
NewPathNode[d,zone.NEW[Boundary PathNode ← [data: Boundary[]]]];
WITH pp:d.front SELECT FROM
Vertex => CheckConvex[d,pp.vrtx];
Cubic => CheckConvex[d,pp.cbc.b0];
ENDCASE;
d.pathClosed←d.boundary←TRUE;
};

CBoundary: PROCEDURE[self: Handle] RETURNS[Area.Handle] = {
d: DataRef=LOOPHOLE[self.data];
RETURN[Poly.NewRec[Boxer.Rectangle[d.boxer]]];
};

CGenerate: PROCEDURE[self: Handle,
clipper: Clipper.Handle, pipe: Pipe.Handle] = {
d: DataRef=LOOPHOLE[self.data];
eps: REAL=1.5;
IF NOT d.pathClosed THEN CClose[self];
pipe←Clipper.NewPipe[clipper,pipe];
IF d.convex THEN {
poly: Poly.Handle←Poly.New[];
Put: PROC[v: Vector.Vec] = { Poly.Put[poly,v] };
IF d.sense=positive THEN {
FOR p: PathNodeRef←d.front,p.fLink UNTIL p=NIL DO
WITH pp:p SELECT FROM
Vertex => Put[pp.vrtx];
Cubic => Cubic.BezierPolygon[pp.cbc,eps,Put];
Boundary => NULL;
ENDCASE => ERROR;
ENDLOOP;
}
ELSE {
-- negative sense is "backward"
FOR p: PathNodeRef←d.back,p.bLink UNTIL p=NIL DO
WITH pp:p SELECT FROM
Vertex => Put[pp.vrtx];
Cubic => {
-- subdivide the cubic in reverse order
b: Cubic.Bezier←pp.cbc;
br: Cubic.Bezier←[b0: b.b3, b1: b.b2, b2: b.b1, b3: b.b0];
Cubic.BezierPolygon[br,eps,Put]
};
Boundary => NULL;
ENDCASE => ERROR;
ENDLOOP;
};
Pipe.Put[pipe,Poly.NewArea[poly]]; Poly.Free[@poly]; Pipe.Free[@pipe];
}
ELSE {
pairing: Reducer.Pairing=(IF d.oddEven THEN odd ELSE nonzero);
reducer: Reducer.Handle←Reducer.NewReducer[pairing];
Put: PROC[v: Vector.Vec] = { Reducer.Vertex[reducer,v] };
FOR p: PathNodeRef←d.front,p.fLink UNTIL p=NIL DO
WITH pp:p SELECT FROM
Vertex => Put[pp.vrtx];
Cubic => Cubic.BezierPolygon[pp.cbc,eps,Put];
Boundary => Reducer.NewBoundary[reducer];
ENDCASE => ERROR;
ENDLOOP;
Reducer.Generate[reducer,pipe];
Reducer.Free[@reducer];
};
};

FreePath: PROCEDURE[d: DataRef] = {
p: PathNodeRef←d.front;
d.front←d.back←NIL;
UNTIL p=NIL DO
next: PathNodeRef=p.fLink;
zone.FREE[@p]; p←next;
ENDLOOP;
};

CFree: PROCEDURE[self: Handle] = {
d: DataRef←LOOPHOLE[self.data];
FreePath[d]; Boxer.Free[@d.boxer];
zone.FREE[@d]; zone.FREE[@self];
};

CheckConvex: PROCEDURE[d: DataRef, v: Vector.Vec] = INLINE {
IF d.convex THEN CCheckConvex[d,@v]
};
CCheckConvex: PROCEDURE[d: DataRef, v: POINTER TO Vector.Vec] = {
xmin,xmax,ymin,ymax: REAL;
IF d.boundary THEN GOTO NonConvex;
IF d.count=one THEN { d.v3←v↑; d.count←two; RETURN }; -- first point
IF Vector.Eq[v↑,d.v3] THEN RETURN; -- new point matches previous point
IF d.count=two THEN { d.v2←d.v3; d.v3←v↑; d.count←more; RETURN };
d.v1←d.v2; d.v2←d.v3; d.v3←v↑;
xmin←MIN[d.v1.x,d.v3.x]; xmax←MAX[d.v1.x,d.v3.x];
ymin←MIN[d.v1.y,d.v3.y]; ymax←MAX[d.v1.y,d.v3.y];
IF d.v2.x NOT IN[xmin..xmax] THEN
IF (d.xturns←d.xturns+1) > 2 THEN GOTO NonConvex;
IF d.v2.y NOT IN[ymin..ymax] THEN
IF (d.yturns←d.yturns+1) > 2 THEN GOTO NonConvex;
SELECT Vector.Cross[Vector.Sub[d.v2,d.v1],Vector.Sub[d.v3,d.v2]] FROM
>0 => SELECT d.sense FROM
none => d.sense←positive;
positive => NULL;
negative => GOTO NonConvex;
ENDCASE;
<0 => SELECT d.sense FROM
none => d.sense←negative;
positive => GOTO NonConvex;
negative => NULL;
ENDCASE;
ENDCASE;
EXITS NonConvex => d.convex←FALSE
};

}.