DIRECTORY
Atom					USING [ GetPropFromList, PutPropOnList, PropList ],
Real					USING [ Fix, Round ],
Basics					USING [ BITOR, BITAND ],
BasicTime			USING [ PulsesToSeconds, GetClockPulses ],
Rope					USING [ ROPE, Cat ],
Convert				USING [ RopeFromReal ],
ScanConvert			USING [ justNoticeable ],
G3dVector	USING [ Add, Cross, Dot, Length, Mul, Normalize ],
G3dMatrix	USING [ Mul, Transform, TransformVec ],
G3dPlane	USING [ DistanceToPoint ],
ThreeDBasics		USING [ AllOut, ClipState, Context, Error, FacingDir,
								 IntegerSequence, NatSequence, NoneOut, OutCode, Patch,
								 PatchSequence, PtrPatchSequence, PtrPatch,
								 RealSequence, RGB, RegisterShadingClass,
								 RegisterSurfaceType, ScaleAndAddXfm,
								 ShadingClass, ShadingSequence, ShadingValue, ShapeClass,
								 ShapeInstance, ShapeSequence, ShapeProc, SixSides, Triple,
								 TripleSequence, Vertex, VertexInfo, VertexInfoProc,
								 VertexInfoSequence, VertexSequence, Xfm3D ],
SurfaceRender		USING [ OutputPolygon, RopeDisplay, ValidatePolyhedron,
								 ValidateRopeShape ],
ShapeUtilities		USING [ ShapePatch ];

ShapeUtilitiesImpl: CEDAR MONITOR
IMPORTS Atom, Basics, BasicTime, Convert, G3dPlane, G3dMatrix, Real, Rope, SurfaceRender, ThreeDBasics, G3dVector
EXPORTS ShapeUtilities 

~ BEGIN 

Context: TYPE ~ ThreeDBasics.Context;
RGB: TYPE ~ ThreeDBasics.RGB;										--	 [ r, g, b: REAL];
SixSides: TYPE ~ ThreeDBasics.SixSides;
ScaleAndAddXfm: TYPE ~ ThreeDBasics.ScaleAndAddXfm;
OutCode: TYPE ~ ThreeDBasics.OutCode;
NoneOut: OutCode ~ ThreeDBasics.NoneOut;
AllOut: OutCode ~ ThreeDBasics.AllOut;
Xfm3D: TYPE ~ ThreeDBasics.Xfm3D;
Triple: TYPE ~ ThreeDBasics.Triple;
TripleSequence: TYPE ~ ThreeDBasics.TripleSequence;
NatSequence: TYPE ~ ThreeDBasics.NatSequence;
IntegerSequence: TYPE ~ ThreeDBasics.IntegerSequence;
RealSequence: TYPE ~ ThreeDBasics.RealSequence;
ShapeInstance: TYPE ~ ThreeDBasics.ShapeInstance;
FacingDir: TYPE ~ ThreeDBasics.FacingDir;
Patch: TYPE ~ ThreeDBasics.Patch;
PatchSequence: TYPE ~ ThreeDBasics.PatchSequence;
PtrPatch: TYPE ~ ThreeDBasics.PtrPatch;
PtrPatchSequence: TYPE ~ ThreeDBasics.PtrPatchSequence;
ShapePatch: TYPE ~ ShapeUtilities.ShapePatch;
Vertex: TYPE ~ ThreeDBasics.Vertex;
VertexSequence: TYPE ~ ThreeDBasics.VertexSequence;
VertexInfo: TYPE ~ ThreeDBasics.VertexInfo;
VertexInfoSequence: TYPE ~ ThreeDBasics.VertexInfoSequence;
VertexInfoProc: TYPE ~ ThreeDBasics.VertexInfoProc;
ShadingValue: TYPE ~ ThreeDBasics.ShadingValue;
ShadingSequence: TYPE ~ ThreeDBasics.ShadingSequence;

ShapeClass: TYPE ~ ThreeDBasics.ShapeClass;
ShadingClass: TYPE ~ ThreeDBasics.ShadingClass;
ShapeProc: TYPE ~ ThreeDBasics.ShapeProc;		-- PROC[ Context, ShapeInstance ]
LORA: TYPE ~ LIST OF REF ANY;
Transform: PROC[p: Triple, mat: Xfm3D] RETURNS[Triple] ~ G3dMatrix.Transform;
TransformVec: PROC[vec: Triple, mat: Xfm3D] RETURNS[Triple] ~
																	 G3dMatrix.TransformVec;
GetProp: PROC [propList: Atom.PropList, prop: REF ANY] RETURNS [REF ANY] ~
																				 Atom.GetPropFromList;
PutProp: PROC [propList: Atom.PropList, prop: REF ANY, val: REF ANY] 
		   RETURNS [Atom.PropList] ~ Atom.PutPropOnList;
nullPtr: INT ~ 0;				-- handy name for zero in sort sequences
nullTriple: Triple _ [0.0, 0.0, 0.0];
defaultWhite: RGB _ [1.0, 1.0, 1.0];
vertexStore: REF VertexInfoSequence _ NEW[ VertexInfoSequence[96] ];	-- Vertex Cache
vertexStoreLength: NAT _ 96;
vertexStorePtr: NAT _ 0;								-- place to return next free record

GetVertexInfo: PUBLIC ENTRY PROC[]  RETURNS[REF VertexInfo] ~ {
ENABLE UNWIND => NULL;
vtx: REF VertexInfo;
IF vertexStorePtr = 0
THEN vtx _  NEW[VertexInfo]
ELSE {
vertexStorePtr _ vertexStorePtr - 1;
vtx _ vertexStore[vertexStorePtr];
vertexStore[vertexStorePtr] _ NIL;
};
vtx.aux _ vtx.props _ NIL;
RETURN[ vtx ];
};

ReleaseVertexInfo: PUBLIC ENTRY PROC[vtx: REF VertexInfo] ~ {
ENABLE UNWIND => NULL;
IF vertexStorePtr = vertexStoreLength THEN {
vertexStore _ NEW[ VertexInfoSequence[vertexStoreLength + 32] ];
vertexStoreLength _ vertexStoreLength + 32;
vertexStorePtr _ 0;
};
IF vertexStorePtr > 0 AND vertexStore[vertexStorePtr-1] = vtx
THEN SIGNAL ThreeDBasics.Error[[$MisMatch, "Double vertexInfo release"]]
ELSE vertexStore[vertexStorePtr] _ vtx;
vertexStorePtr _ vertexStorePtr + 1;
};

patchCache: REF PatchSequence _ NEW[ PatchSequence[16] ];		-- temps for clipping, etc.
patchCacheLength: NAT _ 16;
patchCachePtr: NAT _ 0;								-- place to return next free record

GetPatch: PUBLIC ENTRY PROC[size: NAT]  RETURNS[REF Patch] ~ {
ENABLE UNWIND => NULL;
p: REF Patch;
IF patchCachePtr = 0
THEN p _  NEW[Patch[size]]
ELSE {
patchCachePtr _ patchCachePtr - 1;
p _ patchCache[patchCachePtr];
patchCache[patchCachePtr] _ NIL;
IF p.maxLength < size THEN  p _  NEW[Patch[size]];
};
RETURN[ p ];
};

ReleasePatch: PUBLIC ENTRY PROC[p: REF Patch] ~ {
ENABLE UNWIND => NULL;
IF p = NIL THEN RETURN[];
IF patchCachePtr = patchCacheLength THEN {
patchCache _ NEW[ PatchSequence[patchCacheLength + 2] ];
patchCacheLength _ patchCacheLength + 2;
patchCachePtr _ 0;
};
IF patchCachePtr > 0 AND patchCache[patchCachePtr-1] = p 
THEN SIGNAL ThreeDBasics.Error[[$MisMatch, "Double patch release"]]
ELSE patchCache[patchCachePtr] _ p;
patchCachePtr _ patchCachePtr + 1;
};
Sgn: PROCEDURE [number: REAL] RETURNS [INT] ~ INLINE { 
IF number < 0. THEN RETURN[-1] ELSE RETURN[1];   
};

Ceiling: PROC[number: REAL] RETURNS[result: INTEGER] ~ {
result _ Real.Round[number];
IF result < number THEN result _ result + 1;
};

ElapsedTime: PROC[startTime: REAL]  RETURNS[Rope.ROPE] ~ {
timeX10: REAL _ 10.0 * (BasicTime.PulsesToSeconds[BasicTime.GetClockPulses[]] - startTime);
RETURN[ Rope.Cat[ Convert.RopeFromReal[ Real.Fix[timeX10] / 10.0 ], " secs. " ] ];
};

CurrentTime: PROC[]  RETURNS[REAL] ~ {
RETURN[ BasicTime.PulsesToSeconds[BasicTime.GetClockPulses[]] ];
};

DiffPosns: PROC[vtx1, vtx2: REF Vertex] RETURNS[Triple] ~ {
RETURN[[vtx1.x - vtx2.x, vtx1.y - vtx2.y, vtx1.z - vtx2.z]] };

GetNormal: PROC[vertex: REF ThreeDBasics.VertexSequence, 
					 poly: REF PtrPatch, cVtx: NAT]
			  RETURNS[normal: Triple] ~ { 
lVtx: NAT _ (cVtx + poly.nVtces - 1) MOD poly.nVtces; 
nVtx: NAT _ (cVtx + 1) MOD poly.nVtces;
normal _ G3dVector.Cross[						-- in object space so do right-handed
DiffPosns[ vertex[poly.vtxPtr[lVtx]], vertex[poly.vtxPtr[cVtx]] ],
DiffPosns[ vertex[poly.vtxPtr[nVtx]], vertex[poly.vtxPtr[cVtx]] ] 
];
};

HoldEverything:  PROCEDURE [] ~ {
ERROR ABORTED;
};

ShapePatchToPatch: PUBLIC PROC[context: REF Context, sPatch: REF ShapePatch] 
						 RETURNS [patch: REF Patch] ~ {
ptrPatch: REF PtrPatch _ 
		NARROW[sPatch.shape.surface, REF PtrPatchSequence][sPatch.patch];
auxData: REF _ GetProp[ sPatch.shape.shadingProps, $AuxiliaryVtxData ];
shapeColor: RGB _ sPatch.shape.shadingClass.color;
shapeTransmittance: REAL _ sPatch.shape.shadingClass.transmittance;
faceted: BOOLEAN _ sPatch.shape.shadingClass.shadingType = $Faceted 
						AND sPatch.shape.class.type = $ConvexPolygon;
lines: BOOLEAN _ sPatch.shape.shadingClass.shadingType = $Lines 
					OR sPatch.shape.shadingClass.shadingType = $HiddenLines;
patchInfo: REF ThreeDBasics.ShadingSequence _ sPatch.shape.shadingClass.patchShade;
coloredPatches: BOOLEAN _ IF NOT faceted 
THEN	  GetProp[ sPatch.shape.fixedProps, $PatchColorsInFile ] # NIL 
	 OR GetProp[ sPatch.shape.fixedProps, $PatchTransmittancesInFile ] # NIL
ELSE FALSE;

IF ptrPatch.clipState = out THEN RETURN[NIL];						-- reject if outside frame

patch _ GetPatch[2 * ptrPatch.nVtces];			-- get temp patch, released by OutputPatch
patch.nVtces _ ptrPatch.nVtces; 
patch.clipState _ ptrPatch.clipState; 
patch.type _ sPatch.shape.class.type;				-- take type from class
patch.oneSided _ IF NOT ptrPatch.oneSided THEN FALSE ELSE (shapeTransmittance = 0.0);
patch.dir _ ptrPatch.dir;
patch.props _ PutProp[ ptrPatch.props, $Shape, sPatch.shape ];
patch.props _ PutProp[ patch.props, $PatchNo, NEW[NAT _ sPatch.patch] ];
FOR i: NAT IN [0..ptrPatch.nVtces) DO
j: NAT _ ptrPatch.vtxPtr[i];
patch[i].props _ patch.props;				-- pass info through in case needed
patch[i].coord _ sPatch.shape.vertex[j]^; 
patch[i].shade _ sPatch.shape.shade[j]^;
IF auxData # NIL 
THEN {
data: LORA _ LIST[ auxData, NEW[INTEGER _ j] ];
patch[i] _ sPatch.shape.shadingClass.loadVtxAux[context, patch[i], data];
}
ELSE patch[i].aux _ NIL;
IF lines 
THEN {												-- unshaded lines use shape color
patch[i].shade.er _ shapeColor.R; 
patch[i].shade.eg _ shapeColor.G;
patch[i].shade.eb _ shapeColor.B;
}
ELSE IF patchInfo # NIL THEN IF faceted 			   -- shades for individual patches
THEN patch[i].shade _ patchInfo[sPatch.patch]^	-- faceted, take patch shade
ELSE  IF coloredPatches THEN {				-- smooth, combine vtx and patch shades
patch[i].shade.r _ sPatch.shape.shade[j].r * patchInfo[sPatch.patch].r;
patch[i].shade.g _ sPatch.shape.shade[j].g * patchInfo[sPatch.patch].g;
patch[i].shade.b _ sPatch.shape.shade[j].b * patchInfo[sPatch.patch].b;
patch[i].shade.t _ sPatch.shape.shade[j].t * patchInfo[sPatch.patch].t;
patch[i] _ sPatch.shape.shadingClass.shadeVtx[
context, patch[i], sPatch.shape.shadingClass
];
};
ENDLOOP;
};

InitClasses: PROC[] ~ {				-- register procedures for basic surface types
standardClass: ShapeClass _ [
type: $Light,  
display: NIL,
displayPatch: NIL
];
defaultShadingClass: ShadingClass _ [		-- procs for standard shading (no texture)
type: $Default,
shadingType: $Faceted,
shadeVtx: ShadeVtx
];
ThreeDBasics.RegisterSurfaceType[standardClass, $Light]; -- placeholder class for light source
standardClass.type _ $ConvexPolygon;
standardClass.validate _ SurfaceRender.ValidatePolyhedron;
standardClass.displayPatch _ SurfaceRender.OutputPolygon;
ThreeDBasics.RegisterSurfaceType[standardClass, $ConvexPolygon];	-- ConvexPolygon procs

standardClass.type _ $RopeShape;
standardClass.validate _ SurfaceRender.ValidateRopeShape;
standardClass.displayPatch _ SurfaceRender.RopeDisplay;
ThreeDBasics.RegisterSurfaceType[standardClass, $RopeShape];	-- RopeShape procs

ThreeDBasics.RegisterShadingClass[defaultShadingClass, $Default];
defaultShadingClass.type _ $NoShading;
defaultShadingClass.shadingType _ $Faceted;
defaultShadingClass.shadeVtx _ NoShadeVtx;
ThreeDBasics.RegisterShadingClass[defaultShadingClass, $NoShading];
};

XfmToEyeSpace: PUBLIC PROC[context: REF Context, shape: REF ShapeInstance] 
	 RETURNS[ThreeDBasics.ClipState] ~ {
ClipBoundingBall: PROC[] RETURNS[ThreeDBasics.ClipState] ~ {
clipFlag: BOOLEAN _ FALSE;
FOR plane: SixSides  IN SixSides DO
distance: REAL _ G3dPlane.DistanceToPoint[ 
[shape.centroid.ex, shape.centroid.ey, shape.centroid.ez],
context.clippingPlanes[plane] 
];
IF distance < -shape.boundingRadius THEN RETURN[out]    
ELSE IF distance < shape.boundingRadius THEN clipFlag _ TRUE;
ENDLOOP;
IF clipFlag THEN RETURN[clipped] ELSE RETURN[in];
};
xfm: Xfm3D _ G3dMatrix.Mul[shape.position, context.eyeSpaceXfm];
[[shape.centroid.ex, shape.centroid.ey, shape.centroid.ez]] _ Transform[ 
[shape.centroid.x, shape.centroid.y, shape.centroid.z], 		-- Update shape centroid
xfm
];
shape.clipState _ ClipBoundingBall[];
IF shape.clipState # out THEN {	-- run through vertices and shading and transform
andOfCodes: OutCode _ AllOut;					-- test for trivially out
orOfCodes: OutCode   _ NoneOut;					-- test for trivially in
IF shape.vertex # NIL THEN FOR i: NAT IN [0..shape.vertex.length) DO 
IF shape.vertex[i] # NIL THEN {
OPEN shape.vertex[i];
[ [ex, ey, ez] ] _ Transform[ [x, y, z] , xfm];   -- transform pts to eyespace
IF shape.clipState # in 
THEN {
clip _ GetClipCodeForPt[ context, [ex, ey, ez] ];
orOfCodes _ LOOPHOLE[
Basics.BITOR[LOOPHOLE[orOfCodes], LOOPHOLE[ clip] ], OutCode];   
andOfCodes _ LOOPHOLE[
Basics.BITAND[ LOOPHOLE[andOfCodes], LOOPHOLE[ clip] ], OutCode];
}
ELSE clip _ NoneOut;
};
ENDLOOP;
IF        orOfCodes = NoneOut		THEN shape.clipState _ in
ELSE IF andOfCodes # NoneOut	THEN shape.clipState _ out;

};
RETURN[shape.clipState];
};
  
XfmToDisplay: PUBLIC PROC[ context: REF Context, shape: REF ShapeInstance, 
								   getBox: BOOL _ FALSE ] ~ {
xMin, yMin: REAL _ 32767.0;
xMax, yMax: REAL _ 0.0;
bboxNeeded: BOOLEAN _ context.antiAliasing OR getBox;
IF shape.vertex # NIL THEN FOR i: NAT IN [0..shape.vertex.length) DO 
IF shape.vertex[i] # NIL THEN {
OPEN shape.vertex[i];
IF clip = NoneOut THEN { 
[ [sx, sy, sz] ] _ XfmTripleToDisplay[
pt: [ex, ey, ez], 
xfm: context.eyeToNdc, 
display: context.ndcToPixels,
offset: IF context.antiAliasing THEN .5 ELSE 0.0 -- nojaggy tiler offsets by 1/2 pixel
];
IF bboxNeeded THEN {
IF sx < xMin THEN xMin _ sx;    IF sy < yMin THEN yMin _ sy;
IF sx > xMax THEN xMax _ sx;    IF sy > yMax THEN yMax _ sy;
};
}
ELSE IF bboxNeeded THEN {
IF clip.left THEN xMin _ 0.0;		  
IF clip.right THEN xMax _ context.viewPort.w;
IF clip.top THEN yMin _ 0.0;    
IF clip.bottom THEN yMax _ context.viewPort.h;
};
};
ENDLOOP;
IF bboxNeeded THEN {
xMin _ MAX[0.0, xMin-2.0];     xMax _ MIN[context.viewPort.w, xMax+2.0];
yMin _ MAX[0.0, yMin-2.0];    yMax _ MIN[context.viewPort.h, yMax+2.0];
shape.screenExtent _ [ min: [f: Real.Fix[xMin], s: Real.Fix[yMin]], 
						  max: [f: Ceiling[xMax], s: Ceiling[yMax]] ];
}; 
};
  
GetPolyInfo: PROC[context: REF Context, shape: REF ShapeInstance] ~ { 
surface: REF PtrPatchSequence;
xfm: Xfm3D;
preNormaled: BOOLEAN _ GetProp[ shape.fixedProps, $PatchNormalsInFile] # NIL;
polyShade: REF ShadingSequence _ shape.shadingClass.patchShade;

IF shape.surface = NIL THEN RETURN;			-- not a shape (probably a light source)
IF shape.class.type # $ConvexPolygon THEN {
SIGNAL ThreeDBasics.Error[[$MisMatch, "Operation only for polygons"]];
RETURN[];
};
IF polyShade = NIL THEN {
polyShade _ NEW[ ShadingSequence[shape.numSurfaces] ];
polyShade.length _ shape.numSurfaces;
};
surface _ NARROW[shape.surface, REF PtrPatchSequence];
IF NOT shape.vtcesInValid THEN xfm _ G3dMatrix.Mul[shape.position, context.eyeSpaceXfm];
FOR i: NAT IN [0..shape.numSurfaces) DO 
IF surface[i] # NIL THEN {
sumNmls: Triple _ [0., 0., 0.];
IF polyShade[i] = NIL THEN polyShade[i] _ NEW[ ThreeDBasics.ShadingValue ];
IF NOT preNormaled THEN {
FOR cVtx: NAT IN [0..surface[i].nVtces) DO 
sumNmls _ G3dVector.Add[ sumNmls, GetNormal[shape.vertex, surface[i], cVtx] ];
ENDLOOP;
sumNmls _ G3dVector.Normalize[sumNmls];
polyShade[i].xn _ sumNmls.x;
polyShade[i].yn _ sumNmls.y;
polyShade[i].zn _ sumNmls.z; 
IF NOT shape.vtcesInValid THEN {  -- if vertices already transformed to eyespace
OPEN polyShade[i];										-- transform normal vectors
[ [exn, eyn, ezn] ] _ TransformVec[ [xn, yn, zn] , xfm];    
};
};
};
ENDLOOP; 
shape.shadingProps _ PutProp[shape.shadingProps, $PolygonInfoComputed, $ok];
};
GetPolyShades: PUBLIC PROC[context: REF Context, shape: REF ShapeInstance] ~ {
AverageVertices: PROC[poly: REF PtrPatch] RETURNS[vtx: Vertex] ~ {
FOR i: NAT IN [0..poly.nVtces) DO
addVtx: Vertex _ shape.vertex[poly.vtxPtr[i]]^;
vtx.x _ vtx.x + addVtx.x;      vtx.y _ vtx.y + addVtx.y;     vtx.z _ vtx.z + addVtx.z;
vtx.ex _ vtx.ex + addVtx.ex;  vtx.ey _ vtx.ey + addVtx.ey;  vtx.ez _ vtx.ez + addVtx.ez;
vtx.sx _ vtx.sx + addVtx.sx;   vtx.sy _ vtx.sy + addVtx.sy;  vtx.sz _ vtx.sz + addVtx.sz;
vtx.clip _ LOOPHOLE[ Basics.BITOR[ LOOPHOLE[vtx.clip], LOOPHOLE[addVtx.clip] ],
						 ThreeDBasics.OutCode];   
ENDLOOP;
vtx.x _ vtx.x/poly.nVtces;     vtx.y _ vtx.y/poly.nVtces;    vtx.z _ vtx.z/poly.nVtces;
vtx.ex _ vtx.ex/poly.nVtces;  vtx.ey _ vtx.ey/poly.nVtces;  vtx.ez _ vtx.ez/poly.nVtces;
vtx.sx _ vtx.sx/poly.nVtces;   vtx.sy _ vtx.sy/poly.nVtces;  vtx.sz _ vtx.sz/poly.nVtces;
};
poly: REF PtrPatchSequence;
shapeColor: RGB _ shape.shadingClass.color;
shapeTransmittance: REAL _ shape.shadingClass.transmittance;
polyShade: REF ShadingSequence _ shape.shadingClass.patchShade;

IF shape.class.type # $ConvexPolygon THEN RETURN;	-- patches, etc. shaded after expansion
IF shape.surface = NIL OR shape.shadingClass.shadingType # $Faceted THEN {
SIGNAL ThreeDBasics.Error[[$Condition, "Data missing for faceted shading"]];
RETURN;
};
IF GetProp[ shape.shadingProps, $PolygonInfoComputed] = NIL THEN {
IF polyShade = NIL THEN {
polyShade _ NEW[ ShadingSequence[shape.numSurfaces] ];
polyShade.length _ shape.numSurfaces;
FOR i: NAT IN [0..shape.numSurfaces) DO 
polyShade[i] _ NEW[ ShadingValue ]; 
ENDLOOP;
shape.shadingClass.patchShade _ polyShade;
};
GetPolyInfo[context, shape];
};
poly _ NARROW[ shape.surface, REF PtrPatchSequence ];
FOR i: NAT IN [0..shape.numSurfaces) DO
IF poly[i] # NIL THEN {
vtx: Vertex _ AverageVertices[poly[i]];
pt: VertexInfo _ [ vtx, polyShade[i]^, NIL ];
pt	_ shape.shadingClass.shadeVtx[ context, pt, shape.shadingClass ];  -- calculate shade
polyShade[i].er _ pt.shade.er;
polyShade[i].eg _ pt.shade.eg;
polyShade[i].eb _ pt.shade.eb;
polyShade[i].et _ pt.shade.et;
};
ENDLOOP;
};

GetVtxNmls: PUBLIC PROC[context: REF Context, shape: REF ShapeInstance] ~ {
surface: REF PtrPatchSequence _ NARROW[shape.surface];
preNormaled: BOOLEAN _ GetProp[ shape.fixedProps, $VertexNormalsInFile ] # NIL;
IF shape.shade = NIL THEN {
shape.shade _ NEW[ ThreeDBasics.ShadingSequence[shape.vertex.length] ];
shape.shade.length _ shape.vertex.length;
};
FOR i: NAT IN [0..shape.vertex.length) DO 
IF shape.shade[i] = NIL THEN {
shape.shade[i] _ NEW[ ThreeDBasics.ShadingValue ];
shape.shade[i].xn _ shape.shade[i].yn _ shape.shade[i].zn _ 0.0;		-- debugging aid
};
ENDLOOP;
IF NOT preNormaled THEN {	-- get vertex normal
xfm: Xfm3D _ G3dMatrix.Mul[shape.position, context.eyeSpaceXfm];
FOR i: NAT IN [0..shape.numSurfaces) DO     -- get normals at vertices, add to earlier ones 
IF surface[i] # NIL THEN FOR cVtx: NAT IN [0..surface[i].nVtces) DO 
OPEN shape.shade[surface[i].vtxPtr[cVtx]];	
cornerNormal: Triple _ GetNormal[ shape.vertex, surface[i], cVtx ];
[[xn, yn, zn]] _ G3dVector.Add[ cornerNormal, [xn, yn, zn]];
ENDLOOP;
ENDLOOP; 
FOR i: NAT IN [0..shape.shade.length) DO 
IF shape.shade[i] # NIL THEN {
OPEN shape.shade[i];
IF G3dVector.Length[ [xn, yn, zn] ] > shape.boundingRadius * .0001
THEN {
[[xn, yn, zn]] _ G3dVector.Normalize[ [xn, yn, zn] ];
[[exn, eyn, ezn]] _ TransformVec[ [xn, yn, zn] , xfm];    
}
ELSE {
[xn, yn, zn] _ [exn, eyn, ezn] _ nullTriple;
};
};
ENDLOOP;
};
shape.shadingProps _ PutProp[shape.shadingProps, $VtxInfoComputed, $ok];
}; 

GetVtxShades: PUBLIC PROC[ context: REF Context, shape: REF ShapeInstance] ~ {
tmpShininess: REAL;
IF shape.shadingClass # NIL THEN {  	-- cache highlight power, no highlights here please
tmpShininess _ shape.shadingClass.shininess;    shape.shadingClass.shininess _ 0.0;
};
IF shape.shade # NIL THEN FOR i: NAT IN [0..shape.shade.length) DO
IF shape.shade[i] # NIL THEN {
pt: VertexInfo _ [ coord: shape.vertex[i]^, shade: shape.shade[i]^ ];
pt _ shape.shadingClass.shadeVtx[context, pt, shape.shadingClass];
shape.shade[i].er _ pt.shade.er;
shape.shade[i].eg _ pt.shade.eg;
shape.shade[i].eb _ pt.shade.eb;
shape.shade[i].et _ pt.shade.et;
};
ENDLOOP;
IF shape.shadingClass # NIL THEN shape.shadingClass.shininess _ tmpShininess;
};
ClipPoly: PUBLIC PROC[ context: REF Context, poly: REF Patch] RETURNS [REF Patch] ~ {
Clip: PROC[side: SixSides, pIn, pOut: REF Patch] RETURNS [REF Patch, REF Patch] = {

Dist: PROC[side: SixSides, vtx: Vertex] RETURNS [REAL] = {		-- + inside, - outside
RETURN[ G3dPlane.DistanceToPoint[ 
[vtx.ex, vtx.ey, vtx.ez],
context.clippingPlanes[side] 
] ];
};
lastDist, dist: REAL;    outCnt, last: NAT;
IF pIn.nVtces < 2 THEN RETURN[ pIn, pOut ];	-- return if degenerate (line needs 2)
outCnt _ 0;
IF pIn.type # $PolyLine THEN {
lastDist _ Dist[side, pIn.vtx[pIn.nVtces - 1].coord];
last _ pIn.nVtces - 1;
};
IF pOut.maxLength < 2 * pIn.nVtces THEN pOut _ NEW[Patch[2 * pIn.nVtces]];
FOR i: NAT IN [0..pIn.nVtces) DO
a, b: REAL;
dist _ Dist[side, pIn.vtx[i].coord];
IF (i # 0 OR pIn.type # $PolyLine) AND lastDist * dist < 0. THEN {	
b _ dist / (dist - lastDist);    a _ 1.0 - b;
pOut.vtx[outCnt].coord.x _ pIn.vtx[i].coord.x * a + pIn.vtx[last].coord.x * b;
pOut.vtx[outCnt].coord.y _ pIn.vtx[i].coord.y * a + pIn.vtx[last].coord.y * b;
pOut.vtx[outCnt].coord.z _ pIn.vtx[i].coord.z * a + pIn.vtx[last].coord.z * b;
pOut.vtx[outCnt].coord.ex _ pIn.vtx[i].coord.ex * a + pIn.vtx[last].coord.ex * b;
pOut.vtx[outCnt].coord.ey _ pIn.vtx[i].coord.ey * a + pIn.vtx[last].coord.ey * b;
pOut.vtx[outCnt].coord.ez _ pIn.vtx[i].coord.ez * a + pIn.vtx[last].coord.ez * b;
pOut.vtx[outCnt].shade.exn _ pIn.vtx[i].shade.exn*a + pIn.vtx[last].shade.exn*b;
pOut.vtx[outCnt].shade.eyn _ pIn.vtx[i].shade.eyn*a + pIn.vtx[last].shade.eyn*b;
pOut.vtx[outCnt].shade.ezn _ pIn.vtx[i].shade.ezn*a + pIn.vtx[last].shade.ezn*b;
pOut.vtx[outCnt].shade.r _ pIn.vtx[i].shade.r * a + pIn.vtx[last].shade.r * b;
pOut.vtx[outCnt].shade.g _ pIn.vtx[i].shade.g * a + pIn.vtx[last].shade.g * b;
pOut.vtx[outCnt].shade.b _ pIn.vtx[i].shade.b * a + pIn.vtx[last].shade.b * b;
pOut.vtx[outCnt].shade.t _ pIn.vtx[i].shade.t * a + pIn.vtx[last].shade.t* b;
pOut.vtx[outCnt].shade.er _ pIn.vtx[i].shade.er * a + pIn.vtx[last].shade.er * b;
pOut.vtx[outCnt].shade.eg _ pIn.vtx[i].shade.eg * a + pIn.vtx[last].shade.eg * b;
pOut.vtx[outCnt].shade.eb _ pIn.vtx[i].shade.eb * a + pIn.vtx[last].shade.eb * b;
pOut.vtx[outCnt].shade.et _ pIn.vtx[i].shade.et * a + pIn.vtx[last].shade.et * b;
IF pIn.vtx[i].aux # NIL AND pIn.vtx[last].aux # NIL 
THEN {
data: LORA _ LIST[ 
pIn.vtx[i].aux, pIn.vtx[last].aux, NEW[REAL _ a], NEW[REAL _ b] 
];
pOut.vtx[outCnt] _ lerpProc[ context, pOut.vtx[outCnt], data ];
}
ELSE pOut.vtx[outCnt].aux _ pIn.vtx[i].aux;
outCnt _ outCnt + 1;
};
IF dist >= 0. THEN {						-- put out point if inside
pOut.vtx[outCnt].coord.x _ pIn.vtx[i].coord.x;
pOut.vtx[outCnt].coord.y _ pIn.vtx[i].coord.y;
pOut.vtx[outCnt].coord.z _ pIn.vtx[i].coord.z;
pOut.vtx[outCnt].coord.ex _ pIn.vtx[i].coord.ex;
pOut.vtx[outCnt].coord.ey _ pIn.vtx[i].coord.ey;
pOut.vtx[outCnt].coord.ez _ pIn.vtx[i].coord.ez;
pOut.vtx[outCnt].shade.exn _ pIn.vtx[i].shade.exn;
pOut.vtx[outCnt].shade.eyn _ pIn.vtx[i].shade.eyn;
pOut.vtx[outCnt].shade.ezn _ pIn.vtx[i].shade.ezn;
pOut.vtx[outCnt].shade.r _ pIn.vtx[i].shade.r;
pOut.vtx[outCnt].shade.g _ pIn.vtx[i].shade.g;
pOut.vtx[outCnt].shade.b _ pIn.vtx[i].shade.b;
pOut.vtx[outCnt].shade.t _ pIn.vtx[i].shade.t;
pOut.vtx[outCnt].shade.er _ pIn.vtx[i].shade.er;
pOut.vtx[outCnt].shade.eg _ pIn.vtx[i].shade.eg;
pOut.vtx[outCnt].shade.eb _ pIn.vtx[i].shade.eb;
pOut.vtx[outCnt].shade.et _ pIn.vtx[i].shade.et;
pOut.vtx[outCnt].aux _ pIn.vtx[i].aux;
outCnt _ outCnt + 1;
};
lastDist _ dist;    last _ i;
ENDLOOP;
pOut.type _ pIn.type;
pOut.oneSided _ pIn.oneSided;
pOut.dir _ pIn.dir;
pOut.nVtces _ outCnt;
pOut.props _ pIn.props;
RETURN [ pOut, pIn ];
};	-- end Clip Proc
shape: REF ShapeInstance _ NARROW[ GetProp[poly.props, $Shape] ];
lerpProc: VertexInfoProc _ shape.shadingClass.lerpVtxAux;
orOfCodes: OutCode _ NoneOut;
poly2: REF Patch _ GetPatch[2 * poly.nVtces];		-- get temp patch, released below

IF poly.type # $ConvexPolygon AND poly.type # $PolyLine THEN {
SIGNAL ThreeDBasics.Error[[$Unimplemented, "Not clippable as polygon"]];
RETURN[ NIL ];
};
FOR i: NAT IN [0..poly.nVtces) DO 
orOfCodes _ LOOPHOLE[
Basics.BITOR[LOOPHOLE[orOfCodes], LOOPHOLE[poly.vtx[i].coord.clip]],
OutCode]; 
ENDLOOP;
IF orOfCodes.near    THEN [poly, poly2] _ Clip[  Near, poly, poly2]; 
IF orOfCodes.far      THEN [poly, poly2] _ Clip[    Far, poly, poly2]; 
IF orOfCodes.left     THEN [poly, poly2] _ Clip[    Left, poly, poly2]; 
IF orOfCodes.right   THEN [poly, poly2] _ Clip[  Right, poly, poly2]; 
IF orOfCodes.bottom THEN [poly, poly2] _ Clip[Bottom, poly, poly2];
IF orOfCodes.top     THEN [poly, poly2] _ Clip[    Top, poly, poly2];
ReleasePatch[poly2];								-- done with temp patch
RETURN[ poly ];
};

GetPatchClipState: PUBLIC PROC[ patch: REF Patch] ~ {
orOfCodes: OutCode _ NoneOut;    
andOfCodes: OutCode _ AllOut; 
FOR i: NAT IN [0..patch.nVtces) DO
orOfCodes _ LOOPHOLE[
Basics.BITOR[ LOOPHOLE[orOfCodes], LOOPHOLE[patch[i].coord.clip]],
OutCode];
andOfCodes _ LOOPHOLE[
Basics.BITAND[LOOPHOLE[andOfCodes], LOOPHOLE[patch[i].coord.clip]],
OutCode];
ENDLOOP;
IF andOfCodes # NoneOut 
THEN patch.clipState _ out 
ELSE IF orOfCodes = NoneOut 
THEN patch.clipState _ in
ELSE patch.clipState _ clipped;
};

GetClipCodeForPt: PUBLIC PROC[context: REF Context, pt: Triple] RETURNS[clip: OutCode] ~ { 
clip.bottom_ G3dPlane.DistanceToPoint[ pt, context.clippingPlanes[Bottom]] < 0.;
clip.top	_ G3dPlane.DistanceToPoint[ pt, context.clippingPlanes[Top]	] < 0.;
clip.left	_ G3dPlane.DistanceToPoint[ pt, context.clippingPlanes[Left]	] < 0.;
clip.right	_ G3dPlane.DistanceToPoint[ pt, context.clippingPlanes[Right]	] < 0.;
clip.near	_ G3dPlane.DistanceToPoint[ pt, context.clippingPlanes[Near]	] < 0.;
clip.far	_ G3dPlane.DistanceToPoint[ pt, context.clippingPlanes[Far]	] < 0.;
};

XfmPtToEyeSpace: PUBLIC PROC[context: REF Context, pt: Triple, xfm: Xfm3D _ NIL]
 						RETURNS[Triple, OutCode] ~ {
IF xfm = NIL THEN xfm _ context.eyeSpaceXfm;
pt _ Transform[ pt, xfm ];
RETURN[ pt, GetClipCodeForPt[context, pt] ];  
};
 
XfmTripleToDisplay: PUBLIC PROC[pt: Triple, xfm, display: ScaleAndAddXfm, offset: REAL]
							RETURNS[result: Triple] ~ {
aLilBit: REAL _ ScanConvert.justNoticeable * ScanConvert.justNoticeable;

IF pt.z <= 0.0 THEN {
SIGNAL ThreeDBasics.Error[[$MisMatch, "Negative depth"]];
pt.z _ .001;		-- fudge bad depths
};
result.x _ xfm.scaleX*pt.x/pt.z + xfm.addX; 			-- convert to normalized display coords
result.y _ xfm.scaleY*pt.y/pt.z + xfm.addY;
result.z _ xfm.scaleZ/pt.z + xfm.addZ;

result.x _ display.scaleX * result.x + display.addX;		-- convert to screen coordinates
result.y _ display.scaleY * result.y + display.addY;
result.z _ display.scaleZ * result.z + display.addZ;

result.x _ result.x - offset;		-- nojaggy tiler offsets by 1/2 pixel and spreads out by 1
result.y _ result.y - offset;
RETURN [ result ];
};
 
XfmPtToDisplay: PUBLIC PROC[context: REF Context, pt: Triple, 
									 shape: REF ShapeInstance _ NIL]
						 RETURNS[Triple] ~ {
result: Triple _ XfmTripleToDisplay[
pt: pt, 
xfm: context.eyeToNdc, 
display: context.ndcToPixels,
offset: IF context.antiAliasing THEN .5 ELSE 0.0 		-- nojaggy tiler offsets by 1/2 pixel
];
IF shape # NIL THEN {
xLo: NAT _ Real.Fix[ MAX[0.0, result.x - 2.0] ];
xHi: NAT _ Ceiling[ MIN[context.viewPort.w, result.x + 2.0] ];
yLo: NAT _ Real.Fix[ MAX[0.0, result.y - 2.0] ];
yHi: NAT _ Ceiling[ MIN[context.viewPort.h, result.y + 2.0] ];
IF shape.screenExtent.min.f > xLo THEN shape.screenExtent.min.f _ xLo;
IF shape.screenExtent.max.f < xHi THEN shape.screenExtent.max.f _ xHi;
IF shape.screenExtent.min.s > yLo THEN shape.screenExtent.min.s _ yLo;
IF shape.screenExtent.max.s < yHi THEN shape.screenExtent.max.s _ yHi;
};
RETURN [ result ]; 
};
 

BackFacing: PUBLIC PROC[ context: REF Context, poly: REF Patch, 
								useEyeSpace: BOOLEAN _ FALSE ] 
				RETURNS [FacingDir] ~ {
SELECT poly.type FROM
$ConvexPolygon 	=> IF useEyeSpace 
THEN {
this: VertexInfo _ poly.vtx[0];
next: VertexInfo _ poly.vtx[1];
last:  VertexInfo _ poly.vtx[2]; 
direction: Triple _ G3dVector.Normalize[G3dVector.Cross[
[next.coord.ex - this.coord.ex, next.coord.ey - this.coord.ey, next.coord.ez - this.coord.ez], 
[last.coord.ex - this.coord.ex,  last.coord.ey - this.coord.ey,  last.coord.ez - this.coord.ez] ] ];
dotDir: REAL _ G3dVector.Dot[[this.coord.ex, this.coord.ey, this.coord.ez] , direction]; 
IF dotDir > 0.0 THEN RETURN[back] ELSE IF dotDir < 0.0 THEN RETURN[front];
}
ELSE {						-- do check in image space, rejecting eensy polygon edges
s: REAL _ 1.0 / ScanConvert.justNoticeable;		-- scales visible feature size to 1
FOR i: NAT IN [0..poly.nVtces) DO
this: VertexInfo _ poly.vtx[i];
next: VertexInfo _ poly.vtx[(i+1) MOD poly.nVtces];
last:  VertexInfo _ poly.vtx[(i+poly.nVtces-1) MOD poly.nVtces]; 
zNorm: INT _  		-- integer computation of z-coord of normal (left-handed)
	  ( Real.Fix[s*next.coord.sx - s*this.coord.sx] )
   * ( Real.Fix[s*last.coord.sy - s*this.coord.sy]  )
 -   ( Real.Fix[s*next.coord.sy - s*this.coord.sy] )
   * ( Real.Fix[s*last.coord.sx - s*this.coord.sx]   );
zNorm _ zNorm *Sgn[context.ndcToPixels.scaleY] *Sgn[context.ndcToPixels.scaleX];
IF zNorm > 0 THEN RETURN[ back ] ELSE IF zNorm < 0 THEN RETURN[ front ];
ENDLOOP;
SIGNAL ThreeDBasics.Error[[$Condition, "Edges too small for stable arithmetic"]];
};
$Bezier 			=> {	
SIGNAL ThreeDBasics.Error[[$Unimplemented, "Backfacing for patches not done"]];
};
ENDCASE	=> SIGNAL ThreeDBasics.Error[[$Unimplemented, "Unknown type"]];
RETURN[ undetermined ];
};
ShadePoly: PUBLIC PROC[ context: REF Context, poly: REF Patch] ~ {
shape: REF ShapeInstance _ NARROW[ GetProp[poly.props, $Shape] ];
IF shape.shadingClass.shadingType # $HiddenLines THEN FOR i: NAT IN [0..poly.nVtces) DO
IF shape.shadingClass.shadingType = $Faceted THEN {  -- get normals from vertex coords
lVtx: NAT _ (i + poly.nVtces - 1) MOD poly.nVtces; 
nVtx: NAT _ (i + 1) MOD poly.nVtces;
[[ poly[i].shade.exn, poly[i].shade.eyn, poly[i].shade.ezn ]] _ G3dVector.Cross[
[  poly[nVtx].coord.ex - poly[i].coord.ex, 			-- in eyespace, so do left-handed
poly[nVtx].coord.ey - poly[i].coord.ey, 
poly[nVtx].coord.ez - poly[i].coord.ez  ],
[  poly[lVtx].coord.ex - poly[i].coord.ex, 
poly[lVtx].coord.ey - poly[i].coord.ey, 
poly[lVtx].coord.ez - poly[i].coord.ez  ]
];
};
poly[i] _ shape.shadingClass.shadeVtx[ context, poly[i], shape.shadingClass ];
ENDLOOP;
};
GetAmbientLight: PROC[context: REF Context, normal: Triple] RETURNS[ambnt: RGB] ~ {
IF context = NIL OR context.environment = NIL THEN RETURN[[.2, .2, .2]];
WITH GetProp[context.environment, $AmbientLight] SELECT FROM
clr: REF RGB	=> ambnt _ clr^;
light: REF ShapeInstance =>  {		-- light must be far away, treated as simple direction
dotNL: REAL _ G3dVector.Dot[
G3dVector.Normalize[ [light.centroid.ex, light.centroid.ey, light.centroid.ez] ],
G3dVector.Normalize[ normal ]
];
dotNL _ (dotNL + 1.0) / 2.0;			-- range ambient light over shadowed portions too
ambnt _ light.shadingClass.color;
ambnt.R _ ambnt.R*dotNL;    ambnt.G _ ambnt.G*dotNL;    ambnt.B _ ambnt.B*dotNL;
};
ENDCASE	=> ambnt _ [.2, .2, .2];
};

NoShadeVtx: ThreeDBasics.VertexInfoProc ~ {
shadingClass: REF ShadingClass _ NARROW[data];
shapeClr: RGB _ IF shadingClass # NIL THEN shadingClass.color ELSE defaultWhite;
shapeTrans: REAL _ IF shadingClass # NIL THEN shadingClass.transmittance ELSE 0.0;
vtx.shade.er _  vtx.shade.r * shapeClr.R;
vtx.shade.eg _ vtx.shade.g * shapeClr.G;
vtx.shade.eb _ vtx.shade.b * shapeClr.B;
IF shapeTrans > 0.0 THEN {						-- compute transmittance if transparent
vtx.shade.et _ vtx.shade.t * shapeTrans;								-- Transmittance
vtx.shade.et _ MAX[0.0, MIN[vtx.shade.et, 1.]];
};
RETURN[vtx];		-- avoids shading calculations for background polygons, shadows, etc.
};

ShadeVtx: PUBLIC ThreeDBasics.VertexInfoProc ~ {
shadingClass: REF ShadingClass _ NARROW[data];
shapeClr: RGB _ IF shadingClass # NIL THEN shadingClass.color ELSE defaultWhite;
shapeTrans: REAL _ IF shadingClass # NIL THEN shadingClass.transmittance ELSE 0.0;
shininess: REAL _ IF shadingClass # NIL THEN shadingClass.shininess ELSE 0.0;
shinyPwr: NAT _ Real.Round[shininess];
partShiny: REAL _ 1.0; 
toLightSrc, toEye: Triple;
dotNL, dotNE, sumHilite: REAL _ 0.0;
ambient, diffuse, specular, result: RGB _ [0.0, 0.0, 0.0];
vtxClr: RGB _ [vtx.shade.r * shapeClr.R, vtx.shade.g * shapeClr.G, vtx.shade.b * shapeClr.B];
IF vtx.props # NIL THEN {
ref: REF _  GetProp[vtx.props, $PartShiny];
IF ref # NIL THEN partShiny _ NARROW[ref, REF REAL]^;
};

toEye _ G3dVector.Normalize[[-vtx.coord.ex, -vtx.coord.ey, -vtx.coord.ez]];  -- direction to eye
[ [vtx.shade.exn, vtx.shade.eyn, vtx.shade.ezn] ] _ G3dVector.Normalize[
[vtx.shade.exn, vtx.shade.eyn, vtx.shade.ezn]				-- often not normalized
];

ambient _ GetAmbientLight[ context, [vtx.shade.exn, vtx.shade.eyn, vtx.shade.ezn] ];
ambient.R _  ambient.R * vtxClr.R;
ambient.G _ ambient.G * vtxClr.G;
ambient.B _ ambient.B * vtxClr.B;

IF context.lightSources # NIL THEN FOR i: NAT IN [0..context.lightSources.length) DO
lightClr: RGB _ context.lightSources[i].shadingClass.color;

toLightSrc _ G3dVector.Normalize[ [				-- vector to light source from surface vtx.
context.lightSources[i].centroid.ex - vtx.coord.ex,
context.lightSources[i].centroid.ey - vtx.coord.ey,
context.lightSources[i].centroid.ez - vtx.coord.ez
] ];

IF context.lightSources[i].orientation # [0.0, 0.0, 0.0] THEN { 		-- spotlight, get direction
dotLS, intensity: REAL;
shineDirection: Triple _ TransformVec[ context.lightSources[i].orientation,
														   context.eyeSpaceXfm ];
spotSpread: NAT _ Real.Fix[ context.lightSources[i].shadingClass.shininess ];
dotLS _ -G3dVector.Dot[toLightSrc, shineDirection];
IF dotLS > 0. THEN {								-- compute spotlight factor
binaryCount: NAT _ spotSpread;
intensity _ 1.;
WHILE  binaryCount > 0 DO				-- compute power by repeated squares
IF (binaryCount MOD 2) = 1 THEN intensity _ intensity*dotLS;
dotLS _ dotLS*dotLS;
binaryCount _ binaryCount/2;
ENDLOOP;
}
ELSE intensity _ 0.;
IF intensity < ScanConvert.justNoticeable THEN LOOP;	-- no effect, skip this light	
lightClr.R _ lightClr.R*intensity;
lightClr.G _ lightClr.G*intensity;
lightClr.B _ lightClr.B*intensity;
};

dotNL _ G3dVector.Dot[toLightSrc, [vtx.shade.exn, vtx.shade.eyn, vtx.shade.ezn]];
IF dotNL <= 0. THEN LOOP;							-- surface faces away from light, skip
diffuse.R _ (1. - ambient.R) * dotNL * lightClr.R * vtxClr.R;   -- surface facing the light
diffuse.G _ (1. - ambient.G) * dotNL * lightClr.G * vtxClr.G;
diffuse.B _ (1. - ambient.B) * dotNL * lightClr.B * vtxClr.B;

IF shinyPwr > 0 AND partShiny > 0.0 THEN { 		-- compute Phong specular component
pctHilite: REAL _ 0.0;
halfWay: Triple _ G3dVector.Normalize[		-- normalized average of vectors
G3dVector.Mul[ G3dVector.Add[toEye, toLightSrc], 0.5 ]
];
dotNormHalfWay: REAL _ G3dVector.Dot[ -- cos angle betw. normal and average
[vtx.shade.exn, vtx.shade.eyn, vtx.shade.ezn], 
halfWay
];
IF dotNormHalfWay > 0. THEN {
binaryCount: NAT _ shinyPwr;
pctHilite _ partShiny;
WHILE  binaryCount > 0 DO				-- compute power by repeated squares
IF (binaryCount MOD 2) = 1 THEN pctHilite _ pctHilite*dotNormHalfWay;
dotNormHalfWay _ dotNormHalfWay*dotNormHalfWay;
binaryCount _ binaryCount/2;
ENDLOOP;
IF pctHilite < 0.0 OR pctHilite > 1.0 
THEN SIGNAL ThreeDBasics.Error[[$MisMatch, "Highlight error"]];
};
specular.R _ (1.0 - diffuse.R - ambient.R) * pctHilite * lightClr.R;
specular.G _ (1.0 - diffuse.G - ambient.G) * pctHilite * lightClr.G;
specular.B _ (1.0 - diffuse.B - ambient.B) * pctHilite  * lightClr.B;
sumHilite _ sumHilite + pctHilite;
};
result.R _ result.R + diffuse.R + specular.R;
result.G _ result.G + diffuse.G + specular.G;
result.B _ result.B + diffuse.B + specular.B;
ENDLOOP;								-- end loop for each light source
result.R _ result.R + ambient.R;		   -- add in ambient light
result.G _ result.G + ambient.G;
result.B _ result.B + ambient.B;
vtx.shade.er _  MAX[0.0, MIN[result.R, 1.]];
vtx.shade.eg _ MAX[0.0, MIN[result.G, 1.]];
vtx.shade.eb _ MAX[0.0, MIN[result.B, 1.]];
IF shapeTrans > 0.0 
THEN {						-- compute transmittance if transparent
dotNE _ G3dVector.Dot[toEye, [vtx.shade.exn, vtx.shade.eyn, vtx.shade.ezn]];
dotNE _ 1.0 - ABS[dotNE];    dotNE _ 1.0 - (dotNE * dotNE);	-- invert, square, invert
vtx.shade.et _ dotNE * vtx.shade.t * shapeTrans; -- Transmittance as seen from eyepoint
vtx.shade.et _ MIN[1.0 - sumHilite, vtx.shade.et]; 		-- make highlights more opaque
vtx.shade.et _ MAX[0.0, MIN[vtx.shade.et, 1.]];
}
ELSE vtx.shade.et _ 0.0;
RETURN[vtx];
};
 
InitClasses[];

END.
˜ShapeUtilitiesImpl.mesa
Copyright c 1984, 1986 by Xerox Corporation.  All rights reserved.
Last Edited by: Crow, March 11, 1989 3:37:26 pm PST
Internal Declarations
Renamed Procedures
Global Variables
Caching Procedures
allocation avoidance structures - caches of peculiar data types 
Utility Procedures
Put shape & patch number on property list
Procedures for Manipulating Shapes
Transform Vertices and Centroid to Eye Space, calculate clip codes at vertices
Do gross clip test on bounding sphere, all in or all out allow rejection of entire object
Transform all vertices for a shape from eyespace to display coordinates
run through vertices and transform
Expand extent by two pixels, NOTE!! this is not complete in the presence of clipping, doesn't pick up clipped vertices
Compute Normals, Sum normals at polygon corners to get polygon normal

Calculate shades for Faceted shading (Used for quick display)
Sum normals for vertices given by adjacent polygon corners, only for polygons!
Procedures for Transformations and Clipping
Put out point if clip plane crossed
Compute outcode for one set of coordinates in eyespace
	Transform Vertex to Eye Space 
	Transform vertex from eyespace to display coordinates - local utility
	Transform vertex from eyespace to display coordinates
Procedures for Shading Patches
Assumes left-handed space (eye space or screen space)
Backfacing test based on first vertex and adjacent vertices
last:  VertexInfo _ poly.vtx[poly.nVtces - 1]; 
Adjusts for flip in screen-space transform (ndcToPixels) in y and/or x
Backfacing test based on convex hull being hidden behind its base


Get an ambient light value from the eyespace normal to the surface
PROC[ context: REF Context, vtx: VertexInfo, data: REF ANY _ NIL ] RETURNS[VertexInfo]
Calculate shade at vertices of polygon
Get ambient component of light
Do for each light source
Get Light Direction from Surface
Get Light Strength
Get Basic Lambertian Shade
Get Highlight Contribution
Add in Highlight, based on headroom left after diffuse and ambient light included
Accumulate diffuse and specular contributions from each light
Transmittance is cosine of angle between to eye and normal (modified for effect)

Κύ˜Ihead™šœ
Οm
œ7™BJ™3J˜š
Οk	˜	Jšœ	žœ.˜<Jšœ	žœ˜Jšœžœžœžœ˜#Jšœžœ%˜6Jšœ	žœžœ˜Jšœžœ˜"Jšœžœ˜'Jšœ
žœ-˜<Jšœ
žœ"˜1Jšœ	žœ˜#Jšœžœύ˜JšœžœP˜dJšœžœ˜%—J˜—
head2šœžœ
ž˜!I
ašžœi˜qMšžœ˜J˜Jšœž˜J˜—
head3š
Οb™Jšœ	žœ˜%JšžœžœžœΟc˜<Jšœ
žœ˜'Jšœžœ˜3Jšœ	žœ˜%J˜(J˜&Jšœžœ˜!Jšœžœ˜#Jšœžœ˜3Jšœ
žœ˜-Jšœžœ ˜5Jšœžœ˜/Jšœžœ˜1Jšœžœ˜)Jšœžœ˜!Jšœžœ˜1Jšœ
žœ˜'Jšœžœ!˜7Jšœžœ˜-Jšœžœ˜#Jšœžœ˜3Jšœžœ˜+Jšœžœ#˜;Jšœžœ˜3Jšœžœ˜/Jšœžœ!˜6Jšœžœ˜+Jšœžœ˜/Jšœžœ !˜LJšžœžœžœ
žœ
žœ
žœ
˜—š
Ÿ™JšΟn	œžœžœ˜MJš‘œžœžœ4˜gJš‘œ
žœ!žœ
žœžœžœ
žœ.˜uJš‘œžœ!žœ
žœžœ
žœž
œ&˜x—š
Ÿ™Mšœ	žœ	 (˜=M˜%Mšœžœ˜$—š
Ÿ™J™@Jšœ
žœžœ ˜TJšœžœ˜Jšœžœ
 $˜D
defaultš‘
œžœžœ
žœ˜?Jšžœ
žœžœ
˜Ošœžœ˜šžœ˜Ošžœžœ˜šžœ
ž
˜O˜$O˜"Ošœžœ
˜"O˜——Ošœžœ
˜Ošžœ˜O˜—š‘œžœžœ˜=Jšžœ
žœžœ
˜šžœ$žœ˜,Ošœžœ/˜@O˜+O˜O˜—šžœžœ$˜=Ošžœ
žœ=˜HOšžœ#˜'—O˜$O˜—Jšœžœžœ ˜VJšœžœ˜Jšœžœ
 $˜Cš‘œžœ
žœžœžœ
žœ˜>Jšžœ
žœžœ
˜Ošœžœ˜
šžœ˜Ošžœžœ
˜šžœ
ž
˜O˜"O˜Ošœžœ
˜ Ošžœžœžœ˜2O˜——Ošžœ˜O˜—š‘œžœžœ˜1Jšžœ
žœžœ
˜Ošžœžœ
žœ
žœ˜šžœ"žœ˜*Ošœ
žœ(˜8O˜(O˜O˜—šžœžœ!˜9Ošžœ
žœ8˜COšžœ˜#—O˜"O˜——š
Ÿ™š‘œž	œ
žœžœžœžœ˜7Mšžœ
žœžœ˜1M˜M˜—š
‘œžœ	žœžœ	žœ˜8J˜Jšžœžœ˜,J˜—š
‘œžœžœžœžœ˜:Jšœ	žœN˜[JšžœL˜RJ˜—š‘œžœžœ
žœ˜&Jšžœ:˜@Jšœ‘
˜—š‘	œžœ
žœ	žœ˜;Jšžœ8˜>J˜—š‘	œžœ	žœ+žœžœžœ˜€
Jšœžœžœ˜6Jšœžœžœ
˜'šœ %˜DJ˜BJ˜BJ˜—O˜O˜—š‘œž	œ˜!Mšžœ
žœ
˜J˜J˜—š‘œžœ
žœžœ
žœ	žœ˜sJšœ
žœž	œžœ!˜]Jšœ	žœ;˜GJšœžœ#˜2Jšœžœ+˜CJšœ	žœ;žœ*˜xJšœžœ8žœ6˜~JšœžœE˜Sšœžœžœ
žœ	˜)Jšžœ<ž
œAž˜Ž
Jšžœ
žœ
˜—J˜Jš	žœžœ
žœ
žœ ˜NJšœ) *˜SJ˜ J˜&Jšœ) ˜@Jšœžœ
žœžœ
žœ
žœ˜U˜Jš
 )™)—J˜>Jšœ.žœ
žœ˜Hšžœžœ
žœž˜%Jšœžœ˜Jšœ! #˜DJ˜*J˜(šžœžœ
˜šžœ˜Jš	œžœžœžœ
žœ˜/J˜IJ˜
—Jšžœžœ
˜—šžœ˜	šžœ !˜3J˜"O˜!O˜!O˜
—šžœ
žœ
žœ
žœ
žœ #˜NJšžœ+ ˜Kšžœžœžœ '˜IO˜GJ˜GJ˜GJ˜G˜.J˜,J˜—J˜———Jšžœ
˜—J˜——š
Ÿ"™"š‘œžœ
 .˜I˜J˜Jšœ	žœ
˜
Jšœž˜J˜—šœ' *˜QJ˜J˜J˜J˜—Jšœ9 %˜^J˜$J˜:J˜9JšœA ˜XJ˜ J˜9J˜7Jšœ= œ
˜PO˜AJ˜&J˜+J˜*O˜CJ˜—š
‘
œžœ
žœžœžœ˜qM™Nš‘œžœžœ˜<O™YIcodešœ
žœžœ
˜šžœžœ
ž˜#šœ
žœ˜+P˜:P˜P˜—Pšžœ"žœ
žœ	˜8Pšžœ
žœ!žœžœ
˜=Pšžœ
˜—Pš
žœ
žœ
žœ
žœ
žœ˜1O˜—J˜@˜IJšœ: ˜RJ˜J˜—J˜%
unitšžœžœΟi
Πci ˜QJšœ" ˜;Jšœ$ ˜<š
žœžœ
žœ
žœžœ
žœž˜Ešžœžœ
žœ˜Jšžœ˜Jšœ/ ˜Nšžœ˜šžœ˜J˜1šœžœ
˜Jšœžœ
žœ
žœ˜A—šœ
žœ
˜Jšœžœžœžœ˜A—J˜
—Jšžœ˜—J˜—Jšžœ
˜—Mšžœžœ˜8Jšžœžœ˜8J˜J˜—Jšžœ˜J˜J˜—š‘œžœ
žœžœžœ$žœžœ˜qO™GJšœžœ˜Jšœžœ˜šœžœžœ˜5Oš’œ™"—šžœžœ
žœ
žœžœ
žœžœ
˜Ešžœžœ
žœ˜Jšžœ˜šžœžœ˜˜&J˜J˜J˜Ošœžœžœžœ %˜VJ˜—šžœžœ˜Jšžœžœžœžœ˜<Jšžœžœžœžœ˜<J˜—J˜
—šžœ
žœžœ˜Jšžœžœ˜!Jšžœžœ˜-Jšžœ
žœ˜ Jšžœ
žœ˜.J˜—J˜—Jšžœ
˜—šžœžœ˜JšœžœU™vJšœžœžœ˜HJšœžœžœ˜GJ˜yJ˜—J˜J˜—š‘œžœ
žœžœ˜FMš’œ4™EOšœ	žœ˜J˜Jšœ
žœ5žœ
˜MJšœžœ2˜@Oš	žœžœ
žœ
žœ (˜Nšžœ#žœ˜+Jšžœ@˜FJšžœ˜	J˜—šžœ
žœ
žœ˜Jšœžœ'˜6J˜%J˜—Ošœ
žœžœ˜6Jšžœ
žœžœ:˜Xšžœžœ
žœžœ
˜(šžœžœ
žœ˜J˜Jšžœžœ
žœžœ˜Kšžœž˜šžœžœ
žœžœ
˜+J˜NJšžœ
˜—J˜'J˜J˜J˜šžœ
žœžœ .˜PJšžœ ˜7J˜<J˜—J˜—J˜—Jšžœ˜	—J˜LJ˜J™—š
‘
œžœ
žœ
žœžœ˜NJ™=š‘œžœžœžœ˜Bšžœžœ
žœž˜!J˜/J˜VJ˜XJ˜YJš	œžœ	žœžœžœ1˜pJšžœ
˜—J˜WJ˜XJ˜YJ˜—Jšœžœ˜Jšœžœ˜+Jšœžœ$˜<Jšœžœ2˜@Ošžœ#žœ
žœ '˜Yšžœžœ+žœ˜JOšžœF˜LOšžœ
˜O˜—šžœ6žœ˜Bšžœ
žœ
žœ˜Jšœžœ'˜6J˜%šžœžœ
žœžœ
˜(Jšœžœ˜$Jšžœ
˜—J˜*J˜—J˜J˜—Ošœžœžœ˜5šžœžœ
žœž˜'šžœžœ
žœ˜O˜'Ošœ'žœ˜-OšœD ˜XJ˜J˜J˜J˜J˜—Jšžœ
˜—J˜J˜—š
‘
œžœ
žœ
žœžœ˜KJ™NOšœ	žœžœ˜6Jšœ
žœ7žœ
˜Ošžœžœ
žœ˜Jšœžœ6˜GJ˜)J˜—šžœžœ
žœžœ
˜*šžœžœ
žœ˜Jšœžœ˜2JšœB ˜RJ˜—Jšžœ
˜—šžœ
žœžœ ˜.J˜@š	žœžœ
žœžœ 0˜\šžœžœ
žœ
žœžœ
žœžœ
˜DJšžœ'˜+J˜CJ˜<Jšžœ
˜—Jšžœ˜	—šžœžœ
žœžœ
˜)šžœžœ
žœ˜Jšžœ˜šžœ@˜Bšžœ˜J˜5J˜:J˜
—šžœ˜J˜,J˜——J˜—Jšžœ
˜—J˜—J˜HJ˜—š‘œžœžœžœ˜NMšœžœ
˜šžœžœ
žœ 3˜XM˜SM˜—š
žœžœ
žœ
žœžœ
žœž˜Bšžœžœ
žœ˜O˜EO˜BM˜ M˜ M˜ M˜ M˜—Mšžœ
˜—Mšžœžœ
žœ-˜MM˜——š
Ÿ+™+š‘œžœ
žœžœžœžœžœ˜Uš‘œžœžœžœžœžœ˜Tš	‘œžœžœžœ ˜Ršžœ˜"M˜M˜M˜—M˜—Mšœžœžœ
˜+Qšžœžœ
žœ &˜RM˜šžœžœ˜M˜5M˜M˜—Mšžœ!žœžœ˜Jšžœžœ
žœž˜ Mšœžœ
˜M˜$šžœžœžœžœ˜CMš
 #™#M˜-M˜NM˜NM˜NM˜QM˜QM˜QM˜PM˜PM˜PM˜NM˜NM˜NM˜MM˜QM˜QM˜QM˜Qšžœžœ
žœžœ
˜4šžœ˜šœžœžœ˜Mš	œ#žœ
žœžœ
žœ˜@M˜—M˜?M˜
—Mšžœ'˜+—M˜M˜—šžœžœ ˜4M˜.M˜.M˜.M˜0M˜0M˜0M˜2M˜2M˜2M˜.M˜.M˜.M˜.M˜0M˜0M˜0M˜0M˜&M˜M˜—M˜Mšžœ
˜—M˜M˜J˜M˜M˜Mšžœ˜Mšœ ˜—Qšœžœžœ ˜AO˜9O˜Jšœžœ% !˜PJ˜šžœžœžœ˜>JšžœB˜HJšžœžœ˜J˜—šžœžœ
žœžœ
˜"šœžœ
˜Jšœžœ
žœ
žœ˜DJ˜
—Jšžœ
˜—Jšžœžœ,˜EJšžœžœ-˜GJšžœžœ.˜HJšžœžœ-˜FJšžœžœ+˜CJšžœžœ,˜EJšœ ˜3Jšžœ	˜M˜—š‘œžœ
žœ	žœ˜5J˜!J˜šžœžœ
žœž˜"šœžœ
˜Jšœžœ
ž	œ
žœ˜BJ˜	—šœ
žœ
˜Jšœžœ
žœžœ˜CJ˜	—Jšžœ
˜—šžœ˜Jšžœ˜šžœ
žœ˜Jšžœ˜Jšžœ˜——O˜—š
‘œžœ
žœ
žœžœ˜[J™6J˜PJ˜LJ˜NJ˜PJ˜NJ˜LJ˜J˜—š‘œžœ
žœ
žœ#žœ	žœ˜tJ™Jšžœžœ
žœ˜,J˜Jšžœ(˜.J˜J˜
—š
‘œžœ
žœ3žœ	žœ˜zO™FOšœ	žœ<˜Išžœ
žœ˜Ošžœ3˜9Ošœ ˜!O˜—Ošœ/ '˜VO˜+O˜&O˜Jšœ6  ˜VJ˜4J˜5Jšœ :˜YJ˜Jšžœ˜J˜J˜
—š‘œžœ
žœ(žœžœ	žœ˜ƒ
O™6˜$O˜O˜J˜Ošœžœžœžœ %˜XO˜—šžœ	žœ
žœ˜Ošœžœ
žœ˜0Ošœžœžœ'˜>Ošœžœ
žœ˜0Ošœžœžœ'˜>Ošžœ žœ ˜FOšžœ žœ ˜FOšžœ žœ ˜FOšžœ žœ ˜FO˜—Ošžœ
˜J˜J˜
—O˜—š
Ÿ™š‘
œžœ
žœžœžœžœžœžœ˜„
M™5šžœž˜šœžœ
˜"šžœ˜M™;M˜M˜M˜!M™/	˜8M˜_M˜d—QšœžœM˜YIdefualtšžœžœ
žœžœ
žœžœ
žœ˜JO˜
—šžœ 9˜EOšœžœ& #˜Pšžœžœ
žœž˜!M˜Mšœ"žœ˜3Mšœ/žœ˜A
zdefaultšœžœ 9˜IM˜2M˜5M˜4M˜7—˜PO™F—Ošžœžœ
žœ	žœ
žœžœ
žœ
˜HOšžœ
˜—OšžœK˜QO˜——˜O™AOšžœI˜OO˜—Ošžœžœ6˜G—Ošžœ˜M˜M™—š
‘	œžœ
žœžœžœ˜BJšœžœžœ ˜Aš	žœ-ž	œžœ
žœž˜Wšžœ+žœ !˜VJšœžœžœ˜3Jšœžœžœ
˜$˜Pšœ. !˜OJ˜(J˜*—˜+J˜(J˜)—J˜—M˜—M˜NMšžœ
˜—M˜M™—š
‘œžœ
žœžœžœ˜SO™BOšžœžœ
žœžœ
žœ
žœ˜Hšžœ+žœ
ž˜<Ošœžœ
žœ˜šœžœ 6˜Všœžœ˜O˜QO˜O˜—Ošœ 1˜PO˜!O˜PO˜—Ošžœ˜ —J˜—š‘
œ!˜+Ošœžœžœ˜.Ošœ
žœžœžœ
žœžœ˜POšœžœžœžœ
žœžœ˜RO˜)O˜(O˜(šžœžœ '˜GOšœ0 ˜@Ošœžœžœ˜/O˜—Jšžœ E˜SO˜—š‘œžœ ˜0Ošžœžœ!žœ
žœžœžœ™VM™&Ošœžœžœ˜.Ošœ
žœžœžœ
žœžœ˜POšœžœžœžœ
žœžœ˜ROšœžœžœžœ
žœžœ˜MOšœ
žœ˜&Ošœžœ˜O˜Ošœžœ˜$Ošœ$žœ˜:OšœžœR˜]šžœ
žœ
žœ˜Ošœžœ#˜+Ošžœžœ
žœ
žœžœ
žœ˜5O˜—OšœM ˜`˜HOšœ1 ˜HO˜—M˜O™O˜TO˜"O˜!O˜!M˜š
žœžœ
žœ
žœžœ
žœ"ž˜TOš
 ™Ošœ
žœ/˜<O™ šœ' +˜RO˜3O˜3O˜2O˜—P˜O™šžœ7žœ ˜]Ošœžœ
˜O˜sOšœžœ>˜MP˜3šžœžœ #˜7Ošœ
žœ˜O˜šžœžœ $˜AOšžœžœžœ˜<O˜O˜Ošžœ
˜—O˜
—Ošžœ˜Ošžœ(žœ
žœ ˜SP˜"O˜"O˜"O˜—M˜O™O˜QOšžœ
žœ
žœ &˜FOšœ@ ˜[O˜=O˜>O™šžœžœžœ #˜POšœžœ˜šœ(  ˜HO˜6O˜—šœžœ &˜KO˜/O˜O˜—šžœžœ˜Ošœ
žœ˜O˜šžœžœ $˜AOšžœžœžœ&˜EO˜/O˜Ošžœ
˜—šžœžœ˜&Ošžœ
žœ4˜?—O˜—O™QO˜DO˜DO˜EO˜"O˜—O™=O˜-O˜-O˜-Ošžœ	 !˜1—Ošœ% ˜<O˜ O˜ Ošœžœžœ˜,Ošœžœžœ˜+Ošœžœžœ˜+šžœ˜šžœ '˜3O™PO˜LOšœžœ+ ˜UOšœ1 &˜WOšœžœ# ˜SOšœžœžœ˜/O˜
—Ošžœ˜—Jšžœ˜J˜J˜
—M™J˜—Jšžœ
˜—…—ŠΆ²K