Dynamic 2D imposters of 3D graphic objects

• US 20050110789A1
• Filed: 11/20/2003
• Published: 05/26/2005
• Est. Priority Date: 11/20/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Le Ouay, Franck
• Granted Patent: US 7,019,742 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: A63F 13/10 Control of the course of the game, e.g. start, progess, end
• CPC Class Codes: A63F 13/45 Controlling the progress of the video game
• CPC Class Codes: A63F 13/52 involving aspects of the displayed game scene
• CPC Class Codes: A63F 2300/6615 using models with different levels of detail [LOD]
• CPC Class Codes: A63F 2300/6623 for animating a group of characters
• CPC Class Codes: G06T 15/205 Image-based rendering

Abstract

2D imposters representing 3D graphical objects, such as virtual spectators in a simulated sports arena, are dynamically displayed at predefined locations relative to an arbitrarily movable camera position in a virtual space. A hierarchical data structure is created with branches corresponding to iteratively subdivided groups of imposter data structures and is used to store polygon vertices, texture data, and other 2D imposter data generated during run-time. Center locations of the hierarchically divided groupings are used to determine a common projection location within a current view volume at which each 2D imposter is projected as an oriented image from each corresponding animated 3D graphical object. Sets of contiguous 2D imposter data are determined based on currently visible groupings of predefined locations that do not require rendering as 3D graphical objects due to their distance from the camera position. Each set of contiguous 2D imposters is rendered with a single draw primitive.

Claims

1. A method for dynamically displaying two-dimensional (2D) imposters representing three-dimensional (3D) graphical objects, relative to an arbitrarily movable camera position, wherein each 2D imposter comprises a projection of one of the 3D graphical objects, comprising the steps of:

(a) predefining locations within a virtual space, wherein each location defines a position at which one of;

(i) a 3D graphical object will be displayed; and

(ii) a 2D imposter will be displayed;

(b) predefining a hierarchical data structure comprising hierarchical groups of imposter data structures to be used in defining the 2D imposters, wherein each imposter data structure is associated with one of the predefined locations within the virtual space, and wherein the hierarchical groups are arranged in a contiguous quad order;

(c) determining a current camera view volume within the virtual space;

(d) determining a common projection location within the current camera view volume as a function of a central location of the predefined locations associated with each hierarchical group of imposter data structures;

(e) generating each of the 2D imposters as a projection of each 3D graphical object positioned at the common projection location within the current camera view volume;

(f) determining 2D imposter locations within the current camera view volume at which 2D imposters will be displayed, the 2D imposter locations being determined as a function of a modulated distance from a current camera position;

(g) forming contiguous sets of imposter data structures associated with predefined locations that are not interrupted by one of;

(i) locations at which 3D graphical objects will be rendered; and

(ii) locations that are outside the view volume; and

(h) invoking a single draw primitive for each contiguous set of imposter data structures to render 2D imposters for each contiguous set of imposter data structures, thereby displaying 2D imposters at the predefined locations.

2. The method of claim 1, wherein the 3D graphical objects comprise virtual spectators in a virtual arena.

3. The method of claim 1, wherein the step of predefining the hierarchical data structure comprises the steps of:

(a) iteratively dividing the predefined locations into a plurality of levels of groups, wherein the groups at each level comprise substantially equal numbers of predefined locations; and

(b) arranging plurality of levels of groups in a contiguous quad order.

4. The method of claim 1 wherein an individual imposter data structure comprises:

(a) one of the predefined locations within the virtual space;

(b) a plurality of vertex data elements, wherein each vertex data element is assigned a unique vertex identifier; and

(c) a texture identifier specifying a texture associated with the individual imposter data structure.

5. The method of claim 1, wherein the step of determining a common projection location comprises the steps of:

(a) determining a plurality of group centers, each group center comprising a center location of each hierarchical group that is within a predefined distance of a current camera location;

(b) determining a plurality of modulation functions, each modulation function corresponding to each group center as a function of at least;

(i) the distance between a group center and a centroid of the camera view volume; and

(ii) whether a group center is within the camera view volume; and

(c) computing a weighted average of the group centers as a function of a sum of the group centers and a sum of the modulation functions.

6. The method of claim 1, wherein the step of generating each of the 2D imposters comprises the steps of:

(a) determining a current animation step associated with each of the 3D graphical objects;

(b) generating a posed 3D graphical object for each of the 3D graphical objects as a function of the current animation step associated with each of the 3D graphical objects; and

(c) generating a projected image of each posed 3D graphical object positioned at the common projection location.

7. The method of claim 6, further comprising the step of defining a rectangle size for the projected image as a function of a proximity of the current camera position to the predefined locations.

8. The method of claim 1, wherein the step of determining 2D imposter locations comprises the steps of:

(a) determining the modulated distance from the current camera position as a function of a predefined radius and at least a current zoom factor; and

(b) selecting predefined locations that are within the modulated distance from the current camera position and are within the camera view volume.

9. The method of claim 1, wherein the step of forming contiguous sets of imposter data structures comprises the steps of:

(a) determining visible hierarchical groups from the hierarchical groups of imposter data structures that include at least one predefined location within the camera view volume;

(b) determining any 3D hierarchical group from the visible hierarchical groups that include at least one predefined location within a predefined 3D threshold distance from the current camera position, thereby determining the visible hierarchical groups that will be rendered with 3D graphical objects rather than 2D imposters; and

(c) selecting the visible hierarchical groups that include adjacent imposter data structures not interrupted by a 3D hierarchical group.

10. The method of claim 1, wherein prior to the step of invoking a single draw primitive, further comprising the steps of:

(a) sorting the contiguous sets of imposter data structures into an order, from a contiguous set that is closest to the current camera position, to a contiguous set that is farthest from the current camera position; and

(b) rendering 3D graphical objects at predefined locations that are within the camera view volume and are associated with hierarchical groups that are within a predefined distance from the current camera position.

11. A memory medium on which are stored machine instructions for carrying out the steps of claim 1.

12. A system for dynamically displaying two-dimensional (2D) imposters of three-dimensional (3D) graphical objects relative to an arbitrarily movable camera position, wherein each 2D imposter comprises a projection of one of the 3D graphical objects, comprising:

(a) a processor;

(b) a display in communication with the processor; and

(c) a memory in communication with the processor, the memory storing machine instructions that cause the processor to carry out a plurality of functions, including;

(i) predefining locations within a virtual space, wherein each location defines a position at which one of;

(1) a 3D graphical object will be displayed; and

(2) a 2D imposter will be displayed;

(ii) predefining a hierarchical data structure comprising hierarchical groups of imposter data structures to be used in defining the 2D imposters, wherein each one imposter data structure is associated with one of the predefined locations within the virtual space, and wherein the hierarchical groups are arranged in a contiguous quad order;

(iii) determining a current camera view volume within the virtual space;

(iv) determining a common projection location within the current camera view volume as a function of a central location of the predefined locations associated with each hierarchical group of imposter data structures;

(v) generating each of the 2D imposters as a projection of each 3D graphical object positioned at the common projection location within the current camera view volume;

(vi) determining 2D imposter locations within the current camera view volume at which 2D imposters will be displayed, the 2D imposter locations determined as a function of a modulated distance from a current camera position;

(vii) forming contiguous sets of imposter data structures associated with predefined locations that are not interrupted by one of;

(1) locations at which 3D graphical objects will be rendered; and

(2) locations that are outside the view volume; and

(viii) invoking a single draw primitive for each contiguous set of imposter data structures to render 2D imposters for each contiguous set of imposter data structures, thereby displaying 2D imposters at the predefined locations that are not interrupted by locations at which 3D graphical objects will be rendered.

13. The system of claim 12, wherein the 3D graphical objects comprise virtual spectators in a virtual arena.

14. The system of claim 12, wherein the machine instructions further cause the processor to carry out the functions of:

(a) iteratively dividing the predefined locations into a plurality of levels of groups, wherein the groups at each level comprise substantially equal numbers of predefined locations; and

(b) arranging plurality of levels of groups in a contiguous quad order.

15. The system of claim 12, wherein an individual imposter data structure comprises:

(a) one of the predefined locations within the virtual space;

(b) a plurality of vertex data elements, wherein each vertex data element is assigned a unique vertex identifier; and

(c) a texture identifier specifying a texture associated with the individual imposter data structure.

16. The system of claim 12, wherein the machine instructions further cause the processor to carry out the functions of:

(a) determining a plurality of group centers, each group center comprising a center location of each hierarchical group that is within a predefined distance of a current camera location;

(b) determining a plurality of modulation functions, each modulation function corresponding to each group center as a function of at least;

(i) the distance between a group center and a centroid of the camera view volume; and

(ii) whether a group center is within the camera view volume; and

(c) computing a weighted average of the group centers as a function of a sum of the group centers and a sum of the modulation functions.

17. The system of claim 12, wherein the machine instructions further cause the processor to carry out the functions of:

(a) determining a current animation step associated with each of the 3D graphical objects;

(b) generating a posed 3D graphical object for each of the 3D graphical objects as a function of the current animation step associated with each of the 3D graphical objects; and

(c) generating a projected image of each posed 3D graphical object positioned at the common projection location.

18. The system of claim 12, wherein the machine instructions further cause the processor to carry out the functions of:

(a) determining the modulated distance from the current camera position as a function of a predefined radius and at least a current zoom factor; and

(b) selecting predefined locations that are within the modulated distance from the current camera position and are within the camera view volume.

19. The system of claim 12, wherein the machine instructions further cause the processor to carry out the functions of:

(a) determining visible hierarchical groups from the hierarchical groups of imposter data structures that include at least one predefined location within the camera view volume;

(b) determining any 3D hierarchical group from the visible hierarchical groups that include at least one predefined location within a predefined 3D threshold distance from the current camera position, thereby determining the visible hierarchical groups that will be rendered with 3D graphical objects rather than 2D imposters; and

(c) selecting the visible hierarchical groups that include adjacent imposter data structures not interrupted by a 3D hierarchical group.

20. The system of claim 12, wherein the machine instructions further cause the processor to carry out the functions of:

(a) sorting the contiguous sets of imposter data structures into an order, from a contiguous set that is closest to the current camera position, to a contiguous set that is farthest from the current camera position; and

(b) rendering 3D graphical objects at predefined locations that are within the camera view volume and are associated with hierarchical groups that are within a predefined distance from the current camera position.