Computer graphics processing and selective visual display system – Display driving control circuitry – Controlling the condition of display elements
Reexamination Certificate
1998-04-07
2001-03-20
Zimmerman, Mark (Department: 2772)
Computer graphics processing and selective visual display system
Display driving control circuitry
Controlling the condition of display elements
C345S215000, C345S215000, C345S440000
Reexamination Certificate
active
06204850
ABSTRACT:
BACKGROUND
1. Field of Invention
The present invention relates generally to information display and navigation techniques, and more particularly, to the display of, and navigation through, arbitrarily graph-structured information spaces.
2. Background of the Invention
Computer systems are particularly useful for storing and searching large bodies of information. The information in such collections is typically arranged hierarchically in order to capture various types of relationships between items of information, and to organize the information into various classes, categories, and the like. Given a hierarchical arrangement of the information, it is conventional to display the information using various hierarchical representations.
FIG. 1
illustrates a conventional display of a hierarchical listing of items, here a screen shot showing Microsoft Corp.'s Explorer software application from the Windows95 operating system. Explorer uses a hierarchical outline as the visual interface for displaying and navigating the hierarchical relationship of files in a file system. Similarly, many word processors provide an outline mode to display the hierarchical structure within a document. Hierarchical outline displays are useful for small, well-understood hierarchies, but become difficult and tedious to navigate for large, deep hierarchies. This is because larger hierarchies either have numerous levels of categorization (i.e. deep hierarchies), which requires the user to navigate down through many different levels to a specific item, or have fewer levels (i.e. shallow hierarchies) but many items per level, requiring the user to review the numerous items at each level.
An alternate method for displaying hierarchies is to model and display the hierarchical relationships between information items as self similar branches of decreasing scale in a single absolute coordinate system with two or more dimensions. Display and navigation techniques in these systems then allow users to magnify and expand regions of interest to both visualize overall structure and to find data objects of interest. This type of multi-resolution visualization can be seen as either the ability to manipulate and scale the data structure, or as the ability to translate and scale one's point of view. Both are equally valid and equivalent ways of looking at the same operations.
Pad and Pad++ by Kenneth Perlin of New York University are examples of systems using this technique in two dimensions. Graphical data can be scaled to any size and placed anywhere within a continuous 2D surface, and multiple surfaces may be used, and windows or portals onto the surfaces may be arbitrarily placed. The user can expand, contract, and pan around to view any part of the surface at any scale. While Pad and Pad++ can represent hierarchical information structures, they do so only within continuous 2D surfaces by embedding and shrinking nested surface regions within one another. This limitation to representations and organizations of information to flat surfaces fails to graphically capture the rich variety of semantic relationships that items of information may have with one another.
One of the most significant problems with modeling hierarchies in absolute coordinates is the difficulty of maintenance. For any object to be placed in a hierarchy, a graphical representation of the object must be assigned coordinates placing it rigidly within the coordinate system. By analogy this is the equivalent of modeling a house brick by brick. Instead of simply stating where the house is to be placed, one must determine where every brick goes. This rigidity also makes it difficult to alter hierarchies once they have been created. Continuing the analogy: just as moving the house would require specifying a new location for each brick, altering the hierarchy would require specifying a new location for each object.
Another problem with absolute coordinate spaces is numerical resolution. While it is mathematically simple to think of a system that allows absolute coordinates to be computed within a hierarchy, in order to be used on a typical computer, those coordinate values must be stored with some finite precision. As the number of levels in a hierarchy grow beyond even a moderate number, even double precision numbers quickly run out of resolution to adequately represent numbers at very different scales, and thus very complex hierarchies. While there are methods for storing numbers with arbitrary precision within computers, the cost in additional memory and especially in processing time is usually prohibitive, and may impair real-time navigation within the hierarchy.
As an alternative to absolute coordinate systems, relative coordinate systems have been used for modeling hierarchies of graphical objects, for example in computer animation and computer aided design. Relative coordinate modeling means describing each graphical object in its own coordinate system and then using or “instancing” them wherever they are needed in the overall graphical structure. At display time, each instance of an object takes its scale, position and possibly other attributes from its parent. This approach provides flexibility since moving or reparenting a node simply involves moving or transforming a link. The results of such changes are only observed at display time. Using the house analogy, this approach is like moving a house by simply changing its address instead of moving it brick-by-brick.
The use of relative coordinates also solves the problem of numerical resolution. Each object can be modeled using the full range of numerical resolution. It is only when extremely large and small objects must be rendered in the same coordinate system that numerical problems creep back in. Usually, there is sufficient resolution available in traditional single and double precision numbers to have the added luxury of modeling each object in terms of the most natural units for those objects: feet or meters for human scale objects, Angstroms for molecules, and so forth.
Thus far only strict hierarchical models (i.e., true trees) have been described as potential representation systems. However, it is often very important to be able to represent, display and navigate more general graph structures that may contain loops or other cyclic relationships. Such structures would be impossible to represent completely in absolute coordinates, and even relative coordinate systems have difficulty with them. To see this, imagine a node A that contains node B. Being a sub-node, node B (or a copy of it) would need to be graphically modeled “smaller” and contained within node A when using an absolute coordinate system. If node B also contained node A, then it would need to contain a smaller copy of A that would contain an even smaller copy of B, ad infinitum. In a system that displays only a portion of a general graph at a time as a user navigates from node to node, a relative coordinate system avoids the need to produce copies of graphical nodes at varying locations and scales. The viewing mechanism could descend from A into B and then deeper again back into A as many times as desired. However, with relative coordinate systems, cyclic information structures may still cause infinite recursion of context. For this reason, cyclic graphical structures are typically not allowed in conventional absolute or relative coordinate modeling systems.
Accordingly, it is desirable to provide a system and method for representing and navigating arbitrarily graph structured information spaces.
SUMMARY OF THE INVENTION
The present invention overcomes the limitations of conventional information representation and navigation systems by providing a 3D display and navigation system that employs an arbitrarily structured set of graphical nodes and a viewer module. The graphical nodes correspond to and graphically represent information nodes in an information structure. Each of the information nodes may have a number of semantic containment relationships with child information nodes. The semantic containmen
Fenwick & West LLP
Stevenson Philip
Zimmerman Mark
LandOfFree
Scaleable camera model for the navigation and display of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scaleable camera model for the navigation and display of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scaleable camera model for the navigation and display of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2497370