Method, system and computer program product for navigating through partial hierarchies

• US 6,111,578 A
• Filed: 04/25/1997
• Issued: 08/29/2000
• Est. Priority Date: 03/07/1997
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Tesler, Joel D.
• Primary Examiner(s): Bayerl, Raymond J.
• Assistant Examiner(s): Thai, Cuong T.
• Application Number:
  US08/845,465
• Time in Patent Office: 1,222 Days
• Field of Search: 345/356, 345/355, 345/357, 345/419, 345/427, 345/353, 345/976, 345/473
• US Class Current: 715/850
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

A method, system, and computer program product provides data visualization which optimizes visualization of and navigation through hierarchies. A partial hierarchy is generated and displayed. The partial hierarchy consists of a number levels at least equal to a predetermined depth and less than a total number of levels included in a corresponding complete hierarchy. Parent nodes in the bottom level of the partial hierarchy have segments of connection lines extending toward child nodes not included in the partial hierarchy. A user is permitted to mark selected nodes or locations in a displayed partial hierarchy. Partial hierarchies are generated and stored in a cache or generated on-the-fly. Each partial hierarchy ends at a progressively deeper level. An interpolator interpolates a partial hierarchy layout by interpolating corresponding nodes in two partial hierarchies. A hierarchy manager manages partial hierarchies in response to requests from a viewer to move a camera to camera positions. Partial hierarchies are fetched from the cache or the interpolator. A display then displays display views of fetched partial hierarchies corresponding to the camera positions. During free-form navigation, a hierarchy manager determines and maintain an orientation based on at least one reference object. During zooming, an angular orientation is maintained through successive partial hierarchies. Mapping is also provided between a three-dimensional 3D partial hierarchy and a two-dimensional 2D overview of a complete hierarchy.

Claims

1. A computer-implemented method for navigating through partial hierarchies, the method comprising the steps of:

determining a new effective camera position (x,z) within a current partial hierarchy based on a new navigator position;

fetching a new partial hierarchy corresponding to said new effective camera position;

determining an orientation between said new effective camera position and at least one reference object in said current partial hierarchy;

adjusting said new effective camera position to maintain said orientation with the said at least one reference object as found in said new partial hierarchy fetched in said fetching step;

converting said adjusted new effective camera position to a new camera position; and

displaying a display view showing said fetched partial hierarchy layout in a field of view of a camera positioned at said new camera position;

wherein said orientation determining step determines an orientation between said new effective camera position and two reference objects in the current partial hierarchy;

wherein said orientation determining step comprises the steps of;

finding two reference nodes in the current partial hierarchy, determining a point in front of said new effective camera position on a line intersecting said two reference nodes, and

calculating a proportion of the distance between said determined point and one of said two reference nodes; and

wherein said adjusting step adjusts an x coordinate of said new effective camera position to maintain said proportion with said one reference node as found in said new partial hierarchy fetched in said fetching step;

whereby, a user viewing said current partial hierarchy at said current camera position can navigate in a substantially straight line to a new navigator position.

2. The method of claim 1, wherein said fetching step fetches said new partial hierarchy from a cache of partial hierarchies or fetches said new partial hierarchy from an interpolator.

3. The method of claim 1, wherein said fetching step generates said new partial hierarchy on the fly.

4. The method of claim 1, further comprising the step of:

permitting a user to mark at least one of a selected object or a selected location in said displayed partial hierarchy.

5. The method of claim 4, further comprising the step of:

storing relative coordinates for a mark that identifies a location of said mark relative to coordinates for the selected object.

6. A computer-implemented method for navigating through partial hierarchies, the method comprising the steps of:

determining a new effective camera position (x,z) within a current partial hierarchy based on a new navigator position;

fetching a new partial hierarchy corresponding to said new effective camera position;

determining an orientation between said new effective camera position and at least one reference object in said current partial hierarchy;

adjusting said new effective camera position to maintain said orientation with the said at least one reference object as found in said new partial hierarchy fetched in said fetching step;

converting said adjusted new effective camera position to a new camera position; and

displaying a display view showing said fetched partial hierarchy layout in a field of view of a camera positioned at said new camera position;

wherein said orientation determining step determines an orientation between said new effective camera position and one reference object in the current partial hierarchy; and

wherein said orientation determining step comprises the steps of;

finding one reference node in the current partial hierarchy,

determining a displacement distance between said new effective camera position and said one reference node in said current partial hierarchy; and

said adjusting step adjusts an x coordinate of said new effective camera position to maintain said displacement distance with respect to said one reference node as found in said new partial hierarchy fetched in said fetching step;

whereby, a user viewing said current partial hierarchy at said current camera position can navigate in a substantially straight line to a new navigator position.

7. A computer-implemented method for navigating through partial hierarchies, the method comprising the steps of:

determining a new effective camera position (x,z) within a current partial hierarchy based on a new navigator position;

fetching a new partial hierarchy corresponding to said new effective camera position;

determining an orientation between said new effective camera position and at least one reference object in said current partial hierarchy;

adjusting said new effective camera position to maintain said orientation with the said at least one reference object as found in said new partial hierarchy fetched in said fetching step;

converting said adjusted new effective camera position to a new camera position; and

displaying a display view showing said fetched partial hierarchy layout in a field of view of a camera positioned at said new camera position;

wherein said orientation determining step determines an angular orientation between said new effective camera position and one object selected for zooming in the current partial hierarchy;

wherein said orientation determining step comprises the step of;

determining an angle θ

between said new effective camera position and said selected object in said current partial hierarchy; and

wherein said adjusting step adjusts an x coordinate of said new effective camera position to maintain said angle θ

with respect to said selected object as found in said new partial hierarchy fetched in said fetching step;

whereby, a user viewing said current partial hierarchy at said current camera position can navigate in a substantially straight line to a new navigator position.

8. A computer-implemented method for navigating through partial hierarchies, the method comprising the steps of:

determining a new effective camera position (x,z) within a current partial hierarchy based on a new navigator position;

fetching a new partial hierarchy corresponding to said new effective camera position;

determining an orientation between said new effective camera position and at least one reference object in said current partial hierarchy;

adjusting said new effective camera position to maintain said orientation with the said at least one reference object as found in said new partial hierarchy fetched in said fetching step;

converting said adjusted new effective camera position to a new camera position;

displaying a display view showing said fetched partial hierarchy layout in a field of view of a camera positioned at said new camera position;

permitting a user to mark at least one of a selected object or a selected location in said displayed partial hierarchy;

storing absolute coordinates for a mark that identifies a specific location; and

interpreting said absolute coordinates directly when a camera position is at approximately the same z coordinate position as a z coordinate of said absolute coordinates, and otherwise transforming said absolute coordinates to a coordinate system at the camera position;

whereby, a user viewing said current partial hierarchy at said current camera position can navigate in a substantially straight line to a new navigator position.

9. A computer graphics system for navigating through partial hierarchies, comprising:

means for determining a new effective camera position (x,z) within a current partial hierarchy based on a new navigator position;

means for fetching a new partial hierarchy corresponding to said new effective camera position;

means for determining an orientation between said new effective camera position and at least one reference object in said current partial hierarchy;

means for adjusting said new effective camera position to maintain said orientation with the said at least one reference object as found in said new partial hierarchy fetched by said fetching means;

means for converting said adjusted new effective camera position to a new camera position; and

means for displaying a display view showing said fetched partial hierarchy layout in a field of view of a camera positioned at said new camera position;

wherein said orientation determining means determines an orientation between said new effective camera position and two reference objects in the current partial hierarchy; and

wherein said orientation determining means comprises;

means for finding two reference nodes in the current partial hierarchy,

means for determining a point in front of said new effective camera position on a line intersecting said two reference nodes, and

means for calculating a proportion of the distance between said determined point and one of said two reference nodes; and

wherein said adjusting means adjusts an x coordinate of said new effective camera position to maintain said proportion with said one reference node as found in said new partial hierarchy fetched by said fetching means;

whereby, a user viewing said current partial hierarchy at said current camera position can navigate in a substantially straight line to a new navigator position.

10. The system of claim 9, wherein said fetching means fetches said new partial hierarchy from a cache of partial hierarchies or fetches said new partial hierarchy from an interpolator.

11. The system of claim 9, wherein said fetching means generates said new partial hierarchy on the fly.

12. The system of claim 9, further comprising:

means for permitting a user to mark at least one of a selected object or a selected location in said displayed partial hierarchy.

13. The system of claim 12, further comprising:

means for storing relative coordinates for a mark that identifies a location of said mark relative to coordinates for the selected object.

14. A computer graphics system for navigating through partial hierarchies, comprising:

means for determining a new effective camera position (x,z) within a current partial hierarchy based on a new navigator position;

means for fetching a new partial hierarchy corresponding to said new effective camera position;

means for determining an orientation between said new effective camera position and at least one reference object in said current partial hierarchy;

means for adjusting said new effective camera position to maintain said orientation with the said at least one reference object as found in said new partial hierarchy fetched by said fetching means;

means for converting said adjusted new effective camera position to a new camera position; and

means for displaying a display view showing said fetched partial hierarchy layout in a field of view of a camera positioned at said new camera position;

wherein said orientation determining means determines an orientation between said new effective camera position and one reference object in the current partial hierarchy; and

wherein said orientation determining means comprises;

means for finding one reference node in the current partial hierarchy,

means for determining a displacement distance between said new effective camera position and said one reference node in said current partial hierarchy; and

wherein said adjusting means adjusts an x coordinate of said new effective camera position to maintain said displacement distance with respect to said one reference node as found in said new partial hierarchy fetched by said fetching means;

whereby, a user viewing said current partial hierarchy at said current camera position can navigate in a substantially straight line to a new navigator position.

15. A computer graphics system for navigating through partial hierarchies, comprising:

means for determining a new effective camera position (x,z) within a current partial hierarchy based on a new navigator position;

means for fetching a new partial hierarchy corresponding to said new effective camera position;

means for determining an orientation between said new effective camera position and at least one reference object in said current partial hierarchy;

means for adjusting said new effective camera position to maintain said orientation with the said at least one reference object as found in said new partial hierarchy fetched by said fetching means;

means for converting said adjusted new effective camera position to a new camera position; and

means for displaying a display view showing said fetched partial hierarchy layout in a field of view of a camera positioned at said new camera position;

wherein said orientation determining means determines an angular orientation between said new effective camera position and one object selected for zooming in the current partial hierarchy;

wherein said orientation determining means comprises;

means for determining an angle θ

between said new effective camera position and said selected object in said current partial hierarchy; and

wherein said adjusting means adjusts an x coordinate of said new effective camera position to maintain said angle θ

with respect to said selected object as found in said new partial hierarchy fetched by said fetching means;

whereby, a user viewing said current partial hierarchy at said current camera position can navigate in a substantially straight line to a new navigator position.

16. A computer graphics system for navigating through partial hierarchies, comprising:

means for determining a new effective camera position (x,z) within a current partial hierarchy based on a new navigator position;

means for fetching a new partial hierarchy corresponding to said new effective camera position;

means for determining an orientation between said new effective camera position and

at least one reference object in said current partial hierarchy;

means for adjusting said new effective camera position to maintain said orientation with the said at least one reference object as found in said new partial hierarchy fetched by said fetching means;

means for converting said adjusted new effective camera position to a new camera position;

means for displaying a display view showing said fetched partial hierarchy layout in a field of view of a camera positioned at said new camera position;

means for permitting a user to mark at least one of a selected object or a selected location in said displayed partial hierarchy;

means for storing absolute coordinates for a mark that identifies a specific location; and

means for interpreting said absolute coordinates directly when a camera position is at approximately the same z coordinate position as a z coordinate of said absolute coordinates, and otherwise transforming said absolute coordinates to a coordinate system at the camera position;

whereby, a user viewing said current partial hierarchy at said current camera position can navigate in a substantially straight line to a new navigator position.

17. A computer program product comprising a computer useable medium having computer program logic recorded thereon for enabling a processor in a computer system to navigate through partial hierarchies, said computer program logic comprising:

means for enabling the processor to determine a new effective camera position (x,z) within a current partial hierarchy based on a new navigator position;

means for enabling the processor to fetch a new partial hierarchy corresponding to said new effective camera position;

means for enabling the processor to determine an orientation between said new effective camera position and at least one reference object in said current partial hierarchy;

means for enabling the processor to adjust said new effective camera position to maintain said orientation with the said at least one reference object as found in said new partial hierarchy fetched by said fetching means;

means for enabling the processor to convert said adjusted new effective camera position to a new camera position;

means for enabling the processor to display a display view showing said fetched partial hierarchy layout in a field of view of a camera positioned at said new camera position;

means for enabling the processor to permit a user to mark at least one of a selected object or a selected location in said displayed partial hierarchy;

means for enabling the processor to store absolute coordinates for a mark that identifies a specific location; and

means for enabling the processor to interpret said absolute coordinates directly when a camera position is at approximately the same z coordinate position as a z coordinate of said absolute coordinates, and otherwise to transform said absolute coordinates to a coordinate system at the camera position;

whereby, a user viewing said current partial hierarchy at said current camera position can navigate in an approximately straight line to a new navigator position.

18. A computer graphics system for navigating through partial hierarchies, comprising:

a hierarchy manager that determines a new effective camera position (x,z) within a current partial hierarchy based on a new navigator position, fetches a new partial hierarchy corresponding to the new effective camera position, determines an orientation between the new effective camera position and at least one reference object in said current partial hierarchy, adjusts the new effective camera position to maintain the orientation with the said at least one reference object as found in the new partial hierarchy, and converts the adjusted new effective camera position to a new camera position; and

a display that displays a display view showing said fetched partial hierarchy layout in a field of view of a camera positioned at said new camera position;

wherein said hierarchy manager determines an orientation between said new effective camera position and two reference objects in said current partial hierarchy; and

wherein said hierarchy manager finds two reference nodes in said current partial hierarchy, determines a point in front of said new effective camera position on a line intersecting the two reference nodes, calculates a proportion of the distance between the determined point and one of the two reference nodes, and adjusts an x coordinate of said new effective camera position to maintain said proportion with the one reference node as found in said new partial hierarchy;

whereby, a user viewing said current partial hierarchy at said current camera position can navigate in a substantially straight line to a new navigator position.

19. The system of claim 18, wherein said hierarchy manager fetches said new partial hierarchy from a cache of partial hierarchies or fetches said new partial hierarchy from an interpolator.

20. The system of claim 18, wherein said hierarchy manager generates said new partial hierarchy on the fly.

21. The system of claim 18, wherein said hierarchy manager allows a user to mark at least one of a selected object or a selected location in said displayed partial hierarchy.

22. The system of claim 21, wherein said hierarchy manager stores relative coordinates for a mark that identifies a location of said mark relative to coordinates for the selected object.

23. A computer graphics system for navigating through partial hierarchies, comprising:

a hierarchy manager that determines a new effective camera position (x,z) within a current partial hierarchy based on a new navigator position, fetches a new partial hierarchy corresponding to the new effective camera position, determines an orientation between the new effective camera position and at least one reference object in said current partial hierarchy, adjusts the new effective camera position to maintain the orientation with the said at least one reference object as found in the new partial hierarchy, and converts the adjusted new effective camera position to a new camera position; and

a display that displays a display view showing said fetched partial hierarchy layout in a field of view of a camera positioned at said new camera position;

wherein said hierarchy manager determines an orientation between said new effective camera position and one reference object in the current partial hierarchy; and

wherein said hierarchy manager finds one reference node in the current partial hierarchy, determines a displacement distance between said new effective camera position and the one reference node in said current partial hierarchy, and adjusts an x coordinate of said new effective camera position to maintain the displacement distance with respect to the one reference node as found in said new partial hierarchy;

whereby, a user viewing said current partial hierarchy at said current camera position can navigate in a substantially straight line to a new navigator position.

24. A computer graphics system for navigating through partial hierarchies, comprising:

a hierarchy manager that determines a new effective camera position (x,z) within a current partial hierarchy based on a new navigator position, fetches a new partial hierarchy corresponding to the new effective camera position, determines an orientation between the new effective camera position and at least one reference object in said current partial hierarchy, adjusts the new effective camera position to maintain the orientation with the said at least one reference object as found in the new partial hierarchy, and converts the adjusted new effective camera position to a new camera position; and

a display that displays a display view showing said fetched partial hierarchy layout in a field of view of a camera positioned at said new camera position;

wherein said hierarchy manager determines an angular orientation between said new effective camera position and one object selected for zooming in the current partial hierarchy; and

wherein said hierarchy manager determines an angle θ

between said new effective camera position and said selected object in said current partial hierarchy, and adjusts an x coordinate of said new effective camera position to maintain the angle θ

with respect to said selected object as found in said new partial hierarchy;

whereby, a user viewing said current partial hierarchy at said current camera position can navigate in a substantially straight line to a new navigator position.

25. A computer graphics system for navigating through partial hierarchies, comprising:

a hierarchy manager that determines a new effective camera position (x,z) whine a current partial hierarchy based on a new navigator position, fetches a new partial hierarchy corresponding to the new effective camera position, determines an orientation between the new effective camera position and at least one reference object in said current partial hierarchy, adjusts the new effective camera position to maintain the orientation with the said at least one reference object as found in the new partial hierarchy, and converts the adjusted new effective camera position to a new camera position; and

a display that displays a display view showing said fetched partial hierarchy layout in a field of view of a camera positioned at said new camera position;

wherein said hierarchy manager allows a user to mark at least one of a selected object or a selected location in said displayed partial hierarchy;

wherein said hierarchy manager stores absolute coordinates for a mark that identifies a specific location, interprets said absolute coordinates directly when a camera position is at approximately the same z coordinate position as a z coordinate of said absolute coordinates, and transforms said absolute coordinates to a coordinate system at the camera position;

whereby, a user viewing said current partial hierarchy at said current camera position can navigate in a substantially straight line to a new navigator position.