Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Amendment
The amendment filed on 8/4/26 has been entered and made of record. Claims 1-5, 7-10 and 12-13 are amended. Claims 19-20 are new. Claims 1-20 are pending.
Response to Arguments
Applicant’s arguments with respect to claim 1 have been fully considered but they are moot because the arguments do not apply to the references being used in the current rejection.
Claim Rejections - 35 USC § 103
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 of this title, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-10 and 12-20 are rejected under 35 U.S.C. 103 as being unpatentable over Buhrig et al. (US 11,474,720 B1) in view of Bigos (US 2023/0281912 A1) and Bogacz et al. (US 11,227,432 B1).
As to Claim 1, Buhrig teaches A computer-implemented method for visualizing 3D data of a multitude of data sets in a scene using a computing device having memory for visualizing the 3D data, wherein the memory available for visualizing the 3D data is insufficient for loading all of the 3D data of the multitude of data sets into the memory at one time for visualization (Buhrig, Abstract), the method comprising, in the computing device:
receiving the multitude of data sets, each data set of the multitude of data sets having a level-of-detail structure given as a tree comprising a multitude of nodes, including a root node and branches with nodes having a parent-child relation with respect to each other (Buhrig discloses “As shown in FIG. 4A, custom heap manager 300 may receive (at 402) a first set of nodes from a tree-based representation of a point cloud to process and/or render in order to create a first visualization of the point cloud” in C7L12-16; see also C3L4-12 & 26-46);
determining the amount of memory available for visualizing the 3D data (Buhrig discloses “Accordingly, GPU heap manager 200 may allocate different amounts of memory for different nodes, and may upload different amounts of data to each allocated memory block” in C5L3-6; “custom heap manager 300 may perform (at 302) a single memory allocation to acquire a large block of GPU memory 203 irrespective of the nodes and/or data points that are to be processed and/or rendered during any given execution cycle or pass” in C5L64-C6L1);
selecting nodes of the data sets that comprise 3D data to be loaded into the available memory; loading the 3D data of the selected nodes into the memory (Buhrig discloses “…may assign each node of the set of nodes to an exclusive range of addresses within the single block of memory, and may upload data of each of the set of nodes to the single block of memory in the exclusive range of addresses assigned to each node” in Abstract); and
visualizing the 3D data loaded into the memory on a display (Buhrig discloses “the point cloud may be rendered with different levels of detail at different regions of the 3D space by selectively rendering different nodes at different layers of the tree-based representation” at C4L36-39);
allocating the available memory to the multitude of 3D regions; and selecting, based on the allocated memory, nodes that comprise 3D data to be loaded into the available memory (Buhrig discloses “GPU heap manager 200 may allocate different amounts of memory for different nodes, and may upload different amounts of data to each allocated memory block” in C5L3-6. Bigos discloses higher memory costs having to render the entire 3D scene within the frustum in [0077], see also Fig 4.);
wherein allocating the available memory comprises:
determining, based at least on the amount of memory available, a first tree-traversal depth (Buhrig discloses “The heap memory manager may receive a set of nodes from a tree-based representation of a point cloud… may allocate a single block of memory for processing and/or rendering the set of nodes, may assign each node of the set of nodes to an exclusive range of addresses within the single block of memory” in Abstract; “processing system to quickly and efficiently access different subsets of data points that share specific commonality represented by different branches or parent nodes of the tree-based representation” in C3L7-10, see also C8L6-16);
traversing the level-of-detail structure of each foreground data set using the first tree-traversal depth (Buhrig discloses “a rendering system may determine the render frustum, may determine different levels of detail with which to render different regions of the render frustum, and may process and/or render nodes of the point cloud tree-based representation at the corresponding levels of detail… or may determine to render nodes or data points in a near plane of the render frustum with the first level of detail and nodes or data points in farther planes of the render frustum with progressively lesser levels of detail” in C4L40-51; “Custom heap manager 300 may retain the memory allocation when rendering subsequent images or frames for the same point cloud using different nodes from the tree-based representation… custom heap manager 300 may mark the memory offsets where the data for the first node is stored as being free or unused, may assign the second node to the memory offsets that are marked as free or unused, and may upload the data of the second node to the assigned memory offsets” in C6L43-57.);
mapping each recorded node to one of the 3D regions (Buhrig discloses “the point cloud may be rendered with different levels of detail at different regions of the 3D space by selectively rendering different nodes at different layers of the tree-based representation” in C4L36-39).
Buhrig teaches near/far plane of the render frustum without detailed description. The combination of Bigos teaches following limitations:
wherein selecting the nodes comprises performing a level-of-detail selection comprising:
obtaining camera frustum information defining a camera frustum comprising at least a part of the scene, the camera frustum comprising a near plane and a far plane; dividing the camera frustum by defining at least a near frustum and a background frustum, the near frustum being adjacent to the near plane and comprising a foreground of the scene, the background frustum being adjacent to the far plane and comprising a background of the scene; defining a subset of data sets as foreground data sets based on an overlap of the nodes of the respective data set with the near frustum; dividing at least one of the near frustum and the background frustum of the camera frustum into a multitude of 3D regions (Buhrig discloses “Accordingly, the point cloud may be rendered with different levels of detail at different regions of the 3D space by selectively rendering different nodes at different layers of the tree-based representation….a rendering system may determine the render frustum, may determine different levels of detail with which to render different regions of the render frustum, and may process and/or render nodes of the point cloud tree-based representation at the corresponding levels of detail… or may determine to render nodes or data points in a near plane of the render frustum with the first level of detail and nodes or data points in farther planes of the render frustum with progressively lesser levels of detail” in C4L36-51. Here, Buhrig teaches near frustum plane and farther frustum plane, which is well-known clipping plane. For example, Bigos discloses “In FIG. 4, it can be seen that the frustum 405 of the virtual camera 404 has been split up into a plurality of successive slices. Each slice corresponds to a respective depth segment, with the extremities of each depth segment being defined by a pair of clipping planes… Each pair of clipping planes truncates the frustum 405 into a respective depth segment” in [0046], see also Fig 4 below:
PNG
media_image1.png
659
1019
media_image1.png
Greyscale
).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the invention of Buhrig with the teaching of Bigos so as to explain a clipping plane to intersect virtual objects in a virtual scene.
The combination of Bogacz further teaches following limitations:
thereby recording all nodes that have an overlap with the camera frustum and determining a screen space for each of the recorded nodes; assigning memory to each region based on the screen spaces of the nodes that have been mapped to the respective 3D region (Buhrig discloses “In any case, GPU heap manager 200 may perform a separate memory allocation for each node, and the allocations may be of different sizes based on different amounts of data associated with each node” in C5L53-56. Bogacz further discloses “The system may receive a request to render the 3D environment, load a first tree into memory, generate a first image from the first tree data points, flush the first tree from the memory, load a second tree into the memory, generate a second image from the second tree data points, and present a composite image by combining at least the first image with the second image” in Abstract, see also Fig 5.)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the invention of Buhrig and Bigos with the teaching of Bogacz so as to generate a 3D environment by combining the first set of tree data points with the second set of tree data points (Bogacz, Abstract).
As to Claim 2, Buhrig in view of Bigos and Bogacz teaches The method according to claim 1, comprising defining a subset of data sets as background data sets based on an overlap of the nodes of the respective data set with the background frustum, wherein allocating the available memory comprises:
traversing the level-of-detail structure of each background data set using the first or a second tree-traversal depth, thereby recording all nodes that have an overlap with the camera frustum and determining a screen space for each of the recorded nodes (Buhrig discloses “a rendering system may determine the render frustum, may determine different levels of detail with which to render different regions of the render frustum, and may process and/or render nodes of the point cloud tree-based representation at the corresponding levels of detail… or may determine to render nodes or data points in a near plane of the render frustum with the first level of detail and nodes or data points in farther planes of the render frustum with progressively lesser levels of detail” in C4L40-51; “Custom heap manager 300 may retain the memory allocation when rendering subsequent images or frames for the same point cloud using different nodes from the tree-based representation… custom heap manager 300 may mark the memory offsets where the data for the first node is stored as being free or unused, may assign the second node to the memory offsets that are marked as free or unused, and may upload the data of the second node to the assigned memory offsets” in C6L43-57.);
mapping each recorded node to one of the regions (Buhrig discloses “the point cloud may be rendered with different levels of detail at different regions of the 3D space by selectively rendering different nodes at different layers of the tree-based representation” in C4L36-39); and
assigning memory to each region based on the screen spaces of the nodes that have been mapped to the respective region (Buhrig discloses “In any case, GPU heap manager 200 may perform a separate memory allocation for each node, and the allocations may be of different sizes based on different amounts of data associated with each node” in C5L53-56. Bogacz further discloses “The system may receive a request to render the 3D environment, load a first tree into memory, generate a first image from the first tree data points, flush the first tree from the memory, load a second tree into the memory, generate a second image from the second tree data points, and present a composite image by combining at least the first image with the second image” in Abstract, see also Fig 5.)
As to Claim 3, Buhrig in view of Bigos and Bogacz teaches The method according to claim 2, wherein for traversing the level-of-detail structure of each background data set the first tree-traversal depth is used, and determining the first tree-traversal depth is also based on a number of data sets in the camera frustum (Buhrig discloses a tree-based structure, or rendering point cloud as a hierarchical space-partitioning data structure in col 3; “Accordingly, the point cloud may be rendered with different levels of detail at different regions of the 3D space by selectively rendering different nodes at different layers of the tree-based representation. In some embodiments, a rendering system may determine the render frustum, may determine different levels of detail with which to render different regions of the render frustum, and may process and/or render nodes of the point cloud tree-based representation at the corresponding levels of detail” in C4L36-45.)
As to Claim 4, Buhrig in view of Bigos and Bogacz teaches The method according to claim 2, wherein for traversing the level-of-detail structure of each background data set a second tree-traversal depth is used, wherein:
determining the first tree-traversal depth is also based on a number of data sets in the near frustum, and allocating the available memory comprises determining, based at least on the amount of memory available and on a number of data sets in the background frustum, the second tree-traversal depth (Buhrig discloses “The tree may also represent the point cloud with different levels of detail. In some embodiments, the highest or greatest level of detail for representing the point cloud may be defined at the leaf node layer of the tree. Each leaf node may correspond to a different data point of the point cloud” in C3L26-30; “Process 500 may include assigning (at 508) each node of the sorted first set of nodes to different available or unassigned address ranges within the allocated memory. Assigning (at 508) a node may include reserving an address range within the allocated memory that is large enough or equal in size to the data contained by that node” in C11L5-10.)
As to Claim 5, Buhrig in view of Bigos and Bogacz teaches The method according to claim 4, wherein allocating the available memory comprises:
estimating, based at least on a number of foreground data sets and background data sets, an amount of 3D data in the foreground and in the background; and assigning, based on the estimated amount of 3D data in the foreground and in the background, the available memory as foreground memory to the foreground and as background memory to the background, wherein: determining the first tree-traversal depth is based on the foreground memory, and determining the second tree-traversal depth is based on the background memory; and/or assigning memory to each region comprises assigning foreground memory to regions of the near frustum and background memory to regions of the background frustum (Buhrig discloses “In some embodiments, a rendering system may determine the render frustum, may determine different levels of detail with which to render different regions of the render frustum, and may process and/or render nodes of the point cloud tree-based representation at the corresponding levels of detail… or may determine to render nodes or data points in a near plane of the render frustum with the first level of detail and nodes or data points in farther planes of the render frustum with progressively lesser levels of detail” in C4L40-51; “In some embodiments, the amount of detail selected for the particular image or frame may exceed the amount of allocated memory. In some such embodiments, some nodes may be excluded and not processed and/or rendered as part of the particular image or frame. For instance, as shown in FIG. 4, the last leaf node (e.g., node 5) is excluded from the processing and/or rendering execution cycle and/or pass as the other nodes from the first set of nodes have consumed all the available and/or allocated memory” in C8L11-20; “Process 500 may include assigning (at 508) each node of the sorted first set of nodes to different available or unassigned address ranges within the allocated memory. Assigning (at 508) a node may include reserving an address range within the allocated memory that is large enough or equal in size to the data contained by that node” in C11L5-10.)
As to Claim 6, Buhrig in view of Bigos and Bogacz teaches The method according to claim 5, wherein assigning the available memory as foreground memory to the foreground and as background memory to the background comprises giving more weight to the estimated amount of 3D data in the foreground, particularly wherein more of the available memory is assigned to the foreground than to the background (Buhrig discloses “In some embodiments, the first set of nodes may be sorted based on rendering priority. For instance, the nodes providing the most amount of detail, at the center of the image, in the foreground, and/or representing other prioritized sections of the image may be arranged first so that they are processed first and provided first access to the allocated memory” in C7L23-29.)
As to Claim 7, Buhrig in view of Bigos and Bogacz teaches The method according to claim 1, wherein determining the first tree-traversal depth is also based on a number of data sets in the near frustum (Buhrig discloses “The tree may also represent the point cloud with different levels of detail. In some embodiments, the highest or greatest level of detail for representing the point cloud may be defined at the leaf node layer of the tree. Each leaf node may correspond to a different data point of the point cloud” in C3L26-30; “Process 500 may include assigning (at 508) each node of the sorted first set of nodes to different available or unassigned address ranges within the allocated memory. Assigning (at 508) a node may include reserving an address range within the allocated memory that is large enough or equal in size to the data contained by that node” in C11L5-10.)
As to Claim 8, Buhrig in view of Bigos and Bogacz teaches The method according to claim 1, wherein dividing the camera frustum into a multitude of 3D regions comprises dividing both the near frustum and the background frustum into a multitude of 3D regions (Buhrig discloses “or may determine to render nodes or data points in a near plane of the render frustum with the first level of detail and nodes or data points in farther planes of the render frustum with progressively lesser levels of detail” in C4L48-51. Bogacz, Fig 5-7.)
As to Claim 9, Buhrig in view of Bigos and Bogacz teaches The method according to claim 8, wherein the near frustum and/or the background frustum are divided into at least nine 3D regions or in a 3x3 matrix (Buhrig discloses “In some embodiments, a point cloud may be represented using a binary tree, an octree, a k-d tree, or another tree” in C3L10-12. It is obvious that a tree-based structure may have at least nine subdivisions.)
As to Claim 10, Buhrig in view of Bigos and Bogacz teaches The method according to claim 1, wherein defining the subset of data sets as foreground data sets comprises determining whether the root node intersects the near frustum (Buhrig discloses “may determine to render nodes or data points in a near plane of the render frustum with the first level of detail and nodes or data points in farther planes of the render frustrum with progressively lesser levels of detail” in C4L48-51. Bigos also discloses “FIG. 8 shows schematically an example of ray-casting being used to determine whether a frontmost clipping plane intersects a virtual object in a virtual scene” in [0016].)
As to Claim 12, Buhrig in view of Bigos and Bogacz teaches The method according to claim 1, wherein the computing device is a hand-held device, and the 3D data loaded into the memory is visualized a display of the handheld device (Bogacz discloses a mobile device in C15L3 and touching in col 1.)
As to Claim 13, Buhrig in view of Bigos and Bogacz teaches The method according to claim 12, wherein the computing device is a tablet computer or smart phone and comprises a touch-sensitive display, wherein the 3D data loaded into the memory is visualized on the touch-sensitive display (Bogacz discloses a mobile device in C15L3 and touching in col 1.)
As to Claim 14, Buhrig in view of Bigos and Bogacz teaches The method according to claim 1, wherein the memory for visualizing the data sets is a memory of a graphics card of the computing device (Buhrig discloses a RAM on a GPU card in C11L49.)
Claim 15 is rejected based upon similar rationale as Claim 1.
Claim 16 is rejected based upon similar rationale as Claim 13.
Claim 17 recites similar limitations as claim 1 but in a device form. Therefore, the same rationale used for claim 1 is applied.
Claim 18 recites similar limitations as claim 13 but in a device form. Therefore, the same rationale used for claim 13 is applied.
As to Claim 19, Buhrig in view of Bigos and Bogacz teaches The method according to claim 1, wherein mapping each recorded node to one of the 3D regions comprises mapping each recorded node to the 3D region in which the recorded node has the largest screen-space area share (Buhrig discloses “the point cloud may be rendered with different levels of detail at different regions of the 3D space by selectively rendering different nodes at different layers of the tree-based representation” in C4L36-39); “Assigning (at 508) a node may include reserving an address range within the allocated memory that is large enough or equal in size to the data contained by that node” at C11L7-11. Bigos discloses “In FIG. 8, the clipping of the rearmost object is indicated by the thicker line 805 that coincides with clipping plane 804D. The thicker line 805 indicates a clipped region” in [0073]. Here, the rearmost plane is corresponding to a largest screen space area share.)
As to Claim 20, Buhrig in view of Bigos and Bogacz teaches The method according to claim 1, wherein assigning memory to each 3D region comprises assigning a memory share to each 3D region, and wherein selecting, based on the allocated memory, the nodes that comprise 3D data to be loaded into the available memory comprises, for each 3D region, sorting nodes mapped to the respective 3D region according to their screen-space areas and selecting, based on the memory share assigned to the respective 3D region, nodes having largest screen-space areas (Buhrig discloses a sorted set of nodes from the tree-based representation and assign each node of the sorted first set of nodes to different available or unassigned address ranges within the allocated memory in Fig 5; “To minimize the impact on the particular image or frame, the selected nodes may be sorted so that the nodes that do not fit in the memory and that are at the end of the sorted order relate to data points in the periphery, background, out-of-focus regions, represent the smallest region of space, and/or that are otherwise determined to be of less importance to the particular image or frame than other data points of earlier sorted nodes” in C8L20; “Assigning (at 508) a node may include reserving an address range within the allocated memory that is large enough or equal in size to the data contained by that node” at C11L7-11. See also Bigos’s rearrest clipping plane in Fig 8.)
Claim 11 is rejected under 35 U.S.C. 103 as being unpatentable over Buhrig in view of Bigos, Bogacz and Bijankumar et al. (US 2008/0225048 A1).
As to Claim 11, Buhrig in view of Bigos and Bogacz teaches The method according to claim 1, wherein selecting the nodes comprises removing invisible data sets before performing the level-of-detail selection, wherein the invisible data sets are removed by means of bounding-box culling (Bijankumar discloses “Many of these techniques attempt to minimize the number of primitives pushed into the graphics pipeline by utilizing visibility culling, levels of detail (LOD), or other techniques. Visibility culling techniques remove sections of the model that would be invisible from the current viewpoint. LOD-based techniques reduce the number of primitives in the model… Visibility culling can be further classified into view frustum culling and occlusion culling. View frustum culling prevents objects outside the view frustum from being processed… In various embodiments, view frustum culling can be optimized by using various optimization techniques, such as techniques described in Assarsson, U. & Moller, T., "Optimized View Frustum Culling Algorithms for Bounding Boxes,"…” in [0005].)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the invention of Buhrig and Bogacz with the teaching of Bijankumar so as to utilize a combination of both visibility culling and LOD techniques to reduce the number of primitives that are rendered (Bijankumar, [0005]).
Conclusion
THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any extension fee pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to WEIMING HE whose telephone number is (571)270-1221. The examiner can normally be reached Monday-Friday, 8:30am-5:00pm.
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 on 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.
/Weiming He/
Primary Examiner, Art Unit 2611
