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 .
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.
Claims 1-4 and 12-15 are rejected under 35 U.S.C. 103 as being unpatentable over Wald (US 20180190013 A1) in view of Lu, et al. (Lu, Jiayin, et al. “An extension to Voro++ for multithreaded computation of Voronoi cells” Computer Physics Communications Volume 291, October 2023, 108832. ScienceDirect, 2023.) and Amenta (Amenta, Nina. “Nearest-neighbor search” ECS 226 - Computational Geometry CRN #43770. Department of Computer Science in the University of California at Davis, 2011.).
Regarding claims 1 and 12, for claim 1, Wald teaches A GPU-based method for computing a Voronoi mesh for a plurality of seed points, in an n-dimensional space where n ≥ 2, segmented into octants represented by an octree, the method comprising:
storing the octree (spec [0134]; “One embodiment of the invention relies on the following key kernels which may be executed, regardless of the type of data structure used (e.g., kd-tree or multi-octree):”) on a memory of the GPU; (spec [0042]; “In some embodiments, graphics processor 300 includes a memory interface 314 to access memory. Memory interface 314 can be an interface to local memory, one or more internal caches, one or more shared external caches, and/or to system memory.”)
with the GPU, (spec [0042]; “FIG. 3 is a block diagram of a graphics processor 300, which may be a discrete graphics processing unit, or may be a graphics processor integrated with a plurality of processing cores.”)
using the octree, identifying a set of neighboring seed points in an initial set of octants that are adjacent to a first octant containing the first seed point; (spec [0179]; “For the octant edge vertex Vxy we look at all the neighbor cells that touch Vxy, which are Cx,Cy, and Cxy.”)
identifying zero or more new octants, where each new octant (i) during a first iteration, is adjacent to at least one octant from the initial set of octants, or during a subsequent iteration, is adjacent to at least one new octant identified in the immediately prior iteration, and (spec [0165]; “At these level boundaries the frequency of octants on the fine and coarse sides of this boundary varies, but coarse ones align to fine ones. Furthermore, the vertices of these (implicit) octants at cell boundaries are free to be chosen, allowing the construction of an interpolant in a way that is continuous at the cell boundaries (even those from different levels), while still interpolating the original data points (that always lie within the cells)”)
However, Wald does not teach finding a Voronoi cell around a first seed point in the plurality of seed points using a cell-finding method comprising:
from the first seed point,
using the set of neighboring seed points, determining a set of bisectors that together form a boundary around the first seed point, where each bisector is midway between the first seed point and one of the neighboring seed points, and each bisector meets adjacent bisectors at a shared vertex;
outputting data characterizing the boundary from the last determining step as the Voronoi cell containing the first seed point; and
storing the Voronoi cell
Lu teaches finding a Voronoi cell around a first seed point in the plurality of seed points using a cell-finding method comprising: (2.1.5. Procedure for Voronoi cell computation; “Loop over the particles in the block, and for each particle:”)
from the first seed point, (2.1.5. Procedure for Voronoi cell computation; “Calculate the Voronoi cell of the particle.”)
using the set of neighboring seed points, determining a set of bisectors that together form a boundary around the first seed point, where each bisector is midway between the first seed point and one of the neighboring seed points, and each bisector meets adjacent bisectors at a shared vertex; (2.1.2. Using a voronoicell_2d class to compute a Voronoi cell and fig. 4; “Fig. 4. Illustration of the action of the plane() routine. The Voronoi cell of a particle P located at p is initialized as a large rectangular box filling the computational domain. The plane() routine repeatedly cuts down the rectangular box by planes that are the perpendicular bisectors between the particle and its neighbors, located at q1 and q2.”, in fig. 4, where the bisectors intersect is a shared vertex.)
outputting data characterizing the boundary from the last determining step as the Voronoi cell containing the first seed point; and (2.1.2. Using a voronoicell_2d class to compute a Voronoi cell, “The voronoicell_2d class represents a single Voronoi cell as a convex polygon, with a set of vertices connected by edges.”)
storing the Voronoi cell (1.2. The cell-based approach: advantages and drawbacks; “In Voro++ a typical workflow is to compute a Voronoi cell, calculate and store various statistics about the cell, delete the cell, and move onto the next point.”)
It would be obvious to a person having ordinary skill in the art to combine Wald’s apparatus for an octree and combine it with Lu’s software for computing Voronoi cells so they could create Voronoi diagrams more easily using an octree.
However, Wald in view of Lu does not teach one or more times, iterating the sub-method comprising:
(ii) includes a portion of the n-dimensional space that is no more than a distance ε farther from a vertex than the vertex is from the first seed point; and
adding any new seed points in the zero or more new octants to the set of neighboring seed points;
until the identifying step identifies no new octants;
Amenta teaches one or more times, iterating the sub-method comprising: (page 1, {find an Approximate Nearest Neighbor to query point q} line 5; “while δ ≥ r do”, discloses a code the checks for the nearest neighbor using a while loop.)
(ii) includes a portion of the n-dimensional space that is no more than a distance ε farther from a vertex than the vertex is from the first seed point; and (page 1 paragraph 5; “while δ ≥ (1 + ε)r do”, this can be changed to “while δ ≥ r + ε do” to add an error distance rather than multiplying by an error percentage.)
adding any new seed points in the zero or more new octants to the set of neighboring seed points; (page 1, {find an Approximate Nearest Neighbor to query point q} lines 7-13; “r =d(q,B) if d(q,p) < δ then p becomes best choice seen so far and δ = d(q,p) end if for all children B’ of B containing points in P do enqueue (B’) end for”, boxes (sometimes called cells) B and B’ would be octants.)
until the identifying step identifies no new octants; (page 1, {find an Approximate Nearest Neighbor to query point q} lines 6 and 14; “dequeue box B, containing representative point p” and “end while”)
It would be obvious to a person having ordinary skill in the art to combine Wald’s apparatus for an octree and combine it with Lu’s software for computing Voronoi cells and then combining them with Amenta’s algorithm to find neighboring points/octants more efficiently.
For claim 12, Wald teaches A system for computing a Voronoi mesh for a plurality of seed points, in an n-dimensional space where n ≥ 2, segmented into octants represented by an octree, the system comprising:
a processor; (spec [0042]; “FIG. 3 is a block diagram of a graphics processor 300, which may be a discrete graphics processing unit, or may be a graphics processor integrated with a plurality of processing cores.”)
a GPU; (spec [0042]; “FIG. 3 is a block diagram of a graphics processor 300, which may be a discrete graphics processing unit, or may be a graphics processor integrated with a plurality of processing cores.”)
a non-transitory storage device; and (spec [0033]; “a data storage device 124 (e.g., hard disk drive, flash memory, etc.),”)
a memory storing instructions whereby the processor is configured to perform the steps of: (spec [0042]; “In some embodiments, graphics processor 300 includes a memory interface 314 to access memory.”)
The rest of claim 12 are recitations of claim 1’s limitations and are rejected using the rationale of claim 1.
Regarding claims 2 and 13, for claim 2, Wald in view of Lu and Amenta teaches The method of claim 1, where n is three. (Lu; 1. Introduction and fig. 1; “(b) An example three-dimensional Voronoi tessellation shown in blue generated by the white spheres. A single Voronoi cell is shown in red as an irregular polyhedron. (For interpretation of the colors in the figure(s), the reader is referred to the web version of this article.)”)
Claim 13 recites claim 2, but depends on claim 12 instead, and is rejected using the same rationale as claim 2.
Regarding claims 3 and 14, for claim 3, Wald in view of Lu and Amenta teaches The method of claim 1, where the programming instructions are further executable by the GPU to run the cell-finding method on multiple seed points in parallel. (Lu; 1.3. Outline of this paper; “Here, we consider parallelizing Voro++ using a shared-memory model with multithreading.”)
Claim 14 recites claim 3, but depends on claim 12 instead, and is rejected using the same rationale as claim 3.
Regarding claims 4 and 15, for claim 4, Wald in view of Lu and Amenta teaches The method of claim 1, further comprising, with the GPU:
running the cell-finding method on each seed point in the plurality of seed points; (Lu; 2.1.5. Procedure for Voronoi cell computation; “Loop over the particles in the block, and for each particle:”)
creating a composite of the Voronoi cells for the plurality of seed points as a consistently connected Voronoi mesh; and (Lu; 1.2. The cell-based approach: advantages and drawbacks and fig. 2(a, b); “As discussed by Okabe et al. [2] it has a significant difficulty that is illustrated in Fig. 2(a, b). In most cases, for randomly-distributed points, each vertex of the Voronoi tessellation will be common between three Voronoi cells as shown in Fig. 2(a).”)
storing the consistently connected Voronoi mesh (Lu; 1.2. The cell-based approach: advantages and drawbacks and fig. 2(a, b); “As discussed by Okabe et al. [2] it has a significant difficulty that is illustrated in Fig. 2(a, b). In most cases, for randomly-distributed points, each vertex of the Voronoi tessellation will be common between three Voronoi cells as shown in Fig. 2(a).”) on the memory of the GPU. (Wald; spec [0201]; “It should be possible to precompute and store all octant vertices at those cell boundaries.”)
Claim 15 recites claim 4, but depends on claim 12 instead, and is rejected using the same rationale as claim 4.
Claims 5-6,9-11, 16-17 and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Wald (US 20180190013 A1) in view of Lu, et al. (Lu, Jiayin, et al. “An extension to Voro++ for multithreaded computation of Voronoi cells” Computer Physics Communications Volume 291, October 2023, 108832. ScienceDirect, 2023.), Amenta (Amenta, Nina. “Nearest-neighbor search” ECS 226 - Computational Geometry CRN #43770. Department of Computer Science in the University of California at Davis, 2011.) and Lévy (Lévy, Bruno. “Robustness and efficiency of geometric programs: The Predicate Construction Kit (PCK)” 23rd International Meshing Roundtable Special Issue: Advances in Mesh Generation Volume 72, 2016, Pages 3-12. ScienceDirect, 2016.).
Regarding claims 5 and 16, Wald in view of Lu and Amenta teaches The method of claim 4, further comprising, when creating the composite of the Voronoi cells, (Lu; 1.2. The cell-based approach: advantages and drawbacks and fig. 2(a, b); “As discussed by Okabe et al. [2] it has a significant difficulty that is illustrated in Fig. 2(a, b). In most cases, for randomly-distributed points, each vertex of the Voronoi tessellation will be common between three Voronoi cells as shown in Fig. 2(a).”)
However, Wald in view of Lu and Amenta doesn’t teach guaranteeing that the consistently connected Voronoi mesh is topologically consistently connected by computing robust geometric predicates on the GPU and using the memory of the GPU in order to exclude round-off errors due to floating point operations.
Lévy teaches guaranteeing that the consistently connected Voronoi mesh is topologically consistently connected by computing robust geometric predicates on the GPU and using the memory of the GPU in order to exclude round-off errors due to floating point operations. (A first solution: exact arithmetics using dynamic integers; “There are already several existing programming libraries that implement exact arithmetics. For instance, when considering integer arithmetics, it is possible to represent an integer of arbitrary precision by an array of integers a[0]…a[l-1].”)
It would be obvious to a person having ordinary skill in the art to combine Wald’s apparatus, Lu’s software and Amenta’s algorithm to create the apparatus that creates a Voronoi mesh using an octree where its octants are checked by a distance, and then use Lévy’s exact arithmetics to ensure the Voronoi diagram is consistent so to prevent outputting incorrect Voronoi diagrams.
Regarding claims 6 and 17, Wald in view of Lu, Amenta and Lévy teaches The method of claim 5, further comprising using a compression method to reduce use of the memory of the GPU (Wald; spec [0201]; “Any structured volume can be represented in the form of multi-octree, using either lossy or lossless compression.”) during computation of the robust geometric predicates. (A first solution: exact arithmetics using dynamic integers; “There are already several existing programming libraries that implement exact arithmetics. For instance, when considering integer arithmetics, it is possible to represent an integer of arbitrary precision by an array of integers a[0]…a[l-1].”)
It would be obvious to a person having ordinary skill in the art to combine Wald’s apparatus, Lu’s software, Amenta’s algorithm and Lévy’s exact arithmetics to create the apparatus that creates a Voronoi mesh using an octree where its octants are checked by a distance and ensures that the Voronoi cells are consistent, and combine that apparatus to use Wald’s compression during the Lévy’s exact arithmetics to use less memory.
Regarding claims 9 and 20, Wald in view of Lu and Amenta teaches The method of claim 1, further comprising an interleaved testing step when identifying new octants and determining bisectors, the interleaved testing step comprising:
However, Wald in view of Lu and Amenta doesn’t teach performing an inexact test for whether existing vertices of any Voronoi cell are clipped off by a potential new neighbor site;
performing an error-bounds check on the result of the inexact test based on configured error bounds; and
for any potential new neighbor sites that fail the error bound check, performing an exact check for whether existing vertices of a Voronoi cell are clipped off by the potential new neighbor site.
Lévy teaches performing an inexact test for whether existing vertices of any Voronoi cell are clipped off by a potential new neighbor site; (1.1. Geometric predicates; “an arithmetic filter:[3], that gives an answer in the “easy cases” where the exact answer can be determined using standard floating point arithmetics. This is the key to efficiency (obtaining correctness and robustness without paying the price for it!);”)
performing an error-bounds check on the result of the inexact test based on configured error bounds; and (1.1. Geometric predicates; “For this reason, to improve performances, it is interesting to have a way of determining the answer in the “easy cases”, where we are sure that the result computed using double precision floating points is exact. In other words, this corresponds to configuration where we are sure that the sign of the computed floating point number is correct. Meyer and Pion introduced a method that computes bounds from the formula of the predicate [3]. If the absolute value of the result is larger than the bound, then they prove that the sign is correct. In addition, the bounds can be dynamically adjusted to the input, thus making it even more efficient (with these dynamic bounds, a quick decision can be taken in a much larger number of cases).”)
for any potential new neighbor sites that fail the error bound check, performing an exact check for whether existing vertices of a Voronoi cell are clipped off by the potential new neighbor site. (1.1. Geometric predicates; “exact arithmetics :[1], used when the filter could not determine the answer, this is the key to correctness and robustness;”)
It would be obvious to a person having ordinary skill in the art to combine Wald’s apparatus, Lu’s software and Amenta’s algorithm to create the apparatus that creates a Voronoi mesh using an octree where its octants are checked by a distance, and then use Lévy’s technique of checking the error bounds to see if the Voronoi diagram is consistent so computation is faster.
Claim 20 recites claim 9, but depends on claim 12 instead, and is rejected using the same rationale as claim 9.
Regarding claim 10, Wald in view of Lu, Amenta and Lévy teaches The method of claim 9, further comprising, before performing the interleaved testing step:
determining whether the potential new neighbor site has already been tested during a prior iteration; and (Wald; spec [0201]; “For high sample rates, one can use a cache for already-evaluated octants.”, the cache can be used for neighboring sites.)
where it has already been tested, skipping the interleaved testing step for that potential new neighbor site. (Wald; spec [0201]; “For high sample rates, one can use a cache for already-evaluated octants.”, it is implied that the cache is used for skipping octants and can be used for neighboring sites.)
Regarding claim 11, Wald in view of Lu, Amenta and Lévy teaches The method of claim 9, further comprising, during the steps of identifying new octants and determining bisectors:
compressing the representation of vertices (Lu; 2.1.2. Using a voronoicell_2d class to compute a Voronoi cell; “The voronoicell_2d class represents a single Voronoi cell as a convex polygon, with a set of vertices connected by edges.”) into a compact representation for those vertices which are finally computed; and (Wald; spec [0201]; “Any structured volume can be represented in the form of multi-octree, using either lossy or lossless compression.”)
storing the compressed encoding of the vertex in the memory of the GPU. (Wald; spec [0201]; “It should be possible to precompute and store all octant vertices at those cell boundaries.”)
It would be obvious to a person having ordinary skill in the art to combine Wald’s apparatus, Lu’s software and Amenta’s algorithm to create the apparatus that creates a Voronoi mesh using an octree where its octants are checked by a distance, and then use Wald’s compression on Lu’s Voronoi cells and store them in Wald’s GPU memory to use less storage and use the information for later.
Claims 7 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Wald (US 20180190013 A1) in view of Lu, et al. (Lu, Jiayin, et al. “An extension to Voro++ for multithreaded computation of Voronoi cells” Computer Physics Communications Volume 291, October 2023, 108832. ScienceDirect, 2023.), Amenta (Amenta, Nina. “Nearest-neighbor search” ECS 226 - Computational Geometry CRN #43770. Department of Computer Science in the University of California at Davis, 2011.) and Altaweel (Altaweel, Mark. “Voronoi Diagrams and GIS” Geography Realm 2019.).
Regarding claims 7 and 18, Wald in view of Lu and Amenta teach The method of claim 6, on the GPU using the consistently connected Voronoi mesh stored in the memory of the GPU. (Wald; spec [0042]; “In some embodiments, graphics processor 300 includes a memory interface 314 to access memory.”)
However, Wald in view of Lu and Amenta doesn’t teach further comprising running a solver
Altaweel teaches further comprising running a solver (Applications of Voronoi Tessellations; “Other approaches to voronoi research have included using 3D GIS to better represent how cameras are placed for security reasons.”)
It would be obvious to a person having ordinary skill in the art to combine Wald’s apparatus, Lu’s software and Amenta’s algorithm to create the apparatus that creates a Voronoi mesh using an octree where its octants are checked by a distance, and then use Altaweel’s GIS application to determine where a security camera should go.
Claim 18 recites claim 7, but depends on claim 12 instead, and is rejected using the same rationale as claim 7.
Claims 8 and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Wald (US 20180190013 A1) in view of Lu, et al. (Lu, Jiayin, et al. “An extension to Voro++ for multithreaded computation of Voronoi cells” Computer Physics Communications Volume 291, October 2023, 108832. ScienceDirect, 2023.), Amenta (Amenta, Nina. “Nearest-neighbor search” ECS 226 - Computational Geometry CRN #43770. Department of Computer Science in the University of California at Davis, 2011.) and Kohler (US 20230149813 A1).
Regarding claims 8 and 19, Wald in view of Lu and Amenta teaches The method of claim 1,
However, Wald in view of Lu and Amenta doesn’t teach wherein each seed point is at the centroid of an octant, and wherein each octant contains exactly one seed point.
Kohler teaches wherein each seed point is at the centroid of an octant, and wherein each octant contains exactly one seed point. (spec [0071]; “In a point region octree, the node stores an explicit three-dimensional point, which is the ‘center’ of the subdivision for that node; the point defines one of the corners for each of the eight children.”)
It would be obvious to a person having ordinary skill in the art to combine Wald’s apparatus, Lu’s software and Amenta’s algorithm to create the apparatus that creates a Voronoi mesh using an octree where its octants are checked by a distance, and then use Kohler’s region point octree for the apparatus in order to more easily compute Voronoi diagrams.
Claim 19 recites claim 8, but depends on claim 12 instead, and is rejected using the same rationale as claim 8.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to IRVING SHI whose telephone number is (571)272-9613. The examiner can normally be reached Monday-Friday.
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, Tammy Goddard can be reached at (571) 272-7773. 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.
/IRVING NMN SHI/Examiner, Art Unit 2611
/TAMMY GODDARD/
Supervisory Patent Examiner, Art Unit 2611
Prosecution Insights