File: SVSlicesImpl.mesa
Last edited by: Eric Bier on August 1, 1985 6:05:15 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
CastRays,
CoordSys,
CSG,
CSGGraphics,
Imager,
Matrix3d,
PadGraphics,
Preprocess3d,
SV2d,
SV3d,
SVError,
SVModelTypes,
SVRayTypes,
SVSceneTypes,
SVSlices;
SVSlicesImpl:
CEDAR
PROGRAM
IMPORTS CastRays, CoordSys, CSG, CSGGraphics, Matrix3d, PadGraphics, Preprocess3d, SVError
EXPORTS SVSlices =
BEGIN
Camera: TYPE = SVModelTypes.Camera;
Classification: TYPE = SVRayTypes.Classification;
CSGTree: TYPE = SVRayTypes.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 = SVRayTypes.Ray;
Vector: TYPE = SV3d.Vector;
SliceScanLine: TYPE = REF SliceScanLineObj;
SliceScanLineObj:
TYPE = SVSlices.SliceScanLineObj;
Slice: TYPE = REF SliceObj;
SliceObj: TYPE = SVSlices.SliceObj;
CreateSlice:
PUBLIC
PROC [maxScans:
NAT, coordSys: CoordSystem, frame: FrameBlock, plane: NAT]
RETURNS [slice: Slice] = {
slice ← NEW[SliceObj[maxScans]];
slice.coordSys ← coordSys;
slice.frame ← frame;
slice.plane ← plane;
FOR i:
NAT
IN [0..maxScans)
DO
slice[i] ← NEW[SliceScanLineObj];
ENDLOOP;
};
UpdateSlice:
PUBLIC PROC [slice: Slice, coordSys: CoordSystem, frame: FrameBlock, plane: NAT] = {
slice.coordSys ← coordSys;
slice.frame ← frame;
slice.plane ← plane;
};
ChangeSlicePlane:
PUBLIC PROC [slice: Slice, plane:
NAT] = {
slice.plane ← plane;
};
AddScanLineToSlice:
PRIVATE
PROC [scanLine:
NAT, class: Classification, localBasePt: Point3d, localDirection: Vector, slice: Slice]
RETURNS [modified: Slice] = {
FOR i:
NAT
IN [1..class.count]
DO
t: REAL;
t ← class.params[i];
slice[scanLine].hits[i][1] ← localBasePt[1] + t*localDirection[1];
slice[scanLine].hits[i][2] ← localBasePt[2] + t*localDirection[2];
slice[scanLine].hits[i][3] ← localBasePt[3] + t*localDirection[3];
slice[scanLine].classifs[i] ← class.classifs[i];
ENDLOOP;
slice[scanLine].count ← class.count;
slice[scanLine].classifs[class.count+1] ← class.classifs[class.count+1];
RETURN[slice];
};
RayTraceTheSlice:
PUBLIC
PROC [slice: Slice, tree: CSGTree, camera: Camera] =
TRUSTED {
y, z: REAL;
inc: REAL;
block: FrameBlock ← slice.frame;
basePt, worldBasePt: Point3d;
direction, worldDirection: Vector;
ray: Ray;
class: Classification;
localWRTCamera, localWRTWorld: Matrix4by4;
[] ← Preprocess3d.PreprocessForSlice[tree, camera];
localWRTCamera ← CoordSys.FindInTermsOfCamera[slice.coordSys, camera.coordSys];
localWRTWorld ← CoordSys.FindInTermsOfWorld[slice.coordSys];
ray ← CSG.GetRayFromPool[];
SELECT slice.plane FROM
1 => { -- x = 0 plane. Start rays from hi Z.
y ← block.loY;
inc ← (block.hiY - block.loY) / (slice.maxScans - 1.0);
direction ← [0.0, 0.0, block.loZ - block.hiZ];
worldDirection ← Matrix3d.UpdateVectorEvenScaling[localWRTWorld, direction];
FOR i:
NAT
IN [0..slice.maxScans)
DO
basePt ← [0.0, y, block.hiZ];
worldBasePt ← Matrix3d.Update[localWRTWorld, basePt];
CSG.StuffWorldRay[ray, worldBasePt, worldDirection, camera];
class ← CastRays.RayCastBoundingSpheres[ray, tree.son];
slice ← AddScanLineToSlice[i, class, basePt, direction, slice];
CastRays.ReturnClassToPool[class];
slice[i].lineVal ← y;
y ← y + inc;
ENDLOOP;
};
2 => { -- y = 0 plane. Start rays from lo X.
z ← block.loZ;
inc ← (block.hiZ - block.loZ) / (slice.maxScans - 1.0);
direction ← [block.hiX - block.loX, 0.0, 0.0];
worldDirection ← Matrix3d.UpdateVectorEvenScaling[localWRTWorld, direction];
FOR i:
NAT
IN [0..slice.maxScans)
DO
basePt ← [block.loX, 0.0, z];
worldBasePt ← Matrix3d.Update[localWRTWorld, basePt];
CSG.StuffWorldRay[ray, worldBasePt, worldDirection, camera];
class ← CastRays.RayCastBoundingSpheres[ray, tree.son];
slice ← AddScanLineToSlice[i, class, basePt, direction, slice];
CastRays.ReturnClassToPool[class];
slice[i].lineVal ← z;
z ← z + inc;
ENDLOOP;
};
3 => { -- z = 0 plane. Start rays from lo X.
y ← block.loY;
inc ← (block.hiY - block.loY) / (slice.maxScans - 1.0);
direction ← [block.hiX - block.loX, 0.0, 0.0];
worldDirection ← Matrix3d.UpdateVectorEvenScaling[localWRTWorld, direction];
FOR i:
NAT
IN [0..slice.maxScans)
DO
basePt ← [block.loX, y, 0.0];
worldBasePt ← Matrix3d.Update[localWRTWorld, basePt];
CSG.StuffWorldRay[ray, worldBasePt, worldDirection, camera];
class ← CastRays.RayCastBoundingSpheres[ray, tree.son];
slice ← AddScanLineToSlice[i, class, basePt, direction, slice];
CastRays.ReturnClassToPool[class];
slice[i].lineVal ← y;
y ← y + inc;
ENDLOOP;
};
ENDCASE => ERROR SVError.NotYetImplemented;
CSG.ReturnRayToPool[ray];
ClipSliceAgainstFrame[slice];
WidthAndHeight:
PUBLIC
PROC [slice: Slice]
RETURNS [width, height:
REAL] = {
f: FrameBlock ← slice.frame;
SELECT slice.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 [slice: Slice, i:
NAT] = {
FOR j:
NAT ← slice[i].count, j-1
UNTIL j < 1
DO
slice[i].hits[j+1] ← slice[i].hits[j];
slice[i].classifs[j+1] ← slice[i].classifs[j];
ENDLOOP;
ClipSliceAgainstFrame:
PRIVATE
PROC [slice: Slice] = {
Clip the scanlines represented by a slice against its own frame so they can be drawn in a straightforward manner.
startPt, endPt: Point3d;
block: FrameBlock ← slice.frame;
beenIn: BOOL;
SELECT slice.plane FROM
1 => {
FOR i:
NAT
IN [0..slice.maxScans)
DO
For each scan line...
beenIn ← FALSE;
startPt ← [0, slice[i].lineVal, block.hiZ];
An obscure way of saying "The point at the current y value, on the left border of the slice".
IF slice[i].classifs[1] =
TRUE
THEN { -- ray starts inside
beenIn ← TRUE;
ShiftScanLineUp[slice, i];
slice[i].hits[1] ← startPt;
slice[i].classifs[1] ← FALSE;
slice[i].count ← slice[i].count + 1;
};
FOR j:
NAT
IN [1..slice[i].count]
DO
endPt ← slice[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 {
slice[i].hits[j] ← [0, slice[i].lineVal, block.loZ];
slice[i].count ← j;
}
ELSE slice[i].count ← 0;
};
FINISHED => {
IF beenIn THEN {
IF slice[i].classifs[slice[i].count + 1] =
TRUE
THEN {
slice[i].count ← slice[i].count + 1;
slice[i].hits[slice[i].count] ← [0, slice[i].lineVal, block.loZ];
};
}
ELSE slice[i].count ← 0;
};
ENDLOOP;
ENDLOOP;
};
2 => {
FOR i:
NAT
IN [0..slice.maxScans)
DO
For each scan line...
beenIn ← FALSE;
startPt ← [block.loX, 0, slice[i].lineVal];
An obscure way of saying "The point at the current z value, on the left border of the slice".
IF slice[i].classifs[1] =
TRUE
THEN {
beenIn ← TRUE;
ShiftScanLineUp[slice, i];
slice[i].hits[1] ← startPt;
slice[i].classifs[1] ← FALSE;
slice[i].count ← slice[i].count + 1;
};
FOR j:
NAT
IN [1..slice[i].count]
DO
endPt ← slice[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 {
slice[i].hits[j] ← [block.hiX, 0, slice[i].lineVal];
slice[i].count ← j;
}
ELSE slice[i].count ← 0;
};
FINISHED => {
IF beenIn THEN {
IF slice[i].classifs[slice[i].count + 1] =
TRUE
THEN {
slice[i].count ← slice[i].count + 1;
slice[i].hits[slice[i].count] ← [block.hiX, 0, slice[i].lineVal];
};
}
ELSE slice[i].count ← 0;
};
ENDLOOP;
ENDLOOP;
};
3 => {
FOR i:
NAT
IN [0..slice.maxScans)
DO
For each scan line...
beenIn ← FALSE;
startPt ← [block.loX, slice[i].lineVal, 0];
An obscure way of saying "The point at the current y value, on the left border of the slice".
IF slice[i].classifs[1] =
TRUE
THEN {
beenIn ← TRUE;
ShiftScanLineUp[slice, i];
slice[i].hits[1] ← startPt;
slice[i].classifs[1] ← FALSE;
slice[i].count ← slice[i].count + 1;
};
FOR j:
NAT
IN [1..slice[i].count]
DO
endPt ← slice[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 {
slice[i].hits[j] ← [block.hiX, slice[i].lineVal, 0];
slice[i].count ← j;
}
ELSE slice[i].count ← 0;
};
FINISHED => {
IF beenIn THEN {
IF slice[i].classifs[slice[i].count + 1] =
TRUE
THEN {
slice[i].count ← slice[i].count + 1;
slice[i].hits[slice[i].count] ← [block.hiX, slice[i].lineVal, 0];
};
}
ELSE slice[i].count ← 0;
};
ENDLOOP;
ENDLOOP;
};
ENDCASE => ERROR;
};
DrawSlice:
PUBLIC
PROC [dc: Imager.Context, slice: Slice, origin: Point2d] =
TRUSTED {
Draw the slice in a 2d window such as the scratchpad.
Think of the slice as a sequence of black stripes of width 1 screen scanline.
startPtLocal, endPtLocal: Point3d;
startPad, endPad: Point2d;
SELECT slice.plane FROM
1 => {
-- x=0 plane
FOR i:
NAT
IN [0..slice.maxScans)
DO
For each scan line...
FOR j:
NAT
IN [2..slice[i].count]
DO
For each potential endPtLocal...
IF slice[i].classifs[j]
THEN {
startPtLocal ← slice[i].hits[j-1];
endPtLocal ← slice[i].hits[j];
startPad ← [-startPtLocal[3], startPtLocal[2]];
endPad ← [-endPtLocal[3], endPtLocal[2]];
PadGraphics.MoveTo[dc, startPad, origin];
PadGraphics.DrawTo[dc, endPad, origin];
};
ENDLOOP;
ENDLOOP;
};
2 => {
-- y = 0 plane
FOR i:
NAT
IN [0..slice.maxScans)
DO
For each scan line...
FOR j:
NAT
IN [2..slice[i].count]
DO
For each potential endPtLocal...
IF slice[i].classifs[j]
THEN {
startPtLocal ← slice[i].hits[j-1];
endPtLocal ← slice[i].hits[j];
startPad ← [startPtLocal[1], -startPtLocal[3]];
endPad ← [endPtLocal[1], -endPtLocal[3]];
PadGraphics.MoveTo[dc, startPad, origin];
PadGraphics.DrawTo[dc, endPad, origin];
};
ENDLOOP;
ENDLOOP;
};
3, 4 => {
FOR i:
NAT
IN [0..slice.maxScans)
DO
For each scan line...
FOR j:
NAT
IN [2..slice[i].count]
DO
For each potential endPtLocal...
IF slice[i].classifs[j]
THEN {
startPtLocal ← slice[i].hits[j-1];
endPtLocal ← slice[i].hits[j];
startPad ← [startPtLocal[1], startPtLocal[2]];
endPad ← [endPtLocal[1], endPtLocal[2]];
PadGraphics.MoveTo[dc, startPad, origin];
PadGraphics.DrawTo[dc, endPad, origin];
};
ENDLOOP;
ENDLOOP;
};
ENDCASE => ERROR;
};
DrawSliceAlternate: PRIVATE PROC [dc: Imager.Context, slice: Slice, origin: Point2d] = TRUSTED {
Draw the slice in a 2d window such as the scratchpad.
Think of the slice as a sequence of black stripes of width 1 screen scanline.
startPtLocal, endPtLocal: Point3d;
startPad, endPad: Point2d;
FOR i: NAT IN [0..slice.maxScans) DO
FOR j: NAT ← 1, j+2 UNTIL j +1> slice[i].count DO
startPtLocal ← slice[i].hits[j];
endPtLocal ← slice[i].hits[j+1];
startPad ← [startPtLocal[1], startPtLocal[2]];
endPad ← [endPtLocal[1], endPtLocal[2]];
PadGraphics.MoveTo[dc, startPad, origin];
PadGraphics.DrawTo[dc, endPad, origin];
ENDLOOP;
ENDLOOP;
DrawSlice3d:
PUBLIC
PROC [dc: Imager.Context, slice: Slice, camera: Camera] =
TRUSTED {
Draw the outline of the slice in with a set of solid objects. Like DrawSlice except that points we use CSGGraphics type procdures to project the lines onto a given viewer's screen.
startPtLocal, endPtLocal: Point3d;
FOR i:
NAT
IN [0..slice.maxScans)
DO
FOR j:
NAT
IN [2..slice[i].count]
DO
IF slice[i].classifs[j]
THEN {
startPtLocal ← slice[i].hits[j-1];
endPtLocal ← slice[i].hits[j];
CSGGraphics.DrawLine[dc, startPtLocal, endPtLocal, camera, slice.coordSys];
};
ENDLOOP;
ENDLOOP;
END.