Bounding volume for 3D graphic primitives

• US 6,243,097 B1
• Filed: 12/10/1998
• Issued: 06/05/2001
• Est. Priority Date: 12/10/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Deffeyes, Suzanne Carol, Fossum, Gordon Clyde, Minor, Barry L., Brokenshire, Daniel Alan
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Santiago, Enrique L
• Application Number:
  US09/210,136
• Time in Patent Office: 908 Days
• Field of Search: 345/419, 345/420, 345/421, 345/427, 345/434, 345/437, 345/438
• US Class Current: 345/421
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

A method of and system for testing a graphic primitive for trivial acceptance or rejection. An initial bounding volume, such as a rectangular parallelepiped, is defined by the graphic primitive'"'"'s maximum and minimum x, y, and z coordinates in an initial coordinate system. A first bounding volume is then defined by the graphic primitive'"'"'s maximum and minimum x′, y′, and z′ coordinates in a first coordinate system, where the first coordinate system is transformed with respect to the initial coordinate system. Preferably this transformation comprises a 45° rotation about a common axis such as the z-axis. The initial bounding volume and the first bounding volume are then intersected to form a modified bounding volume. The vertices of the modified bounding volume are then available for use in determining whether the graphic primitive may be trivially rejected or accepted within a specified viewing volume. In one embodiment, the method further includes defining and using a second modified bounding volume by intersecting the initial bounding volume with a second bounding volume defined by the graphic primitive'"'"'s maximum and minimum x″, y″, and z″ values in a second coordinate system. The second coordinate system is determined by applying a second transformation, such as a 45° rotation about a common y-axis, with respect to the initial coordinate system. Still further, the invention may include defining and using a third modified bounding volume by intersecting the initial bounding volume with a third bounding volume defined by the graphic primitive'"'"'s maximum and minimum x′″, y′″, and z′″ values in a third coordinate system determined by applying a third transformation, such as a 45° rotation about a common x-axis with respect to the initial coordinates system.

Claims

1. A method of testing a graphic primitive for trivial acceptance or rejection, comprising:

defining an initial bounding volume by the graphic primitive'"'"'s maximum and minimum x, y, and z coordinates in an initial coordinate system;

defining a first bounding volume by the graphic primitive'"'"'s maximum and minimum x′

, y′

, and z′

coordinates in a first coordinate system, wherein the first coordinate system is determined by applying a first transformation to the initial coordinate system;

intersecting the initial bounding volume and the first bounding volume to form a modified bounding volume;

determining the graphic primitive'"'"'s relationship to a predetermined viewing volume by determining the modified bounding volume'"'"'s relationship to the viewing volume, wherein the graphic primitive is trivially accepted if the modified bounding volume is within the viewing volume and wherein the graphic primitive is trivially rejected if the modified bounding volume is exterior to the viewing volume; and

rendering the graphic primitive in a graphic display system if the primitive was trivially accepted.

2. The method of claim 1, wherein the initial and first bounding volumes comprise rectangular parallelepipeds.

3. The method of claim 1, wherein the step of defining the first bounding volume comprises:

applying the first transformation to the graphic primitive to produce a transformed graphic primitive;

defining a transformed bounding volume by maximum and minimum x, y, and z values of the transformed graphic primitive in the initial coordinate system, wherein the transformed bounding volume comprises a plurality of transformed vertices; and

applying an inverse of the first transformation to each of the plurality of transformed vertices.

4. The method of claim 1, wherein the initial coordinate system and the first coordinates system share a first common axis and further wherein the first transformation comprises a first rotation about the first common axis.

5. The method of claim 4, wherein an angle of the first rotation is 45°

.

6. The method of claim 1, further comprising:

defining a second modified bounding volume by intersecting the initial bounding volume with a second bounding volume defined by the graphic primitive'"'"'s maximum and minimum x″

, y″

, and z″

values in a second coordinate system determined by applying a second transformation to the initial coordinate system; and

trivially accepting the graphic primitive if the second modified bounding volume is within the viewing volume and trivially rejecting the graphic primitive if the second modified bounding volume is exterior to the viewing volume.

7. The method of claim 6, wherein the second coordinate system and the initial coordinate system share a second common axis and further wherein the second transformation comprises a second rotation about the second common axis.

8. The method of claim 6, further comprising

defining a third modified bounding volume by intersecting the initial bounding volume with a third bounding volume defined by the graphic primitive'"'"'s maximum and minimum x′

″

, y′

″

, and z′

″

values in a third coordinate system determined by applying a third transformation to the initial coordinates system; and

trivially accepting the graphic primitive if the third modified bounding volume is within the viewing volume and trivially rejecting the graphic primitive if the third modified bounding volume is exterior to the viewing volume.

9. The method of claim 8, wherein the third coordinate system and the initial coordinate system share a third common axis and further wherein the third transformation comprises a third rotation about the third common axis.

10. A computer readable storage medium configured with computer instructions for generating a bounding volume for a graphic primitive, comprising:

computer code means for defining an initial bounding volume by a graphic primitive'"'"'s maximum and minimum x, y, and z coordinates in an initial coordinate system;

computer code means for defining a first bounding volume by the graphic primitive'"'"'s maximum and minimum x′

, y′

, and z′

coordinates in a first coordinate system, wherein the first coordinate system is determined by applying a first transformation to the initial coordinate system;

computer code means for intersecting the initial bounding volume and the first bounding volume to form a modified bounding volume;

computer code means for storing the modified bounding volume in a storage medium of a graphics display system; and

computer code means for determining the graphic primitive'"'"'s relationship to a predetermined viewing volume by determining the modified bounding volume'"'"'s relationship to the viewing volume, wherein the graphic primitive is trivially accepted if the modified bounding volume is within the viewing volume and wherein the graphic primitive is trivially rejected if the modified bounding volume is exterior to the viewing volume.

11. The storage medium of claim 10, wherein the storage medium comprises a system memory of a graphics display system.

12. The storage medium of claim 10, wherein the code means for defining the first bounding volume comprises:

computer code means for applying the first transformation to the graphic primitive to produce a transformed graphic primitive;

computer code means for defining a transformed bounding volume by maximum and minimum x, y, and z values of the transformed graphic primitive in the initial coordinate system, wherein the transformed bounding volume comprises a plurality of transformed vertices; and

computer code means for applying an inverse of the first transformation to each of the plurality of transformed vertices.

13. The storage medium of claim 10, wherein the first coordinate system and the initial coordinate system share a first common axis and further wherein the first transformation comprises a first rotation of 45°

about the first common axis.

14. The storage medium of claim 10, further comprising:

computer code means for defining a second modified bounding volume by intersecting the initial bounding volume with a second bounding volume defined by the graphic primitive'"'"'s maximum and minimum, x″

, y″

, and z″

values in a second coordinate system determined by applying a second transformation to the initial coordinate system; and

computer code means for trivially accepting the graphic primitive if the second modified bounding volume is within the viewing volume and trivially rejecting the graphic primitive if the second modified bounding volume is exterior to the viewing volume.

15. The storage medium of claim 14, further comprising:

computer code means for defining a third bounding volume defined by the graphic primitive'"'"'s maximum and minimum, x′

″

, y′

″

, and z′

″

values in a third coordinate system determined by applying a third transformation to the initial coordinate system; and

computer code means for trivially accepting the graphic primitive if the third modified bounding volume is within the viewing volume and trivially rejecting the graphic primitive if the third modified bounding volume is exterior to the viewing volume.

16. The storage medium of claim 15, wherein the second coordinate system and the initial coordinate system share a second common axis and wherein the second transformation comprises a 45°

rotation about the second common axis, and further wherein the third coordinate system and the initial coordinate system share a third common axis and wherein the third transformation comprises a 45°

rotation about the third coordinate system.

17. A graphics display system comprised of:

a system memory, including a representation of a graphic primitive;

a display processor configured to execute graphics instructions stored in the system memory to modify contents of a frame buffer, wherein the frame buffer contents include a representation of a screen image;

a display device; and

a video controller capable of accessing the frame buffer and adapted to generate the screen image on the display device based on the frame buffer contents;

wherein the graphics instructions include instructions for trivially rejecting or accepting the graphic primitive comprising;

defining an initial bounding volume by the graphic primitive'"'"'s maximum and minimum x, y, and z coordinates in an initial coordinate system;

defining a first bounding volume by the graphic primitive'"'"'s maximum and minimum x′

, y′

, and z′

coordinates in a first coordinate system, wherein the first coordinate system is determined by applying a first transformation to the initial coordinate system;

intersecting the initial bounding volume and the first bounding volume to form a modified bounding volume; and

determining the graphic primitive'"'"'s relationship to a predetermined viewing volume corresponding to the screen image by determining the modified bounding volume'"'"'s relationship to the viewing volume, wherein the graphic primitive is trivially accepted if the modified bounding volume is within the viewing volume and the graphic primitive is trivially rejected if the modified bounding volume is exterior to the viewing volume.

18. The system of claim 17, wherein the defining of the first bounding volume comprises:

applying the first transformation to the graphic primitive to produce a transformed graphic primitive;

defining a transformed bounding volume by maximum and minimum x, y, and z values of the transformed graphic primitive in the initial coordinate system, wherein the transformed bounding volume comprises a plurality of transformed vertices; and

applying an inverse of the first transformation to each of the plurality of transformed vertices.

19. The system of claim 17, wherein the graphics instructions further comprise:

defining a second modified bounding volume by intersecting the initial bounding volume with a second bounding volume defined by the graphic primitive'"'"'s maximum and minimum, x″

, y″

, and z″

values in a second coordinate system determined by applying a second transformation to the initial coordinate system;

trivially accepting the graphic primitive if the second modified bounding volume is within the viewing volume and trivially rejecting the graphic primitive if the second modified bounding volume is exterior to the viewing volume;

defining a third modified bounding volume by intersecting the initial bounding volume with a third bounding volume defined by the graphic primitive'"'"'s maximum and minimum, x′

″

, y′

″

, and z′

″

values in a third coordinate system determined by applying a third transformation to the initial coordinate system; and

trivially accepting the graphic primitive if the third modified bounding volume is within the viewing volume and trivially rejecting the graphic primitive if the third modified bounding volume is exterior to the viewing volume.

20. The system of claim 19, wherein the second coordinate system and the initial coordinate system share a second common axis and wherein the second transformation comprises a 45°

rotation about the second common axis, and further wherein the third coordinate system and the initial coordinate system share a third common axis and wherein the third transformation comprises a 45°

rotation about the third coordinate system.