Information
Cette décision n'est disponible qu'en Anglais.
T 1546/17 31-03-2022
Téléchargement et informations complémentaires:
IMPROVEMENTS TO A TILING SYSTEM FOR 3D RENDERED GRAPHICS
Amendment after summons - exceptional circumstances (no)
Amendments - added subject-matter (no)
Claims - clarity after amendment (yes)
Remittal - (yes)
Summary of Facts and Submissions
I. The appeal is against the examining division's decision to refuse European patent application No. 04 720 053.0, published as international patent application WO 2004/086309 A2.
II. The following prior-art documents were cited in the decision under appeal:
D1: US 6,437,780 B1
D2: GB 2 343 603 A
III. The decision under appeal was based on the grounds that the independent claims of the then main request and then auxiliary requests 1 to 3 did not meet the requirements of Article 84 EPC and their subject-matter did not involve an inventive step within the meaning of Article 56 EPC.
IV. The applicant (appellant) filed notice of appeal. With the statement of grounds of appeal, the appellant filed claims according to auxiliary requests 1A, 4 and 5. The appellant maintained the main request and auxiliary requests 2 and 3 on which the decision under appeal was based. It indicated a basis in the application as filed for the claimed subject-matter and provided arguments as to why the claims met the requirements of Articles 56 and 84 EPC.
V. A summons to oral proceedings and a communication under Article 15(1) of the Rules of Procedure of the Boards of Appeal in the 2020 version (RPBA 2020; see OJ EPO 2019, A63) were issued. In that communication, the board expressed the following preliminary opinion.
(a) Claim 1 of the main request and of auxiliary requests 1A, 2 and 3 did not contain all the essential features and was thus not clear (Article 84 EPC 1973).
(b) These objections did not apply to claim 1 of auxiliary requests 4 and 5.
(c) The case might be remitted to the examining division for further examination of novelty and inventive step if the appellant were able to convince the board that the claims of one of the requests met the requirements of Article 84 EPC 1973.
VI. By letter of reply dated 25 February 2022, the appellant submitted amended auxiliary requests 4 and 5 and re-ordered the pending requests as follows:
- auxiliary requests 4 and 5
- main request and auxiliary requests 1A, 2, 3
The appellant requested "that we are permitted to amend auxiliary requests 4 and 5, as described below, conditional on the Board:
either
- granting the application on the basis of amended auxiliary request 4,
or
- remitting the application to the Examining Division on the basis of amended auxiliary requests 4 and 5.
If the board is minded not to remit the application based on amended auxiliary requests 4 and 5, then I request that the Board:
either
- grant the application on the basis of current auxiliary request 4,
or
- remit the application to the Examining Division on the basis of current auxiliary requests 4 and 5, as per its initial opinion" (see letter of reply, section "Summary" on page 2).
The appellant withdrew the request for oral proceedings on condition that the board granted the application or remitted it to the examining division on the basis of amended auxiliary requests 4 and 5 or current auxiliary requests 4 and 5.
The amended auxiliary request 4 was filed "to replace auxiliary request 4 as currently on file (conditional on the Board remitting the application to the Examining Division based on this amended auxiliary request 4)". The amended auxiliary request 5 was filed "to replace auxiliary request 5 as currently on file (conditional on the Board remitting the application to the Examining Division based on this amended auxiliary request 5)" (see letter of reply, section "Amendments to auxiliary requests 4 and 5" on page 2).
VII. The board then cancelled the oral proceedings.
VIII. The independent claims of auxiliary request 4 filed with the statement of grounds of appeal read as follows:
"1. A method for culling objects in a system for shading 3-dimensional computer graphics images comprising the steps of:
subdividing a display on which an image is to be viewed into a plurality of rectangular areas;
for each rectangular area deriving a list of objects in the image which may be visible in that rectangular area;
using the list of objects to determine how the rectangular area should be shaded for display;
wherein the step of deriving a list of objects comprises the steps of:
determining maximum and minimum values for X and Y co-ordinates of each object;
for each object in the image, determining a bounding box from the maximum and minimum values of the X and Y co-ordinates of the object; characterized in that the method comprises:
determining a set of pixel sampling locations using the maximum and minimum values;
determining (81) whether or not the bounding box surrounding the object covers any of the pixel sampling locations;
culling (82) the object if the bounding box misses all the pixel sampling locations; and, if the object is not culled:
testing (86) each pixel sampling location in the set against each edge of the object;
determining (87) from the test performed by the testing step whether or not the object covers any of the pixel sampling locations; and
adding (84) or rejecting (82) the object from the list in dependence on the result of the determination,
wherein determining a set of pixel sampling locations comprises determining:
a minimum pixel sampling location X coordinate, Sxmin, from the ceiling of the minimum X coordinate of the object;
a maximum pixel sampling location X coordinate, Sxmax, from the floor of the maximum X coordinate of the object;
a minimum pixel sampling location Y coordinate, Symin, from the ceiling of the minimum Y coordinate of the object; and
a maximum pixel sampling location Y coordinate, Symax, from the floor of the maximum Y coordinate of the object; and
wherein the method further comprises the step of determining whether or not the pixel sampling locations are spread by more than l x l pixel, and not testing the object for culling if the pixel sampling locations exceed this limit.
5. Apparatus for culling objects in a system for shading a three-dimensional computer graphics image comprising:
means for subdividing a display on which the image is to be viewed into a plurality of rectangular areas;
means for deriving for each rectangular area a list of objects in the image which may be visible in that rectangular area;
means for determining how the rectangular area should be shaded for display by using the list of objects;
wherein the means for deriving a list of objects comprises:
means for determining maximum and minimum values for X and Y co-ordinates of each object;
for each object in the image determining (81) a bounding box from the maximum and minimum values of the X and Y co-ordinates of the object; characterized by:
means for determining a set of pixel sampling locations using the maximum and minimum values;
means for determining (81) whether or not the bounding box surrounding the object covers any of the pixel sampling locations; and
means for culling (82) the object if the bounding box misses all the pixel sampling locations;
means for testing (86) each pixel sampling location in the set against each edge of the object, if the object is not culled;
means for determining (87) from the test performed by the means for testing whether or not the object covers any of the pixel sampling locations; and
means for adding (84) or rejecting (82) the object from the list in dependence on the result of the determination,
wherein the means for determining a set of pixel sampling locations comprises:
means for determining a minimum pixel sampling location X coordinate, Sxmin, from the ceiling of the minimum X coordinate of the object;
means for determining a maximum pixel sampling location X coordinate, Sxmax, from the floor of the maximum X coordinate of the object;
means for determining a minimum pixel sampling location Y coordinate, Symin, from the ceiling of the minimum Y coordinate of the object; and
means for determining a maximum pixel sampling location Y coordinate, Symax, from the floor of the maximum Y coordinate of the object; and
wherein the apparatus further comprises means for determining whether or not the pixel sampling locations are spread by more than l x l pixel in the X and Y directions; and not testing the object for culling if the pixel sampling locations exceed this limit."
IX. The examining division's arguments, in so far as they are relevant to the present decision, may be summarised as follows.
(a) The application only provided support for determining exactly four pixel sampling locations in the bounding box, as set out in the description, page 16, lines 5 to 14 (see decision under appeal, page 12, first full paragraph).
(b) If all possible sampling locations within a bounding box were tested, no gain in efficiency would be achieved, i.e. the test of whether an object can be culled would be computationally more complex than simply rendering invisible objects (see decision under appeal, point 2.1.2(b)).
(c) With an arbitrarily selected set of pixel sampling locations, visible objects, e.g. diamond-shaped objects, would be erroneously culled (see decision under appeal, point 2.1.2(c)).
X. The appellant argued that the amended auxiliary requests 4 and 5 should be admitted into the appeal proceedings for the following reasons.
(a) They were submitted in response to a point first raised by the board in its communication, namely that the board was minded to remit the application for further examination on the basis of auxiliary requests 4 and 5 filed with the statement of grounds of appeal.
(b) The amendments improved procedural efficiency because the examining division's subsequent examination could take these amendments into account straight away. The amendments had a basis in the application as filed and the amended claims were clear. Thus, the amended claims were prima facie admissible (see letter of reply, section "Comments in support of admitting the amended requests into the proceedings" on page 4).
XI. Furthermore, the appellant submitted that auxiliary requests 4 and 5 filed with the statement of grounds of appeal corresponded to claims that the examining division had indicated were allowable (see statement of grounds of appeal, page 1, third paragraph, and sections 5 and 6 on pages 20 to 21).
Reasons for the Decision
1. The appeal is admissible.
2. Interpretation of the appellant's requests
2.1 The appellant stated that it had filed amended auxiliary requests 4 and 5 on condition that the board remitted the application to the examining division on the basis of those requests (see point VI. above).
2.2 Taken literally, this would mean that these requests would not be filed if the specified condition (the board remitting the application to the examining division) were not fulfilled.
However, a request needs to be filed first before the board can examine it and possibly decide to remit the application on the basis of the claims in that request.
Since taking the appellant's statement literally would lead to a nonsensical result, an interpretation is required.
2.3 The appellant indicated the following order of preference (see point VI. above):
- a patent be granted on the basis of amended auxiliary request 4
- the application be remitted to the examining division on the basis of amended auxiliary requests 4 and 5
- a patent be granted on the basis of current auxiliary request 4
- the application be remitted to the examining division on the basis of the claims of current auxiliary requests 4 and 5
The most preferred option can only be achieved if amended auxiliary request 4 is filed unconditionally, i.e. not on condition that the board remits the application to the examining division on the basis of that request.
Therefore, the board interprets the appellant's statements as a whole as requesting that the decision under appeal be set aside and that (in the following order of preference):
(a) a patent be granted on the basis of amended auxiliary request 4 filed by letter of reply dated 25 February 2022
(b) the application be remitted to the examining division on the basis of amended auxiliary requests 4 and 5, both requests filed by letter of reply dated 25 February 2022
(c) a patent be granted on the basis of current auxiliary request 4 filed with the statement of grounds of appeal
(d) the application be remitted to the examining division on the basis of the claims of current auxiliary requests 4 and 5 filed with the statement of grounds of appeal
3. Admittance of amended auxiliary requests 4 and 5 (Article 13(2) RPBA 2020)
3.1 Amended auxiliary requests 4 and 5 were filed after the notification of the summons to oral proceedings. These auxiliary requests are therefore amendments within the meaning of Article 13(2) RPBA 2020.
3.2 Article 13(2) RPBA 2020 specifies that any amendment to a party's appeal case made after notification of a summons to oral proceedings is, in principle, not to be taken into account unless there are exceptional circumstances, which have been justified with cogent reasons by the party concerned.
According to the explanatory remarks on Article 13(2) RPBA 2020, paragraph 2 of Article 13 RPBA 2020 implements the third level of the convergent approach applicable in appeal proceedings. The basic principle of the third level of the convergent approach is that, at this stage of the appeal proceedings, amendments to a party's appeal case are not taken into consideration. However, a limited exception is provided for: it requires a party to present compelling reasons which justify clearly why the circumstances leading to the amendment are indeed exceptional in the particular appeal ("cogent reasons"). For example, if a party submits that the board raised an objection for the first time in a communication, it must explain precisely why this objection is new and does not fall under objections previously raised by the board or a party (see document CA/3/19, section VI, explanatory remarks on Article 13(2); see also Supplementary publication 2, OJ EPO 2020).
3.3 The appellant argued that it was appropriate to admit amended auxiliary requests 4 and 5 into the appeal proceedings for the following reasons (see point X. above).
(a) They were submitted in response to a point first raised by the board in its communication, namely that the board was minded to remit the application for further examination on the basis of auxiliary requests 4 and 5 filed with the statement of grounds of appeal.
(b) The amendments improved procedural efficiency because the examining division's subsequent examination could take these amendments into account straight away. The amendments had a basis in the application as filed and the amended claims were clear. Thus, the amended claims were prima facie admissible.
3.4 The board is not convinced by these arguments for the following reasons.
(a) The fact that the board stated that it may be minded to remit the case to the examining division is not a new objection. In fact, the board stated in its communication that the objections raised against the then higher-ranking requests did not apply to claim 1 of auxiliary requests 4 and 5 filed with the statement of grounds of appeal (see point V. above).
(b) The question of procedural economy and whether or not an amendment gives rise to new objections are criteria to be considered by a board when exercising its discretion under Article 13(1) RPBA 2020, which implements the second level of the convergent approach. Fulfilling these criteria is not sufficient to meet the requirements of the third level of the convergent approach as implemented by Article 13(2) RPBA 2020.
3.5 Therefore, the board does not admit the amended auxiliary requests 4 and 5 into the appeal proceedings.
4. Auxiliary request 4 filed with the statement of grounds of appeal - amendments (Article 123(2) EPC)
4.1 Claim 1 according to auxiliary request 4 filed with the statement of grounds of appeal is based on claims 1 and 4 as originally filed.
Furthermore, the feature of claim 1 "determining maximum and minimum values for X and Y coordinates of each object" is based on the description as originally filed, page 7, lines 5 to 16.
The feature of claim 1 "determining (81) whether or not the bounding box surrounding the object covers any of the pixel sampling locations; culling (82) the object if the bounding box misses all the pixel sampling locations" is based on Figure 10: 81, 82 and the description as originally filed, page 16, second full paragraph.
The features of claim 1 "wherein determining a set of pixel sampling locations comprises determining: a minimum pixel sampling location X coordinate ... a maximum pixel sampling location Y coordinate, Symax, from the floor of the maximum Y coordinate of the object" are based on the description as originally filed, page 16, first full paragraph.
The final feature of claim 1 "wherein the method further comprises the step of determining whether or not the pixel sampling locations are spread by more than 1x1 pixel and not testing the object for culling if the pixel sampling locations exceed this limit" is based on Figure 10: 83 -> Yes -> 84 and the paragraph bridging pages 16 and 17 of the description as originally filed.
4.2 Independent apparatus claim 5 according to auxiliary request 4 filed with the statement of grounds of appeal is based on claims 10 and 13 as originally filed. Amendments based on the description as originally filed corresponding to those set out under point 4.1 above also apply.
4.3 The dependent claims according to auxiliary request 4 filed with the statement of grounds of appeal have the following basis:
- claims 2 and 7: see the description as originally filed, page 17, second full paragraph
- claims 3 and 8: see the description as originally filed, page 16, first full paragraph
- claims 4 and 9: see claims 5 and 14 as originally filed, respectively
4.4 In view of the above, the subject-matter of the claims of auxiliary request 4 filed with the statement of grounds of appeal does not extend beyond the content of the application as filed. Thus, the requirements of Article 123(2) EPC are met.
5. Auxiliary request 4 filed with the statement of grounds of appeal - clarity (Article 84 EPC 1973)
5.1 Under Article 84 EPC 1973, the claims "shall be clear".
According to established case law, Article 84 EPC 1973 has to be interpreted as meaning not only that a claim must be comprehensible from a technical point of view, but also that it must define the object of the invention clearly, that is to say indicate all the essential features thereof. All features which are necessary for solving the technical problem with which the application is concerned have to be regarded as essential features (see Case Law of the Boards of Appeal of the European Patent Office, 9th edition 2019, II.A.3.2).
5.2 It is common ground that the technical problem with which the application is concerned is how to cull an object if it will not be visible in an image and render the object if it will be visible in the image (see decision under appeal, point 2.1.1(a) and statement of grounds of appeal, page 8, first full paragraph).
5.3 Claim 1 specifies a method for culling objects comprising the following steps for carrying out a first check to verify whether objects can be culled:
(a) determining a set of pixel sampling locations using the maximum and minimum values
(b) determining (81) whether or not the bounding box surrounding the object covers any of the pixel sampling locations
(c) culling (82) the object if the bounding box misses all the pixel sampling locations
(d) wherein the means for determining a set of pixel sampling locations comprises:
means for determining a minimum pixel sampling location X coordinate, Sxmin, from the ceiling of the minimum X coordinate of the object;
means for determining a maximum pixel sampling location X coordinate, Sxmax, from the floor of the maximum X coordinate of the object;
means for determining a minimum pixel sampling location Y coordinate, Symin, from the ceiling of the minimum Y coordinate of the object; and
means for determining a maximum pixel sampling location Y coordinate, Symax, from the floor of the maximum Y coordinate of the object
5.4 Claim 1 thus specifies the minimum and maximum pixel sampling coordinates as a specific function of the minimum and maximum coordinates of the object, respectively.
Hence, it is not possible that the pixel sampling locations cover a different area from the object's bounding box, so objects would be culled regardless of whether or not they were visible.
5.5 Claim 1 specifies neither the number nor the exact location of the determined pixel sampling locations.
5.6 The examining division argued that the application only provided support for determining exactly four pixel sampling locations in the bounding box (see point IX(a) above).
The board is not convinced that this is a requirement in the application because the bounding boxes of the objects shown in Figures 7, 8 and 9 include zero, two and four sampling points, respectively.
5.7 The examining division argued that if all possible sampling locations within a bounding box were tested, no gain in efficiency would be achieved, i.e. the test of whether an object can be culled would be computationally more complex than simply rendering invisible objects (see point IX(b) above).
The board is not convinced by this argument because the test of whether an object can be culled involves mainly processing steps whereas rendering multiple objects also involves storage operations. Hence, a computationally complex culling test can also bring advantages.
Therefore, the board finds that the number of the determined pixel sampling locations is not essential.
5.8 The examining division argued that with an arbitrarily selected set of pixel sampling locations, visible objects, e.g. diamond-shaped objects, would be erroneously culled (see point IX(c) above).
For the board, this argument does not apply because claim 1 specifies that all the determined sampling points are within an object's bounding box and are thus not selected in an arbitrary manner. The specific location of a pixel sampling point within a bounding box does not affect whether or not the bounding box misses all the pixel sampling locations. In fact, a bounding box can only miss all the determined pixel sampling locations if its extent in either the X or Y direction is smaller than the corresponding spacing between the sampling points in the same direction.
Therefore, the board finds that the exact position of the pixel sampling locations is not essential.
5.9 Claim 1 specifies a method for culling objects comprising the following steps for carrying out a second check to verify whether objects that were not culled in the first check should be culled:
(a) testing (86) each pixel sampling location in the set against each edge of the object
(b) determining (87) from the test performed by the testing step whether or not the object covers any of the pixel sampling locations
(c) adding (84) or rejecting (82) the object from the list in dependence on the result of the determination
wherein this second check is only performed if the pixel sampling locations are not spread by more than 1 x 1 pixel.
5.10 One option covered by claim 1 is that there are four pixel sampling points at the corners of the bounding box.
Graphic objects can include a diamond-shaped object or a star-like object. In contrast to a triangle, these objects have a filled centre. Hence, while four pixel sampling points at the corners of the bounding box may all be outside the edges of an object, there can be a further pixel sampling point in the centre.
However, claim 1 of auxiliary request 4 specifies that the second check for culling is only performed if the sampling locations are not spread out by more than 1 x 1 pixel.
5.11 Thus, for objects with a further central sampling point - in addition to the four corner points - the second check is not applied and objects with a filled centre cannot be erroneously culled.
5.12 In view of the above, the board finds that claim 1 of auxiliary request 4 filed with the statement of ground of appeal specifies all the essential features and meets the requirements of Article 84 EPC 1973.
The same applies to the corresponding independent apparatus claim 5.
6. Remittal to the department of first instance (Article 11 RPBA 2020)
6.1 Auxiliary request 4 filed with the statement of grounds of appeal was not dealt with by the examining division in the decision under appeal.
6.2 In the decision under appeal, the examining division provided reasons as to why the subject-matter of the requests then on file lacked inventive step. According to these reasons, certain features were essential, i.e. without these features the specified algorithm would be non-functional and could thus not be inventive. As set out under point 5. above, these arguments do not apply to the subject-matter claimed in auxiliary request 4 filed with the statement of grounds of appeal. However, the decision under appeal contains no finding that with these features the claimed subject-matter would involve an inventive step.
6.3 The appellant submitted that auxiliary request 4 filed with the statement of grounds of appeal corresponded to claims that the examining division had indicated were allowable (see point XI above).
However, this submission is based on a cursory statement from the examining division without any reasoning as to why the claimed subject-matter involved an inventive step (see telephone minutes dated 24 November 2016, page 4, last paragraph of the section labelled "Re: Auxiliary Request 2").
6.4 Furthermore, the board does not consider itself to be in a position to provide a meaningful assessment of the novelty and inventive step of the claimed subject-matter for the following reasons.
The cited prior-art documents D1 and D2 deal with the problem of identifying which tiles are covered by a "large" graphic primitive, i.e. a graphic primitive covering multiple tiles (see D1, Figure 2D, and D2, Figure 6).
In contrast, the claims of auxiliary request 4 relate to the third embodiment of the application, which provides means for rejecting certain "small" primitives (see description, page 5, last paragraph of the section labelled "Summary of the Invention"). In particular, what is tested is whether a primitive is so small that its bounding box is in between all the sampling locations of a single tile (see Figure 7 of the application).
Hence, the board is not convinced that either document D1 or document D2 is an appropriate starting point for the assessment of inventive step.
6.5 In view of the above, the board finds that there are special reasons within the meaning of Article 11 RPBA 2020 to remit the case to the examining division for further examination of novelty and inventive step.
7. Conclusion
7.1 The board does not admit amended auxiliary requests 4 and 5 into the appeal proceedings (Article 13(2) RPBA 2020).
7.2 The set of claims according to auxiliary request 4 filed with the statement of grounds of appeal meets the requirements of Article 123(2) EPC and Article 84 EPC 1973. However, the board is not in a position to provide a meaningful assessment of the novelty and inventive step of the claimed subject-matter. The board thus remits the case to the examining division for further examination of novelty and inventive step.
7.3 Since the appellant withdrew its request for oral proceedings, on condition that the board remitted the application to the examining division on the basis of auxiliary request 4 filed with the statement of grounds of appeal (see point VI. above), the board is in a position to decide without holding oral proceedings.
Order
For these reasons it is decided that:
1. The decision under appeal is set aside.
2. The case is remitted to the examining division for further prosecution based on the claims of auxiliary request 4 filed with the statement of grounds of appeal.