Ray intersection reduction using directionally classified target lists

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.

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.

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.

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.

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.