SVGravityImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Last edited by Bier on February 17, 1987 11:19:15 pm PST
Contents: Routines to snap the skitter to faces, segments, and points in the scene.
DIRECTORY
AtomButtonsTypes, CodeTimer, SVCoordSys, SVSceneToTree, Feedback, IO, SVMatrix3d, SVPreprocess3d, Real, RealFns, Rope, SV2d, SV3d, SVAssembly, SVCaret, SVCastRays, SVGravity, SVInterfaceTypes, SVLines3d, SVModelTypes, SVRay, SVScene, SVSceneTypes, SVSpheres, SVState, SVVector3d;
SVGravityImpl:
CEDAR
PROGRAM
IMPORTS CodeTimer, SVCoordSys, SVSceneToTree, Feedback, SVMatrix3d, SVPreprocess3d, RealFns, SVAssembly, SVCaret, SVCastRays, SVLines3d, SVRay, SVSpheres, SVState, SVVector3d
BEGIN
AlignBag: TYPE = SVInterfaceTypes.AlignBag;
AlignmentLine: TYPE = SVInterfaceTypes.AlignmentLine;
AlignmentPoint: TYPE = REF AlignmentPointObj;
AlignmentPointObj: TYPE = SVInterfaceTypes.AlignmentPointObj;
AlignmentSphere: TYPE = SVInterfaceTypes.AlignmentSphere;
Camera: TYPE = SVSceneTypes.Camera;
Classification: TYPE = SVSceneTypes.Classification;
CSGTree: TYPE = SVSceneTypes.CSGTree;
Edge3d: TYPE = SV3d.Edge3d;
FeatureCycler: TYPE = REF FeatureCyclerObj;
FeatureCyclerObj: TYPE = SVInterfaceTypes.FeatureCyclerObj;
FeatureData: TYPE = REF FeatureDataObj;
FeatureDataObj: TYPE = SVSceneTypes.FeatureDataObj;
FeedbackData: TYPE = AtomButtonsTypes.FeedbackData;
GoodPoint: TYPE = REF GoodPointObj;
GoodPointObj: TYPE = SVInterfaceTypes.GoodPointObj;
GravityType: TYPE = SVInterfaceTypes.GravityType;
Line3d: TYPE = SV3d.Line3d;
MasterObject: TYPE = SVSceneTypes.MasterObject;
Matrix4by4: TYPE = SV3d.Matrix4by4;
NearDistances: TYPE = REF NearDistancesObj;
NearDistancesObj: TYPE = SVGravity.NearDistancesObj;
NearFeatures: TYPE = REF NearFeaturesObj;
NearFeaturesObj: TYPE = SVGravity.NearFeaturesObj;
NearVertexEdgeAndFaces: TYPE = REF NearVertexEdgeAndFacesObj;
NearVertexEdgeAndFacesObj: TYPE = SVInterfaceTypes.NearVertexEdgeAndFacesObj;
Point2d: TYPE = SV2d.Point2d;
Point3d: TYPE = SV3d.Point3d;
PointAndDone: TYPE = SVSceneTypes.PointAndDone;
PointGenerator: TYPE = SVSceneTypes.PointGenerator;
Primitive: TYPE = SVSceneTypes.Primitive;
Ray: TYPE = SVSceneTypes.Ray;
Scene: TYPE = SVSceneTypes.Scene;
SearchDepth: TYPE = SVSceneTypes.SearchDepth;
Shape: TYPE = SVSceneTypes.Shape;
Skitter: TYPE = SVSceneTypes.Skitter;
Slice: TYPE = SVSceneTypes.Slice;
SliceDescriptor: TYPE = SVSceneTypes.SliceDescriptor;
Sphere: TYPE = SV3d.Sphere;
TriggerBag: TYPE = SVInterfaceTypes.TriggerBag;
Vector3d: TYPE = SV3d.Vector3d;
SVData: TYPE = SVInterfaceTypes.SVData;
Problem: PUBLIC SIGNAL [msg: Rope.ROPE] = Feedback.Problem;
maxFeatures: NAT ← 20;
BestPoints: TYPE = REF BestPointsObj;
BestPointsObj:
TYPE =
RECORD [
size: NAT ← 0,
max, min: REAL,
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];
MultiGravityPool: TYPE = REF MultiGravityPoolObj;
MultiGravityPoolObj:
TYPE =
RECORD [
distances: NearDistances,
features: NearFeatures,
bestpoints: BestPoints,
bestcurves: BestPoints,
bestfaces: BestPoints
];
EmptyBag:
PROC [alignBag: AlignBag]
RETURNS [
BOOL] = {
RETURN[
alignBag.slopeLines = NIL AND
alignBag.slopePlanes = NIL AND
alignBag.anchor = NIL];
};
EmptyTriggers:
PROC [triggerBag: TriggerBag]
RETURNS [
BOOL] = {
RETURN[
triggerBag.slices = NIL AND
triggerBag.anchor = NIL
];
};
RayMap:
PUBLIC PROC [cameraPt: Point2d, t:
REAL, alignBag: AlignBag, sceneBag: TriggerBag, svData: SVData, intersections:
BOOL ← FALSE]
RETURNS [surfacePt
World: Point3d, normal
World: Vector3d, feature: FeatureData, hitData:
REF
ANY] = {
gravityType: GravityType ← SVState.GetGravityType[svData];
camera: Camera ← svData.camera;
CodeTimer.StartInt[$RayMap, $Solidviews];
IF SVState.GetGravity[svData]
THEN {
SELECT gravityType
FROM
facesPreferred =>
[surfacePtWorld, normalWorld, feature, hitData] ← FacesPreferred[cameraPt, t, alignBag, sceneBag, svData];
linesPreferred =>
[surfacePtWorld, normalWorld, feature, hitData] ← LinesPreferred[cameraPt, t, alignBag, sceneBag, svData, intersections];
pointsPreferred =>
[surfacePtWorld, normalWorld, feature, hitData] ← PointsPreferred[cameraPt, t, alignBag, sceneBag, svData, intersections];
ENDCASE => ERROR;
}
ELSE {
parallel: BOOL;
[surfacePtWorld, normalWorld, parallel] ← RayMeetsCentralCameraPlane[cameraPt, camera];
feature ← NIL;
hitData ← NIL;
};
CodeTimer.StopInt[$RayMap, $Solidviews];
};
RayMapCycler:
PUBLIC
PROC [cameraPt: Point2d, t:
REAL, alignBag: AlignBag, sceneBag: TriggerBag, svData: SVData, intersections:
BOOL ←
FALSE]
RETURNS [featureCycler: FeatureCycler] = {
gravityType: GravityType ← SVState.GetGravityType[svData];
camera: Camera ← svData.camera;
IF SVState.GetGravity[svData]
THEN {
SELECT gravityType
FROM
facesPreferred =>
featureCycler ← FacesPreferredCycler[cameraPt, t, alignBag, sceneBag, svData];
linesPreferred =>
featureCycler ← LinesPreferredCycler[cameraPt, t, alignBag, sceneBag, svData, intersections];
pointsPreferred =>
featureCycler ← PointsPreferredCycler[cameraPt, t, alignBag, sceneBag, svData, intersections];
ENDCASE => ERROR;
}
ELSE {
featureCycler ← EmptyCycler[cameraPt, camera];
};
};
EmptyCycler:
PROC [cameraPt: Point2d, camera: Camera]
RETURNS [featureCycler: FeatureCycler] = {
featureCycler ←
NEW[FeatureCyclerObj ← [
nearVEF: NIL,
count: 0,
index: -1,
cameraPt: cameraPt,
camera: camera
]];
};
FacesPreferred:
PUBLIC
PROC [cameraPt: Point2d, t:
REAL, alignBag: AlignBag, sceneBag: TriggerBag, svData: SVData]
RETURNS [surfacePt
World: Point3d, normal
World: Vector3d, feature: FeatureData, hitData:
REF
ANY] = {
Find the nearest face hit by the cursor ray. If the ray hits no faces, find the nearest face that passes within t screen units of the ray. Ideally, this would be implemented by a "nearest face to line" routine that would find the nearest edge of a face in the same way that Solidviews finds the nearest endpoint of an edge. Failing this, we can just combine ray-tracing with an edge finder.
nearVEF: NearVertexEdgeAndFaces;
camera: Camera ← svData.camera;
count: NAT;
[nearVEF, count] ← MultiFacesPreferred[cameraPt, t, alignBag, sceneBag, svData];
IF count = 0
THEN {
parallel: BOOL;
[surfacePtWorld, normalWorld, parallel] ← RayMeetsCentralCameraPlane[cameraPt, camera];
hitData ← NIL;
RETURN;
};
SortByDepth[nearVEF];
RETURN PrepareWinner[nearVEF, 0];
};
LinesPreferred:
PUBLIC
PROC [cameraPt: Point2d, t:
REAL, alignBag: AlignBag, sceneBag: TriggerBag, svData: SVData, intersections:
BOOL]
RETURNS [surfacePt
World: Point3d, normal
World: Vector3d, feature: FeatureData, hitData:
REF
ANY] = {
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 the surface normal of the face that owns that edge, whose normal most nearly points toward the eyepoint.
If no lines exist within t, then choose the nearest face hit by the cursor ray, if any.
If still no object is found, use the background plane.
nearVEF: NearVertexEdgeAndFaces;
count: NAT;
camera: Camera ← svData.camera;
[nearVEF, count] ← MultiLinesPreferred[cameraPt, t, alignBag, sceneBag, svData, intersections];
IF count = 0
THEN {
parallel: BOOL;
[surfacePtWorld, normalWorld, parallel] ← RayMeetsCentralCameraPlane[cameraPt, camera];
feature ← NIL;
hitData ← NIL;
RETURN;
};
IF count = 1 THEN RETURN PrepareWinner[nearVEF, 0]
ELSE {
Otherwise, let's do 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 RETURN PrepareWinner[nearVEF, 0];
bestSceneObject ← -1;
RETURN PrepareWinner[nearVEF, 0];
};
};
PointsPreferred:
PUBLIC
PROC [cameraPt: Point2d, t:
REAL, alignBag: AlignBag, sceneBag: TriggerBag, svData: SVData, intersections:
BOOL]
RETURNS [surfacePt
World: Point3d, normal
World: Vector3d, feature: FeatureData, hitData:
REF
ANY] = {
count: NAT;
nearVEF: NearVertexEdgeAndFaces;
[nearVEF, count] ← MultiPointsPreferred[cameraPt, t, alignBag, sceneBag, svData, intersections];
IF count = 0
THEN
{
parallel: BOOL;
camera: Camera ← svData.camera;
[surfacePtWorld, normalWorld, parallel] ← RayMeetsCentralCameraPlane[cameraPt, camera];
feature ← NIL;
hitData ← NIL;
RETURN;
};
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];
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;
};
};
PrepareWinner:
PROC [nearVEF: NearVertexEdgeAndFaces, index:
NAT]
RETURNS [surfacePt
World: Point3d, normal
World: Vector3d, feature: FeatureData, hitData:
REF
ANY] = {
goodPoint: GoodPoint ← nearVEF[index];
surfacePtWorld ← goodPoint.point;
normalWorld ← goodPoint.normal;
feature ← goodPoint.featureData;
hitData ← goodPoint.hitData;
};
FacesPreferredCycler:
PUBLIC
PROC [cameraPt: Point2d, t:
REAL, alignBag: AlignBag, sceneBag: TriggerBag, svData: SVData]
RETURNS [featureCycler: FeatureCycler] = {
Find the nearest face hit by the cursor ray. If the ray hits no faces, find the nearest face that passes within t screen units of the ray. Ideally, this would be implemented by a "nearest face to line" routine that would find the nearest edge of a face in the same way that Solidviews finds the nearest endpoint of an edge. Failing this, we can just combine ray-tracing with an edge finder.
nearVEF: NearVertexEdgeAndFaces;
camera: Camera ← svData.camera;
count: NAT;
[nearVEF, count] ← MultiFacesPreferred[cameraPt, t, alignBag, sceneBag, svData];
IF count = 0 THEN RETURN[EmptyCycler[cameraPt, camera]];
SortByDepth[nearVEF];
featureCycler ←
NEW[FeatureCyclerObj ← [
nearVEF: nearVEF,
count: count,
index: 0,
cameraPt: cameraPt,
camera: camera
]];
};
LinesPreferredCycler:
PUBLIC
PROC [cameraPt: Point2d, t:
REAL, alignBag: AlignBag, sceneBag: TriggerBag, svData: SVData, intersections:
BOOL, maxDimension: [0..2] ← 2]
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 the surface normal of the face that owns that edge, whose normal most nearly points toward the eyepoint.
If no lines exist within t, then choose the nearest face hit by the cursor ray, if any.
If still no object is found, use the background plane.
nearVEF: NearVertexEdgeAndFaces;
count: NAT;
camera: Camera ← svData.camera;
BEGIN
[nearVEF, count] ← MultiLinesPreferred[cameraPt, t, alignBag, sceneBag, svData, intersections, maxDimension];
IF count = 0 THEN RETURN[EmptyCycler[cameraPt, camera]];
IF count = 1 THEN GOTO MakeSimpleCycler
ELSE {
Otherwise, let's do 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: nearVEF,
count: count,
index: 0,
cameraPt: cameraPt,
camera: camera
]];
};
EXITS
MakeSimpleCycler => {
featureCycler ←
NEW[FeatureCyclerObj ← [
nearVEF: nearVEF,
count: count,
index: 0,
cameraPt: cameraPt,
camera: camera
]];
};
END;
};
PointsPreferredCycler:
PUBLIC
PROC [cameraPt: Point2d, t:
REAL, alignBag: AlignBag, sceneBag: TriggerBag, svData: SVData, intersections:
BOOL, maxDimension: [0..2] ← 2]
RETURNS [featureCycler: FeatureCycler] = {
count: NAT;
nearVEF: NearVertexEdgeAndFaces;
camera: Camera ← svData.camera;
BEGIN
[nearVEF, count] ← MultiPointsPreferred[cameraPt, t, alignBag, sceneBag, svData, intersections, maxDimension];
IF count = 0 THEN RETURN[EmptyCycler[cameraPt, camera]];
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: nearVEF,
count: count,
index: -1,-- will be filled in below
cameraPt: cameraPt,
camera: camera
]];
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;
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: nearVEF,
count: count,
index: 0,
cameraPt: cameraPt,
camera: camera
]];
};
END;
};
FirstFeature:
PUBLIC
PROC [featureCycler: FeatureCycler]
RETURNS [surfacePt
World: Point3d, normal
World: Vector3d, feature: FeatureData, hitData:
REF
ANY] = {
RETURN GetFeature[featureCycler, 0];
};
NextFeature:
PUBLIC
PROC [featureCycler: FeatureCycler]
RETURNS [surfacePt
World: Point3d, normal
World: Vector3d, feature: FeatureData, hitData:
REF
ANY] = {
RETURN GetFeature[featureCycler, 1];
};
PreviousFeature:
PUBLIC
PROC [featureCycler: FeatureCycler]
RETURNS [surfacePt
World: Point3d, normal
World: Vector3d, feature: FeatureData, hitData:
REF
ANY] = {
RETURN GetFeature[featureCycler, -1];
};
GetFeature:
PUBLIC
PROC [featureCycler: FeatureCycler, move: [-1..1]]
RETURNS [surfacePt
World: Point3d, normal
World: Vector3d, feature: FeatureData, hitData:
REF
ANY] = {
IF featureCycler.count = 0
THEN {
-- return a backdrop position
parallel: BOOL;
cameraPt: Point2d ← featureCycler.cameraPt;
camera: Camera ← featureCycler.camera;
[surfacePtWorld, normalWorld, parallel] ← RayMeetsCentralCameraPlane[cameraPt, camera];
feature ← NIL;
hitData ← NIL;
}
ELSE {
featureCycler.index ← (featureCycler.index + move + featureCycler.count) MOD featureCycler.count;
[surfacePtWorld, normalWorld, feature, hitData] ← PrepareWinner[featureCycler.nearVEF, featureCycler.index];
};
};
MultiFacesPreferred:
PROC [cameraPt: Point2d, t:
REAL, alignBag: AlignBag, sceneBag: TriggerBag, svData: SVData]
RETURNS [nearVEF: NearVertexEdgeAndFaces, count:
NAT] = {
camera: Camera ← svData.camera;
bestFaces: BestPoints;
[bestFaces, count] ← FacesInNeighborhoodPlus[alignBag, sceneBag, cameraPt, svData, t];
IF count > 0
THEN {
nearVEF ← NEW[NearVertexEdgeAndFacesObj[count]];
FOR i:
NAT
IN [0..count)
DO
nearVEF[i] ← bestFaces[i];
ENDLOOP;
};
};
MultiLinesPreferred:
PUBLIC
PROC [cameraPt: Point2d, t:
REAL, alignBag: AlignBag, sceneBag: TriggerBag, svData: SVData, intersections:
BOOL, maxDimension: [0..2] ← 2]
RETURNS [nearVEF: NearVertexEdgeAndFaces, count:
NAT] = {
Find the nearest line to ray and those lines that are not much farther. If intersections is TRUE, compute the intersections of surfaces that are within the cone whose radius at the screen is innerR. (For now assume intersections is false).
bestVerts, bestEdges, bestFaces: BestPoints;
vertCount, edgeCount, faceCount, veCount: NAT;
IF EmptyBag[alignBag]
AND EmptyTriggers[sceneBag]
THEN
RETURN[NIL, 0];
IF maxDimension >= 2
THEN {
[bestFaces, faceCount] ← FacesInNeighborhoodPlus[alignBag, sceneBag, cameraPt, svData, t];
SortFaces[bestFaces, faceCount];
}
ELSE faceCount ← 0;
[bestEdges, edgeCount] ← EdgesInNeighborhoodPlus[alignBag, sceneBag, cameraPt, svData, t, 0];
SortCurves[bestEdges, edgeCount];
[bestVerts, vertCount] ← VertsInNeighborhoodPlus[NIL, 0, NIL, 0, alignBag, sceneBag, cameraPt, t, svData, FALSE];
SortPoints[bestVerts, vertCount];
veCount ← MIN[vertCount + edgeCount, maxFeatures];
count ← MIN[veCount + faceCount, maxFeatures];
nearVEF ← NEW[NearVertexEdgeAndFacesObj[count]];
MergePointsAndCurves[bestVerts, vertCount, bestEdges, edgeCount, nearVEF, veCount];
MergeVEWithFaces[bestFaces, faceCount, nearVEF, veCount, maxFeatures];
};
MultiPointsPreferred:
PUBLIC
PROC [cameraPt: Point2d, t:
REAL, alignBag: AlignBag, sceneBag: TriggerBag, svData: SVData, intersections:
BOOL, maxDimension: [0..2] ← 2]
RETURNS [nearVEF: NearVertexEdgeAndFaces, count:
NAT] = {
bestVerts, bestEdges, bestFaces: BestPoints;
vertCount, edgeCount, faceCount, veCount: NAT;
innerR: REAL ← t/2.0;
IF EmptyBag[alignBag] AND EmptyTriggers[sceneBag] THEN RETURN[NIL, 0];
IF maxDimension >= 2
THEN {
[bestFaces, faceCount] ← FacesInNeighborhoodPlus[alignBag, sceneBag, cameraPt, svData, t];
SortFaces[bestFaces, faceCount];
}
ELSE faceCount ← 0;
[bestEdges, edgeCount] ← EdgesInNeighborhoodPlus[alignBag, sceneBag, cameraPt, svData, t, innerR];
SortCurves[bestEdges, edgeCount];
[bestVerts, vertCount] ← VertsInNeighborhoodPlus[bestFaces, faceCount, bestEdges, edgeCount, alignBag, sceneBag, cameraPt, t, svData, intersections];
SortPoints[bestVerts, vertCount];
IF vertCount > 0
AND bestVerts[0].dist < innerR
THEN {
count ← vertCount;
nearVEF ← NEW[NearVertexEdgeAndFacesObj[count]];
NearPointsFromPoints[bestVerts, vertCount, nearVEF];
}
ELSE {
veCount ← MIN[vertCount + edgeCount, maxFeatures];
count ← MIN[veCount + faceCount, maxFeatures];
nearVEF ← NEW[NearVertexEdgeAndFacesObj[count]];
MergePointsAndCurves[bestVerts, vertCount, bestEdges, edgeCount, nearVEF, veCount];
MergeVEWithFaces[bestFaces, faceCount, nearVEF, veCount, maxFeatures];
};
};
ResultsFromClassification:
PROC [class: Classification, ray
World: Ray, sceneBag: TriggerBag, searchDepth:
NAT]
RETURNS [surfacePt
World: Point3d, normal
World: Vector3d, feature: FeatureData, hitData:
REF
ANY] = {
primitive: Primitive;
assembly: Slice;
[assembly, primitive] ← SVCastRays.NthAssemblyAndPrimitive[class, searchDepth];
IF class.count > 0
THEN
[surfacePtWorld, normalWorld] ← SVCastRays.NthSurfacePointAndNormal[class, rayWorld, searchDepth];
feature ← FindFeature[assembly, sceneBag];
hitData ← SVCastRays.NthHitData[class, searchDepth];
};
FaceResultsFromClassification:
PROC [class: Classification, ray
Shape: Ray]
RETURNS [theseIFrames:
LIST
OF Matrix4by4, thisTangency:
LIST
OF
BOOL] = {
surfacePtWorld: Point3d;
normalWorld: Vector3d;
thisMat: Matrix4by4;
theseIFrames ← NIL;
thisTangency ← NIL;
FOR i:
NAT
IN [1..class.count]
DO
[surfacePtWorld, normalWorld] ← SVCastRays.NthSurfacePointAndNormal[class, rayShape, i];
thisMat ← SVMatrix3d.MakeHorizontalMatFromZAxis[normalWorld, surfacePtWorld];
theseIFrames ← CONS[thisMat, theseIFrames];
thisTangency ← CONS[FALSE, thisTangency];
ENDLOOP;
};
FacesInNeighborhoodPlus:
PROC [alignBag: AlignBag, sceneBag: TriggerBag, cameraPt: Point2d, svData: SVData, t:
REAL]
RETURNS [h: BestPoints, count:
NAT] = {
CountStillFaces:
PROC [class: Classification]
RETURNS [stillCount:
NAT ← 0] = {
FOR i:
NAT
IN [1..class.count]
DO
IF class.stills[i] THEN stillCount ← stillCount + 1;
ENDLOOP;
};
goodPoint: GoodPoint ← NEW[GoodPointObj];
camera: Camera ← svData.camera;
class: Classification;
rayWorld: Ray;
rayWorld ← GetWorldRayFromCameraPoint[cameraPt, camera]; -- from pool
Handle the Slices
class ← SingleRay[rayWorld, cameraPt, sceneBag, camera, TRUE, NIL]; -- class from pool
count ← CountStillFaces[class];
h ← BestFacesFromPool[svData];
FOR i:
NAT
IN [1..class.count]
DO
IF class.stills[i]
THEN {
[goodPoint.point, goodPoint.normal, goodPoint.featureData, goodPoint.hitData] ←
ResultsFromClassification[class, rayWorld, sceneBag, i];
goodPoint.dist ← 0.0;
goodPoint.dimension ← 2;
MergeFace[goodPoint, h];
};
ENDLOOP;
SVCastRays.ReturnClassToPool[class];
Handle the Alignment Objects
BEGIN
points: ARRAY [1..2] OF Point3d;
normals: ARRAY [1..2] OF Vector3d;
hitCount: [0..2];
tangent: BOOL;
FOR list:
LIST
OF FeatureData ← alignBag.spheres, list.rest
UNTIL list =
NIL
DO
alignmentSphere: AlignmentSphere ← NARROW[list.first.shape];
sphere: Sphere ← alignmentSphere.sphere;
[points, normals, hitCount, tangent] ← SVSpheres.SphereMeetsRay[sphere, rayWorld];
FOR i:
NAT
IN [1..hitCount]
DO
goodPoint.point ← points[i];
goodPoint.normal ← normals[i];
goodPoint.featureData ← list.first;
goodPoint.hitData ← NIL;
goodPoint.dist ← 0.0;
goodPoint.dimension ← 2;
MergeFace[goodPoint, h];
count ← count + 1;
ENDLOOP;
ENDLOOP;
END;
SVRay.ReturnRayToPool[rayWorld];
};
EdgesInNeighborhoodPlus:
PROC [alignBag: AlignBag, sceneBag: TriggerBag, q: Point2d, svData: SVData, t:
REAL, innerR:
REAL]
RETURNS [h: BestPoints, curveCount:
NAT] = {
ProcessSlice:
PROC [sliceD: SliceDescriptor, thisCurve: GoodPoint, featureData: FeatureData] = {
success: BOOL;
[thisCurve.dist, thisCurve.point, thisCurve.normal, thisCurve.hitData, success] ← SVAssembly.ClosestSegmentToLine[sliceD, q, line3d, t, camera];
IF success
AND thisCurve.dist < t
THEN {
thisCurve.featureData ← featureData;
thisCurve.dimension ← 1;
dTol ← MergeCurve[thisCurve, h];
};
};
ProcessLine:
PROC [line: Line3d, thisCurve: GoodPoint, featureData: FeatureData] = {
thisCurve.dist ← SVLines3d.DistanceLineToLine[line, line3d];
IF thisCurve.dist < t
THEN {
pAlignment, pRay: Point3d;
parallel: BOOL;
thisCurve.featureData ← featureData;
[pAlignment, pRay, parallel] ← SVLines3d.NearLinePoints[line, line3d];
thisCurve.point ← pAlignment;
thisCurve.normal ← SVVector3d.Sub[pRay, pAlignment];
thisCurve.hitData ← NIL;
dTol ← MergeCurve[thisCurve, h];
}
};
line: Line3d;
circle: Circle;
sliceD: SliceDescriptor;
featureData: FeatureData;
added: BOOL ← FALSE;
thisCurve: GoodPoint ← NEW[GoodPointObj];
dTol: REAL ← t;
camera: Camera ← svData.camera;
line3d: Line3d;
rayWorld: Ray ← GetWorldRayFromCameraPoint[q, camera]; -- from pool
h ← BestCurvesFromPool[svData, t, innerR];
line3d ← LineFromRay[rayWorld];
Align Bag
FOR
slopeLines:
LIST
OF FeatureData ← alignBag.slopeLines, slopeLines.rest
UNTIL slopeLines =
NIL
DO
featureData ← slopeLines.first;
line ← NARROW[featureData.shape, AlignmentLine].line;
ProcessLine[line, thisCurve, featureData];
ENDLOOP;
Scene Bag.
FOR
slices:
LIST
OF FeatureData ← sceneBag.slices, slices.rest
UNTIL slices =
NIL
DO
featureData ← slices.first;
sliceD ← NARROW[featureData.shape, SliceDescriptor];
ProcessSlice[sliceD, thisCurve, featureData];
ENDLOOP;
curveCount ← h.size;
IF h.overflow
THEN {
CodeTimer.StartInt[$CurveOverflow, $Solidviews];
CodeTimer.StopInt[$CurveOverflow, $Solidviews];
};
SVRay.ReturnRayToPool[rayWorld];
}; -- end CurvesInNeighborhoodPlus
VertsInNeighborhoodPlus:
PROC [bestFaces: BestPoints, faceCount:
NAT, bestCurves: BestPoints, curveCount:
NAT, alignBag: AlignBag, sceneBag: TriggerBag, q: Point2d, t:
REAL, svData: SVData, intersections:
BOOL]
RETURNS [h: BestPoints, pointCount:
NAT] = {
thisPoint: GoodPoint;
ProcessPoint:
PROC [thisPoint: GoodPoint, featureData: FeatureData] = {
-- used for the anchor
dSquared: REAL;
dTolSquared: REAL ← dTol*dTol;
dSquared ← SVLines3d.Distance2PointToLine[thisPoint.point, line3d];
thisPoint.hitData ← NIL;
IF dSquared < dTolSquared
THEN {
anchor: Skitter ← NARROW[featureData.shape];
thisPoint.dist ← RealFns.SqRt[dSquared];
thisPoint.normal ← SVMatrix3d.ZAxisOfMatrix[SVCaret.GetPosition[anchor]];
thisPoint.featureData ← featureData;
dTol ← MergePoint[thisPoint, h];
};
};
ProcessSlice:
PROC [sliceD: SliceDescriptor, thisPoint: GoodPoint, featureData: FeatureData] = {
[thisPoint.dist, thisPoint.point, thisPoint.normal, thisPoint.hitData, success] ← SVAssembly.ClosestPointToLine[sliceD, q, line3d, dTol, camera, TRUE];
IF success
AND thisPoint.dist < dTol
THEN {
thisPoint.featureData ← featureData;
thisPoint.dimension ← 0;
dTol ← MergePoint[thisPoint, h];
};
};
sliceD: SliceDescriptor;
featureData: FeatureData;
success: BOOL ← FALSE;
dTol: REAL ← t;
midpoints: BOOL ← SVState.GetMidpoints[svData];
camera: Camera ← svData.camera;
line3d: Line3d;
rayWorld: Ray ← GetWorldRayFromCameraPoint[q, camera]; -- from pool
thisPoint ← NEW[GoodPointObj];
h ← BestPointsFromPool[svData, t];
line3d ← LineFromRay[rayWorld];
IF intersections
THEN
dTol ← FindIntersections[bestFaces, faceCount, bestCurves, curveCount, thisPoint, line3d, dTol, h];
IF intersections AND midpoints THEN
dTol ← FindMidpoints[bestCurves, curveCount, thisPoint, q, dTol, h];
FOR
slices:
LIST
OF FeatureData ← sceneBag.slices, slices.rest
UNTIL slices =
NIL
DO
featureData ← slices.first;
sliceD ← NARROW[featureData.shape, SliceDescriptor];
ProcessSlice[sliceD, thisPoint, featureData];
ENDLOOP;
featureData ← alignBag.anchor;
IF featureData #
NIL
THEN {
anchor: Skitter ← NARROW[featureData.shape];
IF NOT SVCaret.Exists[anchor] THEN ERROR;
thisPoint.point ← SVMatrix3d.OriginOfMatrix[SVCaret.GetPosition[anchor]];
ProcessPoint[thisPoint, featureData];
};
pointCount ← h.size;
IF h.overflow
THEN {
CodeTimer.StartInt[$PointOverflow, $Solidviews];
CodeTimer.StopInt[$PointOverflow, $Solidviews];
};
SVRay.ReturnRayToPool[rayWorld];
};
FindIntersections:
PROC [bestFaces: BestPoints, faceCount:
NAT, bestCurves: BestPoints, curveCount:
NAT, thisPoint: GoodPoint, line: Line3d, tolerance:
REAL, h: BestPoints]
RETURNS [dTol:
REAL] = {
curveI, curveJ, faceJ: GoodPoint;
theseIFrames: LIST OF Matrix4by4;
thisTangency, tangentList: LIST OF BOOL;
success: BOOL;
dTol ← tolerance;
Find Curve-Curve intersections.
FOR i:
NAT
IN [0..curveCount)
DO
curveI ← bestCurves[i];
FOR j:
NAT
IN [i+1..curveCount)
DO
curveJ ← bestCurves[j];
[theseIFrames, thisTangency] ← CurveMeetsCurve[curveI, curveJ];
tangentList ← thisTangency;
Check each intersection against the test line.
FOR list:
LIST
OF Matrix4by4 ← theseIFrames, list.rest
UNTIL list =
NIL
DO
thisPoint.point ← SVMatrix3d.OriginOfMatrix[list.first];
thisPoint.normal ← SVMatrix3d.ZAxisOfMatrix[list.first];
thisPoint.dist ← SVLines3d.DistancePointToLine[thisPoint.point, line];
success ← thisPoint.dist <= tolerance;
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;
IF curveI.featureData.type = slice
THEN {
thisPoint.hitData ← curveI.hitData;
}
ELSE
IF curveJ.featureData.type = slice
THEN {
thisPoint.hitData ← curveJ.hitData;
}
ELSE thisPoint.hitData ← NIL;
dTol ← MergePoint[thisPoint, h];
};
tangentList ← tangentList.rest;
ENDLOOP;
ENDLOOP;
ENDLOOP;
Find Curve-Face intersections.
FOR i:
NAT
IN [0..curveCount)
DO
curveI ← bestCurves[i];
FOR j:
NAT
IN [0..faceCount)
DO
faceJ ← bestFaces[j];
[theseIFrames, thisTangency] ← CurveMeetsFace[curveI, faceJ];
tangentList ← thisTangency;
Check each intersection against the test line.
FOR list:
LIST
OF Matrix4by4 ← theseIFrames, list.rest
UNTIL list =
NIL
DO
thisPoint.point ← SVMatrix3d.OriginOfMatrix[list.first];
thisPoint.normal ← SVMatrix3d.ZAxisOfMatrix[list.first];
thisPoint.dist ← SVLines3d.DistancePointToLine[thisPoint.point, line];
success ← thisPoint.dist <= tolerance;
IF success
THEN {
featureData: FeatureData ← NEW[FeatureDataObj];
alignmentPoint: AlignmentPoint ←
NEW[AlignmentPointObj ← [
point: thisPoint.point,
tangent: tangentList.first,
curve1: curveI.featureData,
curve2: faceJ.featureData]];
featureData.type ← intersectionPoint;
featureData.shape ← alignmentPoint;
thisPoint.featureData ← featureData;
IF curveI.featureData.type = slice
THEN {
thisPoint.hitData ← curveI.hitData;
}
ELSE
IF faceJ.featureData.type = slice
THEN {
thisPoint.hitData ← faceJ.hitData;
}
ELSE thisPoint.hitData ← NIL;
dTol ← MergePoint[thisPoint, h];
};
tangentList ← tangentList.rest;
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
MergePoint:
PROC [thisPoint: GoodPoint, h: BestPoints]
RETURNS [dTol:
REAL] = {
d: REAL ← thisPoint.dist;
n: NAT = maxFeatures;
BEGIN
SELECT
TRUE
FROM
h.size < n => GOTO Add;
h.size = n AND d <= h.dTol => GOTO ReplaceOrOverflow;
h.size = n AND d > h.dTol => GOTO Toss; -- the caller is not taking our hints and is passing us trash
ENDCASE => SIGNAL Problem[msg: "Impossible case."];
EXITS
Add => {
h[h.size]^ ← thisPoint^;
h.size ← h.size + 1;
h.min ← MIN[h.min, d];
dTol ← h.dTol ← h.min+h.s;
};
ReplaceOrOverflow => {
iWorst: NAT;
worstDist: REAL ← 0.0;
Replace the worst element with the new one if the new is better.
iWorst ← 0; worstDist ← 0.0;
FOR i:
NAT
IN [0..maxFeatures-1]
DO
IF h[i].dist > worstDist THEN {iWorst ← i; worstDist ← h[i].dist};
ENDLOOP;
IF d < worstDist
THEN {
-- do the replace
h[iWorst].dist ← d;
h[iWorst]^ ← thisPoint^;
h.bestTossed ← MIN[h.bestTossed, worstDist];
h.min ← MIN[h.min, d];
dTol ← h.dTol ← h.min+h.s;
h.overflow ← h.bestTossed <= dTol;
}
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;
};
MergeCurve:
PROC [thisPoint: GoodPoint, h: BestPoints]
RETURNS [dTol:
REAL] = {
d: REAL ← thisPoint.dist;
n: NAT = maxFeatures;
BEGIN
SELECT
TRUE
FROM
h.size < n => GOTO Add;
h.size = n AND d <= h.dTol => GOTO ReplaceOrOverflow;
h.size = n AND d > h.dTol => GOTO Toss; -- the caller is not taking our hints and is passing us trash
ENDCASE => SIGNAL Problem[msg: "Impossible case."];
EXITS
Add => {
h[h.size]^ ← thisPoint^;
h.size ← h.size + 1;
h.min ← MIN[h.min, d];
dTol ← h.dTol ← MAX[h.min+h.s, h.innerR];
};
ReplaceOrOverflow => {
iWorst: NAT;
worstDist: REAL ← 0.0;
Replace the worst element with the new one if the new is better.
iWorst ← 0; worstDist ← 0.0;
FOR i:
NAT
IN [0..maxFeatures-1]
DO
IF h[i].dist > worstDist THEN {iWorst ← i; worstDist ← h[i].dist};
ENDLOOP;
IF d < worstDist
THEN {
-- do the replace
h[iWorst].dist ← d;
h[iWorst]^ ← thisPoint^;
h.bestTossed ← MIN[h.bestTossed, worstDist];
h.min ← MIN[h.min, d];
dTol ← h.dTol ← MAX[h.min+h.s, h.innerR];
h.overflow ← h.bestTossed <= dTol;
}
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;
};
MergeFace:
PROC [thisPoint: GoodPoint, h: BestPoints] = {
Faces are handed to MergeFace in order. Use the size field of h to remember where to put the next face.
n: NAT = maxFeatures;
IF h.size >= n THEN RETURN;
h[h.size]^ ← thisPoint^;
h.size ← h.size + 1;
};
NearPointsFromPoints:
PROC [bestPoints: BestPoints, pointCount:
NAT, nearVEF: NearVertexEdgeAndFaces] = {
FOR i:
NAT
IN [0..pointCount-1]
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 ← curveIndex ← 0;
FOR i:
NAT
IN [0..count-1]
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;
};
MergeVEWithFaces:
PROC [bestFaces: BestPoints, faceCount:
NAT, nearVEF: NearVertexEdgeAndFaces, oldCount, maxCount:
NAT] = {
Add the faces onto the end.
faceIndex, totalCount: NAT;
totalCount ← MIN[oldCount + faceCount, maxCount];
faceIndex ← 0;
FOR i:
NAT
IN [oldCount..totalCount-1]
DO
nearVEF[i] ← bestFaces[faceIndex];
faceIndex ← faceIndex + 1;
ENDLOOP;
};
Computing Intersections
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 ← SVAssembly.HitDataAsSimpleCurve[sliceD.slice, hitData];
IF simpleCurve =
NIL
THEN {
simpleCurve ← sliceD;
class ← 3;
RETURN;
};
};
slopeLine => {
class ← 1;
simpleCurve ← NARROW[feature.shape, AlignmentLine].line;
RETURN;
};
ENDCASE => {class ← 0; simpleCurve ← NIL; RETURN};
WITH simpleCurve
SELECT
FROM
edge: Edge3d => class ← 2;
ENDCASE => ERROR;
};
ClassifyFace:
PROC [face: GoodPoint]
RETURNS [class:
NAT, simpleFace:
REF
ANY] = {
feature: FeatureData ← face.featureData;
WITH feature.shape
SELECT
FROM
sliceD: SliceDescriptor => {simpleFace ← sliceD; class ← 2;};
alignmentSphere: AlignmentSphere => {simpleFace ← alignmentSphere.sphere; class ← 3;};
ENDCASE => ERROR;
};
CurveMeetsCurve:
PROC [c1, c2: GoodPoint]
RETURNS [iFrames:
LIST
OF Matrix4by4, tangency:
LIST
OF
BOOL] = {
typeOfCurve1, typeOfCurve2: NAT;
simpleCurve1, simpleCurve2: REF ANY;
[typeOfCurve1, simpleCurve1] ← ClassifyCurve[c1];
[typeOfCurve2, simpleCurve2] ← ClassifyCurve[c2];
IF typeOfCurve1 >= typeOfCurve2
THEN
[iFrames, tangency] ← ComputeIntersection[typeOfCurve1][typeOfCurve2][simpleCurve1, simpleCurve2]
ELSE
[iFrames, tangency] ← ComputeIntersection[typeOfCurve2][typeOfCurve1][simpleCurve2, simpleCurve1]
};
CurveMeetsFace:
PROC [c, f: GoodPoint]
RETURNS [iFrames:
LIST
OF Matrix4by4, tangency:
LIST
OF
BOOL] = {
typeOfCurve, typeOfFace: NAT;
simpleCurve, simpleFace: REF ANY;
[typeOfCurve, simpleCurve] ← ClassifyCurve[c];
IF typeOfCurve > 1 THEN RETURN;
[typeOfFace, simpleFace] ← ClassifyFace[f];
[iFrames, tangency] ← ComputeFaceIntersection[typeOfCurve][typeOfFace][simpleCurve, simpleFace];
};
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iFrames: LIST OF Matrix4by4, tangency: LIST OF BOOL];
ComputeIntersection:
ARRAY [0..3]
OF
ARRAY [0..3]
OF IntersectionProc = [
0) NoOp 1) Line 2) Edge 3) Slice
[NoOpI, NIL, NIL, NIL], -- 0) NoOp
[NoOpI, LinLinI, NIL, NIL], -- 1) Line
[NoOpI, EdgLinI, EdgEdgI, NIL], -- 2) Edge
[NoOpI, SlcLinI, NoOpI, NoOpI] -- 3) Slice
];
ComputeFaceIntersection:
ARRAY [0..1]
OF
ARRAY [0..3]
OF IntersectionProc = [
0) NoOp 1) Polygon 2) Slice 3) Sphere
[NoOpI, NoOpI, NoOpI, NoOpI], -- 0) NoOp
[NoOpI, NoOpI, LinSlcFI, LinSphFI] -- 1) Line
];
NoOpI: IntersectionProc = {
iFrames ← NIL;
tangency ← NIL;
};
LinSlcFI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iFrames: LIST OF Matrix4by4, tangency: LIST OF BOOL];
line: Line3d ← NARROW[c1];
sliceD: SliceDescriptor ← NARROW[c2];
slice: Slice ← sliceD.slice;
shape: Shape ← NARROW[slice.shape];
worldShape: Matrix4by4 ← SVCoordSys.FindWorldInTermsOf[shape.coordSys];
ray: Ray ← SVRay.GetRayFromPool[];
localRay: Ray;
class: Classification;
SVRay.StuffWorldOnlyRay[ray, line.base, line.direction];
localRay ← SVRay.TransformRay[ray, worldShape];
SVRay.ReturnRayToPool[ray];
class ← SVAssembly.RayCastNoBBoxes[localRay, sliceD, slice.prim, FALSE];
[iFrames, tangency] ← FaceResultsFromClassification[class, localRay];
SVRay.ReturnRayToPool[localRay];
SVCastRays.ReturnClassToPool[class];
};
LinSphFI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iFrames: LIST OF Matrix4by4, tangency: LIST OF BOOL];
line: Line3d ← NARROW[c1];
sphere: Sphere ← NARROW[c2];
points: ARRAY [1..2] OF Point3d;
hitCount: [0..2];
tangent: BOOL ← FALSE;
normal: Vector3d;
[points, hitCount, tangent] ← SVSpheres.SphereMeetsLine[sphere, line];
FOR i:
NAT
IN [1..hitCount]
DO
normal ← SVVector3d.Sub[points[i], sphere.center];
iFrames ← CONS[SVMatrix3d.MakeHorizontalMatFromZAxis[normal, points[i]], iFrames];
tangency ← CONS[tangent, tangency];
ENDLOOP;
};
LinLinI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iFrames: LIST OF Matrix4by4, tangency: LIST OF BOOL];
l1: Line3d ← NARROW[c1];
l2: Line3d ← NARROW[c2];
p1, p2: Point3d;
parallel: BOOL;
[p1, p2, parallel] ← SVLines3d.NearLinePoints[l1, l2];
IF parallel THEN GOTO NoIntersection
ELSE
IF AlmostEqualPoints[p1, p2]
THEN {
normal: Vector3d ← SVVector3d.Normalize[SVVector3d.CrossProduct[l1.direction, l2.direction]];
mat: Matrix4by4 ← SVMatrix3d.MakeHorizontalMatFromZAxis[normal, p1];
iFrames ← LIST[mat]; tangency ← LIST[FALSE];}
ELSE GOTO NoIntersection;
EXITS
NoIntersection => {iFrames ← NIL; tangency ← NIL};
};
AlmostEqualPoints:
PROC [p1, p2: Point3d]
RETURNS [
BOOL] = {
epsilon: REAL = 1.0E-6;
RETURN[SVVector3d.DistanceSquared[p1, p2] < epsilon];
};
EdgLinI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iFrames: LIST OF SVMatrix3d, tangency: LIST OF BOOL];
edge: Edge3d ← NARROW[c1];
line: Line3d ← NARROW[c2];
edgePoint: Point3d;
distance: REAL;
epsilon: REAL = 1.0E-3;
[distance, edgePoint] ← SVLines3d.DistanceAndPointLineToEdge[line, edge];
IF distance < epsilon
THEN {
normal: Vector3d ← SVVector3d.Normalize[SVVector3d.CrossProduct[edge.line.direction, line.direction]];
mat: Matrix4by4 ← SVMatrix3d.MakeHorizontalMatFromZAxis[normal, edgePoint];
iFrames ← LIST[mat]; tangency ← LIST[FALSE]}
ELSE {iFrames ← NIL; tangency ← NIL};
};
EdgEdgI: IntersectionProc = {
IntersectionProc: TYPE = PROC [c1, c2: REF ANY] RETURNS [iFrames: LIST OF SVMatrix3d, tangency: LIST OF BOOL];
e1: Edge3d ← NARROW[c1];
e2: Edge3d ← NARROW[c2];
iFrames ← NIL; tangency ← NIL;
};
SlcLinI: IntersectionProc = {
sliceD: SliceDescriptor ← NARROW[c1];
line: Line ← NARROW[c2];
[iPoints, ----] ← SVAssembly.LineIntersection[sliceD, line];
FOR list: LIST OF Point3d ← iPoints, list.rest UNTIL list = NIL DO
tangency ← CONS[FALSE, tangency];
ENDLOOP;
iFrames ← NIL; tangency ← NIL;
};
Utilities
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: GoodPointObj;
FOR i:
NAT
IN [0..pointCount-2]
DO
FOR j:
NAT
IN [1..pointCount-i-1]
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: GoodPointObj;
FOR i:
NAT
IN [0..curveCount-2]
DO
FOR j:
NAT
IN [1..curveCount-i-1]
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: BestPoints, faceCount:
NAT] = {
};
PointsOrSurfaces: PROC [cameraPt: Point2d, t: REAL, sceneBag: TriggerBag, camera: Camera, searchDepth: SearchDepth, gravityType: GravityType] RETURNS [surfacePtWorld: Point3d, normalWorld: Vector3d, feature: FeatureData, hitData: REF ANY] = {
pointsPtWorld: Point3d;
pointsNormalWorld: Vector3d;
pointsFeature: FeatureData;
parallel: BOOL;
pointsHitData: REF ANY;
rayWorld: Ray ← GetWorldRayFromCameraPoint[cameraPt, camera]; -- from pool
[surfacePtWorld, normalWorld, feature, hitData] ← RayAtSurfaces[rayWorld, cameraPt, t, sceneBag, camera, searchDepth];
[pointsPtWorld, pointsNormalWorld, pointsFeature, pointsHitData] ← RayAtPoints[rayWorld, cameraPt, t, sceneBag, camera, gravityType];
IF pointsFeature # NIL AND WithinTolerance[pointsPtWorld, rayWorld, t] THEN {
surfacePtWorld ← pointsPtWorld;
IF pointsFeature # feature THEN {
normalWorld ← pointsNormalWorld;
feature ← pointsFeature;
};
hitData ← pointsHitData;
}
ELSE IF feature # NIL THEN {
}
ELSE {
[surfacePtWorld, normalWorld, parallel] ← RayMeetsCentralCameraPlane[cameraPt, camera];
hitData ← NIL;
};
SVRay.ReturnRayToPool[rayWorld];
};
LineFromRay:
PROC [ray: Ray]
RETURNS [line: Line3d] = {
basePt: Point3d;
direction: Vector3d;
[basePt, direction] ← SVRay.GetWorldRay[ray];
line ← SVLines3d.LineFromPointAndVector[basePt, direction];
};
WithinTolerance:
PROC [point: Point3d, ray
World: Ray, t:
REAL]
RETURNS [
BOOL] = {
line: Line3d;
dist: REAL;
line ← LineFromRay[rayWorld];
dist ← SVLines3d.DistancePointToLine[point, line];
RETURN[dist <= t];
};
GetWorldRayFromCameraPoint:
PROC [cameraPt: Point2d, camera: Camera]
RETURNS [ray
World: Ray] = {
rayCamera: Ray;
cameraWorld: Matrix4by4 ← SVCoordSys.WRTWorld[camera.coordSys];
rayCamera ← SVRay.GetRayFromPool[]; -- allocates ray from pool
SVRay.StuffCameraRay[rayCamera, cameraPt, camera];
rayWorld ← SVRay.TransformRayToWorld[rayCamera, cameraWorld]; -- allocates ray from pool
SVRay.ReturnRayToPool[rayCamera];
};
FindFeature:
PROC [assembly: Slice, sceneBag: TriggerBag]
RETURNS [feature: FeatureData] = {
sliceD: SliceDescriptor;
IF assembly = NIL THEN RETURN[NIL];
FOR list:
LIST
OF FeatureData ← sceneBag.slices, list.rest
UNTIL list =
NIL
DO
sliceD ← NARROW[list.first.shape];
IF sliceD.slice = assembly THEN RETURN[list.first];
ENDLOOP;
RETURN[NIL];
};
AssemblyAndPrimitiveAtSearchDepth:
PROC [class: Classification, searchDepth: SearchDepth, root: Slice]
RETURNS [assembly: Slice, primitive: Primitive] = {
SELECT searchDepth FROM
first => [assembly, primitive] ← SVCastRays.NthAssemblyAndPrimitive[class, 1];
lastOfFirst => [assembly, primitive] ← SVCastRays.NthAssemblyAndPrimitive[class, 1];
last => [assembly, primitive] ← SVCastRays.NthAssemblyAndPrimitive[class, class.count];
lastOfLevel1 => [assembly, primitive] ← SVCastRays.LastTopLevelAssemAndPrim[class, root];
ENDCASE => ERROR;
};
SurfacePointAndNormalAtSearchDepth:
PROC [class: Classification, ray
World: Ray, searchDepth: SearchDepth, root: Slice]
RETURNS [surfacePt
World: Point3d, normal
World: Vector3d] = {
SELECT searchDepth FROM
first =>
[surfacePtWorld, normalWorld] ← SVCastRays.NthSurfacePointAndNormal[class, rayWorld, 1];
lastOfFirst =>
[surfacePtWorld, normalWorld] ← SVCastRays.LastOfFirstPointAndNormal[class, rayWorld];
last =>
IF class.count = 0 THEN ERROR
ELSE [surfacePtWorld, normalWorld] ← SVCastRays.NthSurfacePointAndNormal[class, rayWorld, class.count];
lastOfLevel1 =>
[surfacePtWorld, normalWorld] ← SVCastRays.LastTopLevelPointAndNormal[class, rayWorld, root];
ENDCASE => ERROR;
};
HitDataAtSearchDepth:
PROC [class: Classification, searchDepth: SearchDepth, root: Slice]
RETURNS [hitData:
REF
ANY] = {
SELECT searchDepth FROM
first =>
hitData ← SVCastRays.NthHitData[class, 1];
lastOfFirst =>
hitData ← SVCastRays.LastOfFirstHitData[class];
last =>
IF class.count = 0 THEN ERROR
ELSE hitData ← SVCastRays.NthHitData[class, class.count];
lastOfLevel1 =>
hitData ← SVCastRays.LastTopLevelHitData[class, root];
ENDCASE => ERROR;
};
SingleRay:
PUBLIC
PROC [rayWorld: Ray, cameraPt: Point2d, sceneBag: TriggerBag, camera: Camera, consolidate:
BOOL ←
TRUE, feedback: FeedbackData, makeStream:
BOOL ←
FALSE]
RETURNS [class: Classification] = {
tree: CSGTree ← sceneBag.tree;
topNode: REF ANY;
IF tree =
NIL
THEN {
class ← SVCastRays.GetClassFromPool[];
SVCastRays.MakeClassAMiss[class];
RETURN;
};
IF tree.outOfDate
THEN {
tree ← SVSceneToTree.AssemblyToTree[sceneBag.scene.assembly, sceneBag.scene, camera, tree, sceneBag.ignoreMoving];
[] ← SVPreprocess3d.PreprocessForInteraction[tree, camera];
tree.outOfDate ← FALSE;
};
topNode ← tree.son;
class ← SVCastRays.RayCast[cameraPt, rayWorld, topNode, consolidate, feedback, makeStream, 0];
}; -- end of SingleRay
RayAtPoints:
PROC [ray: Ray, cameraPt: Point2d, t:
REAL, sceneBag: TriggerBag, camera: Camera, gravityType: GravityType]
RETURNS [bestPoint: Point3d, bestNormal: Vector3d, bestFeature: FeatureData, bestHitData:
REF
ANY] = {
line3d: Line3d;
bestDist, thisDist: REAL;
pointWorld: Point3d;
normalWorld: Vector3d;
feature: FeatureData;
sliceD: SliceDescriptor;
hitData: REF ANY;
success: BOOL;
scene: Scene ← sceneBag.scene;
line3d ← LineFromRay[ray];
bestDist ← Real.LargestNumber;
bestFeature ← NIL;
IF gravityType = linesPreferred
THEN {
FOR list:
LIST
OF FeatureData ← sceneBag.slices, list.rest
UNTIL list =
NIL
DO
feature ← list.first;
sliceD ← NARROW[feature.shape];
[thisDist, pointWorld, normalWorld, hitData, success] ← SVAssembly.ClosestSegmentToLine[sliceD, cameraPt, line3d, t, camera];
IF success
AND thisDist < bestDist
THEN {
bestDist ← thisDist;
bestPoint ← pointWorld;
bestNormal ← normalWorld;
bestHitData ← hitData;
bestFeature ← feature;
};
ENDLOOP;
};
FOR list:
LIST
OF FeatureData ← sceneBag.slices, list.rest
UNTIL list =
NIL
DO
feature ← list.first;
sliceD ← NARROW[feature.shape];
[thisDist, pointWorld, normalWorld, hitData, success] ← SVAssembly.ClosestPointToLine[sliceD, cameraPt, line3d, t, camera, TRUE];
IF success
AND thisDist < bestDist
THEN {
bestDist ← thisDist;
bestPoint ← pointWorld;
bestNormal ← normalWorld;
bestHitData ← hitData;
bestFeature ← feature;
};
ENDLOOP;
bestNormal ← SVMatrix3d.ZAxisOfMatrix[SVCoordSys.WRTWorld[camera.coordSys]];
};
RayMeetsCameraPlane:
PROC [cameraPt: Point2d, depth:
REAL, camera: Camera]
RETURNS [planePt
Camera: Point3d, parallel:
BOOL] = {
rayWorld: Ray;
worldCamera: Matrix4by4;
planePtWorld: Point3d;
rayWorld ← SVRay.GetRayFromPool[];
SVRay.StuffWorldRayFromCamera[rayWorld, cameraPt, camera];
[planePtWorld, parallel] ← SVCastRays.RayMeetsPlaneOfCoordSystem[camera.coordSys, rayWorld, 3, depth];
worldCamera ← SVCoordSys.FindAInTermsOfB[SVCoordSys.Parent[camera.coordSys], camera.coordSys];
planePtCamera ← SVMatrix3d.Update[planePtWorld, worldCamera];
SVRay.ReturnRayToPool[rayWorld];
};
RayMeetsCentralCameraPlane:
PROC [cameraPt: Point2d, camera: Camera]
RETURNS [point
World: Point3d, normal
World: Vector3d, parallel:
BOOL] = {
worldCAMERA: Matrix4by4 ← SVCoordSys.FindWorldInTermsOf[camera.coordSys];
originCAMERA: Point3d ← SVMatrix3d.OriginOfMatrix[worldCAMERA];
depth: REAL ← originCAMERA[3];
rayWorld: Ray;
rayWorld ← SVRay.GetRayFromPool[];
SVRay.StuffWorldRayFromCamera[rayWorld, cameraPt, camera];
[pointWorld, parallel] ← SVCastRays.RayMeetsPlaneOfCoordSystem[camera.coordSys, rayWorld, 3, depth];
normalWorld ← SVMatrix3d.ZAxisOfMatrix[SVCoordSys.WRTWorld[camera.coordSys]];
SVRay.ReturnRayToPool[rayWorld];
};
NewGravityPool:
PUBLIC
PROC []
RETURNS [gravityPool:
REF
ANY] = {
pool: MultiGravityPool ← NEW[MultiGravityPoolObj];
pool.distances ← NEW[NearDistancesObj[maxFeatures]];
pool.features ← NEW[NearFeaturesObj[maxFeatures]];
pool.bestpoints ← NEW[BestPointsObj[maxFeatures]];
pool.bestcurves ← NEW[BestPointsObj[maxFeatures]];
pool.bestfaces ← NEW[BestPointsObj[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];
};
BestFacesFromPool:
PROC [svData: SVData]
RETURNS [h: BestPoints] = {
h ← NARROW[svData.gravityPool, MultiGravityPool].bestfaces;
h.size ← 0;
h.overflow ← FALSE;
FOR i:
NAT
IN [0..maxFeatures)
DO
h[i].dist ← Real.LargestNumber;
h[i].featureData ← NIL;
ENDLOOP;
};
BestCurvesFromPool:
PROC [svData: SVData, t:
REAL, innerR:
REAL]
RETURNS [h: BestPoints] = {
h ← NARROW[svData.gravityPool, MultiGravityPool].bestcurves;
h.size ← 0;
h.max ← 0;
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-1]
DO
h[i].dist ← Real.LargestNumber;
h[i].featureData ← NIL;
ENDLOOP;
};
BestPointsFromPool:
PROC [svData: SVData, t:
REAL]
RETURNS [h: BestPoints] = {
h ← NARROW[svData.gravityPool, MultiGravityPool].bestpoints;
h.size ← 0;
h.max ← 0;
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-1]
DO
h[i].dist ← Real.LargestNumber;
h[i].featureData ← NIL;
ENDLOOP;
};
InitStats:
PROC = {
interval: CodeTimer.Interval;
interval ← CodeTimer.CreateInterval[$RayMap];
CodeTimer.AddInt[interval, $Solidviews];
interval ← CodeTimer.CreateInterval[$PointOverflow];
CodeTimer.AddInt[interval, $Solidviews];
};
InitStats[];
Init[];
END.