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.