POINT CLOUD DATA HIERARCHY

• US 20130265299A1
• Filed: 03/07/2013
• Published: 10/10/2013
• Est. Priority Date: 03/07/2012
• Status: Abandoned Application

• Current Assignee: Willow Garage, Inc.
• Original Assignee: Willow Garage, Inc.
• Inventors: Marder-Eppstein, Eitan, Glaser, Stuart, Meeussen, Wim
• Application Number:
  US13/789,554
• Publication Number:
  US 20130265299A1
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2210/36 Level of detail
• CPC Class Codes: G06T 2210/56 Particle system, point based geometry or rendering

Abstract

One method embodiment comprises storing data on a storage system that is representative of a point cloud comprising a very large number of associated points; organizing the data into an octree hierarchy of data sectors, each of which is representative of one or more of the points at a given octree mesh resolution; receiving a command from a user of a user interface to present an image based at least in part upon a selected viewing perspective origin and vector; and assembling the image based at least in part upon the selected origin and vector, the image comprising a plurality of data sectors pulled from the octree hierarchy, the plurality of data sectors being assembled such that sectors representative of points closer to the selected viewing origin have a higher octree mesh resolution than that of sectors representative of points farther away from the selected viewing origin.

Claims

1. A method for presenting multi-resolution views of a very large point data set, comprising:

a. storing data on a storage system that is representative of a point cloud comprising a very large number of associated points;

b. organizing the data into an octree hierarchy of data sectors, each of which is representative of one or more of the points at a given octree mesh resolution;

c. receiving a command from a user of a user interface to present an image based at least in part upon a selected viewing perspective origin and vector; and

d. assembling the image based at least in part upon the selected origin and vector, the image comprising a plurality of data sectors pulled from the octree hierarchy, the plurality of data sectors being assembled such that sectors representative of points closer to the selected viewing origin have a higher octree mesh resolution than that of sectors representative of points farther away from the selected viewing origin.

2. The method of claim 1, wherein storing comprises accessing a storage cluster.

3. The method of claim 1, further comprising using a network to intercouple the storage system, controller, and user interface.

4. The method of claim 3, wherein at least one portion of the network is accessible to the internet.

5. The method of claim 1, further comprising generating the user interface with a computing system that houses the controller.

6. The method of claim 1, further comprising presenting the user interface to the user within a web browser.

7. The method of claim 1, wherein the user interface is configured such that the user may adjust the selected origin and vector using an input device, causing the controller to assemble a new image based at least in part upon the adjusted origin and vector.

8. The method of claim 1, wherein the very large number of associated points is greater than 1 billion points.

9. The method of claim 1, wherein the point cloud has a uniform point pitch.

10. The method of claim 1, wherein the point cloud has a point pitch that is less than about one meter.

11. The method of claim 10, wherein the point cloud has a point pitch that is less than about 1 centimeter.

12. The method of claim 1, wherein the point cloud represents data that has been collected based upon distance measurement scans of objects.

13. The method of claim 12, wherein the point cloud represents at least one LIDAR scan.

14. The method of claim 1, wherein the octree hierarchy of data sectors is configured such that an N level sector represents a centroid of points at the N+1 level below.

15. The method of claim 14, wherein each point is weighted equally in determining the centroid.

16. The method of claim 14, wherein the points comprising the point cloud are not all weighted equally in determining the centroid.

17. The method of claim 1, further comprising using the controller to store data sectors of similar octree mesh resolution in similar accessibility configurations on the storage system.

18. The method of claim 17, wherein the controller is configured to store data sectors of similar octree mesh resolution on a common storage device.

19. The method of claim 17, wherein the controller is configured to store data sectors of similar octree mesh resolution such that they have similar retrieval latencies from the storage system.

20. The method of claim 1, wherein the image comprises a gradient of octree mesh resolution data sectors in a direction outward from the selected viewing origin.