Method for tree-structured hierarchical occlusion in image generators
First Claim
1. In a digital image generator for generating video images to be displayed on a display screen in real time from a digital database of objects, an improved method of occlusion processing for an efficient determination of objects to be displayed visibly in predetermined pixel level regions, comprising the steps of:
- (a) dividing a display screen, on which at least one object in said database of objects is to be displayed, into a predetermined hierarchy of regions forming a tree structure ranging from a highest covered region to a lowest covered pixel level region on said display screen, wherein each region in said hierarchy is rectangular with uniform boundaries of predetermined dimensions in a first axis, and wherein said highest covered region covers the full dimension of the display screen in a second axis;
(b) subdividing an object in said database to provide data pieces corresponding to said highest of said covered regions of said hierarchy of regions on said display screen;
(c) performing a predetermined test on each of said pieces of said object to reveal information as to whether it is to be displayed within each of said regions, said information including whether said piece of said object occludes the region completely, is occluded completely within the region, or is occluded partially within the region;
(d) developing updated hierarchy information for each region in which an object piece occludes any other piece;
(e) deleting from said hierarchy each object piece that is occluded in a region of said hierarchy;
(f) further subdividing said object in correspondence to a next lower region of said hierarchy for each of said pieces that is partially occluded;
(g) repeating steps (c) through (f) until each subdivided piece is occluded, updates said hierarchy, or until a pixel-level region of said hierarchy is reached; and
(h) repeating steps (b) through (g) for each object in said database of objects;
whereby the occlusion for said predetermined pixel level regions of an image is accomplished efficiently.
6 Assignments
0 Petitions
Accused Products
Abstract
A method for determining which objects are visible in each pixel of a digitally-generated image is described. The method uses comparison of distances from the viewpoint (Z-sorting) for occlusion. The number of Z comparisons required is minimized by utilizing a hierarchy of regions in the screen area, and thereby, resolving occlusion for areas larger than pixel areas where possible. Use of the area hierarchy increases the efficiency of the occlusion processing. In a preferred implementation, the screen is divided into equal-sized horizontal regions each corresponding to typically four scanlines. Polygons for each image are subdivided into pieces that correspond to the preset hierarchy of regions, and occlusion processing occurs independently in parallel for two or more regions. Each region is subdivided further into smaller regions, each level of the hierarchy having regions half the size of a higher level region. The minimum and maximum Z values of a polygon'"'"'s contribution to a region are compared to previously determined values for a hierarchy of subregions. Occlusion is accomplished at the highest level of the hierarchy at which portions of the incoming polygon contribution either occlude or are occluded by previous polygons. Provisions are made for transparent and interpenetrating polygons.
78 Citations
10 Claims
-
1. In a digital image generator for generating video images to be displayed on a display screen in real time from a digital database of objects, an improved method of occlusion processing for an efficient determination of objects to be displayed visibly in predetermined pixel level regions, comprising the steps of:
-
(a) dividing a display screen, on which at least one object in said database of objects is to be displayed, into a predetermined hierarchy of regions forming a tree structure ranging from a highest covered region to a lowest covered pixel level region on said display screen, wherein each region in said hierarchy is rectangular with uniform boundaries of predetermined dimensions in a first axis, and wherein said highest covered region covers the full dimension of the display screen in a second axis; (b) subdividing an object in said database to provide data pieces corresponding to said highest of said covered regions of said hierarchy of regions on said display screen; (c) performing a predetermined test on each of said pieces of said object to reveal information as to whether it is to be displayed within each of said regions, said information including whether said piece of said object occludes the region completely, is occluded completely within the region, or is occluded partially within the region; (d) developing updated hierarchy information for each region in which an object piece occludes any other piece; (e) deleting from said hierarchy each object piece that is occluded in a region of said hierarchy; (f) further subdividing said object in correspondence to a next lower region of said hierarchy for each of said pieces that is partially occluded; (g) repeating steps (c) through (f) until each subdivided piece is occluded, updates said hierarchy, or until a pixel-level region of said hierarchy is reached; and (h) repeating steps (b) through (g) for each object in said database of objects; whereby the occlusion for said predetermined pixel level regions of an image is accomplished efficiently. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
Specification