DIRECTORY
SVCoordSys, Feedback, GGParseIn, Imager, IO, Rope, SV2d, SV3d, SVBasicTypes, SVCastRays, SVDraw3d, SVGraphics, SVHalfSpaces, SVMasterObject, SVModelTypes, SVPolygon3d, SVRay, SVScene, SVSceneTypes;
SVHalfSpacesImpl: CEDAR PROGRAM
IMPORTS SVCoordSys, GGParseIn, SVCastRays, SVRay, SVGraphics, IO, SVDraw3d, SVMasterObject, SVPolygon3d, SVScene
EXPORTS SVHalfSpaces =

BEGIN

BoundHedron: TYPE = SVBasicTypes.BoundHedron;
CoordSystem: TYPE = SVModelTypes.CoordSystem;
CoordSysList: TYPE = SVModelTypes.CoordSysList;
Classification: TYPE =  SVSceneTypes.Classification;
FeedbackData: TYPE = Feedback.FeedbackData;
LightSourceList: TYPE = SVModelTypes.LightSourceList;
Point2d: TYPE = SV2d.Point2d;
Ray: TYPE = SVSceneTypes.Ray;
PlanarSurface: TYPE = REF PlanarSurfaceObj;
PlanarSurfaceObj: TYPE = SVSceneTypes.PlanarSurfaceObj;
PlanarSurfaceList: TYPE = SVSceneTypes.PlanarSurfaceList;
Plane: TYPE = SV3d.Plane;
Point3d: TYPE = SV3d.Point3d;
Poly3d: TYPE = SV3d.Poly3d;
Camera: TYPE = SVModelTypes.Camera;
MasterObjectClass: TYPE = SVSceneTypes.MasterObjectClass;
MasterObjectClassObj: TYPE = SVSceneTypes.MasterObjectClassObj;
MasterObject: TYPE = SVSceneTypes.MasterObject;
Primitive: TYPE = SVSceneTypes.Primitive;
Shape: TYPE = SVSceneTypes.Shape;
Slice: TYPE = SVSceneTypes.Slice;
SliceDescriptor: TYPE = SVSceneTypes.SliceDescriptor;
Surface: TYPE = REF ANY;
Vector3d: TYPE = SV3d.Vector3d;
HalfSpaceRec: TYPE = REF HalfSpaceRecObj;
HalfSpaceRecObj: TYPE = SVHalfSpaces.HalfSpaceRecObj;

PlaneSurface: TYPE = REF PlaneSurfaceObj;
PlaneSurfaceObj: TYPE = SVHalfSpaces.PlaneSurfaceObj;

SortedHalfSpaceSurface: TYPE = REF SortedHalfSpaceSurfaceObj;
SortedHalfSpaceSurfaceObj: TYPE = RECORD [i, j: INT];

halfSpaceClass: MasterObjectClass;

HalfSpaceBody: PRIVATE PROC RETURNS [halfSpaceRec: HalfSpaceRec] = {
halfSpaceRec _ NEW[HalfSpaceRecObj];
halfSpaceRec.gridSide _ 72.0;
};

HalfSpaceMakeMasterObject: PUBLIC PROC [name: Rope.ROPE] RETURNS [mo: MasterObject] = {
mainBody: HalfSpaceRec _ HalfSpaceBody[];
lineBody: REF ANY _ mainBody;
shadeBody: REF ANY _ mainBody;
rayCastBody: REF ANY _ HalfSpaceGetRayCastBody[];
mo _ SVScene.CreateMasterObject[name, halfSpaceClass, mainBody, lineBody, shadeBody, rayCastBody];
};

HalfSpaceBoundHedron: PUBLIC PROC [mo: MasterObject] RETURNS [hedron: BoundHedron] = {
hedron _ NIL;
};

HalfSpaceGetRayCastBody: PRIVATE PROC [] RETURNS [planeS: PlaneSurface] = {
planeS _ NEW[PlaneSurfaceObj];
};

HalfSpaceRayCast: PUBLIC PROC [cameraPoint: Point2d, localRay: Ray, sliceD: SliceDescriptor, prim: Primitive, positiveTOnly: BOOL _ TRUE] RETURNS [class: Classification] = {
mo: MasterObject _ prim.mo;
RETURN[HalfSpaceCastAux[localRay, NARROW[mo.rayCastBody], prim, positiveTOnly]];
};

HalfSpaceCastAux: PRIVATE PROC [localRay: Ray, plane: Surface, prim: Primitive, positiveTOnly: BOOL] RETURNS [class: Classification] = {
almostZero: REAL _ 1.0e-12;
t: REAL;
rayStartsOut: BOOL;
p: Point3d;
d: Vector3d;

class _ SVCastRays.GetClassFromPool[];
[p, d] _ SVRay.GetLocalRay[localRay];

rayStartsOut _ p[2] >0;
IF Abs[d[2]] > almostZero THEN {
t _ -p[2]/d[2];
IF t > 0 THEN {
class.count _ 1;
class.params[1] _ t;
class.surfaces[1] _ plane;
class.normals[1] _ [0,1,0];
class.primitives[1] _ prim;
IF rayStartsOut THEN {
class.classifs[1] _ FALSE;
class.classifs[2] _ TRUE;
}
ELSE {
class.classifs[1] _ TRUE;
class.classifs[2] _ FALSE;
};
}
ELSE {
class.count _ 0;
class.classifs[1] _  d[2] < 0; -- the ray is heading into the half-space.
};
}
ELSE {
class.count _ 0;
IF rayStartsOut THEN class.classifs[1] _ FALSE
ELSE class.classifs[1] _ TRUE;
};
}; -- end of HalfSpaceCastAux

Abs: PROC [r: REAL] RETURNS [REAL] = {
RETURN[IF r >= 0 THEN r ELSE -r];
};

HalfSpaceRayCastNoBBoxes: PUBLIC PROC [localRay: Ray, sliceD: SliceDescriptor, prim: Primitive, positiveTOnly: BOOL _ TRUE] RETURNS [class: Classification] = {
mo: MasterObject _ prim.mo;
RETURN[HalfSpaceCastAux[localRay, NARROW[mo.rayCastBody], prim, positiveTOnly]];
};

HalfSpaceRayCastBoundingSpheres: PUBLIC PROC [localRay: Ray, sliceD: SliceDescriptor, prim: Primitive, positiveTOnly: BOOL _ TRUE] RETURNS [class: Classification] = {
mo: MasterObject _ prim.mo;
RETURN[HalfSpaceCastAux[localRay, NARROW[mo.rayCastBody], prim, positiveTOnly]];
};

HalfSpaceFancyLineDraw: PRIVATE PROC[dc: Imager.Context, data: REF ANY, camera: Camera, localCS: CoordSystem, clippedBy: Imager.Rectangle] = {
halfSpaceRec: HalfSpaceRec _ NARROW[data];
gridSide: REAL _ halfSpaceRec.gridSide;
plane: Plane _ SVPolygon3d.PlaneFromCoefficients[0,1,0,0];
SVGraphics.DrawInfiniteLine[dc, [0,0,0], [1,0,0], camera, localCS, clippedBy];
SVGraphics.DrawInfiniteLine[dc, [0,0,gridSide], [1,0,gridSide], camera, localCS, clippedBy];
SVGraphics.DrawInfiniteLine[dc, [0,0,-gridSide], [1,0,-gridSide], camera, localCS, clippedBy];
SVGraphics.DrawInfiniteLine[dc, [0,0,0], [0,0,1], camera, localCS, clippedBy];
SVGraphics.DrawInfiniteLine[dc, [gridSide,0,0], [gridSide,0,1], camera, localCS, clippedBy];
SVGraphics.DrawInfiniteLine[dc, [-gridSide,0,0], [-gridSide,0,1], camera, localCS, clippedBy];
SVGraphics.DrawHorizonOfPlane[dc, plane, camera, localCS];
};

HalfSpaceLineDraw: PUBLIC PROC [slice: Slice, dc: Imager.Context, camera: Camera] = {
mo: MasterObject _ NARROW[slice.shape, Shape].mo;
halfSpaceRec: HalfSpaceRec _ NARROW[mo.lineBody];
gridSide: REAL _ halfSpaceRec.gridSide;
lineLen: REAL _ 100.0;
localCS: CoordSystem _ slice.coordSys;
SVGraphics.DrawLine[dc, [-lineLen,0,0], [lineLen,0,0], camera, localCS];
SVGraphics.DrawLine[dc, [-lineLen,0,gridSide], [lineLen,0,gridSide], camera, localCS];
SVGraphics.DrawLine[dc, [-lineLen,0,-gridSide], [lineLen,0,-gridSide], camera, localCS];
SVGraphics.DrawLine[dc, [0,0,-lineLen], [0,0,lineLen], camera, localCS];
SVGraphics.DrawLine[dc, [gridSide,0,-lineLen], [gridSide,0,lineLen], camera, localCS];
SVGraphics.DrawLine[dc, [-gridSide,0,-lineLen], [-gridSide,0,lineLen], camera, localCS];
};

HalfSpaceDrawNormals: PUBLIC PROC[dc: Imager.Context, data: REF ANY, camera: Camera, localCS: CoordSystem] = {
SVDraw3d.DrawLocalVector[dc, [0,1,0], [0,0,0], camera, localCS];
};

HalfSpaceCountSurf: PUBLIC PROC [masterObject: MasterObject] RETURNS [len: NAT] = {
len _ 4;
};

HalfSpaceCountVert: PUBLIC PROC [masterObject: MasterObject] RETURNS [len: NAT] = {
len _ 9;
};

AverageDepthInCamera: PROC [poly: Poly3d, localCS, cameraCS: CoordSystem] RETURNS [avgDepth: REAL] = {
sum: REAL _ 0;
realLen: REAL _ poly.len;
localPoint: Point3d;
FOR i: NAT IN[0..poly.len) DO
localPoint _ poly[i];
localPoint _ SVGraphics.LocalToCamera[localPoint, localCS, cameraCS];
sum _ sum + localPoint[3];
ENDLOOP;
avgDepth _ sum/realLen;
};

HalfSpaceGetSurf: PUBLIC PROC [slice: Slice, camera: CoordSystem, eyeWorld: Point3d] RETURNS [psl: PlanarSurfaceList] = {
poly: Poly3d _ SVPolygon3d.CreatePoly[4];
avgDepth: REAL;
shape: Shape _ NARROW[slice.shape, Shape];
mo: MasterObject _ shape.mo;
localCS: CoordSystem _ shape.coordSys;
thisSortedSurface: PlanarSurface;
halfSpaceRec: HalfSpaceRec _ NARROW[mo.shadeBody];
gridSide: REAL _ halfSpaceRec.gridSide;

FOR i: INT IN [-1..0] DO
FOR j: INT IN [-1..0] DO
poly _ SVPolygon3d.AddPolyPoint[poly, [i*gridSide, 0, j*gridSide]];
poly _ SVPolygon3d.AddPolyPoint[poly, [i*gridSide, 0, (j+1)*gridSide]];
poly _ SVPolygon3d.AddPolyPoint[poly, [(i+1)*gridSide, 0, (j+1)*gridSide]];
poly _ SVPolygon3d.AddPolyPoint[poly, [(i+1)*gridSide, 0, j*gridSide]];
avgDepth _ AverageDepthInCamera[poly, localCS, camera];
thisSortedSurface _ NEW[PlanarSurfaceObj _ [
whichSurface: NEW[SortedHalfSpaceSurfaceObj _ [i,j]],
assembly: slice,
normal: [0,1,0],
mo: mo,
depth: avgDepth,
frontDepth: avgDepth,
backDepth: avgDepth]];
psl _ CONS[thisSortedSurface, psl];
SVPolygon3d.ClearPoly[poly];
ENDLOOP;
ENDLOOP;
};

HalfSpaceDrawSurf: PUBLIC PROC [dc: Imager.Context, ps: PlanarSurface, lightSources: LightSourceList, camera: Camera, eyeWorld: Point3d, hiddenLine: BOOL] = {
i, j: INT;
poly: Poly3d _ SVPolygon3d.CreatePoly[4];
avgDepth: REAL;
shape: Shape;
localCS: CoordSystem;
thisHalfSpaceSurface: SortedHalfSpaceSurface;
mo: MasterObject;
halfSpaceRec: HalfSpaceRec;
gridSide: REAL;

thisHalfSpaceSurface _ NARROW[ps.whichSurface];
shape _ NARROW[ps.assembly.shape];
mo _ shape.mo;
halfSpaceRec _ NARROW[mo.shadeBody];
gridSide _ halfSpaceRec.gridSide;
localCS _ shape.coordSys;
i _ thisHalfSpaceSurface.i;
j _ thisHalfSpaceSurface.j;
avgDepth _ ps.depth;
poly _ SVPolygon3d.AddPolyPoint[poly, [i*gridSide, 0, j*gridSide]];
poly _ SVPolygon3d.AddPolyPoint[poly, [i*gridSide, 0, (j+1)*gridSide]];
poly _ SVPolygon3d.AddPolyPoint[poly, [(i+1)*gridSide, 0, (j+1)*gridSide]];
poly _ SVPolygon3d.AddPolyPoint[poly, [(i+1)*gridSide, 0, j*gridSide]];
SVGraphics.DrawAreaNormalAbsolute[dc, ps.normal, poly, ps.assembly.artwork, lightSources, camera, SVCoordSys.WRTCamera[localCS, camera.coordSys], hiddenLine];
};

HalfSpaceFileout: PUBLIC PROC [f: IO.STREAM, mo: MasterObject] = {
f.PutChar[IO.TAB];
f.PutF["data: procedural\n"];
};

HalfSpaceUpdate: PUBLIC PROC [mo: MasterObject, updateData: REF ANY] = {
};

HalfSpaceFilein: PUBLIC PROC [f: IO.STREAM, name: Rope.ROPE, csList: CoordSysList, defaultCS: CoordSystem, wdir: Rope.ROPE, version: REAL, feedback: FeedbackData] RETURNS [mo: MasterObject] = {
GGParseIn.ReadWRope[f, "data: procedural"];
GGParseIn.ReadBlank[f];
mo _ HalfSpaceMakeMasterObject[name];
};

Init: PROC = {
halfSpace: MasterObject;

halfSpaceClass _ NEW[MasterObjectClassObj _ [
name: "halfSpace",
update: HalfSpaceUpdate,
filein: HalfSpaceFilein,
fileout: HalfSpaceFileout,
fileoutPoly: SVMasterObject.NoOpFileoutPoly,
rayCast: HalfSpaceRayCast,
rayCastNoBBoxes: HalfSpaceRayCastNoBBoxes,
rayCastBoundingSpheres: HalfSpaceRayCastBoundingSpheres,
getHedron: HalfSpaceBoundHedron,
preprocess: SVMasterObject.NoOpPreprocess,
lineDraw: HalfSpaceLineDraw,
normalsDraw: HalfSpaceDrawNormals,
countSurf: HalfSpaceCountSurf,
getSurf: HalfSpaceGetSurf,
pointsInDescriptor: SVMasterObject.NoOpPointsInDescriptor,
nextPoint: SVMasterObject.NoOpNextPoint,
drawSurf: HalfSpaceDrawSurf,
drawSubBoxes: SVMasterObject.NoOpDrawSubBoxes,
drawSubSpheres: SVMasterObject.NoOpDrawSubSpheres
]];

SVMasterObject.RegisterMasterObjectClass[halfSpaceClass];
halfSpace _ HalfSpaceMakeMasterObject["halfSpace"];
SVMasterObject.RegisterMasterObject[halfSpace];
};


Init[];

END.

&File: SVHalfSpacesImpl.mesa
Author: Eric Bier on August 12, 1983 1:58 pm
Copyright c 1984 by Xerox Corporation.  All rights reserved.
Last edited by Bier: August 29, 1987 2:22:24 pm PDT
Contents: Implementation of the half-space object class


BASIC SHAPES

Do one ray-plane intersection test.
The half space ends at the xz plane (i.e. the plane with equation y = 0.
Ray parameterization is R = p + t*d.  For y, this is:
y[t] = p[2]+t*d[2].
If d has no y component, this has no solution.  Otherwise, we find t = -p[2]/d[2].  Check to see which side of the plane the ray originates on.  Check to see that t is positive.
The ray hits the plane.
The plane is behind the ray.
Ray is functionally parallel to the plane.  If ray starts in the plane, this is a hit, but with a count of 0.  Else, a complete miss.
HalfSpaceGetSurf: PUBLIC PROC [assembly: Slice, camera: CoordSystem] RETURNS [psl: PlanarSurfaceList] = {
mo: MasterObject _ NARROW[assembly.shape, Shape].mo;
midPoint: Point3d _ SVGraphics.LocalToCamera[[0,0,0], assembly.coordSys];
surface: PlanarSurface;
depth: REAL _ midPoint[3];
surface _ NEW[PlanarSurfaceObj _ [
NIL, assembly, mo, [0,1,0], depth]];
psl _ LIST[surface];
};

HalfSpaceDrawSurf: PUBLIC PROC [dc: Imager.Context, ps: PlanarSurface, lightSources: LightSourceList, camera: Camera] = {
localCS: CoordSystem;
plane: Plane _ SVPolygon3d.PlaneFromCoefficients[0,1,0,0];
localCS _ ps.assembly.coordSys;
SVGraphics.DrawInfinitePlaneShaded[dc, plane, ps.assembly.artwork, lightSources, camera, localCS];
};

HalfSpaces can be recovered from scratch.
ΚL˜Ihead™J™,Jšœ
Οm
œ1™<J™3J™8š
Οk	˜	Jšœ)žœš
˜Ε
—šœž
˜Jšžœ7žœ0˜pJšžœ˜—šžœ
˜Iprocšœ
žœ˜-Lšœ
žœ˜-Lšœžœ˜/Lšœžœ ˜4Lšœžœ˜+Lšœžœ ˜5Lšœ	žœ˜Lšœžœ˜Lšœžœžœ˜+LšΟbœžœ!˜7Lšœžœ"˜9Lšœžœ˜Lšœ	žœ˜Lšœžœ˜Lšœžœ˜#Lšœžœ"˜9Lšœžœ%˜?Lšœžœ˜/Lšœžœ˜)Lšœžœ˜!Lšœžœ˜!Lšœžœ ˜5Lšœ	žœžœ
žœ
˜Lšœ
žœ˜—L™š
œ
™
Lšœžœžœ˜)Lšœžœ!˜6Lšœžœžœ˜)Lšœžœ ˜5L˜Lšœžœžœ˜=Lšœžœžœžœ˜5L˜Lš
œ#˜#—šΟn
œžœ
žœ
žœ!˜DLšœžœ˜$Lš
œ˜Lš
œ˜L˜—š
 œžœ
žœ
žœžœ˜WLš
œ)˜)Lšœ
žœ
žœ˜Lšœžœ
žœ˜Lšœ
žœ
žœ˜1Lš
œb˜bLš
œ˜L˜—š œžœ
žœžœ˜VLšœ	žœ
˜
Lš
œ˜L˜—š œžœ
žœžœ˜KLšœ	žœ˜Lš
œ˜L˜—š œžœ
žœ`žœžœžœ˜­
Lš
œ˜Lšžœžœ(˜PLš
œ˜—š
 œžœ
žœAžœžœ˜ˆ
L™#L™HLšœŸ
œŸ
œŸ
œ™5L™L™±
Lšœžœ˜Lšœžœ
˜Lšœžœ
˜L˜L˜L˜Lš
œ&˜&Lšœ	žœ˜%L˜Lš
œ˜šžœžœ˜ Lš
œ˜šžœžœ˜Lš
Ÿ™L˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜šžœžœ˜Lšœžœ
˜Lšœžœ
˜L˜
—šžœ˜Lšœžœ
˜Lšœžœ
˜L˜—L˜
—šžœ˜L™L˜Lš
œI˜IL˜—L˜
—šžœ˜L™…
L˜Lšžœžœž˜.Lšžœž˜L˜—LšœΟcœ
˜—š
 œžœžœžœžœ˜&Lšžœ
žœžœžœ˜!L˜—L˜š œžœ
žœJžœžœžœ˜Ÿ
Lš
œ˜Lšžœžœ(˜PLš
œ˜L˜—š œžœ
žœJžœžœžœ˜¦
Lš
œ˜Lšžœžœ(˜PLš
œ˜L˜—š
 œžœ
žœžœ
žœH˜Ž
Lšœžœ˜*Lšœ
žœ˜'L˜:Lš
œN˜NLš
œ\˜\Lš
œ^˜^Lš
œN˜NLš
œ\˜\Lš
œ^˜^Lš
œ:˜:Lš
œ˜L˜—š œžœ6˜ULšœžœ˜1Lšœžœ˜1Lšœ
žœ˜'Lšœ	žœ	˜Lš
œ&˜&Lš
œH˜HLš
œV˜VLš
œX˜XLš
œH˜HLš
œV˜VLš
œX˜XLš
œ˜L˜—š
 œžœ
žœžœ
žœ+˜nLš
œ@˜@Lš
œ˜—š
 œžœ
žœžœžœ˜SLš
œ˜Lš
œ˜—š
 œžœ
žœžœžœ˜SLš
œ˜Lš
œ˜—š œžœ
žœ(žœ™iLšœžœ™4Lš
œI™ILš
œ™Lšœžœ™šœ
žœ™"Lšžœ!™$—Lšœžœ
™Lš
œ™—š œžœ0žœžœ˜fLšœžœ˜Lšœ	žœ˜Lš
œ˜šžœžœ
žœž˜Lš
œ˜Lš
œE˜ELš
œ˜Lšžœ
˜—Lš
œ˜Lš
œ˜L˜—š
 œžœ
žœ(Οuœžœ˜yLš
œ)˜)Lšœ
žœ
˜Lšœžœ˜*Lš
œ˜Lš
œ&˜&Lš
œ!˜!Lšœžœ˜2Lšœ
žœ˜'L˜šžœžœ
žœ	ž˜šžœžœ
žœ	ž˜Lš
œC˜CLš
œG˜GLš
œK˜KLš
œG˜GLš
œ7˜7šœžœ˜,Lšœžœ$˜5Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜—Lšœžœ˜#Lš
œ˜—Lšžœ
˜—Lšžœ
˜Lš
œ˜—š œžœ
žœ[™yLš
œ™Lš
œ:™:Lš
œ™Lš
œb™bLš
œ™L™—š
 œžœ
žœ[’œžœ˜ž
L˜
Lš
œ)˜)Lšœ
žœ
˜L˜
Lš
œ˜Lš
œ-˜-Lš
œ˜Lš
œ˜Lšœ
žœ
˜L˜Lšœžœ˜/Lšœžœ˜"Lš
œ˜Lšœžœ˜$Lš
œ!˜!Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œC˜CLš
œG˜GLš
œK˜KLš
œG˜GLš
œž
˜ž
Lš
œ˜—L˜š
 œžœ
žœžœ
žœ˜BLš
œ)™)Lšœ
žœ
žœ˜Lš
œ˜Lš
œ˜—š
 œžœ
žœ žœ
žœ˜HLš
œ˜—š œžœ
žœžœ
žœ
žœ;žœžœžœ˜Α
Lš
œ+˜+Lš
œ˜Lš
œ%˜%Lš
œ˜—š œžœ˜Lš
œ˜L˜šœžœ˜-Lš
œ˜LšŸœ˜LšŸœ˜LšŸœ˜LšŸœ!˜,LšŸœ˜LšŸœ˜*LšŸœ"˜8LšŸ	œ˜ LšŸ
œ ˜*LšŸœ˜LšŸœ˜"LšŸ	œ˜LšŸœ˜LšŸœ(˜:LšŸ	œ˜(LšŸœ˜LšŸœ"˜.LšŸœ#˜1Lš
œ˜—Lš
œ9˜9Lš
œ3˜3Lš
œ/˜/L˜L˜—L˜Lš
œ˜L˜Jšžœ
˜J˜—…—(L9Ύ