SYSTEMS AND METHODS FOR CREATING AN INTERACTIVE 3D VISUALIZATION OF INDEXED MEDIA

• US 20080034326A1
• Filed: 10/10/2007
• Published: 02/07/2008
• Est. Priority Date: 02/12/2004
• Status: Abandoned Application

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: POLAK, Wolfgang, LERTSITHICHAI, Surapong, SHIPMAN, Frank, GIRGENSOHN, Andreas, CHIU, Patrick
• Application Number:
  US11/870,351
• Publication Number:
  US 20080034326A1
• Time in Patent Office: Days
• US Class Current: 715/849
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation
• CPC Class Codes: G06F 2203/04802 3D-info-object: information is displayed on the internal or external surface of a three dimensional manipulable object, e.g. on the faces of a cube that can be rotated by the user
• CPC Class Codes: G06F 3/04815 Interaction with a metaphor-based environment or interaction object displayed as three-dimensional, e.g. changing the user viewpoint with respect to the environment or object
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 2200/04 involving 3D image data

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.

Claims

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 of claim 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 of claim 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 of claim 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 of claim 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 of claim 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 of claim 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 of claim 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 of claim 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 of claim 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 of claim 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 of claim 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 of claim 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 of claim 13, wherein the first selected set and the second selected set are discarded.

15-42. -42. (canceled)