System, program product and method of rendering a three dimensional image on a display

[0002] 1. Field of the Invention

[0003] The present invention generally relates to image processing systems and, more particularly, to image processing systems capable of finding visible points or fragments that are connected by a line segment to the eyepoint that meets the closure of no other primitive within the same scene.

[0004] 2. Background Description

[0005] In a given scene, , finding visible points or fragments that are connected to the eyepoint by a line segment that meets the closure of no other primitive within the same scene is a well known image processing problem. This visibility problem is discussed by D. Dobkin and S. Teller “Computer Graphics,” Handbook of Discrete and Computational Geometry, chapter 42, pages 779-96. CRC Press, Boca Raton, Fla., 1997 (hereinafter Dobkin).

[0006] As described in Dobkin, the scene, , is composed of modeling primitives (e.g., triangles, or spheres), and a viewing frustum defining an eye position, a view direction, and a field of view. For any scene with n primitives, the complexity of the set of visible fragments might be quadratic as a function of n. One well known approach to solving this visibility problem is the Z-buffer algorithm of E. Catmull as described in “A Subdivision Algorithm for Computer Display of Curved Surfaces”, PhD thesis, Dept. of Computer Science, University of Utah, December 1974.

[0007] The Z-buffer algorithm exploits the discrete nature of the screen to solve the visibility problem in time proportional to n, because it only touches each primitive once. The Z-buffer algorithm solves the visibility problem by maintaining a depth value for each pixel and, only updating the pixels when rendering geometry closer to the eyepoint. For high-depth complexity scenes, the Z-buffer algorithm might result in overdrawing each pixel a considerable number of times. However, despite this potential inefficiency, the Z-buffer is a popular algorithm and widely implemented in hardware.

[0008] Given the wide availability of the Z-buffer approach but with exact visibility computations potentially being too costly in terms of computer time and associated hardware costs, alternative approaches are being sought. One approach is to use the Z-buffer as a filter and design algorithms that compute an approximation of the visible set to reduce the amount of overdraw. More precisely, the visible set (a subset of ) is defined to be a set of modeling primitives that contribute at least one pixel to the screen. In computer graphics, visibility-culling research has focused, mainly, on algorithms for computing estimations of , then, obtaining correct images using the Z-buffer.

[0009] The simplest examples of visibility-culling algorithms are the “backface” and “view-frustum” algorithms, as described by Foley et al. “Computer Graphics, Principles and Practice, Second Edition,” Addison-Wesley, Reading, Mass., 1990. Backface-culling algorithms avoid rendering geometric primitives that face away from the viewer; while viewing-frustum culling algorithms avoid rendering geometric primitives that are outside of the viewing frustum.

[0010] Still another approach is using hierarchical occlusion maps as described by Zhang et al. in “Visibility Culling Using Hierarchical Occlusion Maps,” SIGGRAPH 97 Conference Proceedings, pages 77-88, 1997. The hierarchical occlusion map approach solves the visibility problem by using two hierarchies, an object-space bounding volume hierarchy and another hierarchy of image space occlusion maps. A set of objects (occluders) are selected for each frame from a pre-computed database. The occluders are used to cull unseen geometric primitives. Closely related to this technique is the hierarchical Z-buffer described in U.S. Pat. No. 5,579,455 entitled “Rendering of 3dScenes on a Display Using Hierarchical Z-buffer Visibility” to Greene et al., which is incorporated herein by reference.

[0011] Yet another approach is object-space visibility culling. One such object-space visibility culling technique, described by Teller and Sequin in “Visibility Preprocessing for Interactive Walkthroughs,” Computer Graphics, pages 61-69, July 1991 (hereinafter Teller). Teller teaches dividing space into cells and, then, preprocessing the cells for potential visibility. The Teller technique works particularly well for architectural models. These state of the art visibility-culling techniques mostly exploit the presence of large occluders, and keep track of spatial extents over time.

[0012] In yet another approach, Funkhouser and Sequin in “Adaptive Display Algorithm for Interactive Frame Rates During Visualization of Complex Virtual Environments,” Computer Graphics, pp. 247-54, 1993, describe a constant-frame rendering system.

[0013] However, all of the above state of the art techniques for occlusion-culling have several drawbacks. First of all, the simple backface and viewing-frustum culling algorithms of Foley et al. are unable to cull “overdraw” geometry. For this type of culling, more complex techniques that lead to substantial improvements in rendering time are needed. Unfortunately, these techniques for tighter estimation of the visible set do not come easily. Most currently proposed techniques are quite involved and complex, typically requiring computation of complex object hierarchies in both 3- and 2- space.

[0014] In addition to the above problems, typically, a significant portion of the geometric primitives that are not visible are not culled by the prior art occlusion culling methods. Further, these prior art methods do not allow a user-defined budget to be used for culling, e.g., specifying a limit on the number of primitives to render, and therefore, these prior art methods are not time-critical.

[0015] Thus, there is a need for more efficient rendering techniques for optimizing the rendering of high-depth complexity scenes.

[0016] It is therefore a purpose of the present invention to efficiently select geometric primitives to be rendered in an image;

[0017] It is another purpose of the present invention to efficiently select geometric primitives to be rendered within an image processing system's budget constraints;

[0018] It is yet another purpose of the present invention to efficiently select geometric primitives to be rendered within an image processing system's time constraints.

[0019] The present invention is a Prioritized-Layered Projection (PLP) technique and system for optimizing the rendering of high-depth complexity scenes. Objects in each frame are prioritized with an estimation of the visible set within the rendered frame. Visible sets are not explicitly computed, but, instead, a priority order is computed “on demand” to maximize the likelihood of rendering visible primitives before rendering occluded ones. For a fixed budget, e.g., time or number of triangles, the rendering technique of the present invention constrains that geometry rendering to the budgeted priority.

[0020] The preferred embodiment of the present invention includes two main steps: (1) an occupancy-based tessellation of space; and (2) a solidity-based traversal algorithm. By first computing an occupancy-based tessellation of space, more cells result where there are more geometric primitives. In this spatial tessellation, each cell is assigned a “solidity” value directly proportional to its likelihood of occluding other cells. In its simplest form, a cell's solidity value is directly proportional to the number of primitives contained within the cell. Cells are marked for projection, and the geometric primitives contained within the marked cells are rendered. The present invention uses the cells solidity and other view-dependent information to determine the ordering in which to project cells.

[0021] The foregoing and other objects, aspects and advantages will be better understood from the following detailed preferred embodiment description with reference to the drawings, in which:

[0022] FIG. 1 is a block diagram of a preferred embodiment image processing system;

[0023] FIG. 2 is an example of an image rendered on display;

[0024] FIG. 3 is a basic occlusion culling process flow chart for deciding which primitives are to be rendered;

[0025] FIG. 4 is a flow chart of the preferred embodiment geometric rendering process according to the present invention;

[0026] FIG. 5 is a flow chart showing the preferred space tessellation process;

[0027] FIG. 6 is a representation of tessellated space with geometric representations having geometric attributes according to the preferred embodiment;

[0028] FIG. 7 is a flow chart of the preferred embodiment geometric rendering process of FIG. 4 showing the rendering loop of the solidity based traversal step;

[0029] FIGS. 8A-B are pseudo-code and a corresponding flow chart for the rendering loop step executed in FIG. 7;

[0030] FIG. 9 is a representation of a typical subspace traversal of step 142 of the space in FIG. 6;

[0031] FIGS. 10A-B are pseudo-code and a corresponding flow chart of a preferred solidity computation process of FIGS. 8A-B;

[0032] FIGS. 11A-C are a second example of space tessellation according to the preferred embodiment;

[0033] FIGS. 12A-D are an example of a rendered image after processing according to the preferred embodiment of the present invention.

[0034] Referring now to the drawings, and more particularly, FIG. 1 is a block diagram of a preferred embodiment image processing system 100 that includes, as a minimum, a Central Processing Unit (CPU) 102, a memory subsystem 104 and an Input Output (I/O) subsystem 106 communicating through a data bus 108. Optionally, the system may include a graphics coprocessor 110 to offload graphics processing from the CPU 102, thereby reducing CPU computation-intensive tasks. Additionally, the preferred embodiment system 100 may include an optional graphics accelerator subsystem 112. Processed images are visualized on a display 114.

[0035] FIG. 2 is an example of an image rendered on display 114. The display area 120 is subdivided into display cells 122, normally referred to as pixels. A primitive 124, shown on the display 114, is a portion of the displayed three-dimensional scene. The primitive 124 is a projection of a three-dimensional primitive onto a two-dimensional “image space” of the display area 120. In this example, the projection of the primitive 124 occupies a portion of seven pixels 122.

[0036] FIG. 3 is a basic occlusion culling process flow chart such as may be currently practiced for deciding which primitives, preferably triangles, are to be rendered. Accordingly, the culling process begins in step 130 as a pointer, I, is set to point to the first primitive. In step 132, the primitive is checked to determine if it is occluded by other primitives and, if it is, that occluded primitive is skipped, i.e., not rendered. If, however, the primitive is not occluded then, in step 134 the primitive is rendered. Then, in step 136 I is checked to determine if the last primitive has been processed and, if not, I is set to point to the next primitive in step 130. The process repeats until all unoccluded primitives have been identified and rendered.

[0037] FIG. 4 is a flow chart of the preferred embodiment geometric rendering process according to the present invention. The preferred embodiment geometric rendering and culling process begins in first major step 140 with an occupancy-based tessellation of space, wherein a 3-space covered by the scene is decomposed into disjoint cells. Then, in second major step 142 scenes are rendered using a solidity-based traversal algorithm. In the spatial tessellation, each cell is assigned a “solidity” value directly proportional to its likelihood of occluding other cells. In its simplest form, a cell's solidity value is directly proportional to the number of polygons in the cell in the line of sight. Cells are marked for projection in step 142 and the geometric primitives contained within the marked cells are rendered. Each cell's solidity as well as other view-dependent information are used to determine the ordering in which the cells are projected.

[0038] FIG. 5 is a flow chart showing the preferred space tessellation process of step 140. The preferred spatial decomposition process characteristics are: simple traversal characteristics making it easy and computationally inexpensive to walk from cell to cell; good projection properties making the scene depth-orderable from any viewpoint using efficient linear-time projection algorithms and so, making it easy to estimate screen-space coverage; adaptive cell size to provide space filler efficiency such that it is possible to adaptively sample scene geometry, large cells being located in sparse areas and smaller cells in denser areas; and, a data structure that is easily built and stored efficiently. Accordingly, the preferred spatial data structure is a Delaunay triangulation, which is well known in the art.

[0039] As can be seen in the flow diagram of FIG. 5, a spatial decomposition , which very simply adaptively samples the scene with points; then, is constructed as the Delaunay triangulation of the sample points; and, finally, individual primitives in are assigned to . Accordingly, in step 1400 a rough (bounded-error) octree is constructed using only the original vertices. Then, in step 1402 treating the center of the octree leaves as the vertices of the Delaunay triangulation the spatial tessellation is created. Then, in step 1404 after building , primitives are associated with cells using a naive assignment of the primitives in to . Basically, the scene geometry is “scan-converted” into the mesh.

[0040] FIG. 6 is an example of tessellated space with geometric attributes for geometric representations resulting from step 140. The geometric attributes correspond to short line segments 150. The occupancy-based spatial tessellation is shown in dashed lines 152. The view frustum is a cone represented by a solid, thick lines 154, emanating from viewpoint or eyepoint 155 at the apex. The dark points 156 represent sample points for constructing the occupancy-based spatial tessellation.

[0041] After spatial decomposition in step 140, each of cells 158 of the resulting spatial decomposition has a list of the primitives (from ) assigned to it. In the preferred embodiment, each of the assigned primitives is either completely contained in the cell, or it intersects one of the cell's boundary faces 152. Each cell's solidity value is determined by the number of primitives in that cell. In a final pass over the data during preprocessing, the maximum number of primitives in any cell is computed and used later in the process as a scaling factor.

[0042] FIG. 7 is a flow chart of the preferred embodiment geometric rendering process according to the present invention showing the preferred rendering loop executed in step 142 of FIG. 4. Accordingly, after computing the occupancy based spatial tessellation in step 140, the process enters the rendering loop in step 144 starting from a seed cell, which typically contains the eye position, and carves cells out of the tessellation, preferably along layers of primitives. In step 146, primitives are rendered to produce an image or frame until all primitives have been rendered or a predetermined budget condition is met. Image or frame rendering in step 146 continues until it is determined in step 148 that all of the images have been generated.

[0043] In the preferred rendering step 142, the cells 158 are traversed in roughly front-to-back order. Thus, primitives along each pixel are ordered by their positive distance to the eye point. A rank is assigned to the ordered primitives based on each primitive's visibility in each of the pixels that the primitive touches. Preferably, those primitives that are visible in any cell 158 are assigned a lower rank, 1 for example.

[0044] Then, in step 146 an attempt is made to project the modeling primitives by layers, that is, all primitives of rank 1, then rank 2 and so on. This is done by always projecting a front cell from a collection or set (the front) of unprojected cells 158 closest to the viewpoint 155. The set, the front, are immediate candidates for projection. Also, the front cell is least likely to be occluded based on computed cell solidity values. Initially, the front is empty, and as cells are inserted, their solidity values are accumulated to reflect their position during the traversal. Each time a cell 158 in the front is projected, all of the geometric primitives assigned to that projected cell are rendered.

[0045] Any one of several types of budgets may be employed of the present invention. Preferably, a triangle count budget is used for time-critical rendering. However, a priority budget related to cell rank may be employed to result in a more scene-independent budgeting scheme. Accordingly, for the present invention the visible set is not computed exactly. Instead, a solidity-based ordering is combined with a budget to provide an optimal priority based scene rendering.

[0046] FIG. 8A is pseudo-code for the rendering loop of step 142, but, primarily for the scene rendering step 146 and FIG. 8B is a corresponding a flow chart. First, in step 1460, a test is conducted to determine if there are any cells remaining in the scene to project. If there are no cells to project, a break is initiated. Otherwise, in step 1462, function min( ) returns the minimum element in the priority queue . In step 1464, function project(c) renders all the elements assigned to c; project(c) also keeps counts on the number of primitives actually rendered. In step 1466, function reached_budget( ) returns true if k primitives have been rendered already, with k is the budget target in this example, and if a true is returned, in step 1468 a break is initiated. Then, in step 1470, function cell_adjacent_to(c) lists the cells adjacent to c, the current cell. In step 1472, function projected(n) returns true if cell n has already been projected, and if a true is returned, in step 1474 rendering continues. Then, in step 1476, function update_solidity(n, c) computes the updated solidity ρ of cell n, based on the fact that c is one of its neighbors, and has just been projected. Finally, in step 1478, function enqueue(n, ρ) places n in the queue with a solidity ρ. If n was already in the queue, the function enqueue(n, ρ) will first remove n, and re-insert it with the updated solidity value. Then, in step 148 a check is made whether all images, as desired by the user, have been generated. If not, rendering continues on the next frame in step 146.

[0047] FIG. 9 is a representation of a subspace traversal of the space in FIG. 6 in step 142, as further described with reference to FIGS. 7, 8A and B. The rendered areas are marked by shaded regions 160, 162, 164, 166, 168, 170, 172, 174 and 176. In this example, each cell is rendered according to their numbered sequential label. Unshaded cells are unrendered and occluded by geometry in rendered cells. At any given point during rendering, cells are removed from the front, i.e., from the priority queue in “solidity order,” therefore, the cells with the smallest solidity are projected before the one with larger solidity. The solidity of a cell c used in the rendering algorithm is not an intrinsic property of the cell itself. Instead, a set of conditions are used to estimate, roughly, the visibility likelihood of a cell and, to assure that cells that are more likely to be visible get projected before cells that are less likely to be visible.

[0048] Accordingly, FIG. 10A is pseudo-code and FIG. 10B is a corresponding flow chart of the preferred solidity computation step 1476 of FIGS. 8A-B. The solidity is a numerical representation of how difficult it is for the viewer to see a particular cell. The actual solidity value of a particular cell c in FIG. 8A (substituted for A in FIGS. 10A-B) is not defined, intrinsically, but is defined in terms of the solidity of the cells that intersect the closure of a segment from the cell c to the eye point. The number of primitives inside c is normalized $\left(\frac{\left|A\right|}{{\rho }_{\max }}\right)$

[0049] and, in step 760, a comparison is made based on transferring the accumulated solidity of the cell (A) to an adjacent cell (B) based on the orthogonality of the face shared between cells to the view direction.

[0050] This transfer is maximized if the face shared between cells has a normal vector that is parallel to the view direction and, the cell is in a “star-shaped” position. So, in step 762, to avoid projecting cells (with low solidity values) that are occluded by unprotected cells in the front (with higher solidity values) the cells in the front are forced to be as star-shaped as possible. Thus, all of the vertices of the cells newly-inserted in the front can be seen by the viewer. If the alignment is not star shaped, in step 764 penalties are calculated and, in step 766, applied to the transfer. Accordingly, by carefully tailoring the traversal algorithm to the occupancy-based tessellation, excellent frame rates can be achieved with low preprocessing and rendering costs.

[0051] FIG. 11A is another example of a preferred embodiment space tessellation of a scene 180. In the example of FIG. 11A geometric attributes for the scene are represented by line segments 182, 184, 186, 188 and 190. In FIG. 11B, a spatial decomposition tree, a quadtree in this 2D scene, is added. In 3D the spatial decomposition tree would be an octree. The spatial decomposition tree determines the sample points 192 for computing the occupancy-based spatial tessellation. Next, in FIG. 11C, an occupancy-based spatial tessellation is added as represented by dotted lines 194. In this example, a Delaunay Triangulation for the occupancy-based spatial tessellation. Again, other techniques for sampling, and actually constructing the occupancy-based tessellation may be substituted.

[0052] FIGS. 12A-D show an example of a rendered image after processing according to the preferred embodiment of the present invention. FIG. 12A shows the number of visible primitives for a sequence of images, each image being referred to as a frame. For comparison, the number of rendered triangles for representative budget values is included. The top curve 200 is the total number of visible primitives for each given frame, with visible triangles for budgeted values of 1%, 2%, 5% and 10% represented by curves 202, 204, 206 and 208, respectively. FIG. 12B shows the corresponding rendering times. FIG. 12C is an image of all the visible triangles corresponding to the top curve and, FIG. 12D is an image of the 10% budgeted set corresponding to the bottom curve. As is apparent from FIGS. 12A-D, the preferred embodiment of the present invention reduced rendering time for this example by over a factor of two, while the number of visible primitives is approximately 90% of the total number of visible primitives.

[0053] While the invention has been described in terms of preferred embodiments, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims.