Ray intersection reduction using directionally classified target lists

• US 6,489,955 B1
• Filed: 06/07/1999
• Issued: 12/03/2002
• Est. Priority Date: 06/07/1999
• Status: Expired due to Fees

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Intel Corporation
• Inventors: Newhall, Jr., William Parsons
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Sealey, Lance W.
• Application Number:
  US09/327,015
• Time in Patent Office: 1,275 Days
• Field of Search: 345/419, 345/420, 345/441, 345/427, 345/421
• US Class Current: 345/419
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

A method and apparatus, in a computer graphics display system, for reducing the number of polygon intersection tests required to test a ray against a set of polygons. With this method, a multitude of polygons that represent images of object or parts of objects are identified, and these polygons are grouped into a plurality of groups on the basis of the general orientations of the polygons. Also, a ray is identified that represents a line of sight, and the general direction of the ray is compared with the general orientations of the polygons in the above-mentioned groups of polygons. On the basis of this comparison, selected groups of polygons are eliminated from further consideration. Polygons in other groups may be tested to determine if the ray intersects the polygons. The preferred embodiment of the invention described herein in detail has a number of important features. These include (1) a compressed representation of the general direction of displacement of a 3D vector called the directional classification code and a method for computing it given a vector, and (2) a conservative but efficient technique for determining whether the dot product of two vectors of equal length will result in a positive or negative value by comparing their directional classification codes using boolean logic.

Claims

1. A method of reducing polygonal candidates for intersection testing in a ray tracer comprising the steps of:

computing a directional classfication code of a ray, and eliminating directionally classified polygon lists, each of the lists comprising a plurality of polygons represented by a directional classification code, whose directional classification code when compared with a directional classification code of the ray'"'"'s directional vector using pre-established criteria would result in a positive dot product;

if the results of the comparison show that a negative dot product would result or that the result is not certain for all vectors of the polygons represented by the directional classification code of each of the lists, then the polygons in each of the directionally classified polygon lists will be tested against the ray; and

rendering polygons in the non-eliminated directionally classified polygon lists that intersect the ray.

2. A method in a computer graphics display system for reducing a number of polygon intersection tests required to test a ray against a set of polygons, the method comprising:

identifying a plurality of polygons representing images of objects or parts of objects;

grouping the polygons together into a plurality of groups on the basis of general orientations of the polygons;

determining a group orientation value representing the general orientations of the polygons in each group;

identifying a ray representing a line of sight;

determining a ray direction value representing the general direction of the ray;

comparing the direction value of the ray with the group orientation values of said groups of polygons;

eliminating selected groups of polygons from further consideration on the basis of said comparison;

testing polygons in remaining groups to determine if the ray intersects the polygons; and

rendering polygons of the non-eliminated groups that are intersected by the ray, thereby resulting in a more efficient computer graphics display system.

3. A method according to claim 2, wherein the grouping step includes the steps of:

for each of the polygons, determining a polygon orientation value representing the general orientation of the polygon; and

grouping the polygons together into the plurality of groups on the basis of the determined polygon orientation values.

4. A method according to claim 3, wherein:

the step of determining the polygon orientation values includes the steps of, for each of the polygons,

i) determining a polygon normal vector, and

ii) determining and storing a compressed representation of the polygon vector; and

the step of grouping the polygons together on the basis of the polygon orientation values includes the step of grouping the polygons together on the basis of the compressed representations of the polygon vectors.

5. A method according to claim 4, wherein the comparing step includes the steps of:

for each of the group of polygons, determining a group orientation value from the compressed representation of the polygon vectors of the polygons in the group;

determining a ray direction value representing the general direction of the ray; and

comparing the ray direction value against the group orientation values of the groups of polygons.

6. A method according to claim 2, further comprising the steps of:

for each of the polygons, determining a polygon normal vector for the polygon; and

for each of the groups of polygons,

i) determining a group normal vector from the polygon normal vectors for the polygons in the group, and

ii) using the group normal vector to sort the polygons in the group into an order.

7. A method according to claim 6, wherein the step of determining the group normal vector includes the step of adding together the polygon normal vectors for the polygons in the group to obtain the group normal vector.

8. A method according to claim 7, wherein the step of using the group normal vector to sort the polygons in the group includes the steps of:

determining a length of the group normal vector;

dividing the group normal vector by its length to determine a group unit normal vector; and

for each polygon in the group, determining the extent of the polygon along the group normal vector.

9. The method according to claim 2, further comprising:

computing a directional classification code of the ray, and eliminating directionally classified polygon groups from further consideration, each of the groups comprising a plurality of polygons represented by a directional classification code, whose directional classification code when compared with the directional classification code of the ray'"'"'s directional vector using pre-established criteria would result in a positive dot product; and

testing the polygons in each of the directionally classified polygon groups against the ray if the results of the comparison show that a negative dot product would result or that the result is not certain for all vectors of the polygons represented by the directional classification code of each of the groups.

10. Apparatus in a computer graphics display system for reducing the number of polygons intersection tests required to test a ray against a set of polygons, the method using:

means for identifying a multitude of polygons representing images of objects or parts of objects;

means for grouping the polygons together into a plurality of groups on the basis of the general orientations of the polygons;

means for determining a group orientation value representing the general orientations of the polygons in each group;

means for identifying a ray representing a line of sight;

determining a ray direction value representing the general direction of the ray;

means for comparing the direction on value of the ray with the group orientation values of said groups of polygons;

means for eliminating selected groups of polygons from further consideration on the basis of said comparison;

means for testing polygons in remaining groups to determine if the ray intersects the polygons; and

means for rendering polygons of the non-eliminated groups that are intersected by the ray, thereby resulting in a more efficient computer graphics display system.

11. Apparatus according to claim 10, wherein, the means for grouping the polygons together includes:

means for determining, for each of the polygons, a polygon orientation value representing the general orientation of the polygon; and

means for grouping the polygons together into the plurality of groups on the basis of the determined polygon orientation values.

12. Apparatus according to claim 11, wherein:

the means for determining the polygon orientation values includes

i) means for determining, for each of the polygons, a polygon normal vector, and

ii) means for determining and storing a compressed representation of the polygon normal vectors; and

the means for grouping the polygons together on the basis of the polygon orientation values includes means for grouping the polygons together on the basis of the compressed representations of the polygon vectors.

13. Apparatus according to claim 12, wherein the means for comparing includes:

means for determining, for each of the group of polygons, a group orientation value from the compressed representations of the polygon vectors in the group;

means for determining a ray direction value representing the general direction of the ray; and

means for comprising the ray direction value against the group orientation values of the groups of polygons.

14. The apparatus according to claim 10, further comprising a means for computing a directional classification code of the ray, wherein

the means for eliminating further comprises eliminating directionally classified polygon groups from further consideration, each of the groups comprising a plurality of polygons represented by a directional classification code, whose directional classification code when compared with the directional classification code of the ray'"'"'s directional vector using pre-established criteria would result in a positive dot product;

and

the means for testing further comprising testing the polygons in each of the directionally classified polygon groups against the ray if the results of the comparison show that a negative dot product would result or that the result is not certain for all vectors of the polygons represented by the directional classification code of each of the groups.

15. A method in a computer graphics display system for reducing the number of polygon intersection tests required to test a ray against a set of polygons, comprising:

identifying a multitude of polygons representing objects or parts of objects;

for each of the polygons,

i) determining a polygon normal vector, and

ii) determining and storing a compressed representation of the polygon vector;

grouping the polygons together into a plurality of groups on the basis of the compressed representations of the polygon vectors;

for each of said groups, determining a group unit normal vector from the compressed representations of the polygon vectors of the polygons in the group, and determining a directional classification code for the group;

identifying a ray representing a line of sight;

identifying a direction vector for the ray;

determining a directional classification code for the ray from the direction of the ray;

testing the directional classification code for the ray against the directional classification codes of the polygon groups;

on the basis of said testing, eliminating selected groups of the polygons from further consideration;

testing polygons in remaining groups to determine if the ray intersects the polygons; and

rendering polygons of the non-eliminated groups that are intersected by the ray, thereby resulting in a more efficient computer graphics display system.

16. A method according to claim 15, further comprising:

providing a directional classification code of zero to represent rays or polygons for which directional classification does not apply or has not been applied; and

using a directional classification test that always returns positive when testing any directional classification code against a directional classification code of zero.

17. A method according to claim 15, further comprising using a rendering preprocess of sorting the polygons in a directionally classified triangle list in order from most positive maximum group unit normal extent to most negative group unit normal extent.

18. A method according to claim 15, further comprising using a rendering preprocess of sorting the rays to be tested against a sorted directionally classified triangle list in order from most positive maximum group unit normal extent to most negative group unit normal extent.

19. A method according to claim 15, further comprising eliminating intersection tests by testing a group of rays with a common directional classification code against a group of polygons with a common directional classification code with a single directional classification test (instead of testing each ray individually against the group of polygons.

20. A method according to claim 15, further comprising using an early exit test of removing a ray from the list of rays to be tested against a sorted directionally classified triangle list when the maximum extent of the triangles being tested is greater than the minimum extent of the ray.

21. A method according to claim 20, further comprising replacing a ray which passes the early exit test with a ray whose maximum extent is less than the minimum extent of the polygon currently being processed.

22. A method according to claim 15, further comprising skipping over those polygons whose minimum extent is greater than the maximum extent of the first ray in a sorted list of rays.

23. The method according to claim 15, wherein

the eliminating step eliminates directionally classified polygon groups from further consideration, each of the groups comprising a plurality of polygons represented by a directional classification code, whose directional classification code when compared with the directional classification code of the ray'"'"'s directional vector using pre-established criteria would result in a positive dot product;

and

the testing step tests the polygons in each of the directionally classified polygon groups against the ray if the results of the comparison show that a negative dot product would result or that the result is not certain for all vectors of the polygons represented by the directional classification code of each of the groups.

24. Apparatus in a computer graphics display system for reducing the number of polygons intersection tests required to test a ray against a set of polygons, comprising:

means for identifying a multitude of polygons representing objects of parts of objects;

means for determining a polygon normal vector for each of the polygons;

means for determining and storing a compressed representation of each of the polygon vectors;

means for grouping the polygons together into a plurality of groups on the basis of the compressed representations of the polygon vectors;

means for determining, for each of said groups, (i) a group unit normal vector from the compressed representations of the polygon vectors of the polygons in the group, and (ii) a directional classification code for the group;

means for identifying a ray representing a line of sight;

means for identifying a direction vector for the ray;

means for determining a directional classification code from the direction vector of the ray;

means for testing the directional classification code for the ray code against the directional classification codes for the polygon groups;

means for eliminating selected groups of the polygons from further consideration on the basis of said testing;

means for testing polygons in remaining groups to determine if the ray intersects the polygons; and

means for rendering polygons of the non-eliminated groups that are intersected by the ray, thereby resulting in a more efficient computer graphics display system.

25. The apparatus according to claim 24, wherein

the means for eliminating further comprises eliminating directionally classified polygon groups from further consideration, each of the groups comprising a plurality of polygons represented by a directional classification code, whose directional classification code when compared with the directional classification code of the ray'"'"'s directional vector using pre-established criteria would result in a positive dot product; and

the means for testing further comprising testing the polygons in each of the directionally classified polygon groups against the ray if the results of the comparison show that a negative dot product would result or that the result is not certain for all vectors of the polygons represented by the directional classification code of each of the groups.

26. An article of manufacture comprising:

a computer usable medium having computer readable program code embodied therein for reducing the number of polygon intersection tests required to test a ray against a set of polygons, the computer readable program code in said article of manufacture comprising;

computer readable program code for causing a computer to identify a multitude of polygons representing images of objects or parts of objects;

computer readable program code for causing a computer to group the polygons together into a plurality of groups on the basis of the general orientations of the polygons;

computer readable program code for causing a computer to determine a group orientation value representing the general orientations of the polygons in each group;

computer readable program code for causing a computer to identify a ray representing a line of sight;

computer readable program code for causing a computer to determine a ray direction value representing the general direction of the ray;

computer readable program code for causing a computer to compare the direction value of the ray with the group orientation values of ad groups of polygons;

computer readable program code for causing a computer to eliminate selected groups of polygons from further consideration on the basis of said comparison;

computer readable program code for causing a computer to test polygons in remaining groups to determine if the ray intersects the polygons; and

computer readable program code for causing a computer to render polygons of the non-eliminated groups that are intersected by the ray, thereby resulting in a more efficient article of manufacture.

27. An article of manufacture according to claim 26, wherein the computer readable program code for causing a computer to group the polygons together includes:

computer readable program code for causing a computer to determine, for each of the polygons, a polygon orientation value representing the general orientation of the polygon; and

computer readable program code for causing a computer to group the polygons together into the plurality of groups on the basis of the determined polygon orientation values.

28. The article of manufacture according to claim 26, further comprising:

computer readable program code for causing a computer to compute a directional classification code of the ray, and eliminate directionally classified polygon groups from further consideration, each of the groups comprising a plurality of polygons represented by a directional classification code, whose directional classification code when compared with the directional classification code of the ray'"'"'s directional vector using pre-established criteria would result in a positive dot product; and

computer readable program code for causing a computer to test the polygons in each of the directionally classified polygon groups against the ray if the results of the comparison show that a negative dot product would result or that the result is not certain for all vectors of the polygons represented by the directional classification code of each of the groups.