ImagerBrickImpl.mesa
Adapted from CGBrickImpl by Ken Pier
Michael Plass, July 7, 1983 10:14 am
Edited by Doug Wyatt, November 22, 1983 11:57 am
DIRECTORY
Basics USING [LongNumber, BITXOR],
ImagerBrick,
PriorityQueue USING [Ref, Item, Create, Insert, Remove, Empty],
Real USING [RoundLI],
RealFns USING [CosDeg, SinDeg];
ImagerBrickImpl: CEDAR PROGRAM
IMPORTS Basics, PriorityQueue, Real, RealFns
EXPORTS ImagerBrick = {
OPEN ImagerBrick;
QItem: TYPE = REF QItemRep;
QItemRep: TYPE = RECORD [f, s: CARDINAL, val: REAL];
sorting function for halftone generator below
SortPred: PROC [x, y: PriorityQueue.Item, data: REF] RETURNS [BOOL] = {
na: QItem ← NARROW[x];
nb: QItem ← NARROW[y];
RETURN[IF na.val=nb.val THEN RandomBool[NARROW[data]] ELSE na.val < nb.val]
};
Random bit generator
Generates random bits using a shift register 30 bits long, (see Knuth ACM 3.2.2).
RandomHandle: TYPE = REF RandomRec;
RandomRec: TYPE = RECORD [
This seed was generated by InitRandom[4, 1000000]
w: INT ← -1978068312
];
lowTap: INT = 10000000000B;
highTap: INT = 100000000B;
XorC: PROC [long: Basics.LongNumber] RETURNS [INT] = INLINE {
long.lowbits ← Basics.BITXOR[long.lowbits, 514B];
RETURN[long.li];
};
RandomBool: PROC [r: RandomHandle] RETURNS [BOOLEAN] = {
RETURN [0>(r.w ← IF r.w<0 THEN XorC[[li[r.w+r.w]]] ELSE r.w+r.w)]
};
InitRandom: PROC [w: INT, n: INT] RETURNS [r: RandomHandle] = {
r ← NEW[RandomRec ← [w]];
FOR i: INT IN [0..n) DO [] ← RandomBool[r] ENDLOOP;
};
Procedure BuildBrick is called with a halftone dot defined by its
frequency in pixels/dot (may be REAL), rotation angle, and a filter function defined on
the interval [-1..+1] in both x and y, returning values in the range [0..1].
BuildBrick: PUBLIC PROC [freq: REAL, angle: REAL, filter: PROC [x, y:REAL] RETURNS [fvalue: REAL]]
RETURNS [brick: Brick] = {
tInt: INTEGER; --temporary
u,v: REAL ← 0.0; --u/v is tangent[angle]
iu, iv, iuvsqrd: INTEGER 𡤀 -- closest integer values of u,v
absiu, absiv: INTEGER ← 0; -- absolute values of iu,iv
riu, riv, riuvsqrd: REAL ← 0.0; --real versions of iu, iv, etc.
sSize, fSize: INTEGER 𡤀 --dimensions of halftone brick, fSize wide and sSize high
a,b,c,d: REAL ← 0.0; --elements of the transform matrix
LIndex, pIndex: INTEGER ← 0;
x, y: INTEGER ← 0; --for receiving results of ExtendedEuclid.
reali, realj, realiPrime, realjPrime: REAL ← 0.0;
define the parameters u and v of the "enclosing square"
surrounding the rotated halftone dot
u ← freq*RealFns.SinDeg[angle]; v ← freq*RealFns.CosDeg[angle];
iu ← Real.RoundLI[u];-- get nearest integer
iv ← Real.RoundLI[v];
IF iu = 0 AND iv = 0 THEN iu ← 1;--appearance error
now compute rotation for iu, iv into first quadrant
absiv ← ABS[iv]; absiu ← ABS[iu];
IF iu*iv < 0 THEN { tInt ← absiv; absiv ← absiu; absiu ← tInt };
[x, y, sSize] ← ExtendedEuclid[absiu, absiv];--computes GCD of arguments plus phase value arguments
iuvsqrd ← iu*iu + iv*iv;
fSize ← iuvsqrd/sSize;--calculate length of brick
now calculate the elements of the coord transformation from
brick indexes into the elementary dot. This dot is 2 wide and 2 high
centered about the origin. The transform is a concatenation of two
transform matrices, one to normalize the brick by 2, and
another to rotate the brick coordinates into elementary coordinates:
[ 2 0 ] [ cos -sin] [ a b ]
[ ] * [ ] = [ ]
[ 0 2 ] [ sin cos] [ c d ]
riu ← iu; riv ← iv; riuvsqrd ← iuvsqrd;
d ← a ← 2*riv/riuvsqrd ;
c ← 2*riu/riuvsqrd;
b ← -c; -- -2*riu/riuvsqrd
get brick instance
brick ← NEW[BrickRep[fSize*sSize] ← [fSize: fSize, sSize: sSize, phase: 0, u: absiu, v: absiv, cBrick: ]];
brick.phase ← (x*absiv - y*absiu) MOD fSize;
now calculate the brick values
{ -- so we can do some more declarations
item: QItem;
lxp: NAT = fSize*sSize;
sliceInterval: REAL = 1.0/lxp;
currentSlice: REAL ← 0;
pQ: PriorityQueue.Ref ← PriorityQueue.Create[SortPred, NEW[RandomRec]];
FOR LIndex IN [0..fSize) DO
reali ← LIndex+0.5;
FOR pIndex IN [0..sSize) DO
realj ← pIndex+0.5;
realiPrime ← RealMod[(reali*a + realj*c), 2.0] - 1.0;
realjPrime ← RealMod[(reali*b + realj*d), 2.0] - 1.0;
item ← NEW[QItemRep];
item^ ← [f: LIndex, s: pIndex, val: filter[realiPrime, realjPrime]];
pQ.Insert[item];
ENDLOOP;
ENDLOOP;
FOR i: NAT IN [0..lxp) DO
item ← NARROW[pQ.Remove];
brick.cBrick[fSize*item.s + item.f] ← currentSlice;
currentSlice ← currentSlice + sliceInterval;
ENDLOOP;
IF NOT pQ.Empty THEN ERROR;
};--brick values
};--BuildBrick
ExtendedEuclid: PROC [u, v: INTEGER] RETURNS [u1, u2, u3: INTEGER] = {
q, v1, v2, v3, t1, t2, t3: INTEGER;
u1 ← 1; u2 ← 0; u3 ←u;
v1 ← 0; v2 ← 1; v3 ← v;
DO
IF (v3 = 0) THEN EXIT;
q ← u3/v3;
t1 ← u1-(v1*q); t2 ← u2-(v2*q); t3 ← u3-(v3*q);
u1 ← v1; u2 ← v2; u3 ← v3;
v1 ← t1; v2 ← t2; v3 ← t3;
ENDLOOP;
};
RealMod: PROC[a,b: REAL] RETURNS [REAL] =
{ RETURN[a - (FloorI[a/b])*b]};--RealMod
FloorI: PROC[r: REAL] RETURNS [i: INT] = {
i ← Real.RoundLI[r];
IF i>r THEN i←i-1;
};--FloorI
GetSize: PUBLIC PROC[brick: Brick] RETURNS [fSize, sSize: CARDINAL, phase: INTEGER] = {
brick is fSize long and sSize high
RETURN[brick.fSize, brick.sSize, brick.phase];
};--GetSize
Modd: PROC[x, y: LONG INTEGER] RETURNS [LONG INTEGER] = {
RETURN [IF x >= 0 THEN (x MOD y) ELSE ((y-1) + (x+1) MOD y)];
};--Modd
GetElement: PUBLIC PROC[brick: Brick, x, y: CARDINAL] RETURNS [bElement: REAL] = {
row, col: CARDINAL ← 0;
row ← GetRow[brick,x,y];
col ← GetCol[brick,x,y];
RETURN [brick.cBrick[brick.fSize*row + col]];
};--GetElement
GetRow: PUBLIC PROC[brick: Brick, x, y: CARDINAL] RETURNS [row: CARDINAL] = {
RETURN [y MOD brick.sSize];
};--GetRow
GetCol: PUBLIC PROC[brick: Brick, x, y: CARDINAL] RETURNS [col: CARDINAL] = {
i: LONG INTEGER ← Modd[(x - LONG[brick.phase]*(y/brick.sSize)), brick.fSize];
RETURN [i];
};--GetCol
}. --of CGBrickImpl
LOG
created, 21-Oct-81 12:00:21, Pier
changed matrix to store by rows instead of columns 26-Oct-81 15:24:40
fixed Modd to take LONG INTEGERs; added LONG in GetCol 8-Jan-82 13:27:38
changed system zone to CGStorage zone, Brick to REF, 13-Jan-82
reformatted, 18-JAN-82
changed to general purpose halftone brick, 23-Jan`82
changed definition of brick to use L,p,D field names, 2/22/82
Michael Plass, July 6, 1983 3:22 pm: Changed name from CGBrickImpl to ImagerBrickImpl; extensive modifications.
Michael Plass, July 7, 1983 8:59 am: changed brick definition to use fSize, sSize, phase, cBrick field names, Brick and BrickRep instead of BrickHandle and Brick.
Michael Plass, July 7, 1983 10:39 am: Replace use of RandomCard with a shift-register random bit generator, to make BuildBrick into a pure function.