A method of windowing image data in a computer system.

This invention relates to a method of windowing image data in a computer system. More particularly, this invention relates to a method of windowing image data in a computer system in which image data representing an image is maintained in a hierarchical tree structure.

In the application of graphic systems to design tasks, there has been an increasing demand for rapid processing of larger and larger amounts of data. An important area of vital interest to program designers has been in methods by which the data to be presented to the viewer can be rapidly windowed to accommodate veiwer initiated changes in the display request.

Typically, graphics display systems are known to keep subimages in a hierarchical data structure. When the hierarchical data structure is in the form of a data tree, the primitive images, such as, vectors, instances of characters or strings or arrays of characters and noncoded images, are placed at the leaves of the tree structure and attributes such as position and colour maybe placed throughout the data tree structure.

Presently, graphics systems ae designed to operate by placing a data window over a sheet which represents a large complete data image. The portion of the total image within the window is then presented to a viewport on a screen. However, when the window is moved dynamically, to produce an image change, the entire data structure must be traversed for a new image to be compiled. Thus, image changes require an enormous of amount of data to be searched with resultant processing problems of slow reaction time, of tying up of large amounts of data storage and other handling inefficiencies etc.

One method for assembling the image change data has been to process the entire data structure to determine which primitives must be clipped and displayed. However, as the viewer requested information is usually only a small portion of the image data, this method is very time consuming, inefficient and wasteful of large memory.

In another method for assembling viewer requested information, the complete data image has been first transformed line by line to a display format. Every line is then converted to screen coordinates to determine which lines are visible to the user and which can be clipped. Once again, the method is extremely inefficient as unnecessary transformations are made to data not intended to be viewed with requisite sorting of non-visible lines by coordinates.

A related technique which has been incorporated into the above process, known as instance transformations, is a visibility test called boxing as described in <u style="single">Principles of Interactive Computer Graphics</u> by Newman and Sproull, McGraw-Hill Book Company, 1979 (see especially pages 133 to 135). In this method, an extent of visibility is maintained for sets of data subimages. The extent of visibility is determined by a bounding box created for the graphic primitives in the sets of subimages. The bounding box is, then, able to define the data to be displayed by comparing said box to the window characteristics and clipping out unnecessary data. This method, however, requires an extremely accurate specification of the bounding box by the programmer, an extremely difficult task when rotation or similar image transformations are possibly part of the requested information. At best the method led to a gross approximation of a bounding box and large amounts of unnecessary data were will required to be transformed and stored.

It is therefore the object of the present invention to develop a method for windowing of display information in computer graphics which is efficient and provides fast response times.

In accordance with the invention, there is a method of windowing image data in a computer system in which image data representing an image within an image field is maintained ina hierachical tree with the complete image being defined at the root node and sub-images of said complete image being defined at lower order nodes, the primitive images which make up the sub-images and the image being defined at the leaf nodes of the tree, the method comprising the steps of: dividing the image field into a plurality of cells; defining a window which represents the area of the image field to be displayed; defining, around the window, a field of possible interest which comprises at least one of the cells; computing for at least one node of the tree summary node data identifying those cells if any within the field of possible interest which are at least partially occupied by the part of the image defined at that node; traversing the tree to determine, using the summary node data, which of the primitive images need to be processed for display in the window; and processing and displaying primitive images within the window.

A method is thereby provided for facilitating rapid windowing of display information is accomplished by dividing a large complete data image field, a "sheet," into a number of cells (or smaller area boxes) wherein the graphic primitives are placed in a hierarchical tree structure of precomputed data bits. An area of possible interest (or master box) comprising at least one cell is defined. The primitive images (i.e. vectors, instances of characters etc.) are at the leaf nodes (or leaves) of the tree structure and attributes such as position and colour may be placed throughout the data structure.In addition, summary node data comprising small numbers of bits of data are maintained at the nodes of the tree. The summaries are the product of ORing the summaries of lower-level branches. A field of possible interest, or "master box" is further defined for the sheet whereby the data displayed to the user is established by a window less than or equal to the master box.

On panning of the image by the user, the window is moved relative to the sheet and relative to the master box. As long as the window remains in the master box, the hierarchical data tree is traversed for the boxes within the tree and the frame buffer is refreshed. Once the window crosses out of the master box, a new master box has to be created. Following, there from, new summaries are computed at each node indicating which boxes have graphic data to be rendered. Those nodes containing graphic data are then processed to define the extent of the image data. This image extent data is then clipped to the new master box to define a new box. The new box is subsequently clipped to the window and graphic primitives render the image to the viewer.

The present invention is particularly described hereinafter, with reference to the accompanying drawings, of which: <ul id="ul0001" list-style="none"><li>Figure 1 is a diagrammatic representation of the relationship between a sheet, box, master box and window;</li><li>Figures 2.1 and 2.2 show diagrammatically a summary for a window; and</li><li>Figures 2.3 and 2.4 show a diagrammatic representation of a line with a 4 × 4 master box, respectively;</li><li>Figure 3 is a flow chart representing an overview of the window function of Figure 3;</li><li>Figure 4 is a flow chart of a traverse function which is controlled by the window function of Figure 3;</li><li>Figure 5 is a flow chart of a compute-summaries function which is also controlled by the window function of Figure 3;</li><li>Figure 6 is a flow chart for a "calc-sum" function;</li><li>Figure 7 is a flow chart for a "clip-render" function; and</li><li>Figure 8 is a diagrammatic representation of a line image passing through a master box which lies on a screen.</li></ul>

Figure 1 shows a sheet, 1, which is a large area that contains data for an image that could be rendered by line primitives or area primitives. The area primitive may be text, icons or image data specified as two coordinate pairs and the pixel data. The window 3 represents the area on the screen which the user is presently viewing. This window information is displayed on a viewport on a graphics terminal. The master box 5 is an area larger than or equal to the window 3. While the user stays within the master box 5 windowing is governed by one function called "traverse." When the user crosses the master box 5 a special computation involving the calculation of summaries takes place and then a new master box is establilshed which is shifted in the direction the window was travelling. The window, master box and sheet are all multiples of the box size. The sheet may contain many of the smaller boxes 7. In the present description, the window 3 is the size of one box and the master box 7 is comprised of sixteen boxes.

Five basic functions comprise the rapid windowing. A first function called the "window" function effectively governs two further functions or processes in the system.

The first of these is "traverse" which searches a tree structure containing a set of graphics primitives at the leaves. The nodes (a leaf is also a node) group the images into subimages. During the screen is also updated to reflect windowing within the master box.

The other process controlled by the window function is the computing of summaries which is required whenever the window has crossed the master box. A summary is a matrix of bits attached to a node. The summary of a node tells which boxes in the master box have graphics data from the subimage identified by the node to be rendered in that box. Figure 2.4 shows a summary for a 4 × 4 master box. Each bit in the summary represents part of a line passing through a box as shown in Figure 2.3. For each node in the tree, the summary associated, therewith, describes all the graphical data passing through the master box.

The two other functions are "calc-sum" which calculates a summary and "clip -render" which clips and renders a line or area primitive on the screen as defined by the window.

The flow diagram in Figure 3 describes the "window" function. As indicated in the FIGURE, windowing or searching is performed in a looping manner a "while" function until the user stops windowing. A test then determines if the window is in the master box which causes the function "traverse" to be executed and the window function to continue looping. If the window is not in the master box (i.e., it has passed through the master box), the function "compute-summaries" is executed, and later "traverse" is executed.

The function "traverse" is described in Figure 4. The function begins by stacking the root node using the function "npush" and then entering into a loop. At the top of this loop, a node is popped off the node stack, and then one of three cases is obtained. The node is either (1) empty, (2) the node is a leaf or (3) the node has sub-nodes. In case one, if the node is empty, the function is exitted because the traversal is complete. In case two, if the node is a leaf node, one of two situations exist determined by two variables : summary and a mask variable called "window-summary."

An example of a window-summary is described in Figures 2.1 and 2.2 which shows a window within a master box and a corresponding window-summary that is essentially a summary with ones indicating where the window is on the master box. Figures 2.3 and 2.4 have already been described and show a master box with a line passing through it and a summary of that line indicated by a matrix of 1 and 0's placed in a 4 × 4 array. The similarity between a summary and a window-summary can thus be seen directly.

Now in case two above, if the summary ANDed with the window-summary is zero, (no graphic primitives in the window), sub-nodes can then be skipped, and the control returns to the top of the loop to start with the next node on the stack. Otherwise, the "clip-render" function is executed, which draws the line or writes an area and then control is returned to the top of the loop.

The third case is when a node has sub-nodes. A test is made to determine if summary ANDed with window-summary is nonzero. If it is nonzero it indicates that some part of the image under the node appears in the window. Therefore, all the sub-nodes under that node are pushed on the stack by a function called "push-sub-nodes."

Thus, the function "traverse," searches a graphic tree structure for leaves containing a graphic primitive that may need clipping and rendering. When summaries indicate rendering may be required then sub-nodes are processed. If the summaries indicate that no rendering is to be performed then the sub-nodes of that node are skipped.

The "compute-summaries" function described in Figure 5, is executed when the window passes through the master box. This function accesses the tree data structure containing nodes and summaries associated at each node. In operation, two working stacks are used. One stack contains the nodes (n) and the other stack contains the summaries (s). In the first statement of this function the root node (n push (root)) and a summary of zero (spush (0)) are stacked to begin the traversal of the nodes in the tree. A loop is then entered with a while statement and a node and summary are popped. Then, one of four cases is obtained.

In case one if the node stack is empty the process is completed and the function returns to the window function of Figure 3.

In case two if the node is a leaf, then a calculation of a new summary for the leaf is made and it is ORed with a previous summary on the stack. This is the mechanism by which a sibling node passes summary values to the next higher order sibling and finally to the parent node. The statements for processing a leaf node show that a summary named "asum" is popped and a new summary called "summary" is calculated for the node. (See Figure 6 for calc-sum function). Summary ORed with asum (XS) is then pushed back on the stack and the process cycles to the top of loop. Also summary is set in the tree structure. The reason for this is that a summary value is placed on the stack for summaries (which is used to OR summaries among siblings and up the tree to parents) and is also placed in the tree structure (for use in windowing).

The third case governs the process by which the tree is traverse down to the leaves and also up toward the root. During the up traversal the ORing of summaries is performed. The bits of the ORing originates in the leaf nodes and are propagated up the tree. The mechanism used is that when a node is first placed on the stack it is considered a new node, and when processed as a new node becomes an old node. Later when the node is processed as an old node the ORing of summaries takes place up the tree.

In case three although n was popped above, it is pushed back on the stack and all the siblings of node are placed on the stack with the function "push-sub-nodes" which sets the sub-nodes to new. The function "push-zero-sums-for-sub-nodes" stacks zero summaries for the sub-nodes. Finally the attribute of the node is set to be an old node and control returns to the top of the loop.

In case four, an old node indicates traversal up the tree. Obtaining asum from the stack and summary (s) from a previous pop the two are ORed, placed on the summary stack and the summary value from the stack for that node is inserted in the tree structure and control returns to the top of the loop.

Figure 6 describes the function "calc-sum" which calculates a summary only for a leaf node. (Case 2 of "compute-summary" function). First, the variable xbox is set by the function get box which obtains values from the tree structure. Xbox contains the extent (two coordinate pairs) for either a line or an area to be written on the screen.

Then, the function "clip" compares xbox with the master box and clips xbox to master box making a new box called new-box. Next, the function "in-box" determines whether new-box is in master box. If it is not, then its summary is set to zero and the remaining statements are skipped. If new-box is in the master box, the next test determines whether the leaf node is a line or an area primitive. If the node is a line, the function "calc-summary-for-line" determines for new-box the set of the boxes that are intersected by the line. If the leaf node, primitive is an area rendering primitive, then another function called "calc-summary-for-area" examines all the boxes in the new-box which are covered by a full or part of the area to be rendered.

The last function is "clip-render." This is called whenever a line or an area primitive is to be drawn on the screen and clipping must be done before the actual rendering on the screen. Figure 8.1 shows a line passing through a master box which lies on a screen. Xbox in Figure 8.1 describes the extent of the line and new-box in Figure 8.2 is a box clipped to the extents of the line. Finally, a summary in Figure 8.3 is calculated using the new box which determines that four of the boxes in the summary have a line passing through them.

Figure 7 describes the function "clip-render." The first two statements in Figure 7 are the same as used in calc-sum. The coordinates of the extent of the line or area primitive are obtained and placed in xbox. With this function, however, xbox is clipped to the window-box. For assembling image to be rendered, graphic primitives for drawing a line or writing an area are invoked depending on the type of the leaf node.

The above description and figures 3 to 7 described the various functions in programming terms. The person skilled in the art will of course realise that the functions could be implemented in a number of different ways, as programs or, for example, by special purpose logic.

Through the present invention, therefore, there is provided a method for facilitating rapid windowing of image data in computer graphics including the steps of dividing the data image into a number of smaller area boxes, the graphic primitives being placed in a hierarchical tree of precomputed data bits with the primitive images at the leaves of the tree, maintaining small numbers of bits of data at the nodes of the tree which small numbers of bits of data represent the product of ORing the summaries of the leaves of the trees in an ascending manner, defining a master box greater than or equal to one box, establishing a window of a preset data capacity less than or equal to the data size of the master box such that said window represents the area of the data image which is displayed on the screen, locating said window in relationship to the master box such that the window is in the master box, computing small numbers of bits of data at the nodes of the tree for those smaller boxes within the master box, traversing the data trees for the boxes within the master box for graphic primitives calculating the extent of the complete image and clipping the image to the size of said master box calculating the extent of the image in the master box and clipping the image to the size of the window box invoking graphic primitives to render the image to the veiwer.

The steps of locating the window in the master box and traversing may be performed in a loop until the window is moved out of the master box and then a different master box is defined around the window and new summaries for the boxes within the master box are calculated.

The small number of bits of data at the nodes of the tree may be computed by creating two stacks, one for node values and one for temporary summary values, such that by pushing sub-nodes values onto the node stack and temporary summary values onto the other stack, a set of small numbers of bits of data for the sub-nodes may be determined. The small number of bits for each respective sub-node can be ORed together to produce a small number of bits of data for the node above the sub-node.

The nodes of the tree may be new nodes which produce sub-nodes to be stacked.

The nodes of the tree may be leaf nodes which have summaries calculated therefrom if part of the leaf graphic primitive impinges on the master box.

The nodes of the tree may be old nodes which cause summaries to be calculated by ORing with other summary values from the stack.

In the step "traversing" a graphic tree structure is searched for leaves containing a graphic primitive that may need clipping and rendering and when summaries indicate that rendering may be required then sub-nodes are processed otherwise the sub-node are skipped.