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: NATListLength[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: REFNIL] 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.