GGMultiGravityImpl.mesa
Copyright Ó 1986, 1987, 1989, 1992 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]<Gargoyle>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, April 10, 1992 12:09 pm PDT
DIRECTORY
CodeTimer, Cubic2, CubicPaths, GGAlign, GGBasicTypes, GGCaret, GGCircles, GGCoreTypes, GGInterfaceTypes, GGModelTypes, GGMultiGravity, GGParent, GGScene, GGSegmentTypes, GGSliceOps, GGState, GGUtility, Lines2d, Real, RealFns, Rope, Vectors2d;
GGMultiGravityImpl: CEDAR PROGRAM
IMPORTS CodeTimer, CubicPaths, 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;
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.
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] = {
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.
ENABLE UNWIND => {
ggData.multiGravityPool ¬ NewMultiGravityPool[];
In case an ABORT happened while pool was in use
};
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] = {
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.
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 {
Otherwise, let's do arbitration.
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];
Prefer scene objects to alignment lines.
Later, we will prefer objects that say the testpoint is "inside" them.
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] = {
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.
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 {
This code will be used when we wish to do more sophisticated arbitration:
<<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 RETURN PrepareWinner[nearVEF, 0];
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.
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] = {
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.
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;
};
Cycling Gravity
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[];
In case an ABORT happened while pool was in use
};
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 {
Otherwise, let's do arbitration. Find the nearest slice if one is close enough. Otherwise, start with the nearest alignment object.
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];
Start cycling at the first slice.
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] = {
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.
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;
Find how many nearest neighbors there are.
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;
This may come in handy some day for extra arbitration
<<nearestDist: REAL ¬ -1;
bestSceneObject: INT ¬ -1;
neighborCount: NAT ¬ 1;
s: REAL = 0.072; -- 1/1000 inches
nearestDist ¬ nearVEF[0].dist;
Find how many nearest neighbors there are.
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];
};
};
Multi-Gravity Routines
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
facesPreferred =>
[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] = {
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].
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] = {
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].
bestCurves: BestPoints;
bestPoints: BestPoints;
pointCount, curveCount: NAT;
IF GGAlign.EmptyAlignBag[alignBag] AND GGAlign.EmptyTriggerBag[sceneBag] THEN RETURN[NIL, 0];
Caution: bestCurves and bestPoints are allocated from a pool. Copy them before returning them to the user (e.g. in a cycler).
[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] = {
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.
bestCurves: BestPoints;
bestPoints: BestPoints;
pointCount, curveCount: NAT;
innerR: REAL ¬ t/2.0;
IF GGAlign.EmptyAlignBag[alignBag] AND GGAlign.EmptyTriggerBag[sceneBag] THEN RETURN[NIL, 0];
Caution: bestCurves and bestPoints are allocated from a pool. Copy them before returning them to the user (e.g. in a cycler)
[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;
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.
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 ← [0,-1]; -- eventually this should just agree with the anchor orientation
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 = {
FeatureWalkProc: TYPE = PROC [feature: FeatureData] RETURNS [done: BOOL ← FALSE];
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] = {
largeTolerance: REAL = 9999.00;
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] = {
largeTolerance: REAL = 9999.00;
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 ← [0, -1]; -- Should figure out midpoint's normal for slice.  -- Only edge and arc work now anyway.
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] = {
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).
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 = {
FeatureWalkProc: TYPE = PROC [feature: FeatureData] RETURNS [done: BOOL ← FALSE];
line ¬ NARROW[feature.shape, AlignmentLine].line;
ProcessLine[line, thisCurve, feature];
};
DoForSceneSlice: GGAlign.FeatureWalkProc = {
FeatureWalkProc: TYPE = PROC [feature: FeatureData] RETURNS [done: BOOL ← FALSE];
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];
Align Bag
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;
Scene Bag.
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 = {
FeatureWalkProc: TYPE = PROC [feature: FeatureData] RETURNS [done: BOOL ← FALSE];
sliceD ¬ NARROW[feature.shape, SliceDescriptor];
ProcessSlice[sliceD, thisFace, feature];
};
h ¬ BestFacesFromPool[ggData];
Scene Bag.
GGAlign.WalkSliceTriggers[sceneBag, DoForSceneSlice];
faceCount ¬ h.size;
IF h.overflow THEN {
CodeTimer.StartInt[$FaceOverflow, $Gargoyle];
CodeTimer.StopInt[$FaceOverflow, $Gargoyle];
};
SortFaces[h, faceCount];
};
Maintaining the Nearest-Neighbor Structure
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 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.
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 => {
Replace the worst element with the new one if the new is better.
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;
Now, update h.max and h.maxIndex the hard way.
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 => {
Replace the worst element with the new one if the new is better.
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;
Now, update h.minPriority and h.minIndex the hard way.
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] = {
Merge the bestPoints and the bestCurves. There will be count elements in the result.
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] = {
Merge the two sorted lists together classifying the segments by the AND of the Classifs for each segment
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;
We have different paths within the same trajectory or cluster. Choose whichever is closer in the overlap order of the cluster
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] = {
Sort the points in order of increasing distance. Since n is likely to be small, bubble sort is sensible.
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] = {
Sort the curves in order of increasing distance. Since n is likely to be small, bubble sort is sensible.
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] = {
Sort the curves in order of descreasing priority. Since n is likely to be small, bubble sort is sensible.
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] = {
Sort the vertices, edges, and faces in order of decreasing priority. Since n is likely to be small, bubble sort is sensible.
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;
};
Computing Intersections
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 = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL];
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 = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL];
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 = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL];
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 = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL];
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 = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL];
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 = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL];
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 = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL];
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 = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL];
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 = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL];
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 = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL];
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 = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iPoints: LIST OF Point, tangency: LIST OF BOOL];
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] ¬ CubicPaths.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] ¬ CubicPaths.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;
};
Utilities
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.