Ex Parte Fowler et al

Patent Trial and Appeal Board

Sep 25, 2017

12391384 (P.T.A.B. Sep. 25, 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.
12/391,384 02/24/2009 David Keith Fowler ROC920070428US1 6915
139407 7590 09/27/2017
MiHHIetnn Rentlinaer fTRA/H
EXAMINER
401 S. 4th Street, Suite 2600
Louisville, KY 40202
WILLIS, AMANDA LYNN
ART UNIT PAPER NUMBER
2158
NOTIFICATION DATE DELIVERY MODE
09/27/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):
u sptomail @ middle tonlaw. com
PTOL-90A (Rev. 04/07)
UNITED STATES PATENT AND TRADEMARK OFFICE
BEFORE THE PATENT TRIAL AND APPEAL BOARD
Ex parte DAVID KEITH FOWLER, ERIC OLIVER MEJDRICH,
PAUL EMERY SCHARDT, and ROBERT ALLEN SHEARER1’2
Appeal 2017-004599
Application 12/391,384
Technology Center 2100
Before DENISE M. POTHIER, MATTHEW J. McNEILL, and
ALEX S. YAP, Administrative Patent Judges.
POTHIER, Administrative Patent Judge.
DECISION ON APPEAL
1 Throughout this opinion, we refer to (1) the Final Action (Final Act.)
mailed April 12, 2016, (2) the Appeal Brief (App. Br.) filed September 12,
2016, (3) the Examiner’s Answer (Ans.) mailed November 25, 2016, and (4)
the Reply Brief (Reply Br.) filed January 25, 2017.
2 The real party of interest is listed as International Business Machines
Corporation. App. Br. 1.
Appeal 2017-004599
Application 12/391,384
STATEMENT OF THE CASE
Appellants appeal under 35 U.S.C. § 134(a) from the Examiner’s
rejection of claims 1, 2, 4—14, and 16—25. Claims 3 and 15 have been
canceled. App. Br. A-2, A-5 (Claims App’x). We have jurisdiction under
35 U.S.C. § 6(b). We reverse.
Invention
Appellants’ invention relates to a
A circuit arrangement, program product and method []for
resetting a dynamically grown Accelerated Data Structure
(ADS) used in image processing in which an ADS is initialized
by reusing the root node of a prior ADS and resetting at least
one node in the prior ADS to break a link between the reset
node and a linked-to node in the prior ADS.
Spec., Abstract.
Claim 1 is reproduced below:
1. A method of building accelerated data structures for use
in image processing, the method comprising:
generating a first accelerated data structure for a first
image frame in connection with physical rendering of the first
image frame by dynamically adding a plurality of primitives
from a three dimensional scene to the first accelerated data
structure, wherein the first accelerated data structure is accessed
during physical rendering of the first image frame to determine
primitive intersections in the three dimensional scene, the first
accelerated data structure including a plurality of linked nodes
for which memory is allocated in a working memory, the
plurality of linked nodes including a root node that is a top level
node for the first accelerated data structure representing an
entire volume of the three dimensional scene; and
generating a second accelerated data structure for a
second image frame in connection with physical rendering of
the second image frame, wherein the second image frame is the
next image frame rendered after the first image frame is
rendered, wherein the second accelerated data structure is
2
Appeal 2017-004599
Application 12/391,384
accessed during physical rendering of the second image frame
to determine primitive intersections in the three dimensional
scene, and wherein generating the second accelerated data
structure includes:
initializing the second accelerated data structure by
reusing the root node for the first accelerated data structure as a
root node for the second accelerated data structure and resetting
at least one node in the first accelerated data structure to break a
link between the reset node and a linked-to node among the
plurality of nodes, wherein resetting the reset node breaks links
to multiple child nodes of the reset node, and wherein the reset
node is the root node; and
dynamically adding to the second accelerated data
structure for the second image frame the same plurality of
primitives from the three dimensional scene added to the first
accelerated data structure for the first image frame, including
dynamically expanding the reset node by reestablishing the link
between the reset node and the linked-to node and clearing
primitive data from the first accelerated data structure that is
stored in the linked-to node.
The Examiner relies on the following as evidence of unpatentability:
Shearer US 2008/0024489 A1 Jan. 31, 2008
Fowler US 2008/0192051 A1 Aug. 14,2008
S. Kumar et al., A Network on Chip Architecture and Design Methodology,
Proc. IEEE Comput. Soc’y Ann. Symp. on VLSI, Abstract (2002).
Claims 1, 2, 4—10, 12—14, and 16—25 are rejected under 35 U.S.C.
§ 103(a) as unpatentable over Fowler and Shearer. Final Act. 3—19.
Claim 11 is rejected under 35 U.S.C. § 103(a) as unpatentable over
Fowler, Shearer, and Kumar. Final Act. 19—20.
3
Appeal 2017-004599
Application 12/391,384
OBVIOUSNESS REJECTION OVER FOWLER AND SHEARER
Regarding independent claim 1, the Examiner finds Fowler teaches
many of its limitations, including “generating a first accelerated data
structure for a first image frame” as recited. Final Act. 4—5 (citing Fowler
77—79, 95, 118, 122, Fig. 5C). Regarding “generating a second
accelerated data structure for a second image frame . . . wherein the second
image frame is the next image frame rendered after the first image frame is
rendered,” the Examiner relies on both Fowler and Shearer. Final Act. 3—6
(citing Fowler 1193, 122, 125, 127—128, 130, 138, 135, 142, 148; Shearer
1125, 67, 68, 70, 73,74).
Among other arguments, Appellants assert Fowler does not teach,
“within the generation of the same ADS for a single image frame, both reset
a root node to break a link to another node, and then also dynamically add
back a plurality of primitives and reestablish the broken link.” App. Br. 11;
see also id. at 10-12. Appellants even further contend Shearer does not cure
Fowler’s deficiencies. App. Br. 12—14.
ISSUE
Under § 103, has the Examiner erred in rejecting claim 1 by finding
Fowler and Shearer collectively would have taught or suggested generating a
second ADS for a second image frame including:
(1) initializing the second ADS by “resetting at least one node in the
first accelerated data structure to break a link between the reset node and a
linked-to node among the plurality of nodes . . . wherein the reset node is the
root node” and
4
Appeal 2017-004599
Application 12/391,384
(2) dynamically adding to the second ADS “the same plurality of
primitives from the three dimensional scene added to the first” ADS,
“including dynamically expanding the reset node by reestablishing the link
between the reset node and the linked-to node”?
ANALYSIS
Based on the record before us, we find error in the Examiner’s
rejection. The Examiner determines Fowler’s Paragraph 142 teaches
initializing the second ADS by reusing the root node for the first ADS as a
root node of the second ADS and by “resetting at least one node in the first
accelerated data structure to break a link between the first reset node and a
linked-to node among the plurality of nodes.” Final Act. 6 (citing Fowler
1142). In particular, the rejection states Fowler’s Paragraph 142 teaches
“clearing the portion of the ADS” and “clearing all nodes branched from the
internal node.” Id.
Fowler teaches a process of updating an ADS in response to object
movement. Fowler || 122—145, Figs. 10—12. For example, Fowler teaches
in Figure 10 three-dimensional scene 1000 partitioned into planes, some of
which contain primitives. Id. 1123, Fig. 10. The bounding volumes created
by the plane correspond to various nodes as shown in ADS 1005. Id. For
example, ADS 1005 has empty leaf node 1010 which corresponds to empty
bounding volume 1015. Id. 1124, Fig. 10.
Over time, Fowler teaches an object may move into bounding volume
corresponding to an empty leaf node. Id. Tflf 125, 132, Fig. 12 (step 1205).
Such an example is shown in Fowler’s Figure 11, where block object 1100
has moved into previously-empty bounding volume 1015. Id. ^fl[ 126, 132,
5
Appeal 2017-004599
Application 12/391,384
Fig. 11. When this occurs, Fowler teaches ADS 1005 may be updated. Id.
Updating in this scenario involves adding nodes to ADS 1005 branching
beneath previously-empty leaf node 1010 or expanding the empty node. Id.
129, 135. Although this ADS updating may involve reusing and resetting
a root node of a first ADS and establishing a link between a reset node and a
linked-to node3, there is no discussion of breaking links to multiple child
nodes during this process as required by claim 1. See id. H 125—126, 129,
135, Figs. 11-12.
Fowler also teaches updating ADS 1005 when an object moves out of
a previously-empty bounding volume (e.g., “YES” at step 1230). Id. H 130,
140-142, Fig. 12. Updating in this scenario involves searching for a node
(e.g., 1010) associated with an ADS (e.g., 1005) containing an asserted
previously-empty leaf-node bit (step 1235) and, if located, clearing part of
ADS 1005 (step 1240) which was added when an object (e.g., 1100) moved
into an empty volume (e.g., at steps 1205, 1210). Id. 141—142, Fig. 12.
For example, all nodes branched from previously-empty leaf node 1010 are
cleared and previously empty leaf node 1010 is converted from an internal
node back to an empty leaf node. Fowler 1142, Fig. 12. In this scenario,
Fowler teaches reusing and resetting an ADS’s root node and resetting may
involve breaking a link of a child node by converting the internal node
having branched nodes back to an empty leaf node. Id. However, there is
no discussion of re-establishing the link between the reset node and the
linked-to node as also required by claim 1.
3 The disclosure states “[a] linked-to node ... is a node that is the target of a
link in a parent node in an ADS.” Spec. 145.
6
Appeal 2017-004599
Application 12/391,384
From the above discussion, Fowler teaches these ADS updating
techniques occur when an object moves into a previously-empty bounding
volume (e.g., Fig. 11) or, alternatively, moves out of a previously-empty
bounding volume. Id. 125—142, Figs. 10—12. Collectively, these
scenarios both break a link to a reset node and a linked-to node and re­
establish the link. Id. Yet, these updating scenarios occur in different
frames. Id. That is, the ADS updating occurring in steps 1205 and 1210 is
for one image frame and happens when an object moves into a previously-
empty bounding volume. Id. 125—126, 129, 135, Figs. 11—12. On the
other hand, the ADS updating that occurs in steps 1230, 1235, and 1240 is
for another image frame and happens when an object moves out of a
bounding volume defined by a previously-empty leaf node. Id. 130, 140—
142, Fig. 12.
In contrast, claim 1 requires both to break a link between a reset node
and a linked-to node and to re-establish the link when generating a second
ADS for a second image frame. App. Br. A-l (Claims App’x). Thus, as
indicated by Appellants, the Examiner’s reliance (Final Act. 6—7 (citing
Fowler || 135, 142)) on both of these occurrences to teach and suggest
generating a second ADS for the same frame is misplaced. See App. Br. 10,
12. The Examiner provides no further explanation of how these two
embodiments in Fowler could be combined such that both steps are
performed when generating an ADS for the same image frame. See
generally Ans.
Notably, although not possible in all situations, Fowler teaches
updating may involve constructing an entirely new ADS based on all objects
in a three-dimensional scene. Fowler || 128, 130. When constructed anew,
7
Appeal 2017-004599
Application 12/391,384
Fowler suggests re-establishing links between nodes. See id. However, in
this scenario, Fowler does not address whether the root node is reused and
reset to break links as claimed or rather new nodes are generated with newly
established links. See id. In any event, the rejection as proposed does not
rely on or discuss Fowler’s teaching of constructing an entirely new ADS to
suggest the recited breaking of links to multiple child nodes and the recited
re-establishing the link between the reset node and the linked-to node in
claim 1. See Final Act. 6—7 (discussing Fowler H 135, 142).
The Examiner further relies on Shearer to teach this step and more
specifically, to teach reusing stored information and re-establishing the link
between a reset node and a linked-to node. Final Act. 4, 6—7 (citing Shearer
1125, 67—68, 70, 73—74); Ans. 3—5 (citing Shearer 125). As the Examiner
indicates, Shearer teaches known concepts, such as generating nodes being
time consuming and saving node building time by reusing stored
information. See Ans. 3—5. Although we do not disagree with the
Examiner’s determination, these teachings do not demonstrate sufficiently
that combining these known techniques of reusing information and re­
establishing links with Fowler would have predictably yielded generating an
ADS for a single image frame (e.g., the recited second image frame) as
recited.
Shearer teaches recording, storing, and updating node history data
(e.g., ray-intersection test history and kd-tree traversal). Shearer H 66—68,
73—74, Figs. 5, 7. Shearer discusses updating node history bits to reflect
path/branch selected by the image processing system (see id. H 68, 73—74)
and clearing node history bits at a level that a leaf node resides and below
(see id. 170). This clearing, when combined with Fowler, may suggest
8
Appeal 2017-004599
Application 12/391,384
breaking a link between a root node and a linked-to node, but does not
discuss re-establishing this broken link. Id. 68, 70, 73—74. Shearer
further discusses re-traversing an index at a later time. Id. 125. Even
assuming this suggests re-establishing a link, this re-traversal occurs at a
later time, which would suggest that re-establishing of a link would be for a
different frame. As such, Shearer, when combined with Fowler as proposed,
does not establish sufficiently that its updating process would have involved
a single image frame. Shearer thus does not cure the above-noted
deficiencies in Fowler.
For the foregoing reasons, Appellants have persuaded us of error in
the rejection of (1) independent claim 1, (2) independent claims 13, 24,4 and
25, which recite commensurate limitations, and (3) dependent claims 2,
4—10, 12, 14, and 16—23 for similar reasons.
THE REMAINING OBVIOUSNESS REJECTION
Claim 11 indirectly depends from claim 1 and is rejected as
unpatentable over Fowler, Shearer, and Kumar under 35 U.S.C. § 103(a).
Final Act. 19—20. Appellants refer to “the same reasons as claim 1” in
arguing for reversal and contend Kumar is not relied upon to teach claim 1 ’s
limitations. App. Br. 17. We are persuaded and refer above for more
details. Accordingly, we do no sustain the rejection of claim 11.
4 Although written in dependent form, claim 24 is effectively an independent
claim. App. Br. A-6 (Claims App’x) (claiming “[a]n integrated circuit
device including the circuit arrangement of claim 13”).
9
Appeal 2017-004599
Application 12/391,384
DECISION
We reverse the Examiner’s rejections of claims 1, 2, 4—14, and 16—25
under § 103.
REVERSED
10