# US 12,008,714 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,714 B2
- Document ID: US12008714B2
- Status: Granted
- Kind: B2
- Application number: 18/300,277
- Filed: 2023-04-13
- Published: 2023-08-10
- Granted: 2024-06-11
- Earliest claimed: 2012-03-07
- Assignees: Willow Garage, LLC
- Applicants: Willow Garage, LLC
- Inventors: Stuart Glaser; Wim Meeussen; Eitan Marder-Eppstein
- Web page: https://patentgrep.com/patent/US12008714B2

## CPC

- G06T 17/005: {Tree description, e.g. octree, quadtree}
- G06F 3/0482: Interaction with lists of selectable items, e.g. menus
- G06F 3/04842: Selection of displayed objects or displayed text elements (G06F3/0482 takes precedence)
- G06F 3/04845: for image manipulation, e.g. dragging, rotation, expansion or change of colour
- G06F 3/04847: Interaction techniques to control parameter settings, e.g. interaction with sliders or dials
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/26: Visual data mining; Browsing structured data
- G06F 16/282: {Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes}
- G06F 16/287: {Visualization; Browsing}
- G06T 17/05: Geographic models
- G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation}
- G06T 15/20: Perspective computation
- G06T 2207/10028: Range image; Depth image; 3D point clouds
- G06T 2210/56: Particle system, point based geometry or rendering
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

One embodiment is directed to a system for presenting views of a very large point data set, comprising: a storage system comprising data representing a point cloud comprising a very large number of associated points; a controller operatively coupled to the storage cluster and configured to automatically and deterministically organize the point 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; and a user interface through which a user may select a viewing perspective origin and vector, which may be utilized to command the controller to assemble an 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.

## Claims

### Claim 1

A system for presenting views of a point cloud data set, comprising:
a user interface through which a user selects a viewing perspective origin of a frustum, a vector of the frustum originating at the origin of the frustum, and a field of view of the frustum;
a storage system;
the point cloud data set comprising a number of associated points stored on the storage system;
a resolution gradient on the storage system;
octree mesh resolution data sectors on the storage system;
a controller operatively coupled to a storage cluster and configured to organize the point cloud data set into an octree hierarchy of data sectors, wherein each of the data sectors of the octree hierarchy of data sectors comprise, at a given octree mesh resolution, one or more points of the number of associated points;
a retrieval system connected to the storage system to retrieve the resolution gradient and the octree mesh resolution data sectors, wherein based on the viewing perspective origin of the frustum and the vector of the frustum selected using the user interface, the retrieval system retrieves an image that is assembled to include a plurality of data sectors pulled from the octree hierarchy of data sectors, 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 permit tuning, by the user, the resolution gradient between at least two of (i) a linear change in resolution from back to front, (ii) a nonlinear change in resolution from back to front (iii) a stepwise at certain distance thresholds.

### Claim 2 (depends on 1)

The system of claim 1, wherein the resolution gradient has the linear change in resolution from back to front.

### Claim 3 (depends on 1)

The system of claim 1, wherein the resolution gradient has the nonlinear change in resolution from back to front.

### Claim 4 (depends on 3)

The system of claim 3, wherein the resolution gradient has the stepwise at certain distance thresholds.

### Claim 5 (depends on 1)

The system of claim 1, wherein the resolution gradient is tunable by a user based upon at least one of (i) computing resources and (ii) bandwidth resources.

### Claim 6 (depends on 1)

The system of claim 1, wherein the user interface is presented to the user within a web browser.

### Claim 7 (depends on 1)

The system of claim 1, wherein the user interface is configured such that the user adjusts 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 system of claim 1, wherein the number of associated points is greater than 1 billion points.

### Claim 9 (depends on 1)

The system of claim 1, wherein the point cloud data set has a uniform point pitch.

### Claim 10 (depends on 1)

The system of claim 1, wherein the point cloud data set has a point pitch that is less than one meter.

### Claim 11 (depends on 10)

The system of claim 10, wherein the point cloud data set has a point pitch that is less than 1 centimeter.

### Claim 12 (depends on 1)

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

### Claim 13 (depends on 12)

The system of claim 12, wherein the point cloud data set represents at least one LIDAR scan.

### Claim 14 (depends on 1)

The system 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 system of claim 14, wherein each point of the centroid of points is weighted equally in determining the centroid of points.

### Claim 16 (depends on 14)

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

### Claim 17 (depends on 1)

The system of claim 1, wherein the controller is configured to store the data sectors of the octree mesh resolution data sectors with same octree mesh resolution in same accessibility configurations using the storage system.

### Claim 18 (depends on 17)

The system of claim 17, wherein the controller is configured to store the data sectors of the octree mesh resolution data sectors with the same octree mesh resolution on a common storage device.

### Claim 19 (depends on 1)

The system of claim 1, wherein the each of the data sectors of the octree mesh resolution data sectors with same octree mesh resolution are stored such that they have same retrieval latency from the storage system and wherein the each of the data sectors of the octree mesh resolutions of data sectors with different octree mesh resolutions are stored such that they have different retrieval latencies from the storage system.

### Claim 20 (depends on 1)

The system of claim 1, wherein the controller is configured to deterministically organize the point cloud data set into the octree hierarchy of data sectors by automatically naming the each of the data sectors in the octree hierarchy of data sectors with a uniquely identifiable name that is retrievable by the controller.