Three dimensional graphics processing with pre-sorting of surface portions
First Claim
1. An apparatus for generating a sequence of two-dimensional images of a three-dimensional object, the two-dimensional images representing the object from respective desired viewing directions, the apparatus comprising:
- a surface portion store for storing surface portion data corresponding to a plurality of surface portions of the object;
a first sorter for sorting said surface portion data to generate a first ordered list of surface portions corresponding to an order in which the portions may be overwritingly displayed to effect hidden surface removal, by (i) determining which, if any, of the surface portions cannot occlude others from any viewing direction and which can, (ii) entering those which cannot occlude any others in said first ordered list so as to be drawn first, and thereafter (iii) entering further surface portions in said first ordered list in succession, such that each of said first ordered portions is entered in the first ordered list when the surface portions which it can occlude are surface portions already entered in the first ordered list;
a second sorter for sorting surface portions which have not been entered in said first ordered list into a plurality of second ordered lists, each second ordered list being generated with reference to a respective predetermined view direction;
a list selector for selecting, for each two-dimensional image to be generated, one of said plurality of second lists in dependence upon the desired viewing direction of that image; and
an image generator for generating each of said two-dimensional images representing the object by rendering each said portion from the first list and said selected second list in order of occurrence therein, in accordance with the desired viewing directions, portions which are backwards facing relative to the desired viewing direction not being rendered.
1 Assignment
0 Petitions
Accused Products
Abstract
To effect hidden surface removal, polygons making up a three dimensional object are initially ordered using a Topological Sort into, for example, three rendering order lists corresponding to orthogonal axis. When the object is to be represented from a given view direction, the view direction is compared to the axis and the rendering list corresponding to the closest match is selected. Polygons are then rendered in list order, backward facing polygons being omitted. Performing the ordering at the polygon level, in an initial step, saves computation and consequently enables the projection and rendering processes to be speeded up to provide real time interactive three dimensional graphics. The Topological Sorting process is particularly computationally effective.
49 Citations
18 Claims
-
1. An apparatus for generating a sequence of two-dimensional images of a three-dimensional object, the two-dimensional images representing the object from respective desired viewing directions, the apparatus comprising:
-
a surface portion store for storing surface portion data corresponding to a plurality of surface portions of the object; a first sorter for sorting said surface portion data to generate a first ordered list of surface portions corresponding to an order in which the portions may be overwritingly displayed to effect hidden surface removal, by (i) determining which, if any, of the surface portions cannot occlude others from any viewing direction and which can, (ii) entering those which cannot occlude any others in said first ordered list so as to be drawn first, and thereafter (iii) entering further surface portions in said first ordered list in succession, such that each of said first ordered portions is entered in the first ordered list when the surface portions which it can occlude are surface portions already entered in the first ordered list; a second sorter for sorting surface portions which have not been entered in said first ordered list into a plurality of second ordered lists, each second ordered list being generated with reference to a respective predetermined view direction; a list selector for selecting, for each two-dimensional image to be generated, one of said plurality of second lists in dependence upon the desired viewing direction of that image; and an image generator for generating each of said two-dimensional images representing the object by rendering each said portion from the first list and said selected second list in order of occurrence therein, in accordance with the desired viewing directions, portions which are backwards facing relative to the desired viewing direction not being rendered. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for generating a sequence of two-dimensional images of a three-dimensional object, the two-dimensional images representing the object from respective desired viewing directions, the method comprising the steps of:
-
(a) storing surface portion data corresponding to a plurality of surface portions of the object; (b) sorting the surface portion data to generate a first ordered list of surface portions corresponding to an order in which the portions may be overwritingly displayed to effect hidden surface removal, by (i) determining which, if any, of the surface portions cannot occlude others from any viewing direction and which can, (ii) entering those which cannot occlude any others in the first ordered list so as to be drawn first, and thereafter (iii) entering further surface portions in the first ordered list in succession, such that each of said further surface portions is entered in the first ordered list when the surface portions which it can occlude only surface portions already entered in the first ordered list; (c) sorting surface portions which have not been entered in the first ordered list into a plurality of second ordered lists, each second ordered list being generated with reference to a respective predetermined view direction; (d) selecting, for each two-dimensional image to be generated, one of the plurality of second lists in dependence upon the desired viewing direction of that image; and (e) generating each of the two-dimensional images representing the object by rendering each said portion from the first list and the selected second list in order of occurrence therein, in accordance with the desired viewing direction, portions which are backwards facing relative to the desired viewing direction not being rendered. - View Dependent Claims (9, 10, 11, 12, 13, 18)
-
-
14. A method of generating a signal conveying at least one two-dimensional image representing a three-dimensional object from a desired viewing direction, comprising the steps of:
-
(a) storing surface portion data corresponding to a plurality of surface portions of the object; (b) sorting said surface portion data to generate a first ordered list thereof corresponding to an order in which said portions may be overwritingly displayed to effect hidden surface removal, by (i) determining which, if any, of said surface portions cannot occlude others from any viewing direction and which can, (ii) entering those which cannot occlude any others in said first ordered list so as to be drawn first, and thereafter (iii) entering further surface portions in said first ordered list in succession, such that each of said further surface portions is entered in the first ordered list when the surface portions which it can occlude only surface portions already entered in said first ordered list; (c) sorting surface portions which have not been entered in said first ordered list into a plurality of second ordered lists, each second ordered list being generated with reference to a respective predetermined view direction; (d) selecting, for each two-dimensional image to be generated, one of said plurality of second lists in dependence upon the desired viewing direction of that image; and (e) generating an image signal corresponding to each of said two-dimensional images representing said object by rendering each said portion from the first list and the selected second list in order of occurrence therein, in accordance with the desired viewing direction, portions which are backwards facing relative to the desired viewing direction not being rendered.
-
-
15. A method of generating data defining at least one two-dimensional image representing a three-dimensional object from a desired viewing direction, comprising the steps of:
-
(a) storing surface portion data corresponding to a plurality of surface portions of the object; (b) sorting said surface portion data to generate a first ordered list thereof corresponding to an order in which said portions may be overwritingly displayed to effect hidden surface removal, by (i) determining which, if any, of said surface portions cannot occlude others from any viewing direction and which can, (ii) entering those which cannot occlude any others in said first ordered list so as to be drawn first, and thereafter (iii) entering further surface portions in said first ordered list in succession, such that each of said further surface portions is entered in the first ordered list when surface portions which it can occlude only surface portions already entered in said first ordered list; (c) sorting surface portions which have not been entered in said first ordered list into a plurality of second ordered lists, each second ordered list being generated with reference to a respective predetermined view direction; (d) selecting, for each two-dimensional image to be generated, one of said plurality of second lists in dependence upon the desired viewing direction of that image; (e) generating image data corresponding to each of said two-dimensional images representing the object by rendering each said portion from the first list and the selected second list in order of occurrence therein, in accordance with the desired viewing direction, portions which are backwards facing relative to the desired viewing direction not being rendered; and (f) storing said image data in a storage device.
-
-
16. A method of generating a rendering order list for subsequent use in rendering a two-dimensional image representing a three-dimensional object from a desired viewing direction, comprising the steps of:
-
(a) storing surface portion data corresponding to a plurality of surface portions of the object; (b) sorting said surface portion data to generate a first ordered list thereof corresponding to an order in which said portions may be overwritingly displayed to effect hidden surface removal, by (i) determining which, if any, of said surface portions cannot, assuming that rendering will be performed with back face culling, occlude others from any viewing direction and which can, (ii) entering those which cannot occlude any others in said first ordered list so as to be drawn first, and thereafter (iii) entering further surface portions in said first ordered list in succession, such that each of said further surface portions is entered in the first ordered list when the surface portions which it can occlude are surface portions already entered in said first ordered list; (c) sorting surface portions which have not been entered in said first ordered list into a plurality of second ordered lists, each second ordered list being generated with reference to a respective predetermined view direction; and (d) selecting, for the two-dimensional image to be generated, one of said plurality of second lists in dependence upon the desired viewing direction of that image. - View Dependent Claims (17)
-
Specification