Systems and methods for creating an interactive 3D visualization of indexed media

• US 7,340,678 B2
• Filed: 02/12/2004
• Issued: 03/04/2008
• Est. Priority Date: 02/12/2004
• Status: Active Grant

• Current Assignee: Fujifilm Business Innovation Corp. (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Polak, Wolfgang, Girgensohn, Andreas, Chiu, Patrick, Lertsithichai, Surapong, Shipman, Frank III
• Primary Examiner(s): Sax; Steven P.
• Assistant Examiner(s): NGUYEN, LE V
• Application Number:
  US10/776,618
• Publication Number:
  US 20050183041A1
• Time in Patent Office: 1,482 Days
• Field of Search: 715/734
• US Class Current: 715/734
• 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 structure 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 at least one building-like structure.

Claims

1. A system for creating a 3D visualization comprising:

a node identifying circuit, routine, or application that accesses a tree data structure and identifies qualities of nodes within the tree data structure;

a rectangle assigning circuit, routine, or application that assigns rectangular layouts to nodes within the tree data structure;

a rectangle arranging circuit, routine, or application that arranges rectangular layouts into larger candidate rectangular layouts;

a layout testing circuit, routine, or application that compares candidate rectangular layouts and selects a solution layout; and

a media associating circuit, routine, or application that associates media with the solution layout to create a 3D visualization, wherein, if there are two candidate layouts with the least amount of empty space, the layout testing circuit, routine, or application selects the candidate layout with the smallest circumference as the solution layout for that node.

2. The system of claim 1, wherein:

the node identifying circuit, routine, or application accesses a tree data structure and identifies each leaf with the tree data structure; and

the rectangle assigning circuit, routine, or application assigns each identified leaf a rectangular layout.

3. The system of claim 2, wherein:

the node identifying circuit, routine, or application identifies each node whose subnodes are all leaves; and

the rectangle arranging circuit, routine, for each identified node whose subnodes are all leaves, arranges the rectangular layouts of the subnodes of that identified node into a larger rectangular layout and assigns the larger rectangular layout to that identified node.

4. The system of claim 3, wherein:

the node identifying circuit, routine, or application identifies each node that has a rectangular layout for each subnode, more than one of the rectangular layouts for each node being larger than a leaf rectangular layout and more than one of the rectangular layouts for each node being a leaf rectangular layout; and

the rectangle arranging circuit, routine, or application arranges each of the more than one leaf rectangular layouts into a larger leaf rectangular layout and then arranges the larger leaf rectangular layout and the more than one of the larger than a leaf rectangular layout for the subnodes of the node into a plurality of candidate layouts for the node.

5. The system of claim 4, wherein:

the node identifying circuit, routine, or application identifies each node that has a rectangular layout for each subnode, and does not have both more than one of the rectangular layouts for each node being larger than a leaf rectangular layout and more than one of the rectangular layouts for each node being a leaf rectangular layout; and

the rectangle arranging circuit, routine, or application arranges the rectangular layouts for the subnodes of the node into a plurality of candidate layouts for the node.

6. The system of claim 5, further comprising an aspect ratio adjusting circuit, routine, or application, wherein the rectangle arranging circuit, routine, or application only creates candidate layouts within a defined aspect ratio and, if the rectangle arranging circuit routine or application cannot arrange various rectangular layouts for the subnodes of the identified node, the aspect ratio adjusting circuit, routine, or application increases the defined aspect ratio.

7. The system of claim 6, wherein:

the node identifying circuit, routine, or application identifies each node that has a plurality of candidate layouts associated with that node; and

the layout testing circuit, routine, or application, for each identified node that has a plurality of candidate layouts associated with that node, selects the candidate layout for that node with the least amount of empty space as the solution layout for that node.

8. The system of claim 7, wherein, if the layout testing circuit, routine, or application has selected a solution layout for a root node of the tree data structure, the media associating circuit, routine, or application associates summary media that summarizes data within each leaf of the tree data structure with the respective location of each leaf within the solution layout.

9. A system for creating a 3D visualization comprising:

a node identifying circuit, routine, or application that accesses a tree data structure and identifies qualities of nodes within the tree data structure;

a set creating circuit, routine, or application that creates sets with which layouts may be associated;

a set associating circuit, routine, or application that associates one or more sets of layouts with a node of the tree data structure;

a layout constructing circuit, routine, or application that creates rectangular layouts for the leaves of the tree data structure;

a layout size comparing circuit, routine, or application that compares dimensions of a plurality of layouts;

a horizontal layout combining circuit, routine, or application that combines two layouts horizontally;

a vertical layout combining circuit, routine, or application that combines two layouts vertically;

a layout testing circuit, routine, or application that compares candidate rectangular layouts and selects a solution layout; and

a media associating circuit, routine, or application that associates media with the solution layout to create a 3D visualization, wherein, if there are two candidate layouts with the least amount of empty space, the layout testing circuit, routine, or application selects the candidate layout with the smallest circumference as the solution layout for that node.

10. The system of claim 9, wherein:

the node identifying circuit, routine, or application identifies each leaf of a tree data structure;

the set creating circuit, routine, or application, creates a new set of layouts for each identified leaf;

the layout constructing circuit, routine, or application, for each identified leaf, creates a layout for that identified leaf and stores the created layout in the new set of layouts; and

the set associating circuit, routine, or application, for each identified leaf, associates the new set of layouts with the parent node of that identified leaf.

11. The system of claim 10, wherein:

the node identifying circuit, routine, or application identifies each node that has a single set of layouts associated with it; and

the set associating circuit, routine, or application, for each identified node that has a single set of layouts and no sets of layouts associated with any subnodes, associates that single set of layouts with the parent node of the identified node that has a single set of layouts and no sets of layouts associated with any subnodes.

12. The system of claim 11, wherein:

the node identifying circuit, routine, or application identifies each node that has more than one set of nodes associated with it;

the set creating circuit, routine, or application, for each identified node that has more than one set of nodes associated with it, creates a new set of layouts; and

the set associating circuit, routine, or application, for each identified node that has more than one set of nodes associated with it, associates the new set with that identified node that has more than one set of nodes associated with it.

13. The system of claim 12, wherein:

the horizontal combining circuit, routine, or application, selects a first set of layouts associated with that identified node, the first set of layouts containing a smallest layout, selects a second set of layouts associated with that identified node, other than the first set of layouts, that contains a smallest layout, horizontally combines a first layout from the first selected set of layouts with a first layout from the second selected set of layouts, and assigns the horizontally combined layout to the new set of layouts.

14. The system of claim 13, wherein, for each layout within the first selected set of layouts:

the horizontal combining circuit, routine, or application, for each layout within the second selected set of layouts, horizontally combines that layout from the first selected set of layouts with that layout from the second set of selected layouts; and

the layout size comparing circuit, routine, or application, for each layout within the new set for the identified node that has more than one set of nodes associated with it, compares the horizontally combined layout from the first selected set of layouts and the second set of selected layouts and that layout within the new set for the identified node that has more than one set of nodes associated with it;

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 layout size comparing circuit, routine, or application discards the horizontally combined layout from the first selected set and layout from the second selected set;

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, the layout size comparing circuit, routine, or application discards that layout within the new set for the identified node; and

if the layout size comparing circuit, routine, or application has compared the horizontally combined layout from the first selected set and the second selected set with every layout in the new set for the identified node without discarding the horizontally combined layout from the first selected set and the second selected set, the layout size comparing circuit, routine, or application adds the horizontally combined layout from the first selected set and the second selected set to the new set for the identified node.

15. The system of claim 14, wherein, for each layout within the first selected set of layouts:

the vertical combining circuit, routine, or application, for each layout within the second selected set of layouts, vertically combines that layout from the first selected set of layouts with that layout from the second set of selected layouts; and

the layout size comparing circuit, routine, or application, for each layout within the new set for the identified node that has more than one set of nodes associated with it, compares the vertically combined layout from the first selected set of layouts and the second set of selected layouts and that layout within the new set for the identified node that has more than one set of nodes associated with it;

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 layout size comparing circuit, routine, or application discards the vertically combined layout from the first selected set and layout from the second selected set;

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, the layout size comparing circuit, routine, or application discards that layout within the new set for the identified node; and

if the layout size comparing circuit, routine, or application has compared the vertically combined layout from the first selected set and the second selected set with every layout in the new set for the identified node without discarding the vertically combined layout from the first selected set and the second selected set, the layout size comparing circuit, routine, or application adds the vertically combined layout from the first selected set and the second selected set to the new set for the identified node.

16. The system of claim 15, wherein the layout size comparing circuit, routine, or application discards the first selected set and the second selected set.

17. The system of claim 16, wherein when the node identifying circuit routine or application determines that the root node has only one set of layouts associated with it, the layout testing circuit, routine, or application selects a smallest layout from the set of layouts associated with the root node as a solution layout.

18. The system of claim 17, wherein the media associating circuit, routine, or application associates summary media that summarizes the data within each leaf of the tree data structure with the respective location of each leaf within the solution layout.