US20080034326A1 - Systems and methods for creating an interactive 3d visualization of indexed media - Google Patents

Abstract

A 3D graphical user interface includes a two-dimensional ground-plane layout representing the relationship between one or more leaf elements of a tree data structure The interface further includes at least one building-like structure, each of the at least one building-like structures corresponding to a respective one of the one or more leaf elements. Each of the at least one building-like structure provides a summary of media associated with the respective one of the more leaf elements corresponding to that at least one building-like structure.

Description

BACKGROUND OF THE INVENTION
• 1. Field of Invention
• This invention relates to systems and methods for creating an interactive 3D visualization that indexes media and summarizes the indexed media.
• 2. Description of Related Art
• Based on increases in conventional computing speed and resource management, three-dimensional media indices are just recently becoming viable means for indexing a large amount of related media. However, the complexity of the index and information about the indexed media conveyed by the three-dimensional indices is rather limited.
• For instance, SGI FSN is a file system navigator with a 3D landscape visualization. Directories are placed in a hierarchical tree layout in the landscape. Each directory in SGI FSN is represented by a pedestal. The size of the files in the directory is proportional to the pedestal height and the file age is shown by color. Files are placed on top of the directory pedestals. Each file is represented by a box.
• U.S. patent application [Attorney Docket 114890] describes a method for creating and updating interactive 3D visualizations of media indices wherein separate indices are located above and below a ground plane. The indices are organized in a table structure defined by two axes and provide links to the media that is indexed. Various visual characteristics of the indices reflect characteristics of the media that is indexed as well as various user defined or group defined information relating to the indexed media.
• Perspective Wall is a 3D visualization that indexes files. It utilizes a 3D wall with three sections and displays card icons for the files. 3D/Rooms is a 3D index that has a 3D multi-level building floor plan in which users can select a research group and retrieve photos of members and their offices.
• Finally, There are many visualizations of the World Wide Web using 3D landscapes. Most of these such as WWW3D, WebPath, and VR-VIBE use abstract geometric objects to represent documents. The Web Forager, utilizes a space that contains 3D bookcases and 3D books, that when opened, display the indexed Web pages.
SUMMARY OF THE INVENTION
• Each of the above-described systems for indexing media within a three-dimensional space shares a similar shortcoming. Particularly, a user is only able to discern very general, if any, qualities of the indexed media from the visualization itself. For example, according to U.S. patent application [Attorney Docket 114890] a user can determine how the media is classified within two axes or determine whether or not the media indexed is one of or a combination of graphics, text, video, etc. However, none of the above-described systems summarize the indexed media within the summary itself, such that a user can view a summary of the indexed media simply by viewing the 3D visualization of the indexed media.
• Therefore, various exemplary embodiments of the systems, methods, and graphical user interfaces according to this invention provide an interactive 3D visualization wherein the surfaces of 3D objects representing indexed media provide visual summaries of the indexed media.
• Various exemplary embodiments of the systems and methods according to this invention provide a 3D graphical user interface including a two-dimensional ground-plane layout representing the relationship between one or more leaf elements of a tree data structure; and at least one building-like structure, each of the at least one building-like structures corresponding to a respective one of the one or more leaf elements, wherein each of the at least one building-like structure provides a summary of media associated with the respective one of the more leaf elements corresponding to that at least one building-like structure.
• Various exemplary embodiments of the systems and methods according to this invention provide a layout for a 3D visualization including inputting a tree data structure, each leaf of the tree associated with one or more forms of media; determining a plurality of candidate layouts; comparing the plurality of candidate layouts; selecting a solution layout; and constructing a 3D visualization based on the layout, wherein the representation of each leaf within the 3D visualization provides a summary of the media contained by that leaf within the input tree data structure.
BRIEF DESCRIPTION OF THE DRAWINGS
• Various exemplary embodiments of systems and methods according to this invention will be described in detail, with reference to the following figures, wherein:
• FIGS. 1 and 2 show an exemplary embodiment of a 3D visualization that utilizes substantially square and similarly sized building-like structure plots;
• FIGS. 3-6 show a number of variations of the 3D visualization shown inFIGS. 1 and 2;
• FIGS. 7 and 8 show an exemplary embodiment of a 3D visualization according to this invention that utilizes differently sized building-like structure plots;
• FIG. 9 shows a graphical user interface for use with the 3D visualizations of FIGS.1-6;
• FIG. 10 shows a graphical user interface for use with the 3D visualization ofFIGS. 7 and 8;
• FIGS. 11 and 12 are a flowchart outlining an exemplary embodiment of a grid layout method for the type of 3D visualizations shown inFIGS. 1-6.
• FIG. 13 shows an example of leaf nodes layouts and branch nodes layouts;
• FIG. 14 shows the layouts ofFIG. 13 in which the leaf node layouts are combined into a single layout;
• FIG. 15 shows an example of the layouts ofFIG. 14 combined into larger layouts;
• FIG. 16 shows an exemplary embodiment of a functional block diagram of a 3D visualization system;
• FIGS. 17-21 are a flowchart outlining an embodiment of a method for determining layout for the type of 3D visualizations shown inFIGS. 7 and 8; and
• FIG. 22 shows an exemplary embodiment of a functional block diagram of a 3D visualization system.
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
• FIGS. 1 and 2 show an exemplary embodiment of a3D visualization100 according to this invention that utilizes substantially square and similarly sized building-like structure plots.
• As shown inFIGS. 1 and 2, the 3D visualization utilizes a city metaphor in which each amount of media, indexed by a leaf in a tree data structure, is represented by a building-like structure120. According to this exemplary embodiment, the indexed media is video. However, any other media such as text, graphics, charts, etc. may be used. The indexed media is summarized on theroof122 andwalls124,126, and128 (rear not shown) of the buildings such that a user navigating the 3D visualization has an idea of the contents of each leaf without having to access that leaf. In various exemplary embodiments, theroof122 andsides124,126,128 (rear not shown)of the buildings display the same summary. Alternatively, each of theroof122 andsides124,126,128 (rear not shown) have different summaries. In various exemplary embodiments, a video is summarized by arranging key frames of the video in a predefined rectangular area (here defined by the height and width of the sides and roof of the buildings). FXPAL-IP-98-018 and U.S. patent application Ser. No. 10/392,822 describe methods for automatic video summary using key frames and are incorporated herein by reference in their entirety. Key frame video summaries work particularly well within the context of a city metaphor because each of the summary's frames resemble windows on the side of the building-like structures.
• As shown inFIGS. 1 and 2, and consistent with the city metaphor, each building-like structure120 exists on alot110 wherein acurb width140 is the distance from the building-like structure to a road. In various exemplary embodiments, the curb width is inversely proportional to a numerical value associated with each indexed portion of the media. For instance, the numerical value may represent the length of the video or an importance of the video determined by the user, or a predefined group of users. As such, the indexed portions of media that have the higher numerical values will have a smaller curb width and the building-like structure will be larger.
• It should be appreciated that, in other exemplary embodiments of the 3D visualization according to this invention, the numerical value may be directly proportional to the building-like structure's foot print. However, in practice this may result in building-like structures that are too thin to effectively summarize their respectively indexed media, or building-like structures that are too wide and obstruct a user's view of other buildings.
• As shown inFIGS. 1 and 2, and consistent with a city metaphor, a road separates eachlot110. In various exemplary embodiments, the road width (e.g.,130,132) represents the distance between the respective indexed media portions within the underlying tree data structure. For example,lots110 that are separated by roads with aroad width130 are closer to one another within the tree data structure (e.g., leaves) thanlots110 that are separated by roads with road width132 (e.g., braches).
• Furthermore, in various exemplary embodiments, the height250 of each building-like structure is proportional to a numerical value associated with each indexed portion of the media. For instance, the numerical value may represent the length of the video or an importance of the video determined by the user, or a predefined group of users.
• In various exemplary embodiments, as shown inFIG. 1, text may be included in the visualization to providelabels150 for various groups of indexed media. In various exemplary embodiments, these labels float over the building-like structures to simulate clouds, consistent with a city metaphor.
• FIGS. 3-6 show a number ofexemplary variations300,400,500, and600 of thevisualization100 shown inFIGS. 1 and 2. According to thevariations300,400,500, and600, each leaf represented by a building-like structure is summarized by up to four types of media (single video frames310,key frame summaries410,slide images510 and text610). In eachexemplary variation300,400,500, and600, a different type of media is displayed on the roof In various exemplary embodiments of the invention, the type of media that most effectively summarizes the indexed media portion is displayed on the roof because, typically, the roof is most visible from viewpoints in which all or many of the building-like structures are visible.
• FIGS. 7 and 8 show an exemplary embodiment of a 3D visualization according to this invention that utilizes differently sized building-like structure plots wherein the size of each building-like structure's plot is proportional to some numerical quality of the index media represented by that building-like structure.
• Similar to the previously described embodiments ofFIGS. 1-6, the building-like structures have curb widths and building heights that are proportional to some numerical qualities of the indexed media portion (leaf) represented by the building-like structures. Again, similar to the previously described embodiments,FIG. 7 showsroad widths732 that represent the distance between the respective indexed media portions within the tree structure.
• As shown inFIGS. 7 and 8, according to this exemplary embodiment theplots710 of each building-like structure for each leaf are arranged intolarger plots740,760 wherein eachlarger plot740,760 includes all of the plots representing its subnodes according to the underlying tree data structure (e.g.,leaf plot710 is contained nlarger plot740 which is contained in larger plot760). Text may be included in the visualization to providelabels150 for various groups of indexed media. In various exemplary embodiments, theselabels150 float over the building-like structures to simulate clouds, consistent with a city metaphor.
• In order to facilitate the use of the above-described 3D visualization according to various exemplary embodiments of the invention as a graphical user interface, various exemplary embodiments provide a number of functions that facilitate the effective viewing of and interaction with the various portions of the 3D visualizations. Various exemplary embodiments, enable a user of the visualization to change the viewing angles, viewing distance, and view point. For example,FIG. 1 shows the visualization of the first embodiment, in which the view is relatively distant and tilted to primarily display thefronts124 and tops122 of the building-like structures Alternatively,FIG. 2 shows the visualization of the first embodiment in which the view is relatively close and tilted to primarily display thefronts124 and tops122 of the building-like structures. A user may change the viewing angle by, for example grabbing the visualization and rotating it with a pointing device, touch screen, or virtual reality interaction devices such a glove, by using keyboard commands, or by any other known or later developed input device.
• Furthermore, various exemplary embodiments allow a user to access the indexed media portions by clicking on the various summaries on the building-like structures. For example, clicking on asingle video frame310 or a frame within akey frame summary410 will play the indexed video beginning from that frame. Similarly, clicking on aslide510 will access a larger view of the indexed slide or an indexed group of slides. Clicking on atext summary610 will access the document or documents that thetext summary610 represents.
• Alternatively, as shown inFIGS. 9 and 10, various exemplary embodiments of the invention providegraphical user interfaces900,1000 including a number ofslides920 and922 andbuttons924,926,928,930,932,934,936, and938 that enable a user to navigate and interact with the visualization.FIG. 9 shows one exemplary embodiment of a graphical user interface for use with the 3D visualization ofFIGS. 1-6.FIG. 10 shows one exemplary embodiment of a graphical user interface for use with the 3D visualization ofFIGS. 7 and 8. InFIGS. 9 and 10,buttons936,934,932,938 move the viewpoint forward, backward, left, and right, respectively.Buttons928 and930 zoom the viewpoint in and out.Buttons924 and926 move the viewpoint up and down (in altitude).Slider922 tilts the view.Slider920 is a controller does several operations together; it changes altitude and tilts the view, such that the point at center of the screen is kept fixed. As such,slider922 enables the user to see the rooftop when high up, to see the front of the building when near the ground, and to maintain the building in the center of the screen in view.
• FIGS. 11 and 12 show a flowchart outlining an exemplary embodiment of a grid layout method for the above-described type of 3D visualization that utilizes substantially square and similarly sized building-like structure plots according to this invention. As discussed above, the data to be visualized is organized as tree of elements where each branch in the tree is represented by a relatively square rectangle and all of the elements within this rectangle are part of that branch of the tree. This exemplary embodiment of a layout method balances the desire to minimize blank space in the layout with the need for a relatively square layout to match the shape of the majority of output devices, e.g., a computer monitor, a printer, or the like. A single line layout would produce no blank space but would not be an efficient use of output device real estate.
• As shown inFIGS. 11 and 12, operation of the method begins in ‘step S1000 and continues to step S1005 where each leaf of the tree is assigned a similar substantially rectangular area. Then, in step S1010, a first/next node whose subnodes are all leaves is selected as the current node. Next, in step S1015, the leaves of the current node are arranged into a larger rectangle such that the ratio of the height to width and the ratio of the width to height is less than a predetermined aspect ratio and that larger rectangle is assigned to the current node. The predetermined aspect ratio is used to insure that the resulting rectangle is relatively square. This prevents the creation of rectangles that are long and thin. Operation of the method continues to step S1020.
• In step S1020, a determination is made whether the current node is the root node of the tree. If the current node is the root node, all of the leaves of the tree have been arranged within a rectangle and operation jumps to step51085 where the operation of the method ends. However, if the current node is not the root node, operation continues to step S1025.
• In step51025, a determination is made whether all of the nodes whose subnodes are all leaves have been selected as the current node. If all of the nodes whose subnodes are all leaves have not been selected as the current node, operation returns to step S1010. However, if all of the nodes whose subnodes are all leaves have been selected as the current node, operation continues to step S1030.
• In step S1030, a first/next node that has at least one larger rectangle associated with one of its subnodes and a rectangle associated with each subnode is selected as a current node. Then, in step S1035, a determination is made whether a current node has more than one leaf rectangle and more than one larger rectangle associated with its subnodes. For example, as shown inFIG. 13, there are fiveleaf nodes1300 and three branch nodes (larger rectangles)1305,1310,1315. If the current node does not have more than one leaf rectangle and more than one larger rectangle associated with its subnodes, operation continues to step S1040. However, if the current node has more than one leaf rectangle and more than one larger rectangle associated with its subnodes, operation jumps to step S1055.
• In step S1040, the various rectangles, both leaf rectangles and larger rectangles, associated with the subnodes of the current node are arranged into larger rectangles such that the ratio of the height to width and the ratio of the width to height is less than the predetermined aspect ratio. Then, in step S1045, a determination is made whether a successful layout was found such that each of the rectangles fit within a new larger rectangle with a minimum of empty space. If a successful layout is not found, operation to continues to step51050, where the aspect of ratio is increased. Then, operation returns to stepS1040. However, if a successful layout is found, operation jumps to step S1080.
• In step S1055, the various leaf rectangles associated with the subnodes of the current node are arranged into a larger rectangle such that the ratio of the height to width and width to height is less than the predetermined aspect ratio. For example, as shown inFIG. 14, the leaf nodes ofFIG. 13 are combined into a singlelarger rectangle1400. [EXPAND ON ADVANTAGE OF THIS STEP] In various exemplary embodiments, it is advantageous to group the leaf nodes into a larger rectangle because they represent media files in the same directory in the directory tree and therefore should remain close together, rather than scattered throughout the layout. Next, in step S1060, the larger rectangles, including the larger rectangle composed of the various leaf rectangles associated with the subnodes of the current node, are arranged into various larger rectangles such that the ratio of the height to width and width to height is less than the predetermined aspect ratio. For example, as shown inFIG. 15, thevarious rectangles1305,1310,1315,1400 are combined into a number oflarger rectangles1500,1510,1520. For the purpose of this example, the aspect ratio is 1.5 (the height cannot be more than 1.5 times the width and vice versa) andrectangles1500,1510 and1520 show the three larger rectangles that would be considered (4×6, 5×5, and 6×4).
• Then, in step51065, a determination is made whether a successful layout was found such that each of the rectangles fit within the new larger rectangle with a minimum of empty space. As shown inFIG. 15,rectangle1500 encloses each of thesmaller rectangles1305,1310,1315,1400 with only three units of empty space.Rectangle1510 encloses each of thesmaller rectangles1305,1310,1315,1400 with four units of empty space.Rectangle1520 cannot enclose each of thesmaller rectangles1305,1310,1315,1400. It should be appreciated that, in various exemplary embodiments, when the rectangles have the same amount of empty space, preference is given to the rectangle with the smallest circumference. Returning toFIGS. 11 and 12, if a successful layout was not found, operation continues to step S1070, where the aspect ratio is increased. Then, operation returns to step S1055. However, if a successful layout was found, operation continues to step S1080.
• In step51080, the successful layout is assigned to the current node. Then, instep S1085, a determination is made whether the current node is the root node. If the current node is the root node, operation continues to step S1090 where the method ends. However, if the current node is not the root node, operation returns to step S1030 where the next node that has at least one larger rectangle associated with one of its subnodes and a rectangle associated with each subnode is selected as the current node. Operation of the flowchart will continue until, instep S1085, the current node is the root node.
• FIG. 16 is an exemplary embodiment of a functional block diagram of an exemplary embodiment of a3D visualization system1600 that is usable to create 3D visualizations according to the invention. As shown inFIG. 16, the3D visualization system1600 includes an input/output interface1620, acontroller1625, amemory1630, a node identifying circuit, routine, orapplication1640, a rectangle assigning circuit, routine, orapplication1645, a rectangle arranging circuit, routine, orapplication1650, an aspect ratio adjusting circuit, routine, orapplication1655, a layout testing comparing circuit, routine, orapplication1660, and a media associating circuit, routine, orapplication1665, each appropriately interconnected by one or more data/control busses and/orapplication programming interfaces1670, or the like.
• In this exemplary embodiment, the input/output interface1620 is connected to one ormore input devices1605 over one ormore links1601. The input device(s)1605 can be one or more of a keyboard, a mouse, a track ball, a track pad, a touch screen, a virtual reality glove, or any other known or later-developed device for inputting data and/or control signals to the3D visualization system1600. Furthermore, in this exemplary embodiment, the input/output interface1620 is connected to one ormore output devices1610 over one ormore links1602. The output device(s)1610 can be one or more of a computer monitor, cathode ray tube, liquid crystal display, image projector, electrophoretic display, a virtual reality display device, or any other known or later-developed device for visually displaying 3D visualization data output from the3D visualization system1600.
• In this exemplary embodiment, the input/output interface1620 is connected to adata source1700 over alink1701. Thedata source1700 can be a locally or remotely located laptop or personal computer, a personal digital assistant, a tablet computer, a device that stores and/or transmits electronic data, such as a client or a server of a wired or wireless network, such as for example, an intranet, an extranet, a local area network, a wide area network, a storage area network, the Internet (especially the World Wide Web), and the like. In general, thedata source1700 can be any known or later-developed source that is capable of providing a media data organized in a tree to the input/output interface1620.
• Each of thevarious links1601,1602, and1701 can be any known or later-developed device or system for connecting the input device(s)1605, the output device(s)1601, and/or thedata source1700, respectively, to the input/output interface1620. In particular, thelinks1601,1602, and1701 can each be implemented as one or more of a direct cable connection, a connection over a wide area network, a local area network or a storage area network, a connection over an intranet, a connection over an extranet, a connection over the Internet, a connection over any other distributed processing network or system, and/or an infrared, radio-frequency or other wireless connection.
• As shown inFIG. 16, thememory1630 contains a number of different memory portions, including alayouts portion1631, atree structure portion1632, aleaf data portion1633, asolution layout portion1634, and an aspect ratio portion1235. Thelayouts portion1631 of thememory1630 stores various layouts. Thetree structure portion1632 of thememory1630 stores the tree structure of the data that will be represented in the 3D visualization. Theleaf data portion1633 of thememory1630 stores the media represented by each leaf in the tree structure. Thesolution layout portion1634 stores the solution layout that will be used in the 3D visualization. The aspect ratio portion1235 stores the aspect ratio used to determine the various layouts.
• Thememory1630 shown inFIG. 16 can be implemented using any appropriate combination of alterable, volatile or non-volatile memory or non-alterable, or fixed, memory. The alterable memory, whether volatile or non-volatile, can be implemented using any one or more of static or dynamic RAM, a floppy disk and disk drive, a writeable or re-re-writeable optical disk and disk drive, a hard drive, flash memory or the like. Similarly, the non-alterable or fixed memory can be implemented using any one or more of ROM, PROM, EPROM, EEPROM, an optical ROM disk, such as CD-ROM or DVD-ROM disk, and disk drive or the like.
• The node identifying circuit, routine, orapplication1640 accesses the tree structure data and determines the characteristics of a node. The rectangle assigning circuit, routine, orapplication1645 assigns rectangular layouts to leaf nodes. The rectangle arranging circuit, routine, orapplication1650 arranges rectangular layouts into various larger rectangular layouts, based on the aspect ratio. The aspect ratio adjusting circuit, routine, orapplication1655 adjusts the aspect ratio. The layout testing circuit, routine, orapplication1660 tests various layouts to based on the amount of empty space. Finally, the media associating circuit, routine, orapplication1665 associates the leaf data with the solution layout to create the 3D visualization.
• In operation, the exemplary embodiment of the3D visualization system1600 shown inFIG. 16 operates in the following manner. Under control of thecontroller1625, the data necessary for creating the 3D visualization is input form thedata source1700 across thelink1701 via the input/output interface1620 and stored in the tree structure andleaf data portions1632,1633 of thememory1630. Next, under control of thecontroller1625, the node identifying circuit, routine, orapplication1640 accesses the tree structure data in thetree structure portion1632 of thememory1630 and identifies each of the leaf nodes. Then, under control of thecontroller1625, the rectangle assigning circuit, routine, orapplication1645, accesses the identified leaf nodes and assigns each leaf node a similar substantially rectangular area. The rectangles for each leaf node, under control of thecontroller1625, are associated with their respective leaf node and stored in thelayouts portion1631 of thememory1630.
• Under control of thecontroller1625, the node identifying circuit, routine, orapplication1640 accesses the tree structure data stored in thetree structure portion1632 and the layout data in thelayout data portion1631 and identifies each node whose subnodes are all leaves. Then, under control of thecontroller1625, the rectangle arranging circuit, routine, orapplication1650 accesses the identified subnodes and arranges the rectangles assigned to the leaf nodes of each identified node into a larger rectangle. The rectangles for the identified nodes, under control of thecontroller1625, are associated with their respective identified nodes and stored in thelayouts portion1631 of thememory1630.
• Under control of thecontroller1625, the node identifying circuit, routine, orapplication1650 accesses the tree structure data stored in thetree structure portion1632 and the layout data in thelayout data portion1631 and identifies each node that has at least one rectangle associated with each subnode, at least one of the rectangles being larger than a leaf rectangle. Of these identified nodes, under control of thecontroller1625, the node identifying circuit, routine, orapplication1640, further identifies a first subgroup of the identified nodes that have more than one leaf rectangle associated with its subnodes, and more than one rectangle larger than a leaf rectangle associate with its subnodes.
• Under control of thecontroller1625, the rectangle arranging circuit, routine, orapplication150 accesses the first subgroup of the identified nodes, and for each node, arranges the various leaf rectangles associated with the subnodes of that node into a larger rectangle with the smallest circumference. Then, under control of thecontroller1625, the rectangle arranging circuit, routine, orapplication1650, for each node of the of the first subgroup of identified nodes, arranges the larger rectangles of the subnodes of that node into rectangles whose height/width or width/height is less than the aspect ratio stored in theaspect ratio portion1635 of thememory1630. When, for a particular node, the larger rectangles of the subnodes of that node will not fit into any rectangle according to the aspect ratio, the aspect ratio adjusting circuit, routine, orapplication1655 accesses the aspect ratio in theaspect ratio portion1635 and increases the aspect ratio for that node until the larger rectangles of the subnodes of that node will fit into at least one rectangle with the smallest aspect ratio.
• Then, under control of thecontroller1625, the layout testing circuit, routine, orapplication1660 accesses the various rectangles for each node of the first subgroup of identified nodes and selects the rectangle for each node which has the least amount of empty space. If more than one rectangle for a node of the first subgroup of identified nodes has the same amount of empty space, the layout testing circuit, routine, orapplication1660 will select the rectangle with the smallest circumference (i.e., closest to square). Under control of thecontroller1625, the selected rectangle for each node of the first subgroup of identified nodes is associated with its respective node and stored in thelayouts portion1631 of thememory1630.
• Once a rectangle has been stored in thelayouts portion1631 for each node of the first subgroup of identified nodes, the rectangle arranging circuit, routine, orapplication1650 accesses the remaining nodes of the identified nodes as the second subgroup of identified nodes (i.e., having a rectangle associated with each subnode and a rectangle larger than a leaf rectangle associated with at least one subnode, but not included in the first subgroup of identified nodes). Then, under control of thecontroller1625, the rectangle arranging circuit, routine, orapplication1650, for each node of the of the second subgroup of identified nodes, arranges the larger rectangles of the subnodes of that node into a rectangles whose height/width or width/height is less than the aspect ratio stored in theaspect ratio portion1635 of thememory1630. When, for a particular node, the larger rectangles of the subnodes of that node will not fit into any rectangle according to the aspect ratio, the aspect ratio adjusting circuit, routine, orapplication1655 accesses the aspect ratio in theaspect ratio portion1635 and increases the aspect ratio for that node until the rectangles of the subnodes of that node will fit into at least one rectangle.
• Then, under control of thecontroller1625, the layout testing circuit, routine, orapplication1660 accesses the various rectangles for each node of the second subgroup of identified nodes and selects the rectangle for each node which has the least amount of empty space. If more than one rectangle for a node of the second subgroup of identified nodes has the same amount of empty space, the layout testing circuit, routine, orapplication1660 selects the rectangle with the smallest circumference (i.e., closest to square). Under control of thecontroller1625, the selected rectangle for each node of the second subgroup of identified nodes is associated with its respective node and stored in thelayouts portion1631 of thememory1630.
• Once a rectangle has been selected and stored in thelayouts portion1631 for each node of the identified nodes (i.e., both the first and second subgroups), under control of thecontroller1625, the node identifying circuit, routine, orapplication1640 again accesses the tree structure data stored in thetree structure portion1632 and the layout data in thelayout data portion1631 and identifies each node that now has at least one rectangle associated with each subnode, at least one of the rectangles being larger than a leaf rectangle. These nodes become the new set of identified nodes, and the data flow continues as above. However, when at any time during the operation of the3D visualization system1600, under control of thecontroller1625, the node identifying circuit, routine, or application accesses the tree structure data stored in thetree structure portion1632 and the layout data in thelayout data portion1631 and determines that there is only a single layout associated with a single node, the solution layout has been determined (all layouts have been combined until the root node is associated with the only rectangle).
• Then, under control of thecontroller1625, the single layout for the root node is stored in thesolution layout portion1634 of thememory1630. Next, under control of thecontroller1625, the media associating circuit, routine, orapplication1665 accesses the solution layout in thesolution layout portion1634 and the media data in theleaf data portion1633, and associates the media data for each leaf with that leafs location according to the solution layout. At this point the 3D visualization has been created and, under control of thecontroller1625, is ready to be output to the output device(s)1610 acrosslink1602 via the input output interface.
• It should be appreciated that, depending on cost or other design constraints, one or more of the above-described elements of the 3D visualization system1200 may be combined into a single element or divided into multiple elements where appropriate.
• FIGS. 17-21 are flowcharts outlining an exemplary embodiment of a method for determining layout for the above-described 3D visualization, exemplified inFIGS. 7 and 8, wherein each leaf node is assigned a different size parcel that reflects an attribute of that leaf node.
• As shown inFIG. 17, operation of the method begins in step S2000 and continues to step S2005 where the root node is selected as the current node. Then, operation continues to step S2010, where a determination is made whether the current node is a leaf node. If the current node is a leaf node, operation continues to step S2015, where a solution layout for the leaf node is constructed with a given width and height. Then, operation continues to step52170. However, if the current node is not a leaf node, operation continues to step S2020 where the first or next subnode of the current node is selected as the current node. Operation continues to step S2025.
• In step S2025, a determination is made whether the current node is a leaf node. If the current node is a leaf node, operation continues to step S2030 where a layout is constructed for the leaf node with a given width and height. Otherwise, operation jumps to step S2040. Next, in step S2035, the constructed layout is assigned to a new set of layouts associated with the parent node of the current node. Then, operation jumps to step S2065.
• In step S2040, a determination is made whether all the subnodes of the current node have been selected as a current node. If all subnodes of the current node have not been selected as a current node, operation returns to step S2020. If all subnodes of the current node have been selected as a current node, operation continues to step S2045. In step S2045, a determination is made whether more than one set of layouts is associated with the current node. If there is more than one set of layouts associated with the current node, operation jumps to step S2070. If there is not more than one set of layouts associated with the current node, operation continues to step S2050.
• In step S2050, a determination is made whether the current node is the root node. If the current node is the root node, operation continues to step S2055. If the current node is not the root node, operation jumps to step S2060.
• In step S2055, the “smallest” layout is selected from the set of layouts as the solution. In various exemplary embodiments, the “smallest” layout is determined to be the layout with the smallest circumference. As such, the “smallest” layout may not have the smallest overall area, but will have a small area and be the closest to square. Operation then continues to step S2170.
• In step S2060, the set of layouts that is associated with the current node is associated with the parent node of the current node. Then, operation continues to step S2065, where the parent node is selected as the current node. Next, operation returns to step S2040, where it is once again determined whether all of the subnodes the current node have been selected as a current node.
• In step S2070, an empty new set of layouts is created for the current node. Next, in step S2075, a set of layouts containing the smallest layout is selected from the sets of layouts associated with the current node asset1. Then, in step S2080, a set of layouts, other thanset1, containing the smallest layout is selected from the sets of layouts associated with the current node asset2. Next, step S2085, a first or next layout is selected fromset1 as the current layout ofset1. Then, in step S2090, a first or next layout is selected fromset2 as the current layout ofset2. Operation continues to step S2095.
• In step S2095 the current layout ofset1 and the current layout ofset2 are combined horizontally adjacent to one another, separated by a given amount of space, to create the current combined layout. Next, in step S2100, determination is made whether the new set of layouts for the current node is empty. If the new set of layouts for the current node is empty, operation continues to step52105 where the current combined layout is added to the new set of layouts for the current node. Then, operation jumps to step S2145. However, if the new set of layouts for the current node is not empty, operation continues to step S2110.
• In step S2110, a first or next layout from the new set of layouts for the current node is selected as the current new layout. Then, operation continues to step52115, where it is determined whether the current combined layout is “larger” than the current new layout. According to various exemplary embodiments of this method, “larger” means that one layout has both a larger width and a larger height than another layout. If the current combined layout is larger than the current new layout, operation continues to step52120 where the current combined layout is discarded. Then, operation jumps to step S2145. However, if the current combined layout is not larger than the current new layout, operation continues to step S2125.
• In step S2125, it is determined whether the current new layout is “larger” than the current combined layout. If the current new layout is larger than the current combined layout, operation continues to step52130 where the current new layout is discarded. Operation then continues to step S2135. However, if the current new layout is not larger than the current combined layout, operation jumps to step S2135. It should be appreciated that it is possible for the current combined layout to not be larger than the current new layout and the current new layout not be larger than the current combined layout since in order to be larger both the height and the width of one of the layouts must be respectively larger than the height and the width of the other layout.
• In step S2135, a determination is made whether all of the layouts in the new set of layouts for the current node have been compared with the current combined layout. If not, operation returns to step52110. However, if all of the layouts of the new set of layouts for the current node have been compared with the current combined layout, operation continues to step S2140 where the current combined layout is added to the new set of layouts for the current node. Then, operation continues to step S2145.
• In step S2145, it is determined whether the current layout ofset1 and the current layout ofset2 have been combined both horizontally and vertically. If not, operation continues to step S2150, where the current layout ofset1 and the current layout ofset2 are combined vertically adjacent to one another, separated by a given amount of space, to create the current combined layout. Operation then returns to step52110. However, if the current layout ofset1 and the current layout ofset2 have been combined both horizontally and vertically, operation continues to step S2155.
• In step S2155, it is determined whether all of the layouts fromset2 have been combined with the current layout fromset1. If not, operation returns to step S2090 where the next layout fromset2 is selected as the current layout ofset2. If all of the layouts fromset2 have been combined with the current layout fromset1, operation continues to step S2160. In step52160, it is determined whether all the layouts fromset1 have been selected as the current layout forset1. If not, operation returns to step S2085 where the next layout fromset1 is selected as the current layout ofset1. However, if all of the layouts fromset1 have been selected as the current layout forset1, operation continues to step S2165.
• In step S2165, set1 and set2 are discarded, and therefore, are no longer associated with the current node. Then, operation returns to step S2045, where a determination is made whether there are more than on one set of layouts associated with the current node, and the operation of the flowchart continues as above.
• In steps S2015 and S2055, once a solution layout has been determined, operation continues to step S2170. In step S2170, the solution layout is selected as the current layout. Next, in step S2175, a starting x and y are associated with the current layout. Then, in step52180, it is determined whether the current layout is associated with a tree. If the current layout is associated with a tree, operation continues to step S2185, where the x, y, width, and height of the current layout are associated with the tree. Operation continues to step S2190. However, if the current layout is not associated with a tree, operation jumps directly from step S2180 to step S2190.
• In step S2190, it is determined whether the current layout is composed horizontally, (i.e., was the current layout created in step S2095). If the current layout is composed horizontally, operation continues to step S2195. If the current layout is not composed horizontally, operation jumps to step S2205.
• In step52195, the x and y of the current layout are associated with the left component layout, the left component layout being the layout of the left side of the horizontally combined current layout. Next, in step S2200, the left component layout is selected as the current layout. Then, operation returns to step S2180.
• In step S2205, it is determined whether the current layout is composed vertically (i.e., was created during step S2150). If the current layout is composed vertically, operation continues to step S2210. If the current layout is not composed vertically, operation jumps to step S2220. In step52210, the x and y of the current layout are associated with the lower component layout, the lower component layout being the layout on the bottom of the vertically combined current layout. Next, in step52215, the lower component layout is selected as the current layout. Then, operation returns to step S2180.
• In step S2220, a determination is made whether the current layout is the solution layout. If the current layout is the solution layout, every component layout has been assigned a location and operation jumps to step S2270, where the method ends. However, if the current layout is not the solution layout, operation continues to step S2225.
• In step S2225, the enclosing layout is selected as the current layout. Then, in step S2230, it is determined whether the current layout is composed horizontally. If the current layout is not composed horizontally, operation jumps to step S2250. However, if the current layout is composed horizontally, operation continues to step S2235 where it is determined whether the right layout has been assigned a position value (i.e., whether or not an x and y is associated with the right layout). If so, operation returns to step S2220. However, if the right layout has not been assigned a position value, operation continues to step S2240. In step S2240, the width of the left layout and a given amount of space is added to the x associated with the current layout. Then, this new value and the y of the current layout are associated with the right layout. Next, operation continues to step S2245 where the right layout is selected as the current layout. Then, operation returns to step S2180.
• In step S2250, a determination is made whether the current layout is composed vertically. If not, operation returns to step S2220. However, if the current layout is composed vertically, operation continues to step S2255 where it is determined whether the upper layout has been assigned a position value. If the upper layout has been assigned a position value, operation returns to step S2220. If the upper layout has not been assigned a position value, operation continues to step S2260 where the height of the lower layout and a given amount of space is added to the y associated with the current layout. Then, the x of the current layout and the new value for y is associated with the upper layout. Next, operation continues to step S2265. In step S2265, the upper layout is selected as the current layout and operation returns to step S2180. The operation of the flowchart will continue to move the various steps until, in step S2220 the current layout is the solution layout. At such time, each component layout of the solution layout has been assigned a position value and operation continues to step S2270 where operation of the method ends.
• FIG. 22 is exemplary embodiment of a functional block diagram of another exemplary embodiment of a3D visualization system2200 that is usable to create 3D visualizations according to the invention. As shown inFIG. 22, the3D visualization system2200 includes an input/output interface2220, acontroller2225, amemory2230, a node identifying determining circuit, routine, orapplication2240, a set associating circuit, routine, or application2245, a set creating circuit, routine, orapplication2250, a layout size comparing circuit, routine, orapplication2255, a layout constructing circuit, routine, orapplication2260, a horizontal layout combining circuit, routine, orapplication2265, a vertical layout combining circuit, routine, orapplication2270, and a media associating circuit, routine, or application2275, each appropriately interconnected by one or more data/control busses and/or application programming interfaces2280, or the like.
• In this exemplary embodiment, the input/output interface2220 is connected to one ormore input devices2205 over one ormore links2201. The input device(s)2205 can be one or more of a keyboard, a mouse, a track ball, a track pad, a touch screen, a virtual reality glove, or any other known or later-developed device for inputting data and/or control signals to the3D visualization system2200. Furthermore, in this exemplary embodiment, the input/output interface2220 is connected to one or more output devices2210 over one ormore links2202. The output device(s)2210 can be one or more of a computer monitor, cathode ray tube, liquid crystal display, image projector, electrophoretic display, a virtual reality display device, or any other known or later-developed device for visually displaying 3D visualization data output from the3D visualization system2200.
• In this exemplary embodiment, the input/output interface2220 is connected to adata source2300 over a link2301. Thedata source2300 can be a locally or remotely located laptop or personal computer, a personal digital assistant, a tablet computer, a device that stores and/or transmits electronic data, such as a client or a server of a wired or wireless network, such as for example, an intranet, an extranet, a local area network, a wide area network, a storage area network, the Internet (especially the World Wide Web), and the like. In general, thedata source2000 can be any known or later-developed source that is capable of providing a media data organized in a tree to the input/output interface2220.
• Each of thevarious links2201,2202, and2301 can be any known or later-developed device or system for connecting the input device(s)2205, the output device(s)2201, and/or thedata source2300, respectively, to the input/output interface2220. In particular, thelinks2201,2202, and2001 can each be implemented as one or more of a direct cable connection, a connection over a wide area network, a local area network or a storage area network, a connection over an intranet, a connection over an extranet, a connection over the Internet, a connection over any other distributed processing network or system, and/or an infrared, radio-frequency or other wireless connection.
• As shown inFIG. 22, thememory2230 contains a number of different memory portions, including a layouts portion2231, a tree structure portion2232, a leaf data portion2233, and a solution layout portion2234. The layouts portion2231 of thememory2230 stores various layouts. The tree structure portion2232 of thememory2230 stores the tree structure of the data that will be represented in the 3D visualization. The leaf data portion2233 of thememory2230 stores the media represented by each leaf in the tree structure. The solution layout portion2234 stores the solution layout that will be used in the 3D visualization.
• Thememory2230 shown inFIG. 22 can be implemented using any appropriate combination of alterable, volatile or non-volatile memory or non-alterable, or fixed, memory. The alterable memory, whether volatile or non-volatile, can be implemented using any one or more of static or dynamic RAM, a floppy disk and disk drive, a writeable or re-re-writeable optical disk and disk drive, a hard drive, flash memory or the like. Similarly, the non-alterable or fixed memory can be implemented using any one or more of ROM, PROM, EPROM, EEPROM, an optical ROM disk, such as CD-ROM or DVD-ROM disk, and disk drive or the like.
• The node identifying circuit, routine, orapplication2240 accesses the tree structure data and determines the characteristics of a node. The rectangle assigning circuit, routine, or application2245 assigns rectangles to leaf nodes. The set associating circuit, routine, or application2245 associates various layouts with a set of layouts. The set creating circuit, routine, orapplication2250 creates empty sets with which various layouts may be associated. The layout size comparing circuit, routine, orapplication2255 compares the size various layouts. The layout constructing circuit, routine, orapplication2260 creates layouts for leaf nodes. The horizontal layout combining circuit, routine, orapplication2265 combines layouts horizontally into a larger layout. The vertical layout combining circuit, routine, orapplication2270 combines layouts vertically into a larger layout. Finally, the media associating circuit, routine, orapplication2265 associates the leaf data with the solution layout to create the 3D visualization.
• In operation, the exemplary embodiment of the3D visualization system2200 shown inFIG. 16 operates in the following manner. Under control of thecontroller2225, the data necessary for creating the 3D visualization is input from thedata source2000 across the link2001 via the input/output interface2220 and stored in the tree structure and leaf data portions2232,2233 of thememory2230. Next, under control of thecontroller2225, the node identifying circuit, routine, orapplication2240 accesses the tree data stored in the tree structure portion and identifies the leaf nodes. Then, under control of thecontroller2225, the layout constructing circuit, routine, orapplication2260 accesses the identified leaf nodes and constructs a layout with a given width and height for each leaf node. Under control of thecontroller2225, the set creating circuit, routine, orapplication2250 creates an empty set of layouts for each of the identified leaf nodes. Then, under control of thecontroller2225, the layouts for each leaf node are stored within the new set created for that leaf node's layout node in the layouts portion2231 of thememory2230 and associated with the parent node of the leaf node for which the set was created.
• After a layout for each node has been created, under control of thecontroller2225, the node identifying circuit, routine, orapplication2240 accesses the tree structure data stored in the tree structure portion and identifies each node that only has one set associated with it. Then, under control of thecontroller2225, the set associating circuit, routine, or application2245 associates that set with the first parent node in the identified node's progeny that has more than one subnodes. Next, under control of thecontroller2225, the node identifying circuit, routine, orapplication2240 identifies all of the nodes that have a set of layouts associated with each of that node's subnodes.
• Under control of thecontroller2225, the set creating circuit, routine, orapplication2250 creates a new empty set of layouts for each of the identified nodes. Then, under control of thecontroller2225, for each identified node, the horizontal layout combining circuit, routine, orapplication2265 selects a layout from the set of layouts containing the smallest layout (set1). Then, for each identified node, under control of thecontroller2225, the horizontal layout combining circuit, routine, orapplication2265 identifies the set of layouts other thanset1 with the smallest layout (set2). Under control of thecontroller2225, the horizontal layout combining circuit, routine, orapplication2265 combines each layout fromset1 with every layout fromset2 in a horizontally adjacent fashion. The first of these combined layouts is stored in the newly created empty set of layouts for each of identified nodes. Then, under control of thecontroller2225, the remaining combined layouts for each identified node are accessed by the layout size comparing circuit, routine, orapplication2255.
• The layout size comparing circuit, routine, orapplication2255, under control of thecontroller2225, compares each combined layout with each of the layouts in the newly created set. If, under control of thecontroller2225, the layout size comparing circuit, routine, orapplication2255 determines that a combined layout is “larger” than a layout in the new set (i.e., both the height and width of the combined layout is larger than the layout in the new set), the combined layout is discarded. If, under control of thecontroller2225, the layout size comparing circuit, routine, orapplication2255 determines that a layout in the new set is “larger” than a combined layout, the new layout is discarded and the combined layout is stored in the new set.
• Next, under control of thecontroller2225, the vertical layout combining circuit, routine, or application combines each of the layouts fromset1 with every layout fromset2. Again, under control of thecontroller2225, if the layout size comparing circuit, routine, orapplication2255 determines that a combined layout is “larger” than a layout in the new set, the combined layout is discarded. If, under control of thecontroller2225, the layout size comparing circuit, routine, orapplication2255 determines that a layout in the new set is “larger” than a combined layout, the new layout is discarded and the combined layout is stored in the new set.
• Once, under control of thecontroller2225, each of the layouts fromset1 has been combined vertically and horizontally with all of the layouts fromset2, sets1 and2 are discarded. Next, the node identifying circuit, routine, orapplication2240, under control of thecontroller2225, accesses the tree structure data stored in the tree structure portion2232 and the layout data stored in the layout portion2231 and identifies each node that only has one set associated with it. Then, under control of thecontroller2225, the set associating circuit, routine, or application2245 associates that set with the first parent node in the identified node's progeny that has more than one subnodes. Next, under control of thecontroller2225, the node identifying circuit, routine, orapplication2240 identifies all of the nodes that have had a set of layouts associated with each of that node's subnodes.
• Under control of thecontroller2225, the set creating circuit, routine, orapplication2250 again creates a new empty set of layouts for each of the identified nodes. In this manner, for each node, the sets of layouts associated with that node will be consolidated until one set remains and that set will be associated with the nodes parent node. The data flow repeats until, under control of thecontroller2225, the node identifying circuit, routine, orapplication2240 determines that the root node has only one set of layouts associated with it and all of the subnodes of the parent node no longer have any sets. At this point, under control of thecontroller2225, the layout size comparing circuit, routine, orapplication2255 accesses the set of layouts associated with the root node and selects the smallest layout from the set (i.e., the layout with the smallest circumference). Then, under control of thecontroller2225, the smallest layout is stored in the solution layout portion2234, of thememory2230. Next, under control of thecontroller2225, the media associating circuit, routine, or application accesses the solution layout in the solution layout portion2234 and the media data in the leaf data portion2233, and associates the media data for each leaf with that leafs location according to the solution layout. At this point, the 3D visualization has been created and, under control of thecontroller2225, is ready to be output to the output device(s)2210 acrosslink2202 via the input output interface2220.
• It should be appreciated that, depending on cost or other design constraints, one or more of the above-described elements of the 3D visualization system1200 may be combined into a single element or divided into multiple elements where appropriate.
• According to the above-described exemplary embodiments of the systems, methods, and graphical user interfaces according to this invention, a 3D visualization of media indexed within a tree data structure is provided wherein 3D objects representing the indexed media display visual summaries of the indexed media. These summaries allow a user to visually evaluate the indexed media, based on its content, without having to access the media itself. The ability to evaluate the media based on its content is particularly advantageous when a large amount of media is indexed and it would be impractical to access each leaf of the tree data structure in order to evaluate the media.
• While the invention has been described in conjunction with exemplary embodiments, these embodiments should be viewed as illustrative, not limiting. Various modifications, substitutes, or the like are possible within the spirit and scope of the invention.

Claims (15)

1. A method for creating a layout for a 3D visualization comprising:

inputting a tree data structure, each leaf of the tree associated with one or more forms of media;

obtaining a plurality of candidate layouts;

comparing the plurality of candidate layouts;

selecting a solution layout based on the comparison; and

constructing a 3D visualization of the tree data structure based on the solution layout,

wherein the representation of each leaf of the tree data structure within the 3D visualization provides a summary of the media associated with that leaf.

2. The method ofclaim 1, wherein obtaining the plurality of candidate layouts further comprises:

assigning each leaf a rectangular layout;

arranging, for each node of the tree data structure whose subnodes are all leaves, the rectangular layouts of the leaves of that node into a layout for that node.

3. The method ofclaim 2, wherein, for each node that has a rectangular layout for each subnode, one of the rectangular layouts being larger than a leaf rectangular layout, obtaining the plurality of candidate layouts further comprises:

arranging—for each node that has more than one leaf subnode and more than one non-leaf subnode, each non-leaf subnode having a rectangular layout—the rectangular layouts of the more than one leaf subnodes of that node into a rectangular layout; and

arranging, for that node, the rectangular layouts of the non-leaf subnodes and the rectangular layout of the leaf subnodes into a plurality of candidate layouts, the candidate layouts each defined by an aspect ratio.

4. The method ofclaim 3, wherein:

obtaining the plurality of candidate layouts further comprises arranging, for each node that does not have more than one leaf subnode and more than one non-leaf subnode, each non-leaf subnode having a rectangular layout, the layouts of the subnodes of that node into a plurality of candidate layouts, the candidate layouts defined by an aspect ratio.

5. The method ofclaim 4, wherein:

comparing the plurality of candidate layouts comprises determining a total area of each candidate layout that does not contain the rectangular layouts of the non-leaf subnodes and the rectangular layout of the leaf subnodes; and

selecting the solution layout comprises selecting the candidate layout with the smallest total area that does not contain the rectangular layouts of the non-leaf subnodes and the rectangular layout of the leaf subnodes.

6. The method ofclaim 5, wherein constructing the 3D visualization based on the layout comprises:

associating, for each leaf within the input tree data structure, the media associated with that leaf with a location of the layout of that leaf with the solution layout; and

creating, for each leaf within the input free data structure, a summary of the media associated with that leaf.

7. The method ofclaim 6, wherein the summary of the media contained by that leaf is a building-like structure with visual summaries of the media on each side of the building and the roof of the building.

8. The method ofclaim 1, wherein obtaining a plurality of candidate layouts comprises:

determining, for each leaf, a rectangular layout, a size of the rectangular layout being determined by a quality of the media associated with that leaf;

assigning, for each leaf, the determined rectangular layout to a new set of layouts; and

associating, for each leaf, the new set of layouts with a parent node of that leaf;

wherein, whenever there is only a single set of layouts associated with a root node, and no sets of layouts associated with any other nodes, selecting the solution layout comprises selecting a smallest layout from the set of layouts associated with the root node as the solution layout.

9. The method ofclaim 8, wherein obtaining the plurality of candidate layouts further comprises:

identifying each node that has a set of layouts associated with it for each of its subnodes; combining, for each identified node, the sets of layouts associated with that identified node into a single set, wherein the single set contains combined layouts that are not larger than any other combined layouts within the set.

10. The method ofclaim 9, wherein, to be considered larger, a layout must be longer in width and longer in length than another layout of the other layouts within the set.

11. The method ofclaim 10, wherein combining, for each identified node, the sets of layouts associated with that identified node into a single set comprises:

selecting a first set of layouts associated with that identified node containing a smallest layout;

selecting a second set of layouts associated with that identified node, other than the first set of layouts, that contains a smallest layout;

creating a new set of layouts associated with that identified node;

horizontally combining a first layout from the first selected set of layouts with a first layout from the second selected set of layouts; and

assigning the horizontally combined first layout from the first selected set and first layout from the second selected to the new set of layouts associated with the identified node.

12. The method ofclaim 11, wherein combining, for each identified node, the sets of layouts associated with that identified node into a single set further comprises, for each layout within the first selected set of layouts:

horizontally combining, for each layout within the second selected set of layouts, that layout from the first selected set of layouts with that layout from the second selected set of layouts; and

comparing, for each layout within the new set for the identified node, the horizontally combined layout from the first selected set and layout from the second selected set with that layout within the new set;

wherein:

whenever the horizontally combined layout from the first selected set and the second selected set is larger than a layout within the new set for the identified node, the horizontally combined layout from the first selected set and the second selected set is discarded;

whenever a layout within the new set for the identified node is larger than the horizontally combined layout from the first selected set and the second selected set, that layout within the new set for the identified node is discarded; and

if the horizontally combined layout from the first selected set and the second selected set has been compared with every layout in the new set for the identified node without being discarded, the horizontally combined layout from the first selected set and the second selected set is added to the new set for the identified node.

13. The method ofclaim 12, wherein combining, for each identified node, the sets of layouts associated with that identified node into a single set further comprises, for each layout within the first selected set of layouts:

vertically combining, for each layout within the second selected set of layouts, that layout from the first selected set of layouts with that layout from the second selected set of layouts; and

comparing, for each layout within the new set for the identified node, the vertically combined layout from the first selected set and layout from the second selected set with that layout within the new set;

wherein:

whenever the vertically combined layout from the first selected set and the second selected set is larger than a layout within the new set for the identified node, the vertically combined layout from the first selected set and the second selected set is discarded;

whenever a layout within the new set for the identified node is larger than the vertically combined layout from the first selected set and the second selected set, that layout within the new set for the identified node is discarded; and

if the vertically combined layout from the first selected set and the second selected set has been compared with every layout in the new set for the identified node without being discarded, the vertically combined layout from the first selected set and the second selected set is added to the new set for the identified node.

14. The method ofclaim 13, wherein the first selected set and the second selected set are discarded.

15.-42. (canceled)

Images