<> <> <> <> <> DIRECTORY SVCoordSys, SVRay, Convert, SVSceneToTree, Imager, IO, List, PriorityQueue, Rope, SV3d, SVModelTypes, SVSceneTypes, SVSelect; SVSceneToTreeImpl: CEDAR PROGRAM IMPORTS Convert, SVCoordSys, SVRay, SVSelect, Imager, IO, List, PriorityQueue, Rope EXPORTS SVSceneToTree = BEGIN Slice: TYPE = SVSceneTypes.Slice; SliceDescriptor: TYPE = SVSceneTypes.SliceDescriptor; SliceList: TYPE = SVSceneTypes.SliceList; Camera: TYPE = SVModelTypes.Camera; Composite: TYPE = REF CompositeObj; CompositeObj: TYPE = SVSceneTypes.CompositeObj; CoordSystem: TYPE = SVModelTypes.CoordSystem; CoordSysList: TYPE = SVModelTypes.CoordSysList; CSGTree: TYPE = SVSceneTypes.CSGTree; MasterObject: TYPE = SVSceneTypes.MasterObject; Matrix4by4: TYPE = SV3d.Matrix4by4; PointSetOp: TYPE = SVSceneTypes.PointSetOp; -- {union, intersection, difference} Primitive: TYPE = REF PrimitiveObj; PrimitiveObj: TYPE = SVSceneTypes.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 = SVSceneTypes.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, scene, FALSE, ignoreMoving]; -- 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, scene: Scene, inverted, ignoreMoving: BOOL] RETURNS [node: REF ANY] = { <> IF assembly = NIL THEN RETURN[ NIL ]; WITH assembly.shape SELECT FROM shape: Shape => { newPrim: Primitive; newPrim _ PrimitiveFromAssembly[assembly, scene, inverted, ignoreMoving]; node _ newPrim; RETURN}; alist: SliceList => { node _ AssemblyListToNode[alist, scene, assembly.name, ignoreMoving]; RETURN}; ENDCASE => ERROR; }; -- end of AssemblyToNode AssemblyListToNode: PROC [assemblyList: SliceList, scene: Scene, name: Rope.ROPE, ignoreMoving: BOOL] RETURNS [node: REF ANY] = { list: LIST OF Slice _ assemblyList.list; treeList: LIST OF REF ANY; <> treeList _ AssemblyListToTreeList[list, scene, assemblyList.pointSetOp, ignoreMoving]; <> <> 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; endFirstHalf, secondHalf: LIST OF REF ANY; len: CARD; IF treeList = NIL THEN RETURN[ NIL]; IF treeList.rest = NIL THEN RETURN [treeList.first]; len _ List.Length[treeList]; endFirstHalf _ List.NthTail[treeList, len/2-1]; secondHalf _ endFirstHalf.rest; endFirstHalf.rest _ NIL; leftNode _ MakeUnionNode[treeList, name, level + 1]; rightNode _ MakeUnionNode[secondHalf, 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, scene: Scene, op: PointSetOp, ignoreMoving: BOOL] RETURNS [treeList: LIST OF REF ANY] = { IF list = NIL THEN RETURN[NIL]; <> IF op = difference THEN treeList _ CONS[ AssemblyToNode[assembly: list.first, scene: scene, inverted: FALSE, ignoreMoving: ignoreMoving], AssemblyListToTreeList2[list: list.rest, scene: scene, inverted: TRUE, ignoreMoving: ignoreMoving]] ELSE treeList _ CONS[ AssemblyToNode[assembly: list.first, scene: scene, inverted: FALSE, ignoreMoving: ignoreMoving], AssemblyListToTreeList2[list: list.rest, scene: scene, inverted: FALSE, ignoreMoving: ignoreMoving]]; }; -- end of AssemblyListToTreeList SliceListMapCar: PROC [proc: PROC [Slice] RETURNS [REF ANY], list: LIST OF Slice] RETURNS [newList: LIST OF REF ANY] ~ { newListEnd: LIST OF REF ANY; IF list = NIL THEN RETURN[NIL]; newList _ newListEnd _ CONS[proc[list.first], NIL]; FOR tail: LIST OF Slice _ list.rest, tail.rest UNTIL tail = NIL DO newListEnd.rest _ CONS[proc[tail.first], NIL]; newListEnd _ newListEnd.rest; ENDLOOP; }; AssemblyListToTreeList2: PROC [list: LIST OF Slice, scene: Scene, inverted: BOOL, ignoreMoving: BOOL] RETURNS [treeList: LIST OF REF ANY] = { mapProc: PROC [slice: Slice] RETURNS [REF ANY] ~ { <> RETURN[AssemblyToNode[slice, scene, inverted, ignoreMoving]]; }; treeList _ SliceListMapCar[mapProc, list]; }; -- 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 [slice: Slice, scene: Scene, inverted, ignoreMoving: BOOL] RETURNS [prim: Primitive] = { mo: MasterObject; shape: Shape; sliceD, stillD: SliceDescriptor; prim _ NEW[PrimitiveObj]; IF NOT ISTYPE[slice.shape, Shape] THEN ERROR PrimitiveAssemblyWithoutMO; shape _ NARROW[slice.shape]; mo _ shape.mo; <> IF ignoreMoving THEN { sliceD _ SVSelect.FindSelectedSlice[slice, scene, normal]; IF sliceD = NIL THEN stillD _ mo.class.newParts[slice, NIL, [0,0,0], slice] ELSE { background, overlay, rubber, drag: SliceDescriptor; [background, overlay, rubber, drag] _ mo.class.movingParts[sliceD.slice, sliceD.parts]; stillD _ mo.class.unionParts[background, overlay]; }; } ELSE stillD _ mo.class.newParts[slice, NIL, [0,0,0], slice]; prim.name _ slice.name; prim.artwork _ slice.artwork; prim.assembly _ slice; prim.mo _ mo; prim.sliceD _ stillD; prim.rayCast _ mo.class.rayCast; prim.rayCastNoBBoxes _ mo.class.rayCastNoBBoxes; prim.rayCastBoundingSpheres _ mo.class.rayCastBoundingSpheres; prim.localCS _ shape.coordSys; prim.scalars _ SVCoordSys.GetScalars[shape.coordSys]; prim.primWRTWorld _ SVCoordSys.WRTWorld[shape.coordSys]; prim.worldWRTPrim _ SVCoordSys.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; <> slice.prim _ prim; }; 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; < 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 _ SVCoordSys.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.