Display of hierarchical three-dimensional structures with rotating substructures

• US 5,295,243 A
• Filed: 05/21/1993
• Issued: 03/15/1994
• Est. Priority Date: 12/29/1989
• Status: Expired due to Term

• Current Assignee: SAP America Incorporated (SAP SE)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Robertson, George G., Card, Stuart K., Mackinlay, Jock
• Primary Examiner(s): Zimmerman, Mark K.
• Application Number:
  US08/066,311
• Time in Patent Office: 298 Days
• Field of Search: 364/518, 364/521, 364/522, 364/146, 364/147, 395/120, 395/137, 395/160, 395/152, 340/721, 340/729, 340/734
• US Class Current: 715/848
• CPC Class Codes: G06F 2203/04802 3D-info-object: information is displayed on the internal or external surface of a three dimensional manipulable object, e.g. on the faces of a cube that can be rotated by the user
• 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 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: Y10S 715/976 3-D Icon
• CPC Class Codes: Y10S 715/977 Dynamic icon, e.g. animated or live action

Abstract

A processor presents a sequence of images of a hierarchical structure that is perceived as three-dimensional. The hierarchical structure includes conic substructures that can have vertical or horizontal axes. Each cone has a parent node at its vertex and children nodes along its base, each with a link to the parent node. Each child can in turn be at the vertex of another cone. The cones can be rotated in steps that produce the perception of object constancy for each node. For example, if the user requests that an indicated node be moved to a primary viewing position, each of the cones along the path from the indicated node to the root node is rotated in the direction that most directly moves the indicated node to the primary viewing position. Each node can include a selectable unit for indicating it, and a node can also include a grow tab that can be selected to request presentation of its children nodes and links to them. The user can request that the children nodes of a node be replaced by a grow tab. To reduce the computation necessary for each step of rotation, the position relative to a cone'"'"'s axis for each of 80 points on the base of a cone is computed for a level of the hierarchy and is then stored in an array for subsequent use in positioning nodes on that level. The base point of each node on a rotating cone can then be changed in a linked node data structure, and its new position can then be obtained by simple arithmetic operations using the axis coordinates and the appropriate data from the array. The base of each array can be a polygon whose vertices are nodes, and the base shape can be presented as a shadow to provide additional information and strengthen the perception of three dimensions. Or, the profiles of the cones can be presented as a shadow.

Claims

1. A method of operating a processor connected for providing image data to an image output device that includes a display, the image output device presenting images on the display in response to the image data, the processor further being connected for accessing a first level data structure, the method comprising steps of:

providing first image data so that the image output device presents a first image, the first image including a first hierarchical structure that is perceptible as three-dimensional;

the first structure including a first plurality of nodes and a first plurality of links, each of the first plurality of links being perceptible as connecting one of the first plurality of nodes to another of the first plurality of nodes, the first structure further including a plurality of levels, a subset of the first plurality of nodes and the first plurality of links forming a first cone-like substructure at a first one of the levels of the first structure, the step of providing the first image data comprising a substep of determining a position of the first cone-like substructure and including in the first level data structure position data indicating the position of the first cone-like substructure; and

providing second image data so that the image output device presents a second image, the second image including a second hierarchical structure that is perceptible as three-dimensional and that is perceptible different than the first structure;

the second structure including a second plurality of nodes and a second plurality of links, each of the second plurality of links being perceptible as connecting one of the second plurality of nodes to another of the second plurality of nodes;

the second structure further including a plurality of levels, each of the second plurality of nodes being perceptible as a continuation of a respective one of the first plurality of nodes, each of the second plurality of links being perceptible as a continuation of a respective one of the first plurality of links, so that the levels of the second structure are perceptible as continuations of the levels of the first structure;

a subset of the second plurality of nodes and the second plurality of links forming a second cone-like substructure, the step of providing the second image data comprising the substep of accessing the first level data structure and determining the position of the second cone-like substructure using the position data.

2. The method of claim 1 in which the second cone-like substructure is perceptible as a rotated continuation of the first cone-like substructure, the rotation being about an axis, the position data indicating the position of the first cone-like substructure relative to the axis.

3. A method of operating a processor connected for providing image output data to an image output device that includes a display and also connected for receiving signals from a user input device, the image output device presenting images on the display in response to the image output data, the method comprising:

a step of providing initial image output data so that the image output device presents an initial image, the initial image including an initial structure that is perceptible as three-dimensional, the initial structure including a plurality of initial nodes and a plurality of initial links, each of the initial links being perceptible as connecting one of the initial nodes to another of the initial nodes;

the initial structure including an initial cone-like substructure having a vertex and having a directrix that is circular or polygonal, the plurality of initial nodes including an initial parent node at the vertex and a plurality of initial children nodes on the directrix, the plurality of initial links including, for each of the initial children nodes, a respective link in the initial cone-like substructure, the respective link being perceptible as connecting the initial parent node to the initial children node;

a step of receiving a signal from the user input device indicating one of the initial children nodes;

the indicated one of the initial children nodes being at an initial position within the initial structure; and

in response to the signal from the user input device, a plurality of image output steps performed in sequence, each image output step providing respective image output data so that the image output device presents a respective image, the respective image of each step including a respective structure that is perceptible as three-dimensional, each respective structure including a respective plurality of nodes and a respective plurality of links, each of the respective links being perceptible as connecting one of the respective nodes to another of the respective nodes;

each image output step'"'"'s structure including a respective cone-like substructure having a vertex and having a directrix that is circular or polygonal, the step'"'"'s plurality of nodes including a respective parent node at the vertex and a plurality of respective children nodes on the directrix, the step'"'"'s plurality of links including, for each of the step'"'"'s children nodes, a respective link in the step'"'"'s cone-like substructure, the respective link being perceptible as connecting the step'"'"'s parent node to the children node;

the sequence of image output steps including a following step and a preceding step;

each of the respective nodes of the following step being perceptible as a continuation of one of the respective nodes of the preceding step, each of the respective links of the following step being perceptible as a continuation of one of the respective links of the preceding step;

the following step'"'"'s cone-like substructure being perceptible as a rotated continuation of the preceding step'"'"'s cone-like substructure;

the children nodes of each of the image output steps including a respective continued node, each image output step'"'"'s continued node being perceptible as a continuation of the indicated one of the initial children nodes, moved from the initial position toward a final position.

4. The method of claim 3 in which the sequence of image output steps includes a last step;

the respective structure of the last step including a primary viewing position which is the final position.

5. A method of operating a processor connected for providing image data to an image output device that includes a display and also connected for receiving signals from a user input device, the image output device presenting images on the display in response to the image data, the method comprising the steps of:

providing first image data so that the image output device presents a first image, the first image including a first hierarchical structure that is perceptible as three-dimensional, the first structure including a first plurality of nodes and a first plurality of links, each of the first plurality of links being perceptible as connecting one of the first plurality of nodes to another of the first plurality of nodes;

the first structure including a first cone-like substructure having a vertex and having a directrix that is circular or polygonal, the first plurality of nodes including a first parent node at the vertex and a plurality of first children nodes on the directrix, the first plurality of links including, for each of the first children nodes, a respective link in the first cone-like substructure, the respective link being perceptible as connecting the first parent node to the first children node;

receiving a signal from the user input device indicating one of the first children nodes;

the indicated one of the first children nodes being at an initial position within the first structure; and

in response the signal from the user input device, providing second image data so that the image output device presents a second image, the second image including a second hierarchical structure that is perceptible as three-dimensional;

the second structure including a second plurality of nodes and a second plurality of links, each of the second plurality of links being perceptible as connecting one of the second plurality of nodes to another of the second plurality of nodes;

each of the second plurality of nodes being perceptible as a continuation of a respective one of the first plurality of nodes, each of the second plurality of links being perceptible as a continuation of a respective one of the first plurality of links;

the second structure including a second cone-like substructure having a vertex and having a directrix that is circular or polygonal, the second plurality of nodes including a second parent node at the vertex and a plurality of second children nodes on the directrix, the second plurality of links including, for each of the second children nodes, a respective link in the second cone-like substructure, the respective link being perceptible as connecting the second parent node to the second children node;

the second cone-like substructure being perceptible as a rotated continuation of the first cone-like substructure;

the second children nodes including a continued node that is perceptible as a continuation of the indicated one of the first children nodes, moved from the initial position toward a final position within the second structure.

6. The method of claim 5 in which each link of the first and second pluralities of links is perceptible as having a length, the perceptible length of each of the second plurality of links being the same as the perceptible length of the respective one of the first plurality of links.

7. The method of claim 5 in which the first and second structures have equal numbers of hierarchical levels.

8. The method of claim 5 in which the first structure further includes a third cone-like substructure and the second structure further includes a fourth cone-like substructure that is perceptible as a rotated continuation of the third cone-like substructure;

the perceptible rotation from the first cone-like substructure to the second cone-like substructure being about a first axis and the perceptible rotation from the third cone-like substructure to the fourth cone-like substructure being about a second axis, the first and second axes of perceptible rotation being parallel.

9. The method of claim 8 in which the first and second axes are vertical.

10. The method of claim 8 in which the first and second axes are horizontal.

11. The method of claim 5 in which all of the respective links in the first cone-like substructure are perceptible as being of equal length.

12. The method of claim 5 in which the first cone-like substructure is perceptible as having an axis and a profile shape in a first plane that includes the axis, the first image further including a first projected shape that is perceptible as a projection of the profile shape of the first cone-like substructure onto a second plane.

13. The method of claim 12 in which first and second ones of the respective links have positions that define the profile shape in the first plane and the second plane is perceptible as parallel to the first plane, the step of providing the first image data further comprising the substep of determining the positions of the first and second respective links and using the positions both to prepare first structure data defining the first structure and projection data defining the first projected shape.

14. The method of claim 12 in which one of the children nodes comprises a selectable unit that is perceptible as perpendicular to the first plane and the first plane is parallel to the second plane, the first image further including a second projected shape that is perceptible as a projection of the selectable unit onto the second plane, the second projected shape being a line.

15. The method of claim 5 in which the directrix of the first cone-like substructure forms a base, the base having a perceptible geometric shape lying substantially in a first plane;

the first image further including a projected shape that is perceptible as a projection of the geometric shape of the base onto a second plane.

16. The method of claim 15 in which the geometric shape of the base lies entirely in the first plane and the second plane is perceptible as parallel to the first plane, the step of providing the first image data further comprising the substep of determining the geometric shape of the base and using the geometric shape both to prepare first structure data defining the first structure and projection data defining the projected shape.

17. The method of claim 5 in which the first and second structures each have hierarchical levels that include an upper level and a lower level, the first and second cone-like structures being included in the upper levels of the first and second structures respectively, the first structure further including a first lower cone-like substructure in the lower level, the second structure further including a second lower cone-like substructure in the lower level;

the first and second lower cone-like substructures each having a vertex, the vertices of the first and second lower cone-like substructures respectively being on the bases of the first and second cone-like substructures;

the second lower cone-like substructure being perceptible as a rotated continuation of the first lower cone-like substructure;

the perceptible rotation from the first lower cone-like substructure to the second lower cone-like substructure being concurrent with the perceptible rotation from the first cone-like substructure to the second cone-like substructure.

18. The method of claim 17 in which the perceptible rotation from the first cone-like substructure to the second cone-like substructure and from the first lower cone-like substructure to the second lower cone-like substructure is one of a plurality of steps in a sequence of perceptible rotations by which the indicated one of the first children nodes reaches the final position;

the perceptible rotation from the first cone-like substructure to the second cone-like substructure being in a first direction of rotation and the perceptible rotation from the first lower cone-like substructure to the second lower cone-like substructure being in a second direction of rotation;

the step of providing the second image data comprising the substep of selecting the first and second directions of rotation to reduce the number of steps in the sequence to reach the final position.

19. The method of claim 5 in which the step of providing the first image data comprises providing the first image data so that a selectable one of the first plurality of nodes includes a first selectable unit, the step of providing the second image data comprising providing the second image data so that a selectable one of the second plurality of nodes includes a second selectable unit;

the second selectable unit being perceptible as a continuation of the first selectable unit.

20. The method of claim 19 in which the first and second structures have equal numbers of hierarchical levels including an uppermost level that includes uppermost ones of the first and second pluralities of nodes and a sequence of successively lower levels, the first selectable unit being at one of the lower levels, the first plurality of nodes and the first plurality of links including a path of nodes and links between the first selectable unit and the uppermost one of the first plurality of nodes;

the processor further being connected for receiving signals from a user input device;

the method further comprising the steps of;

receiving a signal from the user input device indicating the first selectable unit; and

in response to the signal indicating the first selectable unit, providing selection image data so that the image output device presents a modified image, the path of nodes and links being presented differently in the modified image than in the first image so that the user can more easily distinguish the path of nodes and links.

21. The method of claim 19 in which the first structure includes a number of hierarchical levels, the first selectable unit being at a first one of the hierarchical levels, the processor further being connected for receiving signals from a user input device;

the method further comprising the steps of;

receiving a signal from the user input device indicating the first selectable unit; and

in response to the signal indicating the first selectable unit, providing expanded image data so that the image output device presents a modified image, the modified image including a second hierarchical level below the first hierarchical level, the second hierarchical level including an additional link and an additional node not in the first plurality of links and the first plurality of nodes;

the additional link being perceptible as connecting the selectable node to the additional node.

22. The method of claim 5 in which the first structure includes a number of hierarchical levels;

a first one of the hierarchical levels including a first one of the plurality of nodes;

a second one of the hierarchical levels below the first level including a second one of the pluralit of nodes and a descending link that is perceptible as connecting the first node to the second node, the processor further being connected for receiving signals from a user input device;

the method further comprising the steps of;

receiving a signal from the user input device requesting that the descending link and the second node not be presented; and

in response to the signal, providing reduced image data so that the image output device presents a modified image that does not include the descending link and the second node.