JOVE Project: 3D Tree-Mapped Universes and Data Sphere Navigation, A Method to Increase the Density of Hierarchical Information Visualization in a Finite Display Space. Authors : Pery Pearson e-mail:pery@hprnd.rose.hp.com, Hewlett-Packard Co., Joe Steinmetz e-mail:joes@core.rose.hp.com, Hewlett-Packard Co. Date : 12/05/93 ABSTRACT A three-dimensional universe of tree-mapped data is proposed that uses unique navigation techniques and animation to provide a density increase in visualization. Some of the limitations of tree-maps and cone trees are addressed while preserving their benefits. In addition, "universal" navigation is presented in a way that promotes context identification rather than disorientation. Possible future extensions are introduced in the concluding sections. INTRODUCTION The world that we live and work in contains vast amounts of growing hierarchical information. As information users we strive to understand and utilize these information spaces. As humans we are capable of recognizing and comprehending spatial information and patterns by visualization [1]. The presentation of the information must allow the user to concentrate cognitive skills on the visualization for the purpose of comprehension, not context perception and information space navigation. Two methods have been defined to handle large hierarchical information structures: Tree-maps [1] and Cone trees [3]. Both of these visualization methods are important to understand before introducing a new visualization technique, 3D Tree-Mapped Universes and Data Sphere Navigation, which combines and expands upon these methods. TREE-MAPS Tree-maps provide a method for the visualization of hierarchical information through the use of a space-filling two-dimensional (2D) rectangular mapping algorithm. The space-filling approach allows for a one hundred percent utilization of the available display area. Tree-maps work by partitioning the display area into a set of rectangular boxes or nodes that represent a tree structure. This is done using a slice and dice algorithm which works to partition the display area in both dimensions[2]. The information hierarchy is presented as a series of recursively-drawn boxes, where the bounding dimensions are a result of slicing along the X and Y axes. The nodes within a bounding box are dependent upon a node's contents; thus the size of an individual node depends upon the overall size of the tree structure (see figure 1, infoviz1.gif). It is clear that this approach does utilize the display area in an efficient manner. Content information is explicitly displayed at the leaf level nodes and is under interactive control. Color as well as sound can be used to convey node information. The dense data visualization capability of the tree-map algorithm comes at a cost. The structural information is implicitly defined rather than displayed in an explicit manner. Depending upon the type of data, user familiarity with tree-maps, and tree density, this may or may not be a problem. As the volume of information increases, even tree-map visualization techniques have problems displaying all of the data; some information is lost simply because the display area is limited. Some recent improvements in tree-maps have explored navigation as a means to increase the density of data that can be visualized [2]. These techniques include zooming, panning, and animation. Although the zooming technique can increase the volume of information that can be visualized, if not carefully implemented, it can cause the user to become lost within the structure or require additional cognitive skills that could have been used for comprehension. These techniques are not consistently effective in all tree-map applications and cannot be relied upon as a means to increase the density of data to be displayed. The tree-map technique has been used to visualize hierarchical file structures in the TreeViz application [7]. Other potential applications include: an organizational structural browser, library Dewey decimal system holdings visualizer, stock portfolio profit loss viewer, and a software performance tuning viewer [5]. Some of the features of tree-maps that we find appealing are the use of simple 2D graphics to provide full use of the display area and interactive manipulation of color and depth bounds. Another feature of Tree-maps is the ability to convey spatial relationships of data; i.e. file A is larger than file B. One of the things we felt that tree-maps lacked was the ability to naturally display structural information explicitly. Recent improvements like the top-down algorithm have allowed for structure information to be displayed in an explicit way by using up some of the display space for this purpose [2]. It is our opinion that the tree-map algorithm makes such efficient use of the display area that the user can feel overwhelmed by the densely packed screen; this should become less of a problem as the user gains familiarity with tree-maps. Although zooming has been implemented in certain tree-map applications [2], it is our opinion that tree-map technology lacks an effective zooming method which prevents user disorientation. Also, current tree-map technology does not support the ability to view multiple data sets simultaneously. CONE TREES Cone trees were developed as part of a visualization package called the Information Visualizer; a cone tree is only one of many techniques for information visualization described in [4]. This method utilizes three- dimensional (3D) representations to make efficient use of the available display area as well as allow the data structure to be viewed in its entirety. The cone tree structure is also animated to provide for easier perception. The use of animation trys to exploit the human perceptive system which results in using less cognitive power. The basic structure of a cone tree is a hierarchical information structure that is uniformly spread out in three dimensions (see figure 2, infoviz2.gif). The top of the hierarchy is placed near the ceiling, and the children are positioned uniformly below the parent in a cone structure. This continues until all nodes are displayed. The aspect ratio of the cone structure is fixed to the screen size. This means that as the density of data increases, the visualization data must be compressed and adjusted such that it fits into the available display area. The cone structure is transparently shaded to allow visualization of all nodes, even those that would normally be blocked by other cones or nodes. Light cues allow for better depth perception. Shadowing helps convey additional information about the structure. Nodes are selected using a mouse. As selection occurs, the cone tree rotates such that the selected node and its parent path to the root are displayed and highlighted; this is a form of navigation. The rotation speed of the cone is such that the user can easily track the movement. The Information Visualizer implementation of cone trees offers the capability to cut, hide, focus, and reposition the tree. This visualization technique has been used as a file browser to display 600 Unix directories and the 10,000 associated files as well as an organization structure browser. Cone trees are currently limited to roughly 1000 nodes, 10 layers, or a branching factor of 30 [3]. Cone trees work well with unbalanced hierarchies over balanced ones due to the non-uniform appearance of the sub-trees with respect to each other. Some of the features of cone trees that we find appealing are their use of 3D graphics to provide efficient use of the display area, smooth animation, shading and lighting techniques, interactive manipulation, and explicit visualization of the hierarchical structure. Cone trees are definitely the "Cadillac" of non-standard visualization packages. Some of the shortcomings of cone trees are their lack of ability to visually convey spatial relationships like the tree-map structures and their large computational requirements. The 3D rendering of cone trees is computationally intensive compared to that of tree-maps. Cone trees are not capable of displaying multiple hierarchical data structures, and current cone tree zooming techniques do not prevent user disorientation. DATA SPHERE DEFINITION A data sphere is a semi-transparent, spherical object with two-dimensional data mapped onto its surface. To aid in viewing all of the data on its surface, a data sphere is rotated in space. For 2D viewing purposes, the three-dimensional data sphere is projected onto a 2D area; animation, and light sources with natural shading and shadowing aid in maintaining the user's perception of the data sphere's third dimension. Though not entirely visible at one time, a rotating data sphere is able to display more data in a given area than static 2D views. Using the spherical mapping discussed in a later section, Pi or about 3 times the amount of data can be displayed on a sphere of radius R as can be displayed in a square of 2R by 2R dimensions. There is increased distortion towards the poles of the data sphere using this mapping, but with orthogonal rotation, a second rotational axis perpendicular to and rotating slower than the primary axis, all data will pass by the foreground equatorial region with little distortion; a cylinder could be rotated with no vertical distortion, but a sphere is felt to be much more intuitive and symmetric; further investigation is needed to determine if a sphere is more or less intuitive than a cylinder for this purpose. A data sphere is also semi-transparent with data on the far side of the sphere visible behind the brighter, more distinct foreground side. Data sphere parameters can be varied and include primary and orthogonal rotation speeds and the amount of transparency. UNIVERSAL NAVIGATOR AND VIEWER OVERVIEW The prototype universal navigator and viewer is composed of four main sections: three data spheres and the zoom window which is an expanded two-dimensional view of a selected data area. (see the text figure below or the corresponding image, infoviz3.gif. Note that this image is simulated). Animation plays a major role in reducing the cognitive load on the user by graphically flowing from one state to the next and should be utilized wherever possible, especially when selecting objects [4]; e.g. some graphical interfaces show an expanding box when a file icon is opened, showing the flow from a file icon into a window. The three data spheres or views are used for data navigation while the zoom window is used for viewing data at various levels of detail. _ _ _ /a\ /b\ /c\ :a=rotating universe data sphere \_/ \_/ \_/ :b=rotating world data sphere ------------- :c=static world data sphere | zoom | (associated GIF image: infoviz3.gif) | window | ------------- The first sphere on the top left represents the "universe" of data sets which are seen as labeled spherical objects within the universe view and connected to each other as appropriate. The spheres within the universe view rotate about the vertical axis through the center of the universe view at a selectable rate with or without orthogonal rotation. Spheres which are farther away have a lower luminosity, and can be seen through any foreground spheres since they are semi-transparent. When a spherical object is selected, it becomes highlighted, and an expanded view of it is shown in the world data view; this selection can be animated to transform and expand a copy of the smaller sphere from within the universe view to the world data sphere. Primary and orthogonal rotation rates of the universe view are controlled by graphical widgets when the universe sphere or any of its smaller spheres are selected with the mouse. The top middle data sphere represents an expanded view of any data sphere selected within the universe view. This sphere is called the world data sphere or world view and has data mapped onto its surface; refer to the next section for details of this mapping. The world data sphere rotates about the vertical axis through its center at a selectable rate with or without orthogonal rotation. Data mapped nearer the poles becomes increasingly distorted, but orthogonal rotation allows all data to pass by the equator where data may be viewed with minimal distortion. Data on the far side of the sphere is visible through the semi-transparent foreground data at a lower luminance so all data may be viewed. Any selected area on the world data sphere is expanded and mapped to the 2D zoom window; area selection is described below in more detail. Primary and orthogonal rotation rates are controlled using graphical widgets which become active when the world data sphere is selected with the mouse. The third data sphere which is in the top right of the screen is the static world data sphere or static world view. The static world data sphere is merely a non-rotating version of the rotating world data sphere in the top middle of the screen. Any selected area on the rotating world data sphere is also selected and shown highlighted in the center foreground of the static world data sphere. The static world view's main purpose is to provide an easier means of selecting a data area. It is easier to use a mouse to click in one spot and drag an outline box around desired data if the data is not moving about at the time. This feature could be combined into the rotating world data sphere by freezing its rotation, but having data continuously animated is felt to reduce the user's cognitive load. The static world data sphere may be rotated about the X, Y, or Z axes in small increments by clicking the mouse on rotation widgets; this allows for a more precise positioning of data prior to selection. By clicking the mouse on a single point on the rotating world data sphere, the corresponding point on the static world data sphere is centered in the foreground. Though the selected data area is typically frozen, the selection rectangle may optionally be detached from the data such that the data/sphere moves under the geostationary satellite-like selection area. To aid visualization, when an area on the static world data sphere is selected, a copy of this area is peeled off of the sphere and transformed or morphed until it fits into the zoom window. The zoom window contains data which has been selected on the static world data sphere. As the selection area is changed, so is the zoom window data. The reverse is also true; if the zoom window is scaled in or out or shifted, both world data sphere and static world data sphere selection areas smoothly change size and position to match the new data size. The graphical widgets used to vary primary and orthogonal rotation rates also control the zoom window data position when selected. The zoom window is much like a standard tree-map, though other forms of data representation might also be implemented. HOW TO MAP 2D DATA ONTO A SPHERE One method of mapping a rectangle of X units wide by Y units high onto a sphere uses nested loops around a mapping function; projection of this 3D object onto a 2D screen is a separate task not covered here. The nested loops map the rectangle onto the sphere by wrapping one line of the rectangle in a circle about a given latitude of the sphere; the inner loop circles the sphere, and the outer loop moves the circle from the top of the sphere to the bottom. Distortion is greatest at the poles where an entire line of the rectangle maps to a single point. The core mapping function is a Cartesian to 3D polar coordinate function like: SPHERE(theta, phi) = RECTANGLE_ARRAY([Xmax/2Pi]*theta, [Ymax/Pi]*phi) where Xmax = X-1, Ymax = Y-1, theta is an angle in radians which traces a latitudinal circle, and phi is an azimuth angle ranging from the north to the south pole Though the mapping equations are relatively simple, the rotational transformations and animation of 2D-projected 3D objects at a reasonable frame rate of at least 12fps will require a powerful graphics-oriented compute engine. STRENGTHS AND WEAKNESSES The purpose of the 3D Data Sphere Navigation technique is to improve upon the visualization properties of both tree-map and cone tree technologies. We felt that both techniques had particular strengths that we wanted to maintain in our approach as well as weaknesses that we wanted to solve. The lists below show the various strengths and weaknesses of both tree-maps and cone trees. Tree-maps --------------------------------------------------------------------------- Strengths + simple 2D graphics to provide full use of the display area + interactive manipulation + the capability to visually convey spatial relationships Weaknesses - no natural way to display structural information explicitly - the user can become overwhelmed by the densely-packed screen - lacks an effective zooming (navigation) method which prevents disorientation - viewing multiple data sets is not supported; i.e. multiple worlds Cone Trees --------------------------------------------------------------------------- Strengths + 3D graphics provide efficient use of the display area + smooth animation with shading and lighting techniques + interactive manipulation + explicit structural information + somewhat intuitive Weaknesses - computationally intensive - lacks the capability to visually convey spatial relationships - viewing multiple data sets is not supported; i.e. multiple worlds - zooming can result in disorientation or loss of context (gardening [3]) The following section briefly summarizes the strengths and weakness of the visualization technique, 3D Data Sphere Navigation. 3D Data Sphere Navigation --------------------------------------------------------------------------- Strengths + 3D graphics provide efficient use of the display area + smooth animation with shading and lighting techniques + zooming with no loss of context + viewing multiple data sets is supported + more data can be displayed (increased density over current tree-maps and cone trees) + intuitive visualization + is extendable to an immersive, interactive virtual reality interface with few changes Weaknesses - data is distorted at spherical poles due to increased data density (orthogonal rotation addresses this) - visualization display space is traded for navigation display space - complex 3D graphics - computationally intensive - lacks the capability to explicitly show structural information (the same as tree-maps) FUTURE DIRECTION As the data size grows, individual fields on a data sphere will become increasingly difficult to distinguish. Given below are several methods which can be used to enhance data visualization. To alleviate the spherical distortion, a fisheye view or cylinder can be used. The center foreground of the sphere can be distorted to expand any data passing under this central area. The amount of this fisheye distortion could be varied as desired to view a larger or smaller area of undistorted data.[6] Though it may increase perceptual difficulty, an option to switch between a sphere and a cylinder is capable of reducing the vertical distortion of data. With visual cues like shading and shadowing, an extra dimension of elevation can be added to the data mapped onto a data sphere. Animation will help in perceiving elevation differences. The zoom window, however, would have to be modified to allow the user to see the various elevations. One method is to be able to tilt the zoom window data in 3D space so that the user can view the data as a 3D topological map and be able to transpose and rotate the plane of data. The 3D aspects of universal navigation could work quite well with virtual reality; a virtual reality modification would be to have the data spheres in the user's virtual lap for an overview by which to navigate through the data and maintain the user's orientation. The zoom window would either fill the user's field of view or not be needed since the user could sit inside of the world sphere, viewing the data on its rotating surface. CONCLUSION This paper proposes a visualization concept that uses unique navigation techniques and animation to provide an increase in visual data density in a way that promotes context identification rather than disorientation. This concept offers several advantages over traditional tree-maps and cone trees, including a density increase, multiple visible data sets, zooming with no loss of context, and an intuitive presentation environment. These advantages have not been formally verified and are offered as a hypothesis for further investigation. It is believed that the techniques discussed in this paper can extend visualization capabilities beyond what is offered by current methods, allowing greater tree size and depth to be perceived at a given time. Virtual reality can further stretch the inherent limitations of information visualization by immersing the user within a sphere of data. ACKNOWLEDGEMENTS/REFERENCES We would like to thank Ben Shneiderman and George G. Robertson for allowing us to use images from their papers. We would also like to thank Kim McGoff and Brian Bohmueller for their excellent suggestions and time in reviewing this paper. [1]: Brian Johnson and Ben Shneiderman, Tree-Maps: A Space-Filling Approach to the Visualization of Hierarchical Information Structures, Proc. IEEE Visualization '91 (San Diego, CA, Oct 1991), 284-291. [2]: David Turo and Brian Johnson, Improving the Visualization of Hierarchies with Treemaps: Design Issues and Experimentation, IEEE, 1992, 124-131. [3]: George G. Robertson, Jock D. Mackinlay, and Stuart K. Card, Cone Trees: Animated 3D Visualizations of Hierarchical Information, ACM, 1991, 189-194. [4]: George G. Robertson, Stuart K. Card, and Jock D. Mackinlay, Information Visualization Using 3D Interactive Animation, Communications of the ACM, 1993, Vol 36. No. 4., 57-71. [5]: Ben Shneiderman, Tree Visualization with Tree-Maps: 2-d Space-Filling Approach, ACM transactions on Graphics, Vol. 11, No. 1, Jan 1992, 92-99. [6]: G. W. Furness, Generalized fisheye views, Proceedings of SIGCHI'86, 1986, 16-23. [7]: Brian Johnson, TreeViz: Treemap Visualization of Hierarchically Structured Information, Proc. ACM CHI'92, 369-370. CREDITS The basic ideas and brainstorming for this paper were joint efforts, but the main sections were written as follows: Joe: Introduction, Tree-maps, Cone Trees, and Strengths and Weaknesses Pery: Data Sphere Definition, UNAV Overview, Futures, and editor List of Images -------------- infovis1.gif : Cone Tree example, figure 1 infovis2.gif : Tree-map example, figure 2 infovis3.gif : Prototype Universal Navigator/Viewer example, figure 3