System and method related to data structures in the context of a computer graphics system

#This invention relates generally to the art of computer graphics, and more specifically to the field of maintaining computer graphics data in a line tree data structure.

#One form of computer graphics is to develop a sequence of video image frames of an object scene from object scene information. The sources of object scene information include data stored in computer databases and data output by computer programs. The object scene information includes visual characteristics of an object scene, such as color and movement. Typically, one or more programs comprising a renderer process object scene information.

#More specifically, a video image frame includes a color value for each pixel of a display device. Pixels are the smallest resolution element of the display device. A color of a given pixel is determined by processing object scene information in the general area of the pixel.

#Additional objects and features of the invention will be more readily apparent from the following detailed description and appended claims when taken in conjunction with the drawings, in which:

#FIG. 1A is a block diagram of a computer system in accordance with an embodiment of the present invention.

#FIG. 1B illustrates the projection of an object onto an image plane in accordance with an embodiment of the present invention.

#FIG. 1A shows computer device 100. Computer device 100 is configured to execute the various embodiments of the present invention described below. Included in computer device 100 is central processing unit (CPU) 10, memory 20, and i/o devices 30. CPU 10 executes instructions as directed by operating system 24 and other programs maintained in memory 20 and sends control signals to various hardware components included in computer device 100.

#Memory 20 also includes object scene data 21. Object scene data 21 is static information that describes one or more object scenes. An object scene is one of many that, for example, comprise the scenes of computer animated video. For example, object scene data 21 may describe the actions and physical or visual attributes of characters (i.e., objects) in an object scene. In particular, object scene data 21 specifies locations of objects within an object scene through the use of x, y and z coordinates. The x and y coordinates represent the horizontal and vertical positions with respect to image plane 110 (of FIG. 1B). The z coordinate represents the distance of a point on an object from image plane 110. As illustrated in FIG. 1B, image plane 110 functions as a projection screen for object 120. Thus, image plane 110 facilitates a transformation of three-dimensional objects to a two-dimensional representation. Image plane 110 is analogous to a monitor or video display included in i/o devices 30. Positions on image plane 110 map to positions on a monitor or video display. Thus, references to pixels on image plane 110 are effectively references to pixels of a monitor or video display.

#Object scene data 21 also includes, as noted above, information about the movement of an object during a period of time associated with an image frame. Typically, the time period associated with an image frame is proportional to the shutter speed of a camera. In other words, the amount of time for which a camera exposes a frame of film. Any movement that occurs during this time period results in a blurred video frame or picture. To capture object movement, object scene data 21 provides the position of an object at the beginning of the period of time associated with the image frame and its trajectory and velocity during the time period. This permits the calculation of the position of an object at any point during the period of time associated with the image frame.