CastRays,

CSG,

SV2d,

SV3d,

SVBoundBox,

SVFaces,

SVFacesCast,

SVLines2d,

SVPolygon2d,

SVPolygon3d,

SVRayTypes,

SweepCast,

SweepGeometry;

Classification: TYPE = SVRayTypes.Classification;

Plane: TYPE = SV3d.Plane;

Point2d: TYPE = SV2d.Point2d;

Point3d: TYPE = SV3d.Point3d;

Polygon: TYPE = SV2d.Polygon;

Primitive: TYPE = SVRayTypes.Primitive;

Ray: TYPE = SVRayTypes.Ray;

Vector: TYPE = SV3d.Vector;

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;

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.

poly: Polygon;

faceHit: FaceHitRec;

class ← CastRays.GetClassFromPool[];

globalLinHits.count ← 0;

do 2 ray-xyPolygon tests.

front face;

poly ← faces.poly;

faceHit ← RayXYPolygon[localRay, poly, linMesh.array[1][1][3], [0, 0, 1]];

IF faceHit.count = 1 THEN {

SVFacesCast.ReturnFaceHitToPool[faceHit];

back face

faceHit ← RayXYPolygon[localRay, poly, linMesh.array[1][2][3], [0, 0, -1]];

IF faceHit.count = 1 THEN {

SVFacesCast.ReturnFaceHitToPool[faceHit];

do ray-edgeOnRectangle tests

FOR i: NAT IN [0..faces.len) DO

faceHit ← SVFacesCast.EdgeOnRectCast[faces[i], localRay];

IF faceHit.count = 1 THEN {

SVFacesCast.ReturnFaceHitToPool[faceHit];

ENDLOOP;

now combine the results

SELECT globalLinHits.count FROM

0 => { -- miss.

CastRays.MakeClassAMiss[class]};

1 => {

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, see if the ray starts inside of the solid. If so, proceed. Otherwise, ignore the last one.

iPlusOne: NAT;

startI: NAT ← 1;

SortLinHits[globalLinHits];

IF (globalLinHits.count/2)*2 # globalLinHits.count THEN { -- odd number of hits

class.count ← globalLinHits.count;

FOR i: NAT ← startI, i+2 UNTIL i > globalLinHits.count DO

ENDLOOP;

class.classifs[globalLinHits.count+1] ← FALSE;

}; -- end of 2 or more hits

}; -- end of LinCast

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.

class ← CastRays.GetClassFromPool[];

globalRevoHits.count ← 0;

FOR i: NAT IN[0..faces.len) DO

ENDLOOP;-- next face

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.

SELECT globalRevoHits.count FROM

0 => {-- miss.

CastRays.MakeClassAMiss[class]};

1 => {-- ray just skims one face. Treat as a miss.

CastRays.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

class.count ← globalRevoHits.count;

FOR i: NAT ← 1, i+2 UNTIL i > globalRevoHits.count DO

ENDLOOP;

class.classifs[globalRevoHits.count+1] ← FALSE;

}; -- end of 2 or more hits

}; -- end of RevoCast

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.

class ← CastRays.GetClassFromPool[];

globalRevoHits.count ← 0;

FOR i: NAT IN[0..faces.len) DO

ENDLOOP;-- next face

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.

SELECT globalRevoHits.count FROM

0 => {-- miss.

CastRays.MakeClassAMiss[class]};

1 => {-- ray just skims one face. Treat as a miss.

CastRays.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

class.count ← globalRevoHits.count;

FOR i: NAT ← 1, i+2 UNTIL i > globalRevoHits.count DO

ENDLOOP;

class.classifs[globalRevoHits.count+1] ← FALSE;

}; -- end of 2 or more hits

}; -- end of RevoCast

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.

class ← CastRays.GetClassFromPool[];

globalRevoHits.count ← 0;

FOR i: NAT IN[0..faces.len) DO

ENDLOOP; -- next face

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.

SELECT globalRevoHits.count FROM

0 => {-- miss.

CastRays.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.

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

class.count ← globalRevoHits.count;

FOR i: NAT ← 1, i+2 UNTIL i > globalRevoHits.count DO

ENDLOOP;

class.classifs[globalRevoHits.count+1] ← FALSE;

}; -- end of 2 or more hits

}; -- end of RevoCastBoundSpheres

x, z, r: REAL;

p: Point3d;

d: Vector;

[p, d] ← CSG.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 {

ELSE {

ENDLOOP;

matches ← FALSE;

}; -- end of HitsACrack

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[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]]
];

};

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;

x, z, t: REAL;

p: Point3d;

d: Vector;

[p, d] ← CSG.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 {

}; -- end of HitsDisk

RETURN[Abs[t2-t1] < 1.0e-2];

};

RETURN[Abs[h2-h1] < 1.0];

};

Shift all elements above this one down and reduce count by 1

temp: RevoHitRec ← hits.array[index];

FOR i: NAT IN[index..hits.count-1] DO

ENDLOOP;

hits.array[hits.count] ← temp;-- replace the storage for later use

hits.count ← hits.count - 1;

}; -- end of DeleteFromHits

TRUE means the ray is entering the plane from the normal side.

hitPoint: Point3d;

plane: Plane;

basePt: Point3d;

basePtOnNormalSide: BOOL;

hitPoint ← CSG.EvaluateLocalRay[ray, hit.param];

[basePt,] ← CSG.GetLocalRay[ray];

plane ← SVPolygon3d.PlaneFromPointAndNormal[hitPoint, hit.normal];

basePtOnNormalSide ← SVPolygon3d.PointOnNormalSideOfPlane[basePt, plane];

RETURN[basePtOnNormalSide];

}; -- end of RayGoesIn

temp: LinHitRec;

FOR i: NAT IN[1..hits.count-1] DO

ENDLOOP;

};

temp: RevoHitRec;

FOR i: NAT IN[1..hits.count-1] DO

ENDLOOP;

};

RETURN[IF r >= 0 THEN r ELSE -r];

};

p2[1] ← p3[1];

p2[2] ← p3[2];

};

Interate through consequtive pairs of vertices of the front polygon of the linear mesh. Make linMesh.len faces using SVFaces.EdgeOnRectFromTrigLineSeg

lastPoint, thisPoint: Point2d;

seg: SV2d.TrigLineSeg;

poly: Polygon ← SVPolygon2d.CreatePoly[linMesh.len];

extract the defining polygon

FOR i: NAT IN[1..linMesh.len] DO

ENDLOOP;

Make the edge-on-rectangles

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

ENDLOOP;

};

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.

lastPoint, thisPoint: Point2d;

lastLong: NAT ← revMesh.linesOfLongitude;

seg: SV2d.TrigLineSeg;

faces ← NEW[RevoSweepFacesObj[revMesh.linesOfLatitude+1]];

faces.len ← revMesh.linesOfLatitude+1;

the top of a sweep is a disk

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

ENDLOOP;

The bottom face is a disk

seg ← SVLines2d.CreateTrigLineSeg[lastPoint, [0,lastPoint[2]]];

faces[revMesh.linesOfLatitude] ← SVFaces.DiskRingFromTrigLineSeg[seg];

faces.mesh ← revMesh;

};

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;

x, y, z, t: REAL;

pointClass: SVPolygon2d.PointPolyClass;

p: Point3d;

d: Vector;

linHit ← SVFacesCast.GetFaceHitFromPool[];

[p, d] ← CSG.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 {

ELSE linHit.count ← 0;

}; -- end of RayXYPolygon

globalRevoHits ← NEW[RevoHitArrayObj];

globalRevoHits.count ← 0;

FOR i: NAT IN[1..SweepGeometry.maxLinesOfLat+1] DO

ENDLOOP;

globalLinHits ← NEW[LinHitArrayObj];

globalLinHits.count ← 0;

FOR i: NAT IN[1..SweepGeometry.maxMeshLen-1] DO

ENDLOOP;

};