Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-02-24
2003-06-17
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S418000, C345S419000, C345S420000
Reexamination Certificate
active
06580426
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to apparatus for generating graphical images, and is particularly concerned with the process of converting information describing a scene to be represented into a rasterised image.
2. Description of Related Art
Spatial partitioning is a technique which allows a problem to be broken down into a number of smaller more soluble problems. In the field of computer graphics, objects to be represented in an environment are defined in terms of three-dimensional data, which then needs to be rendered into rasterised two-dimensional data to be displayed on a VDU. From a particular viewpoint, the projections of the objects may overlap significantly, which can lead to very difficult computations having to be made.
By breaking down the larger rendering problem into a number of smaller problems, the overall rendering process can be made easier. As described in “Computer Graphics Principles and Practices” by Foley, Van Dam, Feiner and Hughes, 2nd Edition, Addison-Wesley Publishing Company, ISBN 0-201-12110-7) pp 664-680, it is possible to partition a space by superimposing a three-dimensional grid over a space within which objects are defined, and then each grid box can be processed independently.
Adaptive partitioning, in which the size of partitions within the space varies, involves the sub-division of the space to be rendered according to a recursive process, until a termination criterion is reached. For example, sub-division may stop when there are fewer than a maximum number of objects in a partition.
The partitioning information can be carried in a data structure such as a binary space partition tree (BSP). However, a BSP tree can become unwieldy if partitioning is carried out incorrectly. A number of nodes of the BSP tree may become difficult to process or time consuming in that they represent nearly empty partitions of the space. Moreover, arbitrary partitioning of a space may lead to division of objects between two parts of a space. This can actually increase the computational expense of the rendering process.
It is object of at least an aspect of the invention to provide an improved means of partitioning a space preliminary to rendering procedures.
BRIEF SUMMARY OF THE INVENTION
According to a first aspect of the invention, apparatus for arranging data defining a scene to be represented graphically comprises means for partitioning the scene by means of a plane oriented in a selected one of a predetermined set of directions, the means for partitioning being operable to select the direction and position of the plane with reference to the content of the scene.
According to a second aspect of the invention, a method for arranging data defining a scene to be represented graphically comprises the steps of defining a predetermined set of partition directions, processing the content of the scene to identify a suitable partition plane in one of those predetermined directions, and partitioning the scene by means of the partition plane.
REFERENCES:
patent: 5355325 (1994-10-01), Uhlmann
patent: 5402532 (1995-03-01), Epstein et al.
patent: 5579454 (1996-11-01), Billyard et al.
patent: 5748197 (1998-05-01), Guibas et al.
patent: 5757321 (1998-05-01), Billyard
patent: 6054991 (2000-04-01), Crane et al.
patent: 6215503 (2001-04-01), Snyder et al.
patent: 6310620 (2001-10-01), Lauer et al.
patent: 6373485 (2002-04-01), Sowizral et al.
patent: 6429864 (2002-08-01), Schwarzer
patent: 6437796 (2002-08-01), Sowizral et al.
patent: 2229811 (1990-10-01), None
patent: 2298111 (1996-08-01), None
patent: WO 98/43208 (1998-10-01), None
Hayder Radha, et al., “Image Compression Using Binary Space Partitioning Trees”, Dec., 1996, IEEE Transactions on Image Processing, vol. 5, No. 1, pp. 1610-1624.
J. Foley et al., Computer Graphics Principles and Practices, 2ndEdition, Addison-Wesley Publishing Company, 1996, pp. 664-681.
Billyard Adam Michael
Scallan Damian Justin
Small Jonathan Andrew Stanley
Withey Robert Keith John
Brier Jeffery
Canon Kabushiki Kaisha
Chung Daniel J
LandOfFree
Computer graphics apparatus for processing of data defining... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer graphics apparatus for processing of data defining..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer graphics apparatus for processing of data defining... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3148620