DIRECTORY CodeTimer, Cubic2, CubicPathsExtras, GGAlign, GGBasicTypes, GGCaret, GGCircles, GGCoreTypes, GGInterfaceTypes, GGModelTypes, GGMultiGravity, GGParent, GGScene, GGSegmentTypes, GGSliceOps, GGState, GGUtility, Lines2d, Real, RealFns, Rope, Vectors2d; GGMultiGravityImpl: CEDAR PROGRAM IMPORTS CodeTimer, CubicPathsExtras, GGAlign, GGCaret, GGCircles, GGParent, GGScene, GGSliceOps, GGState, Lines2d, RealFns, Vectors2d EXPORTS GGMultiGravity = BEGIN AlignBag: TYPE = REF AlignBagObj; AlignBagObj: TYPE = GGInterfaceTypes.AlignBagObj; AlignmentCircle: TYPE = GGInterfaceTypes.AlignmentCircle; AlignmentLine: TYPE = GGInterfaceTypes.AlignmentLine; AlignmentPoint: TYPE = REF AlignmentPointObj; AlignmentPointObj: TYPE = GGInterfaceTypes.AlignmentPointObj; Arc: TYPE = GGBasicTypes.Arc; Bezier: TYPE = Cubic2.Bezier; BezierRef: TYPE = REF Bezier; Caret: TYPE = GGInterfaceTypes.Caret; Circle: TYPE = GGBasicTypes.Circle; Edge: TYPE = GGBasicTypes.Edge; FeatureCycler: TYPE = REF FeatureCyclerObj; FeatureCyclerObj: TYPE = GGInterfaceTypes.FeatureCyclerObj; FeatureData: TYPE = REF FeatureDataObj; FeatureDataObj: TYPE = GGModelTypes.FeatureDataObj; GGData: TYPE = GGInterfaceTypes.GGData; GoodPoint: TYPE = REF GoodPointObj; GoodPointObj: TYPE = GGInterfaceTypes.GoodPointObj; GravityType: TYPE = GGInterfaceTypes.GravityType; JointGenerator: TYPE = GGModelTypes.JointGenerator; Line: TYPE = GGCoreTypes.Line; NearVertexEdgeAndFaces: TYPE = REF NearVertexEdgeAndFacesObj; NearVertexEdgeAndFacesObj: TYPE = GGInterfaceTypes.NearVertexEdgeAndFacesObj; Point: TYPE = GGBasicTypes.Point; PointPairAndDone: TYPE = GGModelTypes.PointPairAndDone; PointPairGenerator: TYPE = GGModelTypes.PointPairGenerator; Scene: TYPE = GGModelTypes.Scene; Segment: TYPE = GGSegmentTypes.Segment; SegmentGenerator: TYPE = GGModelTypes.SegmentGenerator; Sequence: TYPE = GGModelTypes.Sequence; Slice: TYPE = GGModelTypes.Slice; SliceDescriptor: TYPE = GGModelTypes.SliceDescriptor; SliceDescriptorObj: TYPE = GGModelTypes.SliceDescriptorObj; TriggerBag: TYPE = REF TriggerBagObj; TriggerBagObj: TYPE = GGInterfaceTypes.TriggerBagObj; Vector: TYPE = GGBasicTypes.Vector; BestPoints: TYPE = REF BestPointsObj; BestPointsObj: TYPE = RECORD [ size: NAT, max, min: REAL, maxIndex: NAT, bestTossed: REAL, -- the distance of the closest object that has been thrown away dTol: REAL, -- min + s innerR: REAL, -- find all curves within this radius even if they are not neighbors of the nearest s: REAL, -- the size of neighborhoods. BestPoints should contain all objects that have been seen such that min <= dist(o, q) <= min+s, unless BestPoints overflows. overflow: BOOL, points: SEQUENCE len: NAT OF GoodPoint]; BestFaces: TYPE = REF BestFacesObj; BestFacesObj: TYPE = RECORD [ size: NAT, maxPriority, minPriority: INT, minIndex: NAT, bestPriorityTossed: INT, priorityTol: INT, -- the farthest overlap level that we are interested in overflow: BOOL, faces: SEQUENCE len: NAT OF GoodPoint]; MultiGravityPool: TYPE = REF MultiGravityPoolObj; MultiGravityPoolObj: TYPE = RECORD [ bestpoints: BestPoints, bestcurves: BestPoints, bestfaces: BestFaces ]; Problem: PUBLIC SIGNAL [msg: Rope.ROPE] = CODE; Map: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData, intersections: BOOL _ FALSE] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { ENABLE UNWIND => { ggData.multiGravityPool _ NewMultiGravityPool[]; }; gravityType: GravityType _ GGState.GetGravityType[ggData]; CodeTimer.StartInt[$MultiMap, $Gargoyle]; IF GGState.GetGravity[ggData] THEN { SELECT gravityType FROM pointsPreferred => [resultPoint, normal, feature, hitData] _ PointsPreferred[testPoint, t, alignBag, sceneBag, ggData, intersections]; linesPreferred, facesPreferred => [resultPoint, normal, feature, hitData] _ LinesPreferred[testPoint, t, alignBag, sceneBag, ggData]; ENDCASE => ERROR; } ELSE { resultPoint _ testPoint; feature _ NIL; normal _ [0,-1]; }; CodeTimer.StopInt[$MultiMap, $Gargoyle]; }; PointsPreferred: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData, intersections: BOOL _ FALSE] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { count: NAT; nearVEF: NearVertexEdgeAndFaces; [nearVEF, count] _ MultiPointsPreferred[testPoint, t, alignBag, sceneBag, ggData, intersections]; IF count = 0 THEN RETURN [testPoint, [0,-1], NIL, NIL]; IF count = 1 THEN RETURN PrepareWinner[nearVEF, 0] ELSE { neighborCount: NAT _ 1; s: REAL = 0.072; -- 1/1000 inches nearestDist: REAL _ -1; nearestDist _ nearVEF[0].dist; FOR i: NAT IN [1..count) DO IF nearVEF[i].dist - nearestDist < s THEN neighborCount _ neighborCount + 1; ENDLOOP; IF neighborCount = 1 THEN RETURN PrepareWinner[nearVEF, 0]; FOR i: NAT IN [0..neighborCount) DO IF nearVEF[i].featureData.type = slice THEN { RETURN PrepareWinner[nearVEF, i]; }; REPEAT FINISHED => RETURN PrepareWinner[nearVEF, 0]; ENDLOOP; }; }; LinesPreferred: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { nearVEF: NearVertexEdgeAndFaces; count: NAT; [nearVEF, count] _ MultiLinesPreferred[testPoint, t, alignBag, sceneBag, ggData]; IF count = 0 THEN RETURN [testPoint, [0,-1], NIL, NIL]; IF count = 1 THEN RETURN PrepareWinner[nearVEF, 0] ELSE { <> RETURN PrepareWinner[nearVEF, 0]; }; }; FacesPreferred: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { nearVEF: NearVertexEdgeAndFaces; count: NAT; [nearVEF, count] _ MultiFacesPreferred[testPoint, t, alignBag, sceneBag, ggData]; IF count = 0 THEN RETURN [testPoint, [0,-1], NIL, NIL]; RETURN PrepareWinner[nearVEF, 0] }; PrepareWinner: PROC [nearVEF: NearVertexEdgeAndFaces, index: NAT] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { goodPoint: GoodPoint _ nearVEF[index]; resultPoint _ goodPoint.point; normal _ goodPoint.normal; feature _ goodPoint.featureData; hitData _ goodPoint.hitData; }; EmptyCycler: PUBLIC PROC [testPoint: Point] RETURNS [featureCycler: FeatureCycler] = { featureCycler _ NEW[FeatureCyclerObj _ [ nearVEF: NIL, count: 0, index: -1, testPoint: testPoint ]]; }; MapCycler: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData, intersections: BOOL _ FALSE] RETURNS [featureCycler: FeatureCycler] = { ENABLE UNWIND => { ggData.multiGravityPool _ NewMultiGravityPool[]; }; gravityType: GravityType _ GGState.GetGravityType[ggData]; IF GGState.GetGravity[ggData] THEN { SELECT gravityType FROM pointsPreferred => featureCycler _ PointsPreferredCycler[testPoint, t, alignBag, sceneBag, ggData, intersections]; linesPreferred, facesPreferred => featureCycler _ LinesPreferredCycler[testPoint, t, alignBag, sceneBag, ggData]; ENDCASE => ERROR; } ELSE { featureCycler _ EmptyCycler[testPoint]; }; }; CopyVEF: PROC [vef: NearVertexEdgeAndFaces, count: NAT] RETURNS [copy: NearVertexEdgeAndFaces] = { oldGoodPoint, newGoodPoint: GoodPoint; copy _ NEW[NearVertexEdgeAndFacesObj[count]]; FOR i: NAT IN [0..count) DO oldGoodPoint _ vef[i]; newGoodPoint _ NEW[GoodPointObj _ [ dist: oldGoodPoint.dist, point: oldGoodPoint.point, normal: oldGoodPoint.normal, featureData: oldGoodPoint.featureData, hitData: oldGoodPoint.hitData, dimension: oldGoodPoint.dimension]]; copy[i] _ newGoodPoint; ENDLOOP; }; PointsPreferredCycler: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData, intersections: BOOL _ FALSE, maxDimension: [0..1] _ 1] RETURNS [featureCycler: FeatureCycler] = { count: NAT; nearVEF: NearVertexEdgeAndFaces; BEGIN [nearVEF, count] _ MultiPointsPreferred[testPoint, t, alignBag, sceneBag, ggData, intersections]; IF count = 0 THEN RETURN[EmptyCycler[testPoint]]; IF count = 1 THEN GOTO MakeSimpleCycler ELSE { neighborCount: NAT _ 1; s: REAL = 0.072; -- 1/1000 inches nearestDist: REAL _ -1; featureCycler _ NEW[FeatureCyclerObj _ [ nearVEF: NIL, -- will be filled in below count: count, index: -1, -- will be filled in below testPoint: testPoint ]]; nearestDist _ nearVEF[0].dist; FOR i: NAT IN [1..count) DO IF nearVEF[i].dist - nearestDist < s THEN neighborCount _ neighborCount + 1; ENDLOOP; IF neighborCount = 1 THEN GOTO MakeSimpleCycler; featureCycler.nearVEF _ CopyVEF[nearVEF, count]; FOR i: NAT IN [0..neighborCount) DO IF nearVEF[i].featureData.type = slice THEN { featureCycler.index _ i; RETURN; }; REPEAT FINISHED => featureCycler.index _ 0; ENDLOOP; }; EXITS MakeSimpleCycler => { featureCycler _ NEW[FeatureCyclerObj _ [ nearVEF: CopyVEF[nearVEF, count], count: count, index: 0, testPoint: testPoint ]]; }; END; }; LinesPreferredCycler: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData] RETURNS [featureCycler: FeatureCycler] = { nearVEF: NearVertexEdgeAndFaces; count: NAT; BEGIN [nearVEF, count] _ MultiLinesPreferred[testPoint, t, alignBag, sceneBag, ggData]; IF count = 0 THEN RETURN[EmptyCycler[testPoint]]; IF count = 1 THEN GOTO MakeSimpleCycler ELSE { nearestDist: REAL _ -1; bestSceneObject: INT _ -1; neighborCount: NAT _ 1; s: REAL = 0.072; -- 1/1000 inches nearestDist _ nearVEF[0].dist; FOR i: NAT IN [1..count) DO IF nearVEF[i].dist - nearestDist < s THEN neighborCount _ neighborCount + 1; ENDLOOP; IF neighborCount = 1 THEN GOTO MakeSimpleCycler; bestSceneObject _ -1; featureCycler _ NEW[FeatureCyclerObj _ [ nearVEF: CopyVEF[nearVEF, count], count: count, index: 0, testPoint: testPoint ]]; }; EXITS MakeSimpleCycler => { featureCycler _ NEW[FeatureCyclerObj _ [ nearVEF: CopyVEF[nearVEF, count], count: count, index: 0, testPoint: testPoint ]]; }; END; }; FacesPreferredCycler: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData] RETURNS [featureCycler: FeatureCycler] = { nearVEF: NearVertexEdgeAndFaces; count: NAT; BEGIN [nearVEF, count] _ MultiFacesPreferred[testPoint, t, alignBag, sceneBag, ggData]; IF count = 0 THEN RETURN[EmptyCycler[testPoint]]; IF count = 1 THEN GOTO MakeSimpleCycler ELSE { GOTO MakeSimpleCycler; <> }; EXITS MakeSimpleCycler => { featureCycler _ NEW[FeatureCyclerObj _ [ nearVEF: CopyVEF[nearVEF, count], count: count, index: 0, testPoint: testPoint ]]; }; END; }; FirstFeature: PUBLIC PROC [featureCycler: FeatureCycler] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { RETURN GetFeature[featureCycler, 0]; }; NextFeature: PUBLIC PROC [featureCycler: FeatureCycler] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { RETURN GetFeature[featureCycler, 1]; }; PreviousFeature: PUBLIC PROC [featureCycler: FeatureCycler] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { RETURN GetFeature[featureCycler, -1]; }; GetFeature: PUBLIC PROC [featureCycler: FeatureCycler, move: [-1..1]] RETURNS [resultPoint: Point, normal: Vector, feature: FeatureData, hitData: REF ANY] = { IF featureCycler = NIL THEN { -- return a backdrop position resultPoint _ [0.0, 0.0]; -- bogus normal _ [0,-1]; feature _ NIL; hitData _ NIL; } ELSE IF featureCycler.count = 0 THEN { -- return a backdrop position resultPoint _ featureCycler.testPoint; normal _ [0,-1]; feature _ NIL; hitData _ NIL; } ELSE { featureCycler.index _ (featureCycler.index + move + featureCycler.count) MOD featureCycler.count; [resultPoint, normal, feature, hitData] _ PrepareWinner[featureCycler.nearVEF, featureCycler.index]; }; }; MultiMap: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData, intersections: BOOL _ FALSE] RETURNS [nearVEF: NearVertexEdgeAndFaces, count: NAT] = { ENABLE UNWIND => ggData.multiGravityPool _ NewMultiGravityPool[]; -- in case an ABORT happened while pool was in use CodeTimer.StartInt[$MultiMap, $Gargoyle]; IF GGState.GetGravity[ggData] THEN { SELECT GGState.GetGravityType[ggData] FROM linesPreferred => [nearVEF, count] _ MultiLinesPreferred[testPoint, t, alignBag, sceneBag, ggData]; pointsPreferred => [nearVEF, count] _ MultiPointsPreferred[testPoint, t, alignBag, sceneBag, ggData, intersections]; ENDCASE => ERROR; } ELSE { nearVEF _ NIL; count _ 0; }; CodeTimer.StopInt[$MultiMap, $Gargoyle]; }; MultiFacesPreferred: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData] RETURNS [nearVEF: NearVertexEdgeAndFaces, count: NAT] = { bestCurves, bestPoints: BestPoints; bestFaces: BestFaces; faceCount, curveCount, pointCount: NAT; IF GGAlign.EmptyAlignBag[alignBag] AND GGAlign.EmptyTriggerBag[sceneBag] THEN RETURN[NIL, 0]; [bestFaces, faceCount] _ FacesInNeighborhoodPlus[alignBag, sceneBag, testPoint, ggData, t]; SortByOverlap[bestFaces, faceCount]; [bestCurves, curveCount] _ CurvesInNeighborhoodPlus[alignBag, sceneBag, testPoint, ggData, t, 0]; [bestPoints, pointCount] _ VertsInNeighborhoodPlus[bestCurves, curveCount, alignBag, sceneBag, testPoint, t, ggData, FALSE]; SortPoints[bestPoints, pointCount]; count _ MIN[pointCount + curveCount, MaxFeatures]; nearVEF _ NEW[NearVertexEdgeAndFacesObj[count]]; MergePointsAndCurves[bestPoints, pointCount, bestCurves, curveCount, nearVEF, count]; [nearVEF, count] _ MergeByOverlapAndDistance[bestFaces, faceCount, nearVEF, count]; }; MultiLinesPreferred: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData] RETURNS [nearVEF: NearVertexEdgeAndFaces, count: NAT] = { bestCurves: BestPoints; bestPoints: BestPoints; pointCount, curveCount: NAT; IF GGAlign.EmptyAlignBag[alignBag] AND GGAlign.EmptyTriggerBag[sceneBag] THEN RETURN[NIL, 0]; [bestCurves, curveCount] _ CurvesInNeighborhoodPlus[alignBag, sceneBag, testPoint, ggData, t, 0]; [bestPoints, pointCount] _ VertsInNeighborhoodPlus[bestCurves, curveCount, alignBag, sceneBag, testPoint, t, ggData, FALSE]; SortPoints[bestPoints, pointCount]; count _ MIN[pointCount + curveCount, MaxFeatures]; nearVEF _ NEW[NearVertexEdgeAndFacesObj[count]]; MergePointsAndCurves[bestPoints, pointCount, bestCurves, curveCount, nearVEF, count]; }; MultiPointsPreferred: PUBLIC PROC [testPoint: Point, t: REAL, alignBag: AlignBag, sceneBag: TriggerBag, ggData: GGData, intersections: BOOL _ FALSE] RETURNS [nearVEF: NearVertexEdgeAndFaces, count: NAT] = { bestCurves: BestPoints; bestPoints: BestPoints; pointCount, curveCount: NAT; innerR: REAL _ t/2.0; IF GGAlign.EmptyAlignBag[alignBag] AND GGAlign.EmptyTriggerBag[sceneBag] THEN RETURN[NIL, 0]; [bestCurves, curveCount] _ CurvesInNeighborhoodPlus[alignBag, sceneBag, testPoint, ggData, t, innerR]; [bestPoints, pointCount] _ VertsInNeighborhoodPlus[bestCurves, curveCount, alignBag, sceneBag, testPoint, t, ggData, intersections]; SortPoints[bestPoints, pointCount]; IF pointCount > 0 AND bestPoints[0].dist < innerR THEN { count _ pointCount; nearVEF _ NEW[NearVertexEdgeAndFacesObj[count]]; NearPointsFromPoints[bestPoints, pointCount, nearVEF]; } ELSE { count _ MIN[pointCount + curveCount, MaxFeatures]; nearVEF _ NEW[NearVertexEdgeAndFacesObj[count]]; MergePointsAndCurves[bestPoints, pointCount, bestCurves, curveCount, nearVEF, count]; }; }; VertsInNeighborhoodPlus: PROC [bestCurves: BestPoints, curveCount: NAT, alignBag: AlignBag, sceneBag: TriggerBag, q: Point, t: REAL, ggData: GGData, intersections: BOOL _ FALSE] RETURNS [h: BestPoints, pointCount: NAT] = { thisPoint: GoodPoint; ProcessPoint: PROC [thisPoint: GoodPoint, featureData: FeatureData] = { -- used for the anchor dSquared: REAL; dTolSquared: REAL _ dTol*dTol; dSquared _ Vectors2d.DistanceSquared[thisPoint.point, q]; thisPoint.hitData _ NIL; IF dSquared < dTolSquared THEN { thisPoint.dist _ RealFns.SqRt[dSquared]; thisPoint.normal _ GGCaret.GetNormal[NARROW[featureData.shape]]; -- the anchor IF Vectors2d.MagnitudeSquared[thisPoint.normal] = 0 THEN thisPoint.normal _ [0, -1]; thisPoint.featureData _ featureData; thisPoint.priority _ -1; dTol _ AddNeighbor[thisPoint, h, FALSE]; }; }; ProcessSlice: PROC [sliceD: SliceDescriptor, thisPoint: GoodPoint, featureData: FeatureData] = { [thisPoint.point, thisPoint.dist, thisPoint.normal, thisPoint.hitData, success] _ sliceD.slice.class.closestPoint[sliceD, q, dTol]; IF success THEN { IF thisPoint.dist < dTol THEN { thisPoint.featureData _ featureData; IF Vectors2d.MagnitudeSquared[thisPoint.normal] = 0 THEN { thisPoint.normal _ [0, -1]; }; thisPoint.priority _ GGScene.GetPriority[ggData.scene, sliceD.slice]; dTol _ AddNeighbor[thisPoint, h, FALSE]; }; }; }; DoForSliceTrigger: GGAlign.FeatureWalkProc = { sliceD _ NARROW[feature.shape, SliceDescriptor]; ProcessSlice[sliceD, thisPoint, feature]; }; sliceD: SliceDescriptor; featureData: FeatureData; success: BOOL _ FALSE; dTol: REAL _ t; midpoints: BOOL _ GGState.GetMidpoints[ggData]; thisPoint _ NEW[GoodPointObj]; h _ BestPointsFromPool[ggData, t]; IF intersections THEN { dTol _ FindIntersections[bestCurves, curveCount, thisPoint, q, dTol, h, ggData.scene]; IF midpoints THEN dTol _ FindMidpoints[bestCurves, curveCount, thisPoint, q, dTol, h, ggData.scene]; }; GGAlign.WalkSliceTriggers[sceneBag, DoForSliceTrigger]; featureData _ alignBag.anchor; IF featureData # NIL THEN { anchor: Caret _ NARROW[featureData.shape]; IF NOT GGCaret.Exists[anchor] THEN ERROR; thisPoint.point _ GGCaret.GetPoint[anchor]; ProcessPoint[thisPoint, featureData]; }; pointCount _ h.size; IF h.overflow THEN { CodeTimer.StartInt[$PointOverflow, $Gargoyle]; CodeTimer.StopInt[$PointOverflow, $Gargoyle]; }; }; -- end of VertsInNeighborhoodPlus FindIntersections: PROC [bestCurves: BestPoints, curveCount: NAT, thisPoint: GoodPoint, q: Point, tolerance: REAL, h: BestPoints, scene: Scene] RETURNS [dTol: REAL] = { curveI, curveJ: GoodPoint; theseIPoints: LIST OF Point; thisTangency, tangentList: LIST OF BOOL; success: BOOL _ FALSE; dTol _ tolerance; FOR i: NAT IN [0..curveCount) DO curveI _ bestCurves[i]; IF curveI.dist > dTol THEN EXIT; -- this curve is too far away (and the rest are farther) FOR j: NAT IN [0..i] DO curveJ _ bestCurves[j]; IF curveJ.dist > dTol THEN LOOP; -- this curve is too far away to be worth considering [theseIPoints, thisTangency] _ CurveMeetsCurve[curveI, curveJ]; tangentList _ thisTangency; FOR list: LIST OF Point _ theseIPoints, list.rest UNTIL list = NIL DO thisPoint.point _ list.first; thisPoint.dist _ Vectors2d.Distance[thisPoint.point, q]; success _ thisPoint.dist <= dTol; IF success THEN { featureData: FeatureData _ NEW[FeatureDataObj]; alignmentPoint: AlignmentPoint _ NEW[AlignmentPointObj _ [ point: thisPoint.point, tangent: tangentList.first, curve1: curveI.featureData, curve2: curveJ.featureData]]; featureData.type _ intersectionPoint; featureData.shape _ alignmentPoint; thisPoint.featureData _ featureData; thisPoint.priority _ -1; IF curveI.featureData.type = slice THEN { sliceD: SliceDescriptor _ NARROW[curveI.featureData.shape]; slice: Slice _ sliceD.slice; thisPoint.priority _ GGScene.GetPriority[scene, slice]; thisPoint.hitData _ curveI.hitData; thisPoint.normal _ GGSliceOps.ClosestSegment[sliceD, q, dTol].bestNormal; -- find normal at nearest vertex. Works for straight edges } ELSE IF curveJ.featureData.type = slice THEN { sliceD: SliceDescriptor _ NARROW[curveJ.featureData.shape]; slice: Slice _ sliceD.slice; thisPoint.priority _ MIN[thisPoint.priority, GGScene.GetPriority[scene, slice]]; thisPoint.hitData _ curveJ.hitData; thisPoint.normal _ GGSliceOps.ClosestSegment[sliceD, q, dTol].bestNormal; -- find normal at nearest vertex. Works for straight edges } ELSE thisPoint.hitData _ NIL; IF Vectors2d.MagnitudeSquared[thisPoint.normal] = 0 THEN thisPoint.normal _ [0, -1]; dTol _ AddNeighbor[thisPoint, h, FALSE]; }; tangentList _ tangentList.rest; ENDLOOP; ENDLOOP; ENDLOOP; }; FindMidpoints: PROC [bestCurves: BestPoints, curveCount: NAT, thisPoint: GoodPoint, q: Point, tolerance: REAL, h: BestPoints, scene: Scene] RETURNS [dTol: REAL] = { curve: GoodPoint; midpoint: Point; success: BOOL _ FALSE; dTol _ tolerance; FOR i: NAT IN [0..curveCount) DO curve _ bestCurves[i]; IF curve.featureData.type#slice THEN LOOP; [midpoint, success] _ ComputeMidpoint[curve]; IF NOT success THEN LOOP; thisPoint.point _ midpoint; thisPoint.dist _ Vectors2d.Distance[thisPoint.point, q]; success _ thisPoint.dist <= dTol; IF success THEN { sliceD: SliceDescriptor _ NARROW[curve.featureData.shape]; slice: Slice _ sliceD.slice; featureData: FeatureData _ NEW[FeatureDataObj]; alignmentPoint: AlignmentPoint _ NEW[AlignmentPointObj _ [ point: thisPoint.point, tangent: FALSE, curve1: curve.featureData, curve2: NIL]]; featureData.type _ midpoint; featureData.shape _ alignmentPoint; thisPoint.featureData _ featureData; thisPoint.hitData _ curve.hitData; thisPoint.normal _ GGSliceOps.ClosestSegment[sliceD, q, dTol].bestNormal; -- find normal at nearest vertex. Works for edges IF Vectors2d.MagnitudeSquared[thisPoint.normal] = 0 THEN thisPoint.normal _ [0, -1]; thisPoint.priority _ GGScene.GetPriority[scene, slice]; dTol _ AddNeighbor[thisPoint, h, FALSE]; }; ENDLOOP; }; CurvesInNeighborhoodPlus: PROC [alignBag: AlignBag, sceneBag: TriggerBag, q: Point, ggData: GGData, t: REAL, innerR: REAL] RETURNS [h: BestPoints, curveCount: NAT] = { ProcessLine: PROC [line: Line, thisCurve: GoodPoint, featureData: FeatureData] = { thisCurve.dist _ Lines2d.LineDistance[q, line]; IF thisCurve.dist < dTol THEN { thisCurve.featureData _ featureData; thisCurve.point _ Lines2d.DropPerpendicular[q, line]; thisCurve.normal _ Vectors2d.Sub[q, thisCurve.point]; IF Vectors2d.MagnitudeSquared[thisCurve.normal] = 0 THEN { thisCurve.normal _ [0, -1];}; thisCurve.hitData _ NIL; thisCurve.priority _ -1; dTol _ AddNeighbor[thisCurve, h, TRUE]; } }; ProcessCircle: PROC [circle: Circle, thisCurve: GoodPoint, featureData: FeatureData] = { QProjectedOntoCircle: PUBLIC PROC [] RETURNS [projectedPt: Point] = { epsilon: REAL = 1.0e-5; IF distQtoCenter < epsilon THEN projectedPt _ [circle.origin.x + circle.radius, circle.origin.y] ELSE projectedPt _ Vectors2d.Add[circle.origin, Vectors2d.Scale[centerToQ, circle.radius/distQtoCenter]]; }; centerToQ: Vector _ Vectors2d.Sub[q, circle.origin]; distQtoCenter: REAL _ Vectors2d.Magnitude[centerToQ]; thisCurve.dist _ ABS[distQtoCenter-circle.radius]; IF thisCurve.dist < dTol THEN { thisCurve.featureData _ featureData; thisCurve.point _ QProjectedOntoCircle[]; IF thisCurve.dist = 0.0 THEN thisCurve.normal _ centerToQ ELSE thisCurve.normal _ Vectors2d.Sub[q, thisCurve.point]; thisCurve.hitData _ NIL; thisCurve.priority _ -1; dTol _ AddNeighbor[thisCurve, h, TRUE]; }; }; ProcessSlice: PROC [sliceD: SliceDescriptor, thisCurve: GoodPoint, featureData: FeatureData] = { success: BOOL _ FALSE; [thisCurve.point, thisCurve.dist, thisCurve.normal, thisCurve.hitData, success] _ sliceD.slice.class.closestSegment[sliceD, q, dTol]; IF success THEN { IF thisCurve.dist < dTol THEN { thisCurve.featureData _ featureData; IF Vectors2d.MagnitudeSquared[thisCurve.normal] = 0 THEN { thisCurve.normal _ [0, -1]; }; thisCurve.priority _ GGScene.GetPriority[ggData.scene, sliceD.slice]; dTol _ AddNeighbor[thisCurve, h, TRUE]; }; }; }; ProcessSlopeLine: GGAlign.FeatureWalkProc = { line _ NARROW[feature.shape, AlignmentLine].line; ProcessLine[line, thisCurve, feature]; }; DoForSceneSlice: GGAlign.FeatureWalkProc = { sliceD _ NARROW[feature.shape, SliceDescriptor]; ProcessSlice[sliceD, thisCurve, feature]; }; line: Line; circle: Circle; sliceD: SliceDescriptor; featureData: FeatureData; added: BOOL _ FALSE; thisCurve: GoodPoint _ NEW[GoodPointObj]; dTol: REAL _ t; h _ BestCurvesFromPool[ggData, t, innerR]; GGAlign.WalkSlopeLines[alignBag, ProcessSlopeLine]; FOR angleLines: LIST OF FeatureData _ alignBag.angleLines, angleLines.rest UNTIL angleLines = NIL DO featureData _ angleLines.first; line _ NARROW[featureData.shape, AlignmentLine].line; ProcessLine[line, thisCurve, featureData]; ENDLOOP; FOR dLines: LIST OF FeatureData _ alignBag.distanceLines, dLines.rest UNTIL dLines = NIL DO featureData _ dLines.first; line _ NARROW[featureData.shape]; ProcessLine[line, thisCurve, featureData]; ENDLOOP; FOR circles: LIST OF FeatureData _ alignBag.radiiCircles, circles.rest UNTIL circles = NIL DO featureData _ circles.first; circle _ NARROW[featureData.shape, AlignmentCircle].circle; ProcessCircle[circle, thisCurve, featureData]; ENDLOOP; GGAlign.WalkSliceTriggers[sceneBag, DoForSceneSlice]; curveCount _ h.size; IF h.overflow THEN { CodeTimer.StartInt[$CurveOverflow, $Gargoyle]; CodeTimer.StopInt[$CurveOverflow, $Gargoyle]; }; SortCurves[h, curveCount]; }; -- end CurvesInNeighborhoodPlus FacesInNeighborhoodPlus: PROC [alignBag: AlignBag, sceneBag: TriggerBag, q: Point, ggData: GGData, t: REAL] RETURNS [h: BestFaces, faceCount: NAT] = { sliceD: SliceDescriptor; added: BOOL _ FALSE; thisFace: GoodPoint _ NEW[GoodPointObj]; priorityTol: INT _ -1; ProcessSlice: PROC [sliceD: SliceDescriptor, thisFace: GoodPoint, featureData: FeatureData] = { hitData: REF ANY; moreHitDatas: LIST OF REF ANY; success: BOOL _ TRUE; IF GGScene.GetPriority[ggData.scene, sliceD.slice] >= priorityTol THEN { [hitData, moreHitDatas] _ GGSliceOps.FilledPathsUnderPoint[sliceD.slice, q, t]; IF hitData # NIL THEN { thisFace.point _ q; thisFace.priority _ GGScene.GetPriority[ggData.scene, sliceD.slice]; thisFace.normal _ [0, -1]; thisFace.hitData _ hitData; thisFace.featureData _ featureData; priorityTol _ AddFace[thisFace, h]; }; FOR list: LIST OF REF ANY _ moreHitDatas, list.rest UNTIL list = NIL DO thisFace.point _ q; thisFace.priority _ GGScene.GetPriority[ggData.scene, sliceD.slice]; thisFace.normal _ [0, -1]; thisFace.hitData _ list.first; thisFace.featureData _ featureData; priorityTol _ AddFace[thisFace, h]; ENDLOOP; }; }; DoForSceneSlice: GGAlign.FeatureWalkProc = { sliceD _ NARROW[feature.shape, SliceDescriptor]; ProcessSlice[sliceD, thisFace, feature]; }; h _ BestFacesFromPool[ggData]; GGAlign.WalkSliceTriggers[sceneBag, DoForSceneSlice]; faceCount _ h.size; IF h.overflow THEN { CodeTimer.StartInt[$FaceOverflow, $Gargoyle]; CodeTimer.StopInt[$FaceOverflow, $Gargoyle]; }; SortFaces[h, faceCount]; }; MaxFeatures: NAT _ 20; BestFacesFromPool: PROC [ggData: GGData] RETURNS [h: BestFaces] = { h _ NARROW[ggData.multiGravityPool, MultiGravityPool].bestfaces; h.size _ 0; h.maxPriority _ -1; h.minIndex _ 9999; h.minPriority _ LAST[INT]; h.bestPriorityTossed _ -1; h.overflow _ FALSE; FOR i: NAT IN [0..MaxFeatures) DO h[i].dist _ Real.LargestNumber; h[i].featureData _ NIL; ENDLOOP; }; BestCurvesFromPool: PROC [ggData: GGData, t: REAL, innerR: REAL] RETURNS [h: BestPoints] = { h _ NARROW[ggData.multiGravityPool, MultiGravityPool].bestcurves; h.size _ 0; h.max _ 0.0; h.maxIndex _ 9999; h.min _ Real.LargestNumber; h.dTol _ t; h.innerR _ innerR; h.s _ 0.072; -- 1/1000 inches h.bestTossed _ Real.LargestNumber; h.overflow _ FALSE; FOR i: NAT IN [0..MaxFeatures) DO h[i].dist _ Real.LargestNumber; h[i].featureData _ NIL; ENDLOOP; }; BestPointsFromPool: PROC [ggData: GGData, t: REAL] RETURNS [h: BestPoints] = { h _ NARROW[ggData.multiGravityPool, MultiGravityPool].bestpoints; h.size _ 0; h.max _ 0.0; h.maxIndex _ 9999; h.min _ Real.LargestNumber; h.dTol _ t; h.s _ 0.072; -- 1/1000 inches h.bestTossed _ Real.LargestNumber; h.overflow _ FALSE; FOR i: NAT IN [0..MaxFeatures) DO h[i].dist _ Real.LargestNumber; h[i].featureData _ NIL; ENDLOOP; }; AddNeighbor: PROC [thisPoint: GoodPoint, h: BestPoints, curve: BOOL _ FALSE] RETURNS [dTol: REAL] = { d: REAL _ thisPoint.dist; n: NAT = MaxFeatures; BEGIN SELECT TRUE FROM d > h.dTol => GOTO Toss; -- the caller is not taking our hints and is passing us trash h.size < n => GOTO Add; h.size = n => GOTO ReplaceOrOverflow; ENDCASE => SIGNAL Problem[msg: "Impossible case."]; EXITS Add => { h[h.size]^ _ thisPoint^; IF d > h.max THEN {h.max _ d; h.maxIndex _ h.size}; h.min _ MIN[h.min, d]; h.size _ h.size + 1; IF curve THEN dTol _ h.dTol _ MAX[h.min+h.s, h.innerR] ELSE dTol _ h.dTol _ h.min+h.s; }; ReplaceOrOverflow => { IF d < h.max THEN { -- do the replace h[h.maxIndex]^ _ thisPoint^; h.bestTossed _ MIN[h.bestTossed, h.max]; h.min _ MIN[h.min, d]; IF curve THEN dTol _ h.dTol _ MAX[h.min+h.s, h.innerR] ELSE dTol _ h.dTol _ h.min+h.s; h.overflow _ h.bestTossed <= dTol; BEGIN maxIndex: NAT _ 0; maxDist: REAL _ 0.0; FOR i: NAT IN [0..MaxFeatures) DO IF h[i].dist > maxDist THEN {maxIndex _ i; maxDist _ h[i].dist}; ENDLOOP; h.max _ maxDist; h.maxIndex _ maxIndex; END; } ELSE { -- toss the new item dTol _ h.dTol; h.bestTossed _ MIN[h.bestTossed, d]; h.overflow _ TRUE; }; }; Toss => { dTol _ h.dTol; h.bestTossed _ MIN[h.bestTossed, d]; h.overflow _ h.bestTossed <= dTol; }; END; }; AddFace: PROC [thisFace: GoodPoint, h: BestFaces] RETURNS [priorityTol: INT] = { d: INT _ thisFace.priority; n: NAT = MaxFeatures; BEGIN SELECT TRUE FROM d < h.priorityTol => GOTO Toss; -- the caller is passing us trash h.size < n => GOTO Add; h.size = n => GOTO ReplaceOrOverflow; ENDCASE => SIGNAL Problem[msg: "Impossible case."]; EXITS Add => { h[h.size]^ _ thisFace^; IF d < h.minPriority THEN {h.minPriority _ d; h.minIndex _ h.size}; h.maxPriority _ MAX[h.maxPriority, d]; h.size _ h.size + 1; priorityTol _ h.priorityTol; }; ReplaceOrOverflow => { IF d > h.minPriority THEN { -- do the replace h[h.minIndex]^ _ thisFace^; h.bestPriorityTossed _ MAX[h.bestPriorityTossed, h.minPriority]; h.maxPriority _ MAX[h.maxPriority, d]; h.overflow _ TRUE; BEGIN minIndex: NAT _ 0; minPriority: INT _ LAST[INT]; FOR i: NAT IN [0..MaxFeatures) DO IF h[i].priority < minPriority THEN {minIndex _ i; minPriority _ h[i].priority}; ENDLOOP; h.minPriority _ minPriority; h.minIndex _ minIndex; END; priorityTol _ h.priorityTol _ h.minPriority; } ELSE { -- toss the new item priorityTol _ h.priorityTol; h.bestPriorityTossed _ MAX[h.bestPriorityTossed, d]; h.overflow _ TRUE; }; }; Toss => { priorityTol _ h.priorityTol; h.bestPriorityTossed _ MAX[h.bestPriorityTossed, d]; h.overflow _ TRUE; }; END; }; NearPointsFromPoints: PROC [bestPoints: BestPoints, pointCount: NAT, nearVEF: NearVertexEdgeAndFaces] = { FOR i: NAT IN [0..pointCount) DO nearVEF[i] _ bestPoints[i]; ENDLOOP; }; MergePointsAndCurves: PROC [bestPoints: BestPoints, pointCount: NAT, bestCurves: BestPoints, curveCount: NAT, nearVEF: NearVertexEdgeAndFaces, count: NAT] = { pointIndex, curveIndex: NAT; pointDist, curveDist: REAL; pointIndex _ 0; curveIndex _ 0; FOR i: INTEGER IN [0..count) DO IF pointIndex >= pointCount THEN GOTO NoMorePoints; IF curveIndex >= curveCount THEN GOTO NoMoreCurves; pointDist _ bestPoints[i].dist; curveDist _ bestCurves[i].dist; IF pointDist <= curveDist THEN { nearVEF[i] _ bestPoints[pointIndex]; pointIndex _ pointIndex + 1; } ELSE { nearVEF[i] _ bestCurves[curveIndex]; curveIndex _ curveIndex + 1; }; REPEAT NoMorePoints => { -- finish up with Curves data FOR k: NAT _ i, k+1 UNTIL k >= count DO nearVEF[k] _ bestCurves[curveIndex]; curveIndex _ curveIndex + 1; ENDLOOP}; NoMoreCurves => { -- finish up with points data FOR k: NAT _ i, k+1 UNTIL k >= count DO nearVEF[k] _ bestPoints[pointIndex]; pointIndex _ pointIndex + 1; ENDLOOP}; ENDLOOP; }; MergeByOverlapAndDistance: PROC [faces: BestFaces, faceCount: NAT, curves: NearVertexEdgeAndFaces, curveCount: NAT] RETURNS [nearVEF: NearVertexEdgeAndFaces, total: NAT] = { facePtr, curvePtr: NAT; total _ MIN[curveCount+faceCount, MaxFeatures]; nearVEF _ NEW[NearVertexEdgeAndFacesObj[total]]; facePtr _ curvePtr _ 0; FOR i: NAT IN[0..total) DO IF curvePtr >= curveCount THEN GOTO CurvePtrWentOver; IF facePtr >= faceCount THEN GOTO FacePtrWentOver; BEGIN SELECT faces[facePtr].priority - curves[curvePtr].priority FROM = 0 => { -- they're part of the same slice slice: Slice _ NARROW[faces[facePtr].featureData.shape, SliceDescriptor].slice; IF GGParent.IsParent[slice] THEN { facePath, curvePath: Slice; faceHitData, curveHitData: REF ANY; [facePath, faceHitData] _ GGParent.PathOfHitData[slice, faces[facePtr].hitData]; [curvePath, curveHitData] _ GGParent.PathOfHitData[slice, curves[curvePtr].hitData]; IF facePath = curvePath THEN GOTO RemoveDuplicate; SELECT GGParent.ComparePriorities[facePath, curvePath] FROM less => GOTO CurveIsCloser; greater => GOTO FaceIsCloser; equal => GOTO RemoveDuplicate; ENDCASE => ERROR; } ELSE GOTO RemoveDuplicate; }; > 0 => GOTO FaceIsCloser; < 0 => GOTO CurveIsCloser; ENDCASE => ERROR; EXITS RemoveDuplicate => { nearVEF[i] _ curves[curvePtr]; curvePtr _ curvePtr + 1; facePtr _ facePtr + 1; total _ total - 1; -- a duplicate has been removed }; FaceIsCloser => { nearVEF[i] _ faces[facePtr]; facePtr _ facePtr + 1; }; CurveIsCloser => { nearVEF[i] _ curves[curvePtr]; curvePtr _ curvePtr + 1; }; END; REPEAT CurvePtrWentOver => { -- finish up with faces FOR k: NAT _ i, k+1 UNTIL k >= total DO nearVEF[k] _ faces[facePtr]; facePtr _ facePtr + 1; ENDLOOP}; FacePtrWentOver => { -- finish up with curves FOR k: NAT _ i, k+1 UNTIL k >= total DO nearVEF[k] _ curves[curvePtr]; curvePtr _ curvePtr + 1; ENDLOOP}; ENDLOOP; }; -- end of MergeByOverlapAndDistance SortPoints: PROC [bestPoints: BestPoints, pointCount: NAT] = { temp: GoodPoint; FOR i: INTEGER IN [0..pointCount-2] DO FOR j: INTEGER IN [1..pointCount-i) DO IF bestPoints[j-1].dist > bestPoints[j].dist THEN { temp _ bestPoints[j]; bestPoints[j] _ bestPoints[j-1]; bestPoints[j-1] _ temp; }; ENDLOOP; ENDLOOP; }; SortCurves: PROC [bestCurves: BestPoints, curveCount: NAT] = { temp: GoodPoint; FOR i: INTEGER IN [0..curveCount-2] DO FOR j: INTEGER IN [1..curveCount-i) DO IF bestCurves[j-1].dist > bestCurves[j].dist THEN { temp _ bestCurves[j]; bestCurves[j] _ bestCurves[j-1]; bestCurves[j-1] _ temp; }; ENDLOOP; ENDLOOP; }; SortFaces: PROC [bestFaces: BestFaces, faceCount: NAT] = { temp: GoodPoint; FOR i: INTEGER IN [0..faceCount-2] DO FOR j: INTEGER IN [1..faceCount-i) DO IF bestFaces[j-1].priority < bestFaces[j].priority THEN { temp _ bestFaces[j]; bestFaces[j] _ bestFaces[j-1]; bestFaces[j-1] _ temp; }; ENDLOOP; ENDLOOP; }; SortByOverlap: PROC [faces: BestFaces, count: NAT] = { temp: GoodPoint; FOR i: INTEGER IN [0..count-2] DO FOR j: INTEGER IN [1..count-i) DO IF faces[j-1].priority < faces[j].priority THEN { temp _ faces[j]; faces[j] _ faces[j-1]; faces[j-1] _ temp; }; ENDLOOP; ENDLOOP; }; ComputeMidpoint: PROC [curve: GoodPoint] RETURNS [midpoint: Point, success: BOOL _ TRUE] = { class: NAT; simpleCurve: REF ANY; [class, simpleCurve] _ ClassifyCurve[curve]; SELECT class FROM 3 => { -- edge edge: Edge _ NARROW[simpleCurve]; midpoint _ Vectors2d.Scale[Vectors2d.Add[edge.start, edge.end], 0.5]; success _ TRUE; }; 4 => { -- arc arc: Arc _ NARROW[simpleCurve]; midpoint _ Vectors2d.Scale[Vectors2d.Add[arc.p0, arc.p2], 0.5]; success _ TRUE; }; ENDCASE => RETURN[[0,0], FALSE]; }; ClassifyCurve: PROC [curve: GoodPoint] RETURNS [class: NAT, simpleCurve: REF ANY] = { feature: FeatureData _ curve.featureData; SELECT feature.type FROM slice => { sliceD: SliceDescriptor _ NARROW[feature.shape]; hitData: REF ANY _ curve.hitData; simpleCurve _ GGSliceOps.HitDataAsSimpleCurve[sliceD.slice, hitData]; IF simpleCurve = NIL THEN { simpleCurve _ sliceD; class _ 6; RETURN; }; }; radiiCircle => { class _ 2; simpleCurve _ NARROW[feature.shape, AlignmentCircle].circle; RETURN; }; slopeLine, angleLine => { class _ 1; simpleCurve _ NARROW[feature.shape, AlignmentLine].line; RETURN; }; distanceLine => { class _ 1; simpleCurve _ NARROW[feature.shape, Line]; RETURN; }; ENDCASE => {class _ 0; simpleCurve _ NIL; RETURN}; WITH simpleCurve SELECT FROM circle: Circle => class _ 2; edge: Edge => class _ 3; arc: Arc => class _ 4; cubic: BezierRef => class _ 5; ENDCASE => ERROR; }; CurveMeetsCurve: PROC [c1, c2: GoodPoint] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL] = { typeOfCurve1, typeOfCurve2: NAT; simpleCurve1, simpleCurve2: REF ANY; [typeOfCurve1, simpleCurve1] _ ClassifyCurve[c1]; [typeOfCurve2, simpleCurve2] _ ClassifyCurve[c2]; IF typeOfCurve1 >= typeOfCurve2 THEN [iPoints, tangency] _ ComputeIntersection[typeOfCurve1][typeOfCurve2][simpleCurve1, simpleCurve2] ELSE [iPoints, tangency] _ ComputeIntersection[typeOfCurve2][typeOfCurve1][simpleCurve2, simpleCurve1] }; IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; ComputeIntersection: ARRAY [0..6] OF ARRAY [0..6] OF IntersectionProc = [ [NoOpI, NIL, NIL, NIL, NIL, NIL, NIL], -- 0) NoOp [NoOpI, LinLinI, NIL, NIL, NIL, NIL, NIL], -- 1) Line [NoOpI, CirLinI, CirCirI, NIL, NIL, NIL, NIL], -- 2) Circle [NoOpI, EdgLinI, EdgCirI, EdgEdgI, NIL, NIL, NIL], -- 3) Edge [NoOpI, ArcLinI, ArcCirI, ArcEdgI, ArcArcI, NIL, NIL], -- 4) Arc [NoOpI, CubLinI, NoOpI, CubEdgI, NoOpI, NoOpI, NIL], -- 5) Cubic [NoOpI, SlcLinI, SlcCirI, NoOpI, NoOpI, NoOpI, NoOpI] -- 6) Slice ]; NoOpI: IntersectionProc = { iPoints _ NIL; tangency _ NIL; }; LinLinI: IntersectionProc = { l1: Line _ NARROW[c1]; l2: Line _ NARROW[c2]; point: Point; parallel: BOOL _ FALSE; [point, parallel] _ Lines2d.LineMeetsLine[l1, l2]; IF NOT parallel THEN {iPoints _ LIST[point]; tangency _ LIST[FALSE]} ELSE {iPoints _ NIL; tangency _ NIL}; }; CirLinI: IntersectionProc = { circle: Circle _ NARROW[c1]; line: Line _ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL _ FALSE; [points, hitCount, tangent] _ GGCircles.CircleMeetsLine[circle, line]; FOR i: NAT IN [1..hitCount] DO iPoints _ CONS[points[i], iPoints]; tangency _ CONS[tangent, tangency]; ENDLOOP; }; CirCirI: IntersectionProc = { circle1: Circle _ NARROW[c1]; circle2: Circle _ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL _ FALSE; [points, hitCount, tangent] _ GGCircles.CircleMeetsCircle[circle1, circle2]; FOR i: NAT IN [1..hitCount] DO iPoints _ CONS[points[i], iPoints]; tangency _ CONS[tangent, tangency]; ENDLOOP; }; EdgLinI: IntersectionProc = { edge: Edge _ NARROW[c1]; line: Line _ NARROW[c2]; point: Point; noHit: BOOL _ FALSE; [point, noHit] _ Lines2d.LineMeetsEdge[line, edge]; IF NOT noHit THEN {iPoints _ LIST[point]; tangency _ LIST[FALSE]} ELSE {iPoints _ NIL; tangency _ NIL}; }; EdgCirI: IntersectionProc = { edge: Edge _ NARROW[c1]; circle: Circle _ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL _ FALSE; [points, hitCount, tangent] _ GGCircles.CircleMeetsEdge[circle, edge]; FOR i: NAT IN [1..hitCount] DO iPoints _ CONS[points[i], iPoints]; tangency _ CONS[tangent, tangency]; ENDLOOP; }; EdgEdgI: IntersectionProc = { e1: Edge _ NARROW[c1]; e2: Edge _ NARROW[c2]; point: Point; noHit: BOOL _ FALSE; [point, noHit] _ Lines2d.EdgeMeetsEdge[e1, e2]; IF NOT noHit THEN {iPoints _ LIST[point]; tangency _ LIST[FALSE]} ELSE {iPoints _ NIL; tangency _ NIL}; }; ArcLinI: IntersectionProc = { arc: Arc _ NARROW[c1]; line: Line _ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL _ FALSE; [points, hitCount, tangent] _ GGCircles.ArcMeetsLine[arc, line]; FOR i: NAT IN [1..hitCount] DO iPoints _ CONS[points[i], iPoints]; tangency _ CONS[tangent, tangency]; ENDLOOP; }; ArcCirI: IntersectionProc = { arc: Arc _ NARROW[c1]; circle: Circle _ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL _ FALSE; [points, hitCount, tangent] _ GGCircles.CircleMeetsArc[circle, arc]; FOR i: NAT IN [1..hitCount] DO iPoints _ CONS[points[i], iPoints]; tangency _ CONS[tangent, tangency]; ENDLOOP; }; ArcEdgI: IntersectionProc = { arc: Arc _ NARROW[c1]; edge: Edge _ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL _ FALSE; [points, hitCount, tangent] _ GGCircles.ArcMeetsEdge[arc, edge]; FOR i: NAT IN [1..hitCount] DO iPoints _ CONS[points[i], iPoints]; tangency _ CONS[tangent, tangency]; ENDLOOP; }; ArcArcI: IntersectionProc = { arc1: Arc _ NARROW[c1]; arc2: Arc _ NARROW[c2]; points: ARRAY [1..2] OF Point; hitCount: [0..2]; tangent: BOOL _ FALSE; [points, hitCount, tangent] _ GGCircles.ArcMeetsArc[arc1, arc2]; FOR i: NAT IN [1..hitCount] DO iPoints _ CONS[points[i], iPoints]; tangency _ CONS[tangent, tangency]; ENDLOOP; }; CubLinI: IntersectionProc = { bezier: BezierRef _ NARROW[c1]; line: Line _ NARROW[c2]; points: ARRAY [0..2] OF Point; hitCount: [0..3]; tangent: ARRAY [0..2] OF BOOL _ ALL[FALSE]; [points, hitCount, tangent] _ CubicPathsExtras.CubicMeetsLine[bezier^, -line.s, line.c, -line.d]; FOR i: NAT IN [0..hitCount) DO iPoints _ CONS[points[i], iPoints]; tangency _ CONS[tangent[i], tangency]; ENDLOOP; }; CubicMeetsEdge: PROC [bezier: BezierRef, edge: Edge] RETURNS [points: ARRAY [0..2] OF Point, hitCount: [0..3] _ 0, tangent: ARRAY [0..2] OF BOOL _ ALL[FALSE]] = { linePoints: ARRAY [0..2] OF Point; lineHitCount: [0..3]; lineTangents: ARRAY [0..2] OF BOOL _ ALL[FALSE]; [linePoints, lineHitCount, lineTangents] _ CubicPathsExtras.CubicMeetsLine[bezier^, -edge.line.s, edge.line.c, -edge.line.d]; FOR i: NAT IN [0..lineHitCount) DO IF Lines2d.OnEdge[linePoints[i], edge] THEN { points[hitCount] _ linePoints[i]; tangent[hitCount] _ lineTangents[i]; hitCount _ hitCount + 1; }; ENDLOOP; }; CubEdgI: IntersectionProc = { IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; bezier: BezierRef _ NARROW[c1]; edge: Edge _ NARROW[c2]; points: ARRAY [0..2] OF Point; hitCount: [0..3]; tangent: ARRAY [0..2] OF BOOL _ ALL[FALSE]; [points, hitCount, tangent] _ CubicMeetsEdge[bezier, edge]; FOR i: NAT IN [0..hitCount) DO iPoints _ CONS[points[i], iPoints]; tangency _ CONS[tangent[i], tangency]; ENDLOOP; }; SlcLinI: IntersectionProc = { sliceD: SliceDescriptor _ NARROW[c1]; line: Line _ NARROW[c2]; [iPoints, ----] _ GGSliceOps.LineIntersection[sliceD, line]; FOR list: LIST OF Point _ iPoints, list.rest UNTIL list = NIL DO tangency _ CONS[FALSE, tangency]; ENDLOOP; }; SlcCirI: IntersectionProc = { sliceD: SliceDescriptor _ NARROW[c1]; circle: Circle _ NARROW[c2]; [iPoints, ----] _ GGSliceOps.CircleIntersection[sliceD, circle]; FOR list: LIST OF Point _ iPoints, list.rest UNTIL list = NIL DO tangency _ CONS[FALSE, tangency]; ENDLOOP; }; NewMultiGravityPool: PUBLIC PROC [] RETURNS [REF]= { -- reuseable storage for BestPointAndCurve proc to avoid NEWs pool: MultiGravityPool _ NEW[MultiGravityPoolObj]; pool.bestpoints _ NEW[BestPointsObj[MaxFeatures]]; pool.bestcurves _ NEW[BestPointsObj[MaxFeatures]]; pool.bestfaces _ NEW[BestFacesObj[MaxFeatures]]; FOR i: NAT IN [0..MaxFeatures) DO pool.bestpoints[i] _ NEW[GoodPointObj]; pool.bestcurves[i] _ NEW[GoodPointObj]; pool.bestfaces[i] _ NEW[GoodPointObj]; ENDLOOP; RETURN[pool]; }; END. %DGGMultiGravityImpl.mesa Copyright Σ 1986, 1987, 1989 by Xerox Corporation. All rights reserved. Contents: Performs hit testing similar to uniGravity. Instead of returning a single nearest feature, we return the N (or fewer) nearest features which are within a given tolerance distance from the test point. The algorithm used is described in [Cyan]Documentation>MultiGravity.tioga. Pier, February 18, 1992 5:16 pm PST Bier, April 11, 1990 2:39:57 pm PDT Eisenman, August 11, 1987 6:14:13 pm PDT Doug Wyatt, December 18, 1989 2:38:04 pm PST Arbitration [Artwork node; type 'ArtworkInterpress on' to command tool] We arbitrate between those points which are within an epsilon-width ring of the nearest point. Dispatches to StrictDistance, PointsPreferred, or does nothing depending on the currently selected gravity type. If intersections is TRUE, compute the intersections of the objects that are in the bags. In case an ABORT happened while pool was in use Calls MultiPointsPreferred and picks a single "best" feature. If there are no good features within radius t of testPoint, then resultPoint = testPoint and feature = hitData = NIL. If intersections is TRUE then compute all pair-wise intersections of gravity-active curves and count them as distinguished points. Otherwise, let's do arbitration. Prefer scene objects to alignment lines. Later, we will prefer objects that say the testpoint is "inside" them. Calls MultiLinesPreferred and picks a single "best" feature. If there are no good features within radius t of testPoint, then resultPoint = testPoint and feature = hitData = NIL. This code will be used when we wish to do more sophisticated arbitration: We have more than one "equally close" features. Now we choose on the following basis: 1) Prefer scene objects to alignment lines. 2) Prefer points to lines. Later, we will prefer objects that say the testpoint is "inside" them to those that don't. Calls MultiFacesPreferred and picks a single "best" feature. If there is a filled region that contains the cursor point, it choose the nearest such filled region. Otherwise, it behaves just like LinesPreferred gravity. Cycling Gravity In case an ABORT happened while pool was in use Otherwise, let's do arbitration. Find the nearest slice if one is close enough. Otherwise, start with the nearest alignment object. Start cycling at the first slice. Find the nearest line and any that are almost as near, if any lines exist with radius t. Choose one of these lines. If the winner is an edge, use its curve normal. If no object is found, use the cursor position. Find how many nearest neighbors there are. This may come in handy some day for extra arbitration Find how many nearest neighbors there are. Multi-Gravity Routines facesPreferred => [nearVEF, count] _ MultiFacesPreferred[testPoint, t, alignBag, sceneBag, ggData]; Returns up to MaxFeatures closest features, their closest points, and their distances from the testpoint. Features outside of criticalR, will not be included. The results will be located in nearVEF[0] .. nearVEF[count-1]. Returns up to MaxFeatures closest features, their closest points, and their distances from the testpoint. Features outside of criticalR, will not be included. The results will be located in nearVEF[0] .. nearVEF[count-1]. Caution: bestCurves and bestPoints are allocated from a pool. Copy them before returning them to the user (e.g. in a cycler). Returns up to MaxFeatures closest features, their closest points, and their distances from the testpoint. Features outside of criticalR, will not be included. The results will be located in nearVEF[0] .. nearVEF[count-1]. If any points are within the inner radius innerR, then only points (e.g. vertices, control points, and intersection points) will be mentioned. Otherwise, nearVEF may consist of a mixture of points and curves. Caution: bestCurves and bestPoints are allocated from a pool. Copy them before returning them to the user (e.g. in a cycler) For each gravity active point, find its distance from the testpoint. Package this information up into the thisPoint record. Then call AddNeighbor, which will add this point to the list of best points, if appropriate. When VertsInNeighborhoodPlus returns, h will contain a set of up to MaxFeatures points all of which are within a distance t of q. If h.overflow is FALSE, h contains the nearest point in the scene (distance h.min from q) and all other points o such that dist(o, q) <= h.min + h.s, and dist(o, q) <= t. If h.overflow is TRUE, there were more than MaxFeatures such points. In this case, h includes the nearest n such points n = MaxFeatures. thisPoint.normal _ [0,-1]; -- eventually this should just agree with the anchor orientation FeatureWalkProc: TYPE = PROC [feature: FeatureData] RETURNS [done: BOOL _ FALSE]; largeTolerance: REAL = 9999.00; largeTolerance: REAL = 9999.00; thisPoint.normal _ [0, -1]; -- Should figure out midpoint's normal for slice. -- Only edge and arc work now anyway. Returns the curves in the near band in order of increasing distance from q. For each gravity active object, find the distance of the gravity active object from the testpoint. Package this information up into the thisCurve record. Then call AddNeighbor, which will add this curve to the list of best curves, if appropriate. When CurvesInNeighborhood returns, h should contain some number of curves such that they are all within t of q. If h.overflow is FALSE, then h contains the closest curve (at distance h.min) and all other curves o such that dist(o, q) < MAX[h.min + h.s, innerR] and dist(o, q) < t. If h.overflow is TRUE then it wasn't possible to include all such curves. h contains the closest n such curves (where n = MaxFeatures). FeatureWalkProc: TYPE = PROC [feature: FeatureData] RETURNS [done: BOOL _ FALSE]; FeatureWalkProc: TYPE = PROC [feature: FeatureData] RETURNS [done: BOOL _ FALSE]; Align Bag Scene Bag. FeatureWalkProc: TYPE = PROC [feature: FeatureData] RETURNS [done: BOOL _ FALSE]; Scene Bag. Maintaining the Nearest-Neighbor Structure AddNeighbor maintains these invariants: There is valid data in h[0] up to h[size-1]. Call these the Elements of h. All other components of h have dist = infinity. h.min is the minimum value of dist(q, x) for x element of h. If overflow is FALSE, then h contains all objects o, seen so far, such that h.min <= dist(o, q) <= MAX[h.min+h.s, innerR], if curve is TRUE, h.min <= dist(o, q) <= h.min+h.s, if curve is FALSE h may contain other objects as well. If overflow is TRUE, all objects in h satisfy h.min <= dist(o, q) <= MAX[h.min+h.s, innerR], if curve is TRUE, h.min <= dist(o, q) <= h.min+h.s, if curve is FALSE but there are one or more objects that satisfy this property that are not in h. Those objects that are not included are at least as far from q as the farthest object in h. dTol is a hint to the caller that the caller need not pass in objects that are more than dTol units away from q, since AddNeighbor is just going to throw them away. When AddNeighbor returns, h.dTol = t if h.size = 0, h.dTol = MAX[h.min+h.s, innerR], if h.size > 0 and curve is TRUE, h.dTol = h.min + h.s, if h.size > 0 and curve is FALSE. Replace the worst element with the new one if the new is better. Now, update h.max and h.maxIndex the hard way. Replace the worst element with the new one if the new is better. Now, update h.minPriority and h.minIndex the hard way. Merge the bestPoints and the bestCurves. There will be count elements in the result. Merge the two sorted lists together classifying the segments by the AND of the Classifs for each segment We have different paths within the same trajectory or cluster. Choose whichever is closer in the overlap order of the cluster Sort the points in order of increasing distance. Since n is likely to be small, bubble sort is sensible. Sort the curves in order of increasing distance. Since n is likely to be small, bubble sort is sensible. Sort the curves in order of descreasing priority. Since n is likely to be small, bubble sort is sensible. Sort the vertices, edges, and faces in order of decreasing priority. Since n is likely to be small, bubble sort is sensible. Computing Intersections 0) NoOp 1) Line 2) Circle 3) Edge 4) Arc 5) Cubic 6) Slice IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; [points, hitCount] _ GGCircles.ArcMeetsArc[arc1, arc2]; IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL]; Utilities Κ>“– "cedar" style•NewlineDelimiter ˜codešœ™KšœH™HKšΟnœ‘™©Kšœ#™#Kšœ#™#Kšœ(™(K™,—K™šΟk ˜ Jšœψ˜ψ—K˜Kšœžœž˜!Kšžœ~˜…Kšžœž˜˜Kšœ žœžœ ˜!Kšœ žœ ˜1Kšœžœ$˜9Kšœžœ"˜5Kšœžœžœ˜-Kšœžœ&˜=Kšœžœ˜Kšœžœ˜Kšœ žœžœ˜Kšœžœ˜%Kšœžœ˜#Kšœžœ˜Kšœžœžœ˜+Kšœžœ%˜;Kšœ žœžœ˜'Kšœžœ˜3Kšœžœ˜'Kšœ žœžœ˜#Kšœžœ!˜3Kšœ žœ ˜1Kšœžœ˜3Kšœžœ˜Kšœžœžœ˜=Kšœžœ.˜MKšœžœ˜!Kšœžœ!˜7Kšœžœ#˜;Kšœžœ˜!Kšœ žœ˜'Kšœžœ!˜7Kšœ žœ˜'Kšœžœ˜!Kšœžœ ˜5Kšœžœ#˜;Kšœ žœžœ˜%Kšœžœ"˜5Kšœžœ˜#K˜Kšœ žœžœ˜%šœžœžœ˜Kšœžœ˜ Kšœ žœ˜Kšœ žœ˜Kšœ žœΟc?˜QKšœžœŸ ˜KšœžœŸS˜aKšœžœŸ›˜€Kšœ žœ˜Kšœžœžœžœ ˜(K˜—Kšœ žœžœ˜#šœžœžœ˜Kšœžœ˜ Kšœžœ˜Kšœ žœ˜Kšœžœ˜Kšœ žœŸ7˜IKšœ žœ˜Kšœžœžœžœ ˜'—K˜Kšœžœžœ˜1šœžœžœ˜$Kšœ˜Kšœ˜K˜Kšœ˜—K˜—Kš œžœžœ žœžœ˜/K˜™ I artworkFigure–G91.72222 mm topLeading 91.72222 mm topIndent 1.411111 mm bottomLeading •Bounds60.0 mm xmin 0.0 mm ymin 93.83888 mm xmax 88.9 mm ymax •Artwork Interpress• Interpressš Interpress/Xerox/3.0  f j k j‘₯“ΔWB € ¨  ͺœ‘£Ι ’ ¨ r j  Ί ’ ¨‘‘¨ΔWB € ¨ r j‘₯“ΔWB € ¨‘‘¨ r jΔWΑΑ €ΔDBCΔŒ5r ’ ₯ ¨‘‘¨ΔŒZ―“Ÿ ™‘ Ÿ ‘“‘Έ k ι r jΔ Ω€ €Δ˜jeΔ[‹B ’ ₯ ¨ r j‘‘¨Ÿ ™‘ Ÿ ‘“‘‘ ‘™ k ι‘‘¨ΔI\―“Ÿ ™‘ Ÿ ‘“‘Έ k ι r jΔ Ω€ €Δ.΅0ΔYΥ? ’ ₯ ¨ r j‘‘¨Ÿ ™‘ Ÿ ‘“‘‘ ‘™ k ι‘‘¨ΔI\―“Ÿ ™‘ Ÿ ‘“‘Έ k ι r jΔ Ω€ €ΔΕ Δ1 ’ ₯ ¨ r j‘‘¨Ÿ ™‘ Ÿ ‘“‘‘ ‘™ k ι‘‘¨ΔI\―“Ÿ ™‘ Ÿ ‘“‘Έ k ι r jΔ Ω€ €ΔΗaSΔAh/ ’ ₯ ¨ r j‘‘¨Ÿ ™‘ Ÿ ‘“‘‘ ‘™ k ι‘‘¨ΔI\―“Ÿ ™‘ Ÿ ‘“‘Έ k ι r jΔ› €ΔDBCΔŒ5r ’ ₯ ¨‘‘¨Δ›Ž―“Ÿ ™‘ Ÿ ‘“‘Έ k ι r jΔ@Όρ €ΔDBCΔŒ5r ’ ₯ ¨‘‘¨Δρ ^―“Ÿ ™‘ Ÿ ‘“‘Έ k ι£―“   £‘ˆ‘‘ΕXeroxΕResearchΕ RGBLinear£‘‘¦ η • ” η­“’·“’°“ΔUήUΥ™ΔDBCΔŒ5r—§Υ—˜ r jΔΔ'εΉ ’ ¨ΕXeroxΕ TiogaFontsΕ Helvetica10£‘ “‘•‘ —‘‘¨  ŠΑTolerance Radius– k ι r j‘‘¨’·“‘―“‘‘¨ k ι r jΔV9^Δϊ^Ή ’ ¨ΕXeroxΕ TiogaFontsΕ Helvetica10£‘ “‘•‘ —‘‘¨  ŠΑNearest– k ι r j‘‘¨’·“‘―“‘‘¨ k ι r jΔ_?cΔμ ’ ¨ΕXeroxΕ TiogaFontsΕ Helvetica10£‘ “‘•‘ —‘‘¨  ŠΑCaret– k ι r j‘‘¨’·“‘―“‘‘¨ k ι r jΔ€Δm ’ ¨ΕXeroxΕ TiogaFontsΕ Helvetica10£‘ “‘•‘ —‘‘¨  ŠΑNearest + Epsilon– k ι r j‘‘¨’·“‘―“‘‘¨ k ι k ι k ι k gšœ=™=IartworkCaption™^K˜—šœžœžœžœKžœžœžœEžœžœ˜άKšœ†žœ@™Κšžœžœ˜Kšœ0˜0KšŸ/™/K˜—Kšœ:˜:Kšœ)˜)šžœžœ˜$šžœ ž˜šœ˜Kšœs˜s—šœ!˜!Kšœc˜c—Kšžœžœ˜—K˜—šžœ˜Kšœ˜Kšœ žœ˜Kšœ˜K˜—Kšœ(˜(K˜K™—šœžœžœžœKžœžœžœEžœžœ˜θKšœ°žœ…™ΈKšœžœ˜ Kšœ ˜ Kšœa˜aKš žœ žœžœžœžœ˜7Kšžœ žœžœ˜2šžœ˜KšΟb ™ Kšœžœ˜Kšœžœ Ÿ˜!Kšœ žœ˜Kšœ˜šžœžœžœ ž˜Kšžœ#žœ#˜LKšžœ˜—Kšžœžœžœ˜;Kš (™(Kš F™Fšžœžœžœž˜#šžœ%žœ˜-Kšžœ˜!K˜—šž˜Kšžœžœ˜-—Kšžœ˜—K˜—K˜—šœžœžœžœ<žœEžœžœ˜ΚKšœ³™³Kšœ ˜ Kšœžœ˜ Kšœ œ+˜QKš žœ žœžœžœžœ˜7Kšžœ žœžœ˜2šžœ˜Kš I™IKšœžœ˜Kšœžœ˜Kšœžœ˜Kšœžœ Ÿ˜!Kšœ˜šžœžœžœ ž˜Kšžœ#žœ#˜LKšžœ˜—šžœžœžœ˜;Kš V™VKš +™+Kš ™Kš Z™Z—K˜Kšžœ˜!K˜—K˜K˜—šœžœžœžœ<žœEžœžœ˜ΚKšœά™άKšœ ˜ Kšœžœ˜ K˜Kšœ œ+˜QKš žœ žœžœžœžœ˜7Kšžœ˜ K˜—K˜š  œžœ*žœžœEžœžœ˜šKšœ&˜&Kšœ˜Kšœ˜Kšœ ˜ Kšœ˜K˜K˜—K™K™š œž œžœ#˜Všœžœ˜(Kšœ žœ˜ Kšœ ˜ Kšœ ˜ Kšœ˜K˜—K˜K˜—š  œžœžœžœKž œžœ#˜΄šžœžœ˜Kšœ0˜0KšŸ/™/K˜—Kšœ:˜:šžœžœ˜$šžœ ž˜šœ˜Kšœ_˜_—šœ!˜!KšœO˜O—Kšžœžœ˜—K˜—šžœ˜Kšœ'˜'K˜—K˜K˜—šœžœ&žœžœ#˜bKšœ&˜&Kšœžœ#˜-šžœžœžœ ž˜Jšœ˜šœžœ˜#Jšœ˜Jšœ˜Jšœ˜Jšœ&˜&Jšœ˜Jšœ$˜$Jšœ˜—Jšžœ˜—K˜K˜—š œžœžœžœKž œžœ#˜ΪKšœžœ˜ Kšœ ˜ šž˜Kšœa˜aKšžœ žœžœ˜1Kšžœ žœžœ˜'šžœ˜Kš  œe™…Kšœžœ˜Kšœžœ Ÿ˜!Kšœ žœ˜K˜šœžœ˜(Kšœ žœŸ˜(Kšœ ˜ Kšœ Ÿ˜%K˜K˜—Kšœ˜šžœžœžœ ž˜Kšžœ#žœ#˜LKšžœ˜—Kšžœžœžœ˜0Kšœ0˜0Kš !™!šžœžœžœž˜#šžœ%žœ˜-Kšœ˜Kšžœ˜K˜—šž˜Kšžœ˜$—Kšžœ˜—K˜—šž˜˜šœžœ˜(Kšœ!˜!Kšœ ˜ Kšœ ˜ K˜K˜—K˜——Kšžœ˜—K˜K˜K˜—š œžœžœžœ<žœ#˜’K™₯K™/Kšœ ˜ Kšœžœ˜ šž˜Kšœ œ+˜QKšžœ žœžœ˜1Kšžœ žœžœ˜'šžœ˜Kšœ žœ˜Kšœžœ˜Kšœžœ˜Kšœžœ Ÿ˜!Kšœ˜Kš *™*šžœžœžœ ž˜Kšžœ#žœ#˜LKšžœ˜—Kšžœžœžœ˜0K˜šœžœ˜(Kšœ!˜!Kšœ ˜ Kšœ ˜ Kšœ˜K˜—K˜—šž˜šœ˜šœžœ˜(Kšœ!˜!Kšœ ˜ Kšœ ˜ Kšœ˜K˜—K˜——Kšžœ˜—K˜K˜—š œžœžœžœ<žœ#˜’Kšœ ˜ Kšœžœ˜ šž˜Kšœ œ+˜QKšžœ žœžœ˜1Kšžœ žœžœ˜'šžœ˜Kšžœ˜Kš 5™5Kšœžœ˜Kšœžœ˜Kšœžœ˜Kšœžœ Ÿ˜!Kšœ˜Kš *™*šžœžœžœ ž˜Kšžœ#žœ#˜LKšžœ˜—Kšžœžœžœ˜0K˜šœžœ˜(Kšœ!˜!Kšœ ˜ Kšœ ˜ Kšœ˜K˜—K˜—šž˜šœ˜šœžœ˜(Kšœ!˜!Kšœ ˜ Kšœ ˜ Kšœ˜K˜—K˜——Kšžœ˜—K˜K™—š  œžœžœ žœEžœžœ˜‘Kšžœ˜$K˜K˜—š  œžœžœ žœEžœžœ˜Kšžœ˜$K˜K˜—š œžœžœ žœEžœžœ˜”Kšžœ˜%K˜K˜—š  œžœžœ/žœEžœžœ˜žšžœžœžœŸ˜;KšœŸ˜"Kšœ˜Kšœ žœ˜Kšœ žœ˜K˜—šžœžœŸ˜DKšœ&˜&Kšœ˜Kšœ žœ˜Kšœ žœ˜K˜—šžœ˜KšœIžœ˜aKšœd˜dK˜—K˜K˜—K™šœ™K™—šœžœžœžœKž œžœ*žœ˜ΒKšžœžœ6Ÿ2˜uKšœ)˜)šžœž˜$šžœ ž˜*™KšœQ™Q—šœ˜KšœQ˜Q—šœ˜Kšœa˜a—Kšžœžœ˜K˜——šžœ˜Kšœ žœ˜Kšœ ˜ K˜—Kšœ(˜(K˜K˜—š œžœžœžœ<žœ*žœ˜°Kšœί™ίKšœ#˜#Kšœ˜Kšœ#žœ˜'K˜šžœ!žœ#ž œžœ˜]K˜—Kšœ œ+˜[Kšœ$˜$K˜Kšœ œ.˜aK˜Kšœ œCžœ˜|Kšœ#˜#K˜Kšœžœ'˜2Kšœ žœ#˜0Kš œA˜UKšœ œ'˜SK˜K˜—š œžœžœžœ<žœ*žœ˜°Kšœί™ίKšœ˜Kšœ˜Kšœžœ˜K˜šžœ!žœ#ž œžœ˜]K˜—Kš ~™~Kšœ œ.˜aK˜Kšœ œCžœ˜|Kšœ#˜#K˜Kšœžœ'˜2Kšœ žœ#˜0Kš œA˜UK˜K˜—šΠbn žœžœžœKž œžœ*žœ˜ΞKšœ²™²Kšœ˜Kšœ˜Kšœžœ˜Kš Πbk  ˜Kš žœ!žœ#žœžœžœ˜]K˜Kš }™}Kšœ œ3˜fK˜Kšœ œR˜„Kšœ#˜#K˜šžœžœžœ˜8Kšœ˜Kšœ žœ#˜0Kšœ6˜6K˜—šžœ˜Kšœžœ'˜2Kšœ žœ#˜0KšœU˜UK˜—K˜K˜—šœžœ&žœ, œ Οiœžœ!ž œžœžœ˜ήKšœ˜KšœΪ™ΪKšœ™Kšœžœ”™ͺKšœžœt™‰š œžœ6Ÿ˜^Kšœ žœ˜Kšœ žœ ˜Kšœ9˜9Kšœžœ˜šžœžœ˜ Kšœ(˜(KšœŸ@™[Kšœ%žœŸ ˜NKšžœ2žœ˜TKšœ$˜$Kšœ˜Kšœ!žœ˜(K˜—K˜—š œžœN˜`Kšœ œc˜ƒšžœ žœ˜šžœžœ˜Kšœ$˜$šžœ2žœ˜;Kšœ˜Kšœ˜—KšœE˜EKšœ!žœ˜(K˜—Kšœ˜—K˜—šœ˜.Kš œžœžœžœžœžœ™QKšœ žœ!˜0Kšœ)˜)K˜K˜—K˜Kšœ˜Kšœ žœžœ˜Kšœžœ˜Kšœ žœ ˜/K˜Kšœ žœ˜Kšœ"˜"K˜šžœžœ˜Kšœ œ>˜VKšžœ žœ  œ>˜dK˜—K˜Kšœ$ œ˜7Kšœ˜šžœžœžœ˜Kš œ žœ˜*Kšžœžœžœžœ˜)Kšœ+˜+Kšœ%˜%K˜—Kšœ˜šžœ žœ˜Kšœ.˜.Kšœ.˜.K˜—KšœŸ!˜$K™—š œžœ&žœ-žœžœžœ˜¨Kšœžœ ™Kšœ˜Kšœžœžœ˜Kšœžœžœžœ˜(Kšœ žœžœ˜Kšœ˜šžœžœžœž˜ Kšœ˜KšžœžœžœŸœ˜Yšžœžœžœž˜Kšœ˜KšžœžœžœŸ5˜VKšœ?˜?Kšœ˜š žœžœžœ!žœžœž˜EKšœ˜Kšœ8˜8Kšœ!˜!šžœ žœ˜Kšœžœ˜/šœ!žœ˜:Kšœ˜Kšœ˜Kšœ˜Kšœ˜—Kšœ%˜%Kšœ#˜#Kšœ$˜$Kšœ˜šžœ!žœ˜)Kšœžœ˜;Kšœ˜Kšœ7˜7Kšœ#˜#KšœœŸ;˜…K˜—šžœžœ!žœ˜.Kšœžœ˜;Kšœ˜Kšœžœ8˜PKšœ#˜#KšœœŸ;˜…K˜—Kšžœžœ˜Kšžœ2žœ˜TKšœ!žœ˜(K˜—Kšœ˜Kšžœ˜—Kšžœ˜—Kšžœ˜—K˜K˜—š  œžœ&žœ-žœžœžœ˜€Kšœžœ ™Kšœ˜Kšœ˜Kšœ žœžœ˜Kšœ˜šžœžœžœž˜ šœ˜Kšžœžœžœ˜*Kšœ-˜-Kšžœžœ žœžœ˜Kšœ˜Kšœ8˜8Kšœ!˜!šžœ žœ˜Kšœžœ˜:Kšœ˜Kšœžœ˜/šœ!žœ˜:Kšœ˜Kšœ žœ˜Kšœ˜Kšœžœ˜—Kšœ˜Kšœ#˜#Kšœ$˜$Kšœ"˜"Kš œŸ1œŸ%™xKšœœŸ2˜|Kšžœ2žœ˜TKšœ7˜7Kšœ!žœ˜(K˜——Kšžœ˜—K˜K˜—š œžœIžœ žœžœžœ˜§K™KKšœψ™ψKšœo™oKšœžœfžœ)™¨Kšœžœs™ˆš œžœA˜RKšœ/˜/šžœžœ˜Kšœ$˜$Kšœ5˜5Kšœ5˜5šžœ1žœ˜;Kšœ˜—Kšœžœ˜Kšœ˜Kšœ!žœ˜'K˜—K˜—š œžœE˜Xšœžœžœžœ˜FKšœ žœ ˜KšžœžœA˜`Kšžœe˜iKšœ˜—Kšœ4˜4Kšœžœ"˜5Kšœžœ˜2šžœžœ˜Kšœ$˜$Kšœ)˜)Kšžœžœ˜9Kšžœ6˜:Kšœžœ˜Kšœ˜Kšœ!žœ˜'K˜—K˜—š œžœN˜`Kšœ žœžœ˜Kšœ…˜…šžœ žœ˜šžœžœ˜Kšœ$˜$šžœ2žœ˜;Kšœ˜Kšœ˜—KšœE˜EKšœ!žœ˜'K˜—K˜—K˜—šœ˜-Kš œžœžœžœžœžœ™QKšœžœ$˜1Kšœ&˜&K˜—šœ˜,Kš œžœžœžœžœžœ™QKšœ žœ!˜0Kšœ)˜)K˜—K˜ K˜K˜Kšœ˜Kšœžœžœ˜Kšœžœ˜)Kšœžœ˜Kšœ*˜*K˜Kš  ™ Kšœ3˜3š žœ  œžœžœ4žœžœž˜dKšœ˜Kšœžœ(˜5Kšœ*˜*Kšžœ˜—š žœ œžœžœ3žœ žœž˜[Kšœ˜Kšœžœ˜!Kšœ*˜*Kšžœ˜—š žœ œžœžœ3žœ žœž˜]Kšœ˜Kšœ žœ,˜;Kšœ.˜.Kšžœ˜—Kš  ™ Kšœ$ œ˜5K˜šžœ žœ˜Kšœ.˜.Kšœ-˜-K˜—Kšœ˜KšœŸ˜"K˜—š œžœIžœžœžœ˜–K˜Kšœžœžœ˜Kšœžœ˜(Kšœ žœ˜K˜š œžœM˜_Kšœ žœžœ˜Kš œžœžœžœžœ˜Kšœ žœžœ˜šžœ@žœ˜HKšœO˜Ošžœ žœžœ˜Kšœ˜K•StartOfExpansion:[scene: GGModelTypes.Scene, slice: GGModelTypes.Slice]šœD˜DKšœ˜Kš œ˜Kšœ#˜#Kšœ œ˜#K˜—šžœžœžœžœžœžœžœž˜GKšœ˜K–:[scene: GGModelTypes.Scene, slice: GGModelTypes.Slice]šœD˜DKšœ˜Kš œ˜Kšœ#˜#Kšœ œ˜#Jšžœ˜—K˜—K˜—šœ˜,Kš œžœžœžœžœžœ™QKšœ žœ!˜0Kšœ(˜(K˜—K˜Kšœ˜K˜Kš  ™ Kšœ$ œ˜5K˜Kšœ˜šžœ žœ˜Kšœ-˜-Kšœ,˜,K˜—Kšœ˜K˜—K˜K™*Kš œžœ˜K˜šœžœžœ˜CKšœžœ6˜@Kšœ ˜ K˜K˜Kšœžœžœ˜Kšœ˜Kšœ žœ˜šžœžœžœž˜!Jšœ˜Jšœžœ˜Jšžœ˜—J˜J˜—š œžœžœ žœžœ˜\Kšœžœ7˜AKšœ ˜ K˜ K˜Kšœ˜K˜ Kšœ˜Kšœ Ÿ˜Kšœ"˜"Kšœ žœ˜šžœžœžœž˜!Jšœ˜Jšœžœ˜Jšžœ˜—J˜J˜—šœžœžœžœ˜NKšœžœ7˜AKšœ ˜ K˜ K˜Kšœ˜K˜ Kšœ Ÿ˜Kšœ"˜"Kšœ žœ˜šžœžœžœž˜!Jšœ˜Jšœžœ˜Jšžœ˜—J˜—˜Kšœγ™γšœžœ7™KKšœžœ&™@Kšœ3™3—Kšœ$™$šœžœ™-Kšœžœ&™@Kšœ3™3—Kšœ¬™¬Kšœ€™€šœ3™3Kšœ žœ5™AKšœ7™7—K™—š  œžœ.ž œžœžœ˜eKšœžœ˜Kšœžœ˜šž˜šžœžœž˜KšœžœŸ=˜VKšœžœ˜Kšœžœ˜%Kšžœžœ"˜3—šž˜šœ˜Kšœ˜Kšžœ žœ"˜3Kšœžœ ˜Kšœ˜Jšžœžœžœ˜6Jšžœ˜K˜—šœ˜Kš @™@šžœ žœžŸ˜%Jšœ˜Jšœžœ˜(Kšœžœ ˜Jšžœžœžœ˜6Jšžœ˜Jšœ"˜"Kš .™.šž˜Kšœ žœ˜Kšœ žœ˜šžœžœžœž˜!Jšžœžœ%˜@Jšžœ˜—Jšœ˜Jšœ˜Jšžœ˜—J˜—šžœŸ˜Jšœ˜Jšœžœ˜$Jšœ žœ˜J˜—J˜—šœ ˜ Jšœ˜Jšœžœ˜$Jšœ"˜"J˜——Jšžœ˜—K˜K˜—šœžœ%žœžœ˜PKšœžœ˜Kšœžœ˜šž˜šžœžœž˜KšœžœŸ!˜AKšœžœ˜Kšœžœ˜%Kšžœžœ"˜3—šž˜šœ˜Kšœ˜Kšžœžœ*˜CKšœžœ˜&Kšœ˜Jšœ˜K˜—šœ˜Kš @™@šžœžœžŸ˜-Jšœ˜Jšœžœ&˜@Kšœžœ˜&Jšœ žœ˜Kš 6™6šž˜Kšœ žœ˜Kšœ žœžœžœ˜šžœžœžœž˜!Jšžœžœ-˜PJšžœ˜—Jšœ˜Jšœ˜Jšžœ˜—Jšœ,˜,J˜—šžœŸ˜Jšœ˜Jšœžœ˜4Jšœ žœ˜J˜—J˜—šœ ˜ Jšœ˜Jšœžœ˜4Jšœ žœ˜J˜——Jšžœ˜—K˜—K˜šœžœ&žœ&˜išžœžœžœž˜ Kšœ˜Kšžœ˜—K˜K˜—š œžœ&žœ&žœ*žœ˜žKš U™UKšœžœ˜Kšœžœ˜K˜K˜šžœžœžœ ž˜Iprocšžœžœžœ˜3Nšžœžœžœ˜3Nšœ˜N˜šžœžœ˜ Nšœ$˜$Nšœ˜N˜—šžœ˜Nšœ$˜$N˜N˜—šž˜NšœŸ˜/šžœžœ žœ ž˜'Nšœ$˜$Nšœ˜—Nšžœ˜ NšœŸ˜/šžœžœ žœ ž˜'Nšœ$˜$Nšœ˜—Nšžœ˜ —Nšžœ˜K˜K˜——š œžœžœ.žœžœ*žœ˜­Nšœh™hNšœžœ˜N˜Kšœžœ$˜/Kšœ žœ#˜0Nšœ˜N˜šžœžœžœ ž˜Nšžœžœžœ˜5Nšžœžœžœ˜2N˜šž˜Nšžœ5ž˜?šœ Ÿ!˜*šœžœ:˜Ošžœžœ˜"N˜Nšœžœžœ˜#NšœP˜PNšœT˜TNšžœžœžœ˜2N™~šžœ1ž˜;Nšœžœ˜Nšœ žœ˜Nšœ žœ˜Nšžœžœ˜—N˜—Nšžœžœ˜—N˜—Nšœžœ˜Nšœžœ˜Nšžœžœ˜šž˜šœ˜Nšœ˜Nšœ˜Nšœ˜Nš œŸ˜2N˜—˜Nšœ˜Nšœ˜N˜—˜Nšœ˜Nšœ˜N˜——Nšžœ˜——šž˜NšœŸ˜-šžœžœ žœ ž˜'Nšœ˜Nšœ˜—Nšžœ˜ NšœŸ˜-šžœžœ žœ ž˜'Nšœ˜Nšœ˜—Nšžœ˜ —Nšžœ˜NšœŸ#˜&N˜—š œžœ&žœ˜>K™iKšœ˜šžœžœžœž˜&šžœžœžœž˜&šžœ+žœ˜3Kšœ˜Kšœ ˜ Kšœ˜K˜—Kšžœ˜—Kšžœ˜—˜K˜——š œžœ&žœ˜>K™iKšœ˜šžœžœžœž˜&šžœžœžœž˜&šžœ+žœ˜3Kšœ˜Kšœ ˜ Kšœ˜K˜—Kšžœ˜—Kšžœ˜—K˜K˜—š œžœ#žœ˜:K™jKšœ˜šžœžœžœž˜%šžœžœžœž˜%šžœ1žœ˜9Kšœ˜Kšœ˜Kšœ˜K˜—Kšžœ˜—Kšžœ˜—K˜K˜—š œžœžœ˜6K™}Kšœ˜šžœžœžœž˜!šžœžœžœž˜!šžœ)žœ˜1Kšœ˜Kšœ˜Kšœ˜K˜—Kšžœ˜—Kšžœ˜—K˜—K™™K™—š œžœžœžœžœ˜\Kšœžœ˜ Kšœ žœžœ˜Kšœ,˜,šžœž˜šœŸ˜Kšœ žœ˜!KšœE˜EKšœ žœ˜K˜—šœŸ˜ Kšœ žœ˜Kšœ?˜?Kšœ žœ˜K˜—Kšžœžœžœ˜ —K˜K˜—š  œžœžœ žœžœžœ˜UKšœ)˜)šžœž˜šœ ˜ Kšœžœ˜0Kšœ žœžœ˜!KšœE˜Ešžœžœžœ˜Kšœ˜Kšœ ˜ Kšžœ˜K˜—Kšœ˜—šœ˜Kšœ ˜ Kšœžœ(˜