DIRECTORY IGScanConverter, Imager, Inline, Mopcodes, Real, Scaled ; IGScanConverterImpl: CEDAR MONITOR IMPORTS Inline, Real, Scaled EXPORTS IGScanConverter = BEGIN OPEN IGScanConverter; xLimit: NAT _ 60; yLimit: NAT _ 60; BITAND: PROC[a, b: CARDINAL] RETURNS [CARDINAL] = TRUSTED MACHINE CODE {Mopcodes.zAND}; BITOR: PROC[a, b: CARDINAL] RETURNS [CARDINAL] = TRUSTED MACHINE CODE {Mopcodes.zOR}; BITXOR: PROC[a, b: CARDINAL] RETURNS [CARDINAL] = TRUSTED MACHINE CODE {Mopcodes.zXOR}; Floor8: PROC[a: CARDINAL] RETURNS [NAT] = INLINE {RETURN[Inline.BITSHIFT[a, -8]]}; Mid: PROC[a, b: CARDINAL] RETURNS [CARDINAL] = INLINE {RETURN[Inline.BITSHIFT[(a+b),-1]]}; Rec6: TYPE = RECORD [a, b, c, d, e, f: CARDINAL]; ShortVec: TYPE = RECORD [x, y: CARDINAL]; XValueFor: PUBLIC PROCEDURE [cubic: CubicRec, y: Scaled.Value] RETURNS [INTEGER] = { OPEN cubic; yRel: CARDINAL; IF y.Ceiling[] < ymin THEN RETURN [LAST[INTEGER]]; IF y.Floor[] > ymax THEN RETURN [FIRST[INTEGER]]; yRel _ y.MINUS[Scaled.FromInt[ymin]].Scale[8].Round[]; IF yRel <= y0 THEN IF yRel < y0 OR openAt0 THEN RETURN [LAST[INTEGER]]; IF yRel >= y3 THEN IF yRel > y3 OR openAt3 THEN RETURN [FIRST[INTEGER]]; WHILE y3 - y0 > 3 -- Required to guarantee termination. AND 0 # BITAND[ BITOR[BITXOR[x0, x1], BITOR[BITXOR[x1, x2], BITXOR[x2, x3]]], LAST[CARDINAL]-255 ] DO a: ShortVec _ [Mid[x0, x1], Mid[y0, y1]]; b: ShortVec _ [Mid[x1, x2], Mid[y1, y2]]; c: ShortVec _ [Mid[x2, x3], Mid[y2, y3]]; ab: ShortVec _ [Mid[a.x, b.x], Mid[a.y, b.y]]; bc: ShortVec _ [Mid[b.x, c.x], Mid[b.y, c.y]]; p: ShortVec _ [Mid[ab.x, bc.x], Mid[ab.y, bc.y]]; IF yRel=0 THEN { sqrt: REAL = Real.SqRt[d]; t0 _ (-b-sqrt)/2; t1 _ (-b+sqrt)/2; }; } ELSE IF d1#0.0 THEN t0 _ -d0/d1; t0 _ MIN[1.0, MAX[0.0, t0]]; t1 _ MIN[1.0, MAX[0.0, t1]]; IF t0 > t1 THEN {t: REAL _ t0; t0 _ t1; t1 _ t}; IF 0.0 < t0 AND t0 < t1 AND t1 < 1.0 THEN { low, middle, high: Imager.Bezier; [middle, high] _ SubDivide[bezier, t1]; [low, middle] _ SubDivide[middle, t0/t1]; Delta[low.b2.y-low.b3.y]; low.b2.y _ low.b3.y; Delta[middle.b1.y-middle.b0.y]; middle.b1.y _ middle.b0.y; Delta[middle.b2.y-middle.b3.y]; middle.b2.y _ middle.b3.y; Delta[high.b1.y-high.b0.y]; high.b1.y _ high.b0.y; AppendMonotoneBezier[devicePath, low]; AppendMonotoneBezier[devicePath, middle]; AppendMonotoneBezier[devicePath, high]; } ELSE IF t0 IN (0.0..1.0) OR t1 IN (0.0..1.0) THEN { low, high: Imager.Bezier; [low, high] _ SubDivide[bezier, IF t0 IN (0.0..1.0) THEN t0 ELSE t1]; Delta[low.b2.y-low.b3.y]; low.b2.y _ low.b3.y; Delta[high.b1.y-high.b0.y]; high.b1.y _ high.b0.y; AppendMonotoneBezier[devicePath, low]; AppendMonotoneBezier[devicePath, high]; } ELSE AppendMonotoneBezier[devicePath, bezier]; }; numberOfDeltas: INT _ 0; sumOfAbsDeltas: REAL _ 0.0; maxDelta: REAL _ 0.0; Delta: PROCEDURE [delta: REAL] = { numberOfDeltas _ numberOfDeltas + 1; sumOfAbsDeltas _ sumOfAbsDeltas + ABS[delta]; IF ABS[delta] > maxDelta THEN maxDelta _ ABS[delta]; }; DeltaStats: PROCEDURE RETURNS [n: INT, sum: REAL, max: REAL] = { n _ numberOfDeltas; sum _ sumOfAbsDeltas; max _ maxDelta; numberOfDeltas _ 0; sumOfAbsDeltas _ maxDelta _ 0.0; }; PushPath: PUBLIC PROCEDURE [ devicePath: DevicePath, path: Imager.Path, transformation: Imager.Transformation ] = { firstPoint, lastPoint: Imager.Vec; started: BOOLEAN _ FALSE; outlineStart: NAT _ devicePath.length; Move: PROC [v: Imager.Vec] = { IF started THEN Close[]; outlineStart _ devicePath.length; started _ TRUE; firstPoint _ lastPoint _ v; }; Line: PROC [v: Imager.Vec] = { started _ TRUE; AppendBezier[devicePath, [lastPoint, Interpolate[0.3333333, lastPoint, v], Interpolate[0.6666667, lastPoint, v], v]]; lastPoint _ v; }; Curve: PROC [v1, v2, v3: Imager.Vec] = { started _ TRUE; AppendBezier[devicePath, [lastPoint, v1, v2, v3]]; lastPoint _ v3; }; Close: PROC = { IF started AND lastPoint # firstPoint THEN Line[firstPoint]; FOR j: NAT IN [outlineStart..devicePath.length) DO i: NAT = IF j = outlineStart THEN devicePath.length-1 ELSE j-1; cubicI: Cubic = devicePath.seq[i]; cubicJ: Cubic = devicePath.seq[j]; iup: BOOLEAN = cubicI.ascending; jup: BOOLEAN = cubicJ.ascending; IF iup THEN cubicI.openAt3 _ FALSE ELSE cubicI.openAt0 _ NOT jup; IF jup THEN cubicJ.openAt0 _ iup ELSE cubicJ.openAt3 _ FALSE; ENDLOOP; started _ FALSE; }; path.generateProc[path, transformation, Move, Line, Curve]; Close[]; devicePath.numberOfOutlines _ devicePath.numberOfOutlines + 1; }; PopPath: PUBLIC PROCEDURE [devicePath: DevicePath] = { devicePath.numberOfOutlines _ devicePath.numberOfOutlines-1; WHILE devicePath.length > 0 AND devicePath.seq[devicePath.length-1].outlineNumber = devicePath.numberOfOutlines DO devicePath.length _ devicePath.length - 1; ENDLOOP; }; ActivePieceTable: TYPE = REF ActivePieceTableRec; ActivePieceTableRec: TYPE = RECORD [ SEQUENCE maxLength: NAT OF ActivePieceRec ]; ActivePieceRec: TYPE = RECORD [ sortKey: INTEGER, pieceIndex: NAT ]; activePieceTable: ActivePieceTable _ NIL; AllocActivePieceTable: ENTRY PROC [size: NAT] RETURNS [a: ActivePieceTable] = { IF activePieceTable # NIL AND activePieceTable.maxLength >= size THEN {a _ activePieceTable; activePieceTable _ NIL} ELSE a _ NEW[ActivePieceTableRec[size]] }; FreeActivePieceTable: ENTRY PROC [a: ActivePieceTable] = { IF activePieceTable = NIL OR a.maxLength > activePieceTable.maxLength THEN activePieceTable _ a }; shellD: ARRAY [1..11] OF CARDINAL = [1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 65535]; ShellSort: PROCEDURE [table: ActivePieceTable, start, startPlusLength: NAT] = TRUSTED { length: NAT _ startPlusLength - start; passesPlusOne: [1..11] _ 1; startPtr: LONG POINTER TO ActivePieceRec _ @(table[start]); endPtr: LONG POINTER TO ActivePieceRec _ @(table[startPlusLength-1]) + SIZE[ActivePieceRec]; UNTIL shellD[passesPlusOne _ passesPlusOne+1] >= length DO NULL ENDLOOP; FOR pass: NAT DECREASING IN [1..passesPlusOne) DO h: NAT _ shellD[pass]; hTimesSize: CARDINAL _ h*SIZE[ActivePieceRec]; iPtr: LONG POINTER TO ActivePieceRec _ startPtr; FOR iPtr: LONG POINTER TO ActivePieceRec _ startPtr, iPtr + SIZE[ActivePieceRec] UNTIL iPtr = endPtr DO a: ActivePieceRec _ iPtr^; jPtr: LONG POINTER TO ActivePieceRec _ iPtr; b: LONG POINTER TO ActivePieceRec; WHILE LOOPHOLE[(b _ jPtr-hTimesSize), LONG CARDINAL] >= LOOPHOLE[startPtr, LONG CARDINAL] AND a.sortKey < b^.sortKey DO jPtr^ _ b^; jPtr _ b; ENDLOOP; jPtr^ _ a; ENDLOOP; ENDLOOP; }; InsertionSort: PROCEDURE [table: ActivePieceTable, start, startPlusLength: NAT] = { FOR i: NAT IN [start..startPlusLength) DO a: ActivePieceRec _ table[i]; b: ActivePieceRec; j: NAT _ i; WHILE j>0 AND a.sortKey < (b _ table[j-1]).sortKey DO table[j] _ b; j _ j-1 ENDLOOP; table[j] _ a; ENDLOOP; }; Sort: PROCEDURE [table: ActivePieceTable, start, startPlusLength: NAT] _ ShellSort; WrapTable: TYPE = REF WrapTableRec; WrapTableRec: TYPE = RECORD [ SEQUENCE maxLength: NAT OF INTEGER ]; wrapTable: WrapTable _ NIL; AllocWrapTable: ENTRY PROC [size: NAT] RETURNS [w: WrapTable] = { IF wrapTable # NIL AND wrapTable.maxLength >= size THEN {w _ wrapTable; wrapTable _ NIL} ELSE w _ NEW[WrapTableRec[size]] }; FreeWrapTable: ENTRY PROC [w: WrapTable] = { IF wrapTable = NIL OR w.maxLength > wrapTable.maxLength THEN wrapTable _ w }; ScanConvert: PUBLIC PROCEDURE [devicePath: DevicePath, LineProc: PROC[xmin, xmax, y: INTEGER]] = { length: NAT _ devicePath.length; outlines: NAT _ devicePath.numberOfOutlines; active: ActivePieceTable _ AllocActivePieceTable[length]; wrap: WrapTable _ AllocWrapTable[outlines]; firstActive, firstUnActivated: NAT _ 0; y: INTEGER _ FIRST[INTEGER]; FOR i: NAT IN [0..length) DO active[i] _ [sortKey: devicePath.seq[i].ymin, pieceIndex: i]; ENDLOOP; Sort[active, 0, length]; WHILE firstActive xStart THEN LineProc[xStart, a.sortKey, y]; nonZeroWrapCount _ nonZeroWrapCount - 1; }; wrap[k] _ w; ENDLOOP; ENDLOOP; FreeActivePieceTable[active]; FreeWrapTable[wrap]; }; END. าIGScanConverterImpl.mesa Created March 11, 1983 Edited by Michael Plass, March 11, 1983 1:50 pm These parameters limit the extent of the pieces in either the x or y directions. Decreasing these paramters will use more devicepath storage, but will lead to fewer subdivisions in the inner loop. Tune them to minimize the overall time. Some inlines for basic bit-hacking operations. Returns LAST[INTEGER] if y is below the piece, FIRST[INTEGER] if it is above, otherwise the x-intercept rounded to the nearest integer. -- The following quantity is zero iff x0, x1, x2, and x3 match in their high-order bits. Let garbage collector get it. Free old sequence here First find the coefficients of the y projection. Now find the coefficients of the derivative. Find where the derivative vanishes. Now break it up as needed This is used to monitor the effects of roundoff error in the computation of the monotone pieces. The globals are meant to be examined with the debugger. ส˜Jšœ™J™J™/unitšฯk ˜ Jšœ˜J˜J˜J˜ J˜Jšœ˜J˜—šœœ˜"Jšœ˜Jšœ˜Jšœœœ˜™๎Jšœœ˜Jšœœ˜—J™™.Jšœœœœœœœœ˜WJšœœœœœœœœ˜UJšœœœœœœœœ˜WJšฯnœœœœœœœœ ˜RJšžœœœœœœœœ ˜Z—Kšœœœœ˜1Kšœ œœœ˜)š ž œœ œ$œœ˜TJš œœœœœK™‡Jšœ˜ Jšœœ˜Jš œœœœœ˜2Jš œœœœœ˜1Jšœ œ(˜6Jšœ œœ œ œœœœ˜GJšœ œœ œ œœœœ˜Hšœฯc%˜8šœ˜JšœX™Xšœ˜Jš œœ œœ œ ˜=Jšœœ˜Jšœ˜——Jš˜Jšœ)˜)Jšœ)˜)Jšœ)˜)Jšœ.˜.Jšœ.˜.Jšœ1˜1Jšœ œ@˜PJšœœ œœ˜/Jšœ@˜DJšœ˜—Jšœ˜Jšœ˜—Kšž œœ!œuœ˜วKšœœœ0˜Kšžœ œœ!˜PJšœ œœ˜.Jš žœœœœœœ˜lJšœF˜FJšœF˜FJšœF˜FJšœ/˜/Jšœ/˜/Jšœ2˜2Jšœq˜wJ˜—šžœœ œœ˜?Jšœ œ˜ Jšœ˜Jšœ ˜ Jšœœ˜+J˜—šžœœ œ*œ˜HJ™—šžœœ œ˜4Jšœ˜Jšœ ˜ Jšœ˜—šžœ œ3˜VJšœ˜ Jš œœ.œ#œœ˜oJšœ œœ œ ˜*šœ-œ˜6šœœœ˜ Jšœœœœ.˜KJšœ˜—šœœœ˜'Jšœ˜Jš˜—Jšœ™Jšœ˜Jšœ˜—Jšœ*˜*Jšœ*˜*Jšœœ˜šœœœ˜JšœN˜NJšœœ˜J˜—Jšœ2˜2Jšœ œ1˜AJšœ˜Jšœ˜Jšœœœ˜SJšœœœ˜SJšœœœ˜SJšœœœ˜SJšœœ.˜AJšœœ.˜AJšœœ.˜AJšœœ.˜AJšœœ+˜FJšœ˜—šžœ œ.˜LJšœœœ9˜LJšœœœA˜TJšœœœ9˜LJšœœœA˜TJšœ˜šœœœ˜Jšœœœ˜Jšœœ˜9Jšœ'˜'—šœ˜Jšœ˜Jšœ$˜$Jšœ$˜$J˜—J˜—šžœ œ4˜Sšœ˜Jšœ<˜˜>Jšœ˜—šžœœ œ˜6Jšœ<˜<šœœQ˜rJšœ*˜*Jš˜—Jšœ˜—Kšœœœ˜1šœœœ˜$Jšœ œœ˜)J˜—šœœœ˜Jšœ œ˜Jšœ ˜J˜—Kšœ%œ˜)š žœœœœœ˜OJš œœœ$œ+œ˜tJšœœ˜'Jšœ˜—šžœœœ˜:šœœœ*˜JJšœ˜—Jšœ˜—Kšœœ œœ<˜]šž œ œ3œœ˜WJšœœ˜&Jšœ˜Jšœ œœœ"˜;Jš œœœœ0œ˜\Jšœ3œœœ˜Hš œœ œœ˜1Jšœœ˜Jšœ œœ˜.Jšœœœœ˜0š œœ œ"œœ˜gJšœ˜Jšœœœœ˜,Jšœœœœ˜"šœœœœœ œœœ˜wJšœ ˜ Jšœ ˜ Jšœ˜—Jšœ ˜ Jšœ˜—Jšœ˜—Jšœ˜—šž œ œ3œ˜Sšœœœ˜)Jšœ˜Jšœ˜Jšœœ˜ Jšœœ&œœ˜TJšœ ˜ Jš˜—Jšœ˜—Kšžœ œ3œ˜SKšœ œœ˜#šœœœ˜Jšœ œœ˜"J˜—Kšœœ˜š žœœœœœ˜AJš œ œœœœ˜XJšœœ˜ Jšœ˜—šž œœœ˜,šœ œœ#˜