Systems and methods for editing, animating, and processing point clouds using bounding volume hierarchies

1. A method comprising:

receiving a point cloud comprising a plurality of data points that are distributed non-uniformly in a three-dimensional (“3D”) space, the plurality of data points generating a first frame of an animation with each particular data point of the plurality of data points comprising a plurality of elements that define a position and visual characteristics of the particular data point in the 3D space;

generating a tree representation of the point cloud, the tree representation comprising a plurality of leaf nodes and a plurality of branches that connect two or more leaf nodes directly or indirectly to parent nodes at one or more levels above the plurality of leaf nodes, wherein the plurality of leaf nodes correspond to the plurality of data points;

detecting a set of the plurality of data points that change between the first frame and a second frame of the animation;

determining a particular branch from the plurality of branches that directly or indirectly connects to a set of leaf nodes that correspond to the set of data points that change between the first frame and a second frame of the animation;

generating a replacement branch for the particular branch, the replacement branch comprising a set of replacement leaf nodes that capture the change between the first frame and the second frame; and

encoding the first frame and the second frame of the animation with the tree representation and the particular replacement branch.

2. The method of claim 1 further comprising:

linking the replacement branch to a particular parent node of the tree representation that is a root node of the particular branch.

3. The method of claim 1 , wherein encoding the first frame and the second frame comprises:

associating the replacement branch to the second frame of the animation.

4. The method of claim 1 further comprising:

receiving a second point cloud comprising all data points within the second frame of the animation;

comparing the second point cloud to the point cloud generating the first frame of the animation; and

wherein encoding the first frame and the second frame comprises:

storing the tree representation with the plurality of leaf nodes that correspond to the plurality of data points; and

storing the replacement branch with the set of replacement leaf nodes instead of the second point cloud and all data points within the second frame.

5. The method of claim 1 , wherein the replacement branch comprises a root node, a set of branches that extend one or more levels below the root node via a subset of parent nodes and that terminate at the set of replacement leaf nodes, wherein the set of replacement leaf nodes correspond to one or more point cloud data points that animate the change between the first frame and the second frame.

6. The method of claim 1 further comprising:

rendering the plurality of data points;

presenting the first frame of the animation in response to rendering the plurality of data points;

rendering data points that correspond to the set of replacement leaf nodes from the replacement branch;

replacing one or more regions of the first frame in response to rendering the data points that correspond to the set of replacement leaf nodes; and

presenting the second frame of the animation after replacing the one or more regions of the first frame.

7. The method of claim 1 ,

wherein detecting the set of data points comprises determining a region of the first frame that changes between the first frame and the second frame and that encompasses the set of data points;

wherein determining the particular branch comprises selecting a particular parent node of the tree representation with a set of branches to leaf nodes that correspond to the set of data points in the region; and

wherein encoding the first frame and the second frame comprises linking the replacement branch to the particular parent node.

8. The method of claim 1 , wherein encoding the first frame and the second frame comprises:

associating a first identifier for the first frame to the tree representation; and

associating a second identifier for the second frame to the replacement branch.

9. The method of claim 1 further comprising:

receiving a request to render the animation;

retrieving the tree representation and the replacement branch in response to the request;

generating the first frame of the animation based on values defined for the plurality of elements of the plurality of data points represented by the plurality of leaf nodes of the tree representation; and

generating the second frame of the animation based on values defined for the plurality of elements of data points represented by the set of replacement leaf nodes of the replacement branch.

10. The method of claim 1 further comprising:

generating the first frame of the animation based on the plurality of elements of the plurality of data points represented by the plurality of leaf nodes of the tree representation; and

updating parts of the first frame that were generated based on the plurality of elements of the set of data points with the plurality of elements of data points represented by the set of replacement leaf nodes of the replacement branch.

11. The method of claim 1 further comprising:

rendering the first frame of the animation based on the plurality of leaf nodes of the tree representation;

replace the particular branch of the tree representation with the replacement branch; and

rendering the second frame of the animation based on the set of replacement leaf nodes replacing the set of leaf nodes as a result of replacing the particular branch with the replacement branch.

12. The method of claim 1 , wherein the tree representation corresponds to one of a binary tree, an octree, and a k-d tree.

13. The method of claim 1 , wherein the plurality of branches organize the plurality of leaf nodes according to positional values of the plurality of data points with each branch of the plurality of branches corresponding to a different region of the first frame.

14. A system comprising:

one or more hardware processors configured to:

receive a point cloud comprising a plurality of data points that are distributed non-uniformly in a three-dimensional (“3D”) space, the plurality of data points generating a first frame of an animation with each particular data point of the plurality of data points comprising a plurality of elements that define a position and visual characteristics of the particular data point in the 3D space;

generate a tree representation of the point cloud, the tree representation comprising a plurality of leaf nodes and a plurality of branches that connect two or more leaf nodes directly or indirectly to parent nodes at one or more levels above the plurality of leaf nodes, wherein the plurality of leaf nodes correspond to the plurality of data points;

detect a set of the plurality of data points that change between the first frame and a second frame of the animation;

determine a particular branch from the plurality of branches that directly or indirectly connects to a set of leaf nodes that correspond to the set of data points that change between the first frame and a second frame of the animation;

generate a replacement branch for the particular branch, the replacement branch comprising a set of replacement leaf nodes that capture the change between the first frame and the second frame; and

encode the first frame and the second frame of the animation with the tree representation and the particular replacement branch.

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

link the replacement branch to a particular parent node of the tree representation that is a root node of the particular branch.

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

receive a second point cloud comprising all data points within the second frame of the animation;

compare the second point cloud to the point cloud generating the first frame of the animation; and

wherein encoding the first frame and the second frame comprises:

storing the tree representation with the plurality of leaf nodes that correspond to the plurality of data points; and

storing the replacement branch with the set of replacement leaf nodes instead of the second point cloud and all data points within the second frame.

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

render the plurality of data points;

present the first frame of the animation in response to rendering the plurality of data points;

render data points that correspond to the set of replacement leaf nodes from the replacement branch;

replace one or more regions of the first frame in response to rendering the data points that correspond to the set of replacement leaf nodes; and

present the second frame of the animation after replacing the one or more regions of the first frame.

18. The system of claim 14 , wherein encoding the first frame and the second frame comprises:

associating a first identifier for the first frame to the tree representation; and

associating a second identifier for the second frame to the replacement branch.

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

receive a request to render the animation;

retrieve the tree representation and the replacement branch in response to the request;

generate the first frame of the animation based on values defined for the plurality of elements of the plurality of data points represented by the plurality of leaf nodes of the tree representation; and

generate the second frame of the animation based on values defined for the plurality of elements of data points represented by the set of replacement leaf nodes of the replacement branch.

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

receive a point cloud comprising a plurality of data points that are distributed non-uniformly in a three-dimensional (“3D”) space, the plurality of data points generating a first frame of an animation with each particular data point of the plurality of data points comprising a plurality of elements that define a position and visual characteristics of the particular data point in the 3D space;

generate a tree representation of the point cloud, the tree representation comprising a plurality of leaf nodes and a plurality of branches that connect two or more leaf nodes directly or indirectly to parent nodes at one or more levels above the plurality of leaf nodes, wherein the plurality of leaf nodes correspond to the plurality of data points;

detect a set of the plurality of data points that change between the first frame and a second frame of the animation;

determine a particular branch from the plurality of branches that directly or indirectly connects to a set of leaf nodes that correspond to the set of data points that change between the first frame and a second frame of the animation;

generate a replacement branch for the particular branch, the replacement branch comprising a set of replacement leaf nodes that capture the change between the first frame and the second frame; and

encode the first frame and the second frame of the animation with the tree representation and the particular replacement branch.