-- 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
	};

}.(670)