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

}.

สแ–
"Mesa" style˜Iprocšะฯc‰
œ
ฯk	œ
žœžœžœ3žœ2žœ
žœ
žœ&žœžœ0žœžœžœžœžœDžœ	žœ
žœ4žœžœžœ	žœažœ
žœžœฯnœžœ
žœžœžœ žœžœžœžœžœ4žœžœŸœžœžœžœ.žœžœžœ
žœžœžœžœžœžœžœ
žœžœžœžœžœ
žœžœžœ2žœ2žœ,žœžœžœ'žœŸ	œžœ
žœžœ
žœžœžœžœ
žœžœžœžœžœžœžœ
žœ
žœžœ'žœžœ
žœ
žœ'žœžœ
žœœžœžœžœžœžœžœ
žœžœžœ
žœ
žœžœžœužœžœ
žœ
žœ
žœ#žœžœ
žœ	Ÿœžœ
žœ.žœ
žœžœžœžœžœžœ
žœžœžœžœžœ#žœžœ
žœ
žœ#žœžœ
žœœžœžœžœžœ?žœ
žœžœYœ
Ÿœžœ
žœLžœžœžœžœžœ
žœžœžœžœžœ#žœžœ
žœ
žœ#žœžœ
žœœžœžœžœžœžœžœ3žœžœ(žœžœYžœ9žœžœžœžœŸ
Ÿœžœ
žœ4žœ1žœ(žœžœžœ
žœžœ
žœžœžœžœžœ
žœžœ
žœžœžœžœžœ
žœžœžœ
žœ
žœžœžœ
žœœžœžœžœžœ.žœžœžœžœ
žœ
žœ
žœ	Ÿœžœžœžœžœ'žœ
žœžœ	žœ
žœ
žœžœ
žœ
žœžœ	žœ
žœ
žœ
žœ
žœŸœžœžœ
žœžœžœžœ
žœžœŸœžœžœ
žœžœžœžœ
žœžœWžœžœžœ
žœžœ"žœžœžœžœžœ
žœ
žœขžœžœ
žœ+žœ3žœžœŸœžœ
žœ0žœ*žœžœ
žœ
žœRžœ(œ
Ÿœžœ
žœ™
žœไžœ$žœžœ&œ
Ÿœžœ
žœ+žœ$œ	žœ4œ,žœ%žœžœžœ
žœžœ…
žœ
žœžœ
žœ œžœžœžœ’žœžœ
žœ%žœ'žœ/žœžœภžœ+žœ&žœ	žœžœžœ'žœ'žœ'žœ8žœžœ	žœ(žœ,'œ
Ÿœžœ
žœžœžœ[žœžœ
žœ
žœฎžœqžœ
œ
Ÿœžœ
žœ#žœKžœžœ
žœ
žœฎžœt.œ˜ฟV—…—+B1)