Systems and methods for converting massive point cloud datasets to a hierarchical storage format

• US 10,438,092 B2
• Filed: 10/22/2018
• Issued: 10/08/2019
• Est. Priority Date: 01/31/2018
• Status: Active Grant

• Current Assignee: Cesium GS, Inc.
• Original Assignee: Analytical Graphics
• Inventors: Lilley, Sean, Li, Kangning, Mohammed, Zakiuddin, Cozzi, Patrick, Lawrence, Joshua
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Cheung, Hubert
• Application Number:
  US16/167,422
• Publication Number:
  US 20190236403A1
• Time in Patent Office: 351 Days
• CPC Class Codes: G06F 12/0848 Partitioned cache, e.g. separate instruction and operand caches
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/0873 Mapping of cache memory to specific storage devices or parts thereof
• CPC Class Codes: G06F 16/185 Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof details of archiving G06F16/11
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06F 18/2451 linear, e.g. hyperplane
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/454 Vector or matrix data
• CPC Class Codes: G06F 2212/455 Image or video data
• CPC Class Codes: G06F 9/28 Enhancement of operational speed, e.g. by using several microcontrol devices operating in parallel
• CPC Class Codes: G06V 10/7625 Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms

Abstract

Methods and systems for converting a point cloud dataset into a hierarchical data structure for a lossless representation of an input file are provided herein. In various embodiments the method comprises recursing subtrees using a preordered traversal for a plurality of nodes, the preordered traversal being checking a parent node and then checking children nodes and stopping the recursing of the subtrees using the preordered traversal of the plurality of nodes when a node of the plurality of nodes is a below threshold node. The below threshold node being less than a configuration specified maximum number of data points, the below threshold node being a leaf of a tileset. Further comprising, aggregating the leaf of the tileset into a lossless representation of the collection of input files.

Claims

1. A method for converting a point cloud dataset into a hierarchical data structure for a lossless representation of an input file, the method comprising:

reading header information of a collection of input files, the reading of the header information determining an axis-aligned bounding box of the collection of input files and a total number of data points in the point cloud dataset, the axis-aligned bounding box representing the amount of space taken by the point cloud dataset;

determining a cache level of the total number of data points in the point cloud dataset to generate a plurality of caches, based on the total number of data points and the axis-aligned bounding box of the point cloud dataset, the cache level being a level of program memory to fit all of the total number of data points in the point cloud dataset;

subdividing each of the plurality of caches into subtrees based on the determining of the cache level of the total number of data points in the point cloud dataset, the subtrees having a plurality of nodes; and

generating a tileset based on sorting of the plurality of nodes in the subtrees, the generating of the tileset resulting in the hierarchical data structure comprising a root tile and a plurality of children.

2. The method of claim 1, further comprising:

reading the total number of data points in the point cloud dataset to produce a plurality of input points; and

inserting the plurality of input points into the plurality of caches, the inserting the plurality of input points into the plurality of caches comprising;

projecting the total number of data points in the point cloud dataset to a coordinate system; and

writing the total number of data points in the point cloud dataset to cache.

3. The method of claim 2, wherein the writing of the total number of data points in the point cloud dataset to the cache is multithreaded resulting in the collection of input files being processed in parallel.

4. The method of claim 2, wherein the inserting of the plurality of input points into the plurality of caches is based on a position check, the position check comprising:

appending the plurality of input points to a cache buffer; and

writing an input point of the plurality of input points in the cache buffer to disk when the cache buffer exceeds a memory threshold for the input point.

5. The method of claim 2, further comprising sorting unordered points of the plurality of input points into a spatially ordered linear array.

6. The method of claim 1, further comprising reading the plurality of caches from disk into program memory.

7. The method of claim 1, further comprising:

recursing the subtrees using a preordered traversal for the plurality of nodes, the preordered traversal being checking a parent node and then checking children nodes.

8. The method of claim 7, further comprising:

stopping the recursing of the subtrees using the preordered traversal of the plurality of nodes when a node of the plurality of nodes is a below threshold node, the below threshold node being less data points than a configuration specified maximum number of data points;

wherein the below threshold node is a leaf of the tileset.

9. The method of claim 8, further comprising:

aggregating the leaf of the tileset into a lossless representation of the collection of input files.

10. The method of claim 7, further comprising:

continuing the recursing of the subtrees using the preordered traversal of the plurality of nodes when a node of the plurality of nodes is an above threshold node, the above threshold node being more data points than a configuration specified maximum number of data points.

11. The method of claim 10, further comprising:

sampling the children nodes of the above threshold node resulting in a representative point collection for the above threshold node, the representative point collection being a lower level of detail of the above threshold node.

12. The method of claim 11, wherein the sampling of the children nodes of the above threshold node comprises at least one or more of:

filtering data point outliers, preserving data point edges, and establishing minimum distances between data points.

13. The method of claim 11, further comprising:

writing the representative point collection to disk resulting in an interior tile of the tileset.

14. The method of claim 13, further comprising:

aggregating the interior tile of the tileset into a lossless representation of the collection of input files.

15. The method of claim 1, wherein the hierarchical data structure comprises an octree.

16. The method of claim 15, wherein the method further comprises:

building the octree where at each level, a different level of detail of the point cloud dataset is provided;

reading each of the data points in the point cloud dataset to determine to which cache each data point belongs, such that a data point position of a given data point is checked against bounding volumes of nodes at that cache level;

inserting each of the data points in the point cloud dataset into their respective caches, based upon the reading of each of the data points; and

writing cache buffers to disk even if the cache buffers are not full.

17. A method for converting a point cloud dataset into a hierarchical data structure for a lossless representation of an input file, the method comprising:

reading header information of a collection of input files, the reading of the header information determining an overall bounding box of the collection of input files and a total number of data points in the point cloud dataset;

determining a cache level of the total number of data points in the point cloud dataset to generate a plurality of caches, the cache level being a level of program memory to fit all of the total number of data points in the point cloud dataset;

subdividing each of the plurality of caches into subtrees based on the determining of the cache level of the total number of data points in the point cloud dataset, the subtrees having a plurality of nodes;

recursing the subtrees using a preordered traversal for the plurality of nodes, the preordered traversal being checking a parent node and then checking children nodes;

stopping the recursing of the subtrees using the preordered traversal of the plurality of nodes when a node of the plurality of nodes is a below threshold node, the below threshold node being less data points than a configuration specified maximum number of data points and the below threshold node being a leaf of a tileset; and

generating the tileset based on sorting of the plurality of nodes in the subtrees, the generating of the tileset resulting in the hierarchical data structure comprising a root tile and a plurality of children.

18. The method of claim 17, further comprising:

aggregating the leaf of the tileset into a lossless representation of the collection of input files.

19. A method for converting a point cloud dataset into a hierarchical data structure for a lossless representation of an input file, the method comprising:

reading header information of a collection of input files, the reading of the header information determining an overall bounding box of the collection of input files and a total number of data points in the point cloud dataset;

determining a cache level of the total number of data points in the point cloud dataset to generate a plurality of caches, the cache level being a level of program memory to fit all of the total number of data points in the point cloud dataset;

subdividing each of the plurality of caches into subtrees based on the determining of the cache level of the total number of data points in the point cloud dataset, the subtrees having a plurality of nodes;

recursing the subtrees using a preordered traversal for the plurality of nodes, the preordered traversal being checking a parent node and then checking children nodes;

continuing the recursing of the subtrees using the preordered traversal of the plurality of nodes when a node of the plurality of nodes is an above threshold node, the above threshold node being more data points than a configuration specified maximum number of data points;

sampling the children nodes of the above threshold node resulting in a representative point collection for the above threshold node, the representative point collection being a lower level of detail of the above threshold node; and

generating a tileset based on sorting of the plurality of nodes in the subtrees, the generating of the tileset resulting in the hierarchical data structure comprising a root tile and a plurality of children.

20. The method of claim 19, wherein the sampling of the children nodes of the above threshold node comprises at least one or more of:

filtering data point outliers, preserving data point edges, and establishing minimum distances between data points.

21. The method of claim 19, further comprising:

writing the representative point collection to disk resulting in an interior tile of the tileset.

22. The method of claim 21, further comprising:

aggregating the interior tile of the tileset into a lossless representation of the collection of input files.