-- CGClipperImpl.mesa
-- Last changed by Doug Wyatt, December 10, 1982 12:47 pm
-- Last changed by Paul Rovner, August 10, 1983 11:30 am

DIRECTORY
Basics USING [BITAND, BITOR],
CGArea,
CGClipper,
CGReducer,
CGStorage USING [pZone, qZone],
GraphicsBasic;

CGClipperImpl: CEDAR PROGRAM
IMPORTS Basics, CGArea, CGReducer, CGStorage
EXPORTS CGClipper = {
OPEN CGReducer, CGClipper, GraphicsBasic;

repZone: ZONE = CGStorage.qZone;
boxZone: ZONE = CGStorage.qZone;
dataZone: ZONE = CGStorage.pZone;
nodeZone: ZONE = CGStorage.qZone;
edgeZone: ZONE = CGStorage.qZone;

nullBox: Box = [0,0,0,0];
nullNode: NodeRep = [FALSE,0,0,0,0,NIL,NIL];
nullEdge: EdgeRep = [this: nil, next: nil,
up: FALSE, vert: FALSE, line: FALSE, lastR: FALSE, tag: 0,
xbot: 0, ybot: 0, xtop: 0, ytop: 0,
a: 0, b: 0, c: 0, slope: 0, yemit: 0];

Error: PUBLIC ERROR[type: ErrorType] = CODE;

New: PUBLIC PROC[size: NAT] RETURNS[Ref] = {
self: Ref ← repZone.NEW[Rep ← [isbox: FALSE, isallboxes: TRUE,
size: 0, data: NIL, box: NIL]];
[] ← GetData[self,size];
self.box ← boxZone.NEW[Box ← nullBox];
RETURN[self];
};

GetData: PROC[self: Ref, size: NAT] RETURNS[Data] = {
data: Data ← self.data;
space: NAT ← IF data=NIL THEN 0 ELSE data.space;
IF space<size THEN {
new: Data ← dataZone.NEW[DataRep[size]];
FOR i: NAT IN[0..space) DO new[i] ← data[i] ENDLOOP;
FOR i: NAT IN[space..size) DO
node: Node ← nodeZone.NEW[NodeRep ← nullNode];
node.edgeL ← edgeZone.NEW[EdgeRep ← nullEdge];
node.edgeR ← edgeZone.NEW[EdgeRep ← nullEdge];
node.edgeL.up ← TRUE; node.edgeR.up ← FALSE;
new[i] ← node;
ENDLOOP;
self.data ← data ← new;
};
RETURN[data];
};

TestPoint: PUBLIC PROC[self: Ref, p: Vec] RETURNS[BOOLEAN] = {
size: NAT ← self.size;
mybox: REF Box ← self.box;
IF size>0
AND mybox.ymin<=p.y AND p.y<mybox.ymax
AND mybox.xmin<=p.x AND p.x<mybox.xmax THEN {
IF self.isbox THEN RETURN[TRUE]
ELSE {
data: Data ← self.data;
FOR i: NAT IN[0..size) DO
node: Node ← data[i];
IF p.y<node.ymin THEN EXIT; -- nodes are sorted by ymin
IF p.y<node.ymax THEN {
  xmin: REAL ← node.xmin;
  xmax: REAL ← node.xmax;
  IF xmin<=p.x AND p.x<xmax THEN {
  IF node.isbox THEN RETURN[TRUE]
  ELSE {
  dy: REAL ← node.ymax - node.ymin;
  xmin ← xmin + dy*node.edgeL.slope;
  xmax ← xmax + dy*node.edgeR.slope;
  IF xmin<=p.x AND p.x<xmax THEN RETURN[TRUE];
  };
  };
  };
ENDLOOP;
};
};
RETURN[FALSE];
};

TestBox: PUBLIC PROC[self: Ref, box: Box, reducer: CGReducer.Ref] RETURNS[BOOLEAN] = {
size: NAT ← self.size;
mybox: REF Box ← self.box;
in: BOOLEAN ← FALSE;
IF size>0
AND mybox.ymin<box.ymax AND box.ymin<mybox.ymax
AND mybox.xmin<box.xmax AND box.xmin<mybox.xmax THEN {
data: Data ← self.data;
FOR i: NAT IN[0..size) DO
node: Node ← data[i];
IF node.ymin>=box.ymax THEN EXIT; -- nodes are sorted by ymin
IF box.ymin<node.ymax
AND node.xmin<box.xmax AND box.xmin<node.xmax THEN {
CGReducer.Clip[reducer,node.edgeL,node.edgeR]; in ← TRUE };
ENDLOOP;
};
RETURN[in];
};
-- test the given box against the clip area
-- load relevant clipping edges into reducer

GenerateBox: PUBLIC PROC[self: Ref, box: Box, reducer: CGReducer.Ref, area: CGArea.Ref] = {
size: NAT ← self.size;
mybox: REF Box ← self.box;
clip: BOOLEAN ← FALSE;
IF size>0
AND mybox.ymin<box.ymax AND box.ymin<mybox.ymax
AND mybox.xmin<box.xmax AND box.xmin<mybox.xmax THEN {
data: Data ← self.data;
FOR i: NAT IN[0..size) DO
node: Node ← data[i];
IF node.ymin>=box.ymax THEN EXIT; -- nodes are sorted by ymin
IF box.ymin<node.ymax AND node.xmin<box.xmax AND box.xmin<node.xmax THEN {
IF node.isbox THEN {
clippedBox: Box = [
xmin: MAX[node.xmin,box.xmin], ymin: MAX[node.ymin,box.ymin],
xmax: MIN[node.xmax,box.xmax], ymax: MIN[node.ymax,box.ymax]];
CGArea.InsertBox[area, clippedBox];
}
ELSE { CGReducer.Clip[reducer,node.edgeL,node.edgeR]; clip ← TRUE };
};
ENDLOOP;
};
IF clip THEN {
CGReducer.Vertex[reducer,[box.xmin,box.ymin]];
CGReducer.Rectangle[reducer,[box.xmax,box.ymax]];
CGReducer.Generate[reducer,area];
};
};

GenerateLine: PUBLIC PROC[self: Ref, p,q: Vec, area: CGArea.Ref] = {
size: NAT ← self.size;
data: Data ← self.data;
mybox: REF Box ← self.box;
xmin,xmax,ymin,ymax: REAL;
IF size=0 THEN RETURN;
IF p.y<=q.y THEN { ymin ← p.y; ymax ← q.y } ELSE { ymin ← q.y; ymax ← p.y };
IF mybox.ymin>ymax OR ymin>=mybox.ymax THEN RETURN;
IF p.x<=q.x THEN { xmin ← p.x; xmax ← q.x } ELSE { xmin ← q.x; xmax ← p.x };
IF mybox.xmin>xmax OR xmin>=mybox.xmax THEN RETURN;
FOR i: NAT IN[0..size) DO
node: Node ← data[i];
IF node.ymin>ymax THEN EXIT; -- nodes are sorted by ymin
IF ymin<node.ymax AND node.xmin<=xmax AND xmin<node.xmax THEN {
pp: Vec ← p; qq: Vec ← q;
Out: TYPE = RECORD[bottom,top,left,right: BOOLEAN];
noneOut: Out = [FALSE,FALSE,FALSE,FALSE];
Code: PROC[x,y: REAL] RETURNS[Out] = INLINE {
out: Out ← noneOut;
IF y<node.ymin THEN out.bottom ← TRUE
ELSE IF y>node.ymax THEN out.top ← TRUE;
IF x<node.xmin THEN out.left ← TRUE
ELSE IF x>node.xmax THEN out.right ← TRUE;
RETURN[out] };
Reject: PROC[a,b: Out] RETURNS[BOOLEAN] = INLINE {
RETURN[Basics.BITAND[LOOPHOLE[a],LOOPHOLE[b]]#0] };
Accept: PROC[a,b: Out] RETURNS[BOOLEAN] = INLINE {
RETURN[Basics.BITOR[LOOPHOLE[a],LOOPHOLE[b]]=0] };
outp: Out ← Code[pp.x,pp.y];
outq: Out ← Code[qq.x,qq.y];
UNTIL Reject[outp,outq] DO
out: Out; x,y: REAL;
IF Accept[outp,outq] THEN { CGArea.InsertLine[area,pp,qq]; EXIT };
 out ← IF outp#noneOut THEN outp ELSE outq;
 SELECT TRUE FROM
  out.bottom => {
  x ← pp.x + (qq.x - pp.x)*(node.ymin - pp.y)/(qq.y - pp.y);
  y ← node.ymin };
  out.top => {
  x ← pp.x + (qq.x - pp.x)*(node.ymax - pp.y)/(qq.y - pp.y);
  y ← node.ymax };
  out.left => {
  y ← pp.y + (qq.y - pp.y)*(node.xmin - pp.x)/(qq.x - pp.x);
  x ← node.xmin };
  out.right => {
  y ← pp.y + (qq.y - pp.y)*(node.xmax - pp.x)/(qq.x - pp.x);
  x ← node.xmax };
  ENDCASE;
 IF out=outp THEN { pp.x ← x; pp.y ← y; outp ← Code[x,y] }
 ELSE { qq.x ← x; qq.y ← y; outq ← Code[x,y] };
ENDLOOP;
};
ENDLOOP;
};

Load: PUBLIC PROC[self: Ref, reducer: CGReducer.Ref] = {
size: NAT ← self.size;
data: Data ← self.data;
FOR i: NAT IN[0..size) DO
node: Node ← data[i];
CGReducer.Clip[reducer,node.edgeL,node.edgeR];
ENDLOOP;
};
-- load all clipping edges into reducer

SetBox: PUBLIC PROC[self: Ref, box: Box] = {
data: Data ← GetData[self,1];
node: Node ← data[0];
edgeL: Edge ← node.edgeL;
edgeR: Edge ← node.edgeR;
node.isbox ← TRUE;
node.ymin ← edgeL.ybot ← edgeR.ybot ← box.ymin;
node.ymax ← edgeL.ytop ← edgeR.ytop ← box.ymax;
node.xmin ← edgeL.xbot ← edgeL.xtop ← box.xmin;
node.xmax ← edgeR.xbot ← edgeR.xtop ← box.xmax;
edgeL.slope ← edgeR.slope ← 0;
edgeL.a ← edgeR.a ← -1;
edgeL.b ← edgeR.b ← 0;
edgeL.c ← box.xmin; edgeR.c ← box.xmax;
edgeL.vert ← edgeR.vert ← TRUE;
self.box^ ← box;
self.isbox ← TRUE;
self.isallboxes ← TRUE;
self.size ← 1;
};
-- set the clip area to the given box

SetArea: PUBLIC PROC[self: Ref, area: CGArea.Ref] = {
asize: NAT ← CGArea.Size[area]; -- number of trapezoids in the area
csize: NAT ← 0; -- number of trapezoids added to the clipper so far
data: Data ← GetData[self, asize];
box: REF Box ← self.box;
self.isallboxes ← TRUE;
FOR i: NAT IN[0..asize) DO
trap: Trap ← CGArea.Remove[area];
node: Node ← data[csize];
edgeL: Edge ← node.edgeL;
edgeR: Edge ← node.edgeR;
IF NOT trap.ytop>trap.ybot THEN LOOP; -- ignore degenerate trapezoids
IF trap.rectangle THEN {
node.isbox ← TRUE;
node.ymin ← edgeL.ybot ← edgeR.ybot ← trap.ybot;
node.ymax ← edgeL.ytop ← edgeR.ytop ← trap.ytop;
node.xmin ← edgeL.xbot ← edgeL.xtop ← trap.xbotL;
node.xmax ← edgeR.xbot ← edgeR.xtop ← trap.xbotR;
edgeL.slope ← edgeR.slope ← 0;
edgeL.a ← edgeR.a ← -1;
edgeL.b ← edgeR.b ← 0;
edgeL.c ← trap.xbotL; edgeR.c ← trap.xbotR;
edgeL.vert ← edgeR.vert ← TRUE;
}
ELSE {
dy: REAL ← trap.ytop - trap.ybot;
dxL: REAL ← trap.xtopL - trap.xbotL;
dxR: REAL ← trap.xtopR - trap.xbotR;
node.isbox ← FALSE;
self.isallboxes ← FALSE;
node.ymin ← edgeL.ybot ← edgeR.ybot ← trap.ybot;
node.ymax ← edgeL.ytop ← edgeR.ytop ← trap.ytop;
edgeL.xbot ← trap.xbotL; edgeL.xtop ← trap.xtopL;
edgeL.slope ← (trap.xtopL - trap.xbotL)/dy;
edgeL.vert ← (edgeL.slope=0);
edgeR.xbot ← trap.xbotR; edgeR.xtop ← trap.xtopR;
edgeR.slope ← (trap.xtopR - trap.xbotR)/dy;
edgeL.a ← dy; edgeL.b ← -dxL;
edgeL.c ← trap.ybot*dxL-trap.xbotL*dy;
edgeR.a ← dy; edgeR.b ← -dxR;
edgeR.c ← trap.ybot*dxR-trap.xbotR*dy;
edgeR.vert ← (edgeR.slope=0);
node.xmin ← MIN[edgeL.xbot,edgeL.xtop];
node.xmax ← MAX[edgeR.xbot,edgeR.xtop];
};
IF csize=0 THEN {
box.xmin ← node.xmin;
box.xmax ← node.xmax;
box.ymin ← node.ymin;
box.ymax ← node.ymax;
}
ELSE {
box.xmin ← MIN[box.xmin,node.xmin];
box.xmax ← MAX[box.xmax,node.xmax];
box.ymin ← MIN[box.ymin,node.ymin];
box.ymax ← MAX[box.ymax,node.ymax];
};
csize ← csize+1;
ENDLOOP;
IF csize=0 THEN box^ ← nullBox;
self.isbox ← csize=1 AND self.isallboxes;
self.size ← csize;
};
-- set the clip area to the given area

Copy: PUBLIC PROC[self: Ref] RETURNS[Ref] = {
size: NAT ← self.size;
old: Data ← self.data;
copy: Ref ← New[size];
new: Data ← copy.data;
FOR i: NAT IN[0..size) DO
oldnode: Node ← old[i];
newnode: Node ← new[i];
newnode.isbox ← oldnode.isbox;
newnode.xmin ← oldnode.xmin;
newnode.xmax ← oldnode.xmax;
newnode.ymin ← oldnode.ymin;
newnode.ymax ← oldnode.ymax;
newnode.edgeL^ ← oldnode.edgeL^;
newnode.edgeR^ ← oldnode.edgeR^;
ENDLOOP;
copy.box^ ← self.box^;
copy.isbox ← self.isbox;
copy.isallboxes ← self.isallboxes;
copy.size ← size;
RETURN[copy];
};
-- make a copy of the clipper

Assign: PUBLIC PROC[self: Ref, copy: Ref] = {
size: NAT ← copy.size;
new: Data ← copy.data;
old: Data ← GetData[self,size];
FOR i: NAT IN[0..size) DO
newnode: Node ← new[i];
oldnode: Node ← old[i];
oldnode.isbox ← newnode.isbox;
oldnode.xmin ← newnode.xmin;
oldnode.xmax ← newnode.xmax;
oldnode.ymin ← newnode.ymin;
oldnode.ymax ← newnode.ymax;
oldnode.edgeL^ ← newnode.edgeL^;
oldnode.edgeR^ ← newnode.edgeR^;
ENDLOOP;
self.box^ ← copy.box^;
self.isbox ← copy.isbox;
self.isallboxes ← copy.isallboxes;
self.size ← size;
};
-- restore the clip area from another clipper

}.