User Selectable Adaptive Degradation for Interactive Computer Rendering System

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.

The advances in Personal Computer ("PC") technology have made possible the introduction of relatively inexpensive workstations for word processing, accounting, graphical design and other similar applications which previously required dedicated use of PC-Based Workstations. Visualization of three dimensional objects set in three-dimensional space has traditionally been hindered by the demands placed by existing software on the computers. The complex mathematical operations required for correctly drawing and rendering three-dimensional objects including hidden surface removal, application of texture, lighting, shadows, and animating the three-dimensional objects make heavy demands on the PCs used for this purpose. Typically, the PC-based systems were designed to defer most of the detailed rendering until after the design was complete. Although this compromise improved the performance of the systems, while designing the scene, the designer was not able to view a substantially accurate representation of the final scene.

In the past, typically only dedicated high-performance graphical workstations or super computers were capable of performing the complex and numerous computations associated with rendering three-dimensional objects while the designer was interacting with the objects in the scene. Less capable systems typically restricted the designer to manipulating wire-frame, or other simplified renditions of three-dimensional objects while editing the scene, and postponing the final rendering of the objects until after the scene has been composed.

This approach has the drawback of preventing the designer from appreciating the full impact of the changes made during the design of the scene. The designer is therefore forced to manipulate wire-frame representations or other simplified renditions of the objects in the scene, render the scene, review the details, and return to the wire-frame or simplified rendition for making adjustments to the scene based on the rendered view. This interactive approach requires many iterations between the wire-frame or simple renditions of the scene and the rendered view, forcing the designer to anticipate how the scene would appear once it is fully rendered without the benefit of actually seeing the objects in their final rendered form.

Another disadvantage of the typical interactive approach is that the designer cannot select the level of detail associated with each stage of the operation according to the designer's requirements.

It is therefore the object of this invention to maximize the performance of a three-dimensional design and rendering system by enabling the designer to select the trade-off between rendering speed and image quality based on the designer's requirements and the performance of the system available.

The adaptive degradation system of the present invention when incorporated into a three-dimensional design and rendering system, running on personal computers or other workstations, permits the designer to select the minimum scene refresh rate or animation redraw rate acceptable by the designer. The system also incorporates a selection of presentation methods for the three-dimensional objects in a scene, arranged in decreasing fidelity, and consequently in computational complexity, as fall back positions for the general rendering technique. Using the designer's selected refresh rate as a target, the system attempts to use the highest quality rendering technique selected by the designer. If the computational complexity of the scene causes the refresh rate of the scene to fall below the minimum acceptable level selected by the designer, the system selects the next lower rendering option selected by the designer, thus degrading the presentation quality of the scene and simultaneously reducing the computational complexity of the task.

If the designated refresh rate can be maintained at that level of degradation, the system continues to use that degradation level until the computation load on the system is lightened to the level where the higher quality rendering could be attained without reducing the refresh rate of the scene below the level designated by the designer. If, however, the user has selected more than one degradation option and reducing the interim quality of the scene to the first degradation option is not sufficient to maintain the frame rate designated by the designer, the system automatically reduces the degradation to the second and subsequent rendering options until the refresh rate selected by the designer is attained or lowest level of degradation of the rendering selected by the designer is selected by the system.

The automatic tradeoff between the scene refresh rate and rendering complexity will make it possible to maximize the performance of the overall system on any given computational platform.

These and other objects, features and advantages of the invention will be apparent from the following description which will be read in light of the accompanying drawings in which the corresponding reference numerals refer to corresponding parts throughout several views.

FIG. 1b is a high-level block diagram showing the rendering sequence used by the system which incorporates this invention.

FIGS. 2a-2c are flowcharts showing the operation of the adaptive degradation system of the present invention.

FIG. 2d is a flowchart showing the operation of an alternative embodiment of the adaptive degradation system of the present invention

FIG. 3a is an example of a screen showing the various rendering options available to the user for rendering a scene.

FIG. 3b is an example of a screen showing the options available to the user in setting the parameters used by the system to control the level of degradation of the rendering of the scene.

FIGS. 4a-4d illustrates the operation of the adaptive degradation system as part of a three-dimensional designer rendering package:

FIG. 4a shows a fully rendered scene containing multiple objects;

FIG. 4b shows a single object from the scene selected for manipulation by the user;

FIG. 4c shows the selected object being manipulated by the user causing a degradation according to the option selected by the user of the system; and

FIG. 4d shows the termination of the manipulation of the objects by the user returning the scene to a fully rendered state.

FIGS. 5a-5e illustrates multilevel degradation of the rendering of objects in a scene with the adaptive degradation system of this invention as part of a three-dimensional design and rendering package:

FIG. 5a illustrates a scene containing multiple objects fully rendered;

FIG. 5b shows a single object being selected by the user for manipulation;

FIG. 5c shows the manipulation of the object causing first level of degradation according to the option selected by the designer;

FIG. 5d illustrates further manipulation of the same object causing a second degradation to a lower level of rendering according to the option set by the designer; and

FIG. 5e illustrates the result of the termination of the manipulation of the selected object by the designer, causing the scene to be fully rendered once again.

FIG. 6 is a high level pseudo-code sequence illustrating the adaptive degradations system of the current invention.

One embodiment of the invention includes a PC-Based system, such as an IBM compatible personal computer or a Macintosh.TM. computer available from Apple Computer, Inc. of Cupertino, Calif.

Referring to FIG. 1b, the overall structure of the adaptive rendering system 100 can be seen. During operation, system 100 is loaded in the Random Access Memory 40 of the computer system 10. Computer system 10 includes one or more Central Processor Units (CPU) 20. Typically the CPU 20 is a Pentium.RTM. processor manufactured by Intel Corporation, however, the adaptive degradation system of this invention may be implemented on any general purpose computer system.

The user operates system 100 via keyboard 30 and graphic input device 30, typically a mouse or digitizing tablet. System 100 includes graphic system user interface 102, geometric pipeline 104, rendering system 106, degradation controller 108, clock 110, user interface 124, controller settings 12, and a display 114.

User interface 124 is a conventional Graphical User Interface that permits the user to enter commands and data to the graphic system 102 via keyboard 30 and graphical input device 60. Graphic system 102 allows the user to enter and modify two or three dimensional scenes containing one or more two or three dimensional objects. Graphic system 102 is coupled to geometric pipeline 104 which converts the high level description of the objects specified by the user to a series of vertexes describing, in three-dimensional space, the object specified by the user as well as any transformations that are applied to the object by the user. Geometric pipeline 104 also generates additional information needed to correctly represent each object, such as a list of connected vertexes, the texture map of the object, the surface normals for each face of the object and a three-dimensional bounding box of the object.

The output of the geometric pipeline for each object in the scene is sent to rendering system 106 which calculates the correct two dimensional screen representation of the three-dimensional vertexes for each object for display on computer display 114. The process of calculating the correct two dimensional screen representation of the three dimensional scene entered by the user is called "rendering the scene" or "rendering". The scene is updated continuously to permit the user to observe the effects of any changes introduced into the scenes by the user. The changes may include translations of the one or more selected objects in the scene, modification of one or more objects in the scene, translation of lighting sources and light types and camera position in the scene, the introduction of atmospheric elements such as fog, addition or modification of materials and textures, etc. Each update of the complete scene is called a "frame". The number of frames generated per second is the "refresh frame rate" or "frame rate" of the system 100.

Rendering system 106 contains a plurality of rendering subsystems such as subsystems 106a through 106g. Each rendering subsystem receives the vertexes received by rendering system 106 and generates a representation having a different level of detail. For example 106a generates a three-dimensional bounding box enclosing the vertexes; 106b generates a wireframe image of the vertexes, 106c generates a wireframe image of the vertexes with lighting highlights, 106d generates a faceted solid representation of the vertexes, 106e generates a faceted solid representation of the vertexes with lighting highlights, 106f generates a smooth solid representation of the vertexes; and 106g generates a smooth solid representation of the vertexes with highlights added to show the effect of lighting on the structure. Typically only one subsystem is used to render the vertexes sent to the rendering system 106 by geometric pipeline 104. The rendering subsystem is selected through the rendering selection input 116. The two-dimensional screen representation generated by rendering system 106 is sent to the computer display 114. Rendering system 106 uses as much of the information provided by geometric pipeline 104 as possible to avoid duplicate calculations. For example, when the geometric pipeline 104 calculates a three dimensional bounding box for an object, rendering system 106 would select a rendering subsystem that only displays the bounding box calculated by the geometric pipeline without re-computing the correct boundaries of the bounding box.

When the rendering process for an object begins and ends the rendering system notifies the Adaptive Degradation controller 108 via rendering signal 118. Adaptive degradation controller 108 determines the refresh frame rate for the object being rendered using the rendering signal 118 and clock input 120, connected to system clock 110. The user selects the options for the operation for the adaptive degradation using control settings 112. The options are communicated to the adaptive degradation controller 108 via options input line 122. Adaptive degradation controller 108, selects the rendering subsystem (106a through 106g) to be used by the rendering system for the current vertexes via rendering option control line 116.

The operation of the adaptive degradation system 100 can be seen in flowchart 150 in FIG. 2a. System 100 is initialized with the values selected by the user (as described in more detail below in connection with FIG. 3). System 100 also sets the current rendering selection to the value specified as the general rendering option (step 152). In step 154 system 100 determines if any objects remain to be rendered. If no objects remain the process exits. If objects remain to be rendered, system 100 proceeds to step 156 and renders the object using the current rendering selection. System 100 calculates the refresh frame rate in step 158. In step 160, the refresh frame rate is compared with a threshold frame rate specified by the user (as described in more detail below in connection with FIG. 3). If the refresh frame rate falls below the threshold frame rate specified by the user, the adaptive degradation controller 108 resets the current rendering option to the next rendering subsystem (106a-106g) which has a lower computational complexity and is specified by the user in step 152.

The operation of the rendering step 156 can be seen in flowchart 156 in FIG. 2b. The rendering system checks the scene to determine if the entire scene has been rendered in step 164. If the scene is completely rendered, step 156 terminates. If objects remain to be rendered, the rendering system determines if any objects have been modified since they were last rendered, or if they are no longer selected by the user, in step 166. The system stores the rendering time for each object to assist in predicting the frame rate for the system. Modifying any object, or changing the current selection of objects invalidates the stored rendering time for the object, and the rendering time required for that object must be measured anew. If the object has been modified, or the selection changed by the user, a changed object flag is set in step 168. In step 170, the appropriate rendering subsystem is selected based on selection signal 116, and the object is rendered in step 172. The changed object flag is checked in step 174. If the flag is set, the time to render the object is stored in step 176.

The operation of the frame rate calculation step 158 can be seen in flowchart 158 in FIG. 2c. The rendering time for each remaining object in the scene is summed in step 178. The effective frame rate of the scene is calculated in step 180. Using the previous rendering times for each object, the system can predict the frame rate of the scene and reduce the rendering quality of the remaining objects in the scene in attempting to maintain the frame rate specified by the user. When the adaptive degradation system of the present invention is used in a graphic system with both active and non-active viewports (as shown in detail in FIGS. 3 through 5) typically, the user focuses on the active viewport for editing and viewing the scene. Preferably, the active viewport is rendered first to permit it to use the majority of the time if necessary. This approach permits the active viewport to be rendered using the highest practical rendering quality to assist the user in better visualizing the scene. The non-active viewports would degrade more than the active viewport and the time available is allocated preferentially to the active viewport.

In an alternative embodiment of the invention, illustrated in flow chart 151 in FIG. 2d, step 156 is postponed until after step 160. The time required to render the scene is predicted by the systems by summing the elapsed time for rendering each of the objects in the scene from the prior frame. The rendering subsystem to be used (106a-106g) is then selected based on the anticipated rendering time for the current frame which is assumed to be the same as the time consumed in rendering the previous frame. The rendering takes place in step 156 using the selection made in steps 160 and 162.

During the initialization step 152 the user may adjust one or more parameters which control the operation of the system. Default values for the parameters in step 152 are provided at startup. FIG. 3a shows a typical set-up screen 300 used to select the general rendering level of the scene. Using the rendering level selection box 302 the user sets the general rendering method. The user makes a single selection in selection box 302. The user can further select to restrict the rendering option to one of the active viewports or to apply to all the viewports on the screen by selecting the appropriate option in selection box 304. In FIG. 3a, the user has selected as the general level the highest level rendering available by this system, specifically the smooth rendering of the sides plus the application of highlights caused by the scene's lighting.

During the initialization step 152, the user may use degradation selection boxes 312 and 314 from the adaptive degradation screen 310 (FIG. 3b) to select, from a palette of available subsystems (106a-106g), the rendering subsystems which may be used by the rendering system 106 to render the scene. The rendering subsystems are arranged in selection box 302, 312 and 314 in descending order of computational complexity. The user may select one or more rendering subsystems in selection boxes 312 and 314. Selection box 312 selects the rendering subsystems used by all the non-active viewports. Selection box 314 is used to select the rendering subsystems used by the rendering system 106 to render the scene in the active viewport only. The distinction between active and non-active viewports will be discussed in detail in connection with FIGS. 4 and 5 below. Generally, when the system is displaying the scene in more than one viewport, the active viewport is the viewport most recently manipulated by the user.

Using option selection box 316, the user may also adjust the frame rate that is used in step 160 to initiate the degradation process in step 162.

Separate degradation options provide more flexibility in selecting the level of degradation acceptable to the designer. The active viewport is generally the focus of the manipulation of the objects and a different level of degradation may be tolerable by the designer in that viewport than in other views of the scene displayed in the non-active viewports. In addition, since the active viewport receives its share of the rendering time first, the active viewport will maintain the highest degree of rendering quality among the several viewports.

As seen in the selection box 316, a dialogue box and appropriate controls are provided to permit the user to select the desired refresh rate of the screen in units of frames per second ("FPS"). The user has the option of selecting a mouse up event as the point where the degradation is terminated and the scene is re-rendered using the selected rendering method as well as the ability to show an interim or rebuilding cursor to inform the designer that a rendering operation is under way.

Other settings located on screen 310 are the Interrupt Settings parameters in option selection box 318. The user may select an update time using the controls located in option selection box 318. The update time setting permits the user to specify a period of time in seconds and fractions of a second. If rendering the scene requires more time than specified in the update time parameter, the screen is updated at intervals equal to the update time setting. For example, if the scene requires ten seconds to render, and the update time setting is set at one second, after the passage of each second of processing time the partial results of the rendering operation are merged with the existing image on the screen. This option permits the user to see the interim results of rendering operations requiring long periods of time to complete. If necessary, the operation can be interrupted without having to wait for it to complete.

The second parameter located in option selection box 318 is the interrupt time setting which specifies the frequency at which the system accepts inputs or possible interruptions from the designer. The setting shown in FIG. 3b for interrupt time is 0.25 which specifies that while the system is busy rendering the scene every one quarter of a second the system checks for input from the user to permit the user to change the parameters or the interrupt operation in progress. Typically, the interrupt detection process controlled by option selection box 318 is a computational thread or process running independently of the rendering system 106. The user may change any of the settings contained on the adaptive degradation screen 310 at any time during the operation of the system, however default values are provided at the initial start-up of the system for the user's convenience.

The operation of the adaptive degradation feature of the preferred embodiment of the adaptive degradations system is further illustrated by the pseudo code contained in FIG. 6. The initialization step 152 may involve performing the functions listed under the heading Initialize Adaptive Degradation in FIG. 6. As shown by the pseudo code sequence in FIG. 6, the adaptive degradation system begins by setting the current rendering level to the general rendering level selected in options selection screen 302. The system then resets the rendering interval timer to the value specified in the update time value in option selection box 318 and resets an interrupt timer to the value set in the interrupt time parameter of the option selection box 318.

For each object in the scene the system calculates the time required to render that object using the current rendering level based on prior rendering of the same object. If, based on the frame rate selected in the "maintain FPS" parameter set in options selection box 316, enough time is available to render the object at the current rendering level, the object is rendered using the current rendering level. If insufficient time remains, and if the reset on mouse up option is selected in options selection box 316 then the system reduces the current rendering level of the viewport being rendered to the next rendering level set in options selection box 314 (for the active viewport) or 312 (for non-active viewports). If the reset on mouse up parameter is not selected by the user, then the system reduces the current rendering level to the lowest rendering level selected by adaptive degradation system in rendering the last frame of the scene.

If the time used to render the scene has exceeded the update time specified in the "update time" option set in option selection box 318, then the system updates the screen with the rendering results available at that time and the rendering interval timer is reset by the system.

Simultaneously with checking the rendering interval timer, the system also checks if the interrupt timer has equaled or exceeded the values set in the "interrupt time" parameter set in option selection box 318. If the interrupt time has been equaled or exceeded, the system enables interruptions to the rendering process for a certain period of time to permit the user to interrupt the rendering process and then disables the interruptions and proceeds to rendering the next portion of the current object and repeats the steps outlined above until every object in the scene has been rendered.

The adaptive degradation system provides the additional advantage to the designer that it responds automatically to any computational load that causes the frame rate to drop. The system is not limited to responding to loads imposed on the computer by the design system alone, but background tasks or the computational requirements of other programs running in a multi-tasking or multi-threaded environment will trigger the adaptive degradations system automatically, if their requirements for computer resources cause a reduction in the system's frame rate. Examples of such processes include Electronic Mail programs, index and search programs, communication programs, data base access programs, etc. which are running concurrently with the design system.

The scene is initially rendered using the general rendering method selected in option selection box 312. When the scene is manipulated or animated causing the frame rate to fall below the value specified by the designer, the system automatically reduces the scene's rendering quality by selecting the next lower quality rendering subsystem (106a through 106g) selected in the option selection boxes 312 and 314 until the frame rate specified by the designer is achieved or the selected object or objects are rendered using the rendering subsystem showing the lowest level of detail. When the actions that caused the reduction of the frame rate, such as object manipulation, or increased computational load due to the activation of background tasks are terminated, the rendering quality is returned to the general rendering method.

At any stage of the process, the designer may choose to override the adaptive degradation system and force the system to render the scene using the general rendering technique. When the override is in effect, the refresh rate may fall below the selected refresh rate. When the designer removes the override, the adaptive degradation system resumes operation.

FIGS. 4a through 4d illustrate the user's view of the adaptive degradation system of the present invention.

In FIG. 4a, the viewport screen 320 is divided into 4 viewports: the active viewport 324 and non-active viewports 322. The configuration is illustrative, and numerous other configuration of viewports are possible and selectable by the user. The viewports display, from varying perspective, the same three dimensional objects 326. The degradation override feature 328 is not engaged, therefore the adaptive degradation system is in operation.

In FIG. 4b, in the active viewport 324, one object 330 is selected for manipulation. The selected object is superimposed with a selection box in all viewports (322, 324).

In FIG. 4c, the selected object 330 is manipulated by the user, and the adaptive degradation system is triggered. The selected object 330 is no longer displayed as smooth shaded with lighting highlights as in FIG. 4b, but is now shown rendered as a lit wireframe in the active viewport 326, and as a bounding box in the non-active viewports 322. The non-selected objects 324, are displayed rendered at their original rendering level.

In FIG. 4d, the manipulation of the selected object 330 is complete. The selected object is rendered using the general rendering level selected in option selection box 302, in both the active viewport 324 and the non-active viewports 322.

FIGS. 5a through 5e illustrate another example of the user's view of the adaptive degradation system of the present invention.

In FIG. 5a, the viewport screen 320 is divided into 4 viewports: the active viewport 324 and non-active viewports 322. The configuration is illustrative, and numerous other configuration of viewports are possible and selectable by the user. The viewports display, from varying perspectives, the same three dimensional objects 326. The degradation override feature 328 is not engaged, therefore the adaptive degradation system is in operation.

In FIG. 5b, in the active viewport 324, object 330 is selected for manipulation 330. The selected object 330 is superimposed with a selection box in all viewports (322, 324).

In FIG. 5c, the selected object 330 is manipulated by the user, and the adaptive degradation system reduces the rendering quality of the selected object. The selected object 330 is no longer displayed as smooth shaded with lighting highlights as in FIG. 5b, but is now shown rendered as a lit wireframe in the active viewport 324, and as a bounding box in the non-active viewports 322. The non-selected objects 326, are displayed rendered at their original rendering level.

In FIG. 5d, the selected object 330 is further manipulated by the user, and the adaptive degradation system further reduces the rendering quality of the selected object. The selected object 330 is no longer displayed as a lit wireframe in the active viewport as in FIG. 5c, but is now shown rendered as a bounding box in both the active viewport 324 and the non-active viewports 322. The non-selected objects 326, are displayed rendered at their original rendering level.

In FIG. 5e, the manipulation of the selected object 330 is complete. The selected object is rendered using the general rendering level selected in option selection box 302, in both the active viewport 324 and the non-active viewports 322.

While the foregoing invention has been described in reference to its preferred embodiments, it should be understood that various modifications and alterations will occur to those practiced in the art. Such modifications and alterations are intended to fall within the scope of the appended claims.