ImagerBrickImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Adapted from CGBrickImpl by Ken Pier
Michael Plass, August 9, 1985 2:54:45 pm PDT
Doug Wyatt, March 20, 1986 2:13:08 pm PST
DIRECTORY
Basics USING [LongDivMod, LongNumber, BITXOR],
ImagerBrick,
ImagerSample,
PriorityQueue USING [Ref, Item, Create, Insert, Remove, Empty],
Real USING [Round],
RealFns USING [CosDeg, SinDeg];
ImagerBrickImpl: CEDAR PROGRAM
IMPORTS Basics, ImagerSample, 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 ACP 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 NewBrick 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].
NewBrick:
PUBLIC
PROC [freq, angle:
REAL, filter: FilterProc]
RETURNS [brick: Brick] = {
tInt: INTEGER; --temporary
u,v: REAL ← 0.0; --u/v is tangent[angle]
iu, iv: INTEGER ← 0; -- closest integer values of u,v
iuvsqrd: INT ← 0; -- 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.Round[u];-- get nearest integer
iv ← Real.Round[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 ← INT[iu]*iu + INT[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, samples: ]];
brick.phase ← Mod[(x*absiv - y*absiu), 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[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.Round[r];
IF i>r THEN i←i-1;
};--FloorI
Mod:
PROC [n:
INT, d:
NAT]
RETURNS [remainder:
NAT] ~ {
Number-theoretic: 0 <= remainder < d
IF d#1
THEN {
nn: Basics.LongNumber ← [li[n]];
WHILE nn.li < 0 DO nn.highbits ← nn.highbits + d ENDLOOP;
WHILE nn.highbits >= d DO nn.highbits ← nn.highbits - d ENDLOOP;
RETURN [Basics.LongDivMod[nn.lc, d].remainder];
}
ELSE RETURN [remainder: 0];
};
GetElement:
PUBLIC
PROC[brick: Brick, s, f:
NAT]
RETURNS [
REAL] = {
row, col: CARDINAL ← 0;
row ← GetRow[brick, f, s];
col ← GetCol[brick, f, s];
RETURN [brick[brick.fSize*row + col]];
};--GetElement
GetRow:
PROC[brick: Brick, x, y:
CARDINAL]
RETURNS [row:
CARDINAL] = {
RETURN [y MOD brick.sSize];
};--GetRow
GetCol:
PROC[brick: Brick, x, y:
CARDINAL]
RETURNS [col:
CARDINAL] = {
RETURN [Mod[(x - INT[brick.phase]*(y/brick.sSize)), brick.fSize]];
};--GetCol
DotScreen:
PUBLIC FilterProc ~ {
tx: REAL ← (x-1)*(x-1)*(x+1)*(x+1);
ty: REAL ← (y-1)*(y-1)*(y+1)*(y+1);
RETURN[(tx+ty)/2];
};
LineScreen:
PUBLIC FilterProc ~ {
RETURN[(x-1)*(x-1)*(x+1)*(x+1)];
};
NewSquareBrick:
PUBLIC
PROC [size:
NAT, p, q:
INTEGER, pModulation, qModulation:
REAL]
RETURNS [Brick] ~ {
max: REAL ← ABS[pModulation]+ABS[qModulation];
min: REAL ← -max;
Screen: FilterProc ~ {
x0: REAL ← (x+1)/2.0;
y0: REAL ← (y+1)/2.0;
u: REAL ← p * x0 + q * y0;
v: REAL ← -q * x0 + p * y0;
RETURN[(pModulation*RealFns.CosDeg[u*360] + qModulation*RealFns.CosDeg[v*360] - min)/(max-min)];
};
RETURN[NewBrick[size, 0, Screen]];
};
ThresholdsFromBrick:
PUBLIC
PROC [brick: Brick, max: Sample,
scratch: SampleMap ←
NIL]
RETURNS [map: SampleMap] ~ {
map ← ImagerSample.NewSampleMap[size: [s: brick.sSize, f: brick.fSize],
bitsPerSample: ImagerSample.maxBitsPerSample, scratch: scratch];
FOR s:
NAT
IN[0..brick.sSize)
DO
FOR f:
NAT
IN[0..brick.fSize)
DO
r: REAL ~ GetElement[brick, s, f];
sample: Sample ~ Real.Round[r*(max-1)]+1;
map.Put[index: [s: s, f: f], value: sample];
ENDLOOP;
ENDLOOP;
};
}. --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.