ImagerBrickImpl.mesa
Adapted from CGBrickImpl by Ken Pier
Michael Plass, July 7, 1983 10:14 am
DIRECTORY
ImagerBrick,
Inline USING [LongNumber, BITXOR],
PriorityQueue USING [Ref, Item, Create, Insert, Remove, Empty],
Real USING [RoundLI],
RealFns USING [CosDeg, SinDeg];
ImagerBrickImpl: CEDAR PROGRAM
IMPORTS Inline, Real, RealFns, PriorityQueue
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: Inline.LongNumber]
RETURNS [
INT] =
INLINE {
long.lowbits ← Inline.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.