Rendering of 3D scenes on a display using hierarchical z-buffer visibility

Abstract

A hierarchical Z-buffer scan-conversion algorithm that does well on both (a) quickly rejecting most of the hidden geometry in a model, and (b) exploiting the spatial and temporal coherence of the images being generated. The method uses two hierarchical data structures, an object-space octree and an image-space Z-pyramid, in order to accelerate scan conversion. The two hierarchical data structures make it possible to reject hidden geometry very rapidly while rendering visible geometry with the speed of scan conversion. For animation purposes, the algorithm is also able to exploit temporal coherence. The resulting method is well suited to models with high depth complexity, achieving significant speedup in some cases compared to ordinary scan conversion.

We claim: 
     
       1. Apparatus for use in rendering a 3D scene onto a display, said display having a display area divided into a plurality of display cells, said 3D scene comprising at least one surface divided into a plurality of surface cells, each of said surface cells corresponding to a respective one of said display cells, said apparatus comprising a depth buffer having a plurality of granularity levels proceeding from a finest level to a coarsest level, each of said granularity levels containing at least one Z-max element,   each of the Z-max elements in said finest granularity level covering a respective one of said display cells,   each of the Z-max elements in a granularity level coarser than said finest granularity level corresponding to and covering all of the display cells covered by a respective group of the Z-max elements in the next finer granularity level,   each of said Z-max elements which covers a display cell into which a surface cell has been rendered, containing a depth value indicating the depth in said 3D scene of the farthest surface cell which is rendered into the group of display cells covered by said Z-max element.   
     
     
       2. Apparatus according to claim 1, further comprising a Z-min element corresponding to each of said Z-max elements which is in a granularity level coarser than said finest granularity level, each of said Z-min elements whose corresponding Z-max element covers a display cell into which a surface cell has been rendered, containing a depth value indicating the depth in said 3D scene of the nearest surface cell which is rendered into the group of display cells covered by the Z-max element corresponding to said Z-min element.   
     
     
       3. Apparatus according to claim 1, wherein said coarsest level contains exactly one Z-max element. 
     
     
       4. Apparatus according to claim 1, wherein each of said groups of Z-max elements in a given granularity level is defined to cover exactly a 2×2 rectangle of the display cells covered by the individual Z-max elements in said given granularity level. 
     
     
       5. Apparatus according to claim 1, further comprising a display buffer having a data element corresponding to each of said display cells, each of said data elements which corresponds to a display cell into which a surface cell has been rendered, containing a color value for said surface cell. 
     
     
       6. A method for updating a depth buffer for a display having a display area divided into a plurality of display cells, for use with a plurality of new depth values for corresponding predetermined ones of said display cells, for use further with a depth buffer having a plurality of granularity levels proceeding from a finest level to a coarsest level, each of said granularity levels containing at least one Z-max element, each of the Z-max elements in said finest granularity level covering a respective one of said display cells, each of the Z-max elements in a granularity level coarser than said finest granularity level corresponding to and covering all of the display cells covered by a respective group of the Z-max elements in the next finer granularity level, comprising the steps of: writing each of said new depth values into said finest granularity level at the Z-max element which covers the display cell to which the new depth value corresponds; and   updating each of the Z-max elements in the granularity levels coarser than said finest granularity level, which Z-max elements cover the display element to which one of said new depth values correspond, to contain the farthest depth value of all the display cells covered by such Z-max element.   
     
     
       7. A method according to claim 6, wherein said step of updating comprises the step of iteratively, for progressively coarser current granularity levels beginning with the granularity level which is immediately coarser than said finest granularity level, for each given Z-max element in the current granularity level which covers the display element to which one of said new depth values corresponds, writing into said given Z-max element, if the farthest depth value in all of the Z-max elements which correspond to the given Z-max element in the next-finer granularity level to the current granularity level is nearer than the depth value than in said given Z-max element, said farthest depth value.   
     
     
       8. A method according to claim 6, wherein said depth buffer further has a Z-min element corresponding to each of said Z-max elements which is in a granularity level coarser than said finest granularity level, further comprising the step of updating each of the Z-min elements in the granularity levels coarser than said finest granularity level, the Z-max elements corresponding to which Z-min elements cover the display element to which one of said new depth values correspond, to contain the nearest depth value of all the display cells covered by the Z-max element corresponding to such Z-min element.   
     
     
       9. A method for updating a depth buffer for a display having a display area divided into a plurality of display cells, for use with a plurality of new depth values for corresponding predetermined ones of said display cells, for use further with a depth buffer having a plurality of granularity levels proceeding from a finest level to a coarsest level, each of said granularity levels containing at least one Z-max element, each of the Z-max elements in said finest granularity level covering a respective one of said display cells, each of the Z-max elements in a granularity level coarser than said finest granularity level corresponding to and covering all of the display cells covered by a respective group of the Z-max elements in the next finer granularity level, comprising the steps of: writing each of said new depth values into said finest granularity level at the Z-max element which covers the display cell to which the new depth value corresponds; and   iteratively, for a particular one of said new depth values and for progressively coarser current granularity levels beginning with the granularity level which is immediately coarser than said finest granularity level, at least while said particular new depth value is nearer than the depth value then in the Z-max element of the current granularity level which covers the display cell corresponding to said particular new depth value,   writing said particular new depth value into said Z-max element of the current granularity level which covers the display cell corresponding to said particular new depth value.   
     
     
       10. A method according to claim 9, wherein said iteration terminates when said particular new depth value is not nearer than the depth value then in the Z-max element of the current granularity level which covers the display cell corresponding to said particular new depth value. 
     
     
       11. A method according to claim 9, wherein said depth buffer further has a Z-min element corresponding to each of said Z-max elements which is in a granularity level coarser than said finest granularity level, further comprising the step of updating each of the Z-min elements in the granularity levels coarser than said finest granularity level, the Z-max elements corresponding to which Z-min elements cover the display element to which one of said new depth values correspond, to contain the nearest depth value of all the display cells covered by the Z-max element corresponding to such Z-min element.   
     
     
       12. A method for attempting to prove that a subject surface is hidden relative to surfaces previously rendered, for use in ultimately displaying a 3D scene on a display having a display area divided into a plurality of display cells, said scene having a plurality of said surfaces, said subject surface being divided into a plurality of subject surface cells corresponding to respective destination ones of said display cells, each of said subject surface cells having a depth, for use further with a depth buffer having a plurality of granularity levels proceeding from a finest level to a coarsest level, each of said granularity levels containing at least one Z-max element, each of the Z-max elements in said finest granularity level covering a respective one of said display cells, each of the Z-max elements in a granularity level coarser than said finest granularity level corresponding to and covering all of the display cells covered by a respective group of the Z-max elements in the next finer granularity level,   said method comprising the steps of:   finding a covering one of said Z-max elements which covers all of said destination display cells; and   determining whether the depth value in said covering Z-max element is nearer than the nearest of said subject surface cells and terminating said method affirmatively if so.   
     
     
       13. A method according to claim 12, wherein said depth buffer further has a Z-min element corresponding to each of said Z-max elements which is in a granularity level coarser than said finest granularity level, further comprising the step of determining whether the depth value in the Z-min element corresponding to said covering Z-max element is farther than the nearest of said subject surface cells and terminating said method non-affirmatively if so.   
     
     
       14. A method according to claim 12, further comprising the step of, after said step of determining, further determining whether the granularity level of said covering Z-max element is finer than a predetermined granularity and terminating said method non-affirmatively if so. 
     
     
       15. A method according to claim 12, further comprising the steps of: finding a first one of the Z-max elements which, in the granularity level immediately finer than the level of said covering Z-max element, corresponds to said covering Z-max element and covers a first non-null portion of said subject surface; and   attempting to prove that said first portion of said subject surface is hidden relative to surfaces previously rendered and terminating said method non-affirmatively if such attempt fails.   
     
     
       16. A method according to claim 15, further comprising the steps of: repeating said steps of finding and attempting to prove, for different ones of said Z-max elements which, in the granularity level immediately finer than the level of said covering Z-max element, corresponds to said covering Z-max element and covers a non-null portion of said subject surface, said repetition continuing until said method terminates in non-affirmatively response to a repetition of said step of attempting to prove; and   after said step of repeating, terminating said method affirmatively.   
     
     
       17. A method according to claim 15, wherein said step of attempting to prove comprises the step of determining whether the depth value in said first Z-max element is nearer than the nearest surface cell of said first portion of said subject surface and, and if so, then terminating affirmatively said step of attempting to prove. 
     
     
       18. A method according to claim 12, further comprising, after said step of determining, the steps of: iterating through finer-level Z-max elements which, in the granularity level immediately finer than the level of a current granularity level, corresponds to a superior Z-max element in said current level and covers a non-null portion of said subject surface; and   in each such iteration, making an attempt to prove that the portion of said subject surface covered by the finer-level Z-max element is hidden relative to surfaces previously rendered and terminating said method non-affirmatively if such attempt fails,   each given iteration of said step of making an attempt to prove, comprising the steps of:   determining whether the depth value in the finer-level Z-max element is nearer than said nearest of said subject surface cells;   if so then terminating affirmatively the given iteration of said step of making an attempt to prove;   and if not then recursively performing the steps of iterating and in each iteration making said attempt to prove, for progressively finer current granularity levels to and including a predetermined minimum granularity level,   said current granularity level beginning with the granularity level of said covering Z-max element,   and said method terminating non-affirmatively in response to a negative determination in any repetition of said step of determining whether the depth value in the finer-level Z-max element is near than said nearest of said subject surface cells, for a current granularity level which is said predetermined minimum granularity level.   
     
     
       19. A method according to claim 12, further comprising, after said step of determining, the steps of: iterating through finer-level Z-max elements which, in the granularity level immediately finer than the level of a current granularity level, corresponds to a superior Z-max element in said current level and covers a non-null portion of said subject surface; and   in each such iteration, making an attempt to prove that the portion of said subject surface covered by the finer-level Z-max element is hidden relative to surfaces previously rendered and terminating said method non-affirmatively if such attempt fails,   each given iteration of said step of making an attempt to prove, comprising the steps of:   determining whether the depth value in the finer-level Z-max element is nearer than the nearest surface cell in the portion of said subject surface covered by the finer-level Z-max element;   if so then terminating affirmatively the given iteration of said step of making an attempt to prove;   and if not then recursively performing the steps of iterating and in each iteration making said attempt to prove for progressively finer current granularity levels to and including a predetermined minimum granularity level,   said current granularity level beginning with the granularity level of said covering Z-max element,   and said method terminating non-affirmatively in response to a negative determination in any repetition of said step of determining whether the depth value in the finer-level Z-max element is near than the nearest surface cell in the portion of said subject surface covered by the finer-level Z-max element, for a current granularity level which is said predetermined minimum granularity level.   
     
     
       20. A method according to claim 18, wherein said depth buffer further has a Z-min element corresponding to each of said Z-max elements which is in a granularity level coarser than said finest granularity level, further comprising the step of determining whether the depth value in the Z-min element corresponding to said covering Z-max element is farther than the nearest of said subject surface cells and terminating said method non-affirmatively if so,   and wherein each of said iterations of said step of making an attempt to prove further comprises, prior to the step of recursively performing, the step of determining whether the depth value in the Z-min element corresponding to the finer-level Z-max element is farther than the nearest of said subject surface cells and terminating said method non-affirmatively if so.   
     
     
       21. A method for rendering sequential frames on a display, each of said frames being a respective view of a plurality of objects, each of said views comprising at least one camera parameter, comprising the steps of: determining, with a visibility algorithm, a first subset of said objects to render in a first frame;   maintaining an indication of which of said objects are in said first subset;   rendering said first subset of objects on said display in said first frame;   re-rendering said first subset of objects on said display in a second frame from said maintained indications;   determining, with a visibility algorithm, a second subset of said objects to render in said second frame in addition to the objects in said first subset; and   rendering said second subset of objects on said display in said second frame.   
     
     
       22. A method according to claim 21, wherein the view of said plurality of objects in said first frame is different from the view of said plurality of objects in said second frame. 
     
     
       23. A method according to claim 21, wherein said step of maintaining an indication of which of said objects are in said first subset, comprises the step of preparing a list of the objects in said first subset, and wherein said step of re-rendering said first subset of objects on said display in a second frame from said maintained indication, comprises the step of re-rendering on said display in said second frame, all of the objects on said list.   
     
     
       24. A method according to claim 23, further comprising the steps of: adding said second subset of objects to said list;   re-rendering on said display in a third frame, all of the objects on said list;   determining, with a visibility algorithm, a third subset of said objects to render in said frame in addition to those objects on said list; and   rendering said third subset of objects on said display in said third frame.   
     
     
       25. A method according to claim 24, further comprising the steps of: determining, with a visibility algorithm, the objects in said first subset which are hidden in the view of said second frame by objects in said second subset; and   deleting said hidden objects from said list.   
     
     
       26. A method according to claim 21, for use with a model space containing said plurality of objects, said model space being represented with an octree having a plurality of nodes including a root node, each of said nodes corresponding to a predetermined sub-space of said model space, each of said nodes except said root node having a parent node, the sub-space corresponding to each of said nodes except said root node being wholly within the sub-space corresponding to the node's parent node, for use further with a plurality of primitives, each associated with at least one of said nodes,   wherein each of said objects comprises the sub-space corresponding to a respective one of said nodes,   and wherein said step of rendering said first subset of objects comprises the step of rendering all of the primitives in said plurality of primitives which are visible in the view of said first frame, and which are associated with the node of an object in said first subset.   
     
     
       27. A method according to claim 26, wherein each of said sub-spaces is bounded by faces, and wherein each of said steps of determining objects to render comprises the step of making an attempt to prove that all of the faces of the sub-space of one of said plurality of objects are hidden in the view of a frame. 
     
     
       28. A method according to claim 21, for use with a model space containing said plurality of objects, each of said objects comprising a sub-space of said model space, each of said sub-spaces being bounded by faces, wherein said step of determining a first subset of said objects to render comprises the step of making an attempt to prove that all of the faces of one of said sub-spaces are hidden in the view of said first frame. 
     
     
       29. Apparatus for use in rendering a view of a model space onto a display, comprising a computer-readable storage medium having stored thereon: information in a data structure having a plurality of nodes organized in a hierarchical tree, said nodes including a root node, each of said nodes corresponding to a predetermined sub-space of said model space, each of said nodes except said root node having a parent node, the sub-space corresponding to each of said nodes except said root node being wholly within the sub-space associated with the node's parent node,   said information representing a plurality of surface primitives, each associated with at least one of said nodes and each at least partly contained within the sub-space corresponding to each of the nodes with which the surface primitive is associated.   
     
     
       30. Apparatus according to claim 29, wherein said hierarchical tree is an octree, wherein all of said sub-spaces are cubic, and wherein the sub-space corresponding to each of said nodes except said root node occupies exactly one octant of the sub-space corresponding to the node's parent node. 
     
     
       31. A method for rendering a 3D scene onto a display, said 3D scene comprising a view of a model space which includes a plurality of surface primitives, comprising the steps of: preparing an object-space octree having a plurality of nodes including a root node, each of said nodes except said root node having a parent node, each of said nodes corresponding to a respective sub-space of said model space, the sub-space of each of said nodes except said root node occupying an octant of the sub-space of the node's parent node, at least each of said primitives which is larger than a particular size being associated with a node whose corresponding model space completely contains the primitive; and   for current nodes of said octree beginning with said root node, performing the recursire steps of: (a) making a determination whether the sub-space corresponding to the current node is definitively hidden relative to primitives previously rendered in said scene, (b) only if not, then rendering at least visible parts of the primitives associated with said current node, and (c) also only if not, recursively performing said recursive steps for each child node of said current node in front-to-back order of the sub-spaces corresponding to said child nodes.   
     
     
       32. A method according to claim 31, wherein each of said primitives in said plurality of surface primitives is associated with a node whose corresponding sub-space completely contains the primitive. 
     
     
       33. A method according to claim 31, wherein all of said primitives which are smaller than said particular size and which intersect two of said sub-spaces which are both larger than a second particular size, are associated with both of the nodes corresponding to said two sub-spaces. 
     
     
       34. A method according to claim 31, wherein for each of said primitives which is associated with a node whose corresponding sub-space contains the primitive, the associated node is the node whose corresponding sub-space is the smallest of said sub-spaces which contains the primitive. 
     
     
       35. A method according to claim 31, wherein each of said sub-spaces is bounded by faces, at least one of which faces of each sub-space is forward-facing, wherein said step of making a determination whether the sub-space corresponding to the current node is definitively hidden relative to primitives previously rendered, comprises the steps of: determining whether all of the forward-facing faces of the sub-space corresponding to the current node are definitively hidden relative to primitives previously rendered;   and if not then terminating non-affirmatively said step of making a determination;   and if so then terminating affirmatively said step of making a determination.   
     
     
       36. A method according to claim 35, wherein said display is divided into a plurality of display cells, and wherein each of said forward-facing faces is divided into a plurality of face cells each corresponding to one of said display cells and each having a depth, for use with a depth buffer having a plurality of granularity levels proceeding from a finest level to a coarsest level, each of said granularity levels containing at least one Z-max element, each of the Z-max elements in said finest granularity level covering a respective one of said display cells, each of the Z-max elements in a granularity level coarser than said finest granularity level corresponding to and covering all of the display cells covered by a respective group of the Z-max elements in the next finer granularity level, each of said Z-max elements which covers a display cell into which a surface cell has been rendered, containing a depth value indicating the depth in said 3D scene of the farthest surface cell which is rendered into the group of display cells covered by said Z-max element,   wherein said step of determining whether all of the forward-facing faces are definitively hidden comprises the steps of:   iteratively, through said forward-facing faces, deciding whether the face is definitively hidden relative to primitives previously rendered;   terminating non-affirmatively said step of determining if said step of determining if said step of deciding terminates non-affirmatively for any of said forward-facing faces; and   terminating affirmatively said step of determining otherwise,   wherein said step of deciding whether the face is definitively hidden comprises the steps of:   finding a covering one of said Z-max elements which covers all of the face cells of the face; and   detecting whether the depth value in said covering Z-max element is nearer than the nearest of the face cells of said first one of said forward-facing faces and terminating affirmatively said step of deciding, if so.   
     
     
       37. A method according to claim 31, wherein said display is divided into a plurality of display cells, and wherein each of said surface primitives associated with said current node is divided into a plurality of surface cells each corresponding to one of said display cells and each having a depth, for use with a depth buffer having a plurality of granularity levels proceeding from a finest level to a coarsest level, each of said granularity levels containing at least one Z-max element, each of the Z-max elements in said finest granularity level covering a respective one of said display cells, each of the Z-max elements in a granularity level coarser than said finest granularity level corresponding to and covering all of the display cells covered by a respective group of the Z-max elements in the next finer granularity level, said groups being defined such that the display cells covered by each of said groups are contiguous,   wherein the step of rendering at least visible parts of the primitives associated with said current node comprises the steps of, for at least one given primitive associated with said current node;   for each of the surface cells in said given primitive, writing the depth value of said surface cell into said finest granularity level at the Z-max element which covers the display cell to which said surface cell corresponds, if the depth value of said surface cell is nearer than the depth value than in the Z-max element which covers the display cell to which said surface cell corresponds; and   updating each of the Z-max elements in the granularity levels coarser than said finest granularity level, which Z-max elements cover the display element to which one of said new depth values correspond, to contain the farthest depth value of all the display cells covered by such Z-max element.