Patent ID: 6580426
Filing Date: 2003-06-17
Classification: G06T

Abstract:
A computer graphics apparatus comprising:a data store configured to store data defining a three-dimensional computer model of a plurality of objects in a three-dimensional space; and a preprocessor operable to partition the three-dimensional space into a plurality of sectors by recursively sub-dividing the three-dimensional space into sectors such that, on each recursion, two sectors are generated using a partition plane positioned with regard to the content of the three-dimensional computer model, the preprocessor being operable to: identify volumes of the three-dimensional space which do not contain any of the objects; determine whether a partition plane having one of a plurality of predetermined directions can be positioned to divide the three-dimensional space to separate an identified volume containing no objects from the rest of the three-dimensional space, wherein each predetermined direction in the plurality of directions available for the partition plane is a direction independent of any object in the three-dimensional computer model; and if it is determined that a partition plane can be so positioned, to position the partition plane so as to create two new sectors in the three-dimensional space, one of the sectors comprising the volume containing no objects, and to add the sectors to a binary space partition tree together with data identifying the objects in each sector.