Directed acyclic graph path enumeration with application in multilevel instancing

1. A non-transitory machine-readable medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform operations comprising:

enumerating a directed path through a directed multi-level instancing graph by popping a node of the directed multi-level instancing graph from a node queue;

computing a key value for the node and assigning the key value to the node;

recording a minimum path identifier to use in processing one or more children of the node;

computing a next path identifier to use in processing one or more children of the node, the next path identifier greater than a current path identifier;

for each child node of the node, updating the minimum path identifier and maximum path identifier for the child node;

pushing a child node onto the node queue after the minimum path identifier and maximum path identifier for the child node is updated for each parent of the child node; and

rending an object for display on a display device using the directed acyclic graph.

2. The non-transitory machine-readable medium of claim 1 , before processing a non-root node of the multi-level instancing graph, the operations include:

initializing the minimum path identifier and the maximum path identifier for a root node of a directed multi-level instancing graph to zero;

initializing the path identifier to one; and

pushing the root node onto the node queue.

3. The non-transitory machine-readable medium as in claim 1 , the operations additionally including determining a value for the minimum path identifier based on the value of a current path identifier.

4. The non-transitory machine-readable medium as in claim 1 , the operations additionally including determining a value of the next path identifier based on values of the minimum path identifier and maximum path identifier for the node.

5. The non-transitory machine-readable medium as in claim 1 , the operations additionally including, after assigning a key to each node of a directed edge, determining a path identifier for the directed edge based on a sum of the key values of each node of the directed edge.

6. A computer-implemented method comprising:

enumerating a directed path through a directed multi-level instancing graph by popping a node of the directed multi-level instancing graph from a node queue;

computing a key value for the node and assigning the key value to the node;

recording a minimum path identifier to use in processing one or more children of the node;

computing a next path identifier to use in processing one or more children of the node, the next path identifier greater than a current path identifier;

for each child node of the node, updating the minimum path identifier and maximum path identifier for the child node;

pushing a child node onto the node queue after the minimum path identifier and maximum path identifier for the child node is updated for each parent of the child node; and

rendering an object for display on a display device using the directed acyclic graph.

7. The method of claim 6 , before processing a non-root node of the multi-level instancing graph, further comprising:

initializing the minimum path identifier and the maximum path identifier for a root node of a directed multi-level instancing graph to zero; initializing the path identifier to one; and

pushing the root node onto the node queue.

8. The method of claim 6 , further comprising determining a value for the minimum path identifier based on the value of a current path identifier.

9. The method of claim 6 , further comprising determining a value of the next path identifier based on values of the minimum path identifier and maximum path identifier for the node.

10. The method of claim 6 , further comprising after assigning a key to each node of a directed edge, determining a path identifier for the directed edge based on a sum of the key values of each node of the directed edge.

11. An apparatus comprising:

one or more processors to:

enumerate a directed path through a directed multi-level instancing graph by pop a node of the directed multi-level instancing graph from a node queue;

compute a key value for the node and assigning the key value to the node;

record a minimum path identifier to use in processing one or more children of the node;

compute a next path identifier to use in processing one or more children of the node, the next path identifier greater than a current path identifier;

for each child node of the node, update the minimum path identifier and maximum path identifier for the child node;

push a child node onto the node queue after the minimum path identifier and maximum path identifier for the child node is updated for each parent of the child node; and

render an object for display on a display device using the directed acyclic graph.

12. The apparatus of claim 11 , before processing a non-root node of the multi-level instancing graph, the one or more processors are further to:

initialize the minimum path identifier and the maximum path identifier for a root node of a directed multi-level instancing graph to zero; initializing the path identifier to one; and

push the root node onto the node queue.

13. The apparatus of claim 11 , wherein the one or more processors are further to determine a value for the minimum path identifier based on the value of a current path identifier.

14. The apparatus of claim 11 , wherein the one or more processors are further to determine a value of the next path identifier based on values of the minimum path identifier and maximum path identifier for the node.

15. The apparatus of claim 11 , after assigning a key to each node of a directed edge, the one or more processors are further to determine a path identifier for the directed edge based on a sum of the key values of each node of the directed edge.

16. A system comprising:

a display device; and

a memory coupled to one or more processors, the one or more processors to:

enumerate a directed path through a directed multi-level instancing graph by pop a node of the directed multi-level instancing graph from a node queue;

compute a key value for the node and assigning the key value to the node;

record a minimum path identifier to use in processing one or more children of the node;

compute a next path identifier to use in processing one or more children of the node, the next path identifier greater than a current path identifier;

for each child node of the node, update the minimum path identifier and maximum path identifier for the child node;

push a child node onto the node queue after the minimum path identifier and maximum path identifier for the child node is updated for each parent of the child node; and

render an object for display on the display device using the directed acyclic graph.

17. The system of claim 16 , before processing a non-root node of the multi-level instancing graph, the one or more processors are further to:

initialize the minimum path identifier and the maximum path identifier for a root node of a directed multi-level instancing graph to zero; initializing the path identifier to one; and

push the root node onto the node queue.

18. The system of claim 16 , wherein the one or more processors are further to determine a value for the minimum path identifier based on the value of a current path identifier.

19. The system of claim 16 , wherein the one or more processors are further to determine a value of the next path identifier based on values of the minimum path identifier and maximum path identifier for the node.

20. The system of claim 16 , after assigning a key to each node of a directed edge, the one or more processors are further to determine a path identifier for the directed edge based on a sum of the key values of each node of the directed edge.