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 .
Specification
The disclosure is objected to because of the following informalities: In page 7 line 5, “FIG. 24 is a view” should read “FIG. 25 is a view”.
Appropriate correction is required.
The use of the terms “Nvidia OptiX” and “GeForce RTX”, which are trade names or marks used in commerce, has been noted in this application. The term should be accompanied by the generic terminology; furthermore the term should be capitalized wherever it appears or, where appropriate, include a proper symbol indicating use in commerce such as ™, SM , or ® following the term. Although the use of trade names and marks used in commerce (i.e., trademarks, service marks, certification marks, and collective marks) are permissible in patent applications, the proprietary nature of the marks should be respected and every effort made to prevent their use in any manner which might adversely affect their validity as commercial marks.
The abstract of the disclosure is objected to because it exceeds 150 words. A corrected abstract of the disclosure is required and must be presented on a separate sheet, apart from any other text. See MPEP § 608.01(b).
Claim Objections
Claims 1 and 4-8 are objected to because of the following informalities:
In claim 1 line 12, the acronym “CSG” should be defined.
Claims 4-8 are objected to under 37 CFR 1.75(c) as being in improper form because a multiple dependent claim cannot depend from any other multiple dependent claims. See MPEP § 608.01(n). For the sake of examination, claims 4-8 are all interpreted to be dependent on claim 1.
In claim 6 line 4, “a same” should read “the same”.
Appropriate correction is required.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are: “primitive generation unit” and “representation processing unit” in claim 1, and “construction line generation unit” in claim 8.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof. The corresponding structure is disclosed in paragraphs 0038-0039 in the specification.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Double Patenting
A rejection based on double patenting of the “same invention” type finds its support in the language of 35 U.S.C. 101 which states that “whoever invents or discovers any new and useful process... may obtain a patent therefor...” (Emphasis added). Thus, the term “same invention,” in this context, means an invention drawn to identical subject matter. See Miller v. Eagle Mfg. Co., 151 U.S. 186 (1894); In re Vogel, 422 F.2d 438, 164 USPQ 619 (CCPA 1970); In re Ockert, 245 F.2d 467, 114 USPQ 330 (CCPA 1957).
The nonstatutory double patenting rejection is based on a judicially created doctrine grounded in public policy (a policy reflected in the statute) so as to prevent the unjustified or improper timewise extension of the “right to exclude” granted by a patent and to prevent possible harassment by multiple assignees. A nonstatutory double patenting rejection is appropriate where the conflicting claims are not identical, but at least one examined application claim is not patentably distinct from the reference claim(s) because the examined application claim is either anticipated by, or would have been obvious over, the reference claim(s). See, e.g., In re Berg, 140 F.3d 1428, 46 USPQ2d 1226 (Fed. Cir. 1998); In re Goodman, 11 F.3d 1046, 29 USPQ2d 2010 (Fed. Cir. 1993); In re Longi, 759 F.2d 887, 225 USPQ 645 (Fed. Cir. 1985); In re Van Ornum, 686 F.2d 937, 214 USPQ 761 (CCPA 1982); In re Vogel, 422 F.2d 438, 164 USPQ 619 (CCPA 1970); In re Thorington, 418 F.2d 528, 163 USPQ 644 (CCPA 1969).
A timely filed terminal disclaimer in compliance with 37 CFR 1.321(c) or 1.321(d) may be used to overcome an actual or provisional rejection based on nonstatutory double patenting provided the reference application or patent either is shown to be commonly owned with the examined application, or claims an invention made as a result of activities undertaken within the scope of a joint research agreement. See MPEP § 717.02 for applications subject to examination under the first inventor to file provisions of the AIA as explained in MPEP § 2159. See MPEP § 2146 et seq. for applications not subject to examination under the first inventor to file provisions of the AIA . A terminal disclaimer must be signed in compliance with 37 CFR 1.321(b).
The filing of a terminal disclaimer by itself is not a complete reply to a nonstatutory double patenting (NSDP) rejection. A complete reply requires that the terminal disclaimer be accompanied by a reply requesting reconsideration of the prior Office action. Even where the NSDP rejection is provisional the reply must be complete. See MPEP § 804, subsection I.B.1. For a reply to a non-final Office action, see 37 CFR 1.111(a). For a reply to final Office action, see 37 CFR 1.113(c). A request for reconsideration while not provided for in 37 CFR 1.113(c) may be filed after final for consideration. See MPEP §§ 706.07(e) and 714.13.
The USPTO Internet website contains terminal disclaimer forms which may be used. Please visit www.uspto.gov/patent/patents-forms. The actual filing date of the application in which the form is filed determines what form (e.g., PTO/SB/25, PTO/SB/26, PTO/AIA /25, or PTO/AIA /26) should be used. A web-based eTerminal Disclaimer may be filled out completely online using web-screens. An eTerminal Disclaimer that meets all requirements is auto-processed and approved immediately upon submission. For more information about eTerminal Disclaimers, refer to www.uspto.gov/patents/apply/applying-online/eterminal-disclaimer.
Claims 1-5, 7, and 9-10 are provisionally rejected on the ground of nonstatutory double patenting as being unpatentable over claims 1-2 and 8-13 of copending Application No. 18/726,942 in view of Romeiro et al. (Hardware-assisted Rendering of CSG Models). See table below.
This is a provisional nonstatutory double patenting rejection because the patentably indistinct claims have not in fact been patented.
Instant Application (18/705,938)
Co-Pending Application (18/726,942)
A three-dimensional CAD system comprising:
___________________________________
a primitive generation unit that uses a differential polyhedron model which is a set of differential polyhedrons including coordinate values of triangle vertices, normal vectors of the triangle vertices, and curved line elements including start/end points consisting of the triangle vertices and tangent vectors at the start/end points to form a curved surface by connecting sides of the differential polyhedron and form a closed surface by connecting curved surfaces with a curved surface boundary line, thereby generating a primitive which is a set of points belonging to the inside of the closed surface;
___________________________________
and a storage unit that stores CSG data which represents a solid model in CSG representation by a tree structure of set operations of the primitives;
___________________________________
and a representation processing unit that determines an intersection point between the solid model and a straight line from the intersection point between the closed surface of the primitive and the straight line by a set operation based on the CSG data,
___________________________________
thereby calculating a reflection position and a reflection direction of a light ray in the solid model.
A three-dimensional CAD/CAM system comprising:
___________________________________
a primitive generation unit that uses a differential polyhedron model which is a set of differential polyhedrons including coordinate values of triangle vertices, normal vectors of the triangle vertices, and curved line elements including start/end points consisting of the triangle vertices and tangent vectors at the start/end points to form a curved surface by connecting sides of the differential polyhedron and form a closed surface by connecting curved surfaces with a curved surface boundary line, thereby generating a primitive which is a set of points belonging to the inside of the closed surface;
___________________________________
a storage unit that stores CSG data which represents a solid model in CSG representation by a tree structure of set operations of the primitives;
___________________________________
a dexel generation unit that determines an intersection point between the solid model and a straight line from the intersection point between the closed surface of the primitive and the straight line by a set operation based on the CSG data,
___________________________________
Claim 1 of 18/705,938 recites calculating a reflection position and a reflection direction of a light ray in the solid model.
Claim 1 of 18/726,942 lacks calculating a reflection position and a reflection direction of a light ray in the solid model.
Romeiro discloses calculating a reflection position and a reflection direction of a light ray in the solid model (Paragraph 2 in 1st Col. of Page 4 – “The pixel shader receives this information, as well as parameters containing information on the primitives in question (depending on primitive: center, radius, etc), calculates the ray direction, traces the ray starting from the point at the bounding box corresponding to the pixel in question, and calculates the closest (to the camera) intersection with the primitive, as well as the primitive normal at that intersection. It then computes the color and the correct depth of the pixel”; Note: the ray position and direction are equivalent to the reflection position and direction of a light ray respectively). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the dexel generation unit recited in claim 1 of 18/726,942 to calculate a reflection position and a reflection direction of a light ray in the solid model because the reflection information allows for determining the lighting and color of the model, which then helps produce an accurate and realistic rendering of the model.
wherein the primitive generation unit generates the differential polyhedron by adding, on the basis of the coordinate values of the triangle vertices and the normal vectors of the triangle vertices, curved line elements including start/end points consisting of the triangle vertices and tangent vectors at the start/end points.
wherein the primitive generation unit generates the differential polyhedron by adding, on the basis of the coordinate values of the triangle vertices and the normal vectors of the triangle vertices, curved line elements including start/end points consisting of the triangle vertices and tangent vectors at the start/end points.
wherein the primitive generation unit generates a spatial geodesic by using coordinate values of triangle vertices shared by adjacent first and second differential polyhedrons and normal vectors of the triangle vertices to construct a connection relation by sharing the spatial geodesic, thereby forming a curved surface.
wherein the primitive generation unit generates a spatial geodesic by using coordinate values of triangle vertices shared by adjacent first and second differential polyhedrons and normal vectors of the triangle vertices to construct a connection relation by sharing the spatial geodesic, thereby forming a curved surface.
wherein the primitive generation unit constructs a connection relation between the curved surfaces by using a curved line element shared between the curved surfaces, thereby forming a closed surface connecting the curved surfaces.
wherein the primitive generation unit constructs a connection relation between the curved surfaces by using a curved line element shared between the curved surfaces, thereby forming a closed surface connecting the curved surfaces.
wherein the curved line element composed of tangent vectors at the start/end points is represented by a cubic polynomial curve shown by Formula 1.
PNG
media_image1.png
81
607
media_image1.png
Greyscale
wherein the curved line element composed of tangent vectors at the start/end points is represented by a cubic polynomial curve shown by Formula 1.
PNG
media_image1.png
81
607
media_image1.png
Greyscale
wherein the representation processing unit uses real-time ray tracing to determine an intersection point between the solid model and the light ray.
wherein the dexel generation unit uses real-time ray tracing to determine an intersection point between the solid model and a straight line.
___________________________________
Claim 7 of 18/705,938 recites determining an intersection point between the solid model and the light ray.
Claim 2 of 18/726,942 lacks the light ray.
Romeiro discloses determining an intersection point between the solid model and the light ray (Paragraph 2 in 1st Col. of Page 4 – “The pixel shader receives this information, as well as parameters containing information on the primitives in question (depending on primitive: center, radius, etc), calculates the ray direction, traces the ray starting from the point at the bounding box corresponding to the pixel in question, and calculates the closest (to the camera) intersection with the primitive, as well as the primitive normal at that intersection. It then computes the color and the correct depth of the pixel”; Note: the ray is a straight line that intersects primitives of the model). A person of ordinary skill in the art before the effective filing date of the claimed invention would have recognized that the straight line of 18/726,942 could have been substituted for the light ray of 18/705,938 because both the straight line and light ray serve the purpose of intersecting the solid model. Furthermore, a person of ordinary skill in the art would have been able to carry out the substitution. Finally, the substitution achieves the predictable result of determining an intersection point. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to substitute the straight line of 18/726,942 for the light ray of 18/705,938 according to known methods to yield the predictable result of determining an intersection point.
A three-dimensional CAD method including:
___________________________________
a primitive generation step of using a differential polyhedron model which is a set of differential polyhedrons including coordinate values of triangle vertices, normal vectors of the triangle vertices, and curved line elements including start/end points consisting of the triangle vertices and tangent vectors at the start/end points to form a curved surface by connecting sides of the differential polyhedron and form a closed surface by connecting curved surfaces with a curved surface boundary line, thereby generating a primitive which is a set of points belonging to the inside of the closed surface;
___________________________________
a storage step of storing CSG data which represents a solid model in CSG representation by a tree structure of set operations of the primitives;
___________________________________
and a representation processing step of determining an intersection point between the solid model and a straight line from the intersection point between the closed surface of the primitive and the straight line by a set operation based on the CSG data,
___________________________________
thereby calculating a reflection position and a reflection direction of a light ray in the solid model.
A three-dimensional CAD/CAM method including:
___________________________________
a primitive generation step of using a differential polyhedron model which is a set of differential polyhedrons including coordinate values of triangle vertices, normal vectors of the triangle vertices, and curved line elements including start/end points consisting of the triangle vertices and tangent vectors at the start/end points to form a curved surface by connecting sides of the differential polyhedron and form a closed surface by connecting curved surfaces with a curved surface boundary line, thereby generating a primitive which is a set of points belonging to the inside of the closed surface;
___________________________________
a storage step of storing CSG data which represents a solid model in CSG representation by a tree structure of set operations of the primitives;
___________________________________
a dexel generation step of determining an intersection point between the solid model and a straight line from the intersection point between the closed surface of the primitive and the straight line by a set operation based on the CSG data,
___________________________________
Claim 9 of 18/705,938 recites calculating a reflection position and a reflection direction of a light ray in the solid model.
Claim 12 of 18/726,942 lacks calculating a reflection position and a reflection direction of a light ray in the solid model.
Romeiro discloses calculating a reflection position and a reflection direction of a light ray in the solid model (Paragraph 2 in 1st Col. of Page 4 – “The pixel shader receives this information, as well as parameters containing information on the primitives in question (depending on primitive: center, radius, etc), calculates the ray direction, traces the ray starting from the point at the bounding box corresponding to the pixel in question, and calculates the closest (to the camera) intersection with the primitive, as well as the primitive normal at that intersection. It then computes the color and the correct depth of the pixel”; Note: the ray position and direction are equivalent to the reflection position and direction of a light ray respectively). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the dexel generation unit recited in claim 12 of 18/726,942 to calculate a reflection position and a reflection direction of a light ray in the solid model because the reflection information allows for determining the lighting and color of the model, which then helps produce an accurate and realistic rendering of the model.
A three-dimensional CAD program that causes a computer to execute:
___________________________________
a primitive generation step of using a differential polyhedron model which is a set of differential polyhedrons including coordinate values of triangle vertices, normal vectors of the triangle vertices, and curved line elements including start/end points consisting of the triangle vertices and tangent vectors at the start/end points to form a curved surface by connecting sides of the differential polyhedron and form a closed surface by connecting curved surfaces with a curved surface boundary line, thereby generating a primitive which is a set of points belonging to the inside of the closed surface;
___________________________________
a storage step of storing CSG data which represents a solid model in CSG representation by a tree structure of set operations of the primitives;
___________________________________
and a representation processing step of determining an intersection point between the solid model and a straight line from the intersection point between the closed surface of the primitive and the straight line by a set operation based on the CSG data,
___________________________________
thereby calculating a reflection position and a reflection direction of a light ray in the solid model.
A three-dimensional CAD/CAM program that causes a computer to execute:
___________________________________
a primitive generation step of using a differential polyhedron model which is a set of differential polyhedrons including coordinate values of triangle vertices, normal vectors of the triangle vertices, and curved line elements including start/end points consisting of the triangle vertices and tangent vectors at the start/end points to form a curved surface by connecting sides of the differential polyhedron and form a closed surface by connecting curved surfaces with a curved surface boundary line, thereby generating a primitive which is a set of points belonging to the inside of the closed surface;
___________________________________
a storage step of storing CSG data which represents a solid model in CSG representation by a tree structure of set operations of the primitives;
___________________________________
a dexel generation step of determining an intersection point between the solid model and a straight line from the intersection point between the closed surface of the primitive and the straight line by a set operation based on the CSG data,
___________________________________
Claim 10 of 18/705,938 recites calculating a reflection position and a reflection direction of a light ray in the solid model.
Claim 13 of 18/726,942 lacks calculating a reflection position and a reflection direction of a light ray in the solid model.
Romeiro discloses calculating a reflection position and a reflection direction of a light ray in the solid model (Paragraph 2 in 1st Col. of Page 4 – “The pixel shader receives this information, as well as parameters containing information on the primitives in question (depending on primitive: center, radius, etc), calculates the ray direction, traces the ray starting from the point at the bounding box corresponding to the pixel in question, and calculates the closest (to the camera) intersection with the primitive, as well as the primitive normal at that intersection. It then computes the color and the correct depth of the pixel”; Note: the ray position and direction are equivalent to the reflection position and direction of a light ray respectively). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the dexel generation unit recited in claim 13 of 18/726,942 to calculate a reflection position and a reflection direction of a light ray in the solid model because the reflection information allows for determining the lighting and color of the model, which then helps produce an accurate and realistic rendering of the model.
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 1-2, 4, and 7-10 are rejected under 35 U.S.C. 103 as being unpatentable over Rossignac (Solid and Physical Modeling) in view of Tokumasu et al. (Solid Model in Geometric Modelling System: HiCAD) and Romeiro et al. (Hardware-assisted Rendering of CSG Models), hereinafter Rossignac, Tokumasu, and Romeiro.
Regarding claim 1, Rossignac teaches a three-dimensional CAD system (Paragraph 3 on Page 1, Paragraph 6 on Page 3 – “CAD/CAM applications evaluate various properties of a solid or assembly, such as volumes or contact areas, or assess the feasibility and cost of life-cycle activities, such as manufacture, assembly, or inspection… The digital representation and basic algorithms used in solid modeling are based on few fundamental principles discussed in this section. In the context of solid modeling, the term solid distinguishes a sub-class of 3D sets from more general sets”; Note: the CAD application is a CAD system that makes 3D models) comprising:
a primitive generation unit that uses a differential polyhedron model which is a set of differential polyhedrons (Paragraph 2 on Page 7, Paragraph 9 on Page 12, Paragraph 1 on Page 13, Paragraph 2 on Page 12 – “polygonal faces may be easily triangulated [Ronfard94], and therefore polyhedra may be represented by triangle meshes…Constructive Solid Geometry (CSG) is the most popular constructive representation. Its primitives are typically parameterized solids (such as cylinders, cones, spheres, blocks, tori), volume features suitable for a particular application domain (such as slots or counter-bored holes), more general translational or rotational extrusions of planar regions, or triangle meshes, such as those discussed above… The faces of a solid defined as a Boolean combination of curved solids may be subdivided into triangles or quads and represented by approximating parametric patches or may be represented as a trimmed surface by a reference to the host surface (original patch) on which they lie, and by trimming loops of curved edges”; Note: the triangle mesh is the differential polyhedron model, and the triangles are the differential polyhedrons) including coordinate values of triangle vertices (Paragraph 3 on Page 9 – “visit the triangles in a depth-first order of a spanning tree and encode the vertices in the order in which they are first encountered by this traversal. The location g(c) of vertex v(c) is estimated using the parallelogram rule as e(c)=g(p(c))+g(n(c))–g(o(c)). Then, the difference vector g(c)–e(c) is encoded. When the coordinates are quantized…”; Note: the triangles have vertex coordinates), normal vectors of the triangle vertices (Paragraph 4 on Page 12 – “These may be distinguished by storing information about which points in the neighborhood of the edge belong to the face. This neighborhood information can be encoded efficiently, as a single-bit “left” or “right” attribute, in terms of the orientation of the surface normal and the orientation of the curve”), and curved line elements including start/end points consisting of the triangle vertices (Paragraph 5 on Page 10 – “a triangle T may be traversed by several trimming curves…To compute the correct topology of the arrangements of the trimming curves in T, we must order their entry and exit points around the perimeter of T”; Note: the entry/exit points are equivalent to the start/end points)
to form a curved surface by connecting sides of the differential polyhedron (Paragraph 9 on Page 11 – “consider a deformed version of a triangle mesh, where each edge is possibly curved and where each triangle is a smooth portion of a possibly curved surface. If we use the Corner Table to represent the vertex locations and the connectivity, we need to augment it with a description of the geometry of each edge and of each triangle. Subdivision rules may be applied to refine each triangle and each edge. Hence, the curved elements (edges, faces) may be represented implicitly as the limit of a subdivision process applied to a coarse control triangle mesh”; Note: triangles in the triangle mesh (differential polyhedron model) are connected to form a curved surface) and form a closed surface by connecting curved surfaces with a curved surface boundary line (Paragraph 2 on Page 12 – “The faces of a solid defined as a Boolean combination of curved solids may be subdivided into triangles or quads and represented by approximating parametric patches or may be represented as a trimmed surface by a reference to the host surface (original patch) on which they lie, and by trimming loops of curved edges. The edges of a solid typically lie on the intersection curves between two surfaces, and sometimes on singular curves (cusps) of a single surface”; Note: the intersection curves are equivalent to the curved surface boundary lines. The surfaces connected to the intersection curves are equivalent to the curved surfaces that make-up a closed surface), thereby generating a primitive which is a set of points belonging to the inside of the closed surface (Paragraph 3 on Page 12 – “modeling systems use two separate approximations of the trimming curves, one per patch, and represent them as two-dimensional curves in the parametric domain of the patch. These may be used to perform point-in-face membership classification in the parametric two-dimensional domain”; Note: points in the curve surface of the patches are determined, which are equivalent to the generated primitive. The algorithm that generates the primitives is equivalent to the primitive generation unit);
and a storage unit that stores CSG data which represents a solid model in CSG representation by a tree structure of set operations of the primitives (Paragraph 4 on Page 13, Paragraph 7 on Page 15, Paragraph 3 on Page 16 – “A CSG solid S is defined as a regularized Boolean expression that combines primitive solid instances through union (+), intersection (omitted), and difference (–) operators. Remember that !A denotes the complement of A. Such an expression may be parsed into a rooted binary tree: the root represents the desired solid, which may be empty; the leaves represent primitive instances; and the nodes are each associated with a Boolean operation… A pivoting strategy that makes the tree left-heavy [Hable05], combined with a linear optimization [Rossignac06] reduces storage requirement for CSG membership evaluation”; Note: there is CSG data representing a CSG model by a tree structure of Boolean operations of primitives. It is implied there is a storage unit because there is a storage requirement related to the data in the tree).
Rossignac does not teach a set of differential polyhedrons including curved line elements including tangent vectors at the start/end points. However, Tokumasu teaches curved line elements including tangent vectors at the start/end points (Paragraph 1 in 2nd Col. of Page 3 – “The curves are easily controlled in models with following distinctive reasons. The direction of tangent line at initial and final vertexes conforms to the P0P1 and P2P3 directions”). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Tokumasu to have the curved lines include tangent vectors at start/end points because the tangent vectors help define the curve of the line, and thus, are important to forming curved surfaces.
Rossignac modified by Tokumasu still does not teach a representation processing unit that determines an intersection point between the solid model and a straight line from the intersection point between the closed surface of the primitive and the straight line by a set operation based on the CSG data, thereby calculating a reflection position and a reflection direction of a light ray in the solid model. However, Romeiro teaches a representation processing unit that determines an intersection point between the solid model and a straight line from the intersection point between the closed surface of the primitive and the straight line by a set operation based on the CSG data (Paragraph 3 in 2nd Col. of Page 4, Paragraph 3 in 1st Col. of Page 5 – “Given a cell L and a primitive P, in order to ray-trace P restricted to L, we use the framework described in 3.1 with a pixel shader that performs: 1) Let r=o+t⋅v denote the ray starting at o (the object space coordinates of the point for which the shader is running), and going in the direction of the camera (v). 2) Intersect L with r - Obtain a segment 1 , SL=[0,tf] _ as a result (i.e., the set of all t such that r and L intersect). 3) Intersect P with r - Obtain Sp, a segment (degenerate or not) or an empty set. Calculate surface normals at the ray-surface intersection points (if any)…8) If t = 0 and (−ε,ε) is in SR for some ε > 0, discard the pixel. Else, the ray intersects the surface of P inside L at o+t·v…Given a cell (L) and two primitives (P1 and P2}, we want to ray trace (P1∩P2) restricted to L. Again we perform the same procedure described in 3.1.2, with a pixel shader”; Note: the ray is a straight line that intersects set/Boolean operations of primitives, which then logically shows how the ray intersects the model. The pixel shader is equivalent to the representation processing unit), thereby calculating a reflection position and a reflection direction of a light ray in the solid model (Paragraph 2 in 1st Col. of Page 4 – “The pixel shader receives this information, as well as parameters containing information on the primitives in question (depending on primitive: center, radius, etc), calculates the ray direction, traces the ray starting from the point at the bounding box corresponding to the pixel in question, and calculates the closest (to the camera) intersection with the primitive, as well as the primitive normal at that intersection. It then computes the color and the correct depth of the pixel”; Note: the ray position and direction are equivalent to the reflection position and direction). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Romeiro to determine an intersection point between the solid model and a straight line for the benefit of determining which parts of the model are visible from a viewpoint, which is important for rendering. It also would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Romeiro to calculate a reflection position and direction of a light ray in the solid model because the reflection information allows for determining the lighting and color of the model, which then helps produce an accurate and realistic rendering of the model.
Regarding claim 2, Rossignac in view of Tokumasu and Romeiro teaches the three-dimensional CAD system according to claim 1. Rossignac further teaches wherein the primitive generation unit generates the differential polyhedron by adding, on the basis of the coordinate values of the triangle vertices, curved line elements including start/end points consisting of the triangle vertices (Paragraph 9 on Page 11 – “consider a deformed version of a triangle mesh, where each edge is possibly curved and where each triangle is a smooth portion of a possibly curved surface. If we use the Corner Table to represent the vertex locations and the connectivity, we need to augment it with a description of the geometry of each edge and of each triangle. Subdivision rules may be applied to refine each triangle and each edge. Hence, the curved elements (edges, faces) may be represented implicitly as the limit of a subdivision process applied to a coarse control triangle mesh”; Note: the triangle mesh (differential polyhedron model) is modified to have curved edge/line elements based on the vertex locations (coordinates)). Rossignac does not directly teach generating the differential polyhedron on the basis of the normal vectors of the triangle vertices. However, Rossignac separately teaches the normal vectors of the triangle vertices (Paragraph 4 on Page 12 – “These may be distinguished by storing information about which points in the neighborhood of the edge belong to the face. This neighborhood information can be encoded efficiently, as a single-bit “left” or “right” attribute, in terms of the orientation of the surface normal and the orientation of the curve”). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to generate the differential polyhedron on the basis of the coordinate values of the triangle vertices and the normal vectors of the triangle vertices because the normal vectors help determine the orientation of the triangle faces, and as a result, helps determine the curvatures on the surface of the model. Furthermore, Rossignac does not teach that the curved line elements include tangent vectors at the start/end points. However, Tokumasu teaches that the curved line elements include tangent vectors at the start/end points (Paragraph 1 in 2nd Col. of Page 3 – “The curves are easily controlled in models with following distinctive reasons. The direction of tangent line at initial and final vertexes conforms to the P0P1 and P2P3 directions”). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Tokumasu to have the curved lines include tangent vectors at start/end points because the tangent vectors help define the curve of the line, and thus, are important to forming curved surfaces.
Regarding claim 4, Rossignac in view of Tokumasu and Romeiro teaches the three-dimensional CAD system according to claim 1. Rossignac further teaches wherein the primitive generation unit constructs a connection relation between the curved surfaces by using a curved line element shared between the curved surfaces, thereby forming a closed surface connecting the curved surfaces (Paragraph 2 on Page 12 – “The faces of a solid defined as a Boolean combination of curved solids may be subdivided into triangles or quads and represented by approximating parametric patches or may be represented as a trimmed surface by a reference to the host surface (original patch) on which they lie, and by trimming loops of curved edges. The edges of a solid typically lie on the intersection curves between two surfaces, and sometimes on singular curves (cusps) of a single surface”; Note: the intersection curves are equivalent to the connection relation. The surfaces connected to the intersection curves are equivalent to the curved surfaces that make-up a closed surface).
Regarding claim 7, Rossignac in view of Tokumasu and Romeiro teaches the three-dimensional CAD system according to claim 1. Rossignac does not teach wherein the representation processing unit uses real-time ray tracing to determine an intersection point between the solid model and the light ray. However, Romeiro teaches wherein the representation processing unit uses real-time ray tracing to determine an intersection point between the solid model and the light ray (Paragraph 3 in 2nd Col. of Page 4 – “Given a cell L and a primitive P, in order to ray-trace P restricted to L, we use the framework described in 3.1 with a pixel shader that performs: 1) Let r=o+t⋅v denote the ray starting at o (the object space coordinates of the point for which the shader is running), and going in the direction of the camera (v). 2) Intersect L with r - Obtain a segment 1 , SL=[0,tf] _ as a result (i.e., the set of all t such that r and L intersect). 3) Intersect P with r - Obtain Sp, a segment (degenerate or not) or an empty set. Calculate surface normals at the ray-surface intersection points (if any)…8) If t = 0 and (−ε,ε) is in SR for some ε > 0, discard the pixel. Else, the ray intersects the surface of P inside L at o+t·v”; Note: the ray is a straight line that intersects primitives of the model. The pixel sahder is equivalent to the representation processing unit). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Romeiro to use ray-tracing to determine an intersection point for the benefit of determining which parts of the model are visible from a viewpoint, which is important for rendering. Furthermore, ray-tracing is beneficial for producing realistic lighting.
Regarding claim 8, Rossignac in view of Tokumasu and Romeiro teaches the three-dimensional CAD system according to claim 1. Rossignac further teaches a construction line generation unit that generates an intersection line of two primitives as a construction line, wherein the primitive generation unit generates a new primitive based on the construction line (Paragraph 5-6 and 9 on Page 14 – “the curve is segmented at places where it reaches, crosses, or leaves the boundary of any primitive. Then, the classification of each segment is inferred from the membership of its midpoint, computed as discussed above. The first step requires computing curve/surface intersections. It is usually performed by substituting a parametric formulation C(t) of the curve into an implicit equation of the surface and finding the roots or through an iterative process…The boundary of a CSG solid S is the union of the trimmed boundaries of its primitives”; Note: the intersection curves are equivalent to the intersection and construction line. The intersection curves define the boundaries of the primitives. Logically, when the boundaries are generated, so are the primitives. The algorithm that determines the intersection curves is equivalent to the construction line unit).
Regarding claim 9, Rossignac teaches a three-dimensional CAD method (Paragraph 3 on Page 1, Paragraph 6 on Page 3 – “CAD/CAM applications evaluate various properties of a solid or assembly, such as volumes or contact areas, or assess the feasibility and cost of life-cycle activities, such as manufacture, assembly, or inspection… The digital representation and basic algorithms used in solid modeling are based on few fundamental principles discussed in this section. In the context of solid modeling, the term solid distinguishes a sub-class of 3D sets from more general sets”; Note: the CAD application is a CAD method that makes 3D models) including:
a primitive generation step of using a differential polyhedron model which is a set of differential polyhedrons (Paragraph 2 on Page 7, Paragraph 9 on Page 12, Paragraph 1 on Page 13, Paragraph 2 on Page 12 – “polygonal faces may be easily triangulated [Ronfard94], and therefore polyhedra may be represented by triangle meshes…Constructive Solid Geometry (CSG) is the most popular constructive representation. Its primitives are typically parameterized solids (such as cylinders, cones, spheres, blocks, tori), volume features suitable for a particular application domain (such as slots or counter-bored holes), more general translational or rotational extrusions of planar regions, or triangle meshes, such as those discussed above… The faces of a solid defined as a Boolean combination of curved solids may be subdivided into triangles or quads and represented by approximating parametric patches or may be represented as a trimmed surface by a reference to the host surface (original patch) on which they lie, and by trimming loops of curved edges”; Note: the triangle mesh is the differential polyhedron model, and the triangles are the differential polyhedrons) including coordinate values of triangle vertices (Paragraph 3 on Page 9 – “visit the triangles in a depth-first order of a spanning tree and encode the vertices in the order in which they are first encountered by this traversal. The location g(c) of vertex v(c) is estimated using the parallelogram rule as e(c)=g(p(c))+g(n(c))–g(o(c)). Then, the difference vector g(c)–e(c) is encoded. When the coordinates are quantized…”; Note: the triangles have vertex coordinates), normal vectors of the triangle vertices (Paragraph 4 on Page 12 – “These may be distinguished by storing information about which points in the neighborhood of the edge belong to the face. This neighborhood information can be encoded efficiently, as a single-bit “left” or “right” attribute, in terms of the orientation of the surface normal and the orientation of the curve”), and curved line elements including start/end points consisting of the triangle vertices (Paragraph 5 on Page 10 – “a triangle T may be traversed by several trimming curves…To compute the correct topology of the arrangements of the trimming curves in T, we must order their entry and exit points around the perimeter of T”; Note: the entry/exit points are equivalent to the start/end points)
to form a curved surface by connecting sides of the differential polyhedron (Paragraph 9 on Page 11 – “consider a deformed version of a triangle mesh, where each edge is possibly curved and where each triangle is a smooth portion of a possibly curved surface. If we use the Corner Table to represent the vertex locations and the connectivity, we need to augment it with a description of the geometry of each edge and of each triangle. Subdivision rules may be applied to refine each triangle and each edge. Hence, the curved elements (edges, faces) may be represented implicitly as the limit of a subdivision process applied to a coarse control triangle mesh”; Note: triangles in the triangle mesh (differential polyhedron model) are connected to form a curved surface) and form a closed surface by connecting curved surfaces with a curved surface boundary line (Paragraph 2 on Page 12 – “The faces of a solid defined as a Boolean combination of curved solids may be subdivided into triangles or quads and represented by approximating parametric patches or may be represented as a trimmed surface by a reference to the host surface (original patch) on which they lie, and by trimming loops of curved edges. The edges of a solid typically lie on the intersection curves between two surfaces, and sometimes on singular curves (cusps) of a single surface”; Note: the intersection curves are equivalent to the curved surface boundary lines. The surfaces connected to the intersection curves are equivalent to the curved surfaces that make-up a closed surface), thereby generating a primitive which is a set of points belonging to the inside of the closed surface (Paragraph 3 on Page 12 – “modeling systems use two separate approximations of the trimming curves, one per patch, and represent them as two-dimensional curves in the parametric domain of the patch. These may be used to perform point-in-face membership classification in the parametric two-dimensional domain”; Note: points in the curve surface of the patches are determined, which are equivalent to the generated primitive. The algorithm that generates the primitives is equivalent to the primitive generation unit);
a storage step of storing CSG data which represents a solid model in CSG representation by a tree structure of set operations of the primitives (Paragraph 4 on Page 13, Paragraph 7 on Page 15, Paragraph 3 on Page 16 – “A CSG solid S is defined as a regularized Boolean expression that combines primitive solid instances through union (+), intersection (omitted), and difference (–) operators. Remember that !A denotes the complement of A. Such an expression may be parsed into a rooted binary tree: the root represents the desired solid, which may be empty; the leaves represent primitive instances; and the nodes are each associated with a Boolean operation… A pivoting strategy that makes the tree left-heavy [Hable05], combined with a linear optimization [Rossignac06] reduces storage requirement for CSG membership evaluation”; Note: there is CSG data representing a CSG model by a tree structure of Boolean operations of primitives. It is implied there is a storage unit because there is a storage requirement related to the data in the tree).
Rossignac does not teach a set of differential polyhedrons including curved line elements including tangent vectors at the start/end points. However, Tokumasu teaches curved line elements including tangent vectors at the start/end points (Paragraph 1 in 2nd Col. of Page 3 – “The curves are easily controlled in models with following distinctive reasons. The direction of tangent line at initial and final vertexes conforms to the P0P1 and P2P3 directions”). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Tokumasu to have the curved lines include tangent vectors at start/end points because the tangent vectors help define the curve of the line, and thus, are important to forming curved surfaces.
Rossignac modified by Tokumasu still does not teach a representation processing step of determining an intersection point between the solid model and a straight line from the intersection point between the closed surface of the primitive and the straight line by a set operation based on the CSG data, thereby calculating a reflection position and a reflection direction of a light ray in the solid model. However, Romeiro teaches a representation processing step of determining an intersection point between the solid model and a straight line from the intersection point between the closed surface of the primitive and the straight line by a set operation based on the CSG data (Paragraph 3 in 2nd Col. of Page 4, Paragraph 3 in 1st Col. of Page 5 – “Given a cell L and a primitive P, in order to ray-trace P restricted to L, we use the framework described in 3.1 with a pixel shader that performs: 1) Let r=o+t⋅v denote the ray starting at o (the object space coordinates of the point for which the shader is running), and going in the direction of the camera (v). 2) Intersect L with r - Obtain a segment 1 , SL=[0,tf] _ as a result (i.e., the set of all t such that r and L intersect). 3) Intersect P with r - Obtain Sp, a segment (degenerate or not) or an empty set. Calculate surface normals at the ray-surface intersection points (if any)…8) If t = 0 and (−ε,ε) is in SR for some ε > 0, discard the pixel. Else, the ray intersects the surface of P inside L at o+t·v…Given a cell (L) and two primitives (P1 and P2}, we want to ray trace (P1∩P2) restricted to L. Again we perform the same procedure described in 3.1.2, with a pixel shader”; Note: the ray is a straight line that intersects set/Boolean operations of primitives, which then logically shows how the ray intersects the model. The pixel shader is equivalent to the representation processing unit), thereby calculating a reflection position and a reflection direction of a light ray in the solid model (Paragraph 2 in 1st Col. of Page 4 – “The pixel shader receives this information, as well as parameters containing information on the primitives in question (depending on primitive: center, radius, etc), calculates the ray direction, traces the ray starting from the point at the bounding box corresponding to the pixel in question, and calculates the closest (to the camera) intersection with the primitive, as well as the primitive normal at that intersection. It then computes the color and the correct depth of the pixel”; Note: the ray position and direction are equivalent to the reflection position and direction). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Romeiro to determine an intersection point between the solid model and a straight line for the benefit of determining which parts of the model are visible from a viewpoint, which is important for rendering. It also would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Romeiro to calculate a reflection position and direction of a light ray in the solid model because the reflection information allows for determining the lighting and color of the model, which then helps produce an accurate and realistic rendering of the model.
Regarding claim 10, Rossignac teaches a three-dimensional CAD program that causes a computer to execute (Paragraph 3 on Page 1, Paragraph 6 on Page 3 – “CAD/CAM applications evaluate various properties of a solid or assembly, such as volumes or contact areas, or assess the feasibility and cost of life-cycle activities, such as manufacture, assembly, or inspection… The digital representation and basic algorithms used in solid modeling are based on few fundamental principles discussed in this section. In the context of solid modeling, the term solid distinguishes a sub-class of 3D sets from more general sets”; Note: the CAD application is a CAD program that makes 3D models. The computer is implied because an application cannot run without a computer):
a primitive generation step of using a differential polyhedron model which is a set of differential polyhedrons (Paragraph 2 on Page 7, Paragraph 9 on Page 12, Paragraph 1 on Page 13, Paragraph 2 on Page 12 – “polygonal faces may be easily triangulated [Ronfard94], and therefore polyhedra may be represented by triangle meshes…Constructive Solid Geometry (CSG) is the most popular constructive representation. Its primitives are typically parameterized solids (such as cylinders, cones, spheres, blocks, tori), volume features suitable for a particular application domain (such as slots or counter-bored holes), more general translational or rotational extrusions of planar regions, or triangle meshes, such as those discussed above… The faces of a solid defined as a Boolean combination of curved solids may be subdivided into triangles or quads and represented by approximating parametric patches or may be represented as a trimmed surface by a reference to the host surface (original patch) on which they lie, and by trimming loops of curved edges”; Note: the triangle mesh is the differential polyhedron model, and the triangles are the differential polyhedrons) including coordinate values of triangle vertices (Paragraph 3 on Page 9 – “visit the triangles in a depth-first order of a spanning tree and encode the vertices in the order in which they are first encountered by this traversal. The location g(c) of vertex v(c) is estimated using the parallelogram rule as e(c)=g(p(c))+g(n(c))–g(o(c)). Then, the difference vector g(c)–e(c) is encoded. When the coordinates are quantized…”; Note: the triangles have vertex coordinates), normal vectors of the triangle vertices (Paragraph 4 on Page 12 – “These may be distinguished by storing information about which points in the neighborhood of the edge belong to the face. This neighborhood information can be encoded efficiently, as a single-bit “left” or “right” attribute, in terms of the orientation of the surface normal and the orientation of the curve”), and curved line elements including start/end points consisting of the triangle vertices (Paragraph 5 on Page 10 – “a triangle T may be traversed by several trimming curves…To compute the correct topology of the arrangements of the trimming curves in T, we must order their entry and exit points around the perimeter of T”; Note: the entry/exit points are equivalent to the start/end points)
to form a curved surface by connecting sides of the differential polyhedron (Paragraph 9 on Page 11 – “consider a deformed version of a triangle mesh, where each edge is possibly curved and where each triangle is a smooth portion of a possibly curved surface. If we use the Corner Table to represent the vertex locations and the connectivity, we need to augment it with a description of the geometry of each edge and of each triangle. Subdivision rules may be applied to refine each triangle and each edge. Hence, the curved elements (edges, faces) may be represented implicitly as the limit of a subdivision process applied to a coarse control triangle mesh”; Note: triangles in the triangle mesh (differential polyhedron model) are connected to form a curved surface) and form a closed surface by connecting curved surfaces with a curved surface boundary line (Paragraph 2 on Page 12 – “The faces of a solid defined as a Boolean combination of curved solids may be subdivided into triangles or quads and represented by approximating parametric patches or may be represented as a trimmed surface by a reference to the host surface (original patch) on which they lie, and by trimming loops of curved edges. The edges of a solid typically lie on the intersection curves between two surfaces, and sometimes on singular curves (cusps) of a single surface”; Note: the intersection curves are equivalent to the curved surface boundary lines. The surfaces connected to the intersection curves are equivalent to the curved surfaces that make-up a closed surface), thereby generating a primitive which is a set of points belonging to the inside of the closed surface (Paragraph 3 on Page 12 – “modeling systems use two separate approximations of the trimming curves, one per patch, and represent them as two-dimensional curves in the parametric domain of the patch. These may be used to perform point-in-face membership classification in the parametric two-dimensional domain”; Note: points in the curve surface of the patches are determined, which are equivalent to the generated primitive. The algorithm that generates the primitives is equivalent to the primitive generation unit);
a storage step of storing CSG data which represents a solid model in CSG representation by a tree structure of set operations of the primitives (Paragraph 4 on Page 13, Paragraph 7 on Page 15, Paragraph 3 on Page 16 – “A CSG solid S is defined as a regularized Boolean expression that combines primitive solid instances through union (+), intersection (omitted), and difference (–) operators. Remember that !A denotes the complement of A. Such an expression may be parsed into a rooted binary tree: the root represents the desired solid, which may be empty; the leaves represent primitive instances; and the nodes are each associated with a Boolean operation… A pivoting strategy that makes the tree left-heavy [Hable05], combined with a linear optimization [Rossignac06] reduces storage requirement for CSG membership evaluation”; Note: there is CSG data representing a CSG model by a tree structure of Boolean operations of primitives. It is implied there is a storage unit because there is a storage requirement related to the data in the tree).
Rossignac does not teach a set of differential polyhedrons including curved line elements including tangent vectors at the start/end points. However, Tokumasu teaches curved line elements including tangent vectors at the start/end points (Paragraph 1 in 2nd Col. of Page 3 – “The curves are easily controlled in models with following distinctive reasons. The direction of tangent line at initial and final vertexes conforms to the P0P1 and P2P3 directions”). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Tokumasu to have the curved lines include tangent vectors at start/end points because the tangent vectors help define the curve of the line, and thus, are important to forming curved surfaces.
Rossignac modified by Tokumasu still does not teach a representation processing step of determining an intersection point between the solid model and a straight line from the intersection point between the closed surface of the primitive and the straight line by a set operation based on the CSG data, thereby calculating a reflection position and a reflection direction of a light ray in the solid model. However, Romeiro teaches a representation processing step of determining an intersection point between the solid model and a straight line from the intersection point between the closed surface of the primitive and the straight line by a set operation based on the CSG data (Paragraph 3 in 2nd Col. of Page 4, Paragraph 3 in 1st Col. of Page 5 – “Given a cell L and a primitive P, in order to ray-trace P restricted to L, we use the framework described in 3.1 with a pixel shader that performs: 1) Let r=o+t⋅v denote the ray starting at o (the object space coordinates of the point for which the shader is running), and going in the direction of the camera (v). 2) Intersect L with r - Obtain a segment 1 , SL=[0,tf] _ as a result (i.e., the set of all t such that r and L intersect). 3) Intersect P with r - Obtain Sp, a segment (degenerate or not) or an empty set. Calculate surface normals at the ray-surface intersection points (if any)…8) If t = 0 and (−ε,ε) is in SR for some ε > 0, discard the pixel. Else, the ray intersects the surface of P inside L at o+t·v…Given a cell (L) and two primitives (P1 and P2}, we want to ray trace (P1∩P2) restricted to L. Again we perform the same procedure described in 3.1.2, with a pixel shader”; Note: the ray is a straight line that intersects set/Boolean operations of primitives, which then logically shows how the ray intersects the model. The pixel shader is equivalent to the representation processing unit), thereby calculating a reflection position and a reflection direction of a light ray in the solid model (Paragraph 2 in 1st Col. of Page 4 – “The pixel shader receives this information, as well as parameters containing information on the primitives in question (depending on primitive: center, radius, etc), calculates the ray direction, traces the ray starting from the point at the bounding box corresponding to the pixel in question, and calculates the closest (to the camera) intersection with the primitive, as well as the primitive normal at that intersection. It then computes the color and the correct depth of the pixel”; Note: the ray position and direction are equivalent to the reflection position and direction). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Romeiro to determine an intersection point between the solid model and a straight line for the benefit of determining which parts of the model are visible from a viewpoint, which is important for rendering. It also would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Romeiro to calculate a reflection position and direction of a light ray in the solid model because the reflection information allows for determining the lighting and color of the model, which then helps produce an accurate and realistic rendering of the model.
Claim 3 is rejected under 35 U.S.C. 103 as being unpatentable over Rossignac in view of Tokumasu, Romeiro, and Page et al. (Normal Vector Voting: Crease Detection and Curvature Estimation on Large, Noisy Meshes), hereinafter Page.
Regarding claim 3, Rossignac in view of Tokumasu and Romeiro teaches the three-dimensional CAD system according to claim 1 or 2. Rossignac does not teach wherein the primitive generation unit generates a spatial geodesic by using coordinate values of triangle vertices shared by adjacent first and second differential polyhedrons and normal vectors of the triangle vertices to construct a connection relation by sharing the spatial geodesic, thereby forming a curved surface. However, Page teaches generating a spatial geodesic by using coordinate values of triangle vertices shared by adjacent first and second differential polyhedrons and normal vectors of the triangle vertices to construct a connection relation by sharing the spatial geodesic, thereby forming a curved surface (Paragraph 3 on Page 8, Paragraph 3 on Page 9 – “For the first pass through a mesh, we estimate the normal vector orientation for each vertex. For the second pass, we estimate curvature. First, we consider normal estimation. The basic idea is to select a surface region around a vertex. A user-specified distance bounds this region in terms of geodesic distance from the vertex where the vertex is the center of the geodesic patch. Each triangle in this patch—or geodesic neighborhood—votes at that center vertex in order to estimate the orientation of that vertex. Note the simple example in Fig. 2. Here, triangle fi in the mesh neighborhood Mv of vertex v has a normal N that generates a normal vote Ni at v. We collect these votes in a covariance matrix and decompose this matrix using eigen-analysis. The eigenvectors and eigenvalues estimate the orientation for v. We illustrate this sequence of events in Fig. 3. With a few slight modifications, this same sequence estimates the curvature at v for the second pass…The smallest neighborhood in this figure consists of just the immediate triangles adjacent to the vertex of interest”; Note: a spatial geodesic patch is generated. It creates a connection between triangles adjacent to the center vertex, and it is obvious that the triangles are adjacent to each other if they are all adjacent to the center vertex. Triangle vertices, which represent coordinate positions, and normals are used in the generation). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Page to generate a spatial geodesic for the benefit of having a consistent way to generate curves. It also would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Page to construct a connection relation by sharing the spatial geodesic and form a curved surface because the geodesic is the shortest path, so the geodesic line would help represent the natural curve of the object, reducing the use of extra space and allowing for a realistic representation of the object.
Claim 5 is rejected under 35 U.S.C. 103 as being unpatentable over Rossignac in view of Tokumasu, Romeiro, and Wolff (Arc length parametrization), hereinafter Wolff.
Regarding claim 5, Rossignac in view of Tokumasu and Romeiro teaches the three-dimensional CAD system according to claim 1. Rossignac does not teach wherein the curved line element composed of tangent vectors at the start/end points is represented by a cubic polynomial curve shown by Formula 1.
PNG
media_image1.png
81
607
media_image1.png
Greyscale
However, Tokumasu teaches the curved line element composed of tangent vectors at the start/end points (Paragraph 1 in 2nd Col. of Page 3 – “The curves are easily controlled in models with following distinctive reasons. The direction of tangent line at initial and final vertexes conforms to the P0P1 and P2P3 directions”). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Tokumasu to have a curved line element composed of tangent vectors at start/end points because the tangent vectors help define the curve of the line, and thus, are important to forming curved surfaces. Rossignac modified by Tokumasu still does not teach wherein the curved line element is represented by a cubic polynomial curve shown by Formula 1. However, Wolff teaches wherein the curved line element is represented by a cubic polynomial curve shown by Formula 1
PNG
media_image1.png
81
607
media_image1.png
Greyscale
(Paragraph 1 on Page 1, Paragraph 2 on Page 3, Fig. 2 – “This means that for a curve parametrized by t∈[t0,t1] we want to relate t and L, with L the length between [t0,t]. For Béziers we take t0=0 as the start of the curve and t1=1 the end…Our polynomial has the form
PNG
media_image2.png
33
249
media_image2.png
Greyscale
”; Note: The equation is equivalent to Formula 1. As shown in Fig. 2, t is between 0 and 1, where 1 is equivalent to the curved line element length in this case).
PNG
media_image3.png
208
681
media_image3.png
Greyscale
Screenshot of Fig. 2 (taken from Wolff)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Rossignac to incorporate the teachings of Wolff to represent the curved line element with a cubic polynomial curve for the benefit of computational efficiency due to the low-degree equation and its ability to produce smooth visuals in graphics.
Allowable Subject Matter
Claim 6 is 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.
Claim 6 would be allowable for disclosing wherein the representation processing unit omits a set operation symbol and determines an intersection point between the solid model and the light ray in the tree structure of set operations of the primitives, when a lower set operation symbol is a same as an upper set operation symbol in a hierarchy.
Regarding claim 6, Rossignac in view of Tokumasu and Romeiro teaches the three-dimensional CAD system according to claim 1. Mostajabodaveh et al. (CSG Ray Tracing Revisited: Interactive Rendering of Massive Models Made of Non-planar Higher Order Primitives), hereinafter Mostajabodaveh, teaches wherein the representation processing unit determines an intersection point between the solid model and the light ray in the tree structure of set operations of the primitives (Paragraph 2-3 in 1st Col. of Page 3 – “A compound object can be described by means of a binary tree, where the leaves correspond to primitives and the inner nodes to set operations…Ray tracing such a structure can be done in a straight forward way. For each ray all the intersection points of the ray with the primitives of the scene are calculated. This leads to a set of intervals that determine the ranges where a ray runs inside or outside of a primitive. These intervals can be grouped in a so-called Roth diagram (Roth, 1982). Here, for each primitive that was pierced by the ray, all entry and exit points are recorded in a sorted order. For each two primitives that are to be combined, the intervals in the Roth diagram are merged according to the relevant Boolean operation. The resulting Roth diagram, i.e, the resulting intervals, represent the entry and exit points of the composite object. The entry point with the closest distance to the ray origin represents the eventual hitpoint (i.e., the nearest surface point which is visible)”; Note: the ray is a straight line that intersects primitives of the model. The eventual hitpoint is equivalent to the intersection point, and the ray-tracing algorithm is equivalent to the representation processing unit). Friedrich et al. (A Flexible Pipeline for the Optimization of CSG Trees), hereinafter Friedrich, teaches omitting a set operation symbol (Paragraph 3 in 2nd Col. of Page 3 – “Empty set ∅ as well as universal set W expressions are then replaced based on the following rules: • If one operand of an intersection expression is the empty set ∅, the expression is replaced with the empty set. • If one operand of an intersection expression is the universal set W, the expression is replaced with the other operand. • If one operand of a union expression is the empty set ∅, the expression is replaced with the other operand”). However, none of the prior art teaches performing the omission and determination steps when a lower set operation symbol is a same as an upper set operation symbol in a hierarchy. Furthermore, it would not have been obvious to combine Friedrich, Mostajabodaveh, and Rossignac to omit a set operation symbol and determine an intersection point between the solid model and the light ray in the tree structure of set operations of the primitives. Based on the configuration, it would be improper hindsight to modify Rossignac in such a way. Therefore, the combination of features is considered allowable.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Krishnan et al. (Representation, Boundary Computation and Fast Display of CSG Models with NURBS Primitives) teaches a method of generating B-reps from CSG models and representing trimming curves. Benouamer et al. (Bridging the Gap between CSG and Brep via a Triple Ray Representation) teaches a method of computing a triple ray representation using ray-tracing to combine CSG and B-rep.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MICHELLE HAU MA whose telephone number is (571)272-2187. The examiner can normally be reached M-Th 7-5:30.
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, King Poon can 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 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.
/MICHELLE HAU MA/ Examiner, Art Unit 2617
/KING Y POON/Supervisory Patent Examiner, Art Unit 2617
Prosecution Insights