DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Amendment
This Office Action is in response to Applicant’s amendment/response filed on 01/27/2026, which has been entered and made of record. Applicant’s amendments to the Specification and Drawings have overcome each and every objection previously set forth in the Non-Final Office Action mailed 10/28/2025.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 9-10 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Muthler et al. (US 20210090319 A1, hereinafter “Muthler”) in view of Hughes (US 2021/0295598 A1, hereinafter “Hughes”) and Lehtinen et al. (US 20160071234 A1, hereinafter “Lehtinen”).
Regarding claim 9, Muthler discloses A method of providing a ray tracing acceleration data structure (para. [0060], “the acceleration data structure comprises a hierarchy of bounding volumes (bounding volume hierarchy or BVH) that recursively encapsulates smaller and smaller bounding volume subdivisions.) for use by a graphics processor that is operable to (para. [0072], “FIG. 1 illustrates an example real time ray interactive tracing graphics system 100 for generating images using three dimensional (3D) data of a scene or object(s)”). Note that: system 100 can be regarded as graphics processor. perform ray tracing using a ray tracing acceleration data structure (para. [0008], “the example non-limiting technology herein relates to a hardware-based traversal coprocessor that efficiently traverses an acceleration data structure e.g., for real time ray tracing”) that comprises a plurality of nodes, wherein each node of the ray tracing acceleration data structure represents a respective volume, and one or more of the nodes of the ray tracing acceleration data structure is an end node associated with geometry that falls within the respective volume that the respective end node represents; (para. [0060], “the acceleration data structure comprises a hierarchy of bounding volumes (bounding volume hierarchy or BVH) that recursively encapsulates smaller and smaller bounding volume subdivisions. The largest volumetric bounding volume may be termed a "root node.” The smallest subdivisions of such hierarchy of bounding volumes ("leaf nodes") contain items. The items could be primitives (e.g., polygons such as triangles) that define surfaces of the object"). Note that: (1) the acceleration structure contains nodes associated with bounding volumes that contain respective items (geometries or primitives); and (2) the nodes and the node corresponding volumes include parent / child nodes covering leaf nodes and corresponding volumes, respectively.
wherein the graphics processor is operable to trace a ray by traversing the ray tracing acceleration data structure and testing the ray against volumes represented by nodes of the ray tracing acceleration data structure to determine whether the ray intersects the volumes, and when it is determined that the ray intersects a volume represented by an end node of the ray tracing acceleration data structure that is associated with a polygon that falls within the volume that the end node represents, (para. [0070], “Given a BVH, ray tracing amounts to a tree search where each node in the tree visited by the ray has a bounding volume for each descendent branch or leaf, and the ray only visits the descendent branches or leaves whose corresponding bound volume it intersects. In this way, only a small number of primitives must be explicitly tested for intersection, namely those that reside in leaf nodes intersected by the ray. In the example non-limiting embodiments, the traversal coprocessor accelerates both tree traversal (including the ray-volume tests) and ray-primitive tests”; para. [0095], “To determine whether the ray 302 intersects one or more triangles in the mesh 320, each triangle could be directly tested against the ray 302. But to accelerate the process (since the object could contain many thousands of triangles), the ray 302 is first tested against the bounding volumes 310 and 315.”). Note that: (1) ray-volume tests indicate determining whether the ray intersects the volumes while ray-primitive tests indicate determining whether determine whether the ray intersects the geometry or primitive; and (2) since a primitive is contained in a volume, ray-primitive tests happen after ray-volume tests have determined that the ray intersects the volumes. load polygon geometry data stored for the end node, and process geometry using the loaded polygon geometry data, … (para. [0099], “The traversal coprocessor 138 determines which bounding volumes of a BVH data structure the ray intersects (the "ray-complet" test 512) and subsequently whether the ray intersects one or more primitives in the intersected bounding volumes and which triangles are intersected (the "ray-primitive test" 520)”; para. [0130], “A Stack Management Unit 740 inspects the traversal state to determine what type of data needs to be retrieved and which data path (complet or primitive) will consume it …The ray-complet test path of the TTU 700 identifies which bounding volumes are intersected by the ray … The intersections for the primitives are determined in the ray-primitive test path including one or more ray-primitive test and transform blocks 720 and one or more intersection management blocks 722”; FIG. 8A: the bounding volume represented by N4 has and is associated with two triangles “01” and “02”; FIG. 8B: triangles “01” and “02” geometry data are stored in a predefined data structure (tree data structure with leaf nodes) in “MEMORY”; para. [0132], “The TTU 700 may request the BVH data structure identified in the query to be retrieved from memory outside of the TTU 700”; para. [0150], “a ray/triangle (or other primitive) intersection 1026 that are each performed by the TTU 700”). Note that: (1) when the ray-geometry (ray-triangle) intersection is determined by TTU 700 with associated triangles (two triangles “01” and “02”), Stack Management Unit 740 can determine what data need to be retrieved or loaded for the associated triangles (two triangles “01” and “02”) from memory outside of the TTU 700; and (2) the triangles with the loaded or retrieved triangle geometry data stored in the predefined data structure are used and processed by TTU 700 for ray-triangle intersection test.
the method comprising:
generating a ray tracing acceleration data structure for use by the graphics processor, (para. [0069], “The acceleration data structure most commonly used by modem ray tracers is a bounding volume hierarchy (BVH) comprising nested axis-aligned bounding boxes (AABBs). The leaf nodes of the BVH contain the primitives (e.g., triangles) to be tested for intersection”; para. [0084], “the example non-limiting technology used to support the system 100 of FIG. 1 provides additional accelerated ray tracing enhancements to a number of units as well as a substantial effort devoted to BVH construction. BVH construction need not be hardware accelerated (although it may be in some non-limiting embodiments) but could instead be implemented using highly-optimized software routines running on SMs 132 and/or CPU 120 and/or other development systems”). Note that: (1) a BVH can be regarded as a ray tracing acceleration data structure; and (2) the system 100 in FIG. 1 can construct or generate a BVH using highly-optimized software routines running on SMs 132 and/or CPU 120 and/or other development systems. wherein the ray tracing acceleration data structure comprises a plurality of nodes, wherein each node of the ray tracing acceleration data structure represents a respective volume, and one or more of the nodes of the ray tracing acceleration data structure is an end node associated with a bounding volume primitive that falls within the respective volume that the respective end node represents; and (para. [0060], “the acceleration data structure comprises a hierarchy of bounding volumes (bounding volume hierarchy or BVH) that recursively encapsulates smaller and smaller bounding volume subdivisions. The largest volumetric bounding volume may be termed a "root node.” The smallest subdivisions of such hierarchy of bounding volumes ("leaf nodes") contain items. The items could be primitives (e.g., polygons such as triangles) that define surfaces of the object; FIG. 8B: the tree acceleration structure (a BVH) comprises a plurality of nodes (i.e., “N1”-“N11”), and each node represents a respective volume). Note that: (1) the acceleration structure contains nodes associated with bounding volumes that contain respective items (geometries or primitives); and (2) the nodes and the node corresponding volumes include parent / child nodes covering leaf nodes and corresponding volumes, respectively.
However, Muthler fails to disclose, but in the same art of computer graphics, Hughes discloses a bounding volume primitive that falls within the respective volume that the respective node represents; and (Hughes, para. [0086], “In some examples, the BVH identification unit 1020 is operable to repeat the identification process until a predetermined level of detail is reached. This means that the BVH may be traversed, with intersection determination processing being performed, until one or more predetermined conditions are met regarding when to terminate the traversal. The predetermined level of detail may be different for different parts of the BVH”; para. [0087], “The predetermined level of detail may be a predetermined multiple of the pixel size used in the rasterization process, such as half, one, one and a quarter, one and a half, or two times the size of the pixels (although of course, any suitable value may be selected as appropriate to achieve a desired visual effect or level of performance). In such a case, it is the size of the bounding volume associated with a BVH node that may be compared to the pixel size so as to determine whether the predetermined level of detail has been reached.”). Note that: (1) when a BVH node 1 has two child nodes, node 2 and node 3. The bounding volume represented by node 1 is an AABB primitive denoted by AABB_n1. The two bounding volumes represented by node 2 and node 3 are two AABB primitives denoted by AABB_n2 and AABB_n3, respectively; (2) When it is determined that a ray intersects the bounding volume AABB_n1, if the size of AABB_n1 is below the predetermined level of detail as specified in the citations of Hughes above (e.g., a predetermined multiple of the pixel size used in the rasterization process), the traversal terminates without further testing the ray against AABB_n2 and AABB_n3 which are contained in AABB_n1, saving the ray intersection testing compute. In this case, AABB_n1 can be regarded as a bounding volume primitive whose size is below the predetermined level of detail; (3) When the traversal stops for AABB_n1, the graphics omits testing the ray against the bounding volume primitive to determine whether the ray intersects the bounding volume primitive including all primitives within it; and (4) a bounding volume primitive falls within the volume represented by its parent node in the ray tracing acceleration data structure.
Muthler and Hughes are in the same field of endeavor, namely computer graphics. Before the effective filing date of the claimed invention, it would have been obvious to apply having a predetermined level of detail and terminating traversal for the volume associated to a bounding volume primitive whose size is below the predetermined level of detail, as taught by Hughes into Muthler. The motivation would have been “the BVH may terminate with bounding volumes representing groups of objects-this would lead to a coarse representation, but one that is reduced in size and may be traversed very quickly.” (Hughes, para. [0024]). The suggestion for doing so would allow to reduce the number of ray-primitive tests and traverse the BVH quickly to improve the processing speed. Therefore, it would have been obvious to combine Muthler and Hughes.
However, Muthler in view of Hughes fails to disclose, but in the same art of computer graphics, Lehtinen discloses … wherein the polygon geometry data is stored using a predefined data structure; (Lehtinen, FIG. 1B: “Compression Block 140” includes or stores includes or stores “Triangle 0 142”, “Triangle 1 144”, “Triangle 2 146”, and “Header 148”; “Header 148” has subfields “MD2 32”, “MD1 2”, “MD0 32”, “α 3”, “Mode 3”, and the x/y/z coordinates or positions of three vertexes of three or more triangles and other information including header using a size of 128-byte block; para. [0030], “each of the three alpha bits may indicate whether a corresponding triangle (e.g., triangle 2, triangle 1, triangle 0) is fully opaque (or, alternatively, partially transparent)”). Note that: (1) Compression Block 140 (the predefined data structure) can be regarded as the predefined data structure that includes the fields 142, 144, 146, and 148; (2) it is obvious to one having ordinary skill that the data structure can be used for a node associated with a bounding volume primitive while there no vertexes of triangles to be filled in, to keep using the same format without havinga different data structure for a node associated with a bounding volume primitive; (3) “α 3” in the “Header 148” can be used a same field to store geometry data (i.e., opaque or partially transparent) for a node associated with a bounding volume primitive as used to store corresponding polygon geometry data; and (4) in addition, a same field (e.g., GeomID) as geometry data can be put into the compression block (the predefined data structure) or its header to store the ID information for the bounding volume either including triangles or being a bounding volume primitive.
storing, for each end node of the ray tracing acceleration data structure that is associated with a bounding volume primitive, bounding volume geometry data using the same predefined data structure as is used to store polygon geometry data. (Lehtinen, FIG. 1B: “Compression Block 140” includes or stores “Triangle 0 142”, “Triangle 1 144”, “Triangle 2 146”, and “Header 148”; “Header 148” has subfields “MD2 32”, “MD1 2”, “MD0 32”, “α 3”, and “Mode 3”; para. [0030], “each of the three alpha bits may indicate whether a corresponding triangle (e.g., triangle 2, triangle 1, triangle 0) is fully opaque (or, alternatively, partially transparent)”). Note that: (1) Compression Block 140 (the predefined data structure) can be regarded as the predefined data structure that includes the fields 142, 144, 146, and 148; (2) it is obvious to one having ordinary skill that the data structure can be used for a node associated with a bounding volume primitive while there no vertexes of triangles to be filled in, to keep using the same format without having a different data structure for a node associated with a bounding volume primitive; (3) “α 3” in the “Header 148” can be used a same field to store geometry data (i.e., opaque or partially transparent) for a node associated with a bounding volume primitive as used to store corresponding polygon geometry data; and (4) in addition, a same field (e.g., GeomID) can be put into the compression block (the predefined data structure) or its header to store the ID information for the bounding volume either including triangles or being a bounding volume primitive.
Muthler in view of Hughes, and Lehtinen, are in the same field of endeavor, namely computer graphics. Before the effective filing date of the claimed invention, it would have been obvious to apply having a predefined data structure storing geometry data (e.g., vertex positions of a set of one or more polygons, and other geometry information) with a size corresponding to a number of cache lines (entries), as taught by Lehtinen into Muthler in view of Hughes. The motivation would have been “Because the number of geometric primitives in a typical scene may be quite large (e.g., on the order of many millions of triangles, etc.), memory bandwidth limitations may constrain overall rendering performance. Thus, there is a need for addressing these issues” (Lehtinen, para. [0004]). The suggestion for doing so would allow to address memory bandwidth limitations for improving geometry data access of geometric primitives. Therefore, it would have been obvious to combine Muthler, Hughes, and Lehtinen.
Claim 10 reciting “A non-transitory computer readable storage medium storing software code which when executing on a processor” is corresponding to the method of claim 9. Therefore, claim 10 is rejected for the same rationale for claim 9.
In addition, the combination of Muthler, Hughes, and Lehtinen discloses A non-transitory computer readable storage medium storing software code which when executing on a processor (Muther, para. [0074], “Based on execution of the application on processor 120, the processor may issue instructions for the GPU 130 to generate images using 3D data stored in memory 140”; para. [0352], “Computer programs, or computer control logic algorithms, may be stored in the main memory 1940 and/or Such computer programs, when executed, enable the system 1965 to perform various functions. The memory 1940, the storage, and/or any other storage are possible examples of computer-readable media”).
Regarding claim 18, the combination of Muthler, Hughes, and Lehtinen discloses A graphics processor that is operable to (Muthler, para. [0072], “FIG. 1 illustrates an example real time ray interactive tracing graphics system 100 for generating images using three dimensional (3D) data of a scene or object(s)”). Note that: system 100 can be regarded as graphics processor. perform ray tracing using a ray tracing acceleration data structure (Muthler, para. [0008], “the example non-limiting technology herein relates to a hardware-based traversal coprocessor that efficiently traverses an acceleration data structure e.g., for real time ray tracing”) that comprises a plurality of nodes, wherein each node of the ray tracing acceleration data structure represents a respective volume, and one or more of the nodes of the ray tracing acceleration data structure is an end node associated with geometry that falls within the respective volume that the respective end node represents; (Muthler, para. [0060], “the acceleration data structure comprises a hierarchy of bounding volumes (bounding volume hierarchy or BVH) that recursively encapsulates smaller and smaller bounding volume subdivisions. The largest volumetric bounding volume may be termed a "root node.” The smallest subdivisions of such hierarchy of bounding volumes ("leaf nodes") contain items. The items could be primitives (e.g., polygons such as triangles) that define surfaces of the object"). Note that: (1) the acceleration structure contains nodes associated with bounding volumes that contain respective items (geometries or primitives); and (2) the nodes and the node corresponding volumes include parent / child nodes covering leaf nodes and corresponding volumes, respectively.
the graphics processor comprising:
a ray-volume intersection testing circuit operable to test a ray against a volume represented by a node of a ray tracing acceleration data structure to determine whether the ray intersects the volume; (Muthler, para. [0070], “Given a BVH, ray tracing amounts to a tree search where each node in the tree visited by the ray has a bounding volume for each descendent branch or leaf, and the ray only visits the descendent branches or leaves whose corresponding bound volume it intersects. In this way, only a small number of primitives must be explicitly tested for intersection, namely those that reside in leaf nodes intersected by the ray. In the example non-limiting embodiments, the traversal coprocessor accelerates both tree traversal (including the ray-volume tests) and ray-primitive tests”; para. [0058], “a hardware co-processor (herein referred to as a "traversal coprocessor" or in some embodiments a "tree traversal unit" or "TTU") accelerates certain processes supporting interactive ray tracing including ray-bounding volume intersection tests, ray-primitive intersection tests and ray "instance" transforms.”). Note that: (1) ray-volume tests indicating determining whether the ray intersects the volumes; and (2) "traversal coprocessor" or in some embodiments a "tree traversal unit" or "TTU" can be regarded as a ray-volume intersection testing circuit.
a geometry data loading circuit operable to load polygon geometry data stored for an end node of a ray tracing acceleration data structure, wherein the polygon geometry data is stored using a predefined data structure; and (Muthler, para. [0099], “The traversal coprocessor 138 determines which bounding volumes of a BVH data structure the ray intersects (the "ray-complet" test 512) and subsequently whether the ray intersects one or more primitives in the intersected bounding volumes and which triangles are intersected (the "ray-primitive test" 520)”; para. [0130], “A Stack Management Unit 740 inspects the traversal state to determine what type of data needs to be retrieved and which data path (complet or primitive) will consume it …The ray-complet test path of the TTU 700 identifies which bounding volumes are intersected by the ray … The intersections for the primitives are determined in the ray-primitive test path including one or more ray-primitive test and transform blocks 720 and one or more intersection management blocks 722”; FIG. 8A: the bounding volume represented by N4 has and is associated with two triangles “01” and “02”; FIG. 8B: triangles “01” and “02” geometry data are stored in a predefined data structure (tree data structure with leaf nodes) in “MEMORY”; para. [0132], “The TTU 700 may request the BVH data structure identified in the query to be retrieved from memory outside of the TTU 700”). Note that: (1) when the ray-geometry (ray-triangle) intersection is determined by TTU 700 with associated triangles (two triangles “01” and “02”), Stack Management Unit 740 can determine what data need to be retrieved or loaded, and can be regarded as a geometry data loading circuit; (2) when the ray-volume intersection is determined by TTU 700 with associated bounding volume primitives, Stack Management Unit 740 can determine what data need to be retrieved or loaded; and (3) FIG. 8B shows a ray tracing acceleration data structures (BVH).
a ray tracing circuit operable to trace a ray by traversing a ray tracing acceleration data structure and causing the ray-volume intersection testing circuit to test the ray against volumes represented by nodes of the ray tracing acceleration data structure to determine whether the ray intersects the volumes, and when it is determined by the ray-volume intersection testing circuit that the ray intersects a volume represented by an end node of the ray tracing acceleration data structure that is associated with a polygon that falls within the volume that the end node represents, (Muthler, para. [0070], “Given a BVH, ray tracing amounts to a tree search where each node in the tree visited by the ray has a bounding volume for each descendent branch or leaf, and the ray only visits the descendent branches or leaves whose corresponding bound volume it intersects. In this way, only a small number of primitives must be explicitly tested for intersection, namely those that reside in leaf nodes intersected by the ray. In the example non-limiting embodiments, the traversal coprocessor accelerates both tree traversal (including the ray-volume tests) and ray-primitive tests”; para. [0078], “To enable the GPU 130 to perform ray tracing in real time in an efficient manner, the GPU is provided with traversal coprocessor 138 coupled to one or more SMs 13”; para. [0095], “To determine whether the ray 302 intersects one or more triangles in the mesh 320, each triangle could be directly tested against the ray 302. But to accelerate the process (since the object could contain many thousands of triangles), the ray 302 is first tested against the bounding volumes 310 and 315.”). Note that: (1) ray-volume tests indicate determining whether the ray intersects the volumes while ray-primitive tests indicate determining whether determine whether the ray intersects the geometry or primitive; (2) since a primitive is contained in a volume, ray-primitive tests happen after ray-volume tests have determined that the ray intersects the volumes; and (3) GPU 130 is regarded as a ray tracing circuit and its traversal coprocessor 138 is responsible for ray-volume tests and ray-geometry tests. cause the geometry data loading circuit to load polygon geometry data stored for the end node, and cause geometry to be processed using the loaded polygon geometry data; (Muthler, para. [0099], “The traversal coprocessor 138 determines which bounding volumes of a BVH data structure the ray intersects (the "ray-complet" test 512) and subsequently whether the ray intersects one or more primitives in the intersected bounding volumes and which triangles are intersected (the "ray-primitive test" 520)”; para. [0130], “A Stack Management Unit 740 inspects the traversal state to determine what type of data needs to be retrieved and which data path (complet or primitive) will consume it …The ray-complet test path of the TTU 700 identifies which bounding volumes are intersected by the ray … The intersections for the primitives are determined in the ray-primitive test path including one or more ray-primitive test and transform blocks 720 and one or more intersection management blocks 722”; FIG. 8A: the bounding volume represented by N4 has and is associated with two triangles “01” and “02”; FIG. 8B: triangles “01” and “02” geometry data are stored in a predefined data structure (tree data structure with leaf nodes) in “MEMORY”; para. [0132], “The TTU 700 may request the BVH data structure identified in the query to be retrieved from memory outside of the TTU 700”; para. [0150], “a ray/triangle (or other primitive) intersection 1026 that are each performed by the TTU 700”). Note that: (1) when the ray-geometry (ray-triangle) intersection is determined by TTU 700 with associated triangles (two triangles “01” and “02”), Stack Management Unit 740 as a geometry data loading circuit can determine what data need to be retrieved or loaded for the associated triangles (two triangles “01” and “02”) from memory outside of the TTU 700; and (2) the triangles with the loaded or retrieved triangle geometry data stored in the predefined data structure are used and processed by TTU 700 for ray-triangle intersection test.
wherein the graphics processor is operable to:
when it is determined by the ray-volume intersection testing circuit that a ray intersects a volume represented by an end node of a ray tracing acceleration data structure that is associated with a bounding volume primitive, (Muthler, para. [0070], “Given a BVH, ray tracing amounts to a tree search where each node in the tree visited by the ray has a bounding volume for each descendent branch or leaf, and the ray only visits the descendent branches or leaves whose corresponding bound volume it intersects. In this way, only a small number of primitives must be explicitly tested for intersection, namely those that reside in leaf nodes intersected by the ray. In the example non-limiting embodiments, the traversal coprocessor accelerates both tree traversal (including the ray-volume tests) and ray-primitive tests”). Note that: the traversal coprocessor can determine that a ray intersects a volume associated with a primitive by performing ray-volume test. cause the geometry data loading circuit to load bounding volume geometry data stored for the node, and cause geometry to be processed using the loaded bounding volume geometry data, wherein the bounding volume geometry data is stored using the same predefined data structure as is used to store polygon geometry data. Note that: (1) when the ray-volume intersection is determined by TTU 700 with associated bounding volume primitives, Stack Management Unit 740 can determine what data need to be retrieved or loaded for the associated bounding volume primitives from memory outside of the TTU 700; and (2) the bounding volume primitive with the loaded or retrieved geometry data stored in the predefined data structure are used and processed by TTU 700 for ray-geometry intersection test to determine whether the ray intersects the bounding volume primitive. Practically, when it is determined that a ray intersects a volume represented by a node of the ray tracing acceleration data structure that is associated with a bounding volume primitive, it indicates that the ray intersects the bounding volume primitive; and (3) the nodes and the node corresponding volumes include parent / child nodes covering leaf nodes and corresponding volumes, respectively.
… a bounding volume primitive, (Hughes, para. [0086], “In some examples, the BVH identification unit 1020 is operable to repeat the identification process until a predetermined level of detail is reached. This means that the BVH may be traversed, with intersection determination processing being performed, until one or more predetermined conditions are met regarding when to terminate the traversal. The predetermined level of detail may be different for different parts of the BVH”; para. [0087], “The predetermined level of detail may be a predetermined multiple of the pixel size used in the rasterization process, such as half, one, one and a quarter, one and a half, or two times the size of the pixels (although of course, any suitable value may be selected as appropriate to achieve a desired visual effect or level of performance). In such a case, it is the size of the bounding volume associated with a BVH node that may be compared to the pixel size so as to determine whether the predetermined level of detail has been reached.”). Note that: (1) when a BVH node 1 has two child nodes, node 2 and node 3. The bounding volume represented by node 1 is an AABB primitive denoted by AABB_n1. The two bounding volumes represented by node 2 and node 3 are two AABB primitives denoted by AABB_n2 and AABB_n3, respectively; (2) When it is determined that a ray intersects the bounding volume AABB_n1, if the size of AABB_n1 is below the predetermined level of detail as specified in the citations of Hughes above (e.g., a predetermined multiple of the pixel size used in the rasterization process), the traversal terminates without further testing the ray against AABB_n2 and AABB_n3 which are contained in AABB_n1, saving the ray intersection testing compute. In this case, AABB_n1 can be regarded as a bounding volume primitive whose size is below the predetermined level of detail; and (3) When the traversal stops for AABB_n1, the graphics omits testing the ray against the bounding volume primitive to determine whether the ray intersects the bounding volume primitive including all primitives within it.
,,, wherein the polygon geometry data is stored using a predefined data structure; and … the geometry data is stored using the predefined data structure that is used to store polygon geometry data. (Lehtinen, FIG. 1B: “Compression Block 140” includes or stores includes or stores “Triangle 0 142”, “Triangle 1 144”, “Triangle 2 146”, and “Header 148”; “Header 148” has subfields “MD2 32”, “MD1 2”, “MD0 32”, “α 3”, “Mode 3”, and the x/y/z coordinates or positions of three vertexes of three or more triangles and other information including header using a size of 128-byte block; para. [0030], “each of the three alpha bits may indicate whether a corresponding triangle (e.g., triangle 2, triangle 1, triangle 0) is fully opaque (or, alternatively, partially transparent)”). Note that: (1) Compression Block 140 (the predefined data structure) can be regarded as the predefined data structure that includes the fields 142, 144, 146, and 148; (2) it is obvious to one having ordinary skill that the data structure can be used for a node associated with a bounding volume primitive while there no vertexes of triangles to be filled in, to keep using the same format without having a different data structure for a node associated with a bounding volume primitive; (3) “α 3” in the “Header 148” can be used a same field to store geometry data (i.e., opaque or partially transparent) for a node associated with a bounding volume primitive as used to store corresponding polygon geometry data; and (4) in addition, a same field (e.g., GeomID) as geometry data can be put into the compression block (the predefined data structure) or its header to store the ID information for the bounding volume either including triangles or being a bounding volume primitive.
The motivation to combine Muthler, Hughes, and Lehtinen given in claim 9 is incorporated here.
Allowable Subject Matter
Claims 1-8 and 11-17 are allowed.
The following is an examiner’s statement of reasons for allowance:
The closest prior art, Muthler et al. (US 20210090319 A1, hereinafter “Muthler”), is made of record as teaching “FIG. 1 illustrates an example real time ray interactive tracing graphics system 100 for generating images using three dimensional (3D) data of a scene or object(s)” (para. [0072]), “the example non-limiting technology herein relates to a hardware-based traversal coprocessor that efficiently traverses an acceleration data structure e.g., for real time ray tracing” (para. [0008]), “the acceleration data structure comprises a hierarchy of bounding volumes (bounding volume hierarchy or BVH) that recursively encapsulates smaller and smaller bounding volume subdivisions. The largest volumetric bounding volume may be termed a "root node.” The smallest subdivisions of such hierarchy of bounding volumes ("leaf nodes") contain items. The items could be primitives (e.g., polygons such as triangles) that define surfaces of the object" (para. [0060]), “Given a BVH, ray tracing amounts to a tree search where each node in the tree visited by the ray has a bounding volume for each descendent branch or leaf, and the ray only visits the descendent branches or leaves whose corresponding bound volume it intersects. In this way, only a small number of primitives must be explicitly tested for intersection, namely those that reside in leaf nodes intersected by the ray. In the example non-limiting embodiments, the traversal coprocessor accelerates both tree traversal (including the ray-volume tests) and ray-primitive tests” (para. [0070]), “To determine whether the ray 302 intersects one or more triangles in the mesh 320, each triangle could be directly tested against the ray 302. But to accelerate the process (since the object could contain many thousands of triangles), the ray 302 is first tested against the bounding volumes 310 and 315.” (para. [0095]), “Given a BVH, ray tracing amounts to a tree search where each node in the tree visited by the ray has a bounding volume for each descendent branch or leaf, and the ray only visits the descendent branches or leaves whose corresponding bound volume it intersects. In this way, only a small number of primitives must be explicitly tested for intersection, namely those that reside in leaf nodes intersected by the ray. In the example non-limiting embodiments, the traversal coprocessor accelerates both tree traversal (including the ray-volume tests) and ray-primitive tests” (para. [0070]), “The traversal coprocessor 138 determines which bounding volumes of a BVH data structure the ray intersects (the "ray-complet" test 512) and subsequently whether the ray intersects one or more primitives in the intersected bounding volumes and which triangles are intersected (the "ray-primitive test" 520)” (para. [0099]), and “A Stack Management Unit 740 inspects the traversal state to determine what type of data needs to be retrieved and which data path (complet or primitive) will consume it …The ray-complet test path of the TTU 700 identifies which bounding volumes are intersected by the ray … The intersections for the primitives are determined in the ray-primitive test path including one or more ray-primitive test and transform blocks 720 and one or more intersection management blocks 722” (para. [0130]), “a ray/triangle (or other primitive) intersection 1026 that are each performed by the TTU 700” (para. [0150]).
Hughes (US 2021/0295598 A1, hereinafter “Hughes”) is made of record as teaching “In some examples, the BVH identification unit 1020 is operable to repeat the identification process until a predetermined level of detail is reached. This means that the BVH may be traversed, with intersection determination processing being performed, until one or more predetermined conditions are met regarding when to terminate the traversal. The predetermined level of detail may be different for different parts of the BVH” (para. [0086]), “The predetermined level of detail may be a predetermined multiple of the pixel size used in the rasterization process, such as half, one, one and a quarter, one and a half, or two times the size of the pixels (although of course, any suitable value may be selected as appropriate to achieve a desired visual effect or level of performance). In such a case, it is the size of the bounding volume associated with a BVH node that may be compared to the pixel size so as to determine whether the predetermined level of detail has been reached.” (para. [0087]).
Lehtinen et al. (US 20160071234 A1, hereinafter “Lehtinen”) is made of record as teaching FIG. 1B: “Compression Block 140” includes or stores includes or stores “Triangle 0 142”, “Triangle 1 144”, “Triangle 2 146”, and “Header 148”; “Header 148” has subfields “MD2 32”, “MD1 2”, “MD0 32”, “α 3”, “Mode 3”, and the x/y/z coordinates or positions of three vertexes of three or more triangles and other information including header using a size of 128-byte block, and “each of the three alpha bits may indicate whether a corresponding triangle (e.g., triangle 2, triangle 1, triangle 0) is fully opaque (or, alternatively, partially transparent)” (para. [0030]).
However, the cited prior art either alone or in combination does not disclose or render obvious omitting testing a ray against the bounding volume primitive when a ray intersects a volume represented by an end node of the ray tracing acceleration data structure that is associated with a bounding volume primitive. Specially, the cited prior art fails to disclose or render obvious the corresponding limitations: “when it is determined that a ray intersects a volume represented by an end node of the ray tracing acceleration data structure that is associated with a bounding volume primitive, omitting testing the ray against the bounding volume primitive to determine whether the ray intersects the bounding volume primitive.”, as recited in independent claim 1.
Dependent claims 2-8 and 19 depend from independent claim 1. They are allowed at least due to their respective dependencies from an allowed claim.
And the cited prior art either alone or in combination does not disclose or render obvious omitting testing a ray against the bounding volume primitive when a ray intersects a volume represented by an end node of the ray tracing acceleration data structure that is associated with a bounding volume primitive. Specially, the cited prior art fails to disclose or render obvious the corresponding limitations: “when it is determined by the ray-volume intersection testing circuit that a ray intersects a volume represented by an end node of a ray tracing acceleration data structure that is associated with a bounding volume primitive, omit testing the ray against the bounding volume primitive to determine whether the ray intersects the bounding volume primitive.”, as recited in independent claim 11.
Dependent claims 12 -17 depend from independent claim 11. They are allowed at least due to their respective dependencies from an allowed claim.
Any comments considered necessary by applicant must be submitted no later than the payment of the issue fee and, to avoid processing delays, should preferably accompany the issue fee. Such submissions should be clearly labeled “Comments on Statement of Reasons for Allowance.”
Response to Arguments
Applicant's arguments with respect to claim rejection 35 U.S.C. 103, have been fully considered but they are not persuasive.
Applicant alleges, “Thus, the combined teachings of Hughes, Muthler and Lehtinen, do not render the claimed subject matter obvious as there is no teaching or suggestion in the references to lead one of average skill to provide a feature calling for storing, for each end node of the ray tracing acceleration data structure that is associated with a bounding volume primitive, bounding volume geometry data using the same predefined data structure as is used to store polygon geometry data, as now claimed in claim 9. Further, there is no teaching of an arrangement in which ‘... bounding volume geometry data is stored using the same predefined data structure as is used to store polygon geometry data’ as defined in claim 18.” (page 14, lines 10-17). However, Examiner respectfully disagrees about the respective allegations as whole because: (1) the combination of Hughes, Muthler and Lehtinen instead of the single reference of them does discloses an end node of the ray tracing acceleration data
structure that is associated with a bounding volume primitive and bounding volume geometry data; and (2) the specific reference and citations are used for the rejection with corresponding rationale in details above. The arguments are not persuasive.
Applicant alleges, “It is therefore respectfully requested that the rejection of claims 9 and 18, and 10 dependent from claim 9 respectively, under 35 U.S.C. §103 be withdrawn.” (page 14, lines 18-19). However, Examiner respectfully disagrees about the respective allegations as whole because: (1) claims 9, 10, and 18 are rejected for the respective rationale above; (2) claim 10 is actually an independent claim corresponding to claim 9. The arguments are not persuasive.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to BIAO CHEN whose telephone number is (703)756-1199. The examiner can normally be reached M-F 8am-5pm ET.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Kee M Tung can be reached at (571)272-7794. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/Biao Chen/
Patent Examiner, Art Unit 2611
/KEE M TUNG/Supervisory Patent Examiner, Art Unit 2611