This invention relates to computer graphics and, more specifically to a parametric geometric element definition and generation system.
Many applications such as on-line advertisements or promotional graphics require rich image data. As well, better computer graphics capabilities are required by interactive Internet based 3D programming and gaming as well as by real time Internet based simulations. These advanced capabilities are required by advertising agencies, people who create content for the Internet, game developers and entertainment companies. Existing systems are limited because of the large file size associated with graphic, images or image manipulation, the long time required to download content, the lack of rich animatable geometries, the long amount of time required to download level of detail (LOD) data, and the extensive memory and processing time required to generate adaptive level of detail information.
In a computer graphics system, graphic images may be created and/or manipulated by the computer. A graphic image may be displayed on a video display or output to a printer, for example. A graphic image is comprised of a plurality of geometric shapes, or polygons, and textures. As the level of detail increases, the number of polygons and/or textures in the graphic image and, consequently, the size of the image increases. The size of the graphic image affects the time that it takes for the image""s display to be updated on the screen as well as the length of time it takes to send the image from one computer to another. It is desirable to be able to minimize the time needed to transmit an image and/or update its display.
A display screen is comprised of a number of horizontal lines (referred to as scan lines) each of which is comprised of a number of dots (or pixels). To update an image on the screen, the area of the screen that contains the image is redisplayed by refreshing each pixel. This is typically performed by starting at the top left corner of the display and ending with the bottom right corner of the display. A complete scan of the display area is referred to as a frame. The number of frames that are displayed per second is referred to as the frame rate. The higher frame rate is typically desirable.
The frame rate is especially important where the graphic image is changed slightly and redisplayed to give the appearance of movement or animation. A low frame rate causes the animation to appear jerky. By lowering the level of detail (e.g., the number of polygons that must be drawn), the frame rate may be increased. However, a lower level of detail may cause the image to appear blocky and unrealistic.
Using existing approaches, each version of the image and/or different levels of detail of each version are created as different images (i.e., different xe2x80x9csnapshotsxe2x80x9d of the image). Before these images may be transmitted to another computer, a data representation of the images must be generated.
One mechanism for generating a data representation of an image is the Virtual Reality Modeling Language (VRML). VRML is a text-based definitional language comprising a statement syntax used to define a graphic image. A VRML file is created to define an image containing VRML statements that define nodes (e.g., sphere, cylinder, cone, cube, translation and transform) and fields (e.g., radius, height, width, and depth) that distinguish one node from another. The following is an example of VRML statements that define a red sphere:
Transform {
translation 301
children [
Shape {
geometry Sphere {radius 2.3}
appearance Appearance {material Material {
diffuseColor 100 #Red
}}
}
]
}
The VRML statements identify five nodes (i.e., xe2x80x9cTransformxe2x80x9d, xe2x80x9cShapexe2x80x9d, xe2x80x9cSpherexe2x80x9d, xe2x80x9cAppearancexe2x80x9d and xe2x80x9cMaterialxe2x80x9d) and fields associated with the nodes. The xe2x80x9cSpherexe2x80x9d node identifies a geometric shape (i.e., sphere) and the xe2x80x9cradiusxe2x80x9d field indicates that the sphere is to have a radius of 2.3. The xe2x80x9cAppearancexe2x80x9d and xe2x80x9cMaterialxe2x80x9d nodes affect the way the sphere is drawn. The material node with a xe2x80x9c1 0 0xe2x80x9d value for its xe2x80x9cdiffuseColorxe2x80x9d field indicates that the sphere is red. The xe2x80x9cShapexe2x80x9d node associates the xe2x80x9cAppearancexe2x80x9d node with the xe2x80x9cSpherexe2x80x9d node. The xe2x80x9cTranslationxe2x80x9d node defines a movement of the sphere to a new location as indicated by the xe2x80x9ctranslationxe2x80x9d field and its value of xe2x80x9c3 0 1xe2x80x9d. A VRML representation is read and the node and field information is used to generate an image.
A VRML representation of an image represents a static state, or snapshot, of the image. Changes to the level of detail within the image, for example, are done by generating a new VRML representation of the image. Where the sphere is to be displayed on another computer, each of these representations must be sent to the computer before they can be used to display the sphere on the other computer.
The VRML representations of the sphere may be sent via the Internet, for example. Most users connect to the Internet using a modem with a maximum transmission rate that is frequently not achieved due to the quality of the phone line(s) used to transmit the data. The transmission rates using a modem connection are not sufficient to provide continuous streams of image data for processing by a computer. It would be beneficial to be able to the processing capabilities available with existing computer systems and minimize the amount of image data that must be transmitted between computer systems.
U.S. Pat. No. 5,581,672 Dec. 3, 1996 Letcher, Jr. and U.S. Pat. No. 5,856,828, Jan. 5, 1999 Letchter, Jr. describe a system of relational entities for object-oriented computer-aided geometric design. In the patents, geometric objects are defined and constructed in a system which retains and utilizes relationsip and dependencies between objects in a directed graph data structure.
A parametric geometric element definition and generation system and method is described herein. Embodiments of the invention comprise a model having a plurality of modeling operations and parameters or properties used in defining and generating geometric elements. In one or more embodiments of the invention, the model is a directed acyclic graph of three-dimensional modeling operations that combine to store information about a process used to construct an image. In one or more embodiments of the invention an object player monitors a model, communicates initialization and modifications of geometric data to the rendering system, and provides geometric data to the rendering system in the appropriate data formats.
In one or more embodiments of the invention, the model and modeling operations are object-oriented objects having properties and methods. One embodiment of the invention comprises geometry, core, operation and player object classes.
Geometry object classes comprise the geometric data (e.g. coordinate, color, normal and texture coordinate data). The geometry object allows data to be shared by describing faces as lists of indices into the data pools. Core classes provide the fundamental communication and generation mechanism used by the model and comprise exceptions, change events, and operation superclasses. The operation classes comprise classes that may generate a geometric object or combine geometric objects to create new geometric objects. The object player provides an interface between the model and the underlying rendering system and may initiate a generation request. Geometric object data is returned to the object player in response to a generation request. This geometric object data is then forwarded to the underlying rendering system for rendering the image.
A notification mechanism is used where objects may send and/or listen for change events. A modification to one or more properties of the model and/or modeling operations may trigger the transmission of a change event. The change event indicates to interested parties (e.g., other modeling operations, the model and for the object player) that an update to their geometric output, or other action, may be needed. A tracking mechanism provides the ability to determine what properties have been changed and assists in determining a response to a generate request. Each modeling operation has the ability to respond to a generate request. In an embodiment of the invention, the generation process is a depth-first traversal of the model graph structure. Generation may be limited to those operations of the model whose properties have been modified, and those operations that depend on the modified operation whose properties have been modified.
Different xe2x80x9csnapshotsxe2x80x9d of an image may be generated at runtime by modifying one or more parameters of operations within a model of the image and then asking the graph to generate. Each snapshot may provide a different level of detail or animation, for example. In one embodiment of the invention, a predictive mechanism is used to determine an optimal level of detail.
In one or more embodiments of the invention, a prediction scheme is used to determine the effect on rendering time of image changes. Rendering times are collected and any differences in rendering times between rendering passes are allocated to the changed geometric objects. It is therefore possible to collect statistics on the effect on rendering time of making various changes to the image. It is possible, for example, to predict the rendering times for different levels of detail associated with a geometric object. Predictions may be used in selecting the appropriate level of detail to achieve a desired frame rate.
In accordance with a further aspect, the invention is directed to a method of computer aided 3D modelling of geometric objects undergoing changes wherein a directed acyclic graph is executed to generate a 3D model, the directed acyclic graph including a plurality of nodes which are connected with other nodes with directed edges between two nodes, each node representing a modelling operation of the geometric objects and each directed edge indicating the direction of flow of data from one node to another. The method comprises steps of a first node sending a change event indication specifying changes to bound properties of the node to a series of nodes in succession along associated directed edges and each node in succession determining if the change event indication received from a preceding node affects its bound properties and further determining based on its own rules that its own change event indication should be sent to a succeeding node. The method includes further steps of sending the change event indication to the succeeding node, and last node in succession instructing a rendering system to render a 3D model in accordance with the received change event indication.
In accordance with a yet another aspect, the invention is directed to a method of computer aided 3D modelling of geometric objects undergoing changes wherein a directed acyclic graph is executed to instruct a rendering system to generate a 3D model, the directed acyclic graph including a plurality of nodes which are connected with other nodes with directed edges between two nodes, each node representing a modelling operation of the geometric objects and each directed edge indicating the direction of flow of data from one node to another. The method comprises steps of (a) executing continually the directed acyclic graph to instruct the rendering system to generate a series of frames of a 3D model of geometric objects which are undergoing changes and (b) measuring a time required for the rendering system to generate a predetermined numbers of preceding frames with respect to a target time. The method further includes steps of (c) modifying bound properties of one or more nodes and (d) repeating iteratively steps (b) and (c) so that the time required for the rendering system to generate the most recent frame approach the target time.
According to another aspect, the invention is directed to a computer aided 3D modelling apparatus for modelling 3D models of geometric objects undergoing change which comprises an instruction storage module containing a directed acyclic graph to be executed to generate a 3D model, the directed acyclic graph including a plurality of nodes which are connected with other nodes with directed edges between two nodes, each node representing a modelling operation of the geometric objects and each directed edge indicating the direction of flow of data from one node to another. The apparatus further includes an input port for inputting changes in bound properties, defined below, of one or more nodes, an instruction execution module for executing the directed acyclic graph to generate an output, an object player module for monitoring the output and regenerating the directed acyclic graph in response to the output if needed, and the rendering system for rendering the 3D model of geometric objects in response to the instructions.