System and method for interactive rendering of three dimensional objects

[0002] This application claims the benefit of U.S. Provisional Pat. Application No. 60/025,117, entitled, “Three Dimensional Modeling and Animation System,” filed Aug. 2, 1996, by inventors Rolf Walter Berteig, Daniel David Silva, Donald Lee Brittain, Thomas Dene Hudson, and Gary S. Yost, which is incorporated herein by reference.

[0003] 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.

[0004] 1. Field of the Invention

[0005] The present invention relates to the field of three-dimensional computer graphics, and more particularly to a system and method for manipulating and rendering of selected three-dimensional objects within a scene using a computer.

[0006] 2. Related Art

[0007] 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 workstations. The use of PC-Based workstations for 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 makes heavy demands on the PCs used for this purpose. Typically, the PC-based systems were designed to defer most of the detailed rendering to after the design was complete. Although this compromise improved the performance of the systems, a graphic designer was not able to view a substantially accurate representation of the final scene while designing the scene.

[0008] Computational demands placed on PCs are particularly severe when one or more objects located in a complex scene are being manipulated by the designer. In a conventional system, the entire scene is rendered continually while the objects are being manipulated by the designer. As a result, even if most of the scene is not affected by manipulation of the selected object or objects, the entire scene must be updated to account for the movement of the selected objects and their effects on the scene. The computational demand may exceed the ability of many PCs.

[0009] It is therefore desirable to provide a system that will minimize the computational requirements for rendering a scene in which one or more selected objects are being manipulated within the scene.

[0010] One embodiment of the invention includes an interactive rendering system which can minimize computational demand while allowing a designer to manipulate one or more selected objects in a scene. One aspect of the present invention is a system which continuously renders the selected objects while the background scene is not continuously rendered. Because there is no need to render the background scene, most of the computational power can be dedicated to the selected objects. In order to give a designer as realistic a view as possible, the perspective and depth relationship between the selected objects and the scene are maintained. It is found that many designers are satisfied with this arrangement.

[0011] The present invention is a system for rendering one or more selected three-dimensional objects of a scene containing a plurality of three-dimensional objects. In one embodiment of the present invention, each object is associated with a modifier stack containing digital information describing the appearance of the object. The selected object(s) can be separated from the rest of the objects in the scene by using a flag. The system comprises a rendering engine for generating two-dimensional pixel data for the modifier stacks of objects. The pixel data includes z values corresponding to a distance between the objects and a predetermined point in space. A first video buffer is coupled to the rendering engine for receiving two dimensional pixel data generated by the rendering engine operating on objects in the scene that are not selected. A second video buffer is coupled to the rendering engine for receiving two dimensional pixel data generated by the rendering engine operating on selected objects. The system then compares the z values of pixels in the first and second video buffers and selects the z value which is closest to the predetermined point. Either the data in the scene video buffer or object video buffer will be displayed depending on whether a selected z value comes from the scene video buffer or object video buffer.

[0012] To further explain the present invention, it should be noted that rendering involves transforming three dimensional representation of objects in a scene on a two dimensional screen. Each pixel on the screen represents a point in three-dimensional space which has a depth or “z” dimension representing the distance of that point from an observer. When two points in three dimensional space are mapped to the same pixel by the system, the point with the smaller z value is displayed while the point with the larger z value is obscured and therefore not drawn on the screen. The system of this invention maintains a buffer containing, among other information, the z values of every pixel in the scene. The information is used to correctly display selected objects in the scene in relation to the background and other objects in the scene without rendering the entire scene when one of the objects in the scene is being manipulated by the designer.

[0013] When a designer begins manipulating one or more selected objects in the scene, the selected objects are flagged and re-rendered frequently while it is being manipulated by the designer. The z values of the selected objects are stored in a separate buffer. The remainder of the scene (with the select objects removed) is rendered once, and is not changed while the objects are being manipulated and therefore the computation requirements for re-rendering are limited to that which is required to correctly render the selected objects and manipulated by the designer and to correctly display the manipulated object in relation to the background and other objects.

[0014] While the object is manipulated within the scene, the z values for the pixels of the manipulated object are compared with the z values of the pixels in the scene and each pixel in the manipulated object or objects is displayed either in front of or behind the scene by comparing the z values of the objects' pixels to those contained in the buffer for the remainder of the scene. The use of the z values eliminates the need for re-rendering any portion of the scene which is not changed by the manipulation of the selected object by the designer and therefore significantly reduces the computational complexity of displaying the scene in rendered form while the designer is manipulating an object within the scene.

[0015] When the manipulation of the selected objects is completed and the designer releases the objects, typically by releasing the mouse button, the system integrates the manipulated objects back into the existing background scene without the necessity of re-rendering the entire scene by using the values stored in the z buffer reserved for the selected objects.

[0016] It should be noted that the input to the rendering engine does not have to be the modifier stack of an object. The present invention is applicable to other ways to represent three-dimensional objects in a scene. Further, it is not essential to use flags to separate selected objects from the scene, as long as the rendering engine can distinguish the status of the objects so that the selected object(s) and the objects of the scene can be separately rendered and delivered to the two video buffers.

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

[0018] FIG. 1 is a block diagram of a workstation that can be used to implement an interactive rendering system of the present invention.

[0019] FIG. 2 is a block diagram showing the details of the interactive rendering system of the present invention.

[0020] FIG. 3 is a flow chart showing the operation of the interactive rendering system shown in FIG. 2.

[0021] The present invention involves a novel interactive rendering system and related methods. The following description is presented to enable any person skilled in the art to make and use the invention. Description of specific applications is provided only as examples. Various modifications to the preferred embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.

[0022] FIG. 1 illustrates a workstation 100 that can be used to implement the present invention. It comprises a central processing unit (CPU) 102, a random access memory (RAM) 104, a read-only-memory (ROM) 106, and a video controller 108. These components can communicate with each other via a bus 110. Workstation 100 also contains a display unit 114. Workstation 100 can be used to execute software which renders three-dimensional representation of a scene on a two dimensional screen on display unit 114. In the present application, the process of calculating the correct two dimensional screen representation of the a three-dimensional scene is called “rendering”. The scene may be updated continuously to permit a user to observe the effects of any changes introduced into the scenes by the user.

[0023] The screen of display unit 114 is composed of two dimensional picture elements or “pixels”. Even though the pixels are addressed in the two dimensional space of the screen, they each represent a point in three-dimensional space which has a depth or “z” dimension representing the distance of that point from an observer (which could be the designer using the workstation). When two points in three dimensional space are mapped to the same pixel by the rendering system, the point with the smaller z value is displayed while the point with the larger z value is obscured and therefore not drawn on the screen.

[0024] An example of rendering is now described. In this example, two objects, e.g., a car and a person, are initially located close to each other and at about the same distance from the observer. When this scene is initially rendered, the z values of the car and the person are about the same. Because the car and the person are separated from (although close to) each other, all the pixels representing the car and the person can be seen by the observer. If the person is moved towards the observer, it will appear to be bigger than the car as a result of change in perspective. Part of the car should be blocked by the person in a proper perspective view. When the car and the person are rendered, the overlapping portion will be mapped into the same pixels. When the scene is displayed by display unit 114, part of the car will be obscured by the person because the z values of the pixels corresponding to the person are smaller than the z values of the pixels corresponding to the car.

[0025] It is found that many workstations do not have enough computational power to continuously render a scene when one or more objects are manipulated. One aspect of the present invention is to continuously render selected objects while the background scene is not continuously rendered. Because there is no need to render the background scene, most of the computational power can be dedicated to rendering and manipulating the selected objects. In order to give a designer as realistic a view as possible, the z values of the selected objects are compared to the z values of the background scene so that the depth relationship can be maintained.

[0026] FIG. 2 is a block diagram of an interactive rendering system 150 of the present invention. System 150 comprises a memory area 160 for storing information about the three-dimensional appearance of all the objects in a scene. Relevant information may include a modifier stack structure disclosed in an appendix of the present application. Memory area 160 is preferably located in RAM 104 of workstation 100. However, memory area 160 could also be a portion of a hard disk, although the performance of the system may be degraded because of slow data retrieval.

[0027] System 150 also comprises a rendering engine 162 that performs rendering operation. Rendering engine 162 is preferably a software module loaded in RAM 104 or stored in ROM 106. As explained before, a rendering operation involves calculating the correct two dimensional screen representation of three-dimensional objects. Rendering engine 162 obtains information on the objects of the scene from memory area 160. After rendering, the two dimensional representation of the scene is stored in a scene video buffer 164. In one embodiment of the present invention, the two-dimensional information includes the z value and the pixel color value (typically in the form of B (blue) R (red) and G (green) for each pixel). Scene video buffer 162 may be located in RAM 104 or in a graphic card commonly used to speed up graphic display of a workstation.

[0028] The pixels are displayed on a display unit 182, which typically accepts sequential input signals having a predetermined frequency and bandwidth (or data rate). These input signals conform to a predefined video format (e.g., VGA, SVGA, etc.). As a result, a video controller 180 is used to convert the two dimensional digital data in scene video buffer 164 to appropriate video signals. Video controller 180 and display unit 182 are substantially the same as video controller 108 and display unit 114 of FIG. 1. Both video controller 180 and scene video buffer 162 may be located in the above mentioned graphic card.

[0029] In the present system, the designer can designate one or a group of objects in the above described scene for manipulation. System 150 comprises a user interface 152 which allows the assigner to select the objects of interest. User interface 152 is preferably a software module loaded in RAM 104 or stored in ROM 106. The selection can be entered by using a mouse (not shown) and/or a keyboard (not shown). As an example, the user can select an object or a group of objects for manipulation by holding down a predetermined button of the mouse and/or key of the keyboard. The selection is transmitted to an interactive rendering controller 154.

[0030] Upon receiving the identity of the selected object(s) from user interface 152, controller 154 flags those objects that are selected (e.g., using a conventional flag typically used in software design). The designer can manipulate (e.g., move, bend, or otherwise modify) the selected object(s). In one embodiment of the present invention, the objects which are not selected cannot be modified. As a result, there is no need to continuously render the scene. The scene with the selected objects removed will be rendered once, and the resulting two-dimensional data is stored in scene video buffer 164 for future uses.

[0031] In the present invention, rendering engine 162 continuously renders the object(s) that are selected. The resulting two-dimensional data is stored in an object video buffer 166. Object video buffer 166 could be a part of RAM 104 or a part of the above mentioned graphic card. As the selected object(s) is being manipulated, the modified object(s) is rendered by rendering engine 162 and the result stored in object video buffer 166. In one embodiment of the present invention, the size and structure of scene video buffer 164 and object video buffer 166 are the same.

[0032] System 150 also contains a compositor 170 which merges data in scene video buffer 164 and object video buffer 166. Specifically, the z values of the pixels in object video buffer 166 are compared with the z values of the corresponding pixels in scene video buffer 164. Each pixel in the selected object(s) is displayed either in front of, or behind, or intersecting the pixel in the scene by comparing the z value of the pixel in object video buffer 166 to the pixel in scene video buffer 164. The use of the z buffer eliminates the need for re-rendering of the scene. This leads to significant reduction of the computational complexity of displaying the scene in rendered form while the designer is manipulating an object within the scene.

[0033] In one embodiment of the present invention, the modifier stack of each object contains a description of a bounding box that encloses the object. In this case, compositor 170 only needs to compare the z values of pixels within the bounding box of the selected object. In some graphic design situations, the size of the selected object(s) is a small fraction of the whole scene. As a result, only a small number of pixels needs to be evaluated by compositor 170.

[0034] The merged data is then sent to video controller 180 for converting to video signals suitable for use by display unit 182.

[0035] It is possible that the selected object(s) has some pre-defined relationship with some of the objects in the scene. For example, the selected object(s) and another object in the scene may be linked together by the same “bend” modifier (i.e., the bending action of one object affects the other object). There are different ways to handle this situation. One way is to prohibit the selected object(s) from using this modifier. Another way is to change just that object in the scene. The exact way to handle this situation is a software design choice, and should not affect the scope of the present invention.

[0036] The operation of interactive rendering system 150 of FIG. 2 is shown in a flow chart 200 in FIG. 3. In step 202, system 150 is initialized, e.g., bringing up a file containing a scene the designer wishes to render. Appropriate information about the objects (e.g., their modifier stacks) is used by rendering engine 162 to render the complete scene (step 204). The scene is displayed by display unit 182.

[0037] System 150 then determines whether any object is selected (step 210). In one embodiment, selection is indicated by the designer holding down a mouse button when a cursor is located within the boundary of a desired object. If no object is selected, system 150 continues to render the scene (i.e., flow chart 200 branches back to step 204). If an object is selected, interactive rendering controller 154 flags the selected objects (step 212). The scene (with the selected object removed) is then rendered. The result is stored in scene video buffer 164. The selected object is also re-rendered and the result is stored in object video buffer 166 (step 214).

[0038] In step 218 system 150 determines whether the view of the selected object has been changed (e.g., moved or modified). If the view is not changed, step 218 returns to itself If the view is changed, the selected object is rendered. The result is stored in object video buffer 166 (step 220). Compositor 170 then merges the data in object video buffer 166 and scene video buffer 164 (step 222). As pointed out above, the merging involves, in part, comparing the z values of the rendered object with the corresponding pixels of the scene. The merged data is then sent to video controller 180 for conversion to appropriate video signals.

[0039] In step 226, system 150 determines if the object of interest is deselected. In one embodiment of the present invention, deselection is indicated by releasing the mouse button. If the object is deselected, the flag associated with the selected object is removed (step 230). Flow chart 200 then branches to step 204 (i.e., rendering the whole scene continuously). If the object is not deselected, flow chart 200 branches to step 218 to determine if the view of the object has been changed.

[0040] It is possible to use the technique disclosed in an appendix of the application entitled “User Selectable Adaptive Degradation for Interactive Computer Rendering System” to render the selected object(s). Stated briefly, the quality of rendering the selected object(s) could be lowered when a desired frame rate cannot be maintained.

[0041] 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.