<> <> <> <> DIRECTORY Atom USING [ GetPropFromList, PutPropOnList, PropList ], Real USING [ Round, Fix, MinusInfinity, PlusInfinity ], RealFns USING [ CosDeg, SinDeg, SqRt, TanDeg ], Basics USING [ BITOR, BITAND ], BasicTime USING [ PulsesToSeconds, GetClockPulses ], IO USING [ Flush, PutRope, STREAM ], Rope USING [ ROPE, Cat ], Convert USING [ RopeFromReal, RopeFromInt ], Process USING [ PauseMsec ], CedarProcess USING [ DoWithPriority ], ImagerSample USING [ Clip, GetBox, SampleMap ], ImagerPixel USING [ MakePixelMap, PixelMap ], ScanConvert USING [ justNoticeable ], G3dVector USING [ Add, Cross, Div, Dot, Length, Mul, Normalize, Null, Sub ], G3dMatrix USING [ Identity, Mul, TransformVec ], G3dPlane USING [ Error, FromThreePoints ], G3dRender USING [ AllOut,Box, BoxFromRectangle, ClipState, Context, ContextProc, Error, FacingDir, IntegerSequence, IntersectRectangles, IntegerPair, LoadShadingClass, LoadSurfaceType, NatSequence, NoneOut, OutCode, Pair, Patch, PatchProc, PatchSequence, Pixel, PtrPatchSequence, PtrPatch, Quad, RealSequence, Rectangle, RectangleFromBox, RGB, SetPosition, SetView, ShadingClass, ShadingSequence, ShadingValue, ShapeInstance, ShapeSequence, ShapeProc, SixSides, Triple, TripleSequence, Vertex, VertexInfo, VertexInfoProc, VertexInfoSequence, VertexSequence, Xfm3D ], ShapeUtilities USING [ BackFacing, ClipPoly, GetPatch, GetPolyShades, GetVtxNmls, GetVtxShades, ReleasePatch, ShapePatch, ShapePatchToPatch, SortSequence, XfmPtToDisplay, XfmToDisplay, XfmToEyeSpace], SurfaceRender USING [ ]; SurfaceRenderImpl: CEDAR MONITOR IMPORTS Atom, Basics, BasicTime, CedarProcess, Convert, ImagerPixel, IO, G3dMatrix, G3dPlane, G3dVector, Real, RealFns, Rope, ImagerSample, Process, ShapeUtilities, G3dRender EXPORTS SurfaceRender ~ BEGIN <> Context: TYPE ~ G3dRender.Context; ContextProc: TYPE ~ G3dRender.ContextProc; RGB: TYPE ~ G3dRender.RGB; -- [ r, g, b: REAL]; Pixel: TYPE ~ G3dRender.Pixel; IntegerPair: TYPE ~ G3dRender.IntegerPair; Pair: TYPE ~ G3dRender.Pair; Box: TYPE ~ G3dRender.Box; Rectangle: TYPE ~ G3dRender.Rectangle; SixSides: TYPE ~ G3dRender.SixSides; OutCode: TYPE ~ G3dRender.OutCode; NoneOut: OutCode ~ G3dRender.NoneOut; AllOut: OutCode ~ G3dRender.AllOut; Triple: TYPE ~ G3dRender.Triple; Quad: TYPE ~ G3dRender.Quad; TripleSequence: TYPE ~ G3dRender.TripleSequence; NatSequence: TYPE ~ G3dRender.NatSequence; IntegerSequence: TYPE ~ G3dRender.IntegerSequence; RealSequence: TYPE ~ G3dRender.RealSequence; ShapeInstance: TYPE ~ G3dRender.ShapeInstance; ShapeSequence: TYPE ~ G3dRender.ShapeSequence; FacingDir: TYPE ~ G3dRender.FacingDir; Patch: TYPE ~ G3dRender.Patch; PatchProc: TYPE ~ G3dRender.PatchProc; PatchSequence: TYPE ~ G3dRender.PatchSequence; PtrPatch: TYPE ~ G3dRender.PtrPatch; PtrPatchSequence: TYPE ~ G3dRender.PtrPatchSequence; ShapePatch: TYPE ~ ShapeUtilities.ShapePatch; SortSequence: TYPE ~ ShapeUtilities.SortSequence; Vertex: TYPE ~ G3dRender.Vertex; VertexSequence: TYPE ~ G3dRender.VertexSequence; VertexInfo: TYPE ~ G3dRender.VertexInfo; VertexInfoProc: TYPE ~ G3dRender.VertexInfoProc; VertexInfoSequence: TYPE ~ G3dRender.VertexInfoSequence; ShadingValue: TYPE ~ G3dRender.ShadingValue; ShadingSequence: TYPE ~ G3dRender.ShadingSequence; Xfm3D: TYPE ~ G3dRender.Xfm3D; Order: TYPE ~ {inFront, behind, coincident, intersects}; Bounds: TYPE ~ RECORD[left, right, bottom, top, near, far: REAL]; BoundsSequence: TYPE ~ RECORD[SEQUENCE length: NAT OF Bounds]; RenderData: TYPE ~ G3dRender.RenderData; ShadingClass: TYPE ~ G3dRender.ShadingClass; ShapeProc: TYPE ~ G3dRender.ShapeProc; -- PROC[ Context, ShapeInstance ] defaultWhite: REF RGB _ NEW[ RGB _ [1.0, 1.0, 1.0] ]; -- default color debug: BOOLEAN _ FALSE; <> 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 progressReportsPerFrame: INT _ 0; -- set to non zero for progress reports on long frames <> Sqr: PROCEDURE [number: REAL] RETURNS [REAL] ~ INLINE { RETURN[number * number]; }; ElapsedTime: PROC[startTime: REAL] RETURNS[Rope.ROPE] ~ { timeX100: REAL _ 100.0 * (CurrentTime[] - startTime); RETURN[ Rope.Cat[ Convert.RopeFromReal[ Real.Fix[timeX100] / 100.0 ], "s," ] ]; }; CurrentTime: PROC[] RETURNS[REAL] ~ { RETURN[ BasicTime.PulsesToSeconds[BasicTime.GetClockPulses[]] ]; }; GetPtrPatchClipState: PUBLIC PROC[ shape: REF ShapeInstance, patch: REF PtrPatch] ~ { orOfCodes: OutCode _ NoneOut; andOfCodes: OutCode _ AllOut; FOR j: NAT IN [0..patch.nVtces) DO k: NAT _ patch.vtxPtr[j]; orOfCodes _ LOOPHOLE[ Basics.BITOR[ LOOPHOLE[orOfCodes], LOOPHOLE[shape.vertex[k].clip]], OutCode]; andOfCodes _ LOOPHOLE[ Basics.BITAND[LOOPHOLE[andOfCodes], LOOPHOLE[shape.vertex[k].clip]], OutCode]; ENDLOOP; IF andOfCodes # NoneOut THEN patch.clipState _ out ELSE IF orOfCodes = NoneOut THEN patch.clipState _ in ELSE patch.clipState _ clipped; }; FlushLog: PUBLIC PROC [context: REF Context] ~ { log: IO.STREAM _ NARROW[Atom.GetPropFromList[context.props, $Log]]; IF log # NIL THEN IO.Flush[log]; }; <> ValidateContext: PUBLIC PROC[ context: REF Context ] ~ { j: CARDINAL _ 0; IF context.viewer = NIL AND context.pixels = NIL AND context.viewPort = NIL THEN SIGNAL G3dRender.Error[[$Fatal, "Image Area Undefined"]]; IF context.class = NIL THEN Process.PauseMsec[3000]; -- wait 3s. (maybe viewers settling) IF context.class = NIL THEN G3dRender.Error[[$Fatal, "No Class for Context"]]; IF context.viewer # NIL AND context.viewPort = NIL AND (context.pixels = NIL OR context.pixels.samplesPerPixel = 1) THEN context.class.updateViewer[context]; IF context.viewPort = NIL AND context.pixels # NIL THEN { ValidateView[context]; ValidateDisplay[context]; } ELSE { ValidateDisplay[context]; ValidateView[context]; }; IF context.shapes # NIL THEN { -- get light sources and visible shapes (convenience) IF context.lightSources = NIL OR context.lightSources.length < context.shapes.length THEN context.lightSources _ NEW[ ShapeSequence[context.shapes.length] ]; FOR i: NAT IN [0..context.shapes.length) DO IF context.shapes[i].class = NIL THEN G3dRender.LoadSurfaceType[context.shapes[i], $ConvexPolygon]; -- default IF context.shapes[i].class.type = $Light THEN { context.lightSources[j] _ context.shapes[i]; j _ j + 1; }; ENDLOOP; context.lightSources.length _ j; j _ 0; IF context.visibleShapes = NIL OR context.visibleShapes.length < context.shapes.length THEN context.visibleShapes _ NEW[ ShapeSequence[context.shapes.length] ]; FOR i: NAT IN [0..context.shapes.length) DO shape: REF ShapeInstance _ ValidateShape[context, context.shapes[i]]; IF shape # NIL THEN { context.visibleShapes[j] _ shape; j _ j + 1; }; ENDLOOP; context.visibleShapes.length _ j; }; }; ValidateDisplay: PUBLIC PROC[ context: REF Context ] ~ { <> IF context.displayInValid THEN { context.class.validateDisplay[context]; IF context.shapes # NIL THEN FOR i: NAT IN [0..context.shapes.length) DO context.shapes[i].vtcesInValid _ TRUE; context.shapes[i].shadingInValid _ TRUE; ENDLOOP; G3dRender.SetView[ -- get new screen dimensions into transformations context: context, eyePoint: context.eyePoint, ptOfInterest: context.ptOfInterest, fieldOfView: context.fieldOfView, rollAngle: context.rollAngle, upDirection: context.upDirection, hitherLimit: context.hitherLimit, yonLimit: context.yonLimit ]; IF context.window = NIL THEN context.window _ WindowFromViewPort[context]; -- fit to viewprt }; context.extentCovered _ [[0,0], [0,0]]; -- clear coverage (new frame, alpha buffer, or display) context.displayInValid _ FALSE; }; ValidateView: PUBLIC PROC[ context: REF Context ] ~ { IF context.viewPort = NIL THEN { -- evidently not using a viewer s: ARRAY [0..5) OF ImagerSample.SampleMap _ ALL[NIL]; pixels: ImagerPixel.PixelMap _ NARROW[ Atom.GetPropFromList[ context.displayProps, $FullDisplayMemory ] ]; IF pixels # NIL THEN context.pixels _ pixels ELSE IF context.pixels = NIL THEN SIGNAL G3dRender.Error[[$MisMatch, "no pixel memory"]]; context.viewPort _ NEW[ Rectangle _ G3dRender.RectangleFromBox[ ImagerSample.GetBox[context.pixels[0]] ] ]; context.viewPort^ _ G3dRender.IntersectRectangles[ context.viewPort^, context.preferredViewPort -- clip viewPort to preferredViewPort ]; context.ndcToPixels _ [ -- going to VM so render with origin at top left context.viewPort.w-1.0, -(context.viewPort.h-1.0), REAL[context.depthResolution-1], 0.0, context.viewPort.h-1.0, 0.0 -- last line scales, this line adds ]; FOR i: NAT IN [0..context.pixels.samplesPerPixel) DO -- re-address pixelmap s[i] _ ImagerSample.Clip[ context.pixels[i], G3dRender.BoxFromRectangle[context.viewPort^] ]; ENDLOOP; context.pixels _ ImagerPixel.MakePixelMap[s[0], s[1], s[2], s[3], s[4]]; }; IF context.window = NIL THEN { context.window _ WindowFromViewPort[context]; context.viewInValid _ TRUE; }; IF context.viewInValid THEN SetView[ context, context.eyePoint, context.ptOfInterest, context.fieldOfView, context.rollAngle, context.upDirection, context.hitherLimit, context.yonLimit ]; context.viewInValid _ FALSE; IF context.pixels # NIL -- check for mismatched viewPort and pixel storage THEN IF context.pixels.box.max.f < context.viewPort.w OR context.pixels.box.max.s < context.viewPort.h THEN SIGNAL G3dRender.Error[[$MisMatch, "pixel memory smaller than viewport"]]; }; ValidateShape: PUBLIC ShapeProc ~ { <> <> render: REF RenderData _ NARROW[shape.renderData]; IF context.stopMe^ THEN RETURN[shape]; IF shape.shadingClass = NIL THEN G3dRender.LoadShadingClass[shape]; -- load default IF Atom.GetPropFromList[shape.props, $Hidden] # NIL AND shape.class.type # $Light THEN RETURN[NIL]; -- not visible, removed from scene temporarily IF shape.positionInValid THEN G3dRender.SetPosition[ shape ]; IF shape.boundingRadius = 0.0 THEN GetBoundingSphere[ shape ]; IF shape.vtcesInValid THEN { -- do only if object or eyespace transform has moved << Transform vertices to eyespace, get clip state of vertices and whole shape>> shape.clipState _ ShapeUtilities.XfmToEyeSpace[ context, shape ]; }; IF shape.class.validate # NIL THEN [] _ shape.class.validate[context, shape, data]; -- get shading, etc. IF shape.clipState # out THEN { << Transform vertices to screen coordinates, get screen extent for whole shape>> ShapeUtilities.XfmToDisplay[context, shape ]; }; IF shape.clipState # out AND shape.surface # NIL THEN RETURN[shape] ELSE RETURN[NIL]; }; ValidatePolyhedron: PUBLIC ShapeProc ~ { <> <> doAlways: BOOLEAN _ IF data # NIL THEN TRUE ELSE FALSE; xfm: Xfm3D _ G3dMatrix.Mul[shape.position, context.eyeSpaceXfm]; IF GetProp[ shape.shadingProps, $VtxInfoComputed] = NIL THEN ShapeUtilities.GetVtxNmls[context, shape]; IF shape.vtcesInValid AND (shape.clipState # out OR doAlways) THEN { IF shape.shade # NIL THEN FOR i: NAT IN [0..shape.shade.length) DO OPEN shape.shade[i]; -- transform normal vectors for shading, backfacing test [ [exn, eyn, ezn] ] _ G3dMatrix.TransformVec[ [xn, yn, zn] , xfm]; ENDLOOP; IF shape.surface # NIL THEN { -- get clipping info for patches patch: REF PtrPatchSequence _ NARROW[shape.surface]; FOR i: NAT IN [0..shape.numSurfaces) DO IF patch[i] # NIL THEN IF shape.clipState = in THEN patch[i].clipState _ in -- unclipped, inside ELSE IF shape.clipState = clipped THEN GetPtrPatchClipState[ shape, patch[i] ] -- evaluate clipping tags ELSE patch[i].clipState _ out; ENDLOOP; }; }; IF shape.shadingInValid AND (shape.clipState # out OR doAlways) THEN { shadingType: REF ANY _ shape.shadingClass.shadingType; SELECT shadingType FROM $Faceted => { polyShade: REF ShadingSequence; IF GetProp[shape.shadingProps, $PolygonInfoComputed] = NIL THEN ShapeUtilities.GetPolyShades[ context, shape ]; -- get data structure for facets polyShade _ shape.shadingClass.patchShade; IF shape.vtcesInValid THEN FOR i: NAT IN [0..polyShade.length) DO IF polyShade[i] # NIL THEN { OPEN polyShade[i]; -- transform normal vectors [ [exn, eyn, ezn] ] _ G3dMatrix.TransformVec[ [xn, yn, zn] , xfm]; }; ENDLOOP; ShapeUtilities.GetPolyShades[ context, shape ]; -- shade polygons (2nd call sometimes) }; $Smooth, $ShadedLines => ShapeUtilities.GetVtxShades[ context, shape ]; -- shade vtces $Lines, $HiddenLines, $NormaledLines => IF context.antiAliasing THEN ShapeUtilities.GetVtxShades[ context, shape ]; NIL => {}; -- For lights, this is a little shaky, what does no shading mean??!! ENDCASE => WITH shadingType SELECT FROM shadingProc: REF ShapeProc => [] _ shadingProc[ context, shape ]; -- supplied proc ENDCASE => G3dRender.Error[[$MisMatch, "Unknown Shading Type"]]; shape.shadingInValid _ FALSE; }; shape.vtcesInValid _ FALSE; RETURN[shape]; }; ValidateRopeShape: PUBLIC ShapeProc ~ { <> <> shape.shadingInValid _ FALSE; shape.vtcesInValid _ FALSE; RETURN[shape]; }; GetBoundingSphere: PUBLIC PROC[shape: REF ShapeInstance] ~ { <> { min, max: Triple; min _ max _ [shape.vertex[0].x, shape.vertex[0].y, shape.vertex[0].z]; FOR i: NAT IN (0..shape.vertex.length) DO -- get min and max in x, y, and z IF shape.vertex[i] # NIL THEN { IF shape.vertex[i].x < min.x THEN min.x _ shape.vertex[i].x ELSE IF shape.vertex[i].x > max.x THEN max.x _ shape.vertex[i].x; IF shape.vertex[i].y < min.y THEN min.y _ shape.vertex[i].y ELSE IF shape.vertex[i].y > max.y THEN max.y _ shape.vertex[i].y; IF shape.vertex[i].z < min.z THEN min.z _ shape.vertex[i].z ELSE IF shape.vertex[i].z > max.z THEN max.z _ shape.vertex[i].z; }; ENDLOOP; shape.centroid.x _ (min.x + max.x) / 2; -- get middle point in each coordinate shape.centroid.y _ (min.y + max.y) / 2; shape.centroid.z _ (min.z + max.z) / 2; shape.boundingRadius _ 0.; FOR i: NAT IN [0..shape.vertex.length) DO -- find radius radius: REAL _ RealFns.SqRt[ Sqr[shape.vertex[i].x - shape.centroid.x] + Sqr[shape.vertex[i].y - shape.centroid.y] + Sqr[shape.vertex[i].z - shape.centroid.z] ]; IF radius > shape.boundingRadius THEN shape.boundingRadius _ radius; ENDLOOP; }; }; SetView: PUBLIC PROC[context: REF Context, eyePoint, ptOfInterest: Triple, fieldOfView: REAL _40.0, rollAngle: REAL _ 0.0, upDirection: Triple _ [ 0., 0., 1.], hitherLimit: REAL _ .01, yonLimit: REAL _ 1000.0] ~ { context.eyePoint _ eyePoint; context.ptOfInterest _ ptOfInterest; context.fieldOfView _ fieldOfView; context.rollAngle _ rollAngle; context.upDirection _ upDirection; context.hitherLimit _ hitherLimit; context.yonLimit _ yonLimit; SetEyeSpace[ context ]; IF context.shapes # NIL THEN FOR i: NAT IN [0..context.shapes.length) DO context.shapes[i].vtcesInValid _ TRUE; -- eyespace and image space will change IF context.shapes[i].shadingClass.shininess > 0.0 OR context.shapes[i].shadingClass.transmittance > 0.0 THEN context.shapes[i].shadingInValid _ TRUE; -- highlights and trans. will change ENDLOOP; }; SetEyeSpace: PUBLIC PROC[ context: REF Context ] ~ { in, right, up, normal: Triple; mtx: Xfm3D; wndw: Rectangle; viewSize, xSize, ySize, aspectRatio: REAL; IF context.viewPort.h <= 0 OR context.viewPort.w <= 0 THEN RETURN[]; <> in _ G3dVector.Normalize[G3dVector.Sub[context.ptOfInterest, context.eyePoint]]; IF G3dVector.Null[in] THEN SIGNAL G3dRender.Error[[$MisMatch, "Eye and Pt of Interest identical"]]; right _ G3dVector.Normalize[G3dVector.Cross[in, context.upDirection]]; IF G3dVector.Null[right] THEN right _ [1.0, 0.0, 0.0]; -- looking straight down up _ G3dVector.Normalize[G3dVector.Cross[right, in]]; <> context.eyeSpaceXfm _ G3dMatrix.Identity[]; context.eyeSpaceXfm[0][0] _ right.x; context.eyeSpaceXfm[1][0] _ right.y; context.eyeSpaceXfm[2][0] _ right.z; context.eyeSpaceXfm[3][0] _ -G3dVector.Dot[right, context.eyePoint]; context.eyeSpaceXfm[0][1] _ up.x; context.eyeSpaceXfm[1][1] _ up.y; context.eyeSpaceXfm[2][1] _ up.z; context.eyeSpaceXfm[3][1] _ -G3dVector.Dot[up, context.eyePoint]; context.eyeSpaceXfm[0][2] _ in.x; context.eyeSpaceXfm[1][2] _ in.y; context.eyeSpaceXfm[2][2] _ in.z; context.eyeSpaceXfm[3][2] _ -G3dVector.Dot[in, context.eyePoint]; mtx _ G3dMatrix.Identity[]; -- Roll about z-axis, clockwise mtx[0][0] _ RealFns.CosDeg[context.rollAngle]; mtx[0][1] _ -RealFns.SinDeg[context.rollAngle]; mtx[1][0] _ RealFns.SinDeg[context.rollAngle]; mtx[1][1] _ RealFns.CosDeg[context.rollAngle]; context.eyeSpaceXfm _ G3dMatrix.Mul[context.eyeSpaceXfm, mtx]; <> IF NOT (context.window.w > 0.0 AND context.window.h > 0.0) THEN RETURN[]; aspectRatio _ context.pixelAspectRatio * (context.viewPort.w/context.viewPort.h); xSize _ IF aspectRatio > 1.0 THEN 1.0 ELSE aspectRatio; ySize _ IF aspectRatio < 1.0 THEN 1.0 ELSE 1.0 / aspectRatio; wndw.x _ MIN[xSize, MAX[-xSize, context.window.x] ]; wndw.w _ MIN[xSize-wndw.x, context.window.w ]; wndw.y _ MIN[ySize, MAX[-ySize, context.window.y] ]; wndw.h _ MIN[ySize-wndw.y, context.window.h ]; viewSize _ 2.0*RealFns.TanDeg[context.fieldOfView/2.0]; -- scale factor for angle of view <> context.clippingPlanes[Near] _ [0., 0., 1., -context.hitherLimit]; context.clippingPlanes[Far] _ [0., 0., -1., context.yonLimit]; <> normal _ G3dVector.Normalize[[1., 0., -(wndw.x * viewSize/2.)]]; context.clippingPlanes[Left] _ [normal.x, 0., normal.z, 0.]; normal _ G3dVector.Normalize[[-1., 0., (wndw.x + wndw.w) * viewSize/2.]]; context.clippingPlanes[Right] _ [normal.x, 0., normal.z, 0.]; normal _ G3dVector.Normalize[[0., 1., -(wndw.y * viewSize/2.)]]; context.clippingPlanes[Bottom] _ [0., normal.y, normal.z, 0.]; normal _ G3dVector.Normalize[[0., -1., (wndw.y + wndw.h) * viewSize/2.]]; context.clippingPlanes[Top] _ [0., normal.y, normal.z, 0.]; <> context.eyeToNdc.addX _ -(wndw.x / wndw.w); context.eyeToNdc.addY _ -(wndw.y / wndw.h); context.eyeToNdc.addZ _ 1.0/(1.0 - context.hitherLimit/context.yonLimit); context.eyeToNdc.scaleX _ 1.0/(wndw.w * viewSize / 2.0); context.eyeToNdc.scaleY _ 1.0/(wndw.h * viewSize / 2.0); context.eyeToNdc.scaleZ _ -context.hitherLimit/(1. - context.hitherLimit/context.yonLimit); }; WindowFromViewPort: PUBLIC PROC[context: REF Context] RETURNS[REF Rectangle] ~ { <> window: REF Rectangle _ NEW[Rectangle]; vp: Rectangle; IF context.viewPort = NIL OR context.viewPort.h <= 0.0 OR context.viewPort.w <= 0.0 THEN RETURN[ NIL ]; vp _ [ context.viewPort.x * context.pixelAspectRatio, context.viewPort.y, context.viewPort.w * context.pixelAspectRatio, context.viewPort.h ]; IF vp.w > vp.h THEN { window.x _ -1.0; window.w _ 2.0; window.y _ -vp.h / vp.w; window.h _ 2.0 * vp.h / vp.w; } ELSE { window.y _ -1.0; window.h _ 2.0; window.x _ -vp.w / vp.h; window.w _ 2.0 * vp.w / vp.h; }; RETURN[ window ]; }; <> GetBounds: PROC[patch: REF PtrPatch, shape: REF ShapeInstance] RETURNS[pBnds: Bounds] ~ { <> pBnds.near _ pBnds.far _ shape.vertex[patch.vtxPtr[0]].ez; pBnds.left _ pBnds.right _ shape.vertex[patch.vtxPtr[0]].sx; pBnds.bottom _ pBnds.top _ shape.vertex[patch.vtxPtr[0]].sy; FOR j: NAT IN [1..patch.nVtces) DO -- get bounds in depth, on display pBnds.near _ MIN[pBnds.near, shape.vertex[patch.vtxPtr[j]].ez]; pBnds.far _ MAX[pBnds.far, shape.vertex[patch.vtxPtr[j]].ez]; pBnds.left _ MIN[pBnds.left, shape.vertex[patch.vtxPtr[j]].sx]; pBnds.right _ MAX[pBnds.right, shape.vertex[patch.vtxPtr[j]].sx]; pBnds.bottom _ MIN[pBnds.bottom, shape.vertex[patch.vtxPtr[j]].sy]; pBnds.top _ MAX[pBnds.top, shape.vertex[patch.vtxPtr[j]].sy]; ENDLOOP; }; GetPlane: PROC[patch: REF PtrPatch, shape: REF ShapeInstance] RETURNS[plane: Quad] ~ { <> p1, p2, p3: Triple; vtx: REF Vertex; vtx _ shape.vertex[patch.vtxPtr[0]]; p1 _ [vtx.ex, vtx.ey, vtx.ez]; vtx _ shape.vertex[patch.vtxPtr[1]]; p2 _ [vtx.ex, vtx.ey, vtx.ez]; vtx _ shape.vertex[patch.vtxPtr[2]]; p3 _ [vtx.ex, vtx.ey, vtx.ez]; plane _ G3dPlane.FromThreePoints[p1, p2, p3, TRUE]; -- get normalized plane RETURN[ [plane.x*100.0, plane.y*100.0, plane.z*100.0, plane.w*100.0] ]; -- scale up }; precisionLimit: REAL _ 0.0001; -- limits precision of intersection calc. to one part in 10,000 CheckAgainstPlane: PROC[nPatch: REF ShapePatch, plane: Quad] RETURNS[order: Order] ~ { <> shape: REF ShapeInstance _ nPatch.shape; patches: REF PtrPatchSequence _ NARROW[shape.surface]; patch: REF PtrPatch _ patches[nPatch.patch]; minusSum, plusSum, side: REAL _ 0.0; FOR j: NAT IN [0..patch.nVtces) DO vtx: REF Vertex _ shape.vertex[patch.vtxPtr[j]]; pt: Triple _ [vtx.ex, vtx.ey, vtx.ez]; dist: REAL _ pt.x*plane.x + pt.y*plane.y + pt.z*plane.z + plane.w; -- eval plane eq. IF dist < 0.0 THEN minusSum _ minusSum - dist ELSE plusSum _ plusSum + dist ENDLOOP; IF minusSum + plusSum < precisionLimit THEN RETURN[coincident]; -- coincident planes IF minusSum < precisionLimit*plusSum THEN side _ 1.0 ELSE IF plusSum < precisionLimit*minusSum THEN side _ -1.0 ELSE RETURN[intersects]; IF ABS[plane.w] < precisionLimit THEN RETURN[behind]; -- clip plane on edge (goes thru eye) IF plane.w * side > 0.0 THEN RETURN[inFront] -- all points of nPatch between plane and eyepoint (origin) ELSE RETURN[behind]; -- all points of nPatch on other side of plane }; ClipPolyToPlane: PROC[context: REF Context, nPatch: REF ShapePatch, plane: Quad] RETURNS[p1, p2: REF ShapePatch]~ { <> <> GetSurfacePlace: PROC[] RETURNS[place: INT32] ~ { -- place to add 2 polys place _ NARROW[GetProp[shape.props, $ClippedPatches], REF INT32]^; IF place+1 >= patches.maxLength THEN { newPatches: REF PtrPatchSequence _ NEW[ PtrPatchSequence[place + MAX[16, INTEGER[place/8]]] ]; newPatches.length _ patches.length; FOR i: NAT IN [0..INTEGER[place]) DO newPatches[i] _ patches[i]; ENDLOOP; shape.surface _ patches _ newPatches; }; shape.props _ PutProp[ shape.props, $ClippedPatches, NEW[INT32 _ place+2] ]; IF patchInfo # NIL THEN { IF place+1 >= patchInfo.maxLength THEN { newPatchInfo: REF ShadingSequence _ NEW[ ShadingSequence[place + MAX[16, INTEGER[place/8]]] ]; newPatchInfo.length _ patchInfo.length; FOR i: NAT IN [0..INTEGER[place]) DO newPatchInfo[i] _ patchInfo[i]; ENDLOOP; patchInfo _ shape.shadingClass.patchShade _ newPatchInfo; }; }; }; GetVertexPlace: PROC[] RETURNS[place: INT32] ~ { -- place to add 1 vertex place _ NARROW[GetProp[shape.props, $ClippedVertices], REF INT32]^; IF place >= shape.vertex.maxLength THEN { newVertices: REF VertexSequence _ NEW[ VertexSequence[place + MAX[16, INTEGER[place/8]]] ]; newShades: REF ShadingSequence _ NEW[ ShadingSequence[place + MAX[16, INTEGER[place/8]]] ]; newVertices.length _ shape.vertex.length; FOR i: NAT IN [0..INTEGER[place]) DO newVertices[i] _ shape.vertex[i]; ENDLOOP; newShades.length _ shape.shade.length; FOR i: NAT IN [0..INTEGER[place]) DO newShades[i] _ shape.shade[i]; ENDLOOP; shape.vertex _ newVertices; shape.shade _ newShades; }; shape.props _ PutProp[ shape.props, $ClippedVertices, NEW[INT32 _ place+1] ]; }; shape: REF ShapeInstance _ nPatch.shape; lerpProc: VertexInfoProc _ shape.shadingClass.lerpVtxAux; patches: REF PtrPatchSequence _ NARROW[shape.surface]; patchInfo: REF ShadingSequence _ shape.shadingClass.patchShade; patch: REF PtrPatch _ patches[nPatch.patch]; patch1, patch2: PtrPatch; i1, i2, place: NAT _ 0; lastVtx: REF Vertex _ shape.vertex[patch.vtxPtr[patch.nVtces-1]]; lastShade: REF ShadingValue _ shape.shade[patch.vtxPtr[patch.nVtces-1]]; lastDist: REAL _ lastVtx.ex*plane.x + lastVtx.ey*plane.y + lastVtx.ez*plane.z + plane.w; IF lerpProc # NIL THEN SIGNAL G3dRender.Error[[$Unimplemented, "Aux not done yet "]]; patch1.type _ patch2.type _ patch.type; patch1.oneSided _ patch2.oneSided _ patch.oneSided; patch1.clipState _ patch2.clipState _ patch.clipState; patch1.dir _ patch2.dir _ patch.dir; patch1.props _ patch2.props _ patch.props; patch1.vtxPtr _ NEW[NatSequence[patch.nVtces+2]]; patch2.vtxPtr _ NEW[NatSequence[patch.nVtces+2]]; FOR j: NAT IN [0..patch.nVtces) DO vtx: REF Vertex _ shape.vertex[patch.vtxPtr[j]]; shade: REF ShadingValue _ shape.shade[patch.vtxPtr[j]]; dist: REAL _ vtx.ex*plane.x + vtx.ey*plane.y + vtx.ez*plane.z + plane.w; -- eval plane eq. IF lastDist * dist < 0.0 THEN { -- intersection, copy computed vertex to both newVtx: Vertex; newShade: ShadingValue; b: REAL _ dist / (dist - lastDist); a: REAL _ 1.0 - b; newVtx.x _ vtx.x * a + lastVtx.x * b; newVtx.y _ vtx.y * a + lastVtx.y * b; newVtx.z _ vtx.z * a + lastVtx.z * b; newVtx.ex _ vtx.ex * a + lastVtx.ex * b; newVtx.ey _ vtx.ey * a + lastVtx.ey * b; newVtx.ez _ vtx.ez * a + lastVtx.ez * b; [[newVtx.sx, newVtx.sy, newVtx.sz]] _ ShapeUtilities.XfmPtToDisplay[ context, [newVtx.ex, newVtx.ey, newVtx.ez] ]; newShade.exn _ shade.exn*a + lastShade.exn*b; newShade.eyn _ shade.eyn*a + lastShade.eyn*b; newShade.ezn _ shade.ezn*a + lastShade.ezn*b; newShade.r _ shade.r * a + lastShade.r * b; newShade.g _ shade.g * a + lastShade.g * b; newShade.b _ shade.b * a + lastShade.b * b; newShade.t _ shade.t * a + lastShade.t* b; newShade.er _ shade.er * a + lastShade.er * b; newShade.eg _ shade.eg * a + lastShade.eg * b; newShade.eb _ shade.eb * a + lastShade.eb * b; newShade.et _ shade.et * a + lastShade.et * b; <> <> <> <> <<];>> <> <<}>> <> place _ GetVertexPlace[]; -- store clipped pt with shape shape.vertex[place] _ NEW[Vertex _ newVtx]; shape.shade[place] _ NEW[ShadingValue _ newShade]; patch1.vtxPtr[i1] _ patch2.vtxPtr[i2] _ place; i1 _ i1+1; i2 _ i2+1; }; IF dist = 0.0 THEN { -- right on plane, copy to both sides patch1.vtxPtr[i1] _ patch.vtxPtr[j]; i1 _ i1+1; patch2.vtxPtr[i2] _ patch.vtxPtr[j]; i2 _ i2+1; } ELSE IF dist*plane.w > 0.0 OR (plane.w = 0.0 AND dist > 0.0) THEN { patch1.vtxPtr[i1] _ patch.vtxPtr[j]; i1 _ i1+1; } -- on eye side of plane ELSE { patch2.vtxPtr[i2] _ patch.vtxPtr[j]; i2 _ i2+1; }; -- on far side of plane lastDist _ dist; lastVtx _ vtx; lastShade _ shade; ENDLOOP; patch1.nVtces _ i1; patch2.nVtces _ i2; IF i1 < 3 OR i2 < 3 THEN SIGNAL G3dRender.Error[[$MisMatch, "Degenerate polygon"]]; place _ GetSurfacePlace[]; patches[place] _ NEW[PtrPatch _ patch1]; patches[place+1] _ NEW[PtrPatch _ patch2]; IF patchInfo # NIL THEN { patchInfo[place] _ patchInfo[place+1] _ patchInfo[nPatch.patch]; }; p1 _ NEW[ShapePatch _ [shape, place, 0, 0, nPatch.awayness]]; p2 _ NEW[ShapePatch _ [shape, place+1, 0, 0, nPatch.awayness]]; }; LineSeparable: PROC[in1, in2: REF ShapePatch] RETURNS[BOOLEAN] ~ { <> overlap: REAL; ptr1, ptr2: NAT; <> centroid1, centroid2: Pair _ [0.0, 0.0]; patches1: REF PtrPatchSequence _ NARROW[in1.shape.surface]; patches2: REF PtrPatchSequence _ NARROW[in2.shape.surface]; patch1: REF PtrPatch _ patches1[in1.patch]; patch2: REF PtrPatch _ patches2[in2.patch]; FOR j: NAT IN [0..patch1.nVtces) DO vtx: REF Vertex _ in1.shape.vertex[patch1.vtxPtr[j]]; centroid1.x _ centroid1.x + vtx.sx; centroid1.y _ centroid1.y + vtx.sy; ENDLOOP; FOR j: NAT IN [0..patch2.nVtces) DO vtx: REF Vertex _ in2.shape.vertex[patch2.vtxPtr[j]]; centroid2.x _ centroid2.x + vtx.sx; centroid2.y _ centroid2.y + vtx.sy; ENDLOOP; centroid1.x _ centroid1.x / patch1.nVtces; centroid1.y _ centroid1.y / patch1.nVtces; centroid2.x _ centroid2.x / patch2.nVtces; centroid2.y _ centroid2.y / patch2.nVtces; <> { max1, min2: REAL; cntrVec: Pair _ [ centroid2.x - centroid1.x, centroid2.y - centroid1.y ]; -- from 1 to 2 cntrVecMag: REAL _ RealFns.SqRt[cntrVec.x*cntrVec.x+cntrVec.y*cntrVec.y]; IF cntrVecMag = 0.0 THEN RETURN[FALSE]; -- can't be separated if identical centroids cntrVec.x _ cntrVec.x / cntrVecMag; cntrVec.y _ cntrVec.y / cntrVecMag; FOR j: NAT IN [0..patch1.nVtces) DO vtx: REF Vertex _ in1.shape.vertex[patch1.vtxPtr[j]]; prod: REAL _ cntrVec.x * (vtx.sx - centroid1.x) + cntrVec.y * (vtx.sy - centroid1.y); IF j = 0 OR prod > max1 THEN { max1 _ prod; ptr1 _ j; } ; ENDLOOP; FOR j: NAT IN [0..patch2.nVtces) DO vtx: REF Vertex _ in2.shape.vertex[patch2.vtxPtr[j]]; prod: REAL _ cntrVec.x * (vtx.sx - centroid1.x) + cntrVec.y * (vtx.sy - centroid1.y); IF j = 0 OR prod < min2 THEN { min2 _ prod; ptr2 _ j; } ; ENDLOOP; <> IF min2 >= max1 * (1.0 - precisionLimit) THEN RETURN[TRUE]; overlap _ max1 - min2; }; <> WHILE TRUE DO min1, min2, centroid1Dist, centroid2Dist, sgn: REAL; nPtr1, nPtr2: NAT; vtx1: REF Vertex _ in1.shape.vertex[patch1.vtxPtr[ptr1]]; vtx2: REF Vertex _ in2.shape.vertex[patch2.vtxPtr[ptr2]]; sepEdge: Triple _ [vtx2.sy - vtx1.sy, vtx1.sx - vtx2.sx, 0.0]; sepEdge _ G3dVector.Normalize[sepEdge]; sepEdge.z _ -(vtx2.sx * sepEdge.x + vtx2.sy * sepEdge.y); centroid1Dist _ sepEdge.x * centroid1.x + sepEdge.y * centroid1.y + sepEdge.z; centroid2Dist _ sepEdge.x * centroid2.x + sepEdge.y * centroid2.y + sepEdge.z; IF centroid1Dist * centroid2Dist > 0.0 THEN RETURN[FALSE]; -- both on same side sgn _ IF centroid1Dist < 0.0 THEN -1.0 ELSE 1.0; FOR j: NAT IN [0..patch1.nVtces) DO vtx: REF Vertex _ in1.shape.vertex[patch1.vtxPtr[j]]; dist: REAL _ sgn * (sepEdge.x * vtx.sx + sepEdge.y * vtx.sy + sepEdge.z); IF j = 0 OR dist < min1 THEN { min1 _ dist; IF min1 < 0.0 THEN nPtr1 _ j; }; ENDLOOP; sgn _ IF centroid2Dist < 0.0 THEN -1.0 ELSE 1.0; FOR j: NAT IN [0..patch2.nVtces) DO vtx: REF Vertex _ in2.shape.vertex[patch2.vtxPtr[j]]; dist: REAL _ sgn * (sepEdge.x * vtx.sx + sepEdge.y * vtx.sy + sepEdge.z); IF j = 0 OR dist < min2 THEN { min2 _ dist; IF min2 < 0.0 THEN nPtr2 _ j; }; ENDLOOP; IF min1 > -ScanConvert.justNoticeable AND min2 > -ScanConvert.justNoticeable THEN RETURN[TRUE] ELSE { nOverlap: REAL _ 0.0; IF min1 < 0.0 THEN { nOverlap _ nOverlap - min1; ptr1 _ nPtr1; }; IF min2 < 0.0 THEN { nOverlap _ nOverlap - min2; ptr2 _ nPtr2; }; IF nOverlap >= overlap THEN RETURN[FALSE] ELSE overlap _ nOverlap; }; ENDLOOP; RETURN[FALSE]; -- can't get here, but compiler doesn't know that }; PlaneSeparable: PROC[in1, in2: REF ShapePatch] RETURNS[Order] ~ { <> overlap: REAL; ptr1, ptr2, nxtPtr1, nxtPtr2: NAT; <> centroid1, centroid2: Triple _ [0.0, 0.0, 0.0]; patches1: REF PtrPatchSequence _ NARROW[in1.shape.surface]; patches2: REF PtrPatchSequence _ NARROW[in2.shape.surface]; patch1: REF PtrPatch _ patches1[in1.patch]; patch2: REF PtrPatch _ patches2[in2.patch]; FOR j: NAT IN [0..patch1.nVtces) DO vtx: REF Vertex _ in1.shape.vertex[patch1.vtxPtr[j]]; centroid1 _ G3dVector.Add[ centroid1, [vtx.ex, vtx.ey, vtx.ez] ]; ENDLOOP; FOR j: NAT IN [0..patch2.nVtces) DO vtx: REF Vertex _ in2.shape.vertex[patch2.vtxPtr[j]]; centroid2 _ G3dVector.Add[ centroid2, [vtx.ex, vtx.ey, vtx.ez] ]; ENDLOOP; centroid1 _ G3dVector.Div[ centroid1 , patch1.nVtces ]; centroid2 _ G3dVector.Div[ centroid2 , patch2.nVtces ]; <> { max1, next1: REAL _ Real.MinusInfinity; min2, next2: REAL _ Real.PlusInfinity; cntrVec: Triple _ G3dVector.Sub[ centroid2, centroid1 ]; -- from 1 to 2 cntrVecMag: REAL _ G3dVector.Length[ cntrVec ]; IF cntrVecMag = 0.0 THEN RETURN[intersects]; -- can't be separated if identical centroids cntrVec _ G3dVector.Div[ cntrVec, cntrVecMag ]; FOR j: NAT IN [0..patch1.nVtces) DO vtx: REF Vertex _ in1.shape.vertex[patch1.vtxPtr[j]]; prod: REAL _ G3dVector.Dot[ cntrVec, G3dVector.Sub[ [vtx.ex, vtx.ey, vtx.ez], centroid1 ] ]; IF j = 0 OR prod > max1 THEN { max1 _ prod; ptr1 _ j; next1 _ max1; nxtPtr1 _ ptr1; } -- new largest ELSE IF prod > next1 THEN { next1 _ prod; nxtPtr1 _ j; }; -- new 2nd largest ENDLOOP; FOR j: NAT IN [0..patch2.nVtces) DO vtx: REF Vertex _ in2.shape.vertex[patch2.vtxPtr[j]]; prod: REAL _ G3dVector.Dot[ cntrVec, G3dVector.Sub[ [vtx.ex, vtx.ey, vtx.ez], centroid1 ] ]; IF j = 0 OR prod < min2 THEN { min2 _ prod; ptr2 _ j; next2 _ min2; nxtPtr2 _ ptr2; } -- new min. ELSE IF prod < next2 THEN { next2 _ prod; nxtPtr2 _ j; }; -- new 2nd minimum ENDLOOP; <> IF min2 >= max1 * (1.0 - precisionLimit) THEN { max1Vec: Triple _ G3dVector.Add[ -- position of max1 projection on cntrVec centroid1, G3dVector.Mul[cntrVec, max1 / cntrVecMag] ]; IF G3dVector.Dot[max1Vec, cntrVec] > 0.0 THEN RETURN[inFront] -- cntrVec tilts away from the eye, in1 in front ELSE RETURN[behind]; -- cntrVec tilts toward the eye, in1 behind }; overlap _ max1 - min2; }; <> { vtx1: REF Vertex _ in1.shape.vertex[patch1.vtxPtr[ptr1]]; vtx2: REF Vertex _ in2.shape.vertex[patch2.vtxPtr[ptr2]]; FOR i: NAT IN [0..2) DO state1, state2: Order; adjPtr: NAT _ IF i = 0 THEN (ptr1 + 1) MOD patch1.nVtces ELSE (ptr1 + patch1.nVtces-1) MOD patch1.nVtces; vtx1a: REF Vertex _ in1.shape.vertex[patch1.vtxPtr[adjPtr]]; sepPlane: Quad _ G3dPlane.FromThreePoints[ [vtx1.ex, vtx1.ey, vtx1.ez], [vtx2.ex, vtx2.ey, vtx2.ez], [vtx1a.ex, vtx1a.ey, vtx1a.ez], TRUE -- normalize ! G3dPlane.Error => LOOP ]; sepPlane _ [sepPlane.x*100.0, sepPlane.y*100.0, sepPlane.z*100.0, sepPlane.w*100.0]; state1 _ CheckAgainstPlane[in1, sepPlane]; state2 _ CheckAgainstPlane[in2, sepPlane]; IF (state1 = behind AND state2 = inFront) OR (state1 = inFront AND state2 = behind) THEN RETURN[state1]; ENDLOOP; FOR i: NAT IN [0..2) DO -- failed to get good planes on first poly, try other one state1, state2: Order; adjPtr: NAT _ IF i = 0 THEN (ptr2 + 1) MOD patch2.nVtces ELSE (ptr2 + patch2.nVtces-2) MOD patch2.nVtces; vtx2a: REF Vertex _ in2.shape.vertex[patch2.vtxPtr[adjPtr]]; sepPlane: Quad _ G3dPlane.FromThreePoints[ [vtx1.ex, vtx1.ey, vtx1.ez], [vtx2.ex, vtx2.ey, vtx2.ez], [vtx2a.ex, vtx2a.ey, vtx2a.ez], TRUE -- normalize ! G3dPlane.Error => LOOP ]; sepPlane _ [sepPlane.x*100.0, sepPlane.y*100.0, sepPlane.z*100.0, sepPlane.w*100.0]; state1 _ CheckAgainstPlane[in1, sepPlane]; state2 _ CheckAgainstPlane[in2, sepPlane]; IF (state1 = behind AND state2 = inFront) OR (state1 = inFront AND state2 = behind) THEN RETURN[state1] ELSE IF i # 0 THEN RETURN[intersects]; ENDLOOP; }; RETURN[intersects]; -- come here on utter failure to get a reasonable answer }; ShowPrioritySeq: PROC[context: REF Context, sortOrder: REF SortSequence] ~ { <> j: NAT _ sortOrder[1].prev; context.class.loadBackground[context]; WHILE j > 0 DO ShowOnePatch[context, sortOrder[j].shape, sortOrder[j].patch]; j _ sortOrder[j].prev; ENDLOOP; }; LoadPrioritySequence: PUBLIC PROC[context: REF Context, sortOrder: LIST OF REF ANY _ NIL] RETURNS[LIST OF REF ANY, CARDINAL] ~ { <> <<(1) Active patches whose far limit is farther than current near limit>> <<(2) permanent list >> <> <<- if far limit closer than current near, delete from active list>> <<- if same shape go to next one>> <<- if screen limits don't overlap go to next one>> <<- compare planes for intersection, clip if not separable, insert if in front>> <<- if clipped >> <<- insert new patches into shape data structures to create new ShapePatch>> <<- put frontmost new patch into active and permanent lists, continue with both halves >> sortKey: REF NatSequence; -- 1st element of 'sortOrder', sort buckets with linked lists of buckets: REF SortSequence; -- 2nd element of 'sortOrder', sort buckets with linked lists of -- REF ShapePatch <> sorted: REF SortSequence; active: REF SortSequence; bounds: REF BoundsSequence; -- RECORD[left, right, bottom, top, near, far: REAL]; activeKey: REF NatSequence; -- keeps order on active and bounds numActive: NAT _ 0; emptySpace: INTEGER _ -1; -- hole in active - negative means NIL endOfActive: NAT _ 0; -- beginning of unused space in active endOfSort: NAT; -- beginning of unused space in sort patchCount: CARDINAL _ 0; ExtendBds: PROC[seq: REF BoundsSequence] RETURNS[newSeq: REF BoundsSequence] ~ { newSeq _ NEW[ BoundsSequence[seq.length + MAX[16, INTEGER[seq.length/8]]] ]; FOR i: NAT IN [0..seq.length) DO newSeq[i] _ seq[i]; ENDLOOP; }; ExtendNat: PROC[seq: REF NatSequence] RETURNS[newSeq: REF NatSequence] ~ { newSeq _ NEW[ NatSequence[seq.maxLength + MAX[16, INTEGER[seq.maxLength/8]]] ]; FOR i: NAT IN [0..seq.maxLength) DO newSeq[i] _ seq[i]; ENDLOOP; }; Extend: PROC[seq: REF SortSequence] RETURNS[newSeq: REF SortSequence] ~ { newSeq _ NEW[ SortSequence[seq.length + MAX[16, INTEGER[seq.length/8]]] ]; FOR i: NAT IN [0..seq.length) DO newSeq[i] _ seq[i]; ENDLOOP; }; DeleteActive: PROC[index: NAT] ~ { j: NAT _ activeKey[index]; active[j] _ NIL; -- nil entry bounds[j] _ [0.0, 0.0, 0.0, 0.0, 0.0, 0.0]; emptySpace _ j; FOR i: NAT IN [index..numActive-1) DO -- close up pointer array activeKey[i] _ activeKey[i+1]; ENDLOOP; activeKey[numActive-1] _ 0; numActive _ numActive - 1; }; InsertActive: PROC[index: NAT, pBnds: Bounds, patch: REF ShapePatch] ~ { place: NAT; IF emptySpace < 0 THEN { place _ endOfActive; endOfActive _ endOfActive+1; IF endOfActive >= active.length THEN { -- overflow, extend sequences active _ Extend[active]; bounds _ ExtendBds[bounds]; activeKey _ ExtendNat[activeKey]; }; } ELSE { place _ emptySpace; emptySpace _ -1; }; IF index = 0 THEN IF numActive = 0 -- first entry in active list ? THEN { patch.prev _ sorted[1].next; patch.next _ sorted[patch.prev].next; } ELSE patch.next _ sorted[active[activeKey[index]].prev].next -- heading active list ELSE patch.next _ active[activeKey[index-1]].next; -- not heading active list IF numActive > 0 THEN patch.prev _ sorted[patch.next].prev; -- back ptr. from next patch sorted[patch.prev].next _ endOfSort; -- fore pointer from current patch sorted[patch.next].prev _ endOfSort; -- back ptr to new patch IF endOfSort >= sorted.length THEN sorted _ Extend[sorted]; sorted[endOfSort] _ patch; -- put in sorted array endOfSort _ endOfSort + 1; -- increment store location FOR i: NAT DECREASING IN [index..numActive) DO -- open up pointer array activeKey[i+1] _ activeKey[i]; ENDLOOP; activeKey[index] _ place; -- insert pointer to Patch and bounds arrays active[place] _ patch; bounds[place] _ pBnds; numActive _ numActive + 1; }; Promote: PROC[from, to: NAT] RETURNS[NAT] ~ { <> fromPlace: NAT _ activeKey[from]; toPlace: NAT _ activeKey[to]; promoteeAddr: NAT; -- location of promotee in sorted sequence tBnds: Bounds _ bounds[fromPlace]; tActive: REF ShapePatch _ active[fromPlace]; FOR i: NAT DECREASING IN [to..from) DO -- move intermediate entries back one activeKey[i+1] _ activeKey[i]; ENDLOOP; activeKey[to] _ fromPlace; -- insert promoted entry <> promoteeAddr _ sorted[tActive.prev].next; -- get pointer to promotee sorted[tActive.prev].next _ tActive.next; -- redirect fore pointer from promoted patch sorted[tActive.next].prev _ tActive.prev; -- redirect back ptr from promoted patch <> tActive.prev _ active[toPlace].prev; -- link promotee into new position tActive.next _ sorted[tActive.prev].next; sorted[tActive.prev].next _ promoteeAddr; -- redirect fore pointer to promoted patch sorted[tActive.next].prev _ promoteeAddr; -- redirect back ptr to promoted patch <> RETURN[to+1]; -- next site to insert polygon }; Insert: PROC[inPatch: REF ShapePatch, start, level: NAT _ 0] RETURNS[NAT] ~ { <> newPatch: REF ShapePatch _ NEW[ShapePatch _ inPatch^]; -- insulate external patch ptrs rearParts: LIST OF REF ShapePatch _ NIL; shape: REF ShapeInstance _ newPatch.shape; away: REAL _ newPatch.awayness; selfIntersecting: BOOLEAN _ FALSE; -- shape property? patches: REF PtrPatchSequence _ NARROW[shape.surface]; patch: REF PtrPatch _ patches[newPatch.patch]; pBnds: Bounds _ GetBounds[patch, shape]; -- Get bounding box for patch i: NAT _ start; inserted: BOOLEAN _ FALSE; insertionPt: NAT; <> WHILE level = 0 AND i < numActive AND bounds[activeKey[i]].far <= pBnds.near DO DeleteActive[i]; i _ i+1; -- cull anything at beginning no depth overlap ENDLOOP; WHILE i < numActive DO newPlane: Quad; j: NAT _ activeKey[i]; i _ i+1; IF bounds[j].right <= pBnds.left THEN LOOP; -- bounds overlap on screen? IF bounds[j].left >= pBnds.right THEN LOOP; IF bounds[j].top <= pBnds.bottom THEN LOOP; IF bounds[j].bottom >= pBnds.top THEN LOOP; IF LineSeparable[active[j], newPatch] THEN LOOP; -- linearly separable on screen IF active[j].shape = shape -- overlapping, same shape THEN IF NOT selfIntersecting THEN IF NOT shape.insideVisible THEN LOOP -- no backfacing polygons ELSE IF ABS[active[j].awayness - newPatch.awayness] < 0.5 -- kluge!! THEN LOOP; -- from same poly < 0.5 * ABS[active[j].awayness + away] >> <> <> <> <> <<}>> <> <> <<{ InsertActive[i-1, pBnds, newPatch]; inserted _ TRUE; insertionPt _ i-1; }; >> <> <<}>> <> <> <> newPlane _ GetPlane[patch, shape]; -- try plane of new polygon as separator SELECT CheckAgainstPlane[active[j], newPlane] FROM inFront, coincident => { -- polygon in front of or coincident with new plane IF inserted THEN insertionPt _ Promote[from: i-1, to: insertionPt]; -- new order LOOP; }; -- else go to next polygon behind => { -- insert in front of polygon IF inserted THEN LOOP; InsertActive[i-1, pBnds, newPatch]; inserted _ TRUE; insertionPt _ i-1; LOOP; }; intersects => { -- vertices on both sides of plane, test other way shape: REF ShapeInstance _ active[j].shape; oldPatches: REF PtrPatchSequence _ NARROW[shape.surface]; oldPatch: REF PtrPatch _ oldPatches[active[j].patch]; oldPlane: Quad _ GetPlane[oldPatch, shape]; -- plane of polygon from active list SELECT CheckAgainstPlane[newPatch, oldPlane] FROM behind, coincident => { -- new poly behind or coincident with old plane IF inserted THEN insertionPt _ Promote[from: i-1, to: insertionPt]; LOOP; }; -- else go to next polygon inFront => { -- insert in front of polygon IF inserted THEN LOOP; InsertActive[i-1, pBnds, newPatch]; inserted _ TRUE; insertionPt _ i-1; LOOP; }; intersects => { -- not resolvable, check for separating plane SELECT PlaneSeparable[newPatch, active[j]] FROM behind => { -- new poly behind old poly IF inserted THEN insertionPt _ Promote[from: i-1, to: insertionPt]; LOOP; }; -- else go to next polygon inFront => { -- insert in front of polygon IF inserted THEN LOOP; InsertActive[i-1, pBnds, newPatch]; inserted _ TRUE; insertionPt _ i-1; LOOP; }; intersects => { -- not resolvable, split new polygon by plane of old rearPatch: REF ShapePatch; [newPatch, rearPatch] _ ClipPolyToPlane[context, newPatch, oldPlane]; rearParts _ CONS[rearPatch, rearParts]; patchCount _ patchCount + 1; -- a new polygon generated IF inserted -- replace whole patch with front part if inserted THEN active[activeKey[insertionPt]].patch _ newPatch.patch ELSE IF NOT LineSeparable[active[j], newPatch] THEN { InsertActive[i-1, pBnds, newPatch]; inserted _ TRUE; insertionPt _ i-1; i _ i+1; -- insert front part }; }; ENDCASE; }; ENDCASE; }; ENDCASE; ENDLOOP; IF NOT inserted THEN { InsertActive[i, pBnds, newPatch]; insertionPt _ i; }; IF NOT debug THEN WHILE rearParts # NIL DO -- continue recursively with rear parts insertionPt _ Insert[rearParts.first, MIN[numActive, insertionPt+2], level+1]; rearParts _ rearParts.rest; ENDLOOP; RETURN[insertionPt]; }; [sortOrder, patchCount] _ LoadDepthSequence[context, sortOrder]; -- sort by nearest vertex sortKey _ NARROW[sortOrder.first, REF NatSequence]; buckets _ NARROW[sortOrder.rest.first, REF SortSequence]; sorted _ NEW[SortSequence[2*patchCount+2]]; bounds _ NEW[BoundsSequence[2*patchCount]]; active _ NEW[SortSequence[2*patchCount]]; activeKey _ NEW[NatSequence[2*patchCount+1]]; sorted[0] _ NEW[ShapePatch _ [NIL, 0, 1, 0, 0.0]]; -- initialize list header sorted[1] _ NEW[ShapePatch _ [NIL, 0, 0, 0, 0.0]]; -- initialize dummy list tail endOfSort _ 2; FOR i: NAT IN [0..sortKey.length) DO -- compose initial sort into complete ordering j: NAT _ sortKey[i]; WHILE j # nullPtr DO [] _ Insert[buckets[j]]; -- insert next polygon in order in list j _ buckets[j].next; IF context.stopMe^ THEN RETURN[sortOrder, patchCount]; -- quit if stop signal received ENDLOOP; ENDLOOP; sortKey[0] _ sorted[0].next; -- start linked list at 1st element sortKey.length _ 1; sorted[sorted[1].prev].next _ 0; -- bind off linked list at last real element sorted[sortKey[0]].prev _ sorted[1].prev; -- set pointer to list tail at 1st element RETURN[ LIST[sortKey, sorted, NIL], patchCount ]; }; LoadDepthSequence: PUBLIC PROC[ context: REF Context, sortOrder: LIST OF REF ANY _ NIL ] RETURNS[LIST OF REF ANY, CARDINAL] ~ { <> sortKey: REF NatSequence; -- 1st element of 'sortOrder', sort buckets with linked lists of buckets: REF SortSequence; -- 2nd element of 'sortOrder', sort buckets with linked lists of -- REF ShapePatch shape: REF ShapeSequence _ context.visibleShapes; patchCount: CARDINAL _ 0; bucketListPtr: INT _ 1; -- start bucket count at 1 to allow use of zero as null minDepth: REAL _ context.yonLimit; maxDepth: REAL _ context.hitherLimit; zScale: REAL _ 1.; NewSortOrder: PROC[] ~ { buckets _ NEW[SortSequence[patchCount+1]]; sortKey _ NEW[NatSequence[context.depthResolution]]; sortKey.length _ context.depthResolution; }; FOR i: NAT IN [0.. shape.length) DO -- get minimum and maximum depth and patch count radius: REAL _ shape[i].boundingRadius; IF shape[i].centroid.ez - radius < minDepth THEN minDepth _ shape[i].centroid.ez - radius; IF shape[i].centroid.ez + radius > maxDepth THEN maxDepth _ shape[i].centroid.ez + radius; patchCount _ patchCount + shape[i].numSurfaces; shape[i].props _ PutProp[ -- set sizes for intersections in priority sdort shape[i].props, $ClippedPatches, NEW[INT32 _ shape[i].numSurfaces] ]; shape[i].props _ PutProp[ shape[i].props, $ClippedVertices, NEW[INT32 _ shape[i].vertex.length] ]; ENDLOOP; minDepth _ MAX[minDepth, 0]; -- nothing allowed behind the eyepoint IF (maxDepth - minDepth) > 0. THEN zScale _ (context.depthResolution - 1) / (maxDepth - minDepth); IF sortOrder # NIL THEN { sortKey _ NARROW[sortOrder.first]; buckets _ NARROW[sortOrder.rest.first]; } ELSE NewSortOrder[]; IF buckets.length < patchCount OR sortKey.length < context.depthResolution THEN NewSortOrder[]; -- get new storage if sizes have expanded FOR i: NAT IN [0..sortKey.length) DO sortKey[i] _ nullPtr; ENDLOOP; -- clear sort structure FOR s: NAT IN [0.. shape.length) DO -- Enter patches (by nearest z) in bucket lists patch: REF PtrPatchSequence _ NARROW[shape[s].surface]; FOR i: NAT IN [0..shape[s].numSurfaces) DO IF context.stopMe^ THEN RETURN[NIL, 0]; -- shut down if stop signal received IF patch[i] # NIL AND patch[i].clipState # out THEN { -- can't be proven not visible neg, pos: BOOLEAN _ FALSE; dirSum: REAL _ 0.0; zNear: REAL _ maxDepth; iz: INT; FOR j: NAT IN [0..patch[i].nVtces) DO -- get minimum z-coordinate zNear _ MIN[zNear, shape[s].vertex[patch[i].vtxPtr[j]].ez]; ENDLOOP; iz _ INTEGER[Real.Fix[zScale *(zNear - minDepth)]]; -- get matching bucket addr. IF iz < 0 THEN iz _ 0; -- clip at zero IF patch[i].type = $ConvexPolygon THEN -- normals valid only for polygons FOR k: NAT IN [0..patch[i].nVtces) DO j: NAT _ patch[i].vtxPtr[k]; dir: REAL _ G3dVector.Dot[ -- normal front or back facing? [shape[s].vertex[j].ex, shape[s].vertex[j].ey, shape[s].vertex[j].ez], [shape[s].shade[j].exn, shape[s].shade[j].eyn, shape[s].shade[j].ezn] ]; IF dir > 0.0 THEN pos _ TRUE ELSE IF dir < 0.0 THEN neg _ TRUE; dirSum _ dirSum + dir; -- sum normals to characterize orientation ENDLOOP; IF pos AND NOT neg THEN patch[i].dir _ back ELSE IF neg AND NOT pos THEN patch[i].dir _ front ELSE patch[i].dir _ undetermined; IF NOT (patch[i].oneSided AND patch[i].dir = back) THEN { -- will be displayed bckPtr, nxtPtr: INT _ nullPtr; nxtPtr _ sortKey[iz]; WHILE nxtPtr # nullPtr AND buckets[nxtPtr].awayness < dirSum DO bckPtr _ nxtPtr; -- find right place in ordered chain nxtPtr _ buckets[nxtPtr].next; ENDLOOP; <> buckets[bucketListPtr] _ NEW[ShapePatch]; buckets[bucketListPtr].shape _ shape[s]; buckets[bucketListPtr].patch _ i; buckets[bucketListPtr].next _ buckets[bucketListPtr].prev _ nullPtr; -- clear IF nxtPtr # nullPtr THEN { -- not at tail of list buckets[bucketListPtr].prev _ buckets[nxtPtr].prev; buckets[bucketListPtr].next _ nxtPtr; buckets[nxtPtr].prev _ bucketListPtr; }; IF bckPtr # nullPtr THEN { -- not at head of list buckets[bucketListPtr].next _ buckets[bckPtr].next; buckets[bucketListPtr].prev _ bckPtr; buckets[bckPtr].next _ bucketListPtr; }; IF bckPtr = nullPtr THEN { -- at head of list sortKey[iz] _ bucketListPtr; -- reset list header }; IF nxtPtr = nullPtr THEN -- at tail of list buckets[sortKey[iz]].prev _ bucketListPtr; -- reset tail ptr at head buckets[bucketListPtr].awayness _ dirSum; -- sum of dot prods of vertex nmls -- with eyept dir, quantitative measure of "backfacingness" bucketListPtr _ bucketListPtr + 1; }; }; ENDLOOP; ENDLOOP; sortKey.length _ context.depthResolution; RETURN[ LIST[sortKey, buckets], patchCount ]; }; <> GetDepths: PROC[ context: REF Context] ~ { <> shape: REF G3dRender.ShapeSequence _ context.visibleShapes; minDepth: REAL _ context.yonLimit; maxDepth: REAL _ context.hitherLimit; zScale: REAL _ 1.; FOR i: NAT IN [0.. shape.length) DO -- get minimum and maximum depth radius: REAL _ shape[i].boundingRadius; IF shape[i].class.type # $ConvexPolygon THEN radius _ 1.1 * radius; -- fudge for patches IF shape[i].centroid.ez - radius < minDepth THEN minDepth _ shape[i].centroid.ez - radius; IF shape[i].centroid.ez + radius > maxDepth THEN maxDepth _ shape[i].centroid.ez + radius; ENDLOOP; minDepth _ MAX[minDepth, context.hitherLimit]; -- nothing allowed behind the eyepoint IF (maxDepth - minDepth) > 0. THEN zScale _ (context.depthResolution - 1) / (maxDepth - minDepth); context.eyeToNdc.addZ _ 1./(1. - minDepth/maxDepth); --smash hither-yon factors context.eyeToNdc.scaleZ _ -minDepth/(1. - minDepth/maxDepth); FOR s: NAT IN [0.. shape.length) DO ShapeUtilities.XfmToDisplay[context, shape[s] ]; ENDLOOP; }; DoBackToFront: PUBLIC PROC[ context: REF Context, sortInfo: LIST OF REF ANY, action: PROC[REF ShapePatch] ] ~ { sortKey: REF NatSequence _ NARROW[sortInfo.first]; buckets: REF SortSequence _ NARROW[sortInfo.rest.first]; FOR i: NAT DECREASING IN [0..sortKey.length) DO j: NAT _ sortKey[i]; WHILE j # nullPtr DO j _ buckets[j].prev; -- jump to tail of list and work back action[buckets[j]]; -- call back with next polygon in order IF j = sortKey[i] THEN j _ nullPtr; -- exit if head of list reached IF context.stopMe^ THEN RETURN[]; -- shut down if stop signal received ENDLOOP; ENDLOOP; CombineBoxes[context]; -- get combined bounding box on scene }; DoFrontToBack: PUBLIC PROC[ context: REF Context, sortInfo: LIST OF REF ANY, action: PROC[REF ShapePatch] ] ~ { sortKey: REF NatSequence _ NARROW[sortInfo.first]; buckets: REF SortSequence _ NARROW[sortInfo.rest.first]; FOR i: NAT IN [0..sortKey.length) DO j: NAT _ sortKey[i]; WHILE j # nullPtr DO action[buckets[j]]; -- call back with next polygon in order j _ buckets[j].next; IF context.stopMe^ THEN RETURN[]; -- shut down if stop signal received ENDLOOP; ENDLOOP; CombineBoxes[context]; -- get combined bounding box on scene }; <<>> DoForPatches: PUBLIC PROC[ context: REF Context, set: REF G3dRender.ShapeSequence, patchAction: PROC[REF ShapePatch], shapeAction: PROC[REF ShapeInstance] _ NIL ] ~ { FOR s: NAT IN [0..set.length) DO IF set[s].clipState = in AND shapeAction # NIL THEN shapeAction[set[s]] ELSE { patch: REF PtrPatchSequence _ NARROW[set[s].surface]; FOR i: NAT IN [0..set[s].numSurfaces) DO IF patch[i] # NIL THEN { IF context.stopMe^ THEN RETURN[]; -- shut down if stop signal received IF set[s].clipState = in THEN patch[i].clipState _ in -- unclipped, inside ELSE IF set[s].clipState = clipped THEN GetPtrPatchClipState[ set[s], patch[i] ] ELSE patch[i].clipState _ out; IF patch[i].clipState # out THEN patchAction[NEW[ ShapePatch _ [set[s], i, 0, 0, 0.0] ]]; }; ENDLOOP; }; ENDLOOP; }; CombineBoxes: PUBLIC PROC[context: REF Context] ~ { -- get combined bounding box context.extentCovered _ [ [LAST[NAT], LAST[NAT]], [FIRST[NAT], FIRST[NAT]] ]; FOR i: NAT IN [0..context.visibleShapes.length) DO IF context.extentCovered.min.f > context.visibleShapes[i].screenExtent.min.f THEN context.extentCovered.min.f _ context.visibleShapes[i].screenExtent.min.f; IF context.extentCovered.max.f < context.visibleShapes[i].screenExtent.max.f THEN context.extentCovered.max.f _ context.visibleShapes[i].screenExtent.max.f; IF context.extentCovered.min.s > context.visibleShapes[i].screenExtent.min.s THEN context.extentCovered.min.s _ context.visibleShapes[i].screenExtent.min.s; IF context.extentCovered.max.s < context.visibleShapes[i].screenExtent.max.s THEN context.extentCovered.max.s _ context.visibleShapes[i].screenExtent.max.s; ENDLOOP; }; ShowOnePatch: PROC[ context: REF Context, shape: REF ShapeInstance, i: NAT] ~ { patch: REF PtrPatchSequence _ NARROW[shape.surface]; IF shape.clipState = in THEN patch[i].clipState _ in -- unclipped, inside ELSE IF shape.clipState = clipped THEN GetPtrPatchClipState[ shape, patch[i] ] ELSE patch[i].clipState _ out; IF patch[i].clipState # out THEN { patch: REF Patch _ ShapeUtilities.ShapePatchToPatch[ context, NEW[ ShapePatch _ [shape, i, 0, 0, 0.0] ] ]; [] _ shape.class.displayPatch[ context, patch ]; }; }; ShowOneVtx: PROC[ context: REF Context, shape: REF ShapeInstance, j: NAT] ~ { patch: REF PtrPatchSequence _ NARROW[shape.surface]; FOR i: NAT IN [0..patch.length) DO containsVtx: BOOLEAN _ FALSE; FOR k: NAT IN [0..patch[i].nVtces) DO IF patch[i].vtxPtr[k] = j THEN { containsVtx _ TRUE; EXIT; }; ENDLOOP; IF containsVtx THEN { IF shape.clipState = in THEN patch[i].clipState _ in -- unclipped, inside ELSE IF shape.clipState = clipped THEN GetPtrPatchClipState[ shape, patch[i] ] ELSE patch[i].clipState _ out; IF patch[i].clipState # out THEN { patch: REF Patch _ ShapeUtilities.ShapePatchToPatch[ context, NEW[ ShapePatch _ [shape, i, 0, 0, 0.0] ] ]; [] _ shape.class.displayPatch[ context, patch ]; }; }; ENDLOOP; }; ShowObjects: PUBLIC PROC[ context: REF Context, frontToBack: BOOLEAN _ FALSE ] ~ { ShowPatch: PROC[p: REF ShapePatch] ~{ patch: REF Patch _ ShapeUtilities.ShapePatchToPatch[ context, p ]; [] _ p.shape.class.displayPatch[ context, patch ]; patchCount _ patchCount + 1; IF log # NIL AND context.antiAliasing AND progressReportsPerFrame > 0 AND patchCount >= nextReport THEN { log.PutRope[ Rope.Cat[ Rope.Cat[ "\n ", Convert.RopeFromInt[patchCount], " of " ], Rope.Cat[ Convert.RopeFromInt[patchTotal], " done in ", ElapsedTime[time] ] ] ]; nextReport _ MIN[patchCount + patchTotal/progressReportsPerFrame, patchTotal-1]; }; }; patchCount, patchTotal, nextReport: INT _ 0; time: REAL _ CurrentTime[]; log: IO.STREAM _ NARROW[ Atom.GetPropFromList[context.props, $Log] ]; timing: Rope.ROPE; justOne: REF IntegerPair _ NARROW[ Atom.GetPropFromList[context.props, $SinglePatch] ]; oneVtx: REF IntegerPair _ NARROW[ Atom.GetPropFromList[context.props, $SingleVtx] ]; shape: REF G3dRender.ShapeSequence _ context.visibleShapes; IF shape = NIL THEN RETURN[]; IF context.depthBuffering THEN GetDepths[context]; IF justOne # NIL THEN { ShowOnePatch[context, shape[justOne.x], justOne.y]; RETURN[]; }; IF oneVtx # NIL THEN { ShowOneVtx[context, shape[oneVtx.x], oneVtx.y]; RETURN[]; }; IF context.depthBuffering AND NOT context.antiAliasing THEN DoForPatches[context, shape, ShowPatch] ELSE { IF GetProp[context.props, $SortToPriority] # NIL THEN [context.sortSequence, patchTotal] _ LoadPrioritySequence[context, NARROW[context.sortSequence] ] ELSE [context.sortSequence, patchTotal] _ LoadDepthSequence[context, NARROW[context.sortSequence] ]; timing _ Rope.Cat[ timing, " Sort: ", ElapsedTime[time] ]; time _ CurrentTime[]; IF context.delayClear THEN context.class.loadBackground[context]; -- load background IF context.stopMe^ THEN RETURN[]; -- shut down if stop signal received IF frontToBack THEN DoFrontToBack[context, NARROW[context.sortSequence], ShowPatch] ELSE DoBackToFront[context, NARROW[context.sortSequence], ShowPatch]; }; IF log # NIL THEN log.PutRope[ Rope.Cat[ timing, " Scan: ", ElapsedTime[time] ] ]; }; ShowWireFrameObjects: PUBLIC PROC[context: REF Context ] ~ { ShowPatch: PROC[p: REF ShapePatch] ~{ patch: REF Patch _ ShapeUtilities.ShapePatchToPatch[ context, p ]; [] _ p.shape.class.displayPatch[ context, patch ]; }; ShowShape: PROC[s: REF ShapeInstance] ~{ IF s.class.display # NIL THEN SELECT context.class.displayType FROM $PseudoColor, $Gray, $FullColor => [] _ s.class.display[ context, s ]; ENDCASE => OutputShape[context, s] ELSE OutputShape[context, s]; }; shape: REF G3dRender.ShapeSequence _ context.visibleShapes; justOne: REF IntegerPair _ NARROW[ Atom.GetPropFromList[context.props, $SinglePatch] ]; oneVtx: REF IntegerPair _ NARROW[ Atom.GetPropFromList[context.props, $SingleVtx] ]; IF shape = NIL THEN RETURN[]; IF context.delayClear THEN context.class.loadBackground[context]; -- load background IF justOne # NIL THEN { ShowOnePatch[context, shape[justOne.x], justOne.y]; RETURN[]; }; IF oneVtx # NIL THEN { ShowOneVtx[context, shape[oneVtx.x], oneVtx.y]; RETURN[]; }; DoForPatches[context, shape, ShowPatch, ShowShape]; CombineBoxes[context]; -- get combined bounding box on scene }; OutputShape: PROC[context: REF Context, shape: REF ShapeInstance] ~ { <> patch: REF PtrPatchSequence; IF shape.surface = NIL THEN RETURN; IF context.stopMe^ THEN RETURN[]; -- shut down if stop signal received patch _ NARROW[shape.surface]; FOR i: NAT IN [0..shape.numSurfaces) DO IF patch[i] # NIL THEN { p: REF Patch _ ShapeUtilities.ShapePatchToPatch[ context, NEW[ShapePatch _ [shape, i, 0, 0, 0.0]] ]; [] _ shape.class.displayPatch[ context, p ]; }; ENDLOOP; }; dummyShape: REF ShapeInstance _ NEW[ShapeInstance]; EdgesToPolygons: PatchProc ~ { <> <> MakeEdge: PROC[pt1, pt2: VertexInfo, edge: REF Patch] ~ { dirX, dirY, mag, offSetX1, offSetY1, offSetX2, offSetY2: REAL; dirX _ pt2.coord.ex - pt1.coord.ex; -- get unit vector in edge direction dirY _ pt2.coord.ey - pt1.coord.ey; mag _ RealFns.SqRt[ Sqr[dirX] + Sqr[dirY] ]; IF mag < ScanConvert.justNoticeable THEN RETURN[]; -- quit if too short to be seen dirX _ dirX / mag; dirY _ dirY / mag; offSetX1 _ dirX * baseRadius; offSetY1 _ dirY * baseRadius; offSetX2 _ dirX * baseRadius; offSetY2 _ dirY * baseRadius; FOR i: NAT IN [0..3) DO edge[i] _ pt1; ENDLOOP; FOR i: NAT IN [3..6) DO edge[i] _ pt2; ENDLOOP; edge[0].coord.ex _ edge[0].coord.ex+offSetY1; edge[0].coord.ey _ edge[0].coord.ey-offSetX1; edge[1].coord.ex _ edge[1].coord.ex-offSetX1; edge[1].coord.ey _ edge[1].coord.ey-offSetY1; edge[2].coord.ex _ edge[2].coord.ex-offSetY1; edge[2].coord.ey _ edge[2].coord.ey+offSetX1; edge[3].coord.ex _ edge[3].coord.ex-offSetY2; edge[3].coord.ey _ edge[3].coord.ey+offSetX2; edge[4].coord.ex _ edge[4].coord.ex+offSetX2; edge[4].coord.ey _ edge[4].coord.ey+offSetY2; edge[5].coord.ex _ edge[5].coord.ex+offSetY2; edge[5].coord.ey _ edge[5].coord.ey-offSetX2; IF patch.dir = back THEN FOR i: NAT IN [0..3) DO -- reverse order to make backfacing temp: VertexInfo _ edge[i]; edge[i] _ edge[5-i]; edge[5-i] _ temp; ENDLOOP; IF edge.clipState = in THEN FOR i: NAT IN [0..6) DO OPEN edge[i].coord; [[sx, sy, sz]] _ ShapeUtilities.XfmPtToDisplay[ context, [ex, ey, ez] ]; ENDLOOP; [] _ OutputPolygon[context, edge]; }; shape: REF ShapeInstance _ NARROW[ Atom.GetPropFromList[patch.props, $Shape] ]; baseRadius: REAL _ .003; limit: NAT _ IF patch.type = $PolyLine THEN patch.nVtces - 1 ELSE patch.nVtces; IF dummyShape.shadingClass = NIL THEN { G3dRender.LoadShadingClass[dummyShape]; dummyShape.shadingClass.shadingType _ $Smooth; }; dummyShape.shadingClass.color _ shape.shadingClass.color; { IF patch.dir = undetermined THEN patch.dir _ ShapeUtilities.BackFacing[ context, patch ! G3dRender.Error => IF reason.code = $Condition THEN GO TO GiveUp ]; IF patch.dir = front OR NOT patch.oneSided THEN FOR i: NAT IN [0..limit) DO edge: REF Patch _ ShapeUtilities.GetPatch[6]; -- will be released by OutputPolygon edge.type _ $ConvexPolygon; edge.nVtces _ 6; edge.oneSided _ patch.oneSided; edge.dir _ patch.dir; edge.clipState _ patch.clipState; edge.props _ Atom.PutPropOnList[ NIL, $Shape, dummyShape ]; MakeEdge[ patch[i], patch[(i+1) MOD patch.nVtces], edge ]; ENDLOOP; EXITS GiveUp => NULL }; ShapeUtilities.ReleasePatch[patch]; -- end of the line for this patch RETURN[NIL]; }; OutputPolygon: PUBLIC PatchProc ~ { <> shape: REF ShapeInstance _ NARROW[ Atom.GetPropFromList[patch.props, $Shape] ]; { IF patch = NIL OR patch.clipState = out THEN GO TO CleanUp; -- reject if outside frame IF patch.type # $ConvexPolygon AND patch.type # $PolyLine THEN { SIGNAL G3dRender.Error[[$MisMatch, "Not a Polygon or PolyLine"]]; GO TO CleanUp; -- catches unexpanded patches, etc. }; IF context.antiAliasing AND ( patch.type = $PolyLine OR shape.shadingClass.shadingType = $Lines OR shape.shadingClass.shadingType = $ShadedLines ) -- antialiased lines THEN { patch _ EdgesToPolygons[context, patch]; GO TO CleanUp; }; IF patch.clipState = clipped THEN { patch _ ShapeUtilities.ClipPoly[context, patch]; IF patch.nVtces > 2 OR ( patch.type = $PolyLine AND patch.nVtces > 1 ) THEN { FOR i: NAT IN [0..patch.nVtces) DO OPEN patch[i].coord; [[sx, sy, sz]] _ ShapeUtilities.XfmPtToDisplay[context, [ex, ey, ez]]; ENDLOOP; }; }; IF patch.nVtces > 2 OR ( patch.type = $PolyLine AND patch.nVtces > 1 ) THEN { IF patch.type = $PolyLine OR shape.shadingClass.shadingType = $Lines THEN { patch _ context.class.displayPolygon[context, patch]; GO TO GiveUp; }; IF patch.dir = undetermined THEN patch.dir _ ShapeUtilities.BackFacing[ context, patch ! G3dRender.Error => IF reason.code = $Condition THEN GO TO GiveUp ]; IF patch.dir = front THEN patch _ context.class.displayPolygon[context, patch] ELSE IF patch.oneSided -- backfacing!! THEN GO TO GiveUp -- Reject if closed surface ELSE { IF shape.shadingClass.shadingType # $HiddenLines AND shape.shadingClass.shadingType # $NormaledLines THEN FOR i: NAT IN [0..patch.nVtces) DO -- recalculate shading for back side patch[i].shade.exn _ -patch[i].shade.exn; -- reverse normals patch[i].shade.eyn _ -patch[i].shade.eyn; patch[i].shade.ezn _ -patch[i].shade.ezn; patch[i] _ shape.shadingClass.shadeVtx[context, patch[i], shape.shadingClass]; ENDLOOP; FOR i: NAT IN [0..patch.nVtces/2) DO -- reorder to keep clockwise on display tempVtx: VertexInfo _ patch[i]; patch[i] _ patch[patch.nVtces-1 - i]; patch[patch.nVtces-1 - i] _ tempVtx; ENDLOOP; patch _ context.class.displayPolygon[context, patch] }; EXITS GiveUp => NULL }; EXITS CleanUp => NULL; }; IF patch # NIL THEN ShapeUtilities.ReleasePatch[patch]; RETURN[NIL]; -- end of the line, nobody wants this polygon back certainly }; RopeDisplay: PUBLIC PatchProc ~ { shape: REF ShapeInstance _ NARROW[ Atom.GetPropFromList[patch.props, $Shape] ]; msg: Rope.ROPE _ NARROW[ Atom.GetPropFromList[shape.fixedProps, $RopeMessage ] ]; font: Rope.ROPE _ NARROW[ Atom.GetPropFromList[shape.fixedProps, $RopeFont ] ]; xfm: Xfm3D _ G3dMatrix.Mul[shape.position, context.eyeSpaceXfm]; color: Pixel _ [ Real.Fix[shape.shadingClass.color.R*255.0], Real.Fix[shape.shadingClass.color.G*255.0], Real.Fix[shape.shadingClass.color.B*255.0], 0, 0 ]; position: Triple _ [shape.vertex[0].sx, shape.vertex[0].sy, shape.vertex[0].sz]; position2: Triple _ [shape.vertex[1].sx, shape.vertex[1].sy, shape.vertex[1].sz]; size: REAL _ G3dVector.Length[ G3dVector.Sub[position2, position] ]; IF context.antiAliasing -- ensure entire rope represented THEN shape.screenExtent.max.f _ Real.Round[context.viewPort.w]; context.class.draw2DRope[ context, msg, [ position.x/context.ndcToPixels.scaleX, 1.0 - position.y/ABS[context.ndcToPixels.scaleY] ], color, size, font ]; RETURN[NIL]; }; <> MakeFrame: PUBLIC ContextProc ~ { MakeTheFrame[context]; }; ShowShapes: PUBLIC ContextProc ~ { <> delay: BOOLEAN _ context.delayClear; context.delayClear _ FALSE; -- avoids frame clear before making new frame MakeTheFrame[context: context, clear: FALSE]; context.delayClear _ delay; }; MakeTheFrame: PROC[context: REF Context, clear: BOOLEAN _ TRUE] ~ { <> Action: PROC ~ { allLines: BOOLEAN _ TRUE; time: REAL _ CurrentTime[]; log: IO.STREAM _ NARROW[ Atom.GetPropFromList[context.props, $Log] ]; context.stopMe^ _ FALSE; -- get stop flag unstuck, if necessary context.imageReady _ FALSE; -- discourage use of bits by other processes context.extentCovered _ [[0,0], [0,0]]; -- clear bounding box of coverage ValidateContext[context]; -- update everything FOR i: NAT IN [0..context.shapes.length) DO IF context.shapes[i].class.doBeforeFrame # NIL THEN -- execute animation updates FOR doList: LIST OF ShapeProc _ context.shapes[i].class.doBeforeFrame, doList.rest UNTIL doList = NIL DO context.shapes[i] _ doList.first[context, context.shapes[i]]; ENDLOOP; ENDLOOP; IF log # NIL THEN log.PutRope[ Rope.Cat[ " VtxOps: ", ElapsedTime[time] ] ]; IF clear AND NOT context.delayClear THEN context.class.loadBackground[context]; -- load background IF context.visibleShapes # NIL AND context.visibleShapes.length > 0 THEN { FOR i: NAT IN [0 .. context.visibleShapes.length) DO -- all line drawing? IF context.visibleShapes[i].shadingClass.shadingType # $Lines THEN allLines _ FALSE; ENDLOOP; IF allLines AND NOT context.antiAliasing THEN ShowWireFrameObjects[ context ] ELSE ShowObjects[ context: context, frontToBack: context.antiAliasing ]; context.imageReady _ TRUE; -- encourage use of bits by other processes IF log # NIL THEN { log.PutRope[ Rope.Cat[ " Frame: ", ElapsedTime[time], "\n"] ]; FlushLog[context]; }; } ELSE { IF log # NIL THEN { log.PutRope[" No visible objects in frame " ]; FlushLog[context]; }; }; }; CedarProcess.DoWithPriority[background, Action]; }; END.