File: DisplayListToTreeImpl.mesa
Author: Eric Bier on January 1, 1983 11:43 pm
Copyright © 1984 by Xerox Corporation. All rights reserved.
Last edited by Bier on August 5, 1984 8:16:14 pm PDT
Contents: Code to extract a CSG Tree from the recursive assemblylist-of-assemblylist DisplayList structure.
DIRECTORY
CoordSys,
CSG,
Convert,
DisplayListToTree,
IO,
Matrix3d,
PriorityQueue,
Rope,
SV3d,
SVModelTypes,
SVRayTypes,
SVSceneTypes,
SVTransforms;
DisplayListToTreeImpl: CEDAR PROGRAM
IMPORTS Convert, CoordSys, CSG, IO, Matrix3d, PriorityQueue, Rope, SVTransforms
EXPORTS DisplayListToTree =
BEGIN
Assembly: TYPE = SVSceneTypes.Assembly;
AssemblyList: TYPE = SVSceneTypes.AssemblyList;
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;
AssemblyToTree:
PUBLIC
PROC [assembly: Assembly, scene: Scene, camera: Camera]
RETURNS [tree: CSGTree] = TRUSTED {
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.
topAssembly: Assembly;
topNode: REF ANY;
SVTransforms.TellAboutCameraAndWorld[assembly.coordSys, camera, scene];
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)
topAssembly ← assembly;
topNode ← AssemblyToNode[topAssembly, FALSE]; -- Make the tree.
tree ←
CSG.MakeCSGTree[topNode, scene.backgroundColor, scene.shadows];
Adds background color, and shadow information and packages up into a CSGTree record.
};
AssemblyToNode:
PROC [assembly: Assembly, inverted:
BOOL]
RETURNS [node:
REF
ANY] = {
If assembly is a primitive assembly, return a primitive CSG node. Otherwise, call AssemblyListToNode on its children and return the resulting tree.
IF assembly = NIL THEN RETURN[ NIL ];
WITH assembly.shape
SELECT
FROM
shape: Shape => {
newPrim: Primitive;
newPrim ← PrimitiveFromAssembly[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;
We have a list of composite assemblies and/or primitive assemblies. Turn this into a list of Composites, Primitives and NILs:
treeList ← AssemblyListToTreeList[list, assemblyList.pointSetOp];
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 treeList = NIL THEN RETURN[ NIL ];
If there is only one item in the list then the node for this assembly is the node produced for its son.
IF treeList.rest =
NIL
THEN {
node ← treeList.first;
RETURN}
ELSE {
-- Inspect the treeList more carefully.
If all of the children are NIL, so is this node.
IF AllAreNil[treeList] THEN RETURN[NIL];
If the operation is intersection and any are NIL then so is the node.
IF assemblyList.pointSetOp = intersection AND AnyAreNIL[treeList] THEN RETURN[ NIL ];
IF the first is NIL and the operation is difference then the node is NIL.
IF treeList.first = NIL AND assemblyList.pointSetOp = difference THEN RETURN[ NIL ];
We have handled all cases which involve NILs. For all other cases, we should ignore them, so we will remove them now:
treeList ← SpliceOutNILs[treeList];
At this point, we must reconsider the possibility that we may have a null list or single member list.
IF treeList = NIL THEN RETURN[NIL];
IF treeList.rest =
NIL
THEN {
node ← treeList.first;
RETURN}
ELSE {
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).
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] = {
In the top level call to MakeUnionNode, treeList should have at least 2 members and none of its members should be NIL.
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] = {
In the top level call to MakeIntersectionNode, treeList should have at least 2 members and none of its members should be NIL.
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] = {
In the top level call to MakeDifferenceNode, treeList should have at least 2 members and none of its members should be NIL.
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 Assembly, op: PointSetOp]
RETURNS [treeList:
LIST
OF
REF
ANY] = {
If there are no children, then this node is NIL. It has no effect on the ray tracing.
IF list = NIL THEN RETURN[ NIL ];
Go down the list turning each primitive or composite assembly into a Composite or Primitive.
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 there are no children, then this node is NIL. It has no effect on the ray tracing.
IF list = NIL THEN RETURN[ NIL ];
Go down the list turning each primitive or composite assembly into a Composite or Primitive.
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: Assembly, inverted:
BOOL]
RETURNS [prim: Primitive] =
TRUSTED {
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.primWRTAssembly ← shape.coordSys;
prim.scalars ← CoordSys.GetScalars[shape.coordSys];
prim.primWRTWorld ← shape.coordSys.wrtWorld;
prim.worldWRTPrim ← Matrix3d.Inverse[prim.primWRTWorld];
prim.hints will be filled in at preprocess time
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] = {
Returns a list of all of the assembly coordinate systems (not including the scalars-only shape coordinate systems). The list is in breadth-first order.
csl ← CoordSysListFromAssembly[scene.assembly];
csl ← SortCoordSysListByBreadth[csl];
csl ← CONS[scene.coordSysRoot, csl]; -- add WORLD
};
CoordSysListFromAssembly:
PROC [assem: Assembly]
RETURNS [csl: CoordSysList] = {
end: CoordSysList;
alist, apos, aend: LIST OF Assembly;
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: AssemblyList => {
FOR children:
LIST
OF Assembly ← 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;
};
Because the coordinate system and assembly trees need not be isomorphic, we must be careful to
1) Put into the list only those coordinate systems belonging to assemblies, but
2) Sort the list by depth order of the coordinate systems.
One unreasonable way to do this is to tree walk the assemblies to make the list and then sort by depth (which we uncover in NlogN fashion by looking up the tree every bloody time). A better solution is to have a "depth" field in coordinate systems, but that will come later.
SortCoordSysListByBreadth:
PRIVATE
PROC [csl: CoordSysList]
RETURNS [sortedCsl: CoordSysList] = {
We do not currently store a node's depth in that node. We recover this information stupidly in an NlogN sort of way by walking to the root from each node. Then we sort these depth numbers. This sorting is used to fileout scene trees. Of course, sorting is NlogN as well. Maybe I will use a bucket sort someday.
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;
We sort deep to shallow so we can put the list together backwards
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] =
TRUSTED {
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] = {
Index is distance from WORLD coordsys
thisCS: CoordSystem;
index ← 0;
thisCS ← cs;
UNTIL thisCS =
NIL
DO
index ← index + 1;
thisCS ← thisCS.parent;
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] =
TRUSTED {
op: Rope.ROPE;
FOR i: NAT IN[1..indent] DO outHandle.PutChar[IO.TAB] ENDLOOP;
op ← CSG.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: Assembly, blue: Assembly, root: Assembly]
RETURNS [gramps: Assembly] = {
Here's where it hurts that assemblys don't point to their parents. For now, I will try a brute force approach. Starting at the root, I will walk down the tree until I find a node which contatins red and blue but none of whose children contains both. Returns NIL if no such node exists (perhaps root is below the real gramps, etc.).
IF red = NIL THEN RETURN[blue];
IF blue = NIL THEN RETURN[red];
WITH root.shape SELECT FROM
shape: Shape => {
If root is a Primitive then root can only be gramps if red = blue = root;
IF red = root AND blue = root THEN RETURN[root]
ELSE RETURN[NIL];
};
alist: AssemblyList => {
Could any of root's sons be gramps?
FOR sons:
LIST
OF Assembly ← alist.list, sons.rest
UNTIL sons =
NIL
DO
IF ContainsBoth[red, blue, sons.first] THEN RETURN[CommonAncestor[red, blue, sons.first]];
ENDLOOP;
None of the sons contain both. If I contain both, I am gramps.
IF ContainsBoth[red, blue, root] THEN RETURN[root]
ELSE RETURN[NIL];
};
ENDCASE => ERROR;
};
ContainsBoth:
PRIVATE
PROC [red: Assembly, blue: Assembly, root: Assembly]
RETURNS [
BOOL] = {
RETURN[IsSuccessorOf[red, root] AND IsSuccessorOf[blue, root]];
};
IsSuccessorOf:
PUBLIC
PROC [testChild: Assembly, testAncestor: Assembly]
RETURNS [
BOOL] = {
WITH testAncestor.shape SELECT FROM
shape: Shape => {
IF testAncestor = testChild THEN RETURN[TRUE]
ELSE RETURN[FALSE];
};
alist: AssemblyList => {
A Composite assembly contains if
1) It is lookFor.
2) It has a son which contains lookFor.
IF testAncestor = testChild THEN RETURN[TRUE];
FOR list:
LIST
OF Assembly ← 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: Assembly, root: Assembly, level:
NAT]
RETURNS [gramps: Assembly] = {
Returns the ancestor of child which is level levels below root. If level is 0, should return root. If level = 1, an immediate child of root and so on. Works recursively as follows: If level is 0 then if root contains child, return root, else return NIL. If level > 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: AssemblyList => {
FOR list:
LIST
OF Assembly ← 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.