GGMultiGravityImpl.mesa
Copyright Ó 1986, 1987, 1989 by Xerox Corporation. All rights reserved.
Contents: Performs hit testing similar to uniGravity. Instead of returning a single nearest feature, we return the N (or fewer) nearest features which are within a given tolerance distance from the test point. The algorithm used is described in [Cyan]<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, December 18, 1989 2:38:04 pm PST
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;
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];
};
};
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;
};
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] ← 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;
};
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.