Generalized instancing for three-dimensional scene data
Systems and methods for rendering three-dimensional images by instancing scene description data using a hierarchy are provided. A hierarchy is accessed. The hierarchy comprises a first node and an instance node. The first node is a predecessor to a subtree of one or more nodes and the first node is associated with a first scene description data object. The instance node is a leaf of the hierarchy. The instance node has a parent node and the instance node is associated with a second scene description data object. The parent node has successor nodes other than the instance node. An instancing instruction of the instance node is read. The instancing instruction comprises information identifying the first node. An instance of the subtree of one or more nodes is merged at a location in the hierarchy of the instance node. An image is rendered based on the merged instance of the subtree.
1. A computer-implemented method for rendering three-dimensional images by instancing scene description data using a hierarchy, the method comprising:
accessing the hierarchy, the hierarchy comprising:
a first node, the first node being a predecessor to a first subtree of one or more nodes and the first node being associated with a first scene description data object;
an instance node, the instance node being a leaf of the hierarchy, the instance node having a parent node, and the instance node being associated with a second scene description data object, and wherein the parent node has successor nodes other than the instance node;
reading an instancing instruction of the instance node, the instancing instruction comprising information identifying the first node;
merging an instance of the first subtree of one or more nodes at a location in the hierarchy of the instance node;
determining a conflict between (a) at least one node of the first subtree and (b) at least one node of the successor nodes other than the instance node of the parent node;
overriding a first value of a property defined by the (b) at least one node of the successor nodes by using a second value of the property defined by the (a) at least one node of the first subtree; and
rendering an image based on the merged instance of the first subtree.
2. The computer-implemented method of claim 1 , wherein merging further comprises:
determining the conflict by:
accessing a first tag of the (a) at least one node of the first subtree, the first tag having a tag value;
accessing a second tag of the (b) at least one node of the successor nodes, the second tag having the tag value; and
wherein tag values uniquely identify sibling nodes in the hierarchy.
3. The computer-implemented method of claim 2 , wherein:
the first node has a third tag;
the information identifying the first node comprises a path; and
the path includes the third tag of the first node.
4. The computer-implemented method of claim 1 , wherein:
the first subtree comprises a second node including a relative reference, the relative reference of the second node identifying a first identified node in the first subtree;
the merged instance of the first subtree comprises a third node including the relative reference, the relative reference of the third node identifying a second identified node in the merged instance of the first subtree; and
wherein the first identified node and the second identified node are not the same node.
5. The computer-implemented method of claim 1 , wherein:
the first subtree comprises a second node including an absolute reference, the absolute reference of the second node identifying a first identified node in the first subtree; and
the merged instance of the first subtree comprises a third node including the absolute reference, the absolute reference of the third node identifying the first identified node in the first subtree.
6. The computer-implemented method of claim 1 , wherein:
the first subtree comprises a fourth node including data that comprises a parent token, the parent token indicating an instruction to move up one level in the hierarchy.
7. A non-transitory computer-readable storage medium comprising computer-executable instructions for rendering three-dimensional images by instancing scene description data using a hierarchy, the computer-executable instructions comprising instructions for:
accessing the hierarchy, the hierarchy comprising:
a first node, the first node being a predecessor to a first subtree of one or more nodes and the first node being associated with a first scene description data object;
an instance node, the instance node being a leaf of the hierarchy, the instance node having a parent node, and the instance node being associated with a second scene description data object, and wherein the parent node has successor nodes other than the instance node;
reading an instancing instruction of the instance node, the instancing instruction comprising information identifying the first node;
merging an instance of the first subtree of one or more nodes at a location in the hierarchy of the instance node;
determining a conflict between (a) at least one node of the first subtree and (b) at least one node of the successor nodes other than the instance node of the parent node; and
overriding a first value of a property defined by the (b) at least one node of the successor nodes by using a second value of the property defined by the (a) at least one node of the first subtree; and
rendering an image based on the merged instance of the first subtree.
8. The non-transitory computer-readable storage medium of claim 7 , wherein merging further comprises instructions for:
determining the conflict by:
accessing a first tag of the (a) at least one node of the first subtree, the first tag having a tag value;
accessing a second tag of the (b) at least one node of the successor nodes, the second tag having the tag value; and
wherein tag values uniquely identify sibling nodes in the hierarchy.
9. The non-transitory computer-readable storage medium of claim 8 , wherein:
the first node has a third tag;
the information identifying the first node comprises a path; and
the path includes the third tag of the first node.
10. The non-transitory computer-readable storage medium of claim 7 , wherein:
the first subtree comprises a second node including a relative reference, the relative reference of the second node identifying a first identified node in the first subtree;
the merged instance of the first subtree comprises a third node including the relative reference, the relative reference of the third node identifying a second identified node in the merged instance of the first subtree; and
wherein the first identified node and the second identified node are not the same node.
11. The non-transitory computer-readable storage medium of claim 8 , wherein:
the first subtree comprises a second node including an absolute reference, the absolute reference of the second node identifying a first identified node in the first subtree; and
the merged instance of the first subtree comprises a third node including the absolute reference, the absolute reference of the third node identifying the first identified node in the first subtree.
12. The non-transitory computer-readable storage medium of claim 7 , wherein:
the first subtree comprises a fourth node including data that comprises a parent token, the parent token indicating an instruction to move up one level in the hierarchy.
13. An apparatus for rendering three-dimensional images by instancing scene description data using a hierarchy, the apparatus comprising:
a memory configured to store the hierarchy; and
one or more computer processors configured to:
access the hierarchy, the hierarchy comprising:
a first node, the first node being a predecessor to a first subtree of one or more nodes and the first node being associated with a first scene description data object;
an instance node, the instance node being a leaf of the hierarchy, the instance node having a parent node, and the instance node being associated with a second scene description data object, and wherein the parent node has successor nodes other than the instance node;
read an instancing instruction of the instance node, the instancing instruction comprising information identifying the first node;
merge an instance of the first subtree of one or more nodes at a location in the hierarchy of the instance node;
determine a conflict between (a) at least one node of the first subtree and (b) at least one node of the successor nodes other than the instance node of the parent node; and
override a first value of a property defined by the (b) at least one node of the successor nodes by using a second value of the property defined by the (a) at least one node of the first subtree; and
render an image based on the merged instance of the first subtree.
14. The apparatus of claim 13 , the one or more computer processors further configured to:
determine the conflict by:
accessing a first tag of the (a) at least one node of the first subtree, the first tag having a tag value;
accessing a second tag of the (b) at least one node of the successor nodes, the second tag having the tag value; and
wherein tag values uniquely identify sibling nodes in the hierarchy.
15. The apparatus of claim 14 , wherein:
the first node has a third tag;
the information identifying the first node comprises a path; and
the path includes the third tag of the first node.
16. The apparatus of claim 13 , wherein:
the first subtree comprises a second node including a relative reference, the relative reference of the second node identifying a first identified node in the first subtree;
the merged instance of the first subtree comprises a third node including the relative reference, the relative reference of the third node identifying a second identified node in the merged instance of the first subtree; and
wherein the first identified node and the second identified node are not the same node.
17. The apparatus of claim 13 , wherein:
the first subtree comprises a second node including an absolute reference, the absolute reference of the second node identifying a first identified node in the first subtree; and
the merged instance of the first subtree comprises a third node including the absolute reference, the absolute reference of the third node identifying the first identified node in the first subtree.
18. The apparatus of claim 13 , wherein:
the first subtree comprises a fourth node including data that comprises a parent token, the parent token indicating an instruction to move up one level in the hierarchy.