DIRECTORY
SVCastRays, SVRay, SV2d, SV3d, SVBoundBox, SVFaces, SVFacesCast, SVLines2d, SVPolygon2d, SVPolygon3d, SVSceneTypes, SweepCast, SweepGeometry;

SweepCastImpl: CEDAR PROGRAM
IMPORTS SVCastRays, SVRay, SVBoundBox, SVFaces, SVFacesCast, SVLines2d, SVPolygon2d, SVPolygon3d
EXPORTS SweepCast =
BEGIN

Classification: TYPE = SVSceneTypes.Classification;
Plane: TYPE = SV3d.Plane;
Point2d: TYPE = SV2d.Point2d;
Point3d: TYPE = SV3d.Point3d;
Polygon: TYPE = SV2d.Polygon;
Primitive: TYPE = SVSceneTypes.Primitive;
Ray: TYPE = SVSceneTypes.Ray;
Vector3d: TYPE = SV3d.Vector3d;

Cone: TYPE = SVFaces.Cone;
DiskRing: TYPE = SVFaces.DiskRing;
Cylinder: TYPE = SVFaces.Cylinder;
FaceHitRec: TYPE = SVFacesCast.FaceHitRec;

LinearMesh: TYPE = REF LinearMeshRecord;
LinearMeshRecord: TYPE = SweepGeometry.LinearMeshRecord;
RevoluteMesh: TYPE = REF RevoluteMeshRecord;
RevoluteMeshRecord: TYPE = SweepGeometry.RevoluteMeshRecord;

RevoSweepFaces: TYPE = REF RevoSweepFacesObj;
RevoSweepFacesObj: TYPE = SweepCast.RevoSweepFacesObj;
SubBoxesBody: TYPE = SweepCast.SubBoxesBody;
SubSpheresBody: TYPE = SweepCast.SubSpheresBody;

RevoHitArray: TYPE = REF RevoHitArrayObj;
RevoHitArrayObj: TYPE = SweepCast.RevoHitArrayObj;
RevoHitRec: TYPE = REF RevoHitRecObj;
RevoHitRecObj: TYPE = SweepCast.RevoHitRecObj;

LinSweepFaces: TYPE = REF LinSweepFacesObj;
LinSweepFacesObj: TYPE = SweepCast.LinSweepFacesObj;
LinHitArray: TYPE = REF LinHitArrayObj;
LinHitArrayObj: TYPE = SweepCast.LinHitArrayObj;
LinHitRec: TYPE = REF LinHitRecObj;
LinHitRecObj: TYPE = SweepCast.LinHitRecObj;

globalRevoHits: RevoHitArray;
globalLinHits: LinHitArray;

almostZero: REAL = 1.0e-12;

LinCast: PUBLIC PROC [localRay: Ray, prim: Primitive, linMesh: LinearMesh, faces: LinSweepFaces] RETURNS [class: Classification] = {

 poly: Polygon;
 faceHit: FaceHitRec;
 
class _ SVCastRays.GetClassFromPool[];
globalLinHits.count _ 0;


 
poly _ faces.poly;
faceHit _ RayXYPolygon[localRay, poly, linMesh.array[1][1][3], [0, 0, 1]];
IF faceHit.count = 1 THEN {
globalLinHits.count _ globalLinHits.count + 1;
 globalLinHits.array[globalLinHits.count]^ _ 
 [faceHit.params[1], faceHit.normals[1], 0]};
SVFacesCast.ReturnFaceHitToPool[faceHit];

faceHit _ RayXYPolygon[localRay, poly, linMesh.array[1][2][3], [0, 0, -1]];
IF faceHit.count = 1 THEN {
globalLinHits.count _ globalLinHits.count + 1;
 globalLinHits.array[globalLinHits.count]^ _ 
 [faceHit.params[1], faceHit.normals[1], linMesh.len+1]};
SVFacesCast.ReturnFaceHitToPool[faceHit];

FOR i: NAT IN [0..faces.len) DO
faceHit _ SVFacesCast.EdgeOnRectCast[faces[i], localRay];
IF faceHit.count = 1 THEN {
globalLinHits.count _ globalLinHits.count + 1;
 globalLinHits.array[globalLinHits.count]^ _ 
 [faceHit.params[1], faceHit.normals[1], i+1]};
SVFacesCast.ReturnFaceHitToPool[faceHit];
ENDLOOP;


SELECT globalLinHits.count FROM
0 => { -- miss.
   SVCastRays.MakeClassAMiss[class]};
1 => { 
p: Point3d;
d: Vector3d;
pointClass: SVPolygon2d.PointPolyClass;
[p, d] _ SVRay.GetLocalRay[localRay];
IF p[3] > linMesh.array[1][2][3] AND p[3] < linMesh.array[1][1][3] THEN { 
pointClass _ SVPolygon2d.BoysePointInPoly[[p[1], p[2]], poly];
IF pointClass = in THEN {
class.count _ 1;
class.params[1] _ globalLinHits.array[1].param;
class.normals[1] _ globalLinHits.array[1].normal;
class.surfaces[1] _ NIL;
class.classifs[1] _ TRUE;
class.classifs[2] _ FALSE;
class.primitives[1] _ prim;
}
ELSE SVCastRays.MakeClassAMiss[class];
}
ELSE SVCastRays.MakeClassAMiss[class];
};
ENDCASE => {
iPlusOne: NAT;
startI: NAT _ 1;
SortLinHits[globalLinHits];
IF (globalLinHits.count/2)*2 # globalLinHits.count THEN { -- odd number of hits
p: Point3d;
d: Vector3d;
pointClass: SVPolygon2d.PointPolyClass;
[p, d] _ SVRay.GetLocalRay[localRay];
IF p[3] > linMesh.array[1][2][3] AND p[3] < linMesh.array[1][1][3] THEN { 
pointClass _ SVPolygon2d.BoysePointInPoly[[p[1], p[2]], poly];
IF pointClass = in THEN {
startI _ 2;
class.params[1] _ globalLinHits.array[1].param;
class.normals[1] _ globalLinHits.array[1].normal;
class.surfaces[1] _ NIL;
class.classifs[1] _ TRUE;
class.primitives[1] _ prim;
}
ELSE globalRevoHits.count _ globalLinHits.count - 1;
}
ELSE globalRevoHits.count _ globalLinHits.count - 1;
};

class.count _ globalLinHits.count;
FOR i: NAT _ startI, i+2 UNTIL i > globalLinHits.count DO
iPlusOne _ i+1;
class.params[i] _ globalLinHits.array[i].param;
class.params[iPlusOne] _ globalLinHits.array[iPlusOne].param;
class.normals[i] _ globalLinHits.array[i].normal;
class.normals[iPlusOne] _ globalLinHits.array[iPlusOne].normal;
class.surfaces[i] _ NIL;
class.surfaces[iPlusOne] _ NIL;
class.classifs[i] _ FALSE;
class.classifs[iPlusOne] _ TRUE;
class.primitives[i] _ prim;
class.primitives[iPlusOne] _ prim;
ENDLOOP;
class.classifs[globalLinHits.count+1] _ FALSE;
};  -- end of 2 or more hits   

}; -- end of LinCast

RevoCast: PUBLIC PROC [cameraPoint: Point2d, localRay: Ray, prim: Primitive, faces: RevoSweepFaces, boxes: SubBoxesBody] RETURNS [class: Classification] = {
class _ SVCastRays.GetClassFromPool[];
globalRevoHits.count _ 0;
FOR i: NAT IN[0..faces.len) DO
WITH faces[i] SELECT FROM
cone: Cone => {
hits: FaceHitRec;
IF NOT SVBoundBox.PointInBoundBox[cameraPoint, boxes[i]] THEN LOOP;
hits _ SVFacesCast.ConeCast[cone, localRay];
FOR j: NAT IN[1..hits.count] DO
globalRevoHits.count _ globalRevoHits.count + 1;
globalRevoHits.array[globalRevoHits.count]^ _ [hits.params[j], hits.normals[j], i];
ENDLOOP;
SVFacesCast.ReturnFaceHitToPool[hits];
};
disk: DiskRing => {
hit: FaceHitRec;
IF NOT SVBoundBox.PointInBoundBox[cameraPoint, boxes[i]] THEN LOOP;
hit _ SVFacesCast.DiskRingCast[disk, localRay];
IF hit.count = 1 THEN {
globalRevoHits.count _ globalRevoHits.count + 1;
globalRevoHits.array[globalRevoHits.count]^ _ [hit.params[1], hit.normals[1], i];
};
SVFacesCast.ReturnFaceHitToPool[hit];
};
cyl: Cylinder => {
hits: FaceHitRec;
IF NOT SVBoundBox.PointInBoundBox[cameraPoint, boxes[i]] THEN LOOP;
hits _ SVFacesCast.CylinderCast[cyl, localRay];
FOR j: NAT IN[1..hits.count] DO
globalRevoHits.count _ globalRevoHits.count + 1;
globalRevoHits.array[globalRevoHits.count]^ _ [hits.params[j], hits.normals[j], i];
ENDLOOP;
SVFacesCast.ReturnFaceHitToPool[hits];
};
ENDCASE => ERROR;
ENDLOOP;-- next face
SELECT globalRevoHits.count FROM
0 => {-- miss.
   SVCastRays.MakeClassAMiss[class]};
1 => {-- ray just skims one face.  Treat as a miss.
   SVCastRays.MakeClassAMiss[class]};
ENDCASE => {
iPlusOne: NAT;
SortRevoHits[globalRevoHits];
IF (globalRevoHits.count/2)*2 # globalRevoHits.count THEN
globalRevoHits.count _ globalRevoHits.count - 1;
class.count _ globalRevoHits.count;
FOR i: NAT _ 1, i+2 UNTIL i > globalRevoHits.count DO
iPlusOne _ i+1;
class.params[i] _ globalRevoHits.array[i].param;
class.params[iPlusOne] _ globalRevoHits.array[iPlusOne].param;
class.normals[i] _ globalRevoHits.array[i].normal;
class.normals[iPlusOne] _ globalRevoHits.array[iPlusOne].normal;
class.surfaces[i] _ NIL;
class.surfaces[iPlusOne] _ NIL;
class.classifs[i] _ FALSE;
class.classifs[iPlusOne] _ TRUE;
class.primitives[i] _ prim;
class.primitives[iPlusOne] _ prim;
 ENDLOOP;
 class.classifs[globalRevoHits.count+1] _ FALSE;
};  -- end of 2 or more hits   

}; -- end of RevoCast
RevoCastNoBBoxes: PUBLIC PROC [localRay: Ray, prim: Primitive, faces: RevoSweepFaces] RETURNS [class: Classification] = {
class _ SVCastRays.GetClassFromPool[];
globalRevoHits.count _ 0;
FOR i: NAT IN[0..faces.len) DO
WITH faces[i] SELECT FROM
cone: Cone => {
hits: FaceHitRec;
hits _ SVFacesCast.ConeCast[cone, localRay];
FOR j: NAT IN[1..hits.count] DO
globalRevoHits.count _ globalRevoHits.count + 1;
globalRevoHits.array[globalRevoHits.count]^ _ [hits.params[j], hits.normals[j], i];
ENDLOOP;
SVFacesCast.ReturnFaceHitToPool[hits];
};
disk: DiskRing => {
hit: FaceHitRec;
hit _ SVFacesCast.DiskRingCast[disk, localRay];
IF hit.count = 1 THEN {
globalRevoHits.count _ globalRevoHits.count + 1;
globalRevoHits.array[globalRevoHits.count]^ _ [hit.params[1], hit.normals[1], i];
};
SVFacesCast.ReturnFaceHitToPool[hit];
};
cyl: Cylinder => {
hits: FaceHitRec;
hits _ SVFacesCast.CylinderCast[cyl, localRay];
FOR j: NAT IN[1..hits.count] DO
globalRevoHits.count _ globalRevoHits.count + 1;
globalRevoHits.array[globalRevoHits.count]^ _ [hits.params[j], hits.normals[j], i];
ENDLOOP;
SVFacesCast.ReturnFaceHitToPool[hits];
};
ENDCASE => ERROR;
ENDLOOP;-- next face
SELECT globalRevoHits.count FROM
0 => {-- miss.
   SVCastRays.MakeClassAMiss[class]};
1 => {-- ray just skims one face.  Treat as a miss.
   SVCastRays.MakeClassAMiss[class]};
ENDCASE => {-- Sort the hits in order of depth along ray.  Assume for now that the ray Doesn't skim edges or miss surfaces or go through cracks.  Hence every other hit is an enter followed by an exit.  If there is an odd number of hits, ignore the last one.
iPlusOne: NAT;
SortRevoHits[globalRevoHits];
IF (globalRevoHits.count/2)*2 # globalRevoHits.count THEN
globalRevoHits.count _ globalRevoHits.count - 1;
class.count _ globalRevoHits.count;
FOR i: NAT _ 1, i+2 UNTIL i > globalRevoHits.count DO
iPlusOne _ i+1;
class.params[i] _ globalRevoHits.array[i].param;
class.params[iPlusOne] _ globalRevoHits.array[iPlusOne].param;
class.normals[i] _ globalRevoHits.array[i].normal;
class.normals[iPlusOne] _ globalRevoHits.array[iPlusOne].normal;
class.surfaces[i] _ NIL;
class.surfaces[iPlusOne] _ NIL;
class.classifs[i] _ FALSE;
class.classifs[iPlusOne] _ TRUE;
class.primitives[i] _ prim;
class.primitives[iPlusOne] _ prim;
ENDLOOP;
class.classifs[globalRevoHits.count+1] _ FALSE;
};  -- end of 2 or more hits   

}; -- end of RevoCast
OddHits: ERROR = CODE;
InOutsDontAlternate: ERROR = CODE;
RevoCastBoundSpheres: PUBLIC PROC [localRay: Ray, prim: Primitive, faces: RevoSweepFaces, spheres: SubSpheresBody] RETURNS [class: Classification] = {
class _ SVCastRays.GetClassFromPool[];
globalRevoHits.count _ 0;
FOR i: NAT IN[0..faces.len) DO
WITH faces[i] SELECT FROM
cone: Cone => {
hits: FaceHitRec;
IF NOT SVRay.RayHitsBoundSphere[localRay, spheres[i]] THEN LOOP;
hits _ SVFacesCast.ConeCast[cone, localRay];
FOR j: NAT IN[1..hits.count] DO
globalRevoHits.count _ globalRevoHits.count + 1;
globalRevoHits.array[globalRevoHits.count]^ _ [hits.params[j], hits.normals[j], i];
ENDLOOP;
SVFacesCast.ReturnFaceHitToPool[hits];
};
disk: DiskRing => {
hit: FaceHitRec;
IF NOT SVRay.RayHitsBoundSphere[localRay, spheres[i]] THEN LOOP;
hit _ SVFacesCast.DiskRingCast[disk, localRay];
IF hit.count = 1 THEN {
globalRevoHits.count _ globalRevoHits.count + 1;
globalRevoHits.array[globalRevoHits.count]^ _ [hit.params[1], hit.normals[1], i];
};
SVFacesCast.ReturnFaceHitToPool[hit];
};
cyl: Cylinder => {
hits: FaceHitRec;
IF NOT SVRay.RayHitsBoundSphere[localRay, spheres[i]] THEN LOOP;
hits _ SVFacesCast.CylinderCast[cyl, localRay];
FOR j: NAT IN[1..hits.count] DO
globalRevoHits.count _ globalRevoHits.count + 1;
globalRevoHits.array[globalRevoHits.count]^ _ [hits.params[j], hits.normals[j], i];
ENDLOOP;
SVFacesCast.ReturnFaceHitToPool[hits];
};
ENDCASE => ERROR;
ENDLOOP; -- next face
SELECT globalRevoHits.count FROM
0 => {-- miss.
   SVCastRays.MakeClassAMiss[class]};
1 => {-- ray originates inside of the sweep or is a glancing hit.  See if ray base-point passes an inside-outside test.  This boils down to a point-in-polygon test.
class.count _ 1;
class.params[1] _ globalRevoHits.array[1].param;
class.surfaces[1] _ NIL;
class.classifs[1] _ TRUE;  class.classifs[2] _ FALSE;
class.normals[1] _ globalRevoHits.array[1].normal;
class.primitives[1] _ prim;
};
ENDCASE => {
iPlusOne: NAT;
SortRevoHits[globalRevoHits];
IF (globalRevoHits.count/2)*2 # globalRevoHits.count THEN
globalRevoHits.count _ globalRevoHits.count - 1;
class.count _ globalRevoHits.count;
FOR i: NAT _ 1, i+2 UNTIL i > globalRevoHits.count DO
iPlusOne _ i+1;
class.params[i] _ globalRevoHits.array[i].param;
class.params[iPlusOne] _ globalRevoHits.array[iPlusOne].param;
class.normals[i] _ globalRevoHits.array[i].normal;
class.normals[iPlusOne] _ globalRevoHits.array[iPlusOne].normal;
class.surfaces[i] _ NIL;
class.surfaces[iPlusOne] _ NIL;
class.classifs[i] _ FALSE;
class.classifs[iPlusOne] _ TRUE;
class.primitives[i] _ prim;
class.primitives[iPlusOne] _ prim;
ENDLOOP;
class.classifs[globalRevoHits.count+1] _ FALSE;
};  -- end of 2 or more hits   

}; -- end of RevoCastBoundSpheres


HitsACrack: PRIVATE PROC [localRay: Ray, t, y: REAL, meshRecord: RevoluteMesh] RETURNS [matches: BOOL, index: NAT] = {
x, z, r: REAL;
p: Point3d;
d: Vector3d;
[p, d] _ SVRay.GetLocalRay[localRay];
FOR i: NAT IN[1..meshRecord.linesOfLatitude] DO
IF AlmostEqualHeights[y, meshRecord.array[i][1][2]] THEN {
x _ p[1] + t*d[1];
z _ p[3] + t*d[3];
r _ meshRecord.array[i][meshRecord.linesOfLongitude][1];
IF x*x + z*z = r*r THEN {
matches _ TRUE; index _ i; RETURN}
ELSE {
matches _ FALSE; RETURN}};
ENDLOOP;
matches _ FALSE;
}; -- end of HitsACrack

HitsNeighbors: PRIVATE PROC [localRay: Ray, index: NAT, mesh: RevoluteMesh] RETURNS [BOOL] = {
IF index = 1 THEN RETURN[HitsDisk[localRay, mesh.array[2][1][2], mesh.array[2][mesh.linesOfLongitude][1]]];
IF index = mesh.linesOfLatitude THEN
RETURN[HitsDisk[localRay, mesh.array[mesh.linesOfLatitude-1][1][2], mesh.array[mesh.linesOfLatitude-1][mesh.linesOfLongitude][1]]];
RETURN[
HitsDisk[localRay, mesh.array[index-1][1][2], mesh.array[index-1][mesh.linesOfLongitude][1]]
OR
HitsDisk[localRay, mesh.array[index+1][1][2], mesh.array[index+1][mesh.linesOfLongitude][1]]
];
};

HitsDisk: PRIVATE PROC [localRay: Ray, y: REAL, r: REAL] RETURNS [success: BOOL] = {
x, z, t: REAL;
p: Point3d;
d: Vector3d;
[p, d] _ SVRay.GetLocalRay[localRay];
success _ FALSE;
IF Abs[d[2]] < almostZero THEN RETURN; -- ray parallel to plane of disk
t _ (y - p[2])/d[2];
IF t > 0 THEN {
x _ p[1] + t*d[1];
z _ p[3] + t*d[3];
IF  x*x + z*z <= r*r THEN success _ TRUE;
};
}; -- end of HitsDisk
 

AlmostEqualParams: PRIVATE PROC [t1, t2: REAL] RETURNS [BOOL] = {
RETURN[Abs[t2-t1] < 1.0e-2];
};
AlmostEqualHeights: PRIVATE PROC [h1, h2: REAL] RETURNS [BOOL] = {
RETURN[Abs[h2-h1] < 1.0];
};
DeleteFromHits: PRIVATE PROC [hits: RevoHitArray, index: NAT] = {
temp: RevoHitRec _ hits.array[index];
FOR i: NAT IN[index..hits.count-1] DO
hits.array[i] _ hits.array[i+1];
ENDLOOP;
hits.array[hits.count] _ temp;-- replace the storage for later use
hits.count _ hits.count - 1;
}; -- end of DeleteFromHits

RayGoesIn: PRIVATE PROC [ray: Ray, hit: RevoHitRec] RETURNS [BOOL] = {
hitPoint: Point3d;
plane: Plane;
basePt: Point3d;
basePtOnNormalSide: BOOL;

hitPoint _ SVRay.EvaluateLocalRay[ray, hit.param];
[basePt,] _ SVRay.GetLocalRay[ray];
plane _ SVPolygon3d.PlaneFromPointAndNormal[hitPoint, hit.normal];
basePtOnNormalSide _ SVPolygon3d.PointOnNormalSideOfPlane[basePt, plane];
RETURN[basePtOnNormalSide];
}; -- end of RayGoesIn

SortLinHits: PROC [hits: LinHitArray] = {
temp: LinHitRec;
FOR i: NAT IN[1..hits.count-1] DO
FOR j: NAT IN[1..hits.count-i] DO
IF hits.array[j].param > hits.array[j+1].param THEN {
temp _ hits.array[j];
hits.array[j] _ hits.array[j+1];
hits.array[j+1] _ temp;};
ENDLOOP;
ENDLOOP;
};
SortRevoHits: PROC [hits: RevoHitArray] = {
temp: RevoHitRec;
FOR i: NAT IN[1..hits.count-1] DO
FOR j: NAT IN[1..hits.count-i] DO
IF hits.array[j].param > hits.array[j+1].param THEN {
temp _ hits.array[j];
hits.array[j] _ hits.array[j+1];
hits.array[j+1] _ temp;};
ENDLOOP;
ENDLOOP;
};
Abs: PROC [r: REAL] RETURNS [REAL] = {
RETURN[IF r >= 0 THEN r ELSE -r];
};
Point3dToPoint2d: PRIVATE PROC [p3: Point3d] RETURNS [p2: Point2d] = {
p2[1] _ p3[1];
p2[2] _ p3[2];
};
MakeLinSweepFaces: PUBLIC PROC [linMesh: LinearMesh] RETURNS [faces: LinSweepFaces] = {
lastPoint, thisPoint: Point2d;
seg: SV2d.TrigLineSeg;
poly: Polygon _ SVPolygon2d.CreatePoly[linMesh.len];
FOR i: NAT IN[1..linMesh.len] DO
poly _ SVPolygon2d.AddPolyPoint[poly, [linMesh.array[i][1][1], linMesh.array[i][1][2]] ];
ENDLOOP;
faces _ NEW[LinSweepFacesObj[linMesh.len]];
faces.len _ linMesh.len;
faces.poly _ poly;
lastPoint _ Point3dToPoint2d[linMesh.array[linMesh.len][1]];
FOR i: NAT IN[1..linMesh.len] DO
thisPoint _ Point3dToPoint2d[linMesh.array[i][1]];
seg _ SVLines2d.CreateTrigLineSeg[lastPoint, thisPoint];
faces[i-1] _ SVFaces.EdgeOnRectFromTrigLineSeg[seg: seg, frontZ: linMesh.array[1][1][3],
backZ: linMesh.array[1][2][3]];
lastPoint _ thisPoint;
ENDLOOP;
};
MakeRevoSweepFaces: PUBLIC PROC [revMesh: RevoluteMesh] RETURNS [faces: RevoSweepFaces] = {
lastPoint, thisPoint: Point2d;
lastLong: NAT _ revMesh.linesOfLongitude;
seg: SV2d.TrigLineSeg;
faces _ NEW[RevoSweepFacesObj[revMesh.linesOfLatitude+1]];
faces.len _ revMesh.linesOfLatitude+1;
lastPoint _ Point3dToPoint2d[revMesh.array[1][lastLong]];
seg _ SVLines2d.CreateTrigLineSeg[[0,lastPoint[2]], lastPoint];
faces[0] _ SVFaces.DiskRingFromTrigLineSeg[seg];
FOR i: NAT IN[2..revMesh.linesOfLatitude] DO -- the intermediate faces
thisPoint _ Point3dToPoint2d[revMesh.array[i][lastLong]];
seg _ SVLines2d.CreateTrigLineSeg[lastPoint, thisPoint];
SELECT seg.line.theta FROM
0, 180 => -- make a disk
faces[i-1] _ SVFaces.DiskRingFromTrigLineSeg[seg];
IN (0..90), IN (90..180), IN (-90..0), IN (-180..-90) => -- make a cone
faces[i-1] _ SVFaces.ConeFromTrigLineSeg[seg];
90, -90 => -- make a cylinder
faces[i-1] _ SVFaces.CylinderFromTrigLineSeg[seg];
ENDCASE => ERROR;
lastPoint _ thisPoint;
ENDLOOP;
seg _ SVLines2d.CreateTrigLineSeg[lastPoint, [0,lastPoint[2]]];
faces[revMesh.linesOfLatitude] _ SVFaces.DiskRingFromTrigLineSeg[seg];
faces.mesh _ revMesh;
};
RayXYPolygon: PRIVATE PROC [localRay: Ray, poly: Polygon, depth: REAL, normal: Vector3d] RETURNS [linHit: FaceHitRec] = {
x, y, z, t: REAL;
pointClass: SVPolygon2d.PointPolyClass;
p: Point3d;
d: Vector3d;
linHit _ SVFacesCast.GetFaceHitFromPool[];
[p, d] _ SVRay.GetLocalRay[localRay];
z _ depth;
IF Abs[d[3]] < almostZero THEN {linHit.count _ 0; RETURN};
t _ (z - p[3])/d[3];
IF t <= 0 THEN {linHit.count _ 0; RETURN};
x _ p[1] + t*d[1];
y _ p[2] + t*d[2];
pointClass _ SVPolygon2d.BoysePointInPoly[[x,y], poly];
IF pointClass = in OR pointClass = on THEN {
linHit.count _ 1;
linHit.params[1] _ t;
linHit.normals[1] _ normal;
}
ELSE linHit.count _ 0;
}; -- end of RayXYPolygon


Init: PROC = {
globalRevoHits _ NEW[RevoHitArrayObj];
globalRevoHits.count _ 0;
FOR i: NAT IN[1..SweepGeometry.maxLinesOfLat+1] DO
globalRevoHits.array[i] _ NEW[RevoHitRecObj];
ENDLOOP;
globalLinHits _ NEW[LinHitArrayObj];
globalLinHits.count _ 0;
FOR i: NAT IN[1..SweepGeometry.maxMeshLen-1] DO
globalLinHits.array[i] _ NEW[LinHitRecObj];
ENDLOOP;
};

Init[];

END.
΄File: SweepCastImpl.mesa
Last edited by: Bier on June 1, 1987 11:14:22 am PDT
Copyright c 1984 by Xerox Corporation.  All rights reserved.
Contents:  Ray Tracing Code for linear and revolute sweep shapes.
A linear sweep in instance coordinates has its two complicated polygons parallel to the xy plane.  Hence, all of the other (rectangular) faces are edge-on when projected on to the xy plane.  We can use this fact to simplify their plane equations to line equations for ray casting.
We must do 2 ray-xyPolygon tests and "len" ray-edgeOnRectangle tests.
the shape may be convex so the ray may hit any even number of faces (in a perfect world), and any number of faces at all in our floating point world.  We ignore odd hits for now.
do 2 ray-xyPolygon tests.
front face;
back face
do ray-edgeOnRectangle tests
now combine the results
Ray just skims one face or ray comes from inside.  If ray comes from inside, classify ray as such.  Otherwise, count as a miss.
Sort the hits in order of depth along ray.  Assume for now that the ray doesn't skim edges or miss surfaces or go through cracks.  Hence every other hit is an enter followed by an exit.  If there is an odd number of hits, see if the ray starts inside of the solid.  If so, proceed.  Otherwise, ignore the last one.
A revolute sweep in instance coordinates has rotational symmetry about the y axis.  Since it consists of straight line segments rotated about the y axis, its faces are cylindrical tubes, planar rings, and conical shouds,  depending on whether the line segment in question was vertical, horizontal or neither respectively.
Given a list of these "faces", we test the ray against each one for intersections.  We may get as many as 4 intersections if the ray skims the cracks between two pairs of faces.  However, we should only come up with two unique ray parameters t.  We will award the intersection to the face which is higher.
Now see how many hits we have.  We can have any number up to linesOfLatitude + 1 since the outline doesn't have to be convex.  The number can be odd if the ray hits a crack between faces and both notice it.  We proceed as follows:  If there are 2 or more hits then we sort all of the hits by t.  If 2 adjacent hits have similar y values and similar t values then we count them as the same hit and throw out the lower one.  We we are done with this processing, if we have an odd number of hits, it is an error.  Next we use the surface normals to see if the ray is entering or exitting at this point.  If this does not alternate (starting with in), we have an error.  Finally, we make a classification with the sorted params.
Sort the hits in order of depth along ray.  Assume for now that the ray doesn't skim edges or miss surfaces or go through cracks.  Hence every other hit is an enter followed by an exit.  If there is an odd number of hits, ignore the last one.
A revolute sweep in instance coordinates has rotational symmetry about the y axis.  Since it consists of straight line segments rotated about the y axis, its faces are cylindrical tubes, planar rings, and conical shouds,  depending on whether the line segment in question was vertical, horizontal or neither respectively.
Given a list of these "faces", we test the ray against each one for intersections.  We may get as many as 4 intersections if the ray skims the cracks between two pairs of faces.  However, we should only come up with two unique ray parameters t.  We will award the intersection to the face which is higher.
Now see how many hits we have.  We can have any number up to linesOfLatitude + 1 since the outline doesn't have to be convex.  The number can be odd if the ray hits a crack between faces and both notice it.  We proceed as follows:  If there are 2 or more hits then we sort all of the hits by t.  If 2 adjacent hits have similar y values and similar t values then we count them as the same hit and throw out the lower one.  We we are done with this processing, if we have an odd number of hits, it is an error.  Next we use the surface normals to see if the ray is entering or exitting at this point.  If this does not alternate (starting with in), we have an error.  Finally, we make a classification with the sorted params.
A revolute sweep in instance coordinates has rotational symmetry about the y axis.  Since it consists of straight line segments rotated about the y axis, its faces are cylindrical tubes, planar rings, and conical shouds,  depending on whether the line segment in question was vertical, horizontal or neither respectively.
Given a list of these "faces", we test the ray against each one for intersections.  We may get as many as 4 intersections if the ray skims the cracks between two pairs of faces.  However, we should only come up with two unique ray parameters t.  We will award the intersection to the face which is higher.
Now see how many hits we have.  We can have any number up to linesOfLatitude + 1 since the outline doesn't have to be convex.  The number can be odd if the ray hits a crack between faces and both notice it.  We proceed as follows:  If there are 2 or more hits then we sort all of the hits by t.  If 2 adjacent hits have similar y values and similar t values then we count them as the same hit and throw out the lower one.  When we are done with this processing, if we have an odd number of hits, we assume that the ray originates inside of
the sweep.  Finally, we make a classification with the sorted params.
r: REAL _ RealFns.SqRt[p[1]*p[1] + p[3]*p[3]];
y: REAL _ p[2];
Sort the hits in order of depth along ray.  Assume for now that the ray doesn't skim edges or miss surfaces or go through cracks.  Hence every other hit is an enter followed by an exit.  If there is an odd number of hits, ignore the last one.
Checks ray for intersections with the disk in plane Y=y of radius r.
do 1 ray-plane intersection and test to see if it is inside the circle
Plane is y = y;
For ray, y = p2 + t*d2;
Solving, y = p2 + t*d2;  (y - p2)/d2 = t;
Shift all elements above this one down and reduce count by 1
TRUE means the ray is entering the plane from the normal side.
If basePt is on the normal side then we are going in.
Interate through consequtive pairs of vertices of the front polygon of the linear mesh.  Make linMesh.len faces using SVFaces.EdgeOnRectFromTrigLineSeg
extract the defining polygon
Make the edge-on-rectangles
Currently the 2d polygon from which a revMesh is derived just happens to be in the last line of longitude (ignoring the z component which is zero);  I assume the revolute mesh is defined clockwise (in the positive x half-plane seen from positive z).  A trig line segment is oriented, so we don't lose the clockwise information when we make one.  This allows SVFaces to orient normals properly.
the top of a sweep is a disk
The bottom face is a disk
Find intersection of localRay with the plane of the polygon.  Use PointInPoly test to see if this point is inside of the polygon.  Return a filled LinHitRec if so.
plane equation Z=z.  Ray equation is, as usual, z = p3 + t*d3.  Solve for t.
(z-p3)/d3 = t;
Κn–
"Mesa" style˜Iheadš
œ™Iprocš
œ4™4Jšœ
Οm
œ1™<Lš
œA™AL˜š
Οk	˜	Lšœžœ|˜
—L˜Lšœž
˜LšžœY˜`Lšžœ˜Lš
ž˜˜Lšœžœ˜3Lšœžœ˜Lšœ	žœ˜Lšœ	žœ˜Lšœ	žœ˜Lšœžœ˜)Lšœžœž
œ˜Lšœ
žœ˜L˜Lšœžœ˜Lšœ
žœ˜"Lšœ
žœ˜"Lšœžœ˜*L˜Lšœžœžœ˜(Lšœžœ"˜8Lšœžœžœ˜,Lšœžœ$˜<L˜Lšœžœžœ˜-Lšœžœ˜6Lšœžœ˜,Lšœžœ˜0L˜Lšœžœžœ˜)Lšœžœ˜2Lšœžœžœ˜%Lšœžœ˜.L˜Lšœžœžœ˜+Lšœžœ˜4Lšœ
žœžœ˜'Lšœžœ˜0Lšœžœžœ˜#Lšœžœ˜,L˜Lš
œ˜Lš
œ˜L˜Lšœžœ˜L˜—šΟnœžœ
žœMžœ˜„
Lš
œ˜™˜Lš
œE™ELš
œ²
™²
L˜Lš
œ˜Lš
œ˜Lš
œ
˜
Lš
œ&˜&Lš
œ˜L˜Lš
œ™L˜Lš
œ
˜
Lš
œ™Lš
œ˜Lš
œJ˜Jšžœžœ˜Lš
œ.˜.Lš
œ-˜-Lš
œ-˜-—Lš
œ)˜)L˜Lš
œ	™	Lš
œK˜Kšžœžœ˜Lš
œ.˜.Lš
œ-˜-Lš
œ9˜9—Lš
œ)˜)L˜Lš
œ™Lšžœžœ
žœž˜Lš
œ9˜9šžœžœ˜Lš
œ.˜.Lš
œ-˜-Lš
œ/˜/—Lš
œ)˜)Lšžœ
˜L˜Lš
œ™L˜Lšžœž˜Lš
œ˜Lš
œ%˜%š
œ˜L˜L˜Lš
œ'˜'Lš
œ™Lšœ	žœ˜%šžœžœžœ˜JLš
œ>˜>šžœžœ˜Lš
œ˜Lš
œ/˜/Lš
œ1˜1Lšœžœ
˜Lšœžœ
˜Lšœžœ
˜Lš
œ˜L˜
—Lšžœ"˜&L˜
—Lšžœ"˜&Lš
œ˜—Lšžœ˜Lš
œΊ™ΊLšœ
žœ
˜Lšœžœ˜Lš
œ˜šžœ1žœΟc˜OL˜L˜Lš
œ'˜'Lšœ	žœ˜%šžœžœžœ˜JLš
œ>˜>šžœžœ˜Lš
œ˜Lš
œ/˜/Lš
œ1˜1Lšœžœ
˜Lšœžœ
˜Lš
œ˜L˜
—Lšžœ0˜4L˜
—Lšžœ0˜4L˜—L˜Lš
œ"˜"šžœžœžœž˜9Lš
œ˜Lš
œ/˜/Lš
œ=˜=Lš
œ1˜1Lš
œ?˜?Lšœžœ
˜Lšœžœ
˜Lšœžœ
˜Lšœžœ
˜ Lš
œ˜Lš
œ"˜"—Lšžœ
˜Lšœ(žœ
˜.Lš
œ˜L˜Lš
œ˜—L˜šŸœžœ
žœdžœ˜œ
Lš
œΑ™ΑLš
œ±™±Lš
œ&˜&Lš
œ˜šžœžœ
žœž˜Lšžœ
žœ
ž˜š
œ˜Lš
œ˜Lšžœ
žœ3žœ
žœ
˜CLš
œ,˜,šžœžœ
žœž˜Lš
œ0˜0Lš
œS˜S—Lšžœ
˜Lš
œ&˜&Lš
œ˜—š
œ˜Lš
œ˜Lšžœ
žœ3žœ
žœ
˜CLš
œ/˜/šžœžœ˜Lš
œ0˜0Lš
œQ˜QLš
œ˜—Lš
œ%˜%Lš
œ˜—š
œ˜Lš
œ˜Lšžœ
žœ3žœ
žœ
˜CLš
œ/˜/šžœžœ
žœž˜Lš
œ0˜0Lš
œS˜S—Lšžœ
˜Lš
œ&˜&Lš
œ˜—Lšžœžœ
˜—Lšžœ
˜Lš
œΤ™ΤLšžœž˜ Lš
œ˜Lš
œ%˜%Lš
œ3˜3Lš
œ%˜%Lšžœ˜Lš
œς
™ς
Lšœ
žœ
˜Lš
œ˜šžœ2ž˜9Lš
œ0˜0—Lš
œ#˜#šžœžœ
žœž˜5Lš
œ˜Lš
œ0˜0Lš
œ>˜>Lš
œ2˜2Lš
œ@˜@Lšœžœ
˜Lšœžœ
˜Lšœžœ
˜Lšœžœ
˜ Lš
œ˜Lš
œ"˜"—Lšœ
žœ
˜	Lšœ*žœ
˜0Lš
œ˜L˜Lš
œ˜—šŸœžœ
žœ9žœ˜yLš
œΑ™ΑLš
œ±™±Lš
œ&˜&Lš
œ˜šžœžœ
žœž˜Lšžœ
žœ
ž˜š
œ˜Lš
œ˜Lš
œ,˜,šžœžœ
žœž˜Lš
œ0˜0Lš
œS˜S—Lšžœ
˜Lš
œ&˜&Lš
œ˜—š
œ˜Lš
œ˜Lš
œ/˜/šžœžœ˜Lš
œ0˜0Lš
œQ˜QLš
œ˜—Lš
œ%˜%Lš
œ˜—š
œ˜Lš
œ˜Lš
œ/˜/šžœžœ
žœž˜Lš
œ0˜0Lš
œS˜S—Lšžœ
˜Lš
œ&˜&Lš
œ˜—Lšžœžœ
˜—Lšžœ
˜Lš
œΤ™ΤLšžœž˜ Lš
œ˜Lš
œ%˜%Lš
œ3˜3Lš
œ%˜%Lšžœϊ
˜Lšœ
žœ
˜Lš
œ˜šžœ2ž˜9Lš
œ0˜0—Lš
œ#˜#šžœžœ
žœž˜5Lš
œ˜Lš
œ0˜0Lš
œ>˜>Lš
œ2˜2Lš
œ@˜@Lšœžœ
˜Lšœžœ
˜Lšœžœ
˜Lšœžœ
˜ Lš
œ˜Lš
œ"˜"—Lšžœ
˜Lšœ)žœ
˜/Lš
œ˜L˜Lš
œ˜—Lšœ	žœžœ
˜Lšœžœžœ
˜"šŸœžœ
žœRžœ˜–
Lš
œΑ™ΑLš
œ±™±Lš
œ&˜&Lš
œ˜šžœžœ
žœž˜Lšžœ
žœ
ž˜š
œ˜Lš
œ˜Lšžœ
žœ0žœ
žœ
˜@Lš
œ,˜,šžœžœ
žœž˜Lš
œ0˜0Lš
œS˜S—Lšžœ
˜Lš
œ&˜&Lš
œ˜—š
œ˜Lš
œ˜Lšžœ
žœ0žœ
žœ
˜@Lš
œ/˜/šžœžœ˜Lš
œ0˜0Lš
œQ˜QLš
œ˜—Lš
œ%˜%Lš
œ˜—š
œ˜Lš
œ˜Lšžœ
žœ0žœ
žœ
˜@Lš
œ/˜/šžœžœ
žœž˜Lš
œ0˜0Lš
œS˜S—Lšžœ
˜Lš
œ&˜&Lš
œ˜—Lšžœžœ
˜—Lšžœ˜Lš
œα™αLšžœž˜ Lš
œ˜Lš
œ%˜%š
œ€
˜€
Lš
œ.™.Lš
œ™Lš
œ˜Lš
œ0˜0Lš
œ˜Lšœžœžœ
˜5Lš
œ2˜2Lš
œ˜Lš
œ˜—Lšžœ˜Lš
œς
™ς
Lšœ
žœ
˜Lš
œ˜šžœ2ž˜9Lš
œ0˜0—Lš
œ#˜#šžœžœ
žœž˜5Lš
œ˜Lš
œ0˜0Lš
œ>˜>Lš
œ2˜2Lš
œ@˜@Lšœžœ
˜Lšœžœ
˜Lšœžœ
˜Lšœžœ
˜ Lš
œ˜Lš
œ"˜"—Lšžœ
˜Lšœ)žœ
˜/Lš
œ˜L˜Lš
œ!˜!L˜—L˜šŸ
œžœ
žœžœžœžœ	žœ˜vLšœ	žœ
˜L˜L˜Lš
œ%˜%Lšžœžœ
žœ ž˜/Lšžœ2žœ˜:Lš
œ˜Lš
œ˜Lš
œ8˜8šžœžœ˜Lšœ
žœ
žœ
˜"—šžœ˜Lšœ
žœžœ˜—Lšžœ
˜Lšœ
žœ
˜Lš
œ˜L˜—šŸ
œžœ
žœžœžœžœ˜^Lšžœžœ
žœS˜kšžœž˜$Lšžœ}˜ƒ
—Lšžœ^žœ`˜Η
Lš
œ˜L˜—šŸœžœ
žœžœžœžœžœ˜TLš
œD™DLš
œF™FLš
œ™Lš
œ™Lš
œ)™)Lšœ	žœ
˜Lš
œ˜Lš
œ˜Lš
œ%˜%Lšœ
žœ
˜Lšžœžœ
žœ"˜GLš
œ˜šžœžœ˜Lš
œ˜Lš
œ˜Lšžœžœžœ
˜)Lš
œ˜—Lš
œ˜—Lš
œ
˜
L˜šŸœžœ
žœ
žœžœžœ˜ALšžœ˜Lš
œ˜—šŸœžœ
žœ
žœžœžœ˜BLšžœ˜Lš
œ˜—šŸœžœ
žœžœ˜ALš
œ<™<Lš
œ%˜%šžœžœ
žœž˜%Lš
œ ˜ —Lšžœ
˜Lš
œB˜BLš
œ˜Lš
œ˜L˜—š
Ÿ	œžœ
žœžœžœ˜FLš
œ>™>Lš
œ˜Lš
œ
˜
Lš
œ˜Lšœžœ
˜L˜Lšœžœ"˜2Lš
œ#˜#Lš
œB˜Bš
œI˜ILš
œ5™5—Lšžœ˜Lšœ ˜L˜—šŸœžœ˜)Lš
œ˜šžœžœ
žœž˜!šžœžœ
žœž˜!Lšžœ-žœ˜5Lš
œ˜Lš
œ ˜ Lš
œ˜—Lšžœ
˜—Lšžœ
˜Lš
œ˜—šŸœžœ˜+Lš
œ˜šžœžœ
žœž˜!šžœžœ
žœž˜!Lšžœ-žœ˜5Lš
œ˜Lš
œ ˜ Lš
œ˜—Lšžœ
˜—Lšžœ
˜Lš
œ˜—š
Ÿœžœžœžœžœ˜&Lšžœ
žœžœžœ˜!Lš
œ˜—šŸœžœ
žœžœ˜FLš
œ˜Lš
œ˜Lš
œ˜—šŸœžœ
žœžœ˜WLš
œ—
™—
Lš
œ˜Lš
œ˜Lš
œ4˜4Lš
œ™šžœžœ
žœž˜ Lš
œY˜Y—Lšžœ
˜Lš
œ™Lšœžœ ˜+Lš
œ˜Lš
œ˜Lš
œ<˜<šžœžœ
žœž˜ Lš
œ2˜2Lš
œ8˜8Lš
œX˜XLš
œ˜Lš
œ˜—Lšžœ
˜Lš
œ˜—šŸœžœ
žœžœ˜[Lš
œ‰™‰Lš
œ˜Lšœ
žœ˜)Lš
œ˜Lšœžœ/˜:Lš
œ&˜&Lš
œ™Lš
œ9˜9Lš
œ?˜?Lš
œ0˜0šžœžœ
žœžœ˜FLš
œ9˜9Lš
œ8˜8Lšžœž˜š
œ˜Lš
œ2˜2—šžœ
žœžœžœ˜GLš
œ.˜.—Lš
œ˜Lš
œ2˜2Lšžœžœ
˜Lš
œ˜—Lšžœ
˜Lš
œ™Lš
œ?˜?Lš
œF˜FLš
œ˜Lš
œ˜—š
Ÿœžœ
žœ'žœžœ˜yLš
ϣ
™£
Lš
œL™LLš
œ™Lšœžœ
˜Lš
œ'˜'L˜L˜Lš
œ*˜*Lš
œ%˜%Lš
œ
˜
Lšžœžœžœ˜:Lš
œ˜Lšžœžœžœ˜*Lš
œ˜Lš
œ˜Lš
œ7˜7šžœžœžœ˜,Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ
˜
—Lšžœ˜Lš
œ˜—L˜L˜šŸœžœ˜Lšœžœ˜&Lš
œ˜šžœžœ
žœ#ž˜2Lšœžœ˜-—Lšžœ
˜Lšœžœ˜$Lš
œ˜šžœžœ
žœ ž˜/Lšœžœ˜+—Lšžœ
˜Lš
œ˜—L˜Lš
œ˜L˜Lšžœ
˜—…—H.yP