Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-12-18
2003-09-23
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06624810
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 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 accurate.
SUMMARY OF THE INVENTION
The present invention provides a method, system, and computer program product for reducing a boundary of a subspace in a binary space partitioning tree. In one embodiment a space containing an object for which an image is to be rendered and displayed to a user is divided into subspaces. The boundaries of each subspace are recalculated to remove at least a portion of the dead space from within the subspace. The recalculation is performed by analyzing the spatial extent of the object or objects within the each subspace and recalculating the boundaries of each subspace to be coextensive with the boundaries of the object or objects within the subspace.
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
International Business Machines - Corporation
McBurney Mark E.
Nguyen Phu K.
Yee Duke W.
Yociss Lisa L. B.
LandOfFree
Tightened bounding volumes for BSP-trees does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Tightened bounding volumes for BSP-trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tightened bounding volumes for BSP-trees will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3101718