Apparatus and method for determining a rendering order between first and second object surface primitives
First Claim
1. In a graphics apparatus having a processor for processing signals defining objects in a three-dimensional space, each object being comprised of a plurality of surface primitives, a method of processing the signals which includes determining a rendering order between a first said primitive and a second said primitive so as to effect hidden surface removal, the method comprising the steps of:
- processing the signals to perform a first test to obtain one of a positive result indicating that the first primitive can be rendered before the second primitive and a negative result indicating that it may not be possible to render the first primitive before the second primitive;
in the case of a negative result in the first test, identifying a part of at least one of the first primitive and the second primitive that has caused the negative result in the first test;
processing the signals to perform a second test with reference to the identified part to obtain one of (1) a positive result indicating that the first primitive in its entirety can be rendered before the second primitive, in spite of the negative result obtained in the first test, and (2) a negative result indicating again that it may not be possible to render the first primitive before the second primitive; and
rendering the surface primitives in accordance with the rendering order to display an image of said objects.
0 Assignments
0 Petitions
Accused Products
Abstract
Polygons defined in three-dimensional space are processed in order to facilitate subsequent manipulation. A first polygon is tested against a second polygon to identify a part of one of the polygons which may have a particular relationship. Thereafter, a second test is performed with reference to that polygon part. When producing rendering order lists, trees or directed graphs, a current favorite polygon (for placing on a list, tree or graph) is tested against a candidate polygon to determine whether the candidate polygon may be occluded by the favorite polygon. In performing this test a fragment of the favorite polygon may be identified which may occlude the candidate polygon and a fragment of the candidate polygon may be identified, as that which may be occluded by the current favorite. Thereafter, a second test is performed with reference to the fragment of the favorite polygon and the fragment of the candidate polygon.
-
Citations
49 Claims
-
1. In a graphics apparatus having a processor for processing signals defining objects in a three-dimensional space, each object being comprised of a plurality of surface primitives, a method of processing the signals which includes determining a rendering order between a first said primitive and a second said primitive so as to effect hidden surface removal, the method comprising the steps of:
-
processing the signals to perform a first test to obtain one of a positive result indicating that the first primitive can be rendered before the second primitive and a negative result indicating that it may not be possible to render the first primitive before the second primitive; in the case of a negative result in the first test, identifying a part of at least one of the first primitive and the second primitive that has caused the negative result in the first test; processing the signals to perform a second test with reference to the identified part to obtain one of (1) a positive result indicating that the first primitive in its entirety can be rendered before the second primitive, in spite of the negative result obtained in the first test, and (2) a negative result indicating again that it may not be possible to render the first primitive before the second primitive; and rendering the surface primitives in accordance with the rendering order to display an image of said objects. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. Apparatus for processing signals defining objects in a three-dimensional space, each object being comprised of a plurality of surface primitives, in order, inter alia, to determine a rendering order between a first said primitive and a second said primitive so as to effect hidden surface removal and to display an image of said objects, comprising:
-
means for processing the signals to perform a first test to obtain one of (1) a positive result indicating that the first primitive can be rendered before the second primitive, and (2) a negative result indicating that it may not be possible to render the first primitive before the second primitive; means for identifying, in case of a negative result in the first test, a part of at least one of the first primitive and the second primitive that has caused the negative result in the first test; means for processing the signals to perform a second test with reference to the identified part to obtain one of (1) a positive result indicating that the first primitive in its entirety can be rendered before the second primitive, in spite of the negative result obtained in the first test, and (2) a negative result indicating again that it may not be possible to render the first primitive before the second primitive; and means for rendering the surface primitives in accordance with the rendering order, so as to display an image of said objects. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. In an interactive graphic system in which objects are defined in a three-dimensional space, and each object is comprised of a plurality of surface primitives, a method including rendering said objects to produce a plurality of two-dimensional images, including the steps of:
-
identifying, for each image, a value for at least one viewing parameter as a selected value; selecting, in dependence upon the selected value, a rendering order list, tree or directed graph for each respective image from among a plurality of rendering order lists, trees or directed graphs defined prior to rendering the images, each being associated with a respective range of values for the viewing parameter; and rendering the objects for each image in accordance with the selected rendering order list, tree or directed graph to display an image of the objects, wherein at least one selected rendering order list, tree or directed graph has been produced by (i) performing a first test with reference to a notional value of a viewing parameter to obtain one of (a) a positive result indicating that a first said primitive cannot occlude a second said primitive and that the first primitive can therefore be rendered before the second primitive, and (b) a negative result indicating that at least part of the first primitive may occlude at least part of the second primitive or that at least part of the second primitive may be occluded by at least part of the first primitive, and that it may not therefore be possible to render the first primitive before the second primitive, (ii) in case of a positive result in the first test, adding the first primitive to the rendering order list, tree or directed graph, (iii) in case of a negative result in the first test, identifying a part of at least one of the first primitive and the second primitive that has caused the negative result, and processing the signals to perform a second test with reference to the identified part to obtain one of (a) a positive result indicating that the first primitive in its entirety can be rendered before the second primitive in spite of the negative result obtained by the first test, and (b) a negative result indicating again that it may not be possible to render the first primitive before the second primitive, and (iv) adding the first primitive in its entirety to the rendering order list, tree or directed graph in the case of a positive result in the second test. - View Dependent Claims (29, 30)
-
-
31. A computer-useable medium having computer-readable instructions stored therein for causing a programmable processing apparatus to process signals defining objects comprised of a plurality of surface primitives in a three-dimensional space including determining a rendering order between a first said primitive and a second said primitive so as to effect hidden surface removal, the instructions comprising instructions for:
-
causing the apparatus to process the signals to perform a first test to obtain one of a positive result indicating that the first primitive can be rendered before the second primitive and a negative result indicating that it may not be possible to render the first primitive before the second primitive; in the case of a negative result in the first test, causing the apparatus to identify a part of at least one of the first primitive and the second primitive that has caused the negative result in the first test; and causing the apparatus to process the signals to perform a second test with reference to the identified part to obtain one of (i) a positive result indicating that the first primitive in its entirety can be rendered before the second primitive, in spite of the negative result obtained in the first test, and (ii) a negative result indicating again that it may not be possible to render the first primitive before the second primitive. - View Dependent Claims (32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45)
-
-
46. A computer-useable medium storing computer-useable instructions for causing a processor in an interactive graphics system to render a plurality of two-dimensional images of objects in a three-dimensional space, each object being comprised of a plurality of surface primitives, the instructions comprising instructions for:
-
causing the processor to allow a user to identify, for each image, a value for at least one viewing parameter in accordance with which the image is to be rendered as a selected value; causing the processor to select, in dependence upon the selected value, a rendering order list, tree or directed graph for each respective image from among a plurality of rendering order lists, trees or directed graphs defined prior to rendering the images, each being associated with a respective range of values for the viewing parameter; and causing the processor to render the objects for each image in accordance with the selected rendering order list, tree or directed graph to display an image of the objects, wherein at least one selected rendering order list, tree or directed graph has been produced by (i) performing a first test with reference to a notional value of a viewing parameter to obtain one of (a) a positive result indicating that a first said primitive cannot occlude a second said primitive and that the first primitive can therefore be rendered before the second primitive and (b) a negative result indicating that at least part of the first primitive may occlude at least part of the second primitive or that at least part of the second primitive may be occluded by at least part of the first primitive, and that it may not therefore be possible to render the first primitive before the second primitive, (ii) in the case of a positive result in the first test, adding the first primitive to the rendering order list, tree or directed graph, (iii) in the case of a negative result in the first test, identifying a part of at least one of the first primitive and the second primitive that has caused the negative result, and processing the signals to perform a second test with reference to the identified part to obtain one of (a) a positive result indicating that the first primitive in its entirety can be rendered before the second primitive in spite of the negative result obtained by the first test, and (b) a negative result indicating again that it may not be possible to render the first primitive before the second primitive, and (iv) adding the first primitive in its entirety to the rendering order list, tree or directed graph in the case of a positive result in the second test. - View Dependent Claims (47, 48, 49)
-
Specification