DIRECTORY
CastRays,
CoordSys,
CSG,
CSGGraphics,
Graphics,
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] = {
startPt, endPt: Point3d;
block: FrameBlock _ slice.frame;
beenIn: BOOL;
SELECT slice.plane FROM
1 => {
FOR i: NAT IN [0..slice.maxScans) DO
beenIn _ FALSE;
startPt _ [0, slice[i].lineVal, block.hiZ];
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
beenIn _ FALSE;
startPt _ [block.loX, 0, slice[i].lineVal];
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
beenIn _ FALSE;
startPt _ [block.loX, slice[i].lineVal, 0];
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 {
startPtLocal, endPtLocal: Point3d;
startPad, endPad: Point2d;
SELECT slice.plane FROM
1 => { -- x=0 plane
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];
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 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];
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 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];
startPad _ [startPtLocal[1], startPtLocal[2]];
endPad _ [endPtLocal[1], endPtLocal[2]];
PadGraphics.MoveTo[dc, startPad, origin];
PadGraphics.DrawTo[dc, endPad, origin];
};
ENDLOOP;
ENDLOOP;
};
ENDCASE => ERROR;
};

DrawSlice3d: PUBLIC PROC [dc: Graphics.Context, slice: Slice, camera: Camera] = TRUSTED {
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.

’File: SVSlicesImpl.mesa
Last edited by: Eric Bier on August 19, 1984 6:22:58 pm PDT
Copyright c 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.

Clip the scanlines represented by a slice against its own frame so they can be drawn in a straightforward manner.
For each scan line...
An obscure way of saying "The point at the current y value, on the left border of the slice".
For each scan line...
An obscure way of saying "The point at the current z value, on the left border of the slice".
For each scan line...
An obscure way of saying "The point at the current y value, on the left border of the slice".
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.
For each scan line...
For each potential endPtLocal...
For each scan line...
For each potential endPtLocal...
For each scan line...
For each potential endPtLocal...
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;
};


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.
Κ>˜Ihead™J™;Jšœ
Οm
œ1™<J™Ο
J™š
Οk	˜	Jš
œ	˜	Jš
œ	˜	Jšžœ
˜Jš
œ˜Jš
œ	˜	Jš
œ˜Jš
œ	˜	J˜J˜
Jš
œ˜Jš
œ˜J˜Jš
œ
˜
Jš
œ˜Jš
œ
˜
Jš
œ	˜	J˜—šœžœ
ž˜Jšžœžœ;˜ZJšžœ˜J˜—Jš
ž˜˜J˜Jšœžœ˜#Jšœžœ˜1Jšœ	žœ˜#Jšœ
žœ˜-Jšœžœ˜+Jšœžœ˜#Jšœžœ˜Jšœ	žœ˜Jšœ	žœ˜Jšœžœ˜Jšœžœ˜J˜Jšœžœžœ˜+šœžœ˜3J˜—Jšœžœžœ
˜Jšœ
žœ˜#J˜—š
Οnœžœ
žœžœ8žœ˜yJšœžœ˜ Jš
œ˜Jš
œ˜Jš
œ˜šžœžœ
žœž˜Jšœžœ˜!—Jšžœ
˜J˜J˜—šŸœžœI˜aJš
œ˜Jš
œ˜Jš
œ˜J˜J˜—šŸœžœžœ˜<Jš
œ˜J˜—J˜š
Ÿœžœ
žœžœUžœ˜‘
šžœžœ
žœž˜!Jšœžœ
˜Jš
œ˜Jš
œB˜BJš
œB˜BJš
œB˜BJš
œ0˜0—Jšžœ
˜Jš
œ$˜$Jš
œH˜HJšžœ˜J˜J˜—šŸœžœ
žœ1žœ˜WJšœžœ
˜J˜
Jš
œ ˜ J˜J˜"J˜	J˜J˜*J˜Jš
œ3˜3Jš
œO˜OJš
œ<˜<J˜Jšœžœ˜Jš
œ˜˜-Jš
œ˜Jš
œ7˜7Jš
œ.˜.Jš
œL˜Lšžœžœ
žœž˜$Jš
œ˜Jš
œ5˜5Jšžœ9˜<Jš
œ7˜7Jš
œ?˜?Jš
œ"˜"Jš
œ˜J˜—Jšžœ
˜J˜—˜-Jš
œ˜Jš
œ7˜7Jš
œ.˜.Jš
œL˜Lšžœžœ
žœž˜$Jš
œ˜Jš
œ5˜5Jšžœ9˜<Jš
œ7˜7Jš
œ?˜?Jš
œ"˜"Jš
œ˜Jš
œ˜—Jšžœ
˜Jš
œ˜—˜-Jš
œ˜Jš
œ7˜7Jš
œ.˜.Jš
œL˜Lšžœžœ
žœž˜$Jš
œ˜Jš
œ5˜5Jšžœ9˜<Jš
œ7˜7Jš
œ?˜?Jš
œ"˜"Jš
œ˜Jš
œ˜—Jšžœ
˜Jš
œ˜—J˜+Jšžœ˜Jš
œ˜˜J˜——J˜š
Ÿœžœ
žœžœžœ˜LJš
œ˜Jšžœ
ž˜šœΟc2˜9Jš
œ˜J˜J˜—šœ 2˜9Jš
œ˜J˜J˜—šœ
 2˜<Jš
œ˜J˜J˜—Jšžœžœ
˜˜J˜——šŸœžœ
žœžœ˜8šžœžœžœž˜/Jš
œ&˜&Jš
œ.˜.—Jšžœ
˜˜J˜——šŸœžœ
žœ˜6J™qJš
œ˜J˜ J˜
Jšžœ
ž˜˜šžœžœ
žœž˜$J™J˜š
œ+˜+J™]šžœžœ
žœ˜:J˜Jš
œ˜Jš
œ˜Jšœžœ
˜Jš
œ$˜$J˜——šžœžœ
žœž˜$Jš
œ˜Jš
œD˜DJšžœžœ
žœ˜0—š
ž˜š
œE˜Eš
œ˜Jš
œ4˜4Jš
œ˜J˜
—Jš
œ˜Jš
œ˜—šžœ˜
š
œ˜šžœ)žœ
žœ˜6Jš
œ$˜$Jš
œA˜AJ˜—J˜
—Jš
œ˜J˜——Jšžœ
˜—Jšžœ
˜J˜—˜šžœžœ
žœž˜$J™J˜š
œ+˜+J™]šžœžœ
žœ˜%J˜Jš
œ˜Jš
œ˜Jšœžœ
˜Jš
œ$˜$J˜——šžœžœ
žœž˜$Jš
œ˜Jš
œD˜DJšžœžœ
žœ˜0—š
ž˜š
œ˜š
œ˜Jš
œ4˜4Jš
œ˜J˜
—Jš
œ˜Jš
œ˜—šžœ˜
š
œ˜šžœ)žœ
žœ˜6Jš
œ$˜$Jš
œA˜AJ˜—J˜
—Jš
œ˜J˜——Jšžœ
˜—Jšžœ
˜J˜—˜šžœžœ
žœž˜$J™J˜š
œ+˜+J™]šžœžœ
žœ˜%J˜Jš
œ˜Jš
œ˜Jšœžœ
˜Jš
œ$˜$J˜——šžœžœ
žœž˜$Jš
œ˜Jš
œD˜DJšžœžœ
žœ˜0—š
ž˜š
œ˜š
œ˜Jš
œ4˜4Jš
œ˜J˜
—Jš
œ˜Jš
œ˜—šžœ˜
š
œ˜šžœ)žœ
žœ˜6Jš
œ$˜$Jš
œA˜AJ˜—J˜
—Jš
œ˜J˜——Jšžœ
˜—Jšžœ
˜J˜—Jšžœžœ
˜J˜J˜—šŸ	œžœ
žœ7žœ˜VJ™5J™MJš
œ"˜"J˜Jšžœ
ž˜šœ ˜šžœžœ
žœž˜$J™šžœžœ
žœž˜$Jš
œ ™ šžœžœ˜Jš
œ"˜"Jš
œ˜Jš
œ/˜/Jš
œ)˜)Jš
œ)˜)Jš
œ'˜'J˜——Jšžœ
˜—Jšžœ
˜J˜—šœ ˜šžœžœ
žœž˜$J™šžœžœ
žœž˜$Jš
œ ™ šžœžœ˜Jš
œ"˜"Jš
œ˜Jš
œ/˜/Jš
œ)˜)Jš
œ)˜)Jš
œ'˜'J˜——Jšžœ
˜—Jšžœ
˜J˜—˜	šžœžœ
žœž˜$J™šžœžœ
žœž˜$Jš
œ ™ šžœžœ˜Jš
œ"˜"Jš
œ˜Jš
œ.˜.Jš
œ(˜(Jš
œ)˜)Jš
œ'˜'J˜——Jšžœ
˜—Jšžœ
˜J˜—Jšžœžœ
˜J˜J˜—šŸœžœ
žœ7žœ™`J™5J™MJš
œ"™"J™šžœžœ
žœž™$šžœžœ
žœž™1Jš
œ ™ Jš
œ ™ Jš
œ.™.Jš
œ(™(Jš
œ)™)Jš
œ'™'—Jšžœ
™—Jšžœ
™™J™—J™—šŸœžœ
žœ8žœ˜YJš
œ΅
™΅
Jš
œ"˜"šžœžœ
žœž˜$šžœžœ
žœž˜$šžœžœ˜Jš
œ"˜"J˜Jš
œK˜KJ˜——Jšžœ
˜—Jšžœ
˜˜J˜—Jšžœ
˜—J˜—…—&B: