# US 12,008,713 B2 · Point cloud data hierarchy > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,008,713 B2 - Document ID: US12008713B2 - Status: Granted - Kind: B2 - Application number: 18/299,642 - Filed: 2023-04-12 - Published: 2023-08-10 - Granted: 2024-06-11 - Earliest claimed: 2012-03-07 - Assignees: Willow Garage, LLC - Applicants: Willow Garage, LLC - Inventors: Eitan Marder-Eppstein; Stuart Glaser; Wim Meeussen - Web page: https://patentgrep.com/patent/US12008713B2 ## CPC - G06T 17/005: {Tree description, e.g. octree, quadtree} - G06T 15/10: Geometric effects - G06T 15/20: Perspective computation - G06T 2207/10028: Range image; Depth image; 3D point clouds - G06T 2210/36: Level of detail - G06T 2210/56: Particle system, point based geometry or rendering - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## 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 ### Claim 1 A method for presenting multi-resolution views of a point data set, comprising: receiving a selection from a user of a user interface to present an image based at least in part upon a viewing perspective origin of the frustum, a vector of the frustum originating at the origin of the frustum and a field of view of the frustum; storing data on a storage system that is representative of a point cloud comprising a number of associated points; storing a resolution gradient on the storage system; octree mesh resolution data sectors on the storage system; 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; retrieving the resolution gradient and the octree mesh resolution data sectors from the storage system, wherein through the selection using the user interface of the origin and vector originating at the origin, the image is assembled to include 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 along the vector, wherein the image is based on the resolution gradient retrieved from the storage system and the resolution gradient is selected to form a first gradient with a descending resolution in a direction outward from the selected viewing perspective origin along the vector; and tuning, by an operator, the resolution gradient between at least two of (i) to have linear change in resolution from back to front, (ii) to be nonlinear and (iii) to be stepwise at certain distance thresholds. ### Claim 2 (depends on 1) The method of claim 1, wherein the resolution gradient has linear change in resolution from back to front. ### Claim 3 (depends on 1) The method of claim 1, wherein the resolution gradient is nonlinear change in resolution from back to front. ### Claim 4 (depends on 3) The method of claim 3, wherein the resolution gradient is stepwise at certain distance thresholds. ### Claim 5 (depends on 1) The method of claim 1, wherein the resolution gradient is tunable by an operator based upon at least one of (i) computing resources and (ii) bandwidth resources. ### Claim 6 (depends on 1) The method of claim 1, further comprising presenting the user interface to the user within a web browser. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) The method of claim 1, wherein the number of associated points is greater than 1 billion points. ### Claim 9 (depends on 1) The method of claim 1, wherein the point cloud has a uniform point pitch. ### Claim 10 (depends on 1) The method of claim 1, wherein the point cloud has a point pitch that is less than about one meter. ### Claim 11 (depends on 10) The method of claim 10, wherein the point cloud has a point pitch that is less than about 1 centimeter. ### Claim 12 (depends on 1) The method of claim 1, wherein the point cloud represents data that has been collected based upon distance measurement scans of objects. ### Claim 13 (depends on 12) The method of claim 12, wherein the point cloud represents at least one LIDAR scan. ### Claim 14 (depends on 1) 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. ### Claim 15 (depends on 14) The method of claim 14, wherein each point is weighted equally in determining the centroid. ### Claim 16 (depends on 14) The method of claim 14, wherein the points comprising the point cloud are not all weighted equally in determining the centroid. ### Claim 17 (depends on 1) 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. ### Claim 18 (depends on 17) The method of claim 17, wherein the controller is configured to store data sectors of similar octree mesh resolution on a common storage device. ### Claim 19 (depends on 1) The method of claim 1, wherein the data sectors have different mesh resolution levels wherein data sectors of similar octree mesh resolution are stored such that they have similar retrieval latencies from the storage system and wherein data sectors of different octree mesh resolution are stored such that they have different retrieval latencies from the storage system.