Method, system, and computer program product for mapping between an overview and a partial hierarchy

• US 6,259,451 B1
• Filed: 04/25/1997
• Issued: 07/10/2001
• 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): Nguyen, Phu K.
• Application Number:
  US08/845,426
• Time in Patent Office: 1,537 Days
• Field of Search: 345/419, 345/421, 345/422, 345/440, 707/512, 707/514, 707/516
• US Class Current: 345/419
• 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 mapping between a camera position in a three-dimensional 3D partial hierarchy and a camera position in a two-dimensional 2D overview of a complete hierarchy, the method comprising the steps of:

determining a 3D camera position (x,y,z) of a camera viewing the 3D partial hierarchy;

mapping a z coordinate of said 3D camera position to a y coordinate of a 2D camera position;

determining an orientation between said 3D camera position and at least one reference object in the 3D partial hierarchy; and

determining an x coordinate of said 2D camera position that maintains in the 2D overview, said orientation determined in said orientation determining step.

2. The method of claim 1, wherein said orientation determining step comprises the steps of:

finding two reference nodes in the 3D partial hierarchy,

determining a point in front of said 3D 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

said x coordinate determining step determines an x coordinate of said 2D camera position that approximately maintains said proportion with said one reference node as found in the 2D overview of a complete hierarchy.

5. The method of claim 1, wherein said partial hierarchy consists of a number levels, said number of levels being at least equal to a predetermined depth and less than a total number of levels included in the complete hierarchy.

6. The method of claim 1, wherein said partial hierarchy includes a bottom level, wherein parent nodes in said bottom level have segments of connection lines automatically extending toward child nodes not included in said partial hierarchy.

3. The method of 1, wherein said orientation determining step comprises the steps of:

finding one reference node in the 3D partial hierarchy, and

determining a displacement distance between said 3D camera position and said one reference node in said 3D partial hierarchy; and

said x coordinate determining step determines an x coordinate of said 2D camera position that approximately maintains said displacement distance with said one reference node as found in the 2D overview of a complete hierarchy.

4. The method of 1, wherein said orientation determining step comprises the steps of:

finding one reference node in the 3D partial hierarchy, and

determining an angle θ

between said 3D camera position and said one reference node in said 3D partial hierarchy; and

said x coordinate determining step determines an x coordinate of said 2D camera position that approximately maintains said angle θ

with said one reference node as found in the 2D overview of a complete hierarchy.

7. A computer-implemented method for mapping between a camera position in a two-dimensional 2D overview of a complete hierarchy and a camera position in a three-dimensional 3D partial hierarchy, the method comprising the steps of:

determining a 2D camera position (x,y) of a camera viewing the 2D overview of a complete hierarchy;

mapping a y coordinate of said 2D camera position to a z coordinate of a 3D camera position;

determining an orientation between said 2D camera position and at least one reference object in the 2D overview of a complete hierarchy; and

determining an x coordinate of said 3D camera position that maintains with respect to the 3D partial hierarchy, said orientation determined in said orientation determining step.

8. The method of claim 7, wherein said orientation determining step comprises the steps of:

finding two reference nodes in the 2D overview of a complete hierarchy,

determining a point in front of said 2D 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

said x coordinate determining step determines an x coordinate of said 3D camera position that approximately maintains said proportion with said one reference node as found in the 3D partial hierarchy.

9. The method of 7, wherein said orientation determining step comprises the steps of:

finding one reference node in the 2D overview of a complete hierarchy, and

determining a displacement distance between said 2D camera position and said one reference node in said 2D overview of a complete hierarchy; and

said x coordinate determining step determines an x coordinate of said 3D camera position that approximately maintains said displacement distance with said one reference node as found in the 3D partial hierarchy.

10. The method of 7, wherein said orientation determining step comprises the steps of:

finding one reference node in the 2D overview of a complete hierarchy, and

determining an angle θ

between said 2D camera position and said one reference node in said 2D overview of a complete hierarchy; and

said x coordinate determining step determines an x coordinate of said 3D camera position that approximately maintains said angle θ

with said one reference node as found in the 3D partial hierarchy.

11. A computer graphics system for mapping between a camera position in a three-dimensional 3D partial hierarchy and a camera position in a two-dimensional 2D overview of a complete hierarchy, the system comprising:

a determiner that determines a 3D camera position (x,y,z) of a camera viewing the 3D partial hierarchy;

a mapper that maps a z coordinate of said 3D camera position to a y coordinate of a 2D camera position;

an orientation determiner that determines an orientation between said 3D camera position and at least one reference object in the 3D partial hierarchy; and

an x coordinate determiner that determines an x coordinate of said 2D camera position that maintains in the 2D overview said orientation determined by said orientation determiner.

12. The system of claim 11, wherein said orientation determiner comprises:

a finder that finds two reference nodes in the 3D partial hierarchy,

a point determiner that determines a point in front of said 3D camera position on a line intersecting said two reference nodes, and

a calculator that calculates a proportion of the distance between said determined point and one of said two reference nodes; and

said x coordinate determiner determines an x coordinate of said 2D camera position that approximately maintains said proportion with said one reference node as found in the 2D overview of a complete hierarchy.

13. The system of 11, wherein said orientation determiner comprises:

a finder that finds one reference node in the 3D partial hierarchy, and

a displacement distance determiner that determines a displacement distance between said 3D camera position and said one reference node in said 3D partial hierarchy; and

said x coordinate determiner determines an x coordinate of said 2D camera position that approximately maintains said displacement distance with said one reference node as found in the 2D overview of a complete hierarchy.

14. The system of 11, wherein said orientation determiner comprises:

a finder that finds one reference node in the 3D partial hierarchy, and

an angle determiner that determines an angle θ

between said 3D camera position and said one reference node in said 3D partial hierarchy; and

said x coordinate determiner determines an x coordinate of said 2D camera position that approximately maintains said angle θ

with said one reference node as found in the 2D overview of a complete hierarchy.

15. A computer graphics system for mapping between a camera position in a two-dimensional 2D overview of a complete hierarchy and a camera position in a three-dimensional 3D partial hierarchy, the system comprising:

a determiner that determines a 2D camera position (x,y) of a camera viewing the 2D overview of a complete hierarchy;

a mapper that maps a y coordinate of said 2D camera position to a z coordinate of a 3D camera position;

an orientation determiner that determines an orientation between said 2D camera position and at least one reference object in the 2D overview of a complete hierarchy; and

an x coordinate determiner that determines an x coordinate of said 3D camera position that maintains with respect to the 3D partial hierarchy, said orientation determined by said orientation determiner.

16. The system of claim 15, wherein said orientation determiner comprises:

a finder that finds two reference nodes in the 2D overview of a complete hierarchy;

a determiner that determines a point in front of said 2D camera position on a line intersecting said two reference nodes, and

a calculator that calculates a proportion of the distance between said determined point and one of said two reference nodes; and

said x coordinate determiner determines an x coordinate of said 3D camera position that approximately maintains said proportion with said one reference node as found in the 3D partial hierarchy.

17. The system of 15, wherein said orientation determiner comprises:

a finder that finds one reference node in the 2D overview of a complete hierarchy; and

a displacement distance determiner that determines a displacement distance between said 2D camera position and said one reference node in said 2D overview of a complete hierarchy; and

said x coordinate determiner determines an x coordinate of said 3D camera position that approximately maintains said displacement distance with said one reference node as found in the 3D partial hierarchy.

18. The system of 15, wherein said orientation determiner comprises:

a finder that finds one reference node in the 2D overview of a complete hierarchy; and

an angle determiner that determines an angle θ

between said 2D camera position and said one reference node in said 2D overview of a complete hierarchy; and

said x coordinate determiner determines an x coordinate of said 3D camera position that approximately maintains said angle θ

with said one reference node as found in the 3D partial hierarchy.

19. A computer program product comprising a computer useable medium having computer program logic recorded thereon for enabling a processor in a computer system to map between a camera position in a three-dimensional 3D partial hierarchy and a camera position in a two-dimensional 2D overview of a complete hierarchy, said computer program logic comprising:

a determiner that enables the processor to determine a 3D camera position (x, y, z) of a camera viewing the 3D partial hierarchy;

a mapper that enables the processor to map a z coordinate of said 3D camera position to a y coordinate of a 2D camera position;

an orientation determiner that enables the processor to determine an orientation between said 3D camera position and at least one reference object in the 3D partial hierarchy; and

an x coordinate determiner that enables the processor to determine an x coordinate of said 2D camera position that maintains in the 2D overview, said orientation determined by said orientation determining means.

20. A computer graphics system for mapping between a camera position in a three-dimensional 3D partial hierarchy and a camera position in a two-dimensional 2D overview of a complete hierarchy, the system comprising:

means for determining a 3D camera position (x,y,z) of a camera viewing the 3D partial hierarchy;

means for mapping a z coordinate of said 3D camera position to a y coordinate of a 2D camera position;

means for determining an orientation between said 3D camera position and at least one reference object in the 3D partial hierarchy; and

means for determining an x coordinate of said 2D camera position that maintains in the 2D overview said orientation determined by said orientation determining means.

21. A computer graphics system for mapping between a camera position in a two-dimensional 2D overview of a complete hierarchy and a camera position in a three-dimensional 3D partial hierarchy, the system comprising:

means for determining a 2D camera position (x,y) of a camera viewing the 2D overview of a complete hierarchy;

means for mapping a y coordinate of said 2D camera position to a z coordinate of a 3D camera position;

means for determining an orientation between said 2D camera position and at least one reference object in the 2D overview of a complete hierarchy; and

means for determining an x coordinate of said 3D camera position that maintains with respect to the 3D partial hierarchy, said orientation determined by said orientation determining means.

22. A computer program product comprising a computer useable medium having computer program logic recorded thereon for enabling a processor in a computer system to map between a camera position in a three-dimensional 3D partial hierarchy and a camera position in a two-dimensional 2D overview of a complete hierarchy, said computer program logic comprising:

means for enabling the processor to determine a 3D camera position (x, y, z) of a camera viewing the 3D partial hierarchy;

means for enabling the processor to map a z coordinate of said 3D camera position to a y coordinate of a 2D camera position;

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

means for enabling the processor to determine an x coordinate of said 2D camera position that maintains in the 2D overview, said orientation determined by said orientation determining means.

23. A computer-implemented method for mapping between a camera position in a three-dimensional 3D partial hierarchy and a camera position in a two-dimensional 2D overview of a complete hierarchy, the method comprising the steps of:

determining a 3D camera position of a camera viewing the 3D partial hierarchy;

mapping a first 3D coordinate of said 3D camera position to a first 2D coordinate of a 2D camera position;

determining an orientation between said 3D camera position and at least one reference object in the 3D partial hierarchy; and

determining a second 2D coordinate of said 2D camera position that maintains in the 2D overview, said orientation determined in said orientation determining step.