[Cyan]<Cedar6.1>Imager>ImagerBrickImpl.mesa!1

ImagerBrickImpl.mesa

Adapted from CGBrickImpl by Ken Pier

Michael Plass, August 9, 1985 2:54:45 pm PDT

Doug Wyatt, May 18, 1985 2:52:39 pm PDT

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;

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;

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: SampleBuffer ← NIL] RETURNS [buffer: SampleBuffer] ~ {

buffer ← ImagerSample.NewBuffer[brick.sSize, brick.fSize, 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;

buffer.PutSample[s, f, sample];

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.