DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application is being examined under the pre-AIA first to invent provisions.
Priority
This application is a continuation of US Application No. 18/102,054, filed 01/26/2023, which is a continuation of US Application No. 17/167,810, filed 02/04/2021, which is a continuation of US Application No. 15/985,312, filed 05/21/2018, which is a divisional Application No. 14/440,021, filed 04/30/2015, which is benefits a priority of PCT/IB2013/002935 filed 11/01/2013, which claims benefits of Provisional Applications of No. 61/897,701, filed 10/30/2013, 61/798,786, filed 03/15/2013, 61/722,109, filed 11/02/2012.
Information Disclosure Statement
The information disclosure statement (IDS) submitted is considered by the examiner.
Claim Rejections - 35 USC § 103
The following is a quotation of pre-AIA 35 U.S.C. 103(a) which forms the basis for all obviousness rejections set forth in this Office action:
(a) A patent may not be obtained though the invention is not identically disclosed or described as set forth in section 102, if the differences between the subject matter sought to be patented and the prior art are such that the subject matter as a whole would have been obvious at the time the invention was made to a person having ordinary skill in the art to which said subject matter pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim 1-3, 5, 7-8, 14, 16-18, 20 is/are rejected under pre-AIA 35 U.S.C. 103(a) as being unpatentable over Frascati et al. (US Publication Number 2014/0267259 A1, hereinafter “Frascati”) in view of Boubekeur et al. (NPL, “A Flexible Kernel for Adaptive Mesh Refinement on GPU”, 2008).
(1) regarding claim 1:
As shown in fig. 3, Frascati disclosed a machine-implemented method for use in 3-D rendering (para. [0013], note that FIG. 3 is a conceptual diagram illustrating an example render target that is subdivided into sub-regions and a plurality of primitives displayed on the subdivided render target), comprising:
accessing, by a processor, geometry data describing geometry located in a 3D scene from which a rendering is to be produced, the geometry data describing geometry control points that define one or more surfaces of the geometry (para. [0041], note that the graphics application may execute on a host processor that is communicatively coupled to the GPU. Certain types of graphics applications (e.g., 3D gaming applications) may use bounding regions for various objects to execute collision detection algorithms);
in dependence on the geometry control points, deriving tessellated geometry by tessellating at least some of the geometry described by the geometry data (para. [0061], note that computing device 2 (e.g., CPU 6 and/or GPU 12) may be configured to perform tile-based rendering for one or more graphics primitives based on a bounding region that encompasses the one or more graphics primitives and based on data that is generated by at least one tessellation processing stage of an on-chip);
producing, by a processor, in dependence on at least the tessellated geometry, geometry extents data that establishes an association between a volume defined in the 3-D scene and a selection of the geometry control points (para. [0268], note that the one or more primitives to be rendered as part of a draw call may include two or more primitives to be rendered, and the bounding region may correspond to a bounding volume that encompasses the two or more primitives).
Frascati disclosed most of the subject matter as described as above except for specifically teaching wherein the selection of geometry control points defines geometry to be used to produce final geometry that is within the defined volume on which rendering will be based; and storing the geometry extents data.
However, Boubekeur disclosed wherein the selection of geometry control points defines geometry to be used to produce final geometry that is within the defined volume on which rendering will be based; and storing the geometry extents data (page 3, para. [0003], note that the vertex program simultaneously interpolates the vertices of the current coarse polygon, and the displacement function, by using the barycentric coordinates stored at each node of the ARP. The first interpolation generates the position of the node on the polygon (i.e. tessellation step) and the second one trans-lates it to its final position (i.e. displacement step). Also see fig. 4, Principle of Uniform Refinement Patterns. (a)Coarse mesh stored on CPU. (b) Uniform Refinement Pat-tern (URP) stored as a vertex buffer object on GPU, where each node is stored as barycentric coordinates. (c) Final re-fined mesh rendered on screen).
At the time of filing for the invention, it would have been obvious to a person of ordinary skilled in the art to teach wherein the selection of geometry control points defines geometry to be used to produce final geometry that is within the defined volume on which rendering will be based; and storing the geometry extents data. The suggestion/motivation for doing so would have been in order to provide a flexible GPU kernel for adaptive on-the-fly refinement of meshes with arbitrary topology (abs.). Therefore, it would have been obvious to combine Frascati with Boubekeur to obtain the invention as specified in claim 1.
(2) regarding claim 2:
Frascati further disclosed the machine-implemented method for use in 3-D rendering of claim 1, wherein deriving tessellated geometry by tessellating at least some of the geometry comprises deriving a plurality of primitives from a surface described by the geometry data (para. [0042], note that in response to receiving a draw call instruction that instructs the GPU to render a higher-order surface (e.g., a Bezier surface), the graphics driver and/or the GPU may generate a convex hull that encompasses the higher-order surface based on the control points for the surface).
(3) regarding claim 3:
Frascati further disclosed the machine-implemented method for use in 3-D rendering of claim 1, wherein deriving tessellated geometry comprises tessellating a plurality of primitives derived from the surface described by the geometry data to obtain a plurality of tessellated primitives (para. [0042], note that in response to receiving a draw call instruction that instructs the GPU to render one or more primitives, the graphics driver and/or the GPU may generate a bounding region for the primitives to be rendered based on positional coordinates associated with the vertices of the primitives to be rendered).
(4) regarding claim 5:
Frascati further disclosed the machine-implemented method for use in 3-D rendering of claim 1, wherein deriving tessellated geometry by tessellating at least some of the geometry comprises: calculating tessellation factors in dependence on a surface described by the geometry data (para. [0225], note that tessellation stages 92 may generate a plurality of tessellated primitives that collectively represent an input primitive. In cases where the input primitive is a higher-order surface (e.g., a patch, a Bezier surfaces, a subdivision surfaces, etc.), tessellation stages 92 may tessellate the higher-order surface into a plurality of lower-order primitives (e.g., points, lines, triangles)); using the geometry control points and the tessellation factors to derive the tessellated geometry comprising a plurality of tessellated primitives (para. [0225], note that the higher-order surfaces may be curved surfaces, and the lower-order primitives may have non-curved surfaces and non-curved edges. Each higher order surface may be defined based on one or more control points in a control point patch list and one or both of a hull shader program and a domain shader program that are used to tessellate the surface).
(5) regarding claim 7:
Frascati further disclosed the machine-implemented method for use in 3-D rendering of claim 1, further comprising using hint data to define the volumes in the 3-D scene that are referenced in the geometry extent data (para. [0065], note that a primitive or a bounding region may, in some examples, refer to a version of a geometrically-defined primitive or a geometrically-defined bounding region that is sampled at regularly-spaced sampling locations or pixels).
(6) regarding claim 8:
Frascati disclosed most of the subject matter as described as above except for specifically teaching associating procedural modifications with geometry extents data that are required to produce the final geometry within a volume of the 3-D scene to which the geometry extents data pertains.
However, Boubekeur disclosed associating procedural modifications with geometry extents data that are required to produce the final geometry within a volume of the 3-D scene to which the geometry extents data pertains (see fig. 9, Displaced Adaptive PN Triangles, generated on the fly in real-time by our GPU Kernel (3.6 M polygons). This final rendering (58FPS) includes the use of displacement map with our kernel on the vertex shader, as well as normal, color and shadow maps on the fragment shader).
At the time of filing for the invention, it would have been obvious to a person of ordinary skilled in the art to teach associating procedural modifications with geometry extents data that are required to produce the final geometry within a volume of the 3-D scene to which the geometry extents data pertains. The suggestion/motivation for doing so would have been in order to provide a flexible GPU kernel for adaptive on-the-fly refinement of meshes with arbitrary topology (abs.). Therefore, it would have been obvious to combine Frascati with Boubekeur to obtain the invention as specified in claim 8.
(7) regarding claim 14:
Frascati further disclosed the machine-implemented method for use in 3-D rendering of claim 1, wherein the accessing and producing are performed in a pre-pass over source geometry data, the source geometry data comprising vertex data and two or more sets of vertex connectivity data (para. [0032], note that during each of the rendering passes, all of the image data associated with the corresponding sub-region may be rendered, which may include rendering each of the primitives that contributes pixel data to the sub-region).
(8) regarding claim 16:
Frascati disclosed most of the subject matter as described as above except for specifically teaching wherein the producing of the geometry extents data comprises producing a hint indicating an amount of geometry expansion to be expected when producing final geometry for the volume defined in the 3-D scene that is associated with that portion of geometry extents data.
However, Boubekeur disclosed wherein the producing of the geometry extents data comprises producing a hint indicating an amount of geometry expansion to be expected when producing final geometry for the volume defined in the 3-D scene that is associated with that portion of geometry extents data (page 8, 4.4 Adaptive terrain rendering, at rendering time, we tag the vertices of the coarse ground using a view-dependent distance metric. Finally, the coarse ground is adaptively tessellated on-the-fly by the ARK and displaced using vertex texture fetch from the height-field texture).
At the time of filing for the invention, it would have been obvious to a person of ordinary skilled in the art to teach wherein the producing of the geometry extents data comprises producing a hint indicating an amount of geometry expansion to be expected when producing final geometry for the volume defined in the 3-D scene that is associated with that portion of geometry extents data. The suggestion/motivation for doing so would have been in order to provide a flexible GPU kernel for adaptive on-the-fly refinement of meshes with arbitrary topology (abs.). Therefore, it would have been obvious to combine Frascati with Boubekeur to obtain the invention as specified in claim 16.
(9) regarding claim 17:
Frascati disclosed most of the subject matter as described as above except for specifically teaching wherein accessing comprises: accessing a hint that is associated with a control point, which indicates a bound on an amount of geometry that may result when performing procedural modification using that control point, to produce final geometry.
However, Boubekeur disclosed wherein accessing comprises: accessing a hint that is associated with a control point, which indicates a bound on an amount of geometry that may result when performing procedural modification using that control point, to produce final geometry (see fig. 11, page 8, note that This terrain has been rendered at an average frame rate of 44 FPS (6M tri.), by using a single height-map texture to displace the refined tessellation. The refinement is driven by a view-dependent depth-tagging. Top: Topology for input ground, uniform and adaptive on-the-fly refinement with the ARK. Bottom: Final adaptive real-time rendering).
At the time of filing for the invention, it would have been obvious to a person of ordinary skilled in the art to teach wherein accessing comprises: accessing a hint that is associated with a control point, which indicates a bound on an amount of geometry that may result when performing procedural modification using that control point, to produce final geometry. The suggestion/motivation for doing so would have been in order to provide a flexible GPU kernel for adaptive on-the-fly refinement of meshes with arbitrary topology (abs.). Therefore, it would have been obvious to combine Frascati with Boubekeur to obtain the invention as specified in claim 17.
The proposed rejection of claim 1 renders obvious the steps of the system (see fig. 1) of claim 18 and the non-transitory computer readable storage medium claim 20 because these steps occur in the operation of the proposed rejection as discussed above. Thus, the arguments similar to that presented above for claim 1 is equally applicable to claims 18 and 20.
Claim 4, 6, 12 and 15 is/are rejected under pre-AIA 35 U.S.C. 103(a) as being unpatentable over Frascati and Boubekeur, and further in view of Thrane et al. (NPL, “A Comparison of Acceleration Structures for GPU Assisted Ray Tracing, 2005”).
(1) regarding claim 4:
Frascati disclosed most of the subject matter as described as above except for specifically teaching defining rays to be traced in the 3-D scene by identifying a volume in the 3-D space in which a subset of the rays is to be tested for intersection; using the geometry extents data to identify geometry control points; obtaining final geometry for those identified geometry control points, the obtaining at least comprising deriving tessellated geometry by tessellating geometry defined by the identified geometry control points; testing the final geometry for intersection with the subset of the rays.
However, Thrane disclosed defining rays to be traced in the 3-D scene by identifying a volume in the 3-D space in which a subset of the rays is to be tested for intersection (page 29, Intersection testing, para. [0001], note that the traversal/intersection kernel takes as input ray origins and directions along with a representation of the scene); using the geometry extents data to identify geometry control points (page 29, Intersection testing, para. [0001], note that we report the three barycentric coordinates of the intersection, relative to the intersected triangle); obtaining final geometry for those identified geometry control points, the obtaining at least comprising deriving tessellated geometry by tessellating geometry defined by the identified geometry control points (page 65, para. [0001], note that this scene allows us to test how well our acceleration structures behaves in conditions where there are small, highly tessellated objects in a large scene); testing the final geometry for intersection with the subset of the rays (page 29, Intersection testing, para. [0001], note that the traversal/intersection kernel takes as input ray origins and directions along with a representation of the scene. The exact representation and method of traversal is the topic of the following sections. After an appropriate number of kernel invocations, we output a hit record for each pixel. If a ray yielded an intersection, we report the three barycentric coordinates of the intersection, relative to the intersected triangle).
At the time of filing for the invention, it would have been obvious to a person of ordinary skilled in the art to teach defining rays to be traced in the 3-D scene by identifying a volume in the 3-D space in which a subset of the rays is to be tested for intersection; using the geometry extents data to identify geometry control points; obtaining final geometry for those identified geometry control points, the obtaining at least comprising deriving tessellated geometry by tessellating geometry defined by the identified geometry control points; testing the final geometry for intersection with the subset of the rays. The suggestion/motivation for doing so would have been in order to provide simplest to implement and most memory efficient GPU (abs.). Therefore, it would have been obvious to combine Frascati, Boubekeur with Thrane to obtain the invention as specified in claim 4.
(2) regarding claim 6:
Frascati disclosed most of the subject matter as described as above except for specifically teaching further comprising producing an acceleration structure comprising elements bounding respective portions of the 3-D scene, and using the acceleration structure to identify respective subsets of the final geometry to be tested for intersection with different rays.
However, Thrane disclosed producing an acceleration structure comprising elements bounding respective portions of the 3-D scene, and using the acceleration structure to identify respective subsets of the final geometry to be tested for intersection with different rays (page 33, Acceleration Structure review, note that introducing the bounding volume hierarchy (BVH) – the ultimate goal is to find good acceleration structures for ray tracing on the GPU, we will include discussions of GPU applicability for each of the structures).
At the time of filing for the invention, it would have been obvious to a person of ordinary skilled in the art to teach producing an acceleration structure comprising elements bounding respective portions of the 3-D scene, and using the acceleration structure to identify respective subsets of the final geometry to be tested for intersection with different rays. The suggestion/motivation for doing so would have been in order to provide simplest to implement and most memory efficient GPU (abs.). Therefore, it would have been obvious to combine Frascati, Boubekeur with Thrane to obtain the invention as specified in claim 6.
(3) regarding claim 12:
Frascati disclosed most of the subject matter as described as above except for specifically teaching producing a coarse acceleration structure with leaf elements and using leaf elements of the coarse acceleration structure as the geometry extents data.
However, Thrane disclosed producing a coarse acceleration structure with leaf elements and using leaf elements of the coarse acceleration structure as the geometry extents data (page, 34, 5.1 a note on octrees, para. [0002], note that Glassner advances a point along the ray and locates the leaf voxel that contains it by searching down the octree, starting from the root. In each octree node he then locates the sub-node by comparing the point against the three split planes that partition the node)
At the time of filing for the invention, it would have been obvious to a person of ordinary skilled in the art to teach producing a coarse acceleration structure with leaf elements and using leaf elements of the coarse acceleration structure as the geometry extents data. The suggestion/motivation for doing so would have been in order to provide simplest to implement and most memory efficient GPU (abs.). Therefore, it would have been obvious to combine Frascati, Boubekeur with Thrane to obtain the invention as specified in claim 12.
(4) regarding claim 15:
Frascati disclosed most of the subject matter as described as above except for specifically teaching wherein the tessellating at least some of the geometry described by the geometry data comprises tessellation to be used for producing finalized geometry for ray tracing and tessellation to be used for producing finalized geometry for rasterization.
However, Thrane disclosed wherein the tessellating at least some of the geometry described by the geometry data comprises tessellation to be used for producing finalized geometry for ray tracing and tessellation to be used for producing finalized geometry for rasterization (page 65, Robots: 71708 triangles, para. [0001], note that this scene allows us to test how well our acceleration structures behaves in conditions where there are small, highly tessellated objects in a large scene. This is sometimes referred to as the “teapot in a stadium problem”. A rendering of the robot scene can be seen in figure 24 (b)).
At the time of filing for the invention, it would have been obvious to a person of ordinary skilled in the art to teach wherein the tessellating at least some of the geometry described by the geometry data comprises tessellation to be used for producing finalized geometry for ray tracing and tessellation to be used for producing finalized geometry for rasterization. The suggestion/motivation for doing so would have been in order to provide simplest to implement and most memory efficient GPU (abs.). Therefore, it would have been obvious to combine Frascati, Boubekeur with Thrane to obtain the invention as specified in claim 15.
Allowable Subject Matter
Claim 9-11, 13 and 19 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims. The following is a statement of reasons for the indication of allowable subject matter: the prior arts made of record do not teach “making a rendering using both a rasterization subsystem and a ray tracing subsystem that each make requests for portions of final geometry, and responsive to the requests, producing the final geometry by performing tessellation and the procedural modifications associated with the geometry extents data associated with volumes of the 3-D scene bounding the requested portions of final geometry”, as recited in claim 9 and 19. Claims 10-11 and 13 depend on claim 9.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Liu et al. (NPL, “A Micro 64-Tree Structure for Accelerating Ray Tracing on a GPU”, 2013) disclosed a novel micro-64-tree structure to speed up grid traversals on a GPU. A micro-64-tree is a compact 64-way full tree that summarizes the occupancy of an underlying uniform grid in a hierarchy.
Any inquiry concerning this communication or earlier communication from the examiner should be directed to Hilina K Demeter whose telephone number is (571) 270-1676.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, King Y. Poon could be reached at (571) 270- 0728. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about PAIR system, see http://pari-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/HILINA K DEMETER/Primary Examiner, Art Unit 2617
Prosecution Insights