<> <> <Documentation>MultiGravity.tioga.>> <> <> <> <> <<>> 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; <> << [Artwork node; type 'ArtworkInterpress on' to command tool] >> <> 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 { <> <> <<1) Prefer scene objects to alignment lines.>> <<2) Prefer points to lines.>> <> bestSceneObject _ -1;>> 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; <> <> 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; }; <<>> 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 <>> <<[nearVEF, count] _ MultiFacesPreferred[testPoint, t, alignBag, sceneBag, ggData];>> 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; }; <> <> <> <> <> <> <> <> <> <> <> < 0 and curve is TRUE,>> < 0 and curve is FALSE.>> <<>> 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 = [ <<0) NoOp 1) Line 2) Circle 3) Edge 4) Arc 5) Cubic 6) Slice>> [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] _ GGCircles.ArcMeetsArc[arc1, arc2];>> [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.