Spatial index compression through spatial subdivision encoding

• US 6,463,180 B1
• Filed: 05/10/2000
• Issued: 10/08/2002
• Est. Priority Date: 04/07/1998
• Status: Expired due to Term

• Current Assignee: Autodesk, Inc.
• Original Assignee: Autodesk, Inc.
• Inventors: Krishnaswamy, Ravinder Patnam
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US09/569,120
• Time in Patent Office: 881 Days
• Field of Search: 382/226, 382/232, 382/240, 341/51, 707/1-10, 707/100-104, 707/200-206
• US Class Current: 382/240
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree

Abstract

A technique for reducing the total storage used in representing data having spatial extents. The data is represented in a tree structure having a plurality of nodes, wherein each of the nodes has parent and child relationship to one or more others of the nodes in the tree structure. An encoded representation of the relation of a child node'"'"'s extents with respect to its parent is stored in the node. A preorder traversal of the tree structure is performed to store it compactly in an output file.

Claims

1. A computer-implemented method for representing and encoding data having spatial extents, comprising:

(a) representing the data in a tree structure having a plurality of nodes; and

(b) encoding a spatial identifier for each node as a representation of the node'"'"'s extents with respect to its parent'"'"'s extents, wherein the encoded spatial identifier includes at least octant, {fraction (1/16)}^th overlap, and degenerate axis Values.

2. The method of claim 1 above, wherein the spatial identifier identifies the node'"'"'s extents as a subdivision of the parent'"'"'s extents.

3. The method of claim 2 above, wherein the subdivision comprises an octant subdivision.

4. The method of claim 2 above, wherein the subdivision comprises a {fraction (1/16)}^th expanded version of an octant subdivision along coordinate planes that divide root extents.

5. The method of claim 2 above, wherein the subdivision comprises a merger of a plurality of expanded octants along a coordinate axis.

6. The method of claim 5 above, wherein the node classifies data that spans the extents along a coordinate axis.

7. The method of claim 5 above, wherein the node comprises a merger of nodes along two coordinate axes.

8. The method of claim 1 above, wherein the spatial identifier is stored in an extension dictionary of a table record of a block table within a database of a datastream.

9. A computer-implemented apparatus for representing and encoding data having spatial extents, comprising:

(a) means for representing the data in a tree structure having a plurality of nodes; and

(b) means for encoding a spatial identifier in each node as a representation of the node'"'"'s extents with respect to its parent'"'"'s extents, wherein the encoded spatial identifier includes at least octant, {fraction (1/16)} overlap, and degenerate axis values.

10. The apparatus of claim 9 above, wherein the spatial identifier identifies the node'"'"'s extents as a subdivision of the parent'"'"'s extents.

11. The apparatus of claim 10 above, wherein the subdivision comprises an octant subdivision.

12. The apparatus of claim 10 above, wherein the subdivision comprises a {fraction (1/16)}^th expanded version of an octant subdivision along coordinate planes that divide root extents.

13. The apparatus of claim 10 above, wherein the subdivision comprises a merger of a plurality of expanded octants along a coordinate axis.

14. The apparatus of claim 13 above, wherein the node classifies data that spans the extents along a coordinate axis.

15. The apparatus of claim 13 above, wherein the node comprises a merger of nodes along two coordinate axes.

16. The apparatus of claim 9 above, wherein the spatial identifier is stored in an extension dictionary of a table record of a block table within a database of a datastream.

17. An article of manufacture embodying logic for representing and encoding data having spatial extents, comprising:

(a) representing the dam in a tree structure having a plurality of nodes; and

(b) encoding a spatial identifier for each node as a representation of the node'"'"'s extents with respect to its parent'"'"'s extents, wherein the encoded spatial identifier includes at least octant, ⅙

^th overlap, and degenerate a values.

18. The article of manufacture of claim 17 above, wherein the spatial identifier identifies the node'"'"'s extents as a subdivision of the parent'"'"'s extents.

19. The article of manufacture of claim 18 above, wherein the subdivision comprises an octant subdivision.

20. The article of manufacture of claim 18 above, wherein the subdivision comprises a {fraction (1/16)}^th expanded version of an octant subdivision along coordinate planes that divide root extents.

21. The article of manufacture of claim 18 above, wherein the subdivision comprises a merger of a plurality of expanded octants along a coordinate axis.

22. The article of manufacture of claim 21 above, wherein the node classifies data that spans the extents along a coordinate axis.

23. The article of manufacture of claim 21 above, wherein the node comprises a merger of nodes along two coordinate axes.

24. The article of manufacture of claim 17 above, wherein the spatial identifier is stored in an extension dictionary of a table record of a block table within a database of a datastream.

25. A data structure stored in a data storage device for representing and encoding data having spatial extents, the data structure comprising a tree structure having a plurality of nodes, wherein a spatial identifier is encoded for each node as a representation of the node'"'"'s extents with respect to its parent'"'"'s extents, wherein the encoded spatial identifier includes at least octant, {fraction (1/16)}^th overlap, and degenerate axis values.

26. The data structure of claim 25 above, wherein the spatial identifier identifies the node'"'"'s extents as a subdivision of the parent'"'"'s extents.

27. The data structure of claim 26 above, wherein the subdivision comprises an octant subdivision.

28. The data structure of claim 26 above, wherein the subdivision comprises a {fraction (1/16)}^th expanded version of an octant subdivision along coordinate planes that divide root extents.

29. The data structure of claim 26 above, wherein the subdivision comprises a merger of a plurality of expanded octants along a coordinate axis.

30. The data structure of claim 29 above, wherein the node classifies data that spans the extents along a coordinate axis.

31. The data structure of claim 29 above, wherein the node comprises a merger of nodes along two coordinate axes.

32. The data structure of claim 25 above, wherein the spatial identifier is stored in an extension dictionary of a table record of a block table within a database of a datastream.