Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1997-04-25
2001-07-10
Nguyen, Phu K. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06259451
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to data visualization and data mining.
2. Problem Overcome By Invention
Electronic data is lifeblood for modern, technology-based society. Advances in computer and networking technology now provide access to an increasing volume and range of data. Businesses, government, and individuals must assimilate relevant information from larger amounts of data. The size, scope, and complexity of data can overwhelm human cognitive abilities. It is increasingly important that information be extracted from the data and presented to a user in a manner commensurate with human cognitive ability.
Virtual reality-based (VR) data visualizations now use hierarchies to represent large collections of complex data and data attributes. A hierarchy data visualization provides greater contextual information for electronic data in a single display view which is more easily assimilated by the human brain than conventional data displays. Data attributes are mapped into objects (or nodes) laid out in a hierarchy. Graphical attributes of the objects in the hierarchy, such as, color and height, also represent different data attributes. A hierarchy can arrange nodes according to a two-dimensional (2D) or three-dimensional (3D) display model representing a tree, perspective wall, cone tree (e.g., a cone tree by Xerox PARC), clusters, nets, links, and/or bar charts. See, Alan Wexelblat, Ed.,
Virtual Reality: Applications and Explorations
(Academic Press: MA; Publication Date, Jul. 1, 1993), Chapter 3, pages 45-74 (incorporated herein by reference).
Hierarchies become too complicated when faced with larger collections of complex data. An attempt to display global contextual information for complicated data can overwhelm or diminish a user's ability to focus on local aspects of the data visualization. Conversely, displaying detail on selected, local aspects of a data visualization masks display of global contextual information.
What is needed is a graphics display tool which optimizes data visualization. A virtual-reality (VR) data visualization is needed which conveys global and local contextual information even for large collections of complex data.
Effective navigation capability is also needed. A user must be able to navigate through a VR data visualization comfortably. Rich contextual information, including graphical attributes representative of data attributes, must be clearly presented to maximize the degree of interest to the user. The content and level of detail must be commensurate with a user's ability to perceive and absorb graphical display information.
Effective display of hierarchies which have a large aspect ratio is especially difficult. Hierarchies can be described with respect to a three-dimensional orthogonal coordinate system (x,y,z). The x coordinate dimension is parallel to the width dimension of a hierarchy, or in other words, left and right across a display screen. The y coordinate dimension is parallel to the height dimension of the hierarchy, or in other words, up and down a display screen. The z coordinate dimension is parallel to the line of sight of a user along a hierarchy toward a hierarchy horizon, or in other words, is perpendicular to the display screen (e.g., a positive z direction begins at the back of a hierarchy and extends forward along hierarchy toward the root node and a display screen).
Hierarchies with a large aspect ratio are relatively wide in the x-dimension compared to their depth in the z-dimension. Conventional techniques for laying out nodes in a hierarchy force room to be made for lower level nodes. When a hierarchy is initially generated, the positions of the bottom child nodes or leaf nodes are spread out across the width of a hierarchy. The positions of higher level parent nodes are then determined and distributed across the width of hierarchy. In this way, parent nodes have a separation dependent upon the number of child nodes in lower levels—even if the child nodes are not later rendered in a particular display view!
When a hierarchy is large, this separation of parent nodes in the complete hierarchy layout can limit the number of parent nodes which are seen effectively in a single display view. This drawback is most evident when trying to observe nodes in levels of a hierarchy closest to a given camera position.
For example,
FIG. 1
(not drawn to exact scale) shows a hierarchy
100
having four levels of nodes. According to conventional hierarchy generation techniques, each level of nodes is laid out in succession beginning at the bottom level, that is, Level
4
. Child nodes in Level
4
are positioned at approximately the same z coordinate position corresponding to Level
4
. The Level
4
nodes are distributed at different x coordinate positions across the hierarchy
100
. The Level
4
nodes are spaced approximately equally across the x coordinate dimension, although additional spaces can be added to further separate groups of child nodes that share a common respective parent node in Level
3
or above.
Nodes in Level
3
are then laid out along the width of the hierarchy
100
at the z coordinate position corresponding to Level
3
. The specific x coordinate positions of these nodes in Level
3
is approximately the average x coordinate position of corresponding child nodes laid out previously in Level
4
. Similarly, x coordinate positions of nodes in Levels
2
and
1
depends upon the average x coordinate position of corresponding child nodes previously laid out in the lower levels.
As mentioned above, the resulting separation of parent nodes in higher levels of a complete hierarchy layout can limit the number of parent nodes which are seen effectively in a single display view. For example, as shown in
FIG. 1
, a display view of hierarchy
100
that covers a width s
w
would only include the two inner nodes of Level
2
. This is especially true for display views beginning at effective camera positions located near Level
2
. Moving the camera position further back from the Level
2
nodes (that is, in a positive z-direction up along the hierarchy) allows more nodes to be included in a single display view; however, the nodes are then appear further away from the user making it more difficult to observe graphical attributes of the nodes and other local detail. Moreover, even if a user was only interested in viewing Levels
2
and
3
and wanted to hide the lower Level
4
, only the two inner nodes of Level
2
would be seen in camera positions taken close to Level
2
because the x coordinate positions of the nodes in Level
2
are separated based on the lower level children laid out in Level
4
.
Artificial perspective can added to compress the spacing of each node in the lower levels. For example, as described in U.S. Pat. No. 5,528,735, incorporated by reference above, the x coordinate of each node is compressed by a magnitude which is a function of the respective node's z coordinate (in other words, the distance of a level from a landscape base point X). Such artificial perspective can increase the number of nodes which are included in a display view; however, parent nodes are still separated based on room made in the hierarchy for lower level nodes.
SUMMARY OF THE INVENTION
As discovered by the inventor, what is needed is a method and system for generating a partial hierarchy such that parent nodes are not forced apart to make room for child nodes in all lower levels. Partial hierarchies need to be generated that allow a greater number of nodes closest to the user to be displayed without sacrificing quick and smooth navigation through the overall hierarchy. Only nodes lying within a predetermined depth from a user's effective camera position need to be laid out and stored for rendering in a single display view.
Further, as a user traverses through a hierarchy, space for lower nodes is allocated first, driving higher nodes apart. This apparent motion needs to be compensated for during navigation to provide a user with the pe
Nguyen Phu K.
Silicon Graphics Inc.
Sterne Kessler Goldstein & Fox
LandOfFree
Method, system, and computer program product for mapping... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, system, and computer program product for mapping..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system, and computer program product for mapping... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2541714