Systems and methods for representing, accessing, and moving within a three-dimensional environment using a mutable tree data structure

1. A method comprising:

receiving a tree-based representation of a three-dimensional (“3D”) environment, the tree-based representation comprising a root node with a position defined in the 3D environment, and a set of branches that are linked to the root node, wherein each branch of the set of branches comprises a set of subtree nodes representing a set of subdivided regions of the 3D environment that are a same distance from the position of the root node, and wherein the set of subtree nodes from different branches of the set of branches represent subdivided regions of the 3D environment that are a different distance from the position of the root node;

receiving a request to access data from a particular position in the 3D environment;

sorting the set of subtree nodes within each branch of the set of branches based on a distance between the particular position and each subdivided region of the 3D environment represented by each subtree node of the set of subtree nodes;

computing a distance between the position of the root node and the particular position; and

accessing the data associated with the particular position by traversing from the root node to a particular branch of the set of branches based on the distance between the position of the root node and the particular position being within the set of subdivided regions represented by the set of subtree nodes of the particular branch, and by selecting a first subtree node in the set of subtree nodes of the particular branch that represents a subdivided region from the set of subdivided regions of the particular branch that is closest to the particular position after said sorting.

2. The method of claim 1 , wherein accessing the data comprises:

retrieving a tree-based representation of the data contained within the subdivided region represented by the first subtree node of the particular branch.

3. The method of claim 2 , wherein accessing the data further comprises:

selecting a subset of nodes from a plurality of nodes of the tree-based representation of the data contained within the subdivided region, wherein the plurality of nodes store all data contained within the subdivided region, and wherein the subset of nodes store a subset of data associated with the particular position specified in the request.

4. The method of claim 1 further comprising:

receiving a second request to access data from a second position in the 3D environment that is different than the particular position; and

rearranging the set of subtree nodes within each branch of the set of branches based on a distance between the second position and each subdivided region of the 3D environment represented by each subtree node of the set of subtree nodes, wherein said rearranging changes the first subtree node in the particular branch from a subtree node representing a first subdivided region that is closest to the particular position to another subtree node representing a second subdivided region that is closest to the second position.

5. The method of claim 1 , wherein accessing the data comprises:

loading data that is stored for the subdivided region represented by the first subtree node into a computer memory.

6. The method of claim 1 , wherein traversing from the root node to a particular branch of the set of branches comprises:

selecting a first branch of the set of branches in response to the distance between the position of the root node and the particular position being a first distance; and

selecting a second branch of the set of branches in response to the distance between the position of the root node and the particular position being a second distance that is outside the set of subdivided regions represented by the first branch.

7. The method of claim 1 further comprising:

linking the set of branches to each other;

receiving a second request to access data from a second position in the 3D environment that is different than the particular position; and

traversing from the particular branch to a different second branch of the set of branches without accessing the root node in response to linking the set of branches and the second position being a second distance from the position of the root node that is encompassed by the set of subdivided regions represented by the different second branch.

8. The method of claim 1 further comprising:

generating a tree-based representation for data contained in each subdivided region of the set of subdivided regions of the particular branch; and

associating the tree-based representation for the data contained in each subdivided region of the set of subdivided regions of the particular branch to a subtree node that represents that subdivided region in the particular branch.

9. The method of claim 1 ,

wherein the 3D environment is defined as a point cloud, and

wherein each subdivided region includes a different set of data points that form the point cloud.

10. The method of claim 1 ,

wherein the 3D environment is defined with a plurality of constructs distributed across a 3D space, and

wherein each subdivided region includes a different set of the plurality of constructs.

11. The method of claim 1 further comprising:

partitioning the 3D environment into a plurality of subdivided regions that extend around the position of the root node, wherein the position of the root node is at a center of the plurality of subdivided regions; and

selecting each set of subdivided regions for each branch of the set of branches based on a distance of the plurality of subdivided regions from the position of the root node.

12. The method of claim 1 further comprising:

determining a center of mass within the 3D environment; and

setting the position of the root node at the center of mass.

13. The method of claim 1 further comprising:

determining a center of the 3D environment; and

setting the position of the root node at the center of the 3D environment.

14. An editing system comprising:

one or more hardware processors configured to:

receive a tree-based representation of a three-dimensional (“3D”) environment, the tree-based representation comprising a root node with a position defined in the 3D environment, and a set of branches that are linked to the root node, wherein each branch of the set of branches comprises a set of subtree nodes representing a set of subdivided regions of the 3D environment that are a same distance from the position of the root node, and wherein the set of subtree nodes from different branches of the set of branches represent subdivided regions of the 3D environment that are a different distance from the position of the root node;

receive a request to access data from a particular position in the 3D environment;

sort the set of subtree nodes within each branch of the set of branches based on a distance between the particular position and each subdivided region of the 3D environment represented by each subtree node of the set of subtree nodes;

compute a distance between the position of the root node and the particular position; and

access the data associated with the particular position by traversing from the root node to a particular branch of the set of branches based on the distance between the position of the root node and the particular position being within the set of subdivided regions represented by the set of subtree nodes of the particular branch, and by selecting a first subtree node in the set of subtree nodes of the particular branch that represents a subdivided region from the set of subdivided regions of the particular branch that is closest to the particular position after said sorting.

15. The editing system of claim 14 , wherein accessing the data comprises:

retrieving a tree-based representation of the data contained within the subdivided region represented by the first subtree node of the particular branch.

16. The editing system of claim 15 , wherein accessing the data further comprises:

selecting a subset of nodes from a plurality of nodes of the tree-based representation of the data contained within the subdivided region, wherein the plurality of nodes store all data contained within the subdivided region, and wherein the subset of nodes store a subset of data associated with the particular position specified in the request.

17. The editing system of claim 14 , wherein the one or more hardware processors are further configured to:

receive a second request to access data from a second position in the 3D environment that is different than the particular position; and

rearrange the set of subtree nodes within each branch of the set of branches based on a distance between the second position and each subdivided region of the 3D environment represented by each subtree node of the set of subtree nodes, wherein said rearranging changes the first subtree node in the particular branch from a subtree node representing a first subdivided region that is closest to the particular position to another subtree node representing a second subdivided region that is closest to the second position.

18. The editing system of claim 14 , wherein traversing from the root node to a particular branch of the set of branches comprises:

selecting a first branch of the set of branches in response to the distance between the position of the root node and the particular position being a first distance; and

selecting a second branch of the set of branches in response to the distance between the position of the root node and the particular position being a second distance that is outside the set of subdivided regions represented by the first branch.

19. The editing system of claim 14 , wherein the one or more hardware processors are further configured to:

generate a tree-based representation for data contained in each subdivided region of the set of subdivided regions of the particular branch; and

associate the tree-based representation for the data contained in each subdivided region of the set of subdivided regions of the particular branch to a subtree node that represents that subdivided region in the particular branch.

20. A non-transitory computer-readable medium storing program instructions that, when executed by one or more hardware processors of an editing system, cause the editing system to perform operations comprising:

receive a tree-based representation of a three-dimensional (“3D”) environment, the tree-based representation comprising a root node with a position defined in the 3D environment, and a set of branches that are linked to the root node, wherein each branch of the set of branches comprises a set of subtree nodes representing a set of subdivided regions of the 3D environment that are a same distance from the position of the root node, and wherein the set of subtree nodes from different branches of the set of branches represent subdivided regions of the 3D environment that are a different distance from the position of the root node;

receive a request to access data from a particular position in the 3D environment;

sort the set of subtree nodes within each branch of the set of branches based on a distance between the particular position and each subdivided region of the 3D environment represented by each subtree node of the set of subtree nodes;

compute a distance between the position of the root node and the particular position; and

access the data associated with the particular position by traversing from the root node to a particular branch of the set of branches based on the distance between the position of the root node and the particular position being within the set of subdivided regions represented by the set of subtree nodes of the particular branch, and by selecting a first subtree node in the set of subtree nodes of the particular branch that represents a subdivided region from the set of subdivided regions of the particular branch that is closest to the particular position after said sorting.