Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-12-18
2003-09-16
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06621492
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates generally to an improved graphics subsystem and in particular to a method and an apparatus for processing binary space partitioning (BSP) trees. Still more particularly, the present invention provides a method and an apparatus for improving the accuracy of the bounding volumes for BSP-trees.
2. Description of the Related Art
The display of two and three dimensional graphic images of complex scenes in real time have improved greatly as hardware and software have improved. These images are very complex, so efficient processing is of utmost importance. Binary space partitioning (BSP) trees were introduced in the early 1980's (See Fuchs, Kedem, and Nayor, “On Visible Surface Generation by A Priori Tree Structures”, SIGGRAPH '80, pp. 124-133, the content of which is hereby incorporated by reference for all purposes) to aid in the processing of 3-D scenes.
BSP trees are a standard tool in image processing and are continually being improved through refinement. A BSP tree divides an n-dimensional space into two components using an n-1 dimensional object. For example, a 0 dimensional point on a line divides the 1 dimensional line into two components. Alternatively, a 1 dimensional line divides a 2 dimensional plane into two components. For a 3 dimension scene, a 2 dimensional plane divides the scene into two components.
The process of subdivision continues recursively to subdivide an n-dimensional space into smaller components called polytopes. A polytope is a generalization of a polyhedron. Informally, it is a multi-dimensional solid with flat sides. The faces are the hyper-planes that are subdividing the n-dimensional space. Storing these polytopes in a BSP tree allows the n-dimensional space to be classified and sorted in a manner that assists in carrying out other processing tasks, such as hidden surface removal.
Polytopes can approximate objects in the n-dimensional space. Therefore, it would be advantageous to have improved bounding volumes in a BSP tree to make graphics processing more efficient.
SUMMARY OF THE INVENTION
The present invention provides a method, system, and program product for creating a child node of a binary space partitioning (BSP) tree node that better approximates the size of an object to be rendered. In one embodiment, a a binary space partitioning tree is created. A rendering process then determines whether either a top node or a child node in a first level of child nodes is a good approximation of the object to be rendered. If not, then the rendering process modifies the binary space partitioning tree to include a new child node having boundaries that are closer to the maximum coordinates of primitives defining the object than are the boundaries of the top node or of the child nodes in the first level of child nodes. This new child node may have a bounding volume that overlaps the bounding volumes of other child nodes in the BSP tree.
REFERENCES:
patent: 4694404 (1987-09-01), Meagher
patent: 6373485 (2002-04-01), Sowizral et al.
patent: 6396492 (2002-05-01), Frisken et al.
patent: 6400846 (2002-06-01), Lin et al.
Brokenshire Daniel Alan
Minor Barry L.
Nutter Mark Richard
McBumey Mark E.
Nguyen Phu K.
Yee Duke W.
Yociss Lisa L. B.
LandOfFree
Method and apparatus using primitive bounding volumes to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus using primitive bounding volumes to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus using primitive bounding volumes to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3054660