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 .
DETAILED ACTION
Information Disclosure Statement
The information disclosure statement filed 07/12/2024 (item 5) and 9/24/2024 (item 7) fails to comply with 37 CFR 1.98(a)(2), which requires a legible copy of each cited foreign patent document; each non-patent literature publication or that portion which caused it to be listed; and all other information or that portion which caused it to be listed. It has been placed in the application file, but the information referred to therein has not been considered.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-10, 14-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more.
Regarding independent claim 1, the claim directs to “a computer-implemented method, comprising: obtaining a groundtruth occupancy function descriptive of a three-dimensional (3D) object; and constructing a constructive solid geometry (CSG) model of the 3D object, the CSG model defined by a binary tree wherein nodes of the binary tree define Boolean operations and leaves of the binary tree define parameters of CSG primitives, wherein values of the Boolean operations and values of the parameters of the CSG primitives for the binary tree are identified by minimizing an error between an occupancy function of the CSG model and the groundtruth occupancy function of the 3D object” which is a process and falls within one of the statutory categories of invention.
The claim recites:
The steps of “obtaining a groundtruth occupancy function descriptive of a three-dimensional (3D) object” is mere data gathering/mathematical formulas or equations. The broadest reasonable interpretation, obtaining limitation, as drafted, is process that covers performance of the limitation in human mind with paper and pen gather data and function limitation is mathematical formulas or equations. The limitation falls within the “mental” process” and/or “mathematical concepts” group of abstract idea.
The steps of “constructing a constructive solid geometry (CSG) model of the 3D object, the CSG model defined by a binary tree wherein nodes of the binary tree define Boolean operations and leaves of the binary tree define parameters of CSG primitives” The broadest reasonable interpretation, constructing limitation, as drafted, covers performance of the limitation in human mind or by hand with pen and paper. The mental process performed by a person with a pen and paper, determining basic primitive shapes (cuboids, cylinders, spheres) and defines how to combine them using boolean operations (union, difference, intersection) by drawing the binary tree structure to represent the order of assembly with internal nodes (operation) and leaf nodes (the primitive shapes and define their parameters (e.g., radius of a cylinder, dimensions of a box, center coordinates). The broadest reasonable interpretation, Boolean operations, parameters limitation, as drafted, is mathematical calculation. The limitation falls within the “mental” process” and/or “mathematical concepts” group of abstract idea. Accordingly, the claim recites an abstract idea.
The steps of “ wherein values of the Boolean operations and values of the parameters of the CSG primitives for the binary tree are identified by minimizing an error between an occupancy function of the CSG model and the groundtruth occupancy function of the 3D object” encompasses mathematical calculation/mathematical relationships/mathematical formulas or equations and can be performed mentally. The mental process performed by a person with a pen and paper, observing and determining parameters (location, size, orientation) of the primitives on paper to match the desired 3D shape. The claim covers performance of limitation in human mind using observation, analyzation and judgment. The broadest reasonable interpretation of values of the Boolean operations and values of the parameters of the CSG primitives for the binary tree are identified , as drafted, is mathematical calculation. The broadest reasonable interpretation of minimizing an error between an occupancy function of the CSG model and the groundtruth occupancy function of the 3D object, as drafted, is mathematic relationship. The limitation falls within the “mental process” and/or “mathematical concepts” group of abstract idea.
This judicial exception is not integrated into a practical application. In particular,
the claim recites additional "constructive solid geometry(CSG), see Figure 4 and
paragraph [0036] " In CSG, the basic building blocks are simple geometric shapes (such as cubes, spheres, cylinders, cones, etc.) referred to as primitives. Complex objects are created by combining primitives using Boolean operations (e.g., union, intersection, and difference).” Constructive solid geometry is tree structure that a human could mentally perform with a pen and paper using mathematical calculation. Accordingly, the claim as a whole does not integrate this judicial exception into a practical application because the claim does not prove an improvement to functioning of computers or an improvement to other technology or technical field. The claim is directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Claim 2 depends from claim 1 recites “wherein the Boolean operations correspond to unified fuzzy Boolean operators that are differentiable with respect to a type of Boolean operator” encompasses mathematical calculation and can be performed mentally. The claim covers performance of limitation in human mind with pen and paper that calculate unified fuzzy Boolean operations that are differentiable with respect to the operator type. The limitation falls within the ”mental process” and/or "mathematical concepts" group of abstract idea.
This judicial exception is not integrated into a practical application because the
claim does not recite any additional elements beyond the judicial exception.
Accordingly, the claim as a whole does not integrate this judicial exception into a
practical application because the claim does not prove an improvement to functioning of
computers or an improvement to other technology or technical field. The claim is
directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Claim 3 depends from claim 2, recites “wherein the unified fuzzy Boolean operators are defined by a tetrahedral barycentric interpolation scheme, based on barycentric coordinates that specify a position between binary Boolean operations that define a tetrahedron” encompasses mathematical calculation. The claim covers performance of limitation in human mind with pen and paper by defining a tetrahedron, calculating barycentric coordinates for a point inside it, and using those to interpolate between four fundamental Boolean operations (e.g., Union, Intersection, Difference) mapped to the vertices. The limitation falls within the “mental process” and/or "mathematical concepts" group of abstract idea.
This judicial exception is not integrated into a practical application because the
claim does not recite any additional elements beyond the judicial exception.
Accordingly, the claim as a whole does not integrate this judicial exception into a
practical application because the claim does not prove an improvement to functioning of
computers or an improvement to other technology or technical field. The claim is
directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Claim 4 depends from claim 1 recites “wherein the CSG primitives are smooth primitives and the CSG model has an adaptive smoothness controlled by changing respective softness of occupancy functions of the smooth primitives.” encompasses mathematical formulas or equations/mathematical relationship. The broadest reasonable interpretation, the CSG primitives are smooth primitives limitation, as drafted, covers performance of the limitation in human mind with pen and paper. The claim covers performance of limitation in human mind using observation, analyzation and judgment. The broadest reasonable interpretation of the CSG model has an adaptive smoothness controlled by changing respective softness of occupancy functions of the smooth primitives is mathematical formulas or equations /mathematical relationship. The limitation falls within the ”mental process” and "mathematical concepts" group of abstract idea.
This judicial exception is not integrated into a practical application because the
claim does not recite any additional elements beyond the judicial exception.
Accordingly, the claim as a whole does not integrate this judicial exception into a
practical application because the claim does not prove an improvement to functioning of
computers or an improvement to other technology or technical field. The claim is
directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Claim 5 depends from claim 4 recites “wherein the CSG primitives are represented as signed distance functions, and further comprising converting the signed distance functions into occupancy functions using a sigmoid function based on a sharpness parameter” encompasses mathematical equation/mathematical calculation. The broadest reasonable interpretation of the CSG primitives are represented as signed distance functions is mathematical formulas or equations. The broadest reasonable interpretation of converting the signed distance functions into occupancy functions using a sigmoid function based on a sharpness parameter is mathematical calculation. The limitation falls within the "mathematical concepts" group of abstract idea.
This judicial exception is not integrated into a practical application because the
claim does not recite any additional elements beyond the judicial exception.
Accordingly, the claim as a whole does not integrate this judicial exception into a
practical application because the claim does not prove an improvement to functioning of
computers or an improvement to other technology or technical field. The claim is
directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Claim 6 depends from claim 5 recites “wherein the respective softness of the occupancy functions of the smooth primitives is controlled by a temperature parameter of the sigmoid function” encompasses mathematical formulas or equations /mathematical calculation. The limitation falls within the "mathematical concepts" group of abstract idea.
This judicial exception is not integrated into a practical application because the
claim does not recite any additional elements beyond the judicial exception.
Accordingly, the claim as a whole does not integrate this judicial exception into a
practical application because the claim does not prove an improvement to functioning of
computers or an improvement to other technology or technical field. The claim is
directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Claim 7 depends from claim 1 recites “wherein the groundtruth occupancy function of the 3D object is obtained from a visual hull representation of the 3D object that is generated based on a mesh corresponding to the 3D object” may be practically performing in human main with pen and paper. The claim covers performance of limitation in human mind using observation, analyzation and judgment. The broadest reasonable interpretation of the groundtruth occupancy function of the 3D object is mathematical formulas or equations. The limitation falls within the ”mental process” and "mathematical concepts" group of abstract idea.
This judicial exception is not integrated into a practical application because the
claim does not recite any additional elements beyond the judicial exception.
Accordingly, the claim as a whole does not integrate this judicial exception into a
practical application because the claim does not prove an improvement to functioning of
computers or an improvement to other technology or technical field. The claim is
directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Claim 8 depends from claim 1 recites:
The steps of “initializing the binary tree with random parameter values” may be practically performing in human main with pen and paper. The claim covers performance of limitation in human mind using observation, analyzation and judgment. The limitation falls within the ”mental process” group of abstract idea.
The steps of “wherein minimizing the error comprises iteratively modifying the values of the Boolean operations and the values of the parameters of the CSG primitives in the binary tree until the error between the occupancy function of the CSG model and the groundtruth occupancy function of the 3D object is less than a threshold value” encompasses mathematical calculation/mathematical formulas or equation/ mathematical relationships that can be performed mentally. The mental process performed by a person with a pen and paper, observing and determining parameters (location, size, orientation) of the primitives on paper to match the desired 3D shape. The claim covers performance of limitation in human mind using observation, analyzation and judgment. The broadest reasonable interpretation of modifying the values of the Boolean operations and the values of the parameters of the CSG is mathematic calculation. The broadest reasonable interpretation of “the occupancy function of the CSG model and the groundtruth occupancy function of the 3D object” is mathematic formulas or equations. The broadest reasonable interpretation of “less than a threshold value” is mathematic relationship. The limitations fall within the ”mental process” and "mathematical concepts" group of abstract idea.
This judicial exception is not integrated into a practical application because the
claim does not recite any additional elements beyond the judicial exception.
Accordingly, the claim as a whole does not integrate this judicial exception into a
practical application because the claim does not prove an improvement to functioning of
computers or an improvement to other technology or technical field. The claim is
directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Claim 9 depends from claim 8 recites “wherein minimizing the error is performed using adaptive moment estimation (ADAM)” encompasses mathematical calculation and mathematical relationships. ADAM is optimization algorithm using a series of mathematical calculations. The limitation falls within the "mathematical concepts" group of abstract idea.
This judicial exception is not integrated into a practical application because the
claim does not recite any additional elements beyond the judicial exception.
Accordingly, the claim as a whole does not integrate this judicial exception into a
practical application because the claim does not prove an improvement to functioning of
computers or an improvement to other technology or technical field. The claim is
directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Claim 10 depends from claim 1 recites “wherein the CSG primitives are selected from the group comprising: spheres, planes, quadric surfaces, multilayer perceptrons (MLPs), and combinations thereof” may be practically performing in human mind with pen and paper. The broadest reasonable interpretation, selecting limitation, as drafted, is process that covers performance of the limitation in human mind using observation and performing determination. The limitation falls within the "mental process" group of abstract idea.
This judicial exception is not integrated into a practical application because the
claim does not recite any additional elements beyond the judicial exception.
Accordingly, the claim as a whole does not integrate this judicial exception into a
practical application because the claim does not prove an improvement to functioning of
computers or an improvement to other technology or technical field. The claim is
directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Claim 14 depends from claim 1 recites:
The step of “pruning the binary tree to remove redundant subtrees to obtain a pruned binary tree by visiting nodes in the tree in post-order and deleting redundant nodes” may be practically performing in human mind with pen and paper. The broadest reasonable interpretation, selecting limitation, as drafted, is process that covers performance of the limitation in human mind using observation, determination and judgment. The limitation falls within the "mental process" group of abstract idea.
Claim recites “ wherein a node is redundant when replacement of the node with a full object or an empty object results in a difference in an output of a Boolean operation associated with the node in the binary tree that satisfies a threshold” compass encompasses mathematical calculation/mathematical relationships that can be performed mentally. The mental process performed by a person with a pen and paper using observation, analyzation and judgment. The limitation falls within the ”mental process” and "mathematical concepts" group of abstract idea.
This judicial exception is not integrated into a practical application because the
claim does not recite any additional elements beyond the judicial exception.
Accordingly, the claim as a whole does not integrate this judicial exception into a
practical application because the claim does not prove an improvement to functioning of
computers or an improvement to other technology or technical field. The claim is
directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Claim 15 depends from claim 14 recites “further comprising traversing the pruned binary tree using a linear time traversal algorithm on a forward pass in post-order using a stack when using the pruned binary tree to infer properties of the CSG model of the 3D object” encompasses mathematical calculation/mathematical relationships that can be performed mentally. The mental process performed by a person with a pen and paper using observation, analyzation and judgment. he broadest reasonable interpretation of using a linear time traversal algorithm as drafted, is process that covers mathematical calculation The limitation falls within the ”mental process” and "mathematical concepts" group of abstract idea.
This judicial exception is not integrated into a practical application because the
claim does not recite any additional elements beyond the judicial exception.
Accordingly, the claim as a whole does not integrate this judicial exception into a
practical application because the claim does not prove an improvement to functioning of
computers or an improvement to other technology or technical field. The claim is
directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Regarding independent claim 16, the claim recites “a non-transitory computer-readable medium with instructions stored thereon that, responsive to execution by a processing device, cause the processing device to perform operations comprising: obtaining a groundtruth occupancy function descriptive of a three-dimensional (3D) object; and constructing a constructive solid geometry (CSG) model of the 3D object, the CSG model defined by a binary tree wherein nodes of the binary tree define Boolean operations and leaves of the binary tree define parameters of CSG primitives, wherein values of the Boolean operations and values of the parameters of the CSG primitives for the binary tree are identified by minimizing an error between an occupancy function of the CSG model and the groundtruth occupancy function of the 3D object” which is manufacture and falls within one of the statutory categories of invention.
The claim recites:
The steps of “obtaining a groundtruth occupancy function descriptive of a three-dimensional (3D) object” is mere data gathering/mathematical formula/equation. The broadest reasonable interpretation, obtaining limitation, as drafted, is process that covers performance of the limitation in human mind with paper and pen gather data and function limitation is mathematical formulas or equations. The limitation falls within the “mental” process” and/or “mathematical concepts” group of abstract idea.
The steps of “constructing a constructive solid geometry (CSG) model of the 3D object, the CSG model defined by a binary tree wherein nodes of the binary tree define Boolean operations and leaves of the binary tree define parameters of CSG primitives” The broadest reasonable interpretation, constructing limitation, as drafted, covers performance of the limitation in human mind or by hand with pen and paper. The mental process performed by a person with a pen and paper, determining basic primitive shapes (cuboids, cylinders, spheres) and defines how to combine them using boolean operations (union, difference, intersection) by drawing the binary tree structure to represent the order of assembly with internal nodes (operation) and leaf nodes (the primitive shapes and define their parameters (e.g., radius of a cylinder, dimensions of a box, center coordinates). The broadest reasonable interpretation, Boolean operations, parameters limitation, as drafted, is mathematical calculation. The limitation falls within the “mental” process” and/or “mathematical concepts” group of abstract idea. Accordingly, the claim recites an abstract idea.
Claim further recites “ wherein values of the Boolean operations and values of the parameters of the CSG primitives for the binary tree are identified by minimizing an error between an occupancy function of the CSG model and the groundtruth occupancy function of the 3D object” encompasses mathematical calculation/mathematical relationships/mathematical equation that can be performed mentally. The mental process performed by a person with a pen and paper, observing and determining parameters (location, size, orientation) of the primitives on paper to match the desired 3D shape. The claim covers performance of limitation in human mind using observation, analyzation and judgment. The broadest reasonable interpretation of values of the Boolean operations and values of the parameters of the CSG primitives for the binary tree are identified , as drafted, is mathematical calculation. The broadest reasonable interpretation of minimizing an error between an occupancy function of the CSG model and the groundtruth occupancy function of the 3D object, as drafted, is mathematic relationship. The limitation falls within the “mental process” and/or “mathematical concepts” group of abstract idea.
This judicial exception is not integrated into a practical application. In particular,
the claim recites additional "constructive solid geometry(CSG), see Figure 4 and
paragraph [0036] " In CSG, the basic building blocks are simple geometric shapes (such as cubes, spheres, cylinders, cones, etc.) referred to as primitives. Complex objects are created by combining primitives using Boolean operations (e.g., union, intersection, and difference).” Constructive solid geometry is tree structure that a human could mentally perform with a pen and paper using mathematical calculation.
Further, the claim recites additional elements: “a non-transitory computer-readable medium with instructions stored thereon that, responsive to execution by a processing device, cause the processing device to perform operations “ which is considered as components of computer to perform functions/operations steps. Using a generic computer components cannot provide an invention concepts. Accordingly, the claim as a whole does not integrate this judicial exception into a practical application because the claim does not prove an improvement to functioning of computers or an improvement to other technology or technical field. The claim is directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Claim 17 depends from claim 16 recites limitations is similar in scope to claim 2 and therefore rejected under the same rationale.
Claim 18 depends from claim 16 recites limitations is similar in scope to claim 8 and therefore rejected under the same rationale.
Regarding independent claim 19 recites “a system comprising: a memory with instructions stored thereon; and a processing device, coupled to the memory, the processing device configured to access the memory and execute the instructions, wherein the instructions cause the processing device to perform operations comprising: obtaining a groundtruth occupancy function descriptive of a three-dimensional (3D) object; and constructing a constructive solid geometry (CSG) model of the 3D object, the CSG model defined by a binary tree wherein nodes of the binary tree define Boolean operations and leaves of the binary tree define parameters of CSG primitives, wherein values of the Boolean operations and values of the parameters of the CSG primitives for the binary tree are identified by minimizing an error between an occupancy function of the CSG model and the groundtruth occupancy function of the 3D object” which is machine and falls within one of the statutory categories of invention.
The claim recites:
The steps of “obtaining a groundtruth occupancy function descriptive of a three-dimensional (3D) object” is mere data gathering/mathematical formula/equation. The broadest reasonable interpretation, obtaining limitation, as drafted, is process that covers performance of the limitation in human mind with paper and pen gather data and function limitation is mathematical formulas or equations. The limitation falls within the “mental” process” and/or “mathematical concepts” group of abstract idea.
The steps of “constructing a constructive solid geometry (CSG) model of the 3D object, the CSG model defined by a binary tree wherein nodes of the binary tree define Boolean operations and leaves of the binary tree define parameters of CSG primitives” The broadest reasonable interpretation, constructing limitation, as drafted, covers performance of the limitation in human mind or by hand with pen and paper. The mental process performed by a person with a pen and paper, determining basic primitive shapes (cuboids, cylinders, spheres) and defines how to combine them using boolean operations (union, difference, intersection) by drawing the binary tree structure to represent the order of assembly with internal nodes (operation) and leaf nodes (the primitive shapes and define their parameters (e.g., radius of a cylinder, dimensions of a box, center coordinates). The broadest reasonable interpretation, Boolean operations, parameters limitation, as drafted, is mathematical calculation. The limitation falls within the “mental” process” and/or “mathematical concepts” group of abstract idea. Accordingly, the claim recites an abstract idea.
Claim further recites “ wherein values of the Boolean operations and values of the parameters of the CSG primitives for the binary tree are identified by minimizing an error between an occupancy function of the CSG model and the groundtruth occupancy function of the 3D object” encompasses mathematical calculation/mathematical relationships/mathematical equation that can be performed mentally. The mental process performed by a person with a pen and paper, observing and determining parameters (location, size, orientation) of the primitives on paper to match the desired 3D shape. The claim covers performance of limitation in human mind using observation, analyzation and judgment. The broadest reasonable interpretation of values of the Boolean operations and values of the parameters of the CSG primitives for the binary tree are identified , as drafted, is mathematical calculation. The broadest reasonable interpretation of minimizing an error between an occupancy function of the CSG model and the groundtruth occupancy function of the 3D object, as drafted, is mathematic relationship. The limitation falls within the “mental process” and/or “mathematical concepts” group of abstract idea.
This judicial exception is not integrated into a practical application. In particular,
the claim recites additional "constructive solid geometry(CSG), see Figure 4 and
paragraph [0036] " In CSG, the basic building blocks are simple geometric shapes (such as cubes, spheres, cylinders, cones, etc.) referred to as primitives. Complex objects are created by combining primitives using Boolean operations (e.g., union, intersection, and difference).” Constructive solid geometry is tree structure that a human could mentally perform with a pen and paper using mathematical calculation.
Further, the claim recites additional elements: “a memory with instructions stored thereon; and a processing device, coupled to the memory, the processing device configured to access the memory and execute the instructions, wherein the instructions cause the processing device to perform operations “ which is considered as components of computer to perform functions/operations steps. Using a generic computer components cannot provide an invention concepts. Accordingly, the claim as a whole does not integrate this judicial exception into a practical application because the claim does not prove an improvement to functioning of computers or an improvement to other technology or technical field. The claim is directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to
significantly more than the judicial exception. The claim is not patent eligible.
Claim 20 depends from claim 19 recites limitations is similar in scope to claim 2 and therefore rejected under the same rationale.
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.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
1. Claims 1,4, 10, 16, 19 are rejected under 35 U.S.C. 103 as being unpatentable over Mehr et al, U.S Patent Application Publication No.2020/0250894 (“Mehr”) in view of KANIA et al, IDS, 2020 UCSG-NET-unsupervised discovering of constructive solid geometry tree Advances in Neural Information Processing Systems 33 (2020), 8776-8786 (“Kania”)
Regarding independent claim 1, Mehr teaches a computer-implemented method, comprising:
constructing a constructive solid geometry (CSG) model of the 3D object the CSG model defined by a binary tree wherein nodes of the binary tree define Boolean operations and leaves of the binary tree define parameters of CSG primitives ([0062] As known from the field of CAD, an editable feature tree is herein an editable data structure which comprises data representing a tree arrangement of geometrical operations applied to leaf geometrical shapes. Each leaf node of the tree arrangement represents a respective leaf geometrical shape, and each non-leaf node of the tree arrangement represents a respective geometrical operation, also called “feature”, to be applied to its child node(s). Applying the tree arrangement of geometrical operations to the leaf geometrical shapes thus amounts to starting with the leaf geometrical shapes, and successively applying the geometrical operation of each non-leaf node following the tree arrangement. The 3D shape represented by the editable feature tree corresponds to the result of the root node(s) of the editable feature tree.” [0063] The leaf geometrical shapes may be of any type. The leaf geometrical shapes may, for example, each comprise (e.g. consist of) a respective 3D shape, such as a respective 3D solid. The geometrical operations may be of any type. In examples, the geometrical operations are all of a same type, for example all the addition/union operation. In such examples, the inference method may be configured to infer editable feature trees restricted to those with only said single type of geometrical operation. In alternative and finer examples, the geometrical operations may comprise operations of different types, for example different Boolean operation types (i.e. binary and continuous operators e.g. which, to two 3D shapes, associate a new 3D shape), including the addition union operation type, the subtraction operation type, and/or the intersection operation type. In such examples, the inference method may be configured to infer editable feature trees with all types of geometrical operations available. Any editable feature tree herein may notably be a Constructive Solid Geometry (CSG) tree, known from the field of solid modeling. In particularly accurate examples, the inference method is configured to infer CSG trees only. The tree arrangement may be of any type. Any editable feature tree herein may notably be a single-rooted tree, a binary tree, and/or a full binary tree (i.e. a binary tree of the type where each non-leaf node has at least one leaf node as a child);[0203] In the first step, the example machine-learning process generates a synthetic dataset of CSG trees. The trees are sequences of primitives interleaved with a Boolean operation between each primitive. Each Boolean operation is a binary operator which applies onto the following primitive and the result of the previous operation. The three usual Boolean operations are addition/subtraction/intersection. Thus, each primitive in the sequence is (added/intersected/subtracted) to the current result of the sequence, as illustrated in FIG. 3. [0204] Primitives belong to a set of base types (labeled as (1, . . . ,4 such as cuboids, cylinders, prisms, etc, Each primitive type has its own set of continuous parameters (for instance, the size and position of a cuboid). [0205] To sample a CSG tree, the example machine-learning process randomly samples its depth, primitive types, and Boolean operations. For each primitive, the example machine-learning process also samples its continuous parameters. The example machine-learning process thus gets a random CSG tree. This CSG can be turned into a raw mesh by applying its Boolean operations sequentially to its sequence of primitives”) , wherein values of the Boolean operations and values of the parameters of the CSG primitives for the binary tree are identified by minimizing an error ([0045] In examples improving accuracy, the inference method may further comprise refining each (initially) inferred editable feature tree, for example automatically. The refining may comprise editing the inferred editable feature tree (for example parameters thereof) in order to make its resulting 3D geometry (e.g. obtainable by “playing” editable feature tree) more similar to the input discrete geometrical representation. The similarity may be increased by minimizing a loss which penalizes a disparity between the 3D geometry provided by the inferred editable feature tree and the input discrete geometrical representation. Minimizing the loss may comprise exploring candidate editions of the initially inferred editable feature tree, for example editions of leaf geometrical shapes thereof. Examples of such editions are provided later. This refinement option improves accuracy by exploiting a fact specific to the context of the present disclosure. Namely, the refinement exploits the fact that an editable feature tree can be used to compute a 3D geometry directly comparable to the discrete geometrical representation, for example by playing the editable feature tree (i.e. applying the geometrical operations of the editable feature tree to the leaf geometrical shapes of the editable feature tree in the order defined by the tree arrangement of the editable feature tree). In other words, accuracy of an output of the neural network can be directly and immediately assessed.”; [0186] An example of a loss for a supervised training which leads to an accurate result penalizes, for the time step respective to each leaf geometrical shape of each discrete geometrical representation (each discrete geometrical representation being here associated to a respective ground truth editable feature tree), one or both of the following quantities: [0187] a lowness of the probability of the respective first data attributed to the respective primitive shape type of the corresponding ground truth leaf geometrical shape, and/or [0188] a disparity between the one or more respective parameter values of the corresponding ground truth leaf geometrical shape and the one or more respective parameter values of the respective second data. In other words, the supervised training may, by minimizing such a loss, act on the weights of the neural network so as to tend to make the respective probabilities outputted by each RNN cell close to 1 (i.e. not low) for the corresponding ground truth primitive shape type and close to 0 (i.e. low) for the other primitive shape types, and/or to make the respective continuous parameter values outputted by each cell close to their ground truth values. Such a loss handles accurately the discrete/continuous mixture of the problem.[0189] In options of this example, the loss may further similarly penalize, for the time step respective to each leaf geometrical shape of each discrete geometrical representation, one or both of the additional quantities: [0190] a lowness of the respective probability (outputted by an RNN cell) attributed to the corresponding ground truth geometrical operation, and/or [0191] a lowness of the probability (outputted by an RNN cell) to reach the tree arrangement (e.g. depth or length) of the corresponding ground truth editable feature tree based on the respective data for inference of the end token.” [0228-0235] The loss that the example machine-learning process minimizes to train the weights of the network (using standard deep learning techniques, such as ADAM solver over mini-batches) may the following:); Mehr is understood to be silent on the remaining limitations of claim 1.
In the same field of endeavor, Kania teaches obtaining a groundtruth occupancy function descriptive of a three-dimensional (3D) object (see at least section 2. Method, Signed Distance Field to Indicator Function Converter, “ CSG operations in SDF representation are often defined as a combination of min and max functions on distance values. One has to apply either LogSumExp operation as in CVXNET or standard Softmax function to obtain differentiable approximation. However, we cast our problem to predict CSG operations for occupancy-valued sets. The motivation is that these are linear operations, hence they provide better training stability. Wetransform signed distances D to occupancy values O ∈ {0,1}. We use parametrized α clipping function that is learned with the rest of the pipeline: O= 1−D α [0,1] inside, O=1 outside, O ∈[0,1) (1) where α is a learnable scalar and α > 0, [·][0,1] clips values to the given range and O means an approximation of occupancy values. O = 1 indicates the inside and the surface of a shape. O ∈ [0,1) means outside of the shape and limα→0 O ∈ {0,1}. Gradual learning of α allows to distribute gradients to all shapes in early stages of training. There are no specific restrictions for α initialization and we set α = 1 in our experiments. The value is pushed towards 0 by optimizing jointly with the rest of parameters by adding the |α| term to the optimized loss. The method follows findings of Sakr et al. [9] that increasing slope of clipping function can be used to obtain binary activations.”; First stage The goal is to find compositions of primitives that minimize the reconstruction error. We employ mean squared error of predicted occupancy values ˆ O(L) with the ground truth O∗. Values are calculated for X which combines points sampled from the surface of the ground truth, and randomly sampled inside a unit cube (or square for 2D case);
constructing a constructive solid geometry (CSG) model of the 3D object, the CSG model defined by a binary tree wherein nodes of the binary tree define Boolean operations and leaves of the binary tree define parameters of CSG primitives (see at least Figures 2-4,6, Primitive parameter prediction network , “The role of this component is to extract the parameters of the primitives, given the latent representation of the input object. The primitive parameter prediction network gφ consists of multiple fully connected layers interleaved with activation functions. The last layer predicts parameters of primitives in the SDF representation. We consider primitives such as boxes and spheres that allow us to calculate signed distance analytically. We note that planes can be used as well, thus extending approaches like BSP-NET [5] and CVXNET [6]. The mathematical formulation of used shapes is provided in the supplementary material. The network produces N tuples of {i ∈ N|pi,ti,qi}. pi ∈ Rdp describes vector of parameters of a particular shape (ex. radius of a sphere), while ti ∈ Rdt is the translation of the shape and qi ∈ Rdq- the rotation represented as a quaternion for 3D shapes and a matrix for 2D shapes. We further combine k different shapes to be predicted by using a fully connected layer for each shape type separately, thus producing kN = M shapes and M ×(dp +dt +dq)parameters in total. Once parameters are predicted, we use them to calculate signed distance values for sampled points x from volume of space that boundaries are normalized to unit square (or unit cube for 3D data). For each shape, that has an analytical equation dist parametrized by p that calculates signed distance from a point x to its surface, we obtain Di = dist(q−1 i (x−ti);pi…”), wherein values of the Boolean operations and values of the parameters of the CSG primitives for the binary tree are identified by minimizing an error between an occupancy function of the CSG model and the groundtruth occupancy function of the 3D object (see at least 2.2 Training “The pipeline is optimized end-to-end using a backpropagation algorithm in a two-stage process. First stage The goal is to find compositions of primitives that minimize the reconstruction error. We employ mean squared error of predicted occupancy values ˆ O(L) with the ground truth O∗. Values are calculated for X which combines points sampled from the surface of the ground truth, and randomly sampled inside a unit cube (or square for 2D case): LMSE = Ex∈X[(O(L) −O∗)2] (8) We also ensure that the network predicts only positive values of parameters of shapes since only for such these shapes have analytical descriptions: M LP = i=1pi∈pi max(−pi,0) (9) To stop primitives from drifting away from the center of considered space in the early stages of the training, we minimize the clipped squared norm of the translation vector. At the same time, we allow primitives to be freely translated inside the space of interest: M LT = i=1 max(||ti||2, 0.5) (10) The last component includes minimizing |α| to perform continuous binarization of distances into {inside, outside} indicator values. Our goal is to find optimal parameters of our model by minimizing the total loss: where we set λT = λα = 0.1…”)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to modify the method of editing the inferred editable feature tree of CSG of Mehr with employing mean squared error of predicted occupancy values with the ground truth as seen in Kania because this modification would find compositions of primitives that minimize the reconstruction error (2.2 Training of Kania).
Thus, the combination of Mehr and Kania teaches a computer-implemented method, comprising: obtaining a groundtruth occupancy function descriptive of a three-dimensional (3D) object; and constructing a constructive solid geometry (CSG) model of the 3D object, the CSG model defined by a binary tree wherein nodes of the binary tree define Boolean operations and leaves of the binary tree define parameters of CSG primitives, wherein values of the Boolean operations and values of the parameters of the CSG primitives for the binary tree are identified by minimizing an error between an occupancy function of the CSG model and the groundtruth occupancy function of the 3D object.
Regarding claim 4, Mehr and Kania teach the computer-implemented method of claim 1, wherein the CSG smooth primitives (see at least [0105] of Mehr “In particularly efficient examples in terms of computation time and/or convergence for the learning Versus representativity of the diversity of real situations, the discrete set of primitive shape types may comprise a cuboid type, a sphere type, one or more cylinder types, and/or one or more prism types. In examples, the discrete set of primitive shape types may comprise any one or any combination (e.g. all) of the following types: [0106] cuboid, e.g. parameterized by three positioning parameters and three dimensional parameters; [0107] sphere, e.g. parameterized by three positioning parameters and one dimensional parameter (diameter); [0108] right circular cylinder oriented along the X, Y or Z axis (thus corresponding to three primitive shape types), e.g. parameterized by three positioning parameters, one dimensional parameter representing height, and one dimensional parameter representing diameter; [0109] straight prism with isosceles trapezoidal base oriented along the axes (X, Y), (X, Z), (Y, Z), (Y, X), (Z, X), (Z, Y) (thus corresponding to six primitive shape types), e.g. parameterized by three positioning parameters, one dimensional parameter representing length of the large trapezoid base, one dimensional parameter representing length of the small trapezoid base, one dimensional parameter representing height of the trapezium, one dimensional parameter representing depth of the prism. [0110] The discrete set of primitive shape types may comprise any other primitive shape type, such as unoriented cylinder with three more rotation parameters, polygonal base cylinder, non-straight cylinder, polygonal base prism, non-oriented prism, and/or non-regular polyhedra. are smooth primitives; see section Primitive parameter prediction network of Kania “The role of this component is to extract the parameters of the primitives, given the latent representation of the input object. The primitive parameter prediction network gφ consists of multiple fully connected layers interleaved with activation functions. The last layer predicts parameters of primitives in the SDF representation. We consider primitives such as boxes and spheres that allow us to calculate signed distance analytically. We note that planes can be used as well, thus extending approaches like BSP-NET [5] and CVXNET [6]. The mathematical formulation of used shapes is provided in the supplementary material. The network produces N tuples of {i ∈ N|pi,ti,qi}. pi ∈ Rdp describes vector of parameters of a particular shape (ex. radius of a sphere), while ti ∈ Rdt is the translation of the shape and qi ∈ Rdq- the rotation represented as a quaternion for 3D shapes and a matrix for 2D shapes. We further combine k different shapes to be predicted by using a fully connected layer for each shape type separately, thus producing kN = M shapes and M ×(dp +dt +dq)parameters in total. Once parameters are predicted, we use them to calculate signed distance values for sampled points x from volume of space that boundaries are normalized to unit square (or unit cube for 3D data). For each shape, that has an analytical equation dist parametrized by p that calculates signed distance from a point x to its surface, we obtain Di = dist(q−1 i (x−ti);pi) and the CSG model has an adaptive smoothness controlled by changing respective softness of occupancy functions of the smooth primitives ( see section Constructive Solid Geometry Layer , “Predicted sets of occupancy values and output of the encoder z are passed to a sequence of L ≥ 1 CSG layers that combine shapes using boolean operators: union (denoted by ∪∗), intersection (∩∗) and difference (−∗). To grasp an idea of how CSG is performed on occupancy-valued sets, we show example operations in Figure 2. CSG operations for two sets A and B are described as: A∪∗B =[A+B][0,1] A∩∗B =[A+B−1][0,1] A−∗B =[A−B][0,1] B−∗A=[B−A][0,1] (2) The question is how to choose operands A and B, denoted as left and right operands, from input shapes O(l) that would compose the output shape in O(l+1). We create two learnable matrices K(l) left, K(l) right ∈ RM× dz. Vectors stored in rows of these matrices serve as keys for a query z to select appropriate shapes for all 4 operations. The input latent code z is used as a query to retrieve the most appropriate operand shapes for each layer. We perform dot product between matrices K(l) left, K(l) right and z, and compute softmax along M input shapes…. where Cᵢ is a sample from Gumbel(0, 1). The benefit of the reparametrization is twofold. Firstly, the expectation over the distribution stays the same despite changing π⁽⁾. Secondly, we can manipulate τ⁽⁾ so for τ⁽¹⁾ 0 the distribution degenerates to categorical distribution. Hence, a single shape selection replaces the fuzzy sum of all input shapes in that case. That way, we allow the network to select the most appropriate shape for the composition during learning by decreasing T¹⁾ gradually. By the end of the learning process, we can retrieve a single shape to be used for the CSG. The temperature τ⁽¹⁾ is learned jointly with the rest of the parameters.”) In addition, the same motivation is used as the rejection for claim 1.
Regarding claim 10, Mehr and Kania teach the computer-implemented method of claim 1, wherein the CSG primitives are selected from the group comprising: spheres, planes, quadric surfaces, multilayer perceptrons (MLPs), and combinations thereof (see at least Mehr: [0025] the discrete set of primitive shape types comprises a cuboid type, a sphere type, one or more cylinder types, and/or one or more prism types; section Primitive parameter prediction network of Kania , “The role of this component is to extract the parameters of the primitives, given the latent representation of the input object. The primitive parameter prediction network gφ consists of multiple fully connected layers interleaved with activation functions. The last layer predicts parameters of primitives in the SDF representation. We consider primitives such as boxes and spheres that allow us to calculate signed distance analytically”; ) In addition, the same motivation is used as the rejection for claim 1.
Regarding independent claim 16, Mehr teaches a non-transitory computer-readable medium with instructions stored thereon that, responsive to execution by a processing device, cause the processing device to perform operations ( see at least [0042] It is further provided a device comprising a data storage medium having recorded thereon the data structure and/or the program. The device may form or serve as a non-transitory computer-readable medium, for example on a SaaS (Software as a service) or other server, or a cloud based platform, or the like. The device may alternatively comprise a processor coupled to the data storage medium. [0106] Any computer program herein may comprise instructions executable by a computer, the instructions comprising means for causing the above system to perform the method. The program may be recordable on any data storage medium, including the memory of the system. The program may for example be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations of them. The program may be implemented as an apparatus, for example a product tangibly embodied in a machine-readable storage device for execution by a programmable processor. Method steps may be performed by a programmable processor executing a program of instructions to perform functions of the method by operating on input data and generating output. The processor may thus be programmable and coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system, at least one input device, and at least one output device. The application program may be implemented in a high-level procedural or object-oriented programming language, or in assembly or machine language if desired. In any case, the language may be a compiled or interpreted language. The program may be a full installation program or an update program. Application of the program on the system results in any case in instructions for performing the method”)comprising: Remaining limitations of claim 16 is similar in scope to claim 1 and therefore rejected under the same rationale.
Regarding independent claim 19, Mehr teaches a system comprising: a memory with instructions stored thereon; and a processing device, coupled to the memory, the processing device configured to access the memory and execute the instructions, wherein the instructions cause the processing device to perform operations (see at least [0100] A typical example of computer-implementation of a method is to perform the method with a system adapted for this purpose. The system may comprise a processor coupled to a memory and a graphical user interface (GUI), the memory having recorded thereon a computer program comprising instructions for performing the method. The memory may also store a database. The memory is any hardware adapted for such storage, possibly comprising several physical distinct parts (e.g. one for the program, and possibly one for the database)”; [0106]) comprising: Remaining limitations of claim 19 is similar in scope to claim 1 and therefore rejected under the same rationale.
2. Claims 2, 17 and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Mehr et al, U.S Patent Application Publication No.2020/0250894 (“Mehr”) in view of KANIA et al, IDS, 2020 UCSG-NET-unsupervised discovering of constructive solid geometry tree Advances in Neural Information Processing Systems 33 (2020), 8776-8786 (“Kania”) further in view of Gielis et al., U.S Patent Application Publication No. 20050140678 (“Gielis”)
Regarding claim 2, Mehr and Kania teach the computer-implemented method of claim 1, wherein the Boolean operations that are respect to a type of Boolean operator (see at least Mehr 0183] In alternative or additional options, each RNN cell may take as an (additional) input a result of a current predicted sequence (feedback loop). This improves accuracy. The feedback loop is possible, because thanks to the continuous parameters involved, the entry of the feedback loop is differentiable. In such options, the neural network may comprise a predetermined geometric modeler (i.e. static, that is, not learnt, in other words not comprising any modifiable weights), applied to the result of each RNN cell for computing a current predicted sequence. The modeler may be any data structure providing a mapping between an editable feature tree and a representation thereof (for example a multi-channel rendering). The geometric modeler may comprise a scheme for playing the editable feature tree and then extracting a representation of the resulting 3D shape. [0203] In the first step, the example machine-learning process generates a synthetic dataset of CSG trees. The trees are sequences of primitives interleaved with a Boolean operation between each primitive. Each Boolean operation is a binary operator which applies onto the following primitive and the result of the previous operation. The three usual Boolean operations are addition/subtraction/intersection. Thus, each primitive in the sequence is (added/intersected/subtracted) to the current result of the sequence, as illustrated in FIG. 3. [0204] Primitives belong to a set of base types (labeled as (1, . . . ,4 such as cuboids, cylinders, prisms, etc, Each primitive type has its own set of continuous parameters (for instance, the size and position of a cuboid). [0205] To sample a CSG tree, the example machine-learning process randomly samples its depth, primitive types, and Boolean operations. For each primitive, the example machine-learning process also samples its continuous parameters. The example machine-learning process thus gets a random CSG tree. This CSG can be turned into a raw mesh by applying its Boolean operations sequentially to its sequence of primitives “; Kania :section 2.1 Constructive Solid Geometry Network, Constructive Solid Geometry Layer, 5 Conclusions We demonstrate UCSG-NET- an unsupervised method for discovering constructive solid geometry parse trees that composes primitives to reconstruct an input shape. Our method predicts CSG trees and is able to use different Boolean operations while maintaining reasonable accuracy of reconstructions. Inferred CSG trees are used to form meshes directly, without the need to use explicit reconstruction methods for implicit representations. We show that these trees can be easily visualized, thus providing interpretability about reconstructions step-by-step. Therefore, the method can be applied in CAD applications for quick prototyping of 3D objects.). In addition, the same motivation is used as the rejection for claim 1. Both Mehr and Kania are understood to be silent on the remaining limitations of claim 2.
In the same field of endeavor, Gielis teaches wherein the Boolean operations correspond to unified fuzzy Boolean operators that are differentiable with respect to a type of Boolean operator ([0145] In addition, for implicit objects a number of operations, such as range operations (such as, e.g. density change or complements), domain operations (such as, e.g., affine mappings or (physically based) deformations), blend operations and combinations (such as, e.g., n-ary operations such as CSG) are straightforward. For characterization of points, point-membership classification is straightforward using either equality or inequalities. Using inequalities, density maps (such as, e.g., colors, heights, etc.) are easily defined. Since SUPERFORMULA 3D shapes can be expressed as implicit functions all of the above and other operations can be performed with SUPERSHAPES. [0146] In that regard, differentiable n-ary operations based on R-functions, such as differentiable Boolean operations can be implemented directly. R-functions are in fact real functions of real variables, and they allow one to write an equation for a domain of a shape in the same way as one writes a logical expression. So, for any volume V, a real continuous (and differentiable) function can be written that is positive inside, zero on and negative outside the shape. The surfaces can then be used, for example, to solve boundary problems. Since for R-functions one has to use implicit functions, they are currently not widely used because of the widespread use of parametric curves. Thus, SUPERSHAPES in two and/or three D greatly enhance the capabilities of R-functions and modelling, allowing for compact analytic expressions of composite shapes [0147] As the SUPERFORMULA allows for both parametric expression and implicit function, the advantages of both, namely enumeration and classification of points, can be combined. This variety of possible operations and basic representations makes the SUPERFORMULA one of the most powerful shape representations, and certainly, a very uniform representation too.”)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to modify the method of editing the inferred editable feature tree of CSG of Mehr and Kania with implementing differentiable Boolean operations as seen in Gielis because this modification would allow for compact analytic expressions of composite shapes ([0146] of Gielis)
Thus, the combination of Mehr, Kania and Gielis teaches wherein the Boolean operations correspond to unified fuzzy Boolean operators that are differentiable with respect to a type of Boolean operator.
Regarding claim 17, Mehr and Kania teach the non-transitory computer-readable medium of claim 16, Remaining limitations of claim 17 is similar in scope to claim 2 and therefore rejected under the same rationale.
Regarding claim 20, Mehr and Kania teach the system of claim 19, Remaining limitations of claim 20 is similar in scope to claim 2 and therefore rejected under the same rationale.
3 Claim 3 is rejected under 35 U.S.C. 103 as being unpatentable over Mehr et al, U.S Patent Application Publication No.2020/0250894 (“Mehr”) in view of KANIA et al, IDS, 2020 UCSG-NET-unsupervised discovering of constructive solid geometry tree Advances in Neural Information Processing Systems 33 (2020), 8776-8786 (“Kania”) f further in view of Gielis et al., U.S Patent Application Publication No. 20050140678 (“Gielis”) further in view of Klinger ,U.S Patent Application Publication No.2019/0243017 (“Klinger”)
Regarding claim 3, Mehr, Kania and Gielis teach the computer-implemented method of claim 2, wherein the unified fuzzy Boolean operators are defined by a tetrahedral scheme, based on coordinates that specify a position between binary Boolean operations that define a tetrahedron (wherein the Boolean operations that are respect to a type of Boolean operator (see at least Mehr 0183] In alternative or additional options, each RNN cell may take as an (additional) input a result of a current predicted sequence (feedback loop). This improves accuracy. The feedback loop is possible, because thanks to the continuous parameters involved, the entry of the feedback loop is differentiable. In such options, the neural network may comprise a predetermined geometric modeler (i.e. static, that is, not learnt, in other words not comprising any modifiable weights), applied to the result of each RNN cell for computing a current predicted sequence. The modeler may be any data structure providing a mapping between an editable feature tree and a representation thereof (for example a multi-channel rendering). The geometric modeler may comprise a scheme for playing the editable feature tree and then extracting a representation of the resulting 3D shape. [0203] In the first step, the example machine-learning process generates a synthetic dataset of CSG trees. The trees are sequences of primitives interleaved with a Boolean operation between each primitive. Each Boolean operation is a binary operator which applies onto the following primitive and the result of the previous operation. The three usual Boolean operations are addition/subtraction/intersection. Thus, each primitive in the sequence is (added/intersected/subtracted) to the current result of the sequence, as illustrated in FIG. 3. [0204] Primitives belong to a set of base types (labeled as (1, . . . ,4 such as cuboids, cylinders, prisms, etc, Each primitive type has its own set of continuous parameters (for instance, the size and position of a cuboid). [0205] To sample a CSG tree, the example machine-learning process randomly samples its depth, primitive types, and Boolean operations. For each primitive, the example machine-learning process also samples its continuous parameters. The example machine-learning process thus gets a random CSG tree. This CSG can be turned into a raw mesh by applying its Boolean operations sequentially to its sequence of primitives “; Kania :section 2.1 Constructive Solid Geometry Network, Constructive Solid Geometry Layer, 5 Conclusions We demonstrate UCSG-NET- an unsupervised method for discovering constructive solid geometry parse trees that composes primitives to reconstruct an input shape. Our method predicts CSG trees and is able to use different Boolean operations while maintaining reasonable accuracy of reconstructions. Inferred CSG trees are used to form meshes directly, without the need to use explicit reconstruction methods for implicit representations. We show that these trees can be easily visualized, thus providing interpretability about reconstructions step-by-step. Therefore, the method can be applied in CAD applications for quick prototyping of 3D object [0146] of Gieli “In that regard, differentiable n-ary operations based on R-functions, such as differentiable Boolean operations can be implemented directly. R-functions are in fact real functions of real variables, and they allow one to write an equation for a domain of a shape in the same way as one writes a logical expression. So, for any volume V, a real continuous (and differentiable) function can be written that is positive inside, zero on and negative outside the shape. The surfaces can then be used, for example, to solve boundary problems. Since for R-functions one has to use implicit functions, they are currently not widely used because of the widespread use of parametric curves. Thus, SUPERSHAPES in two and/or three D greatly enhance the capabilities of R-functions and modelling, allowing for compact analytic expressions of composite shapes) In addition, the same motivation is used as the rejection for claim 2. Mehr, Kania and Gielis are understood to be silent on the remaining limitations of claim 3.
In the same field of endeavor, Klinger teach wherein the unified fuzzy Boolean operators are defined by a tetrahedral barycentric interpolation scheme, based on barycentric coordinates that specify a position that define a tetrahedron ([0085] As an example, a method may include using fuzzy control point constraints. For example, at a location of interpretation points, h.sub.i of φ (see, e.g. point a* in FIG. 3). As an example, an interpretation point may be located at a location other than that of a node of a mesh onto which an interpolation is performed, for example, as a numerical constraint may be expressed as a linear combination of values of φ at nodes of a mesh element (e.g. a tetrahedron, tetrahedral cell, etc.) that includes the interpretation point (e.g., coefficients of a sum being barycentric coordinates of the interpretation point within the element or cell). [0086] For example, for an interpretation point p of a horizon I located inside a tetrahedron which includes vertices are a.sub.0, a.sub.1, a.sub.2 and a.sub.3 and which barycentric coordinates are b.sub.0, b.sub.1, b.sub.2 and b.sub.3 (e.g., such that the sum of the barycentric coordinates is approximately equal to 1) in the tetrahedron, an equation may be formulated as follows: [0089] As an example, a method can include constraining the gradient ∇φ in a mesh element (e.g. a tetrahedron, a tetrahedral cell, etc.) to take an arithmetic average of values of the gradients of φ (e.g., a weighted average) with respect to its neighbors (e.g., topological neighbors). As an example, one or more weighting schemes may be applied (e.g. by volume of an element) that may, for example, include defining of a topological neighborhood (e.g., by face adjacency). As an example, two geometrically “touching” mesh elements that are located on different sides of a fault may be deemed not topological neighbors, for example, as a mesh may be “unsewn” along fault surfaces (e.g., to define a set of elements or a mesh on one side of the fault and another set of elements or a mesh on the other side of the fault).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to modify the method of editing the inferred editable feature tree of CSG of Mehr, Kania and implementing differentiable Boolean operations based on R-function of Gielis with apply barycentric coordinates as seen in Klinger because this modification would provide the interpretation point ([0085-0086]of Klinger)
Thus, the combination of Mehr, Kania, Gielis and Klinger teaches wherein the unified fuzzy Boolean operators are defined by a tetrahedral barycentric interpolation scheme, based on barycentric coordinates that specify a position between binary Boolean operations that define a tetrahedron.
4. Claims 5-6 are rejected under 35 U.S.C. 103 as being unpatentable over Mehr et al, U.S Patent Application Publication No.2020/0250894 (“Mehr”) in view of KANIA et al, IDS, 2020 UCSG-NET-unsupervised discovering of constructive solid geometry tree Advances in Neural Information Processing Systems 33 (2020), 8776-8786 (“Kania”) further in view of DAXUAN REN, et al., IDS, "Csg-stump: A learning friendly csg-like representation for interpretable shape parsing", Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp. 12478-12487 (“Ren”)
Regrading claim 5, Mehr and Kania teach the computer-implemented method of claim 4, wherein the CSG primitives are represented as signed distance functions (see whole paper, at least section 2 Method of Kania “We propose an end-to-end neural network model that predicts parameters of simple geometric primitives and their constructive solid geometry composition to reconstruct a given object. Using our approach, one can predict the CSG parse tree that can be further passed to an external rendering software in order to reconstruct the shape. To achieve this, our model predicts primitive shapes in SDF representation. Then, it converts them into occupancy values O taking 1 if a point in the 2D or the 3D space is inside the shape and 0 otherwise. CSG operations on such a representation are defined as clipped summations and differences of binary values. The model dynamically chooses which operation should be used. During the validation, we retrieve the predicted CSG parse tree and shape primitives, and pass them to the rendering software. Thus, we need a single point in 3D space to infer the structure of the CSG tree. It is possible since primitive parameters and CSG operations are predicted independently from sampled points. In the following subsections, we present 2D examples for clarity. The method scales to 3D inputs trivially, 2.1 Constructive Solid Geometry Network The UCSG-NET architecture is provided in Figure 1. The model is composed of the following main components: encoder, primitive parameter prediction network, signed distance field to indicator function converter and constructive solid geometry layers.”) , and further comprising converting the signed distance functions into occupancy functions (see whole paper, at least section 2.1 Constructive Solid Geometry Network , Signed Distance Field to Indicator Function Converter, “ CSG operations in SDF representation are often defined as a combination of min and max functions on distance values. One has to apply either LogSumExp operation as in CVXNET or standard Softmax function to obtain differentiable approximation. However, we cast our problem to predict CSG operations for occupancy-valued sets. The motivation is that these are linear operations, hence they provide better training stability. We transform signed distances D to occupancy values O ∈ {0,1}. We use parametrized α clipping function that is learned with the rest of the pipeline: O= 1−D α [0,1] inside, O=1 outside, O ∈[0,1) (1) where α is a learnable scalar and α > 0, [·][0,1] clips values to the given range and O means an approximation of occupancy values. O = 1 indicates the inside and the surface of a shape. O ∈ [0,1) means outside of the shape and limα→0 O ∈ {0,1}. Gradual learning of α allows to distribute gradients to all shapes in early stages of training. There are no specific restrictions for α initialization and we set α = 1 in our experiments. The value is pushed towards 0 by optimizing jointly with the rest of parameters by adding the |α| term to the optimized loss. The method follows findings of Sakr et al. [9] that increasing slope of clipping function can be used to obtain binary activations…..”) In addition, the same motivation is used as the rejection for claim 1.
In the same field of endeavor, Ren teaches wherein the CSG primitives are represented as signed distance functions, and further comprising converting the signed distance functions into occupancy functions using a sigmoid function based on a sharpness parameter (whole paper, see at least 4.2. Differentiable Occupancy Calculator “To generate primitive’s occupancy function in a differential fashion, we first compute the primitive’s Signed Distance Field (SDF) [19] and then convert it to occupancy [16] differentially. Denoting the corresponding operations for the extrinsic parameters of a primitive as translation T and rotation R, point x in the world coordinate can be transformed to point x in a local primitive coordinate as x = T−1(R−1(x)). Afterward, SDF can be calculated according to the math ematical formulation of different primitives. For detailed SDF computation regarding each type of primitives, please refer to the Supplementary Material. Inspired by [7], SDF is further converted to occupancy by a sigmoid function Φ: O(x) = Φ(−η×SDF(x)), (12) where the scalar η is a hyperparameter indicating the sharpness of the conversion to occupancy”)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to modify the method of editing the inferred editable feature tree of CSG of Mehr and Kania with using the sigmoid function as seen in Ren because this modification would generate primitive’s occupancy function (4.2 Differentiable occupancy calculator of Ren)
Thus, the combination of Mehr, Kania and Ren teaches wherein the CSG primitives are represented as signed distance functions, and further comprising converting the signed distance functions into occupancy functions using a sigmoid function based on a sharpness parameter.
Regarding claim 6, Mehr, Kania and Ren teach the computer-implemented method of claim 5, wherein the respective softness of the occupancy functions of the smooth primitives is controlled by a temperature parameter of the sigmoid function (whole paper, see at least section 2 Method, Constructive Solid Geometry Layer of Kania, “Predicted sets of occupancy values and output of the encoder z are passed to a sequence of L ≥ 1 CSG layers that combine shapes using boolean operators: union (denoted by ∪∗), intersection (∩∗) and difference (−∗). To grasp an idea of how CSG is performed on occupancy-valued sets, we show example operations in Figure 2. CSG operations for two sets A and B are described as: A∪∗B =[A+B][0,1] A∩∗B =[A+B−1][0,1] A−∗B =[A−B][0,1] B−∗A=[B−A][0,1] (2) The question is how to choose operands A and B, denoted as left and right operands, from input shapes O(l) that would compose the output shape in O(l+1). We create two learnable matrices K(l) left, K(l) right ∈ RM× dz. Vectors stored in rows of these matrices serve as keys for a query z to select appropriate shapes for all 4 operations. The input latent code z is used as a query to retrieve the most appropriate operand shapes for each layer. We perform dot product between matrices K(l) left, K(l) right and z, and compute softmax along M input shapes…. where Cᵢ is a sample from Gumbel(0, 1). The benefit of the reparametrization is twofold. Firstly, the expectation over the distribution stays the same despite changing π⁽⁾. Secondly, we can manipulate τ⁽⁾ so for τ⁽¹⁾ 0 the distribution degenerates to categorical distribution. Hence, a single shape selection replaces the fuzzy sum of all input shapes in that case. That way, we allow the network to select the most appropriate shape for the composition during learning by decreasing T¹⁾ gradually. By the end of the learning process, we can retrieve a single shape to be used for the CSG. The temperature τ⁽¹⁾ is learned jointly with the rest of the parameters…… Second stage We strive for interpretable CSG relations. To achieve this, we output occupancy values, obtained with Equation 1, so these values create binary-valued sets since the α at this stage is near 0. The stage is triggered, when α ≤ 0.05. Its main goal is to enforce ˆ V(l) for l ≤ L to resemble one-hot mask by decreasing the temperature τ(l) in CSG layers.”; section 3. CSG-Stump, 4.2. Differentiable Occupancy Calculator To generate primitive’s occupancy function in a differ ential fashion, we first compute the primitive’s Signed Dis tance Field (SDF) [19] and then convert it to occupancy [16] differentially. Denoting the corresponding operations for the extrinsic parameters of a primitive as translation T and rotation R, point x in the world coordinate can be transformed to point x in a local primitive coordinate as x = T−1(R−1(x)). Afterward, SDF can be calculated according to the math ematical formulation of different primitives. For detailed SDF computation regarding each type of primitives, please refer to the Supplementary Material. Inspired by [7], SDF is further converted to occupancy by a sigmoid function Φ: O(x) = Φ(−η×SDF(x)), (12) where the scalar η is a hyperparameter indicating the sharpness of the conversion to occupancy) In addition, the same motivation is used as the rejection for claim 5.
5. Claim 7 is rejected under 35 U.S.C. 103 as being unpatentable over Mehr et al, U.S Patent Application Publication No.2020/0250894 (“Mehr”) in view of KANIA et al, IDS, 2020 UCSG-NET-unsupervised discovering of constructive solid geometry tree Advances in Neural Information Processing Systems 33 (2020), 8776-8786 (“Kania”) further in view of Wang, Hanqing, et al. "Deep single-view 3D object reconstruction with visual hull embedding." Proceedings of the AAAI conference on artificial intelligence. Vol. 33. No. 01. 2019 (“Wang”)
Regarding claim 7, Mehr and Kania teach the computer-implemented method of claim 1, wherein the groundtruth occupancy function of the 3D object is obtained from the 3D object that is generated based on a mesh corresponding to the 3D object (see whole paper, at least Kania 2.2 Training right for the reconstruction, thus leaving the tree with The pipeline is optimized end-to-end using a backpropagation algorithm in a two-stage process. First stage The goal is to find compositions of primitives that minimize the reconstruction error. We employ mean squared error of predicted occupancy values ˆ O(L) with the ground truth O∗. Values are calculated for X which combines points sampled from the surface of the ground truth”) In addition, the same motivation is used as the rejection for claim 1.
In the same field of endeavor, Wang teaches wherein the groundtruth occupancy function of the 3D object is obtained from a visual hull representation of the 3D object (whole paper, at least section Network Training , “We now present our training strategies, including the training pipeline for the sub-networks and their training losses. Training pipeline. We employ a three-step network training algorithm to train the proposed network. Specifically, we first train V-Net, S-Net and R-Net separately, with input training images and their ground-truth shapes, silhouettes and poses. After V-Net converges, we train R-Net in dependently, with the predicted voxel occupancy probability V from V-Net and the ground-truth visual hull, which is con structed by ground-truth silhouettes and poses via the PSVH layer.”)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to modify the method of editing the inferred editable feature tree of CSG of Mehr and Kania with constructing a probabilistic single view visual hull as seen in Wang because this modification would refine coarse shape predictions (Network Training of Wang).
Thus, the combination of Mehr , Kania and Wang teaches wherein the groundtruth occupancy function of the 3D object is obtained from a visual hull representation of the 3D object that is generated based on a mesh corresponding to the 3D object.
6. Claims 8-9, 11-13 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Mehr et al, U.S Patent Application Publication No.2020/0250894 (“Mehr”) in view of KANIA et al, IDS, 2020 UCSG-NET-unsupervised discovering of constructive solid geometry tree Advances in Neural Information Processing Systems 33 (2020), 8776-8786 (“Kania”) further in view of Planche et al., U.S Patent Application Publication No.2024/0294870 (“Planche”)
Regarding claim 8, Mehr and Kania teach the computer-implemented method of claim 1, further comprising initializing the binary tree with random parameter values (see at least Mehr:[0144] When for each of one or more primitive shape types, the one or more respective continuous parameters comprise one or more dimensional parameters, the synthetizing may in example comprise a mix between generating one or more initial data pieces each from the initial data (as described above), and deriving, based on each such generated initial data piece, one or more respective other (ulterior) data pieces based on a modification of said generated data piece. In examples, the synthetizing may comprise an initial generation of at least one (e.g. several) initial data piece based on the initial data. The initial generation includes, for each dimensional parameter (of each leaf geometrical shape), the earlier-described selection of an initial parameter value (e.g. via a sampling, optionally a random sampling). In such examples, the synthetizing may then comprise (e.g. for one or more—e.g. each—generated initial data piece), determining one or more ulterior data pieces by iteratively, starting from the initial data piece, modifying one or more parameter values each of a respective dimensional parameter and/or deleting one or more leaf geometrical shapes”; [0205] To sample a CSG tree, the example machine-learning process randomly samples its depth, primitive types, and Boolean operations. For each primitive, the example machine-learning process also samples its continuous parameters. The example machine-learning process thus gets a random CSG tree. This CSG can be turned into a raw mesh by applying its Boolean operations sequentially to its sequence of primitives. “; Kania: section 2.2 Training, First stage “The goal is to find compositions of primitives that minimize the reconstruction error. We employ mean squared error of predicted occupancy values ˆ O(L) with the ground truth O∗. Values are calculated for X which combines points sampled from the surface of the ground truth, and randomly sampled inside a unit cube…”), and
wherein minimizing the error comprises iteratively modifying the values of the Boolean operations and the values of the parameters of the CSG primitives in the binary tree until the error between the occupancy function of the CSG model and the groundtruth occupancy function of the 3D object is less than a threshold value (see at least Mehr see at least [0084] of Mehr “ In particularly efficient examples, the learning method may comprise a supervised training based on the dataset formed by the dataset-forming method. In robust examples of such examples, the learning may further comprise an unsupervised training based on another dataset, for example after the supervised training. As known from the field of machine-learning, each training may comprise iteratively processing a respective dataset, for example mini-batch-by-mini-batch, and modifying weight values of the neural network along the iterative processing. This may be performed according to a stochastic gradient descent. The weight values may be initialized in any way for each training. In examples, the weight values of the unsupervised training may be initialized with the weight values obtained at the end of the supervised training. The weight values may be initialized for the supervised training in any arbitrary manner, for example randomly or each to the zero value” [0228-0235],[0228] “The loss that the example machine-learning process minimizes to train the weights of the network (using standard deep learning techniques, such as ADAM solver over mini-batches) may the following:…. [0232] In the case where the example machine-learning process uses the feedback loop, once the RNN is learnt by minimizing the loss L.sub.1(w), the example machine-learning process may minimize the following loss custom-character(w)in order to train the RNN to use its own predicted intermediate representations I.sub.t for its feedback loop.”; 2.2 Training of Kania “First stage The goal is to find compositions of primitives that minimize the reconstruction error. We employ mean squared error of predicted occupancy values ˆ O(L) with the ground truth O∗. Values are calculated for X which combines points sampled from the surface of the ground truth, and randomly sampled inside a unit cube (or square for 2D case): LMSE = Ex∈X[(O(L) −O∗)2] (8) Wealso ensure that the network predicts only positive values of parameters of shapes since only for such these shapes have analytical descriptions: M LP = i=1pi∈pi max(−pi,0) (9) To stop primitives from drifting away from the center of considered space in the early stages of the training, we minimize the clipped squared norm of the translation vector. At the same time, we allow primitives to be freely translated inside the space of interest: M LT = i=1 max(||ti||2, 0.5) (10) The last component includes minimizing |α| to perform continuous binarization of distances into {inside, outside} indicator values. Our goal is to find optimal parameters of our model by minimizing the total loss: where we set λT = λα = 0.1. Second stage We strive for interpretable CSG relations. To achieve this, we output occupancy values, obtained with Equation 1, so these values create binary-valued sets since the α at this stage is near 0. The stage is triggered, when α ≤ 0.05. Its main goal is to enforce ˆ V(l) for l ≤ L to resemble one-hot mask by decreasing the temperature τ(l)… where we set λτ = 0.1 for all experiments. Once α ≈ 0 and ∀l≤Lτ(l) ≈ 0, predictions of the CSG layers become fully interpretable as described above, i.e. CSG parse trees of reconstructions can be retrieved and processed using explicit representation of meshes. We also ensure that α and τ(l) stay positive by manual clipping values to small positive number ≈ 10−5, if they become negative. During experiments, we initialize them to α = 1 and τ(l) = 2. Additional implementation details are provided in supplementary material. ; B Implementation details, “We use Adam optimizer[45] for each task with learning rate 10−4 and beta parameters(0.5,0.99). Batch size was set to 16 samples in 2D and 3D autoencoding tasks. Learning starts with initial values α=1 and τ(l)=2. We use 2 CSG layers for the 2D data and 5 for the 3D” ) In addition, the same motivation is used as the rejection for claim 1.
In the same field of endeavor, Planche teaches minimizing the error comprises iteratively until the error between the occupancy of the model and the groundtruth of the 3D object is less than a threshold value ([0036] FIG. 4 illustrates example operations that may be associated with training a neural network (e.g., an ML model implemented by the neural network) for performing one or more of the tasks described herein. As shown, the training operations may include initializing the operating parameters of the neural network (e.g., weights associated with various layers of the neural network) at 402, for example, by sampling from a probability distribution or by copying the parameters of another neural network having a similar structure. The training operations may further include processing an input (e.g., a training representation such as a heatmap or a segmentation mask of multiple anatomical structures) using presently assigned parameters of the neural network at 404, and making a prediction for a desired result (e.g., a condition agnostic representation or a condition-specific representation of the multiple anatomical structures) at 406. The prediction result may then be compared to a ground truth at 408 to determine a loss associated with the prediction based on a loss function such as mean squared errors between the prediction result and the ground truth, an L1 norm, an L2 norm, etc. The loss may be used to determine, at 410, whether one or more training termination criteria are satisfied. For example, the training termination criteria may be determined to be satisfied if the loss is below a threshold value or if the change in the loss between two training iterations falls below a threshold value. If the determination at 410 is that the termination criteria are satisfied, the training may end; otherwise, the presently assigned network parameters may be adjusted at 412, for example, by backpropagating a gradient descent of the loss function through the network before the training returns to 406.”)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to modify the method of editing the inferred editable feature tree of CSG of Mehr and Kania with training termination criteria may be determined to be satisfied if the loss is below a threshold value as seen in Planche because this modification would use the loss to determine whether one or more training termination criteria are satisfied ( [0036] of Planche)
Thus, the combination of Mehr, Kania and Planche teaches further comprising initializing the binary tree with random parameter values, and wherein minimizing the error comprises iteratively modifying the values of the Boolean operations and the values of the parameters of the CSG primitives in the binary tree until the error between the occupancy function of the CSG model and the groundtruth occupancy function of the 3D object is less than a threshold value.
Regarding claim 9, Mehr, Kania and Planche teach the computer-implemented method of claim 8, wherein minimizing the error is performed using adaptive moment estimation (ADAM) ((see at least Mehr [0228-0235],[0228] “The loss that the example machine-learning process minimizes to train the weights of the network (using standard deep learning techniques, such as ADAM solver over mini-batches) may the following:…. [0232] In the case where the example machine-learning process uses the feedback loop, once the RNN is learnt by minimizing the loss L.sub.1(w), the example machine-learning process may minimize the following loss custom-character(w)in order to train the RNN to use its own predicted intermediate representations I.sub.t for its feedback loop.”; 2.2 Training of Kania “First stage The goal is to find compositions of primitives that minimize the reconstruction error. We employ mean squared error of predicted occupancy values ˆ O(L) with the ground truth O∗. Values are calculated for X which combines points sampled from the surface of the ground truth, and randomly sampled inside a unit cube (or square for 2D case): LMSE = Ex∈X[(O(L) −O∗)2] (8) Wealso ensure that the network predicts only positive values of parameters of shapes since only for such these shapes have analytical descriptions: M LP = i=1pi∈pi max(−pi,0) (9) To stop primitives from drifting away from the center of considered space in the early stages of the training, we minimize the clipped squared norm of the translation vector. At the same time, we allow primitives to be freely translated inside the space of interest: M LT = i=1 max(||ti||2, 0.5) (10) The last component includes minimizing |α| to perform continuous binarization of distances into {inside, outside} indicator values. Our goal is to find optimal parameters of our model by minimizing the total loss: where we set λT = λα = 0.1. Second stage We strive for interpretable CSG relations. To achieve this, we output occupancy values, obtained with Equation 1, so these values create binary-valued sets since the α at this stage is near 0. The stage is triggered, when α ≤ 0.05. Its main goal is to enforce ˆ V(l) for l ≤ L to resemble one-hot mask by decreasing the temperature τ(l)… where we set λτ = 0.1 for all experiments. Once α ≈ 0 and ∀l≤Lτ(l) ≈ 0, predictions of the CSG layers become fully interpretable as described above, i.e. CSG parse trees of reconstructions can be retrieved and processed using explicit representation of meshes. We also ensure that α and τ(l) stay positive by manual clipping values to small positive number ≈ 10−5, if they become negative. During experiments, we initialize them to α = 1 and τ(l) = 2. Additional implementation details are provided in supplementary material. ; B Implementation details, “We use Adam optimizer[45] for each task with learning rate 10−4 and beta parameters(0.5,0.99). Batch size was set to 16 samples in 2D and 3D autoencoding tasks. Learning starts with initial values α=1 and τ(l)=2. We use 2 CSG layers for the 2D data and 5 for the 3D”) In addition, the same motivation is used as the rejection for claim 1.
Regarding claim 11, Mehr and Kania teach the computer-implemented method of claim 1, wherein minimizing the error between an occupancy function of the CSG model and the groundtruth occupancy function of the 3D object comprises updating the values of the Boolean operations and the values of the parameters of the CSG primitives for the binary tree using a machine learning model (see at least [0084] of Mehr “ In particularly efficient examples, the learning method may comprise a supervised training based on the dataset formed by the dataset-forming method. In robust examples of such examples, the learning may further comprise an unsupervised training based on another dataset, for example after the supervised training. As known from the field of machine-learning, each training may comprise iteratively processing a respective dataset, for example mini-batch-by-mini-batch, and modifying weight values of the neural network along the iterative processing. This may be performed according to a stochastic gradient descent. The weight values may be initialized in any way for each training. In examples, the weight values of the unsupervised training may be initialized with the weight values obtained at the end of the supervised training. The weight values may be initialized for the supervised training in any arbitrary manner, for example randomly or each to the zero value”; [0196] The proposed example of unsupervised training proposes to use a reinforcement approach to provide a pseudo-gradient of the loss relative to a variable representing the candidate respective discrete distributions of the respective first data, and optionally a pseudo-gradient of the loss relative to a variable representing the candidate respective discrete distributions over the geometrical operations and/or a pseudo-gradient of the loss relative to a variable representing the end token distribution. The minimizing may then include a backpropagation (e.g. stochastic descent) of such pseudo-gradient(s) of the loss to learn the neural network. Since the pseudo-gradients are provided by a reinforcement algorithm, the learning is accurate even if the backpropagation is not the one of a true gradient. The minimizing may also include a backpropagation of the (true) gradient of the loss relative to the respective parameter values for each of the respective discrete set of one or more parameter domains (since the loss is differentiable relative to these variables). The reinforcement approach thus solves the differentiability issue raised by the introduction of discrete probability distributions, and only this issue.; whole paper, Kania: 2 Method, Interpretability, “All introduced components of the UCSG-NET lead us to interpretable predictions of mesh reconstructions. To see this, consider the following case. When α ≈ 0, we obtain occupancy values calculated with Equation 1. Thus, shapes represented as these values will occupy the same olume as meshes reconstructed from parameters {i M|pᵢ, tᵢ, qᵢ}. These meshes can be visualized and edited explicitly. To further combine these primitives through CSG operations, we calculate arg max, arg max jEM V(1) for left and right operands respectively. Then, we perform operations AU* B, An* B, A B and B A. When (l) ≈ both V1eft, right (l) are one-hot vectors, and operations performed on occupancy values, as in Figure 2, are equivalent to CSG operations executed on aforementioned meshes, ex. by merging binary space partitioning trees of meshes [12]. Additionally, the whole CSG tree can be pruned to form binary tree, by investigating which meshes were selected through V ¹ left' V(1) right for the reconstruction, thus leaving the tree with 2L⁻¹ nodes at each layer”, 2.2 Training, “The pipeline is optimized end-to-end using a backpropagation algorithm in a two-stage process. First stage The goal is to find compositions of primitives that minimize the reconstruction error. We employ mean squared error of predicted occupancy values ˆ O(L) with the ground truth O∗. Values are calculated for X which combines points sampled from the surface of the ground truth, and randomly sampled inside a unit cube (or square for 2D case): LMSE = Ex∈X[(O(L) −O∗)2] (8) We also ensure that the network predicts only positive values of parameters of shapes since only for such these shapes have analytical descriptions: M LP = i=1pi∈pi max(−pi,0) (9) To stop primitives from drifting away from the center of considered space in the early stages of the training, we minimize the clipped squared norm of the translation vector. At the same time, we allow primitives to be freely translated inside the space of interest: M LT = i=1 max(||ti||2, 0.5) (10) The last component includes minimizing |α| to perform continuous binarization of distances into {inside, outside} indicator values. Our goal is to find optimal parameters of our model by minimizing the total loss; Constructive Solid Geometry Network , 2.2 Training, “The pipeline is optimized end-to-end using a backpropagation algorithm in a two-stage process. First stage The goal is to find compositions of primitives that minimize the reconstruction error. We employ mean squared error of predicted occupancy values ˆ O(L) with the ground truth O∗. Values are calculated for X which combines points sampled from the surface of the ground truth, and randomly sampled inside a unit cube (or square for 2D case): LMSE = Ex∈X[(O(L) −O∗)2] (8) We also ensure that the network predicts only positive values of parameters of shapes since only for such these shapes have analytical descriptions: M LP = i=1pi∈pi max(−pi,0) (9) To stop primitives from drifting away from the center of considered space in the early stages of the training, we minimize the clipped squared norm of the translation vector. At the same time, we allow primitives to be freely translated inside the space of interest: M LT = i=1 max(||ti||2, 0.5) (10) The last component includes minimizing |α| to perform continuous binarization of distances into {inside, outside} indicator values. Our goal is to find optimal parameters of our model by minimizing the total loss:… ...4.2 3D Autoencoding “For the 3D autoencoding task, we train the model on 643 volumes of voxelized shapes in the ShapeNet dataset. We sample 16384 points as a ground truth with a higher probability of sampling near the surface. To speed up the training, we applied early stopping heuristic and stop after 40 epochs of no improvement on the L∗ total loss. The data was provided by Chen et al. [5] and bases on the 13 most common classes in the ShapeNet dataset [13]. We used 5 CSG layers to increase the diversity of predictions and set 64 parameters of spheres and boxes to handle the complex nature of the dataset. Each layer predicts CSG 48 combinations of these primitives. Training takes about two days on Nvidia Titan RTX GPU. The CSG inference for a single sample takes 0.068s and the reconstruction 1.68s using the libigl library…”)”, wherein the updating comprises:
determining the occupancy function of the CSG model based on the values of the Boolean operations and parameters of the CSG primitives of the CSG model ( see at least Kania 2 Method, 2.1 Constructive Solid Geometry Network, Signed Distance Field to Indicator Function Converter, “CSG operations in SDF representation are often defined as a combination of min and max functions on distance values. One has to apply either LogSumExp operation as in CVXNET or standard Softmax function to obtain differentiable approximation. However, we cast our problem to predict CSG operations for occupancy-valued sets. The motivation is that these are linear operations, hence they provide better training stability. We transform signed distances D to occupancy values O ∈ {0,1}. We use parametrized α clipping function that is learned with the rest of the pipeline: O= 1−D α [0,1] inside, O=1 outside, O ∈[0,1) (1) where α is a learnable scalar and α > 0, [·][0,1] clips values to the given range and O means an approximation of occupancy values. O = 1 indicates the inside and the surface of a shape. O ∈ [0,1) means outside of the shape and limα→0 O ∈ {0,1}. Gradual learning of α allows to distribute gradients to all shapes in early stages of training. There are no specific restrictions for α initialization and we set α = 1 in our experiments. The value is pushed towards 0 by optimizing jointly with the rest of parameters by adding the |α| term to the optimized loss. The method follows findings of Sakr et al. [9] that increasing slope of clipping function can be used to obtain binary activations. Constructive Solid Geometry Layer Predicted sets of occupancy values and output of the encoder z are passed to a sequence of L ≥ 1 CSG layers that combine shapes using boolean operators: union (denoted by ∪∗), intersection (∩∗) and difference (−∗). To grasp an idea of how CSG is performed on occupancy-valued sets, we show example operations in Figure 2. CSG operations for two sets A and …..”);
computing a difference between the occupancy function of the CSG model and the groundtruth occupancy function of the 3D object (see at least Mehr: [186] An example of a loss for a supervised training which leads to an accurate result penalizes, for the time step respective to each leaf geometrical shape of each discrete geometrical representation (each discrete geometrical representation being here associated to a respective ground truth editable feature tree), one or both of the following quantities: [0187] a lowness of the probability of the respective first data attributed to the respective primitive shape type of the corresponding ground truth leaf geometrical shape, and/or [0188] a disparity between the one or more respective parameter values of the corresponding ground truth leaf geometrical shape and the one or more respective parameter values of the respective second data. In other words, the supervised training may, by minimizing such a loss, act on the weights of the neural network so as to tend to make the respective probabilities outputted by each RNN cell close to 1 (i.e. not low) for the corresponding ground truth primitive shape type and close to 0 (i.e. low) for the other primitive shape types, and/or to make the respective continuous parameter values outputted by each cell close to their ground truth values. Such a loss handles accurately the discrete/continuous mixture of the problem.[0189] In options of this example, the loss may further similarly penalize, for the time step respective to each leaf geometrical shape of each discrete geometrical representation, one or both of the additional quantities: [0190] a lowness of the respective probability (outputted by an RNN cell) attributed to the corresponding ground truth geometrical operation, and/or [0191] a lowness of the probability (outputted by an RNN cell) to reach the tree arrangement (e.g. depth or length) of the corresponding ground truth editable feature tree based on the respective data for inference of the end token.” [0228-0235] The loss that the example machine-learning process minimizes to train the weights of the network (using standard deep learning techniques, such as ADAM solver over mini-batches) may the following”; Kania: 2 Method, 2.1 Constructive Solid Geometry Network , 2.2 Training, “The pipeline is optimized end-to-end using a backpropagation algorithm in a two-stage process. First stage The goal is to find compositions of primitives that minimize the reconstruction error. We employ mean squared error of predicted occupancy values ˆ O(L) with the ground truth O∗. Values are calculated for X which combines points sampled from the surface of the ground truth, and randomly sampled inside a unit cube (or square for 2D case): LMSE = Ex∈X[(O(L) −O∗)2] (8) We also ensure that the network predicts only positive values of parameters of shapes since only for such these shapes have analytical descriptions: M LP = i=1pi∈pi max(−pi,0) (9) To stop primitives from drifting away from the center of considered space in the early stages of the training, we minimize the clipped squared norm of the translation vector. At the same time, we allow primitives to be freely translated inside the space of interest: M LT = i=1 max(||ti||2, 0.5) (10) The last component includes minimizing |α| to perform continuous binarization of distances into {inside, outside} indicator values. Our goal is to find optimal parameters of our model by minimizing the total loss:…”);
and modifying values of the Boolean operations and parameters of the CSG primitives of the CSG model based on the difference, wherein the modifying is performed using gradient descent, wherein the determining, computing, and modifying are performed iteratively until a stopping criterion is met, wherein the stopping criterion is at least one of: the difference between the occupancy function of the CSG model and the groundtruth occupancy function of the 3D object falling below a threshold, change between the occupancy function of the CSG model between consecutive iterations falling below a change threshold, or a computational budget being exhausted (see at least [0084] of Mehr “ In particularly efficient examples, the learning method may comprise a supervised training based on the dataset formed by the dataset-forming method. In robust examples of such examples, the learning may further comprise an unsupervised training based on another dataset, for example after the supervised training. As known from the field of machine-learning, each training may comprise iteratively processing a respective dataset, for example mini-batch-by-mini-batch, and modifying weight values of the neural network along the iterative processing. This may be performed according to a stochastic gradient descent. The weight values may be initialized in any way for each training. In examples, the weight values of the unsupervised training may be initialized with the weight values obtained at the end of the supervised training. The weight values may be initialized for the supervised training in any arbitrary manner, for example randomly or each to the zero value”; Kania 2 Method, Second stage , “We strive for interpretable CSG relations. To achieve this, we output occupancy values, obtained with Equation 1, so these values create binary-valued sets since the α at this stage is near 0. The stage is triggered, when α ≤ 0.05. Its main goal is to enforce ˆ V(l) for l ≤ L to resemble one-hot mask by decreasing the temperature τ(l) in CSG layers. The optimized loss is defined as: L L∗ total = Ltotal + λτ l=1 |τ(l)| (12) where we set λτ = 0.1 for all experiments. Once α ≈ 0 and ∀l≤Lτ(l) ≈ 0, predictions of the CSG layers become fully interpretable as described above, i.e. CSG parse trees of reconstructions can be retrieved and processed using explicit representation of meshes. We also ensure that α and τ(l) stay positive by manual clipping values to small positive number ≈ 10−5, if they become negative. During experiments, we initialize them to α = 1 and τ(l) = 2. Additional implementation details are provided in supplementary material.”; B Implementation details, “We follow architectures described by Chen et al. [5] to show influence of our framework on obtained results. For 2D and 3D autoencoding, we use a simple convolutional network where each convolutional layer reduces feature map spatial dimensions by a factor of two. The decoder is a multilayer perceptron with a leaky ReLU activation units in each hidden layer. The final layer outputs parameters of primitives and its size varies depending on a number of considered dimensions, a number of input and output shapes. Refer to Section 2 for more details. No batch normalization is used. The parameter prediction network takes the latent code of size d₇ = 256. Parameter encoders h⁽¹ consists of a single hidden fully connected layer of size d₂. GRU units has a latent dimension size equal to d₂. Architectures are summarized in Table 4. In CSG layers we sample initial values of K (l) from N(0,0.1). We use Adam optimizer[45] for each task with learning rate 10−4 and beta parameters(0.5,0.99). Batch size was set to 16 samples in 2D and 3D autoencoding tasks. Learning starts with initial values α=1 and τ(l)=2. We use 2 CSG layers for the 2D data and 5 for the 3D…). In addition, the same motivation is used as the rejection for claim 1. Both Mehr and Kania are understood to be silent on the remaining limitations of claim 11.
In the same field of endeavor, Planche teaches wherein minimizing the error between an occupancy model and the groundtruth of the 3D object comprises updating the values of the parameters using a machine learning model (see at least [0033] Various techniques may be used to optimize the first and second ML models (e.g., the mapping and SDF functions realized via the ML models), and/or to learn the patient-specific feature descriptor. As an example, the condition-specific representation predicted in the process described above may be compared to the second representation of the anatomical structures included in the training dataset to determine a loss between the predicted representation and the second representation (e.g., as ground truth), and the loss may be used to adjust the estimated feature descriptor and/or respective parameters of the first ANN and the second ANN, with an objective to minimize the loss. As another example, the SDF field predicted by the second ML model may be sampled to obtain respective SDF values for a plurality of points in the input data that may have ground truth SDF values. The sampled SDF values may then be compared to the ground truth SDF values to determine a loss for adjusting the estimated feature descriptor and/or the respective parameters of the first ANN and the second ANN. Once learned, the parameters of the first and second ML models may be fixed during application of the ML models (e.g., at an inference time), while a patient-specific feature descriptor may be optimized based on a given representation the target anatomical structures (e.g., derived from a medical scan of the patient) and used to predict geometric characteristics of the target anatomical structures (e.g., organ shapes) under a set of new conditions.”), wherein the updating comprises:
determining the occupancy model based on the values of parameters of the model; computing a difference between the occupancy of the model and the groundtruth of the 3D object; and modifying values and parameters of the model based on the difference (see at least [0033] Various techniques may be used to optimize the first and second ML models (e.g., the mapping and SDF functions realized via the ML models), and/or to learn the patient-specific feature descriptor. As an example, the condition-specific representation predicted in the process described above may be compared to the second representation of the anatomical structures included in the training dataset to determine a loss between the predicted representation and the second representation (e.g., as ground truth), and the loss may be used to adjust the estimated feature descriptor and/or respective parameters of the first ANN and the second ANN, with an objective to minimize the loss. As another example, the SDF field predicted by the second ML model may be sampled to obtain respective SDF values for a plurality of points in the input data that may have ground truth SDF values. The sampled SDF values may then be compared to the ground truth SDF values to determine a loss for adjusting the estimated feature descriptor and/or the respective parameters of the first ANN and the second ANN. Once learned, the parameters of the first and second ML models may be fixed during application of the ML models (e.g., at an inference time), while a patient-specific feature descriptor may be optimized based on a given representation the target anatomical structures (e.g., derived from a medical scan of the patient) and used to predict geometric characteristics of the target anatomical structures (e.g., organ shapes) under a set of new conditions.”; [0036]), wherein the modifying is performed using gradient descent, wherein the determining, computing, and modifying are performed iteratively until a stopping criterion is met, wherein the stopping criterion is at least one of: the difference between the occupancy model and the groundtruth of the 3D object falling below a threshold, change between the occupancy model between consecutive iterations falling below a change threshold, or a computational budget being exhausted (see at least [0036] FIG. 4 illustrates example operations that may be associated with training a neural network (e.g., an ML model implemented by the neural network) for performing one or more of the tasks described herein. As shown, the training operations may include initializing the operating parameters of the neural network (e.g., weights associated with various layers of the neural network) at 402, for example, by sampling from a probability distribution or by copying the parameters of another neural network having a similar structure. The training operations may further include processing an input (e.g., a training representation such as a heatmap or a segmentation mask of multiple anatomical structures) using presently assigned parameters of the neural network at 404, and making a prediction for a desired result (e.g., a condition agnostic representation or a condition-specific representation of the multiple anatomical structures) at 406. The prediction result may then be compared to a ground truth at 408 to determine a loss associated with the prediction based on a loss function such as mean squared errors between the prediction result and the ground truth, an L1 norm, an L2 norm, etc. The loss may be used to determine, at 410, whether one or more training termination criteria are satisfied. For example, the training termination criteria may be determined to be satisfied if the loss is below a threshold value or if the change in the loss between two training iterations falls below a threshold value. If the determination at 410 is that the termination criteria are satisfied, the training may end; otherwise, the presently assigned network parameters may be adjusted at 412, for example, by backpropagating a gradient descent of the loss function through the network before the training returns to 406.”)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to modify the method of editing the inferred editable feature tree of CSG of Mehr and Kania with training termination criteria may be determined to be satisfied if the loss is below a threshold value or if the change in the loss between two training iterations falls below a threshold value as seen in Planche because this modification would use the loss to determine whether one or more training termination criteria are satisfied ( [0036] of Planche)
Thus, the combination of Mehr, Kania and Planche teaches wherein minimizing the error between an occupancy function of the CSG model and the groundtruth occupancy function of the 3D object comprises updating the values of the Boolean operations and the values of the parameters of the CSG primitives for the binary tree using a machine learning model, wherein the updating comprises: determining the occupancy function of the CSG model based on the values of the Boolean operations and parameters of the CSG primitives of the CSG model; computing a difference between the occupancy function of the CSG model and the groundtruth occupancy function of the 3D object; and modifying values of the Boolean operations and parameters of the CSG primitives of the CSG model based on the difference, wherein the modifying is performed using gradient descent, wherein the determining, computing, and modifying are performed iteratively until a stopping criterion is met, wherein the stopping criterion is at least one of: the difference between the occupancy function of the CSG model and the groundtruth occupancy function of the 3D object falling below a threshold, change between the occupancy function of the CSG model between consecutive iterations falling below a change threshold, or a computational budget being exhausted.
Regarding claim 12, Mehr, Kania and Planche teach the computer-implemented method of claim 11, wherein computing the difference comprises:
sampling the groundtruth occupancy of the 3D object to identify a plurality of groundtruth points (see at least Kania 2.2 Training right for the reconstruction, thus leaving the tree with The pipeline is optimized end-to-end using a backpropagation algorithm in a two-stage process. First stage The goal is to find compositions of primitives that minimize the reconstruction error. We employ mean squared error of predicted occupancy values ˆ O(L) with the ground truth O∗. Values are calculated for X which combines points sampled from the surface of the ground truth, and randomly sampled inside a unit cube (or square for 2D case): LMSE = Ex∈X[(O(L) −O∗)2] (8) We also ensure that the network predicts only positive values of parameters of shapes since only for such these shapes have analytical descriptions: M LP = i=1pi∈pi max(−pi,0) (9) To stop primitives from drifting away from the center of considered space in the early stages of the training, we minimize the clipped squared norm of the translation vector. At the same time, we allow primitives to be freely translated inside the space of interest: M LT = i=1 max(||ti||2, 0.5) (10) The last component includes minimizing |α| to perform continuous binarization of distances into {inside, outside} indicator values. Our goal is to find optimal parameters of our model by minimizing the total loss: where we set λT = λα = 0.1. Ltotal = LMSE +LP +λTLT +λα|α| (11)’; 4.2 3D Autoencoding , “For the 3D autoencoding task, we train the model on 643 volumes of voxelized shapes in the ShapeNet dataset. We sample 16384 points as a ground truth with a higher probability of sampling near the surface. To speed up the training, we applied early stopping heuristic and stop after 40 epochs of no improvement on the L∗ total loss. The data was provided by Chen et al. [5] and bases on the 13 most common classes in the ShapeNet dataset [13]. We used 5 CSG layers to increase the diversity”);
determining corresponding modeled points obtained based on the CSG model(see at least Kania 2.2 Training right for the reconstruction, thus leaving the tree with The pipeline is optimized end-to-end using a backpropagation algorithm in a two-stage process. First stage The goal is to find compositions of primitives that minimize the reconstruction error. We employ mean squared error of predicted occupancy values ˆ O(L) with the ground truth O∗. Values are calculated for X which combines points sampled from the surface of the ground truth, and randomly sampled inside a unit cube (or square for 2D case): LMSE = Ex∈X[(O(L) −O∗)2] (8) We also ensure that the network predicts only positive values of parameters of shapes since only for such these shapes have analytical descriptions: M LP = i=1pi∈pi max(−pi,0) (9) To stop primitives from drifting away from the center of considered space in the early stages of the training, we minimize the clipped squared norm of the translation vector. At the same time, we allow primitives to be freely translated inside the space of interest: M LT = i=1 max(||ti||2, 0.5) (10) The last component includes minimizing |α| to perform continuous binarization of distances into {inside, outside} indicator values. Our goal is to find optimal parameters of our model by minimizing the total loss: where we set λT = λα = 0.1. Ltotal = LMSE +LP +λTLT +λα|α| (11)’; 4.2 3D Autoencoding , “For the 3D autoencoding task, we train the model on 643 volumes of voxelized shapes in the ShapeNet dataset. We sample 16384 points as a ground truth with a higher probability of sampling near the surface. To speed up the training, we applied early stopping heuristic and stop after 40 epochs of no improvement on the L∗ total loss. The data was provided by Chen et al. [5] and bases on the 13 most common classes in the ShapeNet dataset [13]. We used 5 CSG layers to increase the diversity”; and
computing an error by pairwise comparison of points from the plurality of groundtruth points and corresponding modeled points ( section 2. Method, Signed Distance Field to Indicator Function Converter CSG operations in SDF representation are often defined as a combination of min and max functions on distance values. One has to apply either LogSumExp operation as in CVXNET or standard Softmax function to obtain differentiable approximation. However, we cast our problem to predict CSG operations for occupancy-valued sets. The motivation is that these are linear operations, hence they provide better training stability. We transform signed distances D to occupancy values O ∈ {0,1}. We use parametrized α clipping function that is learned with the rest of the pipeline: O= 1−D α [0,1] inside, O=1 outside, O ∈[0,1) (1) where α is a learnable scalar and α > 0, [·][0,1] clips values to the given range and O means an approximation of occupancy values. O = 1 indicates the inside and the surface of a shape. O ∈ [0,1) means outside of the shape and limα→0 O ∈ {0,1}. Gradual learning of α allows to distribute gradients to all shapes in early stages of training. There are no specific restrictions for α initialization and we set α = 1 in our experiments. The value is pushed towards 0 by optimizing jointly with the rest of parameters by adding the |α| term to the optimized loss. The method follows findings of Sakr et al. [9] that increasing slope of clipping function can be used to obtain binary activations.; 2.2 Training right for the reconstruction, thus leaving the tree with The pipeline is optimized end-to-end using a backpropagation algorithm in a two-stage process. First stage The goal is to find compositions of primitives that minimize the reconstruction error. Weemploy mean squared error of predicted occupancy values ˆ O(L) with the ground truth O∗. Values are calculated for X which combines points sampled from the surface of the ground truth, and randomly sampled inside a unit cube (or square for 2D case): LMSE = Ex∈X[(O(L) −O∗)2] (8) We also ensure that the network predicts only positive values of parameters of shapes since only for such these shapes have analytical descriptions: M LP = i=1pi∈pi max(−pi,0) (9) To stop primitives from drifting away from the center of considered space in the early stages of the training, we minimize the clipped squared norm of the translation vector. At the same time, we allow primitives to be freely translated inside the space of interest: M LT = i=1 max(||ti||2, 0.5) (10) The last component includes minimizing |α| to perform continuous binarization of distances into {inside, outside} indicator values. Our goal is to find optimal parameters of our model by minimizing the total loss: where we set λT = λα = 0.1”; [0033] of Planche “Various techniques may be used to optimize the first and second ML models (e.g., the mapping and SDF functions realized via the ML models), and/or to learn the patient-specific feature descriptor. As an example, the condition-specific representation predicted in the process described above may be compared to the second representation of the anatomical structures included in the training dataset to determine a loss between the predicted representation and the second representation (e.g., as ground truth), and the loss may be used to adjust the estimated feature descriptor and/or respective parameters of the first ANN and the second ANN, with an objective to minimize the loss. As another example, the SDF field predicted by the second ML model may be sampled to obtain respective SDF values for a plurality of points in the input data that may have ground truth SDF values. The sampled SDF values may then be compared to the ground truth SDF values to determine a loss for adjusting the estimated feature descriptor and/or the respective parameters of the first ANN and the second ANN.”) In addition, the same motivation is used as the rejection for claim 11.
Regarding claim 13, Mehr, Kania and Planche teach the computer-implemented method of claim 11, wherein the gradient descent uses Boolean parameterization based on a temperatured SoftMax function to facilitate convergence for the Boolean operations to a single Boolean logic operation ([0196] The proposed example of unsupervised training proposes to use a reinforcement approach to provide a pseudo-gradient of the loss relative to a variable representing the candidate respective discrete distributions of the respective first data, and optionally a pseudo-gradient of the loss relative to a variable representing the candidate respective discrete distributions over the geometrical operations and/or a pseudo-gradient of the loss relative to a variable representing the end token distribution. The minimizing may then include a backpropagation (e.g. stochastic descent) of such pseudo-gradient(s) of the loss to learn the neural network [0250] In order to fine tune also these distributions, the example machine-learning process may backpropagate a gradient of the loss with respect to these distributions, The example machine-learning process may use a reinforcement algorithm to get such gradients for the discrete distributions p,o,q. The reinforcement algorithm is limited to these discrete distributions, and thus the unsupervised learning may get true gradients for the other variables, This limits approximation and thereby effects on accuracy, and this allows to optimize distributions which would otherwise not be updated and thus not learnt.”; Kania: section Constructive Solid Geometry Layer, “ Predicted sets of occupancy values and output of the encoder z are passed to a sequence of L ≥ 1 CSG layers that combine shapes using boolean operators: union (denoted by ∪∗), intersection (∩∗) and difference (−∗). To grasp an idea of how CSG is performed on occupancy-valued sets, we show example operations in Figure 2. CSG operations for two sets A and B are described as: A∪∗B =[A+B][0,1] A∩∗B =[A+B−1][0,1] A−∗B =[A−B][0,1] B−∗A=[B−A][0,1] (2) The question is how to choose operands A and B, denoted as left and right operands, from input shapes O(l) that would compose the output shape in O(l+1). We create two learnable matrices K(l) left, K(l) right ∈ RM× dz. Vectors stored in rows of these matrices serve as keys for a query z to select appropriate shapes for all 4 operations. The input latent code z is used as a query to retrieve the most appropriate operand shapes for each layer. We perform dot product between matrices K(l) left, K(l) right and z, and compute softmax along M input shapes. V(l) left = softmax(K(l) leftz) V(l) right = softmax(K(l) (3) The index of a particular operand is retrieved using Gumbel-Softmax [10] reparametrization of the rightz) categorical distribution: exp log(V(l) ˆ V(l) side,i = side,i) + ci /τ(l) M j=1 exp log(V(l) for i = 1,...,M side,j) + cj /τ(l) and side ∈ {left,right} (4)
where Cᵢ is a sample from Gumbel(0, 1). The benefit of the reparametrization is twofold. Firstly, the expectation over the distribution stays the same despite changing π⁽⁾. Secondly, we can manipulate τ⁽⁾ so for τ⁽¹⁾ 0 the distribution degenerates to categorical distribution. Hence, a single shape selection replaces the fuzzy sum of all input shapes in that case. That way, we allow the network to select the most appropriate shape for the composition during learning by decreasing T¹⁾ gradually. By the end of the learning process, we can retrieve a single shape to be used for the CSG. The temperature τ⁽¹⁾ is learned jointly with the rest of the parameters. Left and right operands O(right are retrieved as: .where left, right E M denotes left and right operands of the operation. By performing these operations manually, we increase the diversity of possible shape combinations and leave to the model which operations should be used for the reconstruction. Operations can be repeated to output multiple shapes. Note that the computation overhead increases linearly with the number of output shapes per layer. The whole procedure can be stacked in 1<L layers to create a CSG network. The L-th layer outputs a union since it is guaranteed to return a non-empty shape in most cases. At this point, the network has to learn passing primitives untouched by operators if any primitive should be used in later layers of the CSG tree to create, for example, nested rings. To mitigate the problem, each 1+1 layer receives outputs from the l-th layer concatenated with the original binarized values O⁰. For the first layer l = 1, it means receiving initial shapes only.”; [0036] of Kania) In addition, the same motivation is used as the rejection for claim 11.
Regarding claim 18, Mehr and Kania teach the non-transitory computer-readable medium of claim 16, wherein the operations further comprise: Remaining limitations of claim 18 is similar in scope to claim 8 and therefore rejected under the same rationale.
7. Claim 14 is rejected under 35 U.S.C. 103 as being unpatentable over Mehr et al, U.S Patent Application Publication No.2020/0250894 (“Mehr”) in view of KANIA et al, IDS, 2020 UCSG-NET-unsupervised discovering of constructive solid geometry tree Advances in Neural Information Processing Systems 33 (2020), 8776-8786 (“Kania”) further in view of Walker, Robert J., and Jack Snoeyink, NPL, "Practical point-in-polygon tests using CSG representations of polygons." Workshop on algorithm engineering and experimentation. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. (“Walker”)
Regarding claim 14, Mehr and Kania teach the computer-implemented method of claim 1, further comprising: pruning the binary tree to remove redundant subtrees to obtain a pruned binary tree and deleting redundant nodes, wherein a node is redundant when replacement of the node with a full object or an empty object results in a difference in an output of a Boolean operation associated with the node in the binary tree that satisfies a threshold( see at least of Mehr [0200] The example machine-learning process allows learning a recurrent neural network which predicts a CSG tree from a raw mesh. Firstly, a synthetic dataset of CSG trees is randomly generated. Each CSG tree in the dataset is reduced to its minimal expression, in order to remove any redundancy. This dataset is used to train in a supervised way a recurrent neural network to predict a CSG tree from a raw mesh. The network is then refined in an unsupervised way by reinforcement learning on a real dataset of raw meshes, whose CSG trees are unknown. Finally, the network is used to infer plausible CSG trees from a new raw mesh. An optimization scheme is used to refine the continuous parameters of the tree in order to fit at best the CSG tree to the input mesh. [0201] Also, any CSG tree in the example machine-learning process is a single-rooted and full binary tree (of the type where each non-leaf node has at least one leaf node as a child).”; section Interpretability “..To further combine these primitives through CSG operations, we calculate argmaxi∈M ˆV(l) left,i, arg maxj∈M ˆV(l) right,j for left and right operands respectively. Then, we perform operations A∪∗ B, A∩∗B, A−∗B and B−∗A. When∀l≤Lτ(l) ≈ 0, both ˆ V(l) left, ˆ V(l) right are one-hot vectors, and operations performed on occupancy values, as in Figure 2, are equivalent to CSG operations executed on aforementioned meshes, ex. by merging binary space partitioning trees of meshes [12]. Additionally, the whole CSG tree can be pruned to form binary tree, by investigating which meshes were selected through ˆ V(l) left, ˆ V(l) 2L−l nodes at each layer l ≤ L.2”) In addition, the same motivation is used as the rejection for claim 1.
In the same field of endeavor, Walker teaches further comprising: pruning the binary tree to remove redundant subtrees to obtain a pruned binary tree by visiting nodes in the tree in post-order and deleting redundant nodes, wherein a node is redundant when replacement of the node with a full object or an empty object results in a difference in an output of a Boolean operation associated with the node in the binary tree that satisfies a threshold (see whole paper, at least section 2.2 Evaluation by Tree Pruning Conceptually, “ we wish to test a given point against each edge of the polygon. The location of the point can then be determined by evaluating the Boolean formula represented by the CSG tree. However, we take advantage of the alternating structure of the logical operators found in the CSG tree representation as seen in Figure 2b to eliminate unnecessary tests before computing their results. As soon as a subtree that is the child of an AND node is known to be FALSE, we may stop testing he children of that node, and assign the Boolean value FALSE to that AND node. Likewise, as soon as a subtree that is the child of an OR node is known to be TRUE, we may stop testing the children of that node, and assign the Boolean value TRUE to that OR node. The base case is at the leaves where we assign TRUE if the testing point is to the left of the edge, and FALSE if it is to the right. When a Boolean value is selected for the root of the tree, a value of TRUE indicates that the point is inside the polygon and FALSE indicates outside. Since we are effectively pruning the CSG tree for some test points, we wish to permute the children of nodes within the tree to minimize the number of edges that need to be tested against, on average. In general, finding the permutation that yields optimal average performance requires us to analyze all such possible permutations (Section 3.3.1). We resort to heuristic methods to approximate the optimal permutation while performing less work. Such heuristics will be discussed in Section 3.3.”; see section 3.2 Building the Edge-Sequence Graph, “ For a given point + , we can evaluate every leaf of the CSG tree, and hence, every edge of the polygon it represents. The logical operators within the tree could then be evaluated to determine the location of + . However, we can take advantage of the alternating structure of the logical operators found in the CSG tree to prune unrequired edges from the tree during traversal. As soon as a node evaluates to FALSE and is the child of an AND node ] , we may stop testing the children of ] and assign the Boolean value FALSE to ] . Likewise, assoonas anode testing the children of 0^ evaluates to TRUE and 0^ is the child of an OR node ] ^ , we maystop ] ^ and assign TRUE to ]'^ . At a leaf node _ , we assign TRUE if + is to the left of the edge represented by _ , and FALSE if it is to the right. When a Boolean value is determined for the root of the tree, the location of + is known: a value of TRUE indicates that + is inside the polygon and FALSE indicates that it is outside. The CSG tree is evaluated via postorder traversal. After each edge is tested, there are exactly two choices as to which edge to test next; the selection of this edge is determined from the Boolean result of testing the current edge. These choices can be encoded in a new data structure, the edge-sequence graph (ESG), in such a way that most of the processing time required to perform the point-in-polygon test will be occupied in testing the point against edges of the polygon rather than determining which edges to test. We amortize the cost of constructing an ESG across tests of multiple points for the same polygon. We assume that once a given embedding for the tree has been chosen, that embedding is used to perform all point-in-polygon tests henceforth. It would be costly to alter the embedding during the actual point test. An ESG is a data structure representing a single polygon; it contains an array of edges (edges), an array of indices into the edge array (lookup), an integer indicating the number of edges in the polygon (edgec), and a Boolean flag indicating whether the polygon is oriented counterclockwise (ccw). The latter is not strictly required, but is of practical value when comparing the algorithm against other algorithms that ignore orientation of edges in defining the true interior of a polygon. The lookup array contains two elements for each edge occurring in the polygon. An ESG is constructed from a CSG tree via the following algorithm”)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to modify the method of editing the inferred editable feature tree of CSG of Mehr and Kania with using post order traversal as seen in Walker because this modification would evaluate the CSG tree via postorder traversal (see section 3.2 Building the Edge-Sequence Graph of Walker).
Thus, the combination of Mehr, Kania and Walker teaches further comprising: pruning the binary tree to remove redundant subtrees to obtain a pruned binary tree by visiting nodes in the tree in post-order and deleting redundant nodes, wherein a node is redundant when replacement of the node with a full object or an empty object results in a difference in an output of a Boolean operation associated with the node in the binary tree that satisfies a threshold.
8. Claim 15 is rejected under 35 U.S.C. 103 as being unpatentable over Mehr et al, U.S Patent Application Publication No.2020/0250894 (“Mehr”) in view of KANIA et al, IDS, 2020 UCSG-NET-unsupervised discovering of constructive solid geometry tree Advances in Neural Information Processing Systems 33 (2020), 8776-8786 (“Kania”) further in view of Walker, Robert J., and Jack Snoeyink, NPL, "Practical point-in-polygon tests using CSG representations of polygons." Workshop on algorithm engineering and experimentation. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. (“Walker”) further in view of Rohan Kumar Singh, NPL, “Postorder Traversal without Recursion”; 3 May 2023, https://www.scaler.com/topics/postorder-traversal-without-recursion/ (“Singh”)
Regarding claim 15, Mehr, Kania and Walker teach the computer-implemented method of claim 14, further comprising traversing the pruned binary tree using a linear time traversal algorithm on a forward pass in post-order using a stack when using the pruned binary tree to infer properties of the CSG model of the 3D object (see at least of Mehr [0200] The example machine-learning process allows learning a recurrent neural network which predicts a CSG tree from a raw mesh. Firstly, a synthetic dataset of CSG trees is randomly generated. Each CSG tree in the dataset is reduced to its minimal expression, in order to remove any redundancy. This dataset is used to train in a supervised way a recurrent neural network to predict a CSG tree from a raw mesh. The network is then refined in an unsupervised way by reinforcement learning on a real dataset of raw meshes, whose CSG trees are unknown. Finally, the network is used to infer plausible CSG trees from a new raw mesh. An optimization scheme is used to refine the continuous parameters of the tree in order to fit at best the CSG tree to the input mesh. [0201] Also, any CSG tree in the example machine-learning process is a single-rooted and full binary tree (of the type where each non-leaf node has at least one leaf node as a child).”; section Interpretability “..To further combine these primitives through CSG operations, we calculate argmaxi∈M ˆV(l) left,i, arg maxj∈M ˆV(l) right,j for left and right operands respectively. Then, we perform operations A∪∗ B, A∩∗B, A−∗B and B−∗A. When∀l≤Lτ(l) ≈ 0, both ˆ V(l) left, ˆ V(l) right are one-hot vectors, and operations performed on occupancy values, as in Figure 2, are equivalent to CSG operations executed on aforementioned meshes, ex. by merging binary space partitioning trees of meshes [12]. Additionally, the whole CSG tree can be pruned to form binary tree, by investigating which meshes were selected through ˆ V(l) left, ˆ V(l) 2L−l nodes at each layer l ≤ L.2see section 3.2 Building the Edge-Sequence Graph, “ For a given point + , we can evaluate every leaf of the CSG tree, and hence, every edge of the polygon it represents. The logical operators within the tree could then be evaluated to determine the location of + . However, we can take advantage of the alternating structure of the logical operators found in the CSG tree to prune unrequired edges from the tree during traversal. As soon as a node evaluates to FALSE and is the child of an AND node ] , we may stop testing the children of ] and assign the Boolean value FALSE to ] . Likewise, assoonas anode testing the children of 0^ evaluates to TRUE and 0^ is the child of an OR node ] ^ , we maystop ] ^ and assign TRUE to ]'^ . At a leaf node _ , we assign TRUE if + is to the left of the edge represented by _ , and FALSE if it is to the right. When a Boolean value is determined for the root of the tree, the location of + is known: a value of TRUE indicates that + is inside the polygon and FALSE indicates that it is outside. The CSG tree is evaluated via postorder traversal. After each edge is tested, there are exactly two choices as to which edge to test next; the selection of this edge is determined from the Boolean result of testing the current edge. These choices can be encoded in a new data structure, the edge-sequence graph (ESG), in such a way that most of the processing time required to perform the point-in-polygon test will be occupied in testing the point against edges of the polygon rather than determining which edges to test. We amortize the cost of constructing an ESG across tests of multiple points for the same polygon. We assume that once a given embedding for the tree has been chosen, that embedding is used to perform all point-in-polygon tests henceforth. It would be costly to alter the embedding during the actual point test. An ESG is a data structure representing a single polygon; it contains an array of edges (edges), an array of indices into the edge array (lookup), an integer indicating the number of edges in the polygon (edgec), and a Boolean flag indicating whether the polygon is oriented counterclockwise (ccw). The latter is not strictly required, but is of practical value when comparing the algorithm against other algorithms that ignore orientation of edges in defining the true interior of a polygon. The lookup array contains two elements for each edge occurring in the polygon. An ESG is constructed from a CSG tree via the following algorithm.”) In addition, the same motivation is used as the rejection for claim 14.
In the same field of endeavor, Singh teaches traversing the tree using a linear time traversal algorithm on a forward pass in post-order using a stack (whole paper, see at least Example Explanation, “Let's understand how post-order traversal is done using two stacks by traversing on the tree shown below and see algorithm 1 and algorithm 2 where Time Complexity: As in the post-order traversal every node is iterated and pushed to the stack so the time taken to do traversal on every node of the tree is O(n), where n is the number of nodes in the tree which is considered as a linear time traversal algorithm using a stack)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to modify the method of editing the inferred editable feature tree of CSG of Mehr, Kania and using post order traversal of Walker with using stack for post order traversal as seen in Singh because this modification would store the nodes of the binary tree (algorithm 1 of Singh).
Thus, the combination of Mehr, Kania, Walker and Singh teaches further comprising traversing the pruned binary tree using a linear time traversal algorithm on a forward pass in post-order using a stack when using the pruned binary tree to infer properties of the CSG model of the 3D object.
Contact
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SARAH LE whose telephone number is (571)270-7842. The examiner can normally be reached Monday: 8AM-4:30PM EST, Tuesday: 8 AM-3:30PM EST, Wednesday: 8AM-2:30PM EST, Thursday and Friday off.
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, Kent Chang can be reached at (571) 272-7667. 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.
/SARAH LE/ Primary Examiner, Art Unit 2614
Prosecution Insights