Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1998-07-29
2001-10-09
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06300957
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to mapping a node-link structure laid out in negatively curved space into a rendering space, such as for presentation on a display.
BACKGROUND AND SUMMARY OF THE INVENTION
Lamping, J. and Rao, R., “The Hyperbolic Browser: A Focus+Context Technique for Visualizing Large Hierarchies”,
Journal of Visual Languages and Computing
, Vol. 7, 1996, pp. 33-55, disclose techniques for laying out a hierarchy on a hyperbolic plane and then mapping the plane onto a Euclidean display region such as a unit disk. Initially, a tree has its root at the center or focus of the display region, but the display can be smoothly transformed to bring other nodes into focus. Changes of focus can be implemented by adjusting the focus of the mapping from the hyperbolic plane to the Euclidean plane, such as by a transformation in the hyperbolic plane that moves a new focus to the location that is mapped to the center of the unit disk. Lamping et al., U.S. Pat. No. 5,590,250, disclose similar mapping techniques in which a transformation is performed on positions in a layout space and the transformed positions are then mapped to obtain positions on a display; mapping is performed recursively, beginning at the root node.
Munzner, T., and Burchard, P., “Visualizing the Structure of the World Wide Web in 3D Hyperbolic Space”, in
Proceedings of the VRML
'95
Symposium
(San Diego, Calif., Dec. 13-16, 1995), ACM SIGGRAPH, 1995, pages 33-38 and 138, disclose techniques based on laying out an exhaustive subtree of a graph in standard hyperbolic space. Due to multiple images, sophisticated level-of-detail culling is required to render the view inside a manifold efficiently. The choice of an exhaustive subtree corresponds to choosing a root node and, for each other node, one incoming edge. Taking the tree that would be obtained by navigating out from the root node and attaching all children, a subtree can be selected by choosing a traversal order for the tree and then only retaining the first copy of each graph node. A graphical representation is constructed and written into a 3D data file, which is loaded into Geomview, a public domain 3D viewer.
The invention addresses problems in mapping a node-link structure laid out in a space with negative curvature, such as hyperbolic space, into a rendering space, such as a two dimensional space in which it can be displayed.
With the techniques described by Lamping and Rao and with other conventional mapping techniques for node-link structures laid out in negatively curved space, mapping begins at a fixed part of the structure, such as the root node of a directed graph or a node at the lowest level of a directed graph. Mapping from the root node or other fixed part can be inefficient, however, if the point of interest in the structure is distant from the fixed part at which mapping begins, since the region of the structure around the fixed part may be of only peripheral interest. Furthermore, the representation of a location far from the root may cause loss of numerical precision, leading to mispositioning the node when it is mapped near the center.
The invention alleviates mapping problems due to beginning from a fixed part by providing techniques that can begin mapping at any element within the structure. The techniques obtain data identifying a starting element within the structure. The techniques then locate the starting element at a starting position in rendering space. Then, for each of a set of other elements of the structure, the techniques map the element's position in the negatively curved space to a position in rendering space. The set of other elements includes at least a parent and a child of the starting element, and each element in the set is reachable from the starting element by a path that leads only through elements in the set. In mapping the position of each element in the set, the techniques use the element's position relative to the preceding element in the negatively curved space and the position of the preceding element in the rendering space to obtain the element's position in the rendering space.
The starting position in rendering space can correspond to a display region's focus, for example. If the display region is a circle, the starting position can correspond to its center. The space with negative curvature space can be the hyperbolic plane, and the rendering space can be the unit disk.
Data identifying the starting element can be obtained based on signals from a user. For example, a user signal can indicate a position in a display region that can be converted to a position in rendering space and used to obtain data identifying the starting element. Or the user signal can indicate the starting element, and can be used to obtain data identifying the starting element; the signal can also indicate the starting position. Or the user signal can indicate a change in the node-link structure and data can be obtained that identify a starting element that is not affected by the change.
Where the node-link structure is a tree, locating the starting element can include walking up to the root element of the node-link structure to obtain identifiers of elements on the path from the starting element to the root element. Then, the identifiers can be used to walk down to the starting element, using the starting orientation of the root element to obtain the starting element's orientation in rendering space.
In one implementation, the rendering space includes a bounded precision region within which elements can be mapped with adequate precision. Mapping can include walking upward on a path from the starting element, mapping each element on the path, until a first element is mapped outside the precision region. Then a second element that precedes the first element along the upward path can be selected as a mapping root within the precision region. Mapping can be performed by then walking downward from the mapping root, the set of other elements thus including only the mapping root and descendants of the mapping root. For example, the first and second elements can be nodes, and the second element can be the node immediately preceding the first element on the upward path.
In this implementation, a criterion can be applied to determine whether to map descendants of each element that is mapped. The criterion can include determining whether the element has descendants in the node-link structure. It can also include determining whether the element is in the precision region. It can also include determining, in relation to an active region such as a view within the precision region, whether the element is in the active region or its parent is outside the active region. In accordance with this criterion, if an element has no descendants, is outside the precision region, or is outside the active region with a parent inside the active region, it is not necessary to map its descendants.
The new techniques are advantageous because it is often possible to identify a starting node that will provide more efficient mapping than other nodes. For example, a user may select a node to be positioned at the display region's focus. As a result, mapping can be done more efficiently than if it always began at a fixed part of the structure, and operations that require repeated mappings in a short period of time, such as animation, can be done more effectively.
The new techniques are especially advantageous if data defining the layout of the node-link structure indicate positions relative to other nodes in negatively curved space rather than indicating absolute positions. For example, a node's position relative to its parent could be indicated. With relative position data, computation can be especially efficient.
The new techniques are also advantageous because they avoid precision problems that can result when mapping to a rendering space begins at a root node. If there are too many generations between the root node and a node of interest, the position of the node of interest in the negatively curved
Lamping John O.
Rao Ramana B.
Tenev Tichomir G.
Haynes Mark A.
Haynes Beffel & Wolfeld LLP
Inxight Software, Inc.
Sealey Lance W.
Zimmerman Mark
LandOfFree
Mapping a node-link structure to a rendering space beginning... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mapping a node-link structure to a rendering space beginning..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mapping a node-link structure to a rendering space beginning... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2574713