<> <> <> <> <> DIRECTORY CoordSys, SVRay, Convert, DisplayListToTree, Imager, IO, PriorityQueue, Rope, SV3d, SVModelTypes, SVRayTypes, SVSceneTypes; DisplayListToTreeImpl: CEDAR PROGRAM IMPORTS Convert, CoordSys, SVRay, Imager, IO, PriorityQueue, Rope EXPORTS DisplayListToTree = BEGIN Slice: TYPE = SVSceneTypes.Slice; SliceList: TYPE = SVSceneTypes.SliceList; Camera: TYPE = SVModelTypes.Camera; Composite: TYPE = REF CompositeObj; CompositeObj: TYPE = SVRayTypes.CompositeObj; CoordSystem: TYPE = SVModelTypes.CoordSystem; CoordSysList: TYPE = SVModelTypes.CoordSysList; CSGTree: TYPE = SVRayTypes.CSGTree; MasterObject: TYPE = SVSceneTypes.MasterObject; Matrix4by4: TYPE = SV3d.Matrix4by4; PointSetOp: TYPE = SVRayTypes.PointSetOp; -- {union, intersection, difference} Primitive: TYPE = REF PrimitiveObj; PrimitiveObj: TYPE = SVRayTypes.PrimitiveObj; Scene: TYPE = SVSceneTypes.Scene; Shape: TYPE = SVSceneTypes.Shape; Surface: TYPE = REF ANY; -- may be RectSurface, TubeSurface, DiskSurface, or ShellSurface (of BasicObject3d), etc. SurfaceArray: TYPE = SVRayTypes.SurfaceArray; CreateEmptyTree: PUBLIC PROC [] RETURNS [tree: CSGTree] = { tree _ SVRay.MakeCSGTree[NIL, Imager.white, FALSE]; }; AssemblyToTree: PUBLIC PROC [assembly: Slice, scene: Scene, camera: Camera, oldTree: CSGTree _ NIL, ignoreMoving: BOOL _ FALSE] RETURNS [tree: CSGTree] = { <> topAssembly: Slice; topNode: REF ANY; topAssembly _ assembly; topNode _ AssemblyToNode[topAssembly, FALSE]; -- Make the tree. IF oldTree # NIL THEN { oldTree.son _ topNode; tree _ oldTree; } ELSE tree _ SVRay.MakeCSGTree[topNode, scene.backgroundColor, scene.shadows]; <> }; AssemblyToNode: PROC [assembly: Slice, inverted: BOOL] RETURNS [node: REF ANY] = { <> IF assembly = NIL THEN RETURN[ NIL ]; WITH assembly.shape SELECT FROM shape: Shape => { newPrim: Primitive; newPrim _ PrimitiveFromAssembly[assembly, inverted]; node _ newPrim; RETURN}; alist: SliceList => { node _ AssemblyListToNode[alist, assembly.name]; RETURN}; ENDCASE => ERROR; }; -- end of AssemblyToNode AssemblyListToNode: PROC [assemblyList: SliceList, name: Rope.ROPE] RETURNS [node: REF ANY] = { list: LIST OF Slice _ assemblyList.list; treeList: LIST OF REF ANY; <> treeList _ AssemblyListToTreeList[list, assemblyList.pointSetOp]; <> <> IF treeList = NIL THEN RETURN[ NIL ]; <> IF treeList.rest = NIL THEN { node _ treeList.first; RETURN} ELSE { -- Inspect the treeList more carefully. <> IF AllAreNil[treeList] THEN RETURN[NIL]; <> IF assemblyList.pointSetOp = intersection AND AnyAreNIL[treeList] THEN RETURN[ NIL ]; <> IF treeList.first = NIL AND assemblyList.pointSetOp = difference THEN RETURN[ NIL ]; <> treeList _ SpliceOutNILs[treeList]; <> IF treeList = NIL THEN RETURN[NIL]; IF treeList.rest = NIL THEN { node _ treeList.first; RETURN} ELSE { <> SELECT assemblyList.pointSetOp FROM union => node _ MakeUnionNode[treeList, name, 1]; intersection => node _ MakeIntersectionNode[treeList, name, 1]; difference => node _ MakeDifferenceNode[treeList, name, 1]; ENDCASE => ERROR; }; -- end ELSE }; -- end of ELSE }; -- end of AssemblyListToNode MakeUnionNode: PROC [treeList: LIST OF REF ANY, name: Rope.ROPE, level: NAT] RETURNS [node: REF ANY] = { <> leftNode, rightNode: REF ANY; intermediateName: Rope.ROPE; IF treeList = NIL THEN RETURN[ NIL]; IF treeList.rest = NIL THEN RETURN [treeList.first]; leftNode _ treeList.first; rightNode _ MakeUnionNode[treeList.rest, name, level + 1]; intermediateName _ Rope.Concat [name, Convert.RopeFromInt[level]]; node _ NEW[CompositeObj _ [intermediateName, union, leftNode, rightNode]]; }; -- end of MakeUnionNode MakeIntersectionNode: PROC [treeList: LIST OF REF ANY, name: Rope.ROPE, level: NAT] RETURNS [node: REF ANY] = { <> leftNode, rightNode: REF ANY; intermediateName: Rope.ROPE; IF treeList = NIL THEN RETURN[ NIL]; IF treeList.rest = NIL THEN RETURN [treeList.first]; leftNode _ treeList.first; rightNode _ MakeIntersectionNode[treeList.rest, name, level + 1]; intermediateName _ Rope.Concat [name, Convert.RopeFromInt[level]]; node _ NEW[CompositeObj _ [intermediateName, intersection, leftNode, rightNode]]; }; -- end of MakeIntersectionNode MakeDifferenceNode: PROC [treeList: LIST OF REF ANY, name: Rope.ROPE, level: NAT] RETURNS [node: REF ANY] = { <> leftNode, rightNode: REF ANY; intermediateName: Rope.ROPE; leftNode _ treeList.first; rightNode _ MakeUnionNode[treeList.rest, name, level + 1]; intermediateName _ Rope.Concat [name, Convert.RopeFromInt[level]]; node _ NEW[CompositeObj _ [intermediateName, difference, leftNode, rightNode]]; }; -- end of MakeDifferenceNode AssemblyListToTreeList: PROC [list: LIST OF Slice, op: PointSetOp] RETURNS [treeList: LIST OF REF ANY] = { <> IF list = NIL THEN RETURN[ NIL ]; <> IF op = difference THEN treeList _ CONS[AssemblyToNode[assembly: list.first, inverted: FALSE], AssemblyListToTreeList2[list: list.rest, inverted: TRUE]] ELSE treeList _ CONS[AssemblyToNode[assembly: list.first, inverted: FALSE], AssemblyListToTreeList2[list: list.rest, inverted: FALSE]]; }; -- end of AssemblyListToTreeList AssemblyListToTreeList2: PROC [list: LIST OF Slice, inverted: BOOL] RETURNS [treeList: LIST OF REF ANY] = { <> IF list = NIL THEN RETURN[ NIL ]; <> treeList _ CONS[AssemblyToNode[list.first, inverted], AssemblyListToTreeList2[list.rest, inverted]]; }; -- end of AssemblyListToTreeList2 AllAreNil: PRIVATE PROC [list: LIST OF REF ANY] RETURNS [BOOL] = { FOR l: LIST OF REF ANY _ list, l.rest UNTIL l = NIL DO IF l.first # NIL THEN RETURN[FALSE]; ENDLOOP; RETURN[TRUE]; }; AnyAreNIL: PRIVATE PROC [list: LIST OF REF ANY] RETURNS [BOOL] = { FOR l: LIST OF REF ANY _ list, l.rest UNTIL l = NIL DO IF l.first = NIL THEN RETURN[TRUE]; ENDLOOP; RETURN[FALSE]; }; SpliceOutNILs: PRIVATE PROC [list: LIST OF REF ANY] RETURNS [compressed: LIST OF REF ANY] = { IF list = NIL THEN RETURN[ NIL]; IF list.first # NIL THEN compressed _ CONS[list.first, SpliceOutNILs[list.rest]] ELSE compressed _ SpliceOutNILs[list.rest]; }; <<-- ---- ---- ---->> <<-- ---- ---- ---->> PrimitiveFromAssembly: PUBLIC PROC [assem: Slice, inverted: BOOL] RETURNS [prim: Primitive] = { mo: MasterObject; shape: Shape; prim _ NEW[PrimitiveObj]; IF NOT ISTYPE[assem.shape, Shape] THEN ERROR PrimitiveAssemblyWithoutMO; shape _ NARROW[assem.shape]; mo _ shape.mo; prim.name _ assem.name; prim.artwork _ assem.artwork; prim.assembly _ assem; prim.mo _ mo; prim.rayCast _ mo.class.rayCast; prim.rayCastNoBBoxes _ mo.class.rayCastNoBBoxes; prim.rayCastBoundingSpheres _ mo.class.rayCastBoundingSpheres; prim.localCS _ shape.coordSys; prim.scalars _ CoordSys.GetScalars[shape.coordSys]; prim.primWRTWorld _ CoordSys.WRTWorld[shape.coordSys]; prim.worldWRTPrim _ CoordSys.FindWorldInTermsOf[shape.coordSys]; <> prim.boundBox _ NIL; -- will be filled in at tree preprocess time prim.boundHedron _ mo.class.getHedron[mo]; prim.inverted _ inverted; prim.currentRay _ NIL; prim.rayStepX _ NIL; }; PrimitiveAssemblyWithoutMO: PUBLIC ERROR = CODE; CoordSysListFromScene: PUBLIC PROC [scene: Scene] RETURNS [csl: CoordSysList] = { <> csl _ CoordSysListFromAssembly[scene.assembly]; csl _ SortCoordSysListByBreadth[csl]; csl _ CONS[scene.coordSysRoot, csl]; -- add WORLD }; <<>> CoordSysListFromAssembly: PROC [assem: Slice] RETURNS [csl: CoordSysList] = { end: CoordSysList; alist, apos, aend: LIST OF Slice; root: CoordSystem _ assem.coordSys; i: NAT _ 0; end _ csl _ CONS[root, NIL]; aend _ alist _ CONS[assem, NIL]; FOR apos _ alist, apos.rest UNTIL apos = NIL DO WITH apos.first.shape SELECT FROM assemList: SliceList => { FOR children: LIST OF Slice _ assemList.list, children.rest UNTIL children = NIL DO end.rest _ CONS[children.first.coordSys, NIL]; aend.rest _ CONS[children.first, NIL]; end _ end.rest; aend _ aend.rest; i _ i+1; IF i > 300 THEN ERROR; ENDLOOP; }; ENDCASE => {}; -- we have no children and are already on the list. ENDLOOP; }; <> <<1) Put into the list only those coordinate systems belonging to assemblies, but>> <<2) Sort the list by depth order of the coordinate systems.>> <> <<>> SortCoordSysListByBreadth: PRIVATE PROC [csl: CoordSysList] RETURNS [sortedCsl: CoordSysList] = { <> q: PriorityQueue.Ref; thisRec, lastRec: CoordSysSortRec; len: NAT _ ListLength[csl]; q _ PriorityQueue.Predict[len, SortProc]; FOR list: CoordSysList _ csl, list.rest UNTIL list = NIL DO thisRec _ NEW[CoordSysSortRecObj _ [Depth[list.first], list]]; PriorityQueue.Insert[q, thisRec]; ENDLOOP; <> lastRec _ NARROW[PriorityQueue.Remove[q]]; lastRec.coordSysCell.rest _ NIL; FOR i: NAT IN [1..len-1] DO thisRec _ NARROW[PriorityQueue.Remove[q]]; thisRec.coordSysCell.rest _ lastRec.coordSysCell; lastRec _ thisRec; ENDLOOP; sortedCsl _ thisRec.coordSysCell; }; -- end of SortCoordSysListByBreadth CoordSysSortRec: TYPE = REF CoordSysSortRecObj; CoordSysSortRecObj: TYPE = RECORD[ index: NAT, coordSysCell: CoordSysList]; SortProc: SAFE PROC [x, y: PriorityQueue.Item, data: REF _ NIL] RETURNS [BOOL] = { xRec: CoordSysSortRec _ NARROW[x]; yRec: CoordSysSortRec _ NARROW[y]; RETURN[xRec.index > yRec.index]; }; ListLength: PRIVATE PROC [csl: CoordSysList] RETURNS [len: NAT] = { len _ 0; FOR list: CoordSysList _ csl, list.rest UNTIL list = NIL DO len _ len + 1; ENDLOOP; }; Depth: PRIVATE PROC [cs: CoordSystem] RETURNS [index: NAT] = { <> thisCS: CoordSystem; index _ 0; thisCS _ cs; UNTIL thisCS = NIL DO index _ index + 1; thisCS _ CoordSys.Parent[thisCS]; ENDLOOP; }; <<>> ListTree: PUBLIC PROC [outHandle: IO.STREAM, tree: CSGTree] = { indent: NAT _ 0; node: REF ANY _ tree.son; ListNode[outHandle, node, indent]; }; ListNode: PROC [outHandle: IO.STREAM, node: REF ANY, indent: NAT] = { WITH node SELECT FROM prim: Primitive => ListPrimitive[outHandle, prim, indent]; comp: Composite => ListComposite[outHandle, comp, indent]; ENDCASE => ERROR; }; ListPrimitive: PROC [outHandle: IO.STREAM, prim: Primitive, indent: NAT] = { FOR i: NAT IN[1..indent] DO outHandle.PutChar[IO.TAB] ENDLOOP; outHandle.PutF["Primitive: %g\n",[rope[prim.name]]]; }; ListComposite: PROC [outHandle: IO.STREAM, comp: Composite, indent: NAT] = { op: Rope.ROPE; FOR i: NAT IN[1..indent] DO outHandle.PutChar[IO.TAB] ENDLOOP; op _ SVRay.PointSetOpToRope[comp.operation]; outHandle.PutF["Composite: %g op: %g\n",[rope[comp.name]], [rope[op]]]; ListNode[outHandle, comp.leftSolid, indent + 1]; ListNode[outHandle, comp.rightSolid, indent + 1]; }; FindNodeFromName: PUBLIC PROC [tree: REF ANY, name: Rope.ROPE] RETURNS [node: REF ANY, success: BOOL] = { WITH tree SELECT FROM c: Composite => {[node, success] _ FindNodeFromNameInComposite[c, name]; RETURN}; p: Primitive => {[node, success] _ FindNodeFromNameInPrimitive[p, name]; RETURN}; ENDCASE => ERROR; }; FindNodeFromNameInComposite: PROC [c: Composite, name: Rope.ROPE] RETURNS [node: REF ANY, success: BOOL] = { IF Rope.Equal[c.name, name, TRUE] THEN RETURN[c, TRUE]; [node, success] _ FindNodeFromName[c.leftSolid, name]; IF success THEN RETURN; [node, success] _ FindNodeFromName[c.rightSolid, name]; IF success THEN RETURN ELSE RETURN[NIL, FALSE]; }; FindNodeFromNameInPrimitive: PROC [p: Primitive, name: Rope.ROPE] RETURNS [node: REF ANY, success: BOOL] = { IF p.name = name THEN RETURN[p, TRUE] ELSE RETURN[NIL, FALSE]; }; CommonAncestor: PUBLIC PROC [red: Slice, blue: Slice, root: Slice] RETURNS [gramps: Slice] = { <> IF red = NIL THEN RETURN[blue]; IF blue = NIL THEN RETURN[red]; WITH root.shape SELECT FROM shape: Shape => { <> IF red = root AND blue = root THEN RETURN[root] ELSE RETURN[NIL]; }; alist: SliceList => { <> FOR sons: LIST OF Slice _ alist.list, sons.rest UNTIL sons = NIL DO IF ContainsBoth[red, blue, sons.first] THEN RETURN[CommonAncestor[red, blue, sons.first]]; ENDLOOP; <> IF ContainsBoth[red, blue, root] THEN RETURN[root] ELSE RETURN[NIL]; }; ENDCASE => ERROR; }; ContainsBoth: PRIVATE PROC [red: Slice, blue: Slice, root: Slice] RETURNS [BOOL] = { RETURN[IsSuccessorOf[red, root] AND IsSuccessorOf[blue, root]]; }; IsSuccessorOf: PUBLIC PROC [testChild: Slice, testAncestor: Slice] RETURNS [BOOL] = { WITH testAncestor.shape SELECT FROM shape: Shape => { IF testAncestor = testChild THEN RETURN[TRUE] ELSE RETURN[FALSE]; }; alist: SliceList => { <> <<1) It is lookFor.>> <<2) It has a son which contains lookFor.>> IF testAncestor = testChild THEN RETURN[TRUE]; FOR list: LIST OF Slice _ alist.list, list.rest UNTIL list = NIL DO IF IsSuccessorOf[testChild, list.first] THEN RETURN[TRUE]; ENDLOOP; RETURN[FALSE]; }; ENDCASE => ERROR; }; AncestorAtLevel: PUBLIC PROC [child: Slice, root: Slice, level: NAT] RETURNS [gramps: Slice] = { < 0 then return the first non-NIL value returned by one of the children, or NIL if there are none.>> IF level = 0 THEN { IF IsSuccessorOf[child, root] THEN RETURN[root] ELSE RETURN[NIL]; } ELSE { WITH root.shape SELECT FROM shape: Shape => RETURN[NIL]; -- level >0 and we have no children. alist: SliceList => { FOR list: LIST OF Slice _ alist.list, list.rest UNTIL list = NIL DO gramps _ AncestorAtLevel[child, list.first, level-1]; IF gramps # NIL THEN RETURN; ENDLOOP; RETURN[NIL]; }; ENDCASE => ERROR; }; }; END.