DIRECTORY ImagerBrick USING [Brick, BrickShape, BrickSpec], ImagerSample USING [Clear, NewSampleMap, Put, RasterSampleMap], ImagerSys USING [LongMult], ImagerTransformation USING [Cat, Create, InverseTransformVec, Rotate, Scale, Transformation, TransformVec], List USING [Compare, CompareProc, LORA, Sort], Real USING [Round], RealInline USING [MCFix], RealFns USING [CosDeg], SF USING [Vec], Vector2 USING [Add, Cross, Sub, VEC]; ImagerBrickImpl: CEDAR PROGRAM IMPORTS List, ImagerTransformation, Real, RealInline, RealFns, Vector2, ImagerSample, ImagerSys EXPORTS ImagerBrick ~ BEGIN VEC: TYPE ~ Vector2.VEC; Transformation: TYPE ~ ImagerTransformation.Transformation; BrickShape: TYPE ~ ImagerBrick.BrickShape; ExtendedGCD: TYPE ~ RECORD [p, q: INTEGER, g: NAT]; ExtendedEuclid: PROC [u, v: NAT] RETURNS [ExtendedGCD] ~ { u1: INTEGER ¬ 1; u2: INTEGER ¬ 0; u3: NAT ¬ u; v1: INTEGER ¬ 0; v2: INTEGER ¬ 1; v3: NAT ¬ v; WHILE v3 # 0 DO quotient: NAT ~ u3/v3; t1: INTEGER ~ u1-(v1*quotient); t2: INTEGER ~ u2-(v2*quotient); t3: INTEGER ~ u3-(v3*quotient); u1 ¬ v1; u2 ¬ v2; u3 ¬ v3; v1 ¬ t1; v2 ¬ t2; v3 ¬ t3; ENDLOOP; RETURN [[p: u1, q: u2, g: u3]] }; Sig: PROC [a, b: INT] RETURNS [INT] ~ {RETURN [IF a < 0 THEN -b ELSE b]}; BrickShapeFromDeltas: PUBLIC PROC [s0, f0, s1, f1: INT] RETURNS [BrickShape] ~ { area: CARD ~ ABS[INT[s0]*INT[f1] - INT[s1]*INT[f0]]; -- cross product to get area gcd: ExtendedGCD ~ ExtendedEuclid[ABS[s0], ABS[s1]]; sSize: CARD ~ gcd.g; fSize: INT ~ area/sSize; phase: INT ¬ Sig[s0, f0]*INT[gcd.p] + Sig[s1, f1]*INT[gcd.q]; WHILE phase < 0 DO phase ¬ phase + fSize ENDLOOP; WHILE phase >= fSize DO phase ¬ phase - fSize ENDLOOP; RETURN [[sSize, fSize, phase]]; }; SqrAbs: PROC [v: VEC] RETURNS [REAL] ~ INLINE {RETURN [v.x*v.x+v.y*v.y]}; SqrLen: PROC [u, v: VEC] RETURNS [REAL] ~ INLINE {RETURN [SqrAbs[Vector2.Sub[u, v]]]}; BrickSpec: TYPE ~ ImagerBrick.BrickSpec; BrickSpecFromTransformedRectangle: PUBLIC PROC [w, h: REAL, clientToDevice: Transformation, allowedRelativeError: REAL, minLevels: CARD] RETURNS [BrickSpec] ~ { v: ARRAY [0..1] OF VEC ~ [ ImagerTransformation.TransformVec[clientToDevice, [w, 0]], ImagerTransformation.TransformVec[clientToDevice, [0, h]] ]; vMul: ARRAY [0..1] OF VEC ¬ v; allowSqr: REAL ~ allowedRelativeError*allowedRelativeError; n0: INT ¬ 1; n1: INT ¬ 1; IF ABS[Vector2.Cross[v[0], v[1]]] < 0.015625 THEN { RETURN [[[sSize: 1, fSize: 2, phase: 1], ImagerTransformation.Create[a: 1, b: -1, c: clientToDevice.c, d: 1, e: 1, f: clientToDevice.f]]] }; DO v0x: INT ¬ Real.Round[vMul[0].x]; v0y: INT ¬ Real.Round[vMul[0].y]; v1x: INT ¬ Real.Round[vMul[1].x]; v1y: INT ¬ Real.Round[vMul[1].y]; SELECT TRUE FROM SqrLen[vMul[0], [v0x, v0y]] > SqrAbs[vMul[0]]*allowSqr => { vMul[0] ¬ Vector2.Add[v[0], vMul[0]]; n0 ¬ n0 + 1; }; SqrLen[vMul[1], [v1x, v1y]] > SqrAbs[vMul[1]]*allowSqr => { vMul[1] ¬ Vector2.Add[v[1], vMul[1]]; n1 ¬ n1 + 1; }; ENDCASE => { n0w: REAL ~ REAL[n0]*w; n1h: REAL ~ REAL[n1*h]; bs: BrickShape ~ BrickShapeFromDeltas[v0x, v0y, v1x, v1y]; brickShape: BrickShape ¬ bs; m: Transformation ~ ImagerTransformation.Create[a: v0x/n0w, b: v1x/n1h, c: clientToDevice.c, d: v0y/n0w, e: v1y/n1h, f: clientToDevice.f]; WHILE brickShape.sSize*brickShape.fSize < minLevels DO IF brickShape.sSize < brickShape.fSize THEN { brickShape.sSize ¬ brickShape.sSize + bs.sSize; brickShape.phase ¬ brickShape.phase + bs.phase; IF brickShape.phase >= bs.fSize THEN brickShape.phase ¬ brickShape.phase - bs.fSize; } ELSE { brickShape.fSize ¬ brickShape.fSize + bs.fSize; }; ENDLOOP; RETURN [[brickShape, m]] }; ENDLOOP; }; Brick: TYPE ~ ImagerBrick.Brick; FilterProc: TYPE ~ PROC [x, y: REAL] RETURNS [REAL]; eps: VEC ¬ [0.314156, 0.271828]; BrickFromDotScreen: PUBLIC PROC [pixelsPerDot: REAL, degrees: REAL, shape: REAL, allowedRelativeError: REAL, minLevels: CARD, maxSample: CARDINAL, pixelToDevice: Transformation, trc: PROC [REAL] RETURNS [REAL]] RETURNS [Brick] ~ { Filter: FilterProc ~ { tx: REAL ¬ RealFns.CosDeg[x*180+eps.x]; ty: REAL ¬ RealFns.CosDeg[y*180+eps.y]; RETURN [shape*tx+(1.0-shape)*ty] }; m: Transformation ~ ImagerTransformation.Cat[ImagerTransformation.Scale[pixelsPerDot*0.5], ImagerTransformation.Rotate[degrees], pixelToDevice]; brickSpec: BrickSpec ~ BrickSpecFromTransformedRectangle[2, 2, m, allowedRelativeError, minLevels]; brick: Brick ~ BrickFromFilter[brickSpec, Filter, maxSample, trc]; RETURN [brick]; }; LORA: TYPE ~ LIST OF REF ANY; NodeRep: TYPE ~ RECORD [pos: SF.Vec, value: REAL]; BrickFromFilter: PUBLIC PROC [brickSpec: BrickSpec, filter: FilterProc, maxSample: CARDINAL, trc: PROC [REAL] RETURNS [REAL]] RETURNS [Brick] ~ { brickShape: BrickShape ~ brickSpec.brickShape; Encode: PROC [pos: SF.Vec] RETURNS [CARD] ~ { RETURN [ImagerSys.LongMult[pos.s, brickShape.fSize]+NAT[pos.f]] }; n: CARD ~ brickShape.fSize*brickShape.sSize; m: CARD ~ IF n = 101 THEN 53 ELSE 101; Equidistribute: PROC [i: CARD] RETURNS [CARD] ~ { RETURN [(i*m+13) MOD n] }; list: LORA ¬ NIL; Compare: List.CompareProc ~ { a: REF NodeRep ~ NARROW[ref1]; b: REF NodeRep ~ NARROW[ref2]; IF a.value < b.value THEN RETURN [less]; IF a.value > b.value THEN RETURN [greater]; IF Equidistribute[Encode[a.pos]] < Equidistribute[Encode[b.pos]] THEN RETURN [less]; RETURN [greater]; }; bitsPerSample: NAT ~ SELECT maxSample FROM <= LAST[BYTE] => BITS[BYTE], <= LAST[CARD16] => BITS[CARD16], ENDCASE => BITS[CARDINAL]; sampleMap: ImagerSample.RasterSampleMap ~ ImagerSample.NewSampleMap[box: [max: [brickShape.sSize, brickShape.fSize]], bitsPerSample: bitsPerSample]; scale: REAL ~ 1.0/REAL[n]; realMaxSample: REAL ~ REAL[maxSample]; ImagerSample.Clear[sampleMap]; FOR s: NAT IN [0..NAT[brickShape.sSize]) DO FOR f: NAT IN [0..NAT[brickShape.fSize]) DO p: VEC ¬ ImagerTransformation.InverseTransformVec[m: brickSpec.m, v: [s + 0.5, f + 0.5]]; p ¬ [p.x - 1.0, p.y - 1.0]; WHILE p.x > 1.0 DO p.x ¬ p.x - 2.0 ENDLOOP; WHILE p.x < -1.0 DO p.x ¬ p.x + 2.0 ENDLOOP; WHILE p.y > 1.0 DO p.y ¬ p.y - 2.0 ENDLOOP; WHILE p.y < -1.0 DO p.y ¬ p.y + 2.0 ENDLOOP; list ¬ CONS[NEW[NodeRep ¬ [[s, f], filter[p.x, p.y]]], list]; ENDLOOP; ENDLOOP; list ¬ List.Sort[list: list, compareProc: Compare]; FOR i: CARD IN [0..n) DO node: REF NodeRep ~ NARROW[list.first]; rest: LIST OF REF ~ list.rest; valReal: REAL ¬ (i+0.5)*scale; IF trc # NIL THEN { valReal ¬ MIN[MAX[trc[valReal], 0.0], 1.0] }; { value: CARD ¬ RealInline.MCFix[valReal*(realMaxSample)]; IF value >= maxSample THEN value ¬ maxSample-1; ImagerSample.Put[map: sampleMap, index: node.pos, value: value]; }; list.rest ¬ NIL; list ¬ rest; ENDLOOP; RETURN [[maxSample, sampleMap, brickShape.phase]] }; END.  ImagerBrickImpl.mesa Copyright Σ 1987, 1989, 1991, 1993 by Xerox Corporation. All rights reserved. Michael Plass, May 27, 1993 4:35 pm PDT Finds p, q, g such that p*u + q*v = g = GCD(u, v) The dimensions asked for are tiny (less than 1/64 pixel area), so we'll punt and use a rather minimal brickSpec. In this near-degenerate case, we ignore the requested allowedRelativeError and minLevels. m should: map [0, 0] to [b, f], map vector [n0*w, 0] to vector [v0x, v0y], map vector [0, n1*h] to vector [v1x, v1y] relativeError _ Real.SqRt[MAX[SqrLen[vMul[0], [v0x, v0y]]/SqrAbs[vMul[0]], SqrLen[vMul[1], [v1x, v1y]]/SqrAbs[vMul[1]]]]; A filter function defined on x in [-1..+1], y in [-1..+1], returning values in [0..1] tx: REAL _ (x-1)*(x-1)*(x+1)*(x+1); ty: REAL _ (y-1)*(y-1)*(y+1)*(y+1); Assert i IN [0..n) This should return p[i], where p is a permutation of [0..n) that scatters things around pretty well. value: CARD ¬ MIN[MAX[CARD[Real.Round[valReal*realMaxSample]], 1], maxSample-1]; value: CARD ¬ Real.Round[valReal*(realMaxSample-1)]; Κ ^•NewlineDelimiter –(cedarcode) style™codešœ™Kšœ ΟeœC™NK™'K™—šΟk ˜ Kšœ žœ ˜1Kšœ žœ-˜?Kšœ žœ ˜KšœžœQ˜kKšœžœžœ˜.Kšœžœ ˜Kšœ žœ ˜Kšœžœ ˜Kšžœžœ˜Kšœžœžœ˜%—K˜KšΟnœžœž˜KšžœX˜_Kšžœ ˜šœž˜K˜šžœžœ žœ˜K˜—šœžœ'˜;K˜—šœ žœ˜*K˜—š œ žœžœžœžœ˜3K˜—šŸœžœžœžœ˜:Kšœ1™1Kšœžœ˜Kšœžœ˜Kšœžœ˜ Kšœžœ˜Kšœžœ˜Kšœžœ˜ šžœž˜Kšœ žœ ˜Kšœžœ˜Kšœžœ˜Kšœžœ˜K˜K˜Kšžœ˜—Kšžœ˜Kšœ˜K˜—šŸœžœžœžœžœžœžœžœžœ˜IK˜—š Ÿœžœžœžœžœ˜PKšœžœžœžœžœžœžœΟc˜QKšœ"žœžœ˜4Kšœžœ ˜Kšœžœ˜Kšœžœžœžœ˜=Kšžœ žœžœ˜1Kšžœžœžœ˜6Kšžœ˜Kšœ˜K˜—KšŸœžœžœžœžœžœžœ˜IšŸœžœžœžœžœžœžœ˜VK˜—šœ žœ˜(K˜—šŸ!œžœžœžœ8žœ žœžœ˜ šœžœžœžœ˜Kšœ:˜:Kšœ9˜9Kšœ˜—Kšœžœžœžœ˜Kšœ žœ-˜;Kšœžœ˜ Kšœžœ˜ šžœžœ'žœ˜3K™ΛKšžœƒ˜‰Kšœ˜—šž˜Kšœžœ˜!Kšœžœ˜!Kšœžœ˜!Kšœžœ˜!šžœžœž˜˜;Kšœ%˜%Kšœ ˜ Kšœ˜—˜;Kšœ%˜%Kšœ ˜ Kšœ˜—šžœ˜ Kšœžœžœ˜Kšœžœžœ˜K˜:K˜šœŠ˜Ššœ ™ Kšœ™Kšœ*™*Kšœ)™)——Kšœžœ\™y•StartOfExpansionB[a: REAL, b: REAL, c: REAL, d: REAL, e: REAL, f: REAL]šžœ/ž˜6šžœ$˜&šžœ˜J˜/K˜/Kšžœžœ0˜TK˜—šžœ˜J˜/Kšœ˜——Kšžœ˜—Kšžœ˜Kšœ˜——Kšžœ˜—Kšœ˜K˜—šœžœ˜ K˜—š œ žœžœžœžœžœ˜4KšœU™UK™—šœžœ˜ K˜—šŸœžœžœžœ žœ žœžœ žœ žœ&žœžœžœžœžœ ˜ζšŸœ˜Kšœžœ™#Kšœžœ™#Kšœžœ˜'Kšœžœ˜'Kšžœ˜ Kšœ˜—Kšœ˜Kšœc˜cKšœB˜BKšžœ ˜Kšœ˜K˜—š žœžœžœžœžœžœ˜K˜—š œ žœžœžœ žœ˜2K˜—šŸœžœžœ7žœžœžœžœžœžœ ˜‘Kšœ.˜.š Ÿœžœžœžœžœ˜-Kšžœ.žœ˜?Kšœ˜—Kšœžœ%˜,Kš œžœžœ žœžœ˜&š Ÿœžœžœžœžœ˜1Kšœ žœ™K™dKšžœ žœ˜Kšœ˜—Kšœžœžœ˜šŸœ˜Kšœžœ žœ˜Kšœžœ žœ˜Kšžœžœžœ˜(Kšžœžœžœ ˜+Kšžœ?žœžœ˜TKšžœ ˜Kšœ˜—–X[box: SF.Box, bitsPerSample: ImagerSample.BitsPerSample _ 1, bitsPerLine: INT _ 0]šœžœžœ ž˜*Kš œžœžœžœžœ˜Kš œžœžœžœžœ˜ Kšžœžœžœ˜—Kšœ”˜”Kšœžœžœ˜Kšœžœžœ ˜&Kšœ˜š žœžœžœžœž˜+š žœžœžœžœž˜+K–4[m: ImagerTransformation.Transformation, v: VEC]šœžœS˜YK˜Kšžœ žœžœ˜+Kšžœ žœžœ˜,Kšžœ žœžœ˜+Kšžœ žœžœ˜,Kšœžœžœ.˜=Kšžœ˜—Kšžœ˜—K–:[list: LIST OF REF ANY, compareProc: List.CompareProc]šœ3˜3šžœžœžœž˜K––[map: ImagerSample.SampleMap, index: SF.Vec, value: ImagerSample.Sample, function: ImagerSample.Function _ [dstFunc: null, srcFunc: null]]šœžœ žœ ˜'Kšœžœžœžœ ˜Kšœ žœ˜Kš žœžœžœ žœžœ˜A˜Kš œžœžœžœžœ6™PKšœžœ)™4Kšœžœœ*˜8Kšžœžœ˜/K˜@K˜—Kšœ žœ˜Kšœ ˜ Kšžœ˜—Kšžœ+˜1Kšœ˜K˜——Kšžœ˜—…—Ϊ)V