DIRECTORY CSG, CSGGraphics, Convert, DisplayList3d, IO, Matrix3d, Rope, SVPrimitive, SVTransforms; DisplayListToTreeImpl: PROGRAM IMPORTS Convert, CSG, IO, Rope, SVPrimitive, SVTransforms EXPORTS DisplayList3d = BEGIN Scene: TYPE = REF SceneObj; SceneObj: TYPE = DisplayList3d.SceneObj; AssemblyList: TYPE = REF AssemblyListObj; AssemblyListObj: TYPE = DisplayList3d.AssemblyListObj; PointSetOp: TYPE = CSG.PointSetOp;-- {union, intersection, difference} Assembly: TYPE = REF AssemblyObj; AssemblyObj: TYPE = DisplayList3d.AssemblyObj; Camera: TYPE = CSGGraphics.Camera; MasterObject: TYPE = REF MasterObjectRec; MasterObjectRec: TYPE = DisplayList3d.MasterObjectRec; CSGTree: TYPE = REF CSGTreeObj; CSGTreeObj: TYPE = CSG.CSGTreeObj; Primitive: TYPE = REF PrimitiveObj; PrimitiveObj: TYPE = CSG.PrimitiveObj; Matrix4by4: TYPE = Matrix3d.Matrix4by4; SurfaceArray: TYPE = REF SurfaceArrayObj; SurfaceArrayObj: TYPE = CSG.SurfaceArrayObj;-- ARRAY[1..maxSceneDepth] OF Surface; Surface: TYPE = REF ANY; -- may be RectSurface, TubeSurface, DiskSurface, or ShellSurface (of BasicObject3d), etc. Composite: TYPE = REF CompositeObj; CompositeObj: TYPE = CSG.CompositeObj; SceneToTree: PUBLIC PROC [scene: Scene, camera: Camera] RETURNS [tree: CSGTree] = { topAssembly: Assembly; topNode: REF ANY; SVTransforms.TellAboutCameraAndWorld[scene.assembly, camera, scene]; topAssembly _ scene.assembly; topNode _ AssemblyToNode[topAssembly, FALSE]; tree _ CSG.MakeCSGTree[topNode, scene.backgroundColor, scene.shadows]; }; AssemblyToNode: PROC [assembly: Assembly, inverted: BOOL] RETURNS [node: REF ANY] = { IF assembly = NIL THEN RETURN[ NIL ]; WITH assembly.object SELECT FROM mo: MasterObject => { newPrim: Primitive; newPrim _ SVPrimitive.FromAssembly[assembly, inverted]; node _ newPrim; RETURN}; alist: AssemblyList => { node _ AssemblyListToNode[alist, assembly.name]; RETURN}; ENDCASE => ERROR; }; -- end of AssemblyToNode AssemblyListToNode: PROC [assemblyList: AssemblyList, name: Rope.ROPE] RETURNS [node: REF ANY] = { list: LIST OF Assembly _ 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.ValueToRope[[unsigned[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.ValueToRope[[unsigned[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.ValueToRope[[unsigned[level]]]]; node _ NEW[CompositeObj _ [intermediateName, difference, leftNode, rightNode]]; }; -- end of MakeDifferenceNode AssemblyListToTreeList: PROC [list: LIST OF Assembly, 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 Assembly, 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]; }; ---- ---- ---- ---- ---- ---- ---- ---- 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; SELECT comp.operation FROM union => op _ "union"; intersection => op _ "intersection"; difference => op _ "difference"; ENDCASE => ERROR; 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]; }; END. ╬File: DisplayListToTreeImpl.mesa Author: Eric Bier on January 1, 1983 11:43 pm Last edited by Bier on August 18, 1983 12:16 pm Contents: Code to extract a CSG Tree from the recursive assemblylist-of-assemblylist DisplayList structure. Here's the plan: Each assembly list has an associated PointSetOp. If this op is null, it defaults to "union". Intersection means the intersection of all objects on the assembly list. Union is the union of all of them. Difference is the first one minus all of the others. Preprocess the scene to make sure all the assemblies know where they are so they can tell the primitives at PrimitiveFromAssembly time (see BasicObject3dImpl.mesa for example) If assembly is a primitive assembly, return a primitive CSG node. Otherwise, call AssemblyListToNode on its children and return the resulting tree. We have a list of composite assemblies and/or primitive assemblies. Turn this into a list of Composites, Primitives and NILs: Now we will inspect our list in order to combine the trees we have made. If there are no children, then this node is NIL. It has no effect on the ray tracing. If there is only one item in the list then the node for this assembly is the node produced for its son. If all of the children are NIL, so is this node. If the operation is intersection and any are NIL then so is the node. IF the first is NIL and the operation is difference then the node is NIL. We have handled all cases which involve NILs. For all other cases, we should ignore them, so we will remove them now: At this point, we must reconsider the possibility that we may have a null list or single member list. Since it is now clear that this node has more than one child, we make n-1 Composite nodes for it (if there are n children remaining). In the top level call to MakeUnionNode, treeList should have at least 2 members and none of its members should be NIL. In the top level call to MakeIntersectionNode, treeList should have at least 2 members and none of its members should be NIL. In the top level call to MakeDifferenceNode, treeList should have at least 2 members and none of its members should be NIL. If there are no children, then this node is NIL. It has no effect on the ray tracing. Go down the list turning each primitive or composite assembly into a Composite or Primitive. If there are no children, then this node is NIL. It has no effect on the ray tracing. Go down the list turning each primitive or composite assembly into a Composite or Primitive. Э╩Ц "cedar" styleШIheadЪЬ Щ IprocЪЬ-Щ-LЪЬ/Щ/LЪЬkЩkLШЪ╧k Ш LЪЭЬШLЪЬШLЪЬШLЪЬШLЪЭЬШLЪЬ Ш LЪЬШLЪЬШLЪЬ Ш LШЧЪЬЭШLЪЭЬ ЭЬЭЬ!Ш9LЪЭЬШЧLЪЭШШLЪЬЭЬЭЬ ШLЪЬ ЭЬШ(LШLЪЬЭЬЭЬШ)LЪЬЭЬ!Ш6LШLЪЬЭЬЭЬ╧c$ШFLШLЪЬ ЭЬЭЬ Ш!LЪЬ ЭЬШ.LШLЪЬЭЬШ"LШLЪЬЭЬЭЬШ)LЪЬЭЬ!Ш6LШLЪЬ ЭЬЭЬШLЪЬЭЬЭЬШ"LШLЪЬЭЬЭЬШ#LЪЬЭЬЭЬШ&LШLЪЬЭЬШ'LЪЬЭЬЭЬШ)LЪЬЭЬЭЬЮ&ШRLЪЬ ЭЬЭЬЭЬЮYШrLШLЪЬЭЬЭЬШ#LЪЬЭЬЭЬШ&LШLШЪ╧nЬЭЬЭЬ ЭЬШSLЪЬУЩУLЪЬШLЪЬ ЭЬЭЬШLЪЬDШDLЪЬпЩпLЪЬШLЪЬ&ЭЬШ-LЪЬЭЬ<ШFLЪЬШЧLШЪЯЬЭЬ ЭЬЭЬЭЬЭЬШULЪЬФЩФLЪ ЭЬЭЬЭЬЭЬЭЬШ%ЪЭЬЭЬЭШ ЪЬШLЪЬШLЪЬ7Ш7LЪЬШLЪЭЬШЧЪЬШLЪЬ0Ш0LЪЭЬШЧLЪЭЬЭЬШЧLЪЬЮШЧLШЪЯЬЭЬ)ЭЬЭЬЭЬЭЬШbLЪЬЭЬЭЬШ+LЪ Ь ЭЬЭЬЭЬЭЬШLЩ~LЪЬAШALЩHLЪЬVЩVLЪ ЭЬЭЬЭЬЭЬЭЬШ%LЪЬgЩgЪЭЬЭЬЭЬШLЪЬШLЪЭЬШЧЪЭЬЮ'Ш.LЩ0LЪЭЬЭЬЭЬЭЬШ(LЩELЪ ЭЬ(ЭЬЭЬЭЬЭЬШULЩILЪЭЬЭЬЭЬ&ЭЬЭЬЭЬШTLЩvLЪЬ#Ш#LШLЩeLЪ ЭЬЭЬЭЬЭЬЭЬШ#ЪЭЬЭЬЭЬШLЪЬШLЪЭЬШЧLЪЭЬШLЩЕЪЭЬЭШ#LЪЬ1Ш1LЪЬ?Ш?LЪЬ;Ш;LЪЭЬЭЬШLЪЬЮШЧLЪЬЮШЧLЪЬЮШ ЧЪЯ ЬЭЬЭЬЭЬЭЬЭЬ ЭЬ ЭЬЭЬЭЬЭЬШhLЪЬvЩvLЪЬЭЬЭЬШLЪЬЭЬШLЪ ЭЬЭЬЭЬЭЬЭЬШ$LЪЭЬЭЬЭЬЭЬШ4LЪЬШLЪЬ:Ш:LЪЬNШNLЪЬЭЬ@ШJLЪЬЮШЧЪЯЬЭЬЭЬЭЬЭЬЭЬ ЭЬ ЭЬЭЬЭЬЭЬШoLЪЬ}Щ}LЪЬЭЬЭЬШLЪЬЭЬШLЪ ЭЬЭЬЭЬЭЬЭЬШ$LЪЭЬЭЬЭЬЭЬШ4LЪЬШLЪЬAШALЪЬNШNLЪЬЭЬGШQLЪЬЮШ"ЧЪЯЬЭЬЭЬЭЬЭЬЭЬ ЭЬ ЭЬЭЬЭЬЭЬШmLЪЬ{Щ{LЪЬЭЬЭЬШLЪЬЭЬШLЪЬШLЪЬ╧b Ь!Ш:LЪЬNШNLЪЬЭЬEШOLЪЬЮШЧLШЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШmLЪЬVЩVLЪ ЭЬЭЬЭЬЭЬЭЬШ!LЪЬ\Щ\ЪЭЬЭЬШLЪЬЭЬ0ЭЬ6ЭЬШАЧЪЭШLЪЬЭЬ0ЭЬ6ЭЬШВЧLЪЬЮ!Ш$ЧЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШnLЪЬVЩVLЪ ЭЬЭЬЭЬЭЬЭЬШ!LЪЬ\Щ\LЪЬЭЬVШeLЪЬЮ!ЬШ%ЧЪЯ ЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШBЪЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭШ6LЪ ЭЬЭЬЭЬЭЬЭЬШ$ЧLЪЭЬШLЪЭЬЭЬШ LШЧЪЯ ЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШBЪЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭШ6LЪ ЭЬЭЬЭЬЭЬЭЬШ#ЧLЪЭЬШLЪЭЬЭЬШLШЧЪЯ ЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШ]LЪ ЭЬЭЬЭЬЭЬЭЬШ LЪЭЬЭЬЭЬЭЬ&ШPLЪЭЬ'Ш+LШЧLЪЮЬЮЬЮЬЮШLШLЪЮЬЮЬЮЬЮШLШLШЪ ЯЬЭЬЭЬ ЭЬЭЬШ?LЪЬЭЬШLЪЬЭЬЭЬШLЪЬ"Ш"LЪЬШЧLШЪЯЬЭЬ ЭЬЭЬЭЬЭЬ ЭЬШEЪЭЬЭЬЭШLЪЬ:Ш:LЪЬ:Ш:LЪЭЬЭЬШЧLЪЬШЧLШЪ Я ЬЭЬ ЭЬЭЬЭЬШLLЪЭЬЭЬЭЬЭЬЭЬЭЬЭЬШ>LЪЬ4Ш4LЪЬШЧLШЪ Я ЬЭЬ ЭЬЭЬЭЬШLLЪЬ ЭЬШLЪЭЬЭЬЭЬЭЬЭЬЭЬЭЬШ>ЪЭЬЭШLЪЬШLЪЬ$Ш$LЪЬ Ш LЪЭЬЭЬШЧLЪЬGШGLЪЬ0Ш0LЪЬ1Ш1LЪЬШЧLШЪЯЬЭЬЭЬЭЬЭЬ ЭЬЭЬЭЬЭЬЭЬШiЪЭЬЭЬЭШLЪЬIЭЬШQLЪЬIЭЬШQLЪЭЬЭЬШЧLЪЬШЧLШЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬШlLЪ ЭЬЭЬЭЬЭЬЭЬШ7LЪЬ6Ш6LЪЭЬ ЭЬЭЬШLЪЬ7Ш7LЪЭЬ ЭЬЭШLЪЭЬЭЬЭЬЭЬШLЪЬШЧLШЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬШlLЪЭЬЭЬЭЬЭЬШ%LЪЭЬЭЬЭЬЭЬШLЪЬШЧЧLШLШLЪЭЬШLШЧЕЧ|4V