Ex Parte Soupikov et alDownload PDFPatent Trial and Appeal BoardOct 24, 201713505007 (P.T.A.B. Oct. 24, 2017) Copy Citation United States Patent and Trademark Office UNITED STATES DEPARTMENT OF COMMERCE United States Patent and Trademark Office Address: COMMISSIONER FOR PATENTS P.O.Box 1450 Alexandria, Virginia 22313-1450 www.uspto.gov APPLICATION NO. FILING DATE FIRST NAMED INVENTOR ATTORNEY DOCKET NO. CONFIRMATION NO. 13/505,007 07/17/2012 Alexei Soupikov ITL.2118US (P30289US) 5594 47795 7590 10/26/2017 TROP, PRUNER & HU, P.C. 1616 S. VOSS RD., SUITE 750 HOUSTON, TX 77057-2631 EXAMINER NGUYEN, PHONG X ART UNIT PAPER NUMBER 2618 NOTIFICATION DATE DELIVERY MODE 10/26/2017 ELECTRONIC Please find below and/or attached an Office communication concerning this application or proceeding. The time period for reply, if any, is set in the attached communication. Notice of the Office communication was sent electronically on above-indicated "Notification Date" to the following e-mail address(es): tphpto@tphm.com Inteldocs_docketing @ cpaglobal.com PTOL-90A (Rev. 04/07) UNITED STATES PATENT AND TRADEMARK OFFICE BEFORE THE PATENT TRIAL AND APPEAL BOARD Ex parte ALEXEI SOUPIKOV, MAXIM Y. SHEVTSOV, and ALEXANDER V. RESHETOV Appeal 2017-005729 Application 13/505,007 Technology Center 2600 Before TERRENCE W. McMILLIN, KARA L. SZPONDOWSKI, and SCOTT B. HOWARD, Administrative Patent Judges. SZPONDOWSKI, Administrative Patent Judge. DECISION ON APPEAL This is a decision on appeal under 35 U.S.C § 134(a) of the Final Rejection of claims 1—4, 6—11, 13—17, and 19—30, all claims currently pending in the application. We have jurisdiction under 35 U.S.C. § 6(b). We AFFIRM. Appeal 2017-005729 Application 13/505,007 STATEMENT OF THE CASE Appellants’ invention is directed to rendering primitives during graphics processing using acceleration structures. Spec. Tflf 1,4. Claim 1, reproduced below with the disputed limitations in italics, is representative of the claimed subject matter: 1. A method comprising: building, in a hardware processor, a hierarchical acceleration structure for graphics processing using a bit format of a first size; and in a hardware processor, allocating a memory region of the hierarchical acceleration structure, determining if the memory region is full, and if the memory region is full, allocating a new continuous region, using offsets of a first size for references to a child node in the memory region, using offsets of a second size to references to child nodes outside the memory region, wherein said first size is smaller than said second size. REJECTIONS Claims 1—4, 6—9, 13, 15—17, 19—22, and 24 stand rejected under 35 U.S.C. § 103(a) as being unpatentable over Leonenko (US 2009/0157997 Al; published June 18, 2009), Vingralek et al. (US 2008/0244210 Al; published Oct. 2, 2008) (“Vingralek”), and Ernst et al. (US 2011/0080403 Al; published Apr. 7, 2011) (“Ernst”). Final Act. 3. Claims 10, 11, 14, and 23 stand rejected under 35 U.S.C. § 103(a) as being unpatentable over Leonenko, Vingralek, Ernst, and Shahidzadeh et al. (US 6,349,380 Bl; published Feb. 19, 2002) (“Shahidzadeh”). Final Act. 7. Claims 25, 26, 28, and 29 stand rejected under 35 U.S.C. § 103(a) as being unpatentable over Leonenko, Popov et al. (Stefan Popov et al., Stackless KD-Tree Traversal for High Performance GPU Ray Tracing, 26 Eurographics 415—24 (2007)) (“Popov”), Vingralek, and Ernst. Final Act. 10. 2 Appeal 2017-005729 Application 13/505,007 Claims 27 and 30 stand rejected under 35 U.S.C. § 103(a) as being unpatentable over Leonenko, Popov, Vingralek, Ernst, and Shahidzadeh. Final Act. 13. ANALYSIS Issue 1: Did the Examiner err in finding that the combination of Leonenko, Vingralek, and Ernst teaches or suggests “allocating a memory region of the hierarchical acceleration structure, determining if the memory region is full, and if the memory region is full, allocating a new continuous region,” as recited in claim 1 and commensurately recited in independent claims 13 and 25? The Examiner finds Vingralek teaches determining if the memory region is full and then allocating a new continuous region. Final Act. 4 (citing Vingralek Figs. 1A—1C, Tflf 39-43); see also Ans. 15. Appellants argue Vingralek’s memory has gaps and is never full, resulting in no new region ever being allocated. Br. 6. We are not persuaded of Examiner error by Appellants’ argument. Initially, we note “if the memory region is fulF is not explicitly defined in Appellants’ Specification. Appellants argue, without providing support from the Specification, that a region that is full cannot have gaps in it. Br. 6. However, the ordinary meaning of “full” is “containing as much or as many as is possible or normal.” Full, Merriam-Webster.com, https://www.merriam-webster.com/dictionary/full (last visited Oct. 16, 2017). This definition of “full” is consistent with the definition applied by the Examiner, that memory is “full” despite the existence of gaps because the “gaps cannot be used for storing data.” Ans. 15. As cited by the 3 Appeal 2017-005729 Application 13/505,007 Examiner (Ans. 15), Vingralek teaches “even if a data chunk does not occupy an entire allocation unit, the unused portion of the allocation unit, by its nature, is not available for storing other data.” Vingralek 139. These unusable gaps are shown in Figure 1 A, and as a result, when a request is received to store an additional data chunk 125d, “there are not sufficient free allocation units to store the additional data chunk 125d.” Vingralek 140. In other words, Vingralek’s allocated memory, as occupied by data chunks with unusable gaps, contains as much data as is possible in usable memory. Therefore, we agree with the Examiner’s findings that the claimed “if the memory region is full,” encompassing the memory region containing as much data as is possible, is taught by Vingralek’s memory region, when allocated for data with unusable gaps, which is “practically full despite the existence of these gaps because . . . these gaps cannot be used for storing data.” Ans. 15. Appellants further argue Vingralek’s defragmentation and use of unusable areas does not allocate a new continuous region and rather reorganizes data within an existing region. Br. 6. Appellants’ argument is not persuasive. Appellants’ Specification describes “a continuous region is allocated” and requesting “a new region from a memory allocation system.” Spec. 124. Appellants’ Specification provides an example of new or continuous region allocation, describing “when the sub-tree outgrew the region k, a continuous region k+1 was allocated.” Spec. 125. In other words, allocating a new continuous region includes allocating a continuous region k+1 when region k is full. We agree with the Examiner’s findings that Vingralek’s “memory region 125d containing allocation units 1201-n (see Fig. 1C) is created only after the 4 Appeal 2017-005729 Application 13/505,007 memory regions 125a-125c have been reallocated” and “from the perspective of an executing program using the memory, it can be said that a new continuous region (region 125d) has been allocated.” Ans. 15. As cited by the Examiner (Final Act. 4), Vingralek teaches that data chunks 125a, 125b, and 125c are stored across allocation units 120a-n, when a request is received to store data chunk 125d for which there are not sufficient free allocation units among 120a-n to store the additional chunk. Vingralek Fig. la, 39-40. In order to store additional data chunk 125d, the data chunks are relocated and allocation units are reallocated. Vingralek Fig. lb, H 41— 42. The result is that allocation units 1201-n are made newly available for data chunk 125d, and data chunk 125d is newly stored in the allocation units in addition to data chunks 125a, 125b, and 125c. In other words, Vingralek provides for allocating allocation units 1201-n (i.e., 1201, 120m, 120n, or 1201, 1201+1, 1201+2) to data chunk 125d, when allocation units 120a-m are reallocated and allocation units 120a-k (i.e., 120k, or 1201-1) are full (i.e., allocation unit 1201-1 is full and newly allocating 1201, 1201+1, and 1201+2). Appellants fail to persuasively argue how Vingralek’s reorganization of data (relocating data chunks 125a-c and reallocating their corresponding allocation units 120) does not teach allocating a new continuous region (newly locating data chunk 125d to allocation units 1201-n newly allocated for data chunk 125d). Issue 2\ Did the Examiner err in finding that the combination of Feonenko, Vingralek, and Ernst teaches or suggests “using offsets of a first size for references to a child node in the memory region, using offsets of a second size to references to child nodes outside the memory region, wherein 5 Appeal 2017-005729 Application 13/505,007 said first size is smaller than said second size,” as recited in claim 1 and commensurately recited in independent claims 13 and 25? The Examiner finds Ernst teaches using offsets of different sizes to reference child nodes. Final Act. 5 (citing Ernst | 51). Appellants argue Vingralek “does not need offsets because he reallocates the data and then assigns new addresses to the newly stored data.” Br. 7 (citing Vingralek 142). Appellants’ argument is directed against the combination of Vingralek and Ernst. However, Appellants have not addressed the Examiner’s findings that: Leonenko teaches a kd-tree as a hierarchical acceleration structure and allocation a memory region of it (Final Act. 4 (citing Leonenko Fig. 5, 14, 16, 21, 26, 17)); Vingralek teaches memory allocation as claimed (Final Act. 4 (citing Vingralek Figs. 1A—1C, 39-43)); and Ernst teaches using offsets of varied sizes to reference child nodes (Final Act. 5 (citing Ernst 151)). The Examiner has provided articulated reasoning of how the claimed features are met by the proposed combination of the reference teachings with some rational underpinning, specifically that it would be obvious to combine Vingralek with Leonenko “to reduce the amount of fragmentation on a computer memory device” (Final Act. 5 (citing Vingralek, Abstract)) and to combine Ernst with Leonenko “to provide a compact data structure” (Final Act. 5 (citing Ernst, Abstract)). See KSR Int’l Co. v. Teleflex Inc., 550 U.S. 398 (2007). Appellants fail to persuasively address or rebut the Examiner’s specific findings and, thus, we are not persuaded of error by Appellants’ mere allegation that Vingralek does not need offsets. Accordingly, for the foregoing reasons, we sustain the Examiner’s 35 U.S.C. § 103(a) rejections of independent claims 1,13, and 25, and for the 6 Appeal 2017-005729 Application 13/505,007 same reasons sustain the Examiner’s 35 U.S.C. § 103(a) rejections of dependent claims 2-4, 6—11, 14—17, 19—24, and 26—30, which were not argued separately (Br. 8). DECISION The Examiner’s decision to reject claims 1—4, 6—11, 13—17, and 19— 30 under 35 U.S.C. § 103(a) is affirmed. No time period for taking any subsequent action in connection with this appeal may be extended under 37 C.F.R. § 1.136(a)(l)(iv). AFFIRMED 7 Copy with citationCopy as parenthetical citation