Method of generating a 3-D representation of a hierarchical data structure

• US 5,877,775 A
• Filed: 08/06/1997
• Issued: 03/02/1999
• Est. Priority Date: 08/08/1996
• Status: Expired due to Fees

• Current Assignee: Vinq, LLC
• Original Assignee: Elastic Technology, Inc.
• Inventors: Jhong, Eugene, Theisen, Karen E.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/907,207
• Time in Patent Office: 573 Days
• Field of Search: 345/440, 345/441, 345/433, 345/333, 345/334
• US Class Current: 345/440
• CPC Class Codes: G06F 3/04815 Interaction with a metaphor-based environment or interaction object displayed as three-dimensional, e.g. changing the user viewpoint with respect to the environment or object
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering

Abstract

A method of generating a three-dimensional representation of a hierarchical data structure is disclosed. By taking advantage of a compact three-dimensional representation, the present invention provides an overview of an entire hierarchy of files so as to facilitate use orientation within the hierarchical data structure. The method commences with the generation of a hierarchical data structure, which is then mapped onto a two-dimensional grid by assigning each node in the hierarchical data structure X and Y axis coordinates. A Z axis, which may be at an angle of 30° relative to an X axis, is then defined. Within each level within the hierarchical data structure, a Z line is then defined as being parallel to the Z axis and as intersecting the level. Thereafter, for each level, each node is mapped from a location on a Y line to a corresponding location on the defined Z line, so that at least the Y coordinate for each node is recalculated. A node representation for each node is then displayed at a first point defined by the respective X coordinate and the recalculated Y coordinate on a display unit. A connector representation is then displayed between each parent and child node on the display unit.

Claims

1. A computer-implemented method of generating a three-dimensional representation of a hierarchical data structure for display on a display unit, the hierarchical data structure comprising a plurality of nodes arranged in a plurality of levels, each node representing a data item, the method comprising the steps of:

generating the hierarchical data structure;

assigning each node a pair of X and Y axis coordinates in a two-dimensional grid having X and Y axis which are perpendicular, so that nodes on a common level each have a common Y axis coordinate to define a Y line;

defining a Z axis with a predetermined angle relative to the X axis;

for each level, defining a Z line which is parallel to the Z axis;

for each level, mapping each node location on the respective Y line to a corresponding location on the respective Z line so as to recalculate at least the Y coordinate of each node;

displaying a node representation of each node at a respective first point defined at the respective X coordinate and the recalculated Y coordinates on the display unit; and

displaying a respective connector representation between each parent and child node representation on the display unit so as to generate the three-dimensional representation.

2. The method of claim 1 wherein the step of mapping comprises recalculating, for each node, the Y coordinate to fall on the respective Z-line while maintaining a previously calculated X coordinate.

3. The method of claim 1 including the step of, for each level, shifting the level parallel to the X axis by recalculating the X coordinate for each node.

4. The method of claim 1 wherein each node representation extends from the respective first point to a second point, and wherein the step of displaying the connector comprises displaying a connector representation between the second point of a parent node and the first point of a child node so as to impart a stepped appearance to the three-dimensional representation.

5. The method of claim 4 wherein the first and second points for each node have a common X coordinate or a common Y coordinate.

6. The method of claim 1 wherein the first and second points for each node have a common X coordinate or a common Y coordinate.

7. The method of claim 1 including the step of recalculating the X coordinates of the nodes of each level, so that each level is substantially centered with respect to a preceding level.

8. The method of claim 1 including the step of recalculating the X and Y coordinates of each of the nodes according to a zoom factor input.

9. The method of claim 1 wherein the step of assigning each node a pair of X and Y axis coordinates in a two-dimensional grid comprises the steps of:

(a) determining a node gap value which indicates a spacing between nodes in a group of nodes having a common parent and being on a common level;

(b) determining a group gap value which indicates a spacing between the group of nodes and an adjacent group of nodes on the common level; and

(c) for each group of nodes, calculating the X-axis coordinates for each node so that the spacing between adjacent nodes within a current group is equal to the node gap value; and

(d) for each group of nodes, calculating the X-axis coordinates for each node so that the spacing between adjacent groups is at least the group gap value.

10. The method of claim 9 including the step of, for each group of nodes, calculating the X-axis coordinates so that the current group is substantially centered with respect to the parent of the current group.

11. The method of claim 9 including the step of determining whether the width of at least a portion of the current level is too large with respect to a previous level by a predetermined metric and, if so, decreasing the node gap value and/or the group gap value for the current level.

12. The method of claim 1 wherein the predetermined angle of the Z axis relative to the X axis is between 25 and 35 degrees.

13. The method of claim 1 wherein the node representation includes a sheared identifier string.

14. A computer-readable medium having stored thereon a sequence of instructions which, when executed by a processor, cause the processor to perform the steps of:

generating a hierarchical data structure, the hierarchical data structure comprising a plurality of nodes, each of which represents a data item;

assigning each node a pair of X and Y axis coordinates in a two-dimensional grid having X and Y axis which are perpendicular, so that nodes on a common level each have a common X axis coordinate to define a Y line;

defining a Z axis with a predetermined angle relative to the X axis;

for each level, defining a Z line which is parallel to the Z axis;

for each level, mapping each node location on the respective Y line to a corresponding location on the respective Z line so as to recalculate at least the Y coordinate of each node;

displaying a node representation of each node at a respective first point defined at the X coordinate and the recalculated Y coordinate on a display unit; and

displaying a respective connector representation between each parent and child node representation on the display unit.

15. A computer data signal embodied in a carrier wave and representing a sequence of instructions which, when executed by a processor, cause the processor to perform the steps of:

generating a hierarchical data structure, the hierarchical data structure comprising a plurality of nodes, each of which represents a data item;

assigning each node a pair of X and Y axis coordinates in a two-dimensional grid having X and Y axis which are perpendicular, so that nodes on a common level each have a common X axis coordinate to define a Y line;

defining a Z axis with a predetermined angle relative to the X axis;

for each level, defining a Z line which is parallel to the Z axis;

for each level, mapping each node location on the respective Y line to a corresponding location on the respective Z line so as to recalculate at least the Y coordinate of each node;

displaying a node representation of each node at a respective first point defined at the X coordinate and the recalculated Y coordinate on a display unit; and

displaying a respective connector representation between each parent and child node representation on the display unit.