File: SVCatScanImpl.mesa
Last edited by: Eric Bier on August 7, 1987 1:48:29 pm PDT
Copyright © 1984 by Xerox Corporation. All rights reserved.
Contents: A scanline data structure representing a ray-traced slice thru a 3D scene. Can be shown in 3D by drawing the endpoints in perspective or in 2D by rotating the slicing plane into the viewing plane.
DIRECTORY
SVCastRays, SVCoordSys, SVRay, SVGraphics, Feedback, Imager, SVMatrix3d, SVPadGraphics, SVPreprocess3d, SV2d, SV3d, SVModelTypes, SVSceneTypes, SVCatScan;
SVCatScanImpl:
CEDAR
PROGRAM
IMPORTS SVCastRays, SVCoordSys, SVRay, SVGraphics, Feedback, SVMatrix3d, SVPadGraphics, SVPreprocess3d
EXPORTS SVCatScan =
BEGIN
Camera: TYPE = SVModelTypes.Camera;
Classification: TYPE = SVSceneTypes.Classification;
CSGTree: TYPE = SVSceneTypes.CSGTree;
CoordSystem: TYPE = SVModelTypes.CoordSystem;
FrameBlock: TYPE = SVSceneTypes.FrameBlock;
Matrix4by4: TYPE = SV3d.Matrix4by4;
Plane: TYPE = SV3d.Plane;
Point2d: TYPE = SV2d.Point2d;
Point3d: TYPE = SV3d.Point3d;
Ray: TYPE = SVSceneTypes.Ray;
Vector3d: TYPE = SV3d.Vector3d;
CatScanScanLine: TYPE = REF CatScanScanLineObj;
CatScanScanLineObj:
TYPE = SVCatScan.CatScanScanLineObj;
CatScan: TYPE = REF CatScanObj;
CatScanObj: TYPE = SVCatScan.CatScanObj;
CreateCatScan:
PUBLIC
PROC [maxScans:
NAT, coordSys: CoordSystem, frame: FrameBlock, plane:
NAT]
RETURNS [catScan: CatScan] = {
catScan ← NEW[CatScanObj[maxScans]];
catScan.coordSys ← coordSys;
catScan.frame ← frame;
catScan.plane ← plane;
FOR i:
NAT
IN [0..maxScans)
DO
catScan[i] ← NEW[CatScanScanLineObj];
ENDLOOP;
};
UpdateCatScan:
PUBLIC
PROC [catScan: CatScan, coordSys: CoordSystem, frame: FrameBlock, plane:
NAT] = {
catScan.coordSys ← coordSys;
catScan.frame ← frame;
catScan.plane ← plane;
};
ChangeCatScanPlane:
PUBLIC
PROC [catScan: CatScan, plane:
NAT] = {
catScan.plane ← plane;
};
AddScanLineToCatScan:
PRIVATE
PROC [scanLine:
NAT, class: Classification, localBasePt: Point3d, localDirection: Vector3d, catScan: CatScan]
RETURNS [modified: CatScan] = {
FOR i:
NAT
IN [1..class.count]
DO
t: REAL;
t ← class.params[i];
catScan[scanLine].hits[i][1] ← localBasePt[1] + t*localDirection[1];
catScan[scanLine].hits[i][2] ← localBasePt[2] + t*localDirection[2];
catScan[scanLine].hits[i][3] ← localBasePt[3] + t*localDirection[3];
catScan[scanLine].classifs[i] ← class.classifs[i];
ENDLOOP;
catScan[scanLine].count ← class.count;
catScan[scanLine].classifs[class.count+1] ← class.classifs[class.count+1];
RETURN[catScan];
};
RayTraceTheCatScan:
PUBLIC
PROC [catScan: CatScan, tree: CSGTree, camera: Camera] = {
y, z: REAL;
inc: REAL;
block: FrameBlock ← catScan.frame;
basePt, worldBasePt: Point3d;
direction, worldDirection: Vector3d;
ray: Ray;
class: Classification;
localWRTCamera, localWRTWorld: Matrix4by4;
[] ← SVPreprocess3d.PreprocessForCatScan[tree, camera];
localWRTCamera ← SVCoordSys.WRTCamera[catScan.coordSys, camera.coordSys];
localWRTWorld ← SVCoordSys.WRTWorld[catScan.coordSys];
ray ← SVRay.GetRayFromPool[];
SELECT catScan.plane FROM
1 => {
-- x = 0 plane. Start rays from hi Z.
y ← block.loY;
inc ← (block.hiY - block.loY) / (catScan.maxScans - 1.0);
direction ← [0.0, 0.0, block.loZ - block.hiZ];
worldDirection ← SVMatrix3d.UpdateVectorEvenScaling[direction, localWRTWorld];
FOR i:
NAT
IN [0..catScan.maxScans)
DO
basePt ← [0.0, y, block.hiZ];
worldBasePt ← SVMatrix3d.Update[basePt, localWRTWorld];
SVRay.StuffWorldRay[ray, worldBasePt, worldDirection, camera];
class ← SVCastRays.RayCastBoundingSpheres[ray, tree.son];
catScan ← AddScanLineToCatScan[i, class, basePt, direction, catScan];
SVCastRays.ReturnClassToPool[class];
catScan[i].lineVal ← y;
y ← y + inc;
ENDLOOP;
};
2 => {
-- y = 0 plane. Start rays from lo X.
z ← block.loZ;
inc ← (block.hiZ - block.loZ) / (catScan.maxScans - 1.0);
direction ← [block.hiX - block.loX, 0.0, 0.0];
worldDirection ← SVMatrix3d.UpdateVectorEvenScaling[direction, localWRTWorld];
FOR i:
NAT
IN [0..catScan.maxScans)
DO
basePt ← [block.loX, 0.0, z];
worldBasePt ← SVMatrix3d.Update[basePt, localWRTWorld];
SVRay.StuffWorldRay[ray, worldBasePt, worldDirection, camera];
class ← SVCastRays.RayCastBoundingSpheres[ray, tree.son];
catScan ← AddScanLineToCatScan[i, class, basePt, direction, catScan];
SVCastRays.ReturnClassToPool[class];
catScan[i].lineVal ← z;
z ← z + inc;
ENDLOOP;
};
3 => {
-- z = 0 plane. Start rays from lo X.
y ← block.loY;
inc ← (block.hiY - block.loY) / (catScan.maxScans - 1.0);
direction ← [block.hiX - block.loX, 0.0, 0.0];
worldDirection ← SVMatrix3d.UpdateVectorEvenScaling[direction, localWRTWorld];
FOR i:
NAT
IN [0..catScan.maxScans)
DO
basePt ← [block.loX, y, 0.0];
worldBasePt ← SVMatrix3d.Update[basePt, localWRTWorld];
SVRay.StuffWorldRay[ray, worldBasePt, worldDirection, camera];
class ← SVCastRays.RayCastBoundingSpheres[ray, tree.son];
catScan ← AddScanLineToCatScan[i, class, basePt, direction, catScan];
SVCastRays.ReturnClassToPool[class];
catScan[i].lineVal ← y;
y ← y + inc;
ENDLOOP;
};
ENDCASE => ERROR Feedback.Problem["All three is not yet implemented"];
SVRay.ReturnRayToPool[ray];
ClipCatScanAgainstFrame[catScan];
WidthAndHeight:
PUBLIC
PROC [catScan: CatScan]
RETURNS [width, height:
REAL] = {
f: FrameBlock ← catScan.frame;
SELECT catScan.plane FROM
1 => {
-- x = 0 plane. y top to bottom. z left to right.
width ← f.hiZ - f.loZ;
height ← f.hiY - f.loY;
};
2 => {
-- y = 0 plane. z top to bottom. x left to right.
width ← f.hiX - f.loX;
height ← f.hiZ - f.loZ;
};
3, 4 => {
-- z = 0 plane. y top to bottom. x left to right.
width ← f.hiX - f.loX;
height ← f.hiY - f.loY;
};
ENDCASE => ERROR;
ShiftScanLineUp:
PRIVATE
PROC [catScan: CatScan, i:
NAT] = {
FOR j:
NAT ← catScan[i].count, j-1
UNTIL j < 1
DO
catScan[i].hits[j+1] ← catScan[i].hits[j];
catScan[i].classifs[j+1] ← catScan[i].classifs[j];
ENDLOOP;
ClipCatScanAgainstFrame:
PRIVATE
PROC [catScan: CatScan] = {
Clip the scanlines represented by a catScan against its own frame so they can be drawn in a straightforward manner.
startPt, endPt: Point3d;
block: FrameBlock ← catScan.frame;
beenIn: BOOL;
SELECT catScan.plane FROM
1 => {
FOR i:
NAT
IN [0..catScan.maxScans)
DO
For each scan line...
beenIn ← FALSE;
startPt ← [0, catScan[i].lineVal, block.hiZ];
An obscure way of saying "The point at the current y value, on the left border of the catScan".
IF catScan[i].classifs[1] =
TRUE
THEN {
-- ray starts inside
beenIn ← TRUE;
ShiftScanLineUp[catScan, i];
catScan[i].hits[1] ← startPt;
catScan[i].classifs[1] ← FALSE;
catScan[i].count ← catScan[i].count + 1;
};
FOR j:
NAT
IN [1..catScan[i].count]
DO
endPt ← catScan[i].hits[j];
IF endPt[3] > block.loZ AND endPt[3] < block.hiZ THEN beenIn ← TRUE;
IF endPt[3] < block.loZ THEN GOTO EndOfScanline;
REPEAT
EndOfScanline => {
-- use this point instead of the out of bounds one
IF beenIn
THEN {
catScan[i].hits[j] ← [0, catScan[i].lineVal, block.loZ];
catScan[i].count ← j;
}
ELSE catScan[i].count ← 0;
};
FINISHED => {
IF beenIn
THEN {
IF catScan[i].classifs[catScan[i].count + 1] =
TRUE
THEN {
catScan[i].count ← catScan[i].count + 1;
catScan[i].hits[catScan[i].count] ← [0, catScan[i].lineVal, block.loZ];
};
}
ELSE catScan[i].count ← 0;
};
ENDLOOP;
ENDLOOP;
};
2 => {
FOR i:
NAT
IN [0..catScan.maxScans)
DO
For each scan line...
beenIn ← FALSE;
startPt ← [block.loX, 0, catScan[i].lineVal];
An obscure way of saying "The point at the current z value, on the left border of the catScan".
IF catScan[i].classifs[1] =
TRUE
THEN {
beenIn ← TRUE;
ShiftScanLineUp[catScan, i];
catScan[i].hits[1] ← startPt;
catScan[i].classifs[1] ← FALSE;
catScan[i].count ← catScan[i].count + 1;
};
FOR j:
NAT
IN [1..catScan[i].count]
DO
endPt ← catScan[i].hits[j];
IF endPt[1] < block.hiX AND endPt[1] > block.loX THEN beenIn ← TRUE;
IF endPt[1] > block.hiX THEN GOTO EndOfScanline;
REPEAT
EndOfScanline => {
IF beenIn
THEN {
catScan[i].hits[j] ← [block.hiX, 0, catScan[i].lineVal];
catScan[i].count ← j;
}
ELSE catScan[i].count ← 0;
};
FINISHED => {
IF beenIn
THEN {
IF catScan[i].classifs[catScan[i].count + 1] =
TRUE
THEN {
catScan[i].count ← catScan[i].count + 1;
catScan[i].hits[catScan[i].count] ← [block.hiX, 0, catScan[i].lineVal];
};
}
ELSE catScan[i].count ← 0;
};
ENDLOOP;
ENDLOOP;
};
3 => {
FOR i:
NAT
IN [0..catScan.maxScans)
DO
For each scan line...
beenIn ← FALSE;
startPt ← [block.loX, catScan[i].lineVal, 0];
An obscure way of saying "The point at the current y value, on the left border of the catScan".
IF catScan[i].classifs[1] =
TRUE
THEN {
beenIn ← TRUE;
ShiftScanLineUp[catScan, i];
catScan[i].hits[1] ← startPt;
catScan[i].classifs[1] ← FALSE;
catScan[i].count ← catScan[i].count + 1;
};
FOR j:
NAT
IN [1..catScan[i].count]
DO
endPt ← catScan[i].hits[j];
IF endPt[1] < block.hiX AND endPt[1] > block.loX THEN beenIn ← TRUE;
IF endPt[1] > block.hiX THEN GOTO EndOfScanline;
REPEAT
EndOfScanline => {
IF beenIn
THEN {
catScan[i].hits[j] ← [block.hiX, catScan[i].lineVal, 0];
catScan[i].count ← j;
}
ELSE catScan[i].count ← 0;
};
FINISHED => {
IF beenIn
THEN {
IF catScan[i].classifs[catScan[i].count + 1] =
TRUE
THEN {
catScan[i].count ← catScan[i].count + 1;
catScan[i].hits[catScan[i].count] ← [block.hiX, catScan[i].lineVal, 0];
};
}
ELSE catScan[i].count ← 0;
};
ENDLOOP;
ENDLOOP;
};
ENDCASE => ERROR;
};
DrawCatScan:
PUBLIC
PROC [dc: Imager.Context, catScan: CatScan, origin: Point2d] =
TRUSTED {
Draw the catScan in a 2d window such as the scratchpad.
Think of the catScan as a sequence of black stripes of width 1 screen scanline.
startPtLocal, endPtLocal: Point3d;
startPad, endPad: Point2d;
SELECT catScan.plane FROM
1 => {
-- x=0 plane
FOR i:
NAT
IN [0..catScan.maxScans)
DO
For each scan line...
FOR j:
NAT
IN [2..catScan[i].count]
DO
For each potential endPtLocal...
IF catScan[i].classifs[j]
THEN {
startPtLocal ← catScan[i].hits[j-1];
endPtLocal ← catScan[i].hits[j];
startPad ← [-startPtLocal[3], startPtLocal[2]];
endPad ← [-endPtLocal[3], endPtLocal[2]];
SVPadGraphics.MoveTo[dc, startPad, origin];
SVPadGraphics.DrawTo[dc, endPad, origin];
};
ENDLOOP;
ENDLOOP;
};
2 => {
-- y = 0 plane
FOR i:
NAT
IN [0..catScan.maxScans)
DO
For each scan line...
FOR j:
NAT
IN [2..catScan[i].count]
DO
For each potential endPtLocal...
IF catScan[i].classifs[j]
THEN {
startPtLocal ← catScan[i].hits[j-1];
endPtLocal ← catScan[i].hits[j];
startPad ← [startPtLocal[1], -startPtLocal[3]];
endPad ← [endPtLocal[1], -endPtLocal[3]];
SVPadGraphics.MoveTo[dc, startPad, origin];
SVPadGraphics.DrawTo[dc, endPad, origin];
};
ENDLOOP;
ENDLOOP;
};
3, 4 => {
FOR i:
NAT
IN [0..catScan.maxScans)
DO
For each scan line...
FOR j:
NAT
IN [2..catScan[i].count]
DO
For each potential endPtLocal...
IF catScan[i].classifs[j]
THEN {
startPtLocal ← catScan[i].hits[j-1];
endPtLocal ← catScan[i].hits[j];
startPad ← [startPtLocal[1], startPtLocal[2]];
endPad ← [endPtLocal[1], endPtLocal[2]];
SVPadGraphics.MoveTo[dc, startPad, origin];
SVPadGraphics.DrawTo[dc, endPad, origin];
};
ENDLOOP;
ENDLOOP;
};
ENDCASE => ERROR;
};
DrawCatScanAlternate: PRIVATE PROC [dc: Imager.Context, catScan: CatScan, origin: Point2d] = TRUSTED {
Draw the catScan in a 2d window such as the scratchpad.
Think of the catScan as a sequence of black stripes of width 1 screen scanline.
startPtLocal, endPtLocal: Point3d;
startPad, endPad: Point2d;
FOR i: NAT IN [0..catScan.maxScans) DO
FOR j: NAT ← 1, j+2 UNTIL j +1> catScan[i].count DO
startPtLocal ← catScan[i].hits[j];
endPtLocal ← catScan[i].hits[j+1];
startPad ← [startPtLocal[1], startPtLocal[2]];
endPad ← [endPtLocal[1], endPtLocal[2]];
SVPadGraphics.MoveTo[dc, startPad, origin];
SVPadGraphics.DrawTo[dc, endPad, origin];
ENDLOOP;
ENDLOOP;
DrawCatScan3d:
PUBLIC
PROC [dc: Imager.Context, catScan: CatScan, camera: Camera] =
TRUSTED {
Draw the outline of the catScan in with a set of solid objects. Like DrawCatScan except that points we use SVGraphics type procdures to project the lines onto a given viewer's screen.
startPtLocal, endPtLocal: Point3d;
FOR i:
NAT
IN [0..catScan.maxScans)
DO
FOR j:
NAT
IN [2..catScan[i].count]
DO
IF catScan[i].classifs[j]
THEN {
startPtLocal ← catScan[i].hits[j-1];
endPtLocal ← catScan[i].hits[j];
SVGraphics.DrawLine[dc, startPtLocal, endPtLocal, camera, catScan.coordSys];
};
ENDLOOP;
ENDLOOP;
END.