Method, system, and computer program product for efficient ray tracing of micropolygon geometry

A computer program product embodied on a non-transitory computer readable medium, comprising:

• computer code for identifying a plurality of surface patches;
• computer code for establishing a first hierarchy by organizing the surface patches into an acceleration structure, such that each leaf node of the first hierarchy references a bounding box of a different one of the surface patches;
• computer code for tracing rays using the first hierarchy to identify that at least one of the bounding boxes of one of the surface patches is potentially intersected by at least one of the rays;
• computer code for, for a predetermined number of the potential intersections between one of the rays and one of the bounding boxes of one of the surface patches, storing in a single array a tuple including a ray identifier of the one of the rays and a leaf identifier associated with the one of the surface patches in the one of the bounding boxes that are potentially intersected;
• computer code for, for each of the leaf identifiers stored in the array:
• determining a level of detail of a two-dimensional array of vertices and micropolygons based on the bounding box of the surface patch that is referenced by the leaf identifier and the rays identified to potentially intersect the surface patch, such that a number of the micropolygons is at least equal to a number of the rays identified to potentially intersect the surface patch referenced by the leaf identifier;
• decomposing, on-demand, the surface patch referenced by the leaf identifier into the two-dimensional array of vertices and micropolygons;
• establishing a second hierarchy for the two-dimensional array of vertices and micropolygons of the surface patch referenced by the leaf identifier, the second hierarchy being determined by a connectivity of the micropolygons in the two-dimensional array of vertices and micropolygons, in order to accelerate ray tracing;
• and
• intersecting, utilizing the second hierarchy, the micropolygons of the two dimensional array of vertices and micropolygons of the surface patch referenced by the leaf identifier with all rays in the array that are stored in one of the tuples of the array including the leaf identifier.

An apparatus, comprising:

• one or more processors capable of:
• identifying a plurality of surface patches;
• establishing a first hierarchy by organizing the surface patches into an acceleration structure, such that each leaf node of the first hierarchy references a bounding box of a different one of the surface patches;
• tracing rays using the first hierarchy to identify that at least one of the bounding boxes of one of the surface patches is potentially intersected by at least one of the rays;
• for a predetermined number of the potential intersections between one of the rays and one of the bounding boxes of one of the surface patches, storing in a single array a tuple including a ray identifier of the one of the rays and a leaf identifier associated with the one of the surface patches in the one of the bounding boxes that are potentially intersected;
• for each of the leaf identifiers stored in the array:
• determining a level of detail of a two-dimensional array of vertices and micropolygons based on the bounding box of the surface patch that is referenced by the leaf identifier and the rays identified to potentially intersect the surface patch, such that a number of the micropolygons is at least equal to a number of the rays identified to potentially intersect the surface patch referenced by the leaf identifier;
• decomposing, on-demand, the surface patch referenced by the leaf identifier into the two-dimensional array of vertices and micropolygons;
• establishing a second hierarchy for the two-dimensional array of vertices and micropolygons of the surface patch referenced by the leaf identifier, the second hierarchy being determined by a connectivity of the micropolygons in the two-dimensional array of vertices and micropolygons, in order to accelerate ray tracing;
• and
• intersecting, utilizing the second hierarchy, the micropolygons of the two dimensional array of vertices and micropolygons of the surface patch referenced by the leaf identifier with all rays in the array that are stored in one of the tuples of the array including the leaf identifier.