Ex Parte Soupikov et al

Patent Trial and Appeal Board

Oct 24, 2017

13505007 (P.T.A.B. Oct. 24, 2017)

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