Intersection testing in a ray tracing system using convex polygon edge signed parameters

An intersection testing module, for use in a ray tracing system, configured to perform intersection testing for a ray with respect to a plurality of convex polygons, wherein each of the convex polygons is defined by an ordered set of vertices, and wherein at least one of the vertices is a shared vertex which is used to define two or more of the convex polygons, the intersection testing module being configured to:

• project the vertices of the convex polygons onto a pair of axes orthogonal to the ray direction, wherein the origin of the pair of axes corresponds with the ray origin;
• and
• for each of the convex polygons:
• for each edge of the convex polygon defined by two of the projected vertices, determine a signed parameter, wherein the sign of the signed parameter is indicative of which side of the edge the ray passes on, wherein the position of a first of the projected vertices vi defining the edge is defined with coordinates pi and qi along the respective axes of the pair of axes, and wherein a position of a second of the projected vertices vj defining the edge is defined with coordinates pj and qj along the respective axes of the pair of axes, wherein the intersection testing module is configured to use a module to determine the sign of the signed parameter if the ray is determined to intersect a point on the edge, wherein the module is configured to:
• take as inputs, indications which classify each of the pi, qi, pj and qj coordinates as negative, zero or positive, and
• output, for valid combinations of classifications of the pi, qi, pj and qj coordinates, an indication of the sign of the signed parameter;
• and
• determine whether the ray intersects the convex polygon based on the signs of the signed parameters determined for the edges of the convex polygon.

A non-transitory computer readable storage medium having stored thereon an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, configures the integrated circuit manufacturing system to manufacture an intersection testing module for use in a ray tracing system, the intersection testing module being configured to perform intersection testing for a ray with respect to a plurality of convex polygons, wherein each of the convex polygons is defined by an ordered set of vertices, and wherein at least one of the vertices is a shared vertex which is used to define two or more of the convex polygons, the intersection testing module being configured to:

• project the vertices of the convex polygons onto a pair of axes orthogonal to the ray direction, wherein the origin of the pair of axes corresponds with the ray origin;
• and
• for each of the convex polygons:
• for each edge of the convex polygon defined by two of the projected vertices, determine a signed parameter, wherein the sign of the signed parameter is indicative of which side of the edge the ray passes on, wherein the position of a first of the projected vertices vi defining the edge is defined with coordinates pi and qi along the respective axes of the pair of axes, and wherein a position of a second of the projected vertices vj defining the edge is defined with coordinates pj and qj along the respective axes of the pair of axes, wherein the intersection testing module is configured to use a module to determine the sign of the signed parameter if the ray is determined to intersect a point on the edge, wherein the module is configured to:
• take as inputs, indications which classify each of the pi, qi, pj and qj coordinates as negative, zero or positive, and
• output, for valid combinations of classifications of the pi, qi, pj and qj coordinates, an indication of the sign of the signed parameter;
• and
• determine whether the ray intersects the convex polygon based on the signs of the signed parameters determined for the edges of the convex polygon.