<> <> <> <> <> <<>> DIRECTORY SelectRegions, Basics USING [RawWords], RefTab USING [Create, Fetch, Ref, Store], SampleMapOps USING [Buffer, Clear, Create, Fill, Function, Get, GetPointer, ObtainBuffer, Put, PutSample, SampleMap, Transfer, UnsafeCreate]; SelectRegionsImpl: CEDAR PROGRAM IMPORTS RefTab, SampleMapOps EXPORTS SelectRegions = BEGIN OPEN SelectRegions; Buffer: TYPE ~ SampleMapOps.Buffer; SampleArrayHack: TYPE ~ REF SampleArrayHackRep; SampleArrayHackRep: TYPE ~ RECORD [ SEQUENCE n: NAT OF SampleVectorHack ]; SampleVectorHack: TYPE ~ LONG POINTER TO PACKED ARRAY [0..0) OF [0..256); ArrayHack: TYPE ~ REF ArrayHackRep; ArrayHackRep: TYPE ~ RECORD [ SEQUENCE n: NAT OF VectorHack ]; VectorHack: TYPE ~ LONG POINTER TO PACKED ARRAY [0..0) OF BOOLEAN; sampleMapToSampleArrayHack: RefTab.Ref ~ RefTab.Create[]; <> maskFcns: ARRAY Operation OF SampleMapOps.Function _ [ on: [or, null], off: [and, complement], flip: [xor, null] ]; PaintBrush: PUBLIC PROC [sm: SampleMap, loc: CVEC, op: Operation, brush: SampleMap] ~ { SampleMapOps.Transfer[ dest: sm, destStart: loc, source: [sampleMap: brush], function: maskFcns[op] ]; }; PaintPixel: PUBLIC PROC [sm: SampleMap, loc: CVEC, op: Operation] ~ { SampleMapOps.PutSample[sampleMap: sm, index: loc, value: 1, function: maskFcns[op]]; }; FillRectangle: PUBLIC PROC [sm: SampleMap, rect: Rectangle, op: Operation] ~ { SampleMapOps.Fill[dest: [sm, [rect.sMin, rect.fMin], [rect.sMax-rect.sMin, rect.fMax-rect.fMin]], value: 1, function: maskFcns[op]]; }; TestDifferences: PROC [a, b: Rectangle] RETURNS [list: LIST OF Rectangle _ NIL] ~ { Action: PROC [r: Rectangle] ~ { list _ CONS[r, list]; }; Differences[a, b, Action]; }; Intersect: PUBLIC PROC [a, b: Rectangle] RETURNS [Rectangle] ~ { RETURN [[sMin: MAX[a.sMin, b.sMin], fMin: MAX[a.fMin, b.fMin], sMax: MIN[a.sMax, b.sMax], fMax: MIN[a.fMax, b.fMax]]]; }; Differences: PUBLIC PROC [a, b: Rectangle, action: PROC [r: Rectangle]] ~ { i: Rectangle ~ Intersect[a, b]; DoRectangle: PROC [q: Rectangle] ~ { <> IF q.fMax>q.fMin THEN { IF q.sMini.sMax THEN action[[sMin: i.sMax, sMax: q.sMax, fMin: q.fMin, fMax: q.fMax]]; }; IF i.sMax>i.sMin THEN { IF q.fMini.fMax THEN action[[sMin: i.sMin, sMax: i.sMax, fMin: i.fMax, fMax: q.fMax]]; }; }; IF i.sMaxa.sMin AND a.fMax>a.fMin THEN action[a]; IF b.sMax>b.sMin AND b.fMax>b.fMin THEN action[b]; } ELSE { DoRectangle[a]; DoRectangle[b]; }; <b.sMax OR b.sMin>a.sMax OR a.fMin>b.fMax OR b.fMin>a.fMax THEN RETURN;>> }; <> trcSize: CARDINAL ~ 256; ApplyTRC: PUBLIC PROC [sm: SampleMap, sa: SampleArray, trcs: TRCSequence, bounds: Rectangle _ nullRectangle] ~ TRUSTED { UnsafeLookup: UNSAFE PROC [tbl, src, dst: LONG POINTER TO Basics.RawWords, count: NAT] ~ UNCHECKED { THROUGH [0..count/8) DO dst[0] _ tbl[src[0]]; dst[1] _ tbl[src[1]]; dst[2] _ tbl[src[2]]; dst[3] _ tbl[src[3]]; dst[4] _ tbl[src[4]]; dst[5] _ tbl[src[5]]; dst[6] _ tbl[src[6]]; dst[7] _ tbl[src[7]]; src _ src+8; dst _ dst+8; ENDLOOP; FOR k: NAT IN[0..count MOD 8) DO dst[k] _ tbl[src[k]] ENDLOOP; }; <<>> fSize: CARDINAL; scratchBuffer, bitBuffer: Buffer; scratchPtr: LONG POINTER TO Basics.RawWords; scratchMapByteKludge: SampleMap; table: Buffer; tablePtr: LONG POINTER TO Basics.RawWords; IF sa.n#trcs.n THEN ERROR; bounds _ Intersect[bounds, [sMin: 0, fMin: 0, sMax: sa.sSize-1, fMax: sa.fSize-1]]; fSize _ bounds.fMax+1-bounds.fMin; bitBuffer _ SampleMapOps.ObtainBuffer[length: fSize]; scratchBuffer _ SampleMapOps.ObtainBuffer[length: fSize]; scratchPtr _ SampleMapOps.GetPointer[buffer: scratchBuffer, start: 0, count: fSize]; scratchMapByteKludge _ SampleMapOps.UnsafeCreate[sSize: 1, fSize: fSize*2, bitsPerSample: 8, bitsPerLine: fSize*16, base: [word: scratchPtr, bit: 0], nWords: fSize, ref: NIL]; table _ SampleMapOps.ObtainBuffer[length: trcSize*2]; tablePtr _ SampleMapOps.GetPointer[buffer: table, start: 0, count: trcSize*2]; FOR sample: NAT IN [0..trcSize) DO table[sample] _ sample; ENDLOOP; FOR i: NAT IN [0..sa.n) DO sep: SampleMap ~ sa.layer[i].sm; LOOPHOLE[tablePtr+trcSize, LONG POINTER TO TRC]^ _ trcs[i]^; FOR scan: CARDINAL IN [bounds.sMin .. bounds.sMax] DO SampleMapOps.Get[buffer: bitBuffer, count: fSize, sampleMap: sm, s: scan, f: bounds.fMin]; SampleMapOps.Get[buffer: scratchBuffer, count: fSize, sampleMap: sep, s: scan, f: bounds.fMin]; SampleMapOps.Put[buffer: bitBuffer, count: fSize, sampleMap: scratchMapByteKludge, df: 2]; UnsafeLookup[tbl: tablePtr, src: scratchPtr, dst: scratchPtr, count: fSize]; SampleMapOps.Put[buffer: scratchBuffer, count: fSize, sampleMap: sep, s: scan, f: bounds.fMin]; ENDLOOP; ENDLOOP; }; <> OutOfRectangle: PUBLIC ERROR ~ CODE; Direction: TYPE ~ { r, ur, u, ul, l, dl, d, dr}; next: ARRAY Direction OF Direction ~ [ur, u, ul, l, dl, d, dr, r]; prv: ARRAY Direction OF Direction ~ [dr, r, ur, u, ul, l, dl, d]; start: ARRAY Direction OF Direction ~ [dr, dr, r, r, ul, ul, dl, dl]; <> ds: ARRAY Direction OF INTEGER ~ [ 0, -1, -1, -1, 0, 1, 1, 1]; df: ARRAY Direction OF INTEGER ~ [ 1, 1, 0, -1, -1, -1, 0, 1]; Fill: PUBLIC PROC [sm: SampleMap, loc: CVEC, bounds: Rectangle _ nullRectangle] RETURNS [extent: Rectangle] ~ TRUSTED { <> <<1. Find a left edge.>> <<2. For each edge not previously found:>> <> <> sMin, sMax, fMin, fMax: CARDINAL; filledMap: SampleMap ~ SampleMapOps.Create[sSize: sm.sSize, fSize: sm.fSize, bitsPerSample: 1]; edgesMap: SampleMap ~ SampleMapOps.Create[sSize: sm.sSize, fSize: sm.fSize, bitsPerSample: 1]; filled: ArrayHack ~ SampleMapToArrayHack[filledMap]; edges: ArrayHack ~ SampleMapToArrayHack[edgesMap]; mask: ArrayHack ~ SampleMapToArrayHack[sm]; leftEdges: LIST OF CVEC _ NIL; IfRectangle: PROC [v: CVEC] RETURNS [BOOLEAN] ~ TRUSTED INLINE { RETURN [~(v.s IN (sMin .. sMax) AND v.f IN (fMin .. fMax))] }; IfEdge: PROC [v: CVEC] RETURNS [BOOLEAN] ~ TRUSTED INLINE { RETURN [(mask[v.s][v.f] AND ~filled[v.s][v.f]) OR IfRectangle[v]] }; RememberLeftEdgePos: PROC [p: CVEC] ~ TRUSTED INLINE { leftEdges _ CONS[p, leftEdges]; extent.sMin _ MIN[extent.sMin, p.s]; extent.sMax _ MAX[extent.sMax, p.s]; extent.fMin _ MIN[extent.fMin, p.f]; <> }; GetNextLeftEdgePos: PROC RETURNS [p: CVEC] ~ TRUSTED INLINE { p _ leftEdges.first; leftEdges _ leftEdges.rest; }; Navigate: PROC [initial: CVEC] ~ TRUSTED { IsSingleton: PROC RETURNS [BOOLEAN] ~ TRUSTED INLINE { count: CARDINAL _ 0; IF IfRectangle[initial] THEN RETURN [FALSE]; --We know it's not a singleton on the bounds edge, and it may be dangerous to check as below... FOR f: INTEGER IN [-1..1] DO FOR s: INTEGER IN [-1..1] DO IF IfEdge[[s: initial.s+s, f: initial.f+f]] THEN count _ count+1; ENDLOOP; ENDLOOP; RETURN [count <= 1] }; <> direction, lastDirection: Direction _ dr; --(Choosing dr rather than r, so that the algorithm checks dl and d). pos: CVEC _ initial; IF edges[initial.s][initial.f] THEN RETURN; --We've already seen this edge IF IsSingleton[] THEN { RememberLeftEdgePos[initial]; RETURN; }; <> lastDirection _ r; --(Actually, know can't get this...) UNTIL IfEdge[[s: pos.s-ds[lastDirection], f: pos.f-df[lastDirection]]] DO --Reversed sign is because we're moving into rather than out of pos. lastDirection _ prv[lastDirection]; ENDLOOP; DO edges[pos.s][pos.f] _ TRUE; direction _ start[direction]; DO IF IfEdge[[s: pos.s+ds[direction], f: pos.f+df[direction]]] THEN EXIT ELSE IF direction=r THEN RememberLeftEdgePos[pos]; --I.e., if we see a blank spot to our right, then this is a left edge direction _ next[direction]; ENDLOOP; <<>> <> pos _ [s: pos.s+ds[direction], f: pos.f+df[direction]]; <> IF pos=initial AND direction=lastDirection THEN EXIT; ENDLOOP; IF lastDirection IN [ur..ul] THEN RememberLeftEdgePos[initial]; }; <
> SampleMapOps.Clear[filledMap]; SampleMapOps.Clear[edgesMap]; bounds _ Intersect[bounds, [sMin: 0, fMin: 0, sMax: sm.sSize-1, fMax: sm.fSize-1]]; sMin _ bounds.sMin; sMax _ bounds.sMax; fMin _ bounds.fMin; fMax _ bounds.fMax; IF ~loc.s IN (sMin .. sMax) OR ~loc.f IN (fMin .. fMax) THEN ERROR OutOfRectangle[]; IF mask[loc.s][loc.f] THEN RETURN; --If it's already on, there's nothing we can do... extent _ [sMin: loc.s, sMax: loc.s, fMin: loc.f, fMax: loc.f]; UNTIL mask[loc.s][loc.f] DO --Find a right edge loc.f _ loc.f + 1; ENDLOOP; Navigate[loc]; --Navigate the first edge found UNTIL leftEdges=NIL DO --While left edge positions remain... f, s: CARDINAL; vector: LONG POINTER TO PACKED ARRAY [0..0) OF BOOLEAN; [[s: s, f: f]] _ GetNextLeftEdgePos[]; vector _ mask[s]; f _ f+1; --Start on blank square UNTIL vector[f] OR f=fMax DO vector[f] _ filled[s][f] _ TRUE; f _ f+1; ENDLOOP; <> extent.fMax _ MAX[extent.fMax, f]; Navigate[[s: s, f: f]]; ENDLOOP; }; defaultColorDistance: PUBLIC CARDINAL _ 10; MatchColorFill: PUBLIC PROC [sm: SampleMap, sa: SampleArray, loc: CVEC, bounds: Rectangle _ nullRectangle, colorDistance: CARDINAL _ defaultColorDistance] RETURNS [extent: Rectangle] ~ TRUSTED { <> <<1. Find a left edge.>> <<2. For each edge not previously found:>> <> <> sMin, sMax, fMin, fMax: CARDINAL; filledMap: SampleMap ~ SampleMapOps.Create[sSize: sm.sSize, fSize: sm.fSize, bitsPerSample: 1]; edgesMap: SampleMap ~ SampleMapOps.Create[sSize: sm.sSize, fSize: sm.fSize, bitsPerSample: 1]; filled: ArrayHack ~ SampleMapToArrayHack[filledMap]; edges: ArrayHack ~ SampleMapToArrayHack[edgesMap]; mask: ArrayHack ~ SampleMapToArrayHack[sm]; redHack, greenHack, blueHack: SampleArrayHack; leftEdges: LIST OF CVEC _ NIL; red, green, blue, g2r, g2b: INTEGER; ColorDistance: PROC [r, g, b: CARDINAL] RETURNS [d: CARDINAL] ~ TRUSTED INLINE { RETURN [ABS[INTEGER[g]-INTEGER[r] - g2r] + ABS[INTEGER[g]-INTEGER[b] - g2b]]; }; FetchRed: PROC [v: CVEC] RETURNS [value: CARDINAL] ~ TRUSTED INLINE { RETURN [redHack[v.s][v.f]]; }; FetchGreen: PROC [v: CVEC] RETURNS [value: CARDINAL] ~ TRUSTED INLINE { RETURN [greenHack[v.s][v.f]]; }; FetchBlue: PROC [v: CVEC] RETURNS [value: CARDINAL] ~ TRUSTED INLINE { RETURN [blueHack[v.s][v.f]]; }; IfBounds: PROC [v: CVEC] RETURNS [BOOLEAN] ~ TRUSTED INLINE { RETURN [~(v.s IN (sMin .. sMax) AND v.f IN (fMin .. fMax))] }; IfEdge: PROC [v: CVEC] RETURNS [BOOLEAN] ~ TRUSTED INLINE { RETURN [IfBounds[v] OR (ColorDistance[r: FetchRed[v], g: FetchGreen[v], b: FetchBlue[v]] > colorDistance)]; }; RememberLeftEdgePos: PROC [p: CVEC] ~ TRUSTED INLINE { leftEdges _ CONS[p, leftEdges]; extent.sMin _ MIN[extent.sMin, p.s]; extent.sMax _ MAX[extent.sMax, p.s]; extent.fMin _ MIN[extent.fMin, p.f]; <> }; GetNextLeftEdgePos: PROC RETURNS [p: CVEC] ~ TRUSTED INLINE { p _ leftEdges.first; leftEdges _ leftEdges.rest; }; Navigate: PROC [initial: CVEC] ~ TRUSTED { IsSingleton: PROC RETURNS [BOOLEAN] ~ TRUSTED INLINE { count: CARDINAL _ 0; IF IfBounds[initial] THEN RETURN [FALSE]; --We know it's not a singleton on the bounds edge, and it may be dangerous to check as below... FOR f: INTEGER IN [-1..1] DO FOR s: INTEGER IN [-1..1] DO IF IfEdge[[s: initial.s+s, f: initial.f+f]] THEN count _ count+1; ENDLOOP; ENDLOOP; RETURN [count <= 1] }; <> direction, lastDirection: Direction _ dr; --(Choosing dr rather than r, so that the algorithm checks dl and d). pos: CVEC _ initial; IF edges[initial.s][initial.f] THEN RETURN; --We've already seen this edge IF IsSingleton[] THEN { RememberLeftEdgePos[initial]; RETURN; }; <> lastDirection _ r; --(Actually, know can't get this...) UNTIL IfEdge[[s: pos.s-ds[lastDirection], f: pos.f-df[lastDirection]]] DO --Reversed sign is because we're moving into rather than out of pos. lastDirection _ prv[lastDirection]; ENDLOOP; DO edges[pos.s][pos.f] _ TRUE; direction _ start[direction]; DO IF IfEdge[[s: pos.s+ds[direction], f: pos.f+df[direction]]] THEN EXIT ELSE IF direction=r THEN RememberLeftEdgePos[pos]; --I.e., if we see a blank spot to our right, then this is a left edge direction _ next[direction]; ENDLOOP; <<>> <> pos _ [s: pos.s+ds[direction], f: pos.f+df[direction]]; <> IF pos=initial AND direction=lastDirection THEN EXIT; ENDLOOP; IF lastDirection IN [ur..ul] THEN RememberLeftEdgePos[initial]; }; <
> IF sa.n#3 THEN ERROR; redHack _ SampleMapToSampleArrayHack[sa[0].sm]; greenHack _ SampleMapToSampleArrayHack[sa[1].sm]; blueHack _ SampleMapToSampleArrayHack[sa[2].sm]; SampleMapOps.Clear[filledMap]; SampleMapOps.Clear[edgesMap]; bounds _ Intersect[bounds, [sMin: 0, fMin: 0, sMax: sm.sSize-1, fMax: sm.fSize-1]]; sMin _ bounds.sMin; sMax _ bounds.sMax; fMin _ bounds.fMin; fMax _ bounds.fMax; IF ~loc.s IN (sMin .. sMax) OR ~loc.f IN (fMin .. fMax) THEN ERROR OutOfRectangle[]; extent _ [sMin: loc.s, sMax: loc.s, fMin: loc.f, fMax: loc.f]; <> red _ FetchRed[loc]; green _ FetchGreen[loc]; blue _ FetchBlue[loc]; g2r _ green - red; g2b _ green - blue; UNTIL IfEdge[loc] DO --Find a right edge loc.f _ loc.f + 1; ENDLOOP; Navigate[loc]; --Navigate the first edge found UNTIL leftEdges=NIL DO --While left edge positions remain... f, s: CARDINAL; vector: LONG POINTER TO PACKED ARRAY [0..0) OF BOOLEAN; [[s: s, f: f]] _ GetNextLeftEdgePos[]; vector _ mask[s]; f _ f+1; --Start on blank square UNTIL IfEdge[[s: s, f: f]] OR f=fMax DO vector[f] _ filled[s][f] _ TRUE; f _ f+1; ENDLOOP; <> extent.fMax _ MAX[extent.fMax, f]; Navigate[[s: s, f: f]]; ENDLOOP; }; MatchColor: PUBLIC PROC [sm: SampleMap, sa: SampleArray, rgb: RGB, bounds: Rectangle _ nullRectangle, colorDistance: CARDINAL _ defaultColorDistance] ~ TRUSTED { mask: ArrayHack ~ SampleMapToArrayHack[sm]; redHack, greenHack, blueHack: SampleArrayHack; red, green, blue: INTEGER; ColorDistance: PROC [r, g, b: CARDINAL] RETURNS [d: CARDINAL] ~ TRUSTED INLINE { RETURN [ABS[INTEGER[r] - red] + ABS[INTEGER[g]-green] + ABS[INTEGER[b] - blue]]; }; FetchRed: PROC [s, f: CARDINAL] RETURNS [value: CARDINAL] ~ TRUSTED INLINE { RETURN [redHack[s][f]]; }; FetchGreen: PROC [s, f: CARDINAL] RETURNS [value: CARDINAL] ~ TRUSTED INLINE { RETURN [greenHack[s][f]]; }; FetchBlue: PROC [s, f: CARDINAL] RETURNS [value: CARDINAL] ~ TRUSTED INLINE { RETURN [blueHack[s][f]]; }; IF sa.n#3 THEN ERROR; redHack _ SampleMapToSampleArrayHack[sa[0].sm]; greenHack _ SampleMapToSampleArrayHack[sa[1].sm]; blueHack _ SampleMapToSampleArrayHack[sa[2].sm]; <> red _ rgb.r; green _ rgb.g; blue _ rgb.b; bounds _ Intersect[bounds, [sMin: 0, fMin: 0, sMax: sm.sSize-1, fMax: sm.fSize-1]]; FOR s: CARDINAL IN [bounds.sMin .. bounds.sMax] DO vector: LONG POINTER TO PACKED ARRAY [0..0) OF BOOLEAN ~ mask[s]; FOR f: CARDINAL IN [bounds.fMin .. bounds.fMax] DO IF ColorDistance[r: FetchRed[s: s, f: f], g: FetchGreen[s: s, f: f], b: FetchBlue[s: s, f: f]] < colorDistance THEN vector[f] _ TRUE; ENDLOOP; ENDLOOP; }; DiscriminateColor: PUBLIC PROC [sm: SampleMap, sa: SampleArray, near, far: RGB, bounds: Rectangle _ nullRectangle] ~ TRUSTED { nearR: INTEGER ~ near.r; nearG: INTEGER ~ near.g; nearB: INTEGER ~ near.b; farR: INTEGER ~ far.r; farG: INTEGER ~ far.g; farB: INTEGER ~ far.b; mask: ArrayHack ~ SampleMapToArrayHack[sm]; redHack, greenHack, blueHack: SampleArrayHack; Near: PROC [r, g, b: CARDINAL] RETURNS [BOOLEAN] ~ TRUSTED INLINE { RETURN [ ABS[INTEGER[r] - nearR] + ABS[INTEGER[g]-nearG] + ABS[INTEGER[b] - nearB] < ABS[INTEGER[r] - farR] + ABS[INTEGER[g]-farG] + ABS[INTEGER[b] - farB] ]; }; IF sa.n#3 THEN ERROR; redHack _ SampleMapToSampleArrayHack[sa[0].sm]; greenHack _ SampleMapToSampleArrayHack[sa[1].sm]; blueHack _ SampleMapToSampleArrayHack[sa[2].sm]; bounds _ Intersect[bounds, [sMin: 0, fMin: 0, sMax: sm.sSize-1, fMax: sm.fSize-1]]; FOR s: CARDINAL IN [bounds.sMin .. bounds.sMax] DO vector: LONG POINTER TO PACKED ARRAY [0..0) OF BOOLEAN ~ mask[s]; FOR f: CARDINAL IN [bounds.fMin .. bounds.fMax] DO IF Near[r: redHack[s][f], g: greenHack[s][f], b: blueHack[s][f]] THEN vector[f] _ TRUE; ENDLOOP; ENDLOOP; }; SampleMapToSampleArrayHack: PROC [sm: SampleMap] RETURNS [sah: SampleArrayHack] ~ TRUSTED { ref: REF ~ RefTab.Fetch[x: sampleMapToSampleArrayHack, key: sm].val; IF ref=NIL THEN { ptr: LONG POINTER _ sm.base.word; offset: NAT _ sm.bitsPerLine/16; IF sm.base.bit#0 OR sm.bitsPerSample#8 THEN ERROR; sah _ NEW[SampleArrayHackRep[sm.sSize]]; FOR i: NAT IN [0..sah.n) DO sah[i] _ ptr; ptr _ ptr+offset; ENDLOOP; [] _ RefTab.Store[x: sampleMapToSampleArrayHack, key: sm, val: sah]; } ELSE sah _ NARROW[ref]; }; SampleMapToArrayHack: PROC [sm: SampleMap] RETURNS [array: ArrayHack] ~ TRUSTED { ptr: LONG POINTER _ sm.base.word; offset: NAT _ sm.bitsPerLine/16; IF sm.base.bit#0 OR sm.bitsPerSample#1 THEN ERROR; array _ NEW[ArrayHackRep[sm.sSize]]; FOR i: NAT IN [0..array.n) DO array[i] _ ptr; ptr _ ptr+offset; ENDLOOP; }; END.