Method and system for generating images using Gsprites

• US 5,867,166 A
• Filed: 06/27/1996
• Issued: 02/02/1999
• Est. Priority Date: 08/04/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Schick, Russell, Myhrvold, Nathan P., Kajiya, James T., Lengyel, Jerome E.
• Primary Examiner(s): BUCHEL JR, RUDOLPH JOHN
• Application Number:
  US08/671,412
• Time in Patent Office: 950 Days
• Field of Search: 345/418-20, 345/433-7, 345/501-5, 345/473-75, 345/960
• US Class Current: 345/419
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 13/80 2D [Two Dimensional] animation, e.g. using sprites
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 15/60 Shadow generation

Abstract

In an image processing system, a method for generating a images includes rendering graphical models comprising a scene to separate image layers called "gsprites," and then compositing these image layers to generate an image. An image processor can retrieve gsprites from memory, transform them, and composite them for display at video rates. Gsprites can be re-rendered or updated at different rates. Reducing the rendering overhead of the system, the image processor can perform an affine transformation on the gsprite to approximate motion of the graphical object that it represents, rather than re-render the object. Objects in a scene can be queued for re-rendering based on a predefined update rate, or based on the accuracy of representing the object with a transformed gsprite, rendered for a previously displayed image.

Claims

1. In a system for generating images in a view space at a computational rate, a method of generating images comprising:

assigning objects in a view volume for a current image to at least two gsprites;

independently rendering the objects to the at least two gsprites;

storing the at least two gsprites;

deriving a 2D geometric transform from characteristic points of a 3D object to simulate geometric motion of the 3D object over time;

applying the 2D geometric transform to a gsprite representing a rendering of the 3D object to simulate the geometric motion of the 3D object;

compositing the at least two gsprites, including the transformed gsprite, to generate the current image at the computational rate; and

repeating the above steps to generate subsequent images for subsequent computational periods.

2. The method of claim 1 wherein the objects are 3-D objects.

3. The method of claim 1 wherein the at least two gsprites are m by n image regions occupying a portion of the view space, where m and n are integers.

4. The method of claim 1 wherein the independently rendering step comprises rendering the at least two gsprites in series including:

rendering a first group of geometric primitives assigned to a first gsprite, and then after rendering the first group, rendering a second group of geometric primitives assigned to a second gsprite.

5. The method of claim 1 wherein the rendering step comprises rendering the at least two gsprites in parallel.

6. The method of claim 1 further including:

transferring the current image to a physical output device for display at a video refresh rate.

7. The method of claim 6 wherein the computational rate is substantially similar to the video refresh rate.

8. The method of claim 1 further including:

rendering a first 3-D object to a first gsprite;

computing an affine transform to simulate the motion of the first 3-D object; and

performing an affine transformation on the first gsprite using the affine transform.

9. The method of claim 1 further including:

computing an affine transform matrix using characteristic points of a first object rendered to a first gsprite;

determining whether an affine transformation of the first gsprite using the affine transformation matrix is within a predefined error tolerance;

if the affine transformation is within the predefined error tolerance, then performing an affine transformation on the first gsprite to simulate motion of the first object.

10. A method according to claim 1 including the steps of:

comparing characteristic points for a first object in a first computational period with characteristic points for the object in a second computational period; and

re-rendering the first object when changes in the characteristic points are not within a predefined tolerance.

11. A method according to claim 1 in which the rendering step comprises the step of updating gsprites rendered in previous computational periods at varying rates.

12. A method according to claim 1 further including the step of computing a priority list for re-rendering objects in subsequent computational periods.

13. The method of claim 12 wherein priority for re-rendering the objects is computed at least in part by determining accuracy in approximating motion of a first object with an affine transformation of a first gsprite representing the first object.

14. The method of claim 12 wherein the priority for re-rendering is computed at least in part by using a predefined update rate for one or more of the objects.

15. The method of claim 12 wherein the priority of re-rendering is computed by:

computing an affine transform matrix to approximate motion of a first object;

performing the affine transformation on characteristic points of the first object for a previous image to find transformed characteristic points;

the comparing the transformed characteristic points with characteristic points for the current image to find an error value;

comparing the error value with a predefined tolerance to find an accuracy value; and

prioritizing objects for rendering based on the accuracy value.

16. The method of claim 1 including the step of:

selectively rendering objects to gsprites at various resolutions, a low resolution gsprite being expanded to cover a portion of the view space allocated for the display of the low resolution gsprite.

17. The method of claim 1 including the step of compositing gsprites of varying resolutions in a common graphics pipeline.

18. The method of claim 1 in which inputs for a subsequent image are used to compute an affine transform for a gsprite in the current image.

19. The method claim 1 comprising the steps of:

receiving inputs for a first image during a first view space period;

computing an affine transform during a next or second view space period, and transforming gsprites during a succeeding or third view space period;

wherein inputs for a subsequent image are received during the second view space period, such inputs for the subsequent image being used in the second period for computing the affine transform for the first image.

20. The method of claim 1 comprising the steps of:

assigning an object temporally spaced from the view volume for the current image to a first gsprite of the at least two gsprites;

independently rendering the object temporally spaced from the view volume to the first gsprite;

storing the first gsprite; and

compositing the first gsprite with other gsprites to generate one of the subsequent images.

21. In a graphics rendering system for generating a series of images for a view space displayed at a refresh rate, a method for generating a current image for a view space, the method comprising:

storing gsprites displayed in one or more previous images of the series of images;

determining whether to update one or more of tie stored gsprites for the current image;

updating at least a first gsprite of the stored gsprites by rendering a first object to the first gsprite based on inputs to the graphics rendering system describing the location of the first object in a scene represented in the current image;

deriving a 2D geometric transform from characteristic points of a 3D object to simulate geometric motion of the 3D object over time,

applying the 2D geometric transform to a gsprite representing a rendering of the 3D object to simulate the geometric motion of the 3D object; and

compositing the first gsprite with at least a sub-set of the stored gsprites and at least a portion of the transformed gsprite for display as the current image.

22. The method of claim 21 further including:

updating the first gsprite based on a predefined update rate.

23. The method of claim 21 further including the steps of:

deriving an affine transform from characteristic points representing a second object at a first time corresponding to the current image and a second time corresponding to a previous image of the series of images;

performing an affine transformation on a second gsprite of the gsprites representing the second object using the affine transform; and

compositing the second gsprite with at least a sub-set of the stored gsprites for display as the current image.

24. The method of claim 21 further including:

simulating change in position of a second object between the current and a previous image by performing an affine transformation on one of the stored gsprites representing the second object.

25. The method of claim 21 further including:

deriving an affine transform from characteristic points representing a second object at a first time corresponding to the current image and a second time corresponding to a previous image of the series of images; and

performing an affine transformation on the characteristic points representing the second object at the second time using the affine transform to find transformed characteristic points;

comparing the characteristic points representing the second object at the first time with the transformed characteristic points; and

determining whether to update one of the stored gsprites representing the second object based on the comparing step.

26. The method of claim 25 wherein the comparing step includes comparing the characteristic points representing the second object at the first time with the transformed characteristic points to compute an error value;

repeating the deriving, performing, and comparing steps for other objects and corresponding gsprites of the stored gsprites; and

prioritizing the objects for re-rendering based on the error values computed in the comparing steps.

27. The method of claim 21 further including the steps of:

receiving inputs to the graphics rendering system describing a position of a second object for a subsequent image to the current image;

using the inputs to compute an affine transform; and

performing an affine transformation on a second gsprite of the stored gsprites representing the second object; and

compositing the second gsprite with at least a sub-set of the stored gsprites for display as the current image.

28. An image processing system for generating a display image using gsprites, the system comprising:

gsprite memory;

an image pre-processor receiving input describing location of objects and a viewpoint, for determining which of the objects intersect with a view volume, for assigning objects intersecting with the view volume to gsprites, and for computing affine transforms used to transform the gsprites by deriving an affine transform from a change in position of characteristic points of a 3D object to simulate geometric motion of the 3D object over time; and

an image processor coupled to the image pre-processor for rendering the objects to respective gsprites, for storing the gsprites to the gsprite memory, for reading the gsprites from the gsprite memory and transforming the gsprites to physical output device coordinates according to the affine transforms, and for compositing the rendered gsprites for display on the physical output device.

29. The system of claim 28 wherein the image pre-processor comprises a programmed processor in a computer system.

30. The system of claim 28 wherein the image pre-processor comprises a programmed digital signal processor.

31. The system of claim 28 wherein the image pre-processor comprises a programmed processor in a computer system and a programmed digital signal processor coupled to the programmed processor.

32. The system of claim 28 wherein the image processor includes a tiler for rendering the objects to the gsprites and storing the gsprites in the gsprite memory.

33. The system of claim 28 wherein the image processor includes a gsprite engine for reading the gsprites from the gsprite memory and for transforming the gsprites to the physical output device coordinates.

34. The system of claim 33 wherein the image processor includes a compositing buffer coupled to the gsprite engine for compositing the gsprites for display on the physical output device.

37. The image processing system of claim 28 wherein the image preprocessor comprises a computer executing an operating system.

38. The image processing system of claim 37 wherein the image preprocessor comprises the computer executing the operating system and graphic support software.

35. A computer-readable medium on which is stored a computer program for processing gsprites, said computer program comprising instructions, which when executed by a computer, perform the steps of:

computing an affine transform from characteristic points for an object at first and second view space periods;

performing an affine transformation on the characteristic points for the object at the first view space period to find transformed characteristic points; and

comparing the transformed characteristic points with the characteristic points at the second view space period to determine accuracy of the affine transform.

36. In a graphics rendering system for rendering objects in a scene to generate frames of images at a frame refresh rate, a method of generating images comprising:

assigning the objects in a view volume for a current image to separate gsprites;

independently rendering the objects to the gsprites;

deriving an affine transform from characteristic points of at least one 3D object to simulate geometric motion of the 3D object over time;

storing the gsprites in memory;

retrieving the gsprites from memory according to a display list;

transforming the gsprites to physical output device coordinates, including applying the affine transform to a gsprite representing a rendering of the at least one 3D object;

compositing the gsprites to generate the current image at the frame refresh rate; and

repeating the above steps to generate subsequent images for subsequent frame periods.