-- ChipOrientImpl.mesa

-- A package to transform Chipmonk rectangles and
-- orientations.

-- last edited by E. McCreight, December 15, 1982  6:10 PM
-- written by E. McCreight, February 22, 1982  10:11 AM

DIRECTORY
  ChipOrient,
  InlineDefs,
  ppdefs;

ChipOrientImpl: PROGRAM
  IMPORTS ChipOrient, InlineDefs, ppdefs
  EXPORTS ChipOrient =
  BEGIN OPEN ppdefs, ChipOrient;


  -- Orientation Transformations

  -- x increases to the right, y increases downward.

  -- An orientationIndex idx is composed of two parts:
  --    a clockwise rotation of (idx/2)*45 degrees,
  --    followed by a reflection in x if (idx MOD 2)#0.
  -- Odd multiples of 45 degrees are not yet supported.

  MapRect: PUBLIC PROC [itemInCell: Rect, cellSize: Point,
    cellInstOrient: orientationIndex, cellInstPos: Point _ [0,0]]
    RETURNS [itemInWorld: Rect] =

    -- Given an item in a prototype cell, and the
    -- size of the prototype cell, both in "cell" co-ordinates, and
    -- the position and orientation index of an instance of that cell in "world"
    -- co-ordinates, this procedure returns the world
    -- co-ordinates of the instance of the item.

    BEGIN OPEN InlineDefs;
    x1, y1, x2, y2, sizeX, sizeY, t: locNum;
    IF cellInstOrient=0 THEN
      RETURN[[x1: cellInstPos.x+itemInCell.x1,
        x2: cellInstPos.x+itemInCell.x2,
        y1: cellInstPos.y+itemInCell.y1,
        y2: cellInstPos.y+itemInCell.y2]];
        -- most common case
    [x: sizeX, y: sizeY] _ cellSize;
    [x1: x1, x2: x2, y1: y1, y2: y2] _ itemInCell;

    SELECT BITAND[cellInstOrient, 14B] FROM
      0 => NULL;
      4 => -- 90 degrees clockwise
        BEGIN
        t _ y1;
        y1 _ x1;
        x1 _ sizeY-y2;
        y2 _ x2;
        x2 _ sizeY-t;
        sizeX _ sizeY;
        END;
      10B => -- 180 degrees clockwise
        BEGIN
        t _ sizeX-x1; x1 _ sizeX-x2; x2 _ t;
        t _ sizeY-y1; y1 _ sizeY-y2; y2 _ t;
        END;
      14B => -- 270 degrees clockwise
        BEGIN
        t _ x1;
        x1 _ y1;
        y1 _ sizeX-x2;
        x2 _ y2;
        y2 _ sizeX-t;
        sizeX _ sizeY;
        END;
      ENDCASE;

    IF BITAND[cellInstOrient, 1]#0 THEN -- mirror in x
      {t _ sizeX-x1; x1 _ sizeX-x2; x2 _ t};

    itemInWorld _ [x1: cellInstPos.x+x1, -- translate by cellInstPos
      y1: cellInstPos.y+y1, x2: cellInstPos.x+x2,
      y2: cellInstPos.y+y2];
    END;


  DeMapRect: PUBLIC PROC [itemInWorld: Rect, cellSize: Point,
    cellInstOrient: orientationIndex, cellInstPos: Point _ [0,0]]
    RETURNS [itemInCell: Rect] =
    BEGIN OPEN InlineDefs;

    -- Given an item in world co-ordinates, and the
    -- size of a prototype cell, both in "cell" co-ordinates, and
    -- the position and orientation index of an instance of that cell in "world"
    -- co-ordinates, this procedure returns the cell prototype
    -- co-ordinates of that item.

    inverseOrient: orientationIndex = InverseOrient[cellInstOrient];
    itemInCell _ MapRect[
      itemInCell: [x1: itemInWorld.x1-cellInstPos.x, y1: itemInWorld.y1-cellInstPos.y,
            x2: itemInWorld.x2-cellInstPos.x, y2: itemInWorld.y2-cellInstPos.y],
      cellInstOrient: inverseOrient,
      cellSize: Size[size: cellSize, orient: inverseOrient]];
    END;


  ComposeOrient: PUBLIC PROC [
    itemOrientInCell, cellOrientInWorld: orientationIndex]
    RETURNS [itemOrientInWorld: orientationIndex] =
    BEGIN OPEN InlineDefs;

    -- This procedure produces the composite orientation
    -- obtained by first doing itemOrientInCell and then
    -- doing cellOrientInWorld.  It uses the observation
    -- that a reflection in x followed by a z-degree clockwise
    -- rotation is the same as a (360-z)-degree clockwise rotation
    -- followed by a reflection in x.  Thus if itemOrientInCell
    -- contains a final reflection, then cellOrientInWorld's rotation
    -- operates in reverse.

    refl1: [0..1] _ BITAND[itemOrientInCell, 1];
    rot2: [0..14] _ BITAND[cellOrientInWorld, 14];
    IF refl1#0 AND rot2#0 THEN rot2 _ 16-rot2;
    itemOrientInWorld _ BITAND[BITAND[itemOrientInCell, 14]+
      rot2+BITXOR[refl1, BITAND[cellOrientInWorld, 1]], 15];
    END;


  InverseOrient: PUBLIC PROC [orient: orientationIndex]
    RETURNS [inverse: orientationIndex] =
    BEGIN OPEN InlineDefs;

    -- For all orientationIndexes o1, ComposeOrient[o1, InverseOrient[o1]] = 0.

    -- A reflection in x followed by a z-degree clockwise
    -- rotation is the same as a (360-z)-degree clockwise rotation
    -- followed by a reflection in x.  Thus if orient
    -- contains a final reflection, then the inverse rotation
    -- operates in the same direction as the forward one.

    refl: [0..1] _ BITAND[orient, 1];
    rot: [0..14] _ BITAND[orient, 14];
    IF refl=0 AND rot#0 THEN rot _ 16-rot;
    inverse _ rot+refl;
    END;


  DecomposeOrient: PUBLIC PROC [
    itemOrientInWorld, cellOrientInWorld: orientationIndex]
    RETURNS [itemOrientInCell: orientationIndex] =
    BEGIN

    -- For all orientationIndexes o1 and o2,
    -- DecomposeOrient[cellOrientInWorld: o1, itemOrientInWorld:
    --   ComposeOrient[cellOrientInWorld: o1, itemOrientInCell: o2]] = o2.

    RETURN[ComposeOrient[itemOrientInCell: itemOrientInWorld,
      cellOrientInWorld: InverseOrient[cellOrientInWorld]]];
    END;


  RefPt: PUBLIC PROC [r: Rect] RETURNS [Point] =
    {RETURN[[x: ((r.x1+r.x2)/(2*Lambda))*Lambda,
      y: ((r.y1+r.y2)/(2*Lambda))*Lambda]]};


  NormalizeList: PUBLIC PROC [lp: listPtr,
    origin: Point _ [0,0]] RETURNS [size, offset: Point] =
    BEGIN
    r: Rect _ BoundingRect[lp];
    offset _ [x: origin.x-r.x1, y: origin.y-r.y1];
    size _ [x: r.x2-r.x1, y: r.y2-r.y1];
    FOR lpp: listPtr _ lp, lpp.nxt WHILE lpp#NIL DO
      lpp.lx _ lpp.lx+offset.x;
      lpp.ly _ lpp.ly+offset.y;
      ENDLOOP;
    END;


  BoundingRect: PUBLIC PROC [lp: listPtr]
    RETURNS [r: Rect] =
    BEGIN
    x1, y1, x2, y2: locNum;
    [mix: x1, miy: y1, max: x2, may: y2] _ minmax[lp];
    r _ [x1: x1, y1: y1, x2: x2, y2: y2];
    END;


  DecomposeRect: PUBLIC PROC [r, test: Rect, rInsideTest, rOutsideTest: PROC[Rect]] =
    BEGIN
    IF r.x1<test.x1 THEN
      BEGIN
      rOutsideTest[[x1: r.x1, y1: r.y1, x2: MIN[r.x2, test.x1], y2: r.y2]];
      IF r.x2<test.x1 THEN RETURN;
      END;
    IF r.y1<test.y1 THEN
      BEGIN
      rOutsideTest[[x1: MAX[test.x1, r.x1], y1: r.y1, x2: r.x2, y2: MIN[r.y2, test.y1]]];
      IF r.y2<test.y1 THEN RETURN;
      END;
    IF test.y2<r.y2 THEN
      BEGIN
      rOutsideTest[[x1: MAX[test.x1, r.x1], y1: MAX[test.y2, r.y1], x2: r.x2,
        y2: r.y2]];
      IF test.y2<r.y1 THEN RETURN;
      END;
    IF test.x2<r.x2 THEN
      BEGIN
      rOutsideTest[[x1: MAX[test.x2, r.x1], y1: MAX[test.y1, r.y1], x2: r.x2,
        y2: MIN[r.y2, test.y2]]];
      IF test.x2<r.x1 THEN RETURN;
      END;
    rInsideTest[[x1: MAX[test.x1, r.x1], y1: MAX[test.y1, r.y1],
      x2: MIN[test.x2, r.x2], y2: MIN[test.y2, r.y2]]];
    END;


  -- Certification tests, can be commented out for speed of startup

--  FOR o1: orientationIndex IN orientationIndex DO
--    IF ComposeOrient[o1, InverseOrient[o1]] # 0 THEN ERROR;
--    FOR o2: orientationIndex IN orientationIndex DO
--      IF DecomposeOrient[cellOrientInWorld: o1, itemOrientInWorld:
--        ComposeOrient[cellOrientInWorld: o1, itemOrientInCell: o2]] # o2 THEN ERROR;
--      ENDLOOP;
--    ENDLOOP;

  END. -- of ChipOrientImpl