System and method for efficient storage and manipulation of extremely large amounts of scan data

• US 20050203930A1
• Filed: 03/09/2005
• Published: 09/15/2005
• Est. Priority Date: 03/10/2004
• Status: Active Grant

• Current Assignee: Leica Geosystems AG (Hexagon AB)
• Original Assignee: Leica Geosystems AG (Hexagon AB)
• Inventors: Wheeler, Mark Damon, Bukowski, Richard William, Kung, Jonathan Apollo, Downs, Laura Michele
• Granted Patent: US 7,373,473 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

Large data sets can be stored and processed in real time by combining and registering the large data sets into a single data set. The data can be stored in a data tree structure formed of layers of spatially organized blocks of data. Such storage allows portions of the data to be viewed efficiently, displaying actual point data at an acceptable resolution for the viewing mechanism. Density limited queries can be executed that allow sub-sampling to be done directly and evenly without geometric constraint, to provide a subset of points that is limited in size and includes a spatially-even decomposition of that set of points. This allows the system as a whole to support arbitrarily large point sets while allowing full partitioning functionality, which is efficient to use in both time and space.

Claims

1. A method of organizing and storing point data, comprising the steps of:

obtaining a set of related point data;

sorting the related point data by at least one of spatial density and region of space;

partitioning the sorted point data into separately addressable blocks of data;

organizing the separately addressable blocks by at least one of spatial density and region of space; and

stitching related separately addressable blocks together to form a single global data tree.

2. A method according to claim 1, further comprising:

storing the set of related point data to an external storage medium, whereby the related point data can be sorted from the external storage medium.

3. A method according to claim 1, further comprising:

writing the separately addressable blocks to a database.

4. A method according to claim 1, wherein:

sorting the related point data includes writing the point data to a linear array.

5. A method according to claim 4, further comprising:

allocating an organizational array to contain organizational structure information for the respective linear array.

6. A method according to claim 5, wherein:

the organizational array organizes the set of related point data by at least one of spatial density and region of space.

7. A method according to claim 5, wherein:

partitioning the sorted point data into separately addressable blocks of data uses the organizational structure information partition the linear array into blocks.

8. A method according to claim 1, further comprising:

organizing each separately addressable block by at least one of spatial density and region of space.

9. A method according to claim 1, wherein:

at least one of the sorting, partitioning, organizing, and stitching steps can be executed at least partially during the step of obtaining the set of related point data.

10. A method according to claim 1, wherein:

obtaining a set of related point data includes taking a scan of a physical object.

11. A method according to claim 1, further comprising:

obtaining auxiliary information for the set of related point data.

12. A method according to claim 11, further comprising:

associating at least one auxiliary data field with each data point in the set of related point data.

13. A method according to claim 12, further comprising:

maintaining the association between each at least one auxiliary data field and the respective data point until the data tree is formed.

14. A method according to claim 13, further comprising:

writing the separately addressable blocks to a database to form a single queryable instance of a data structure for the point data with auxiliary data.

15. A method according to claim 14, wherein:

the single queryable instance is formed regardless of the size of the set of point data.

18. A method according to claim 1, wherein:

the subset represents a spatial downsampling of the set of related point data over the specified spatial area.

16. A method of querying a point data set consisting of a global data tree of separately addressable blocks, comprising the steps of:

specifying a spatial area of the point data set;

specifying a maximum number of data points to be returned;

specifying whether to return auxiliary data associated with points in the data set; and

receiving a subset of the point data set corresponding to the spatial area, the subset having a number of points at most equal to the maximum number, the subset further including any specified per-point auxiliary data corresponding to data points in the subset.

17. A method according to claim 16, further comprising:

specifying a maximum resolution, such that the subset will include data points of a density at most equal to the maximum resolution.

19. A method of querying a point data set, comprising the steps of:

allowing a user to specify a spatial area of the point data set;

allowing a user to specify a maximum number of data points to be returned;

allowing a user to specify whether to return auxiliary data associated with points in the data set;

formulating a query based on the spatial area, maximum number, and auxiliary data specification and running that query against a database;

receiving from the database a subset of the point data set corresponding to the spatial area, the subset having a number of points at most equal to the maximum number, the subset further including any per-point auxiliary data corresponding to data points in the subset; and

at least one of displaying the subset and writing the subset to a database.

20. A method of registering multiple data sets, comprising the steps of:

obtaining a plurality of data sets, each data set including separately addressable blocks stitched together to form a single data tree;

running a series of queries against the plurality of data sets, each query specifying a spatial area and maximum number of points;

using results from the series of queries to relate the data sets together; and

organizing the related data sets to form a single global data tree.

21. A method according to claim 20, wherein:

obtaining a plurality of data sets includes obtaining a set of related point data for each data set, sorting the related point data by at least one of spatial density and region of space, partitioning the sorted point data into separately addressable blocks of data, organizing the separately addressable blocks by at least one of spatial density and region of space, and stitching related separately addressable blocks together to form a single data tree.

22. A method according to claim 20, wherein:

organizing the related data sets includes sorting point data in the related data sets by at least one of spatial density and region of space, partitioning the sorted point data into separately addressable blocks of data, organizing the separately addressable blocks by at least one of spatial density and region of space, and stitching related separately addressable blocks together to form a single global data tree.

23. A method according to claim 20, wherein:

using results from the series of queries to relate the data sets together produces a single registered set of data.

24. A method according to claim 20, wherein:

obtaining the plurality of related data sets includes taking a plurality of scans of a physical object, each scan corresponding to a related data set.

25. A memory for storing data for access by an application program being executed on a data processing system, comprising:

a data structure stored in said memory, said data structure including information resident in a database used by said application program and including;

a plurality of spatial block data objects, each spatial block data object representing a spatially indexed partitioning of a data set, each spatial block data object containing a set of data arrays storing point data from the data set, as well as corresponding organizational structure information and any auxiliary information; and

a point set spatial tree data object formed of the plurality of spatial block data objects at a number of body layers, the spatial tree data object growing from a global root block data object using the organizational structure information for the spatial block data objects.

26. A memory according to claim 25, wherein:

the data structure further includes a plurality of header block data objects in the point set spatial tree.

27. A memory according to claim 25, wherein:

the data of the data set includes three-dimensional point data.

28. A memory according to claim 25, wherein:

the body layers are indexed spatially by at least one of density and region of space.

29. A memory according to claim 25, wherein:

each body layer represents a cross section of data at a predetermined density.

30. A memory according to claim 25, wherein:

the point set spatial tree data object is an octree data structure.

31. A memory according to claim 25, wherein:

each of the plurality of data arrays is a linear data array of the same size, with one field and one structural element per point.

32. A memory according to claim 31, wherein:

the linear data arrays within a spatial block are partitioned into segments, each segment containing a portion of the data array that corresponds exactly to one or more body layers.

33. A memory according to claim 25, wherein:

information stored for each point of the data set includes information selected from the group consisting of index information about a parent sample within the spatial block, index information about a first child sample within the spatial block, a flag field indicating whether a point sample represents a last sub-sample of a parent in the data array, a flag field indicating whether there are subfields within other spatial blocks, and a flag indicating whether another spatial block is rooted at the location of a point sample.

34. A memory according to claim 25, wherein:

each spatial block stores pieces of information selected from the group consisting of references to any child spatial blocks, the sizes of each body layer from a root of the spatial block down to an end of the spatial block, a bounding region of a root sample of the spatial block, a bounding region specifying a bound of a subtree of samples rooted at a root of the spatial block, a spatial resolution of each layer of the spatial tree, the resolutions of each layer from the root of the spatial block to the bottom of the spatial tree, a reference to a parent spatial block of the spatial block, and at least one header block referring to a root spatial block of the spatial tree.

35. A memory according to claim 34, wherein:

the data structure further includes at least one data subset of the point set.

36. A memory according to claim 35, wherein:

the subset is a mathematical or geometric combination of one or more of a filtered subset, an enumerated subset, and a composite subset.

37. A memory according to claim 36, wherein:

the mathematical or geometric combination includes unions, intersections, and negations.

38. A memory according to claim 35, wherein:

the point subset is represented in the data structure by an expression tree, internal nodes of the expression tree including expressions for combining subsets.

39. A memory according to claim 35, wherein:

each of the at least one data subset includes contents and properties that are evaluated when that subset is evaluated, rather than when that subset is defined.

40. A memory according to claim 35, wherein:

each of the at least one data subset comprises an expression tree, and a plurality of the at least one data subset are combinable into an aggregate subset that comprises an aggregate expression tree.

41. A memory according to claim 39, wherein:

the combination into an aggregate subset is performed by at least one of a union, an intersection, and a negation of individual expressions of the at least one data subset.

42. A memory according to claim 37, wherein:

at least one of the at least one data subset includes an individual expression capable of being simplified to reduce complexity.

43. A memory according to claim 42, wherein:

the simplification to reduce complexity uses at least one of the point data, mathematical properties of the individual expression, and geometric properties of the individual expression.

44. A memory according to claim 35, wherein:

each of the at least one data subset is capable of being filtered using at least one filter operable to filter by one of geometric properties, intensity, color, and other auxiliary data fields associated per point.

45. A memory according to claim 36, wherein:

each filtered subsets includes at least one geometric filter selected from the group consisting of cones, spheres, cylinders, slices, torii, axis aligned boxes, non axis aligned boxes, polygonal fences, half-spaces, parallel planes, caps, and vectors.

46. A memory according to claim 35, wherein:

the at least one data subset is built up interactively from multiple independent operations that are capable of adding constraints to, and removing constraints from, the subset before committing the subset to the memory.