Method and device for rending three-dimensional graphics

A method for updating values of a depth buffer comprising values for display blocks of a display, and a device for implementing the method. The display is partitioned into a plurality of display regions, including a plurality of display blocks and having a minimum region depth value and a maximum region depth value. Each display region includes a plurality of display subregions. A minimum subregion depth value and a maximum subregion depth value are determined relative to at least one of the minimum region depth value and the maximum region depth value.

TECHNICAL FIELD OF THE INVENTION

The present invention relates to a method for updating a depth buffer comprising depth values for rendering three-dimensional graphics. The invention also relates to a device for implementing the method.

DESCRIPTION OF RELATED ART

Real-time rendering of three-dimensional graphics has a number of appealing applications on a portable electronic apparatus, such as a mobile terminal. Such applications include, e.g., games man-machine interfaces, messaging, and m-commerce. Since three-dimensional rendering is a computationally intensive task, dedicated hardware is often used to reach sufficient performance.

During three-dimensional rendering, a depth buffer may be used to resolve visibility, because geometric primitives, such as polygons or triangles, can be drawn in any order. The depth buffer stores a distance from the eye to the object. If a new object to be rendered is farther away than the contents of the depth buffer, it is hidden by already drawn content and should not be displayed, and the depth buffer should not be overwritten.

However, such a graphics system is not optimal, as a pixel can be overdrawn several times. Even if a pixel is overdrawn several times, only one geometric primitive (polygon) will be visible at the end.

One way to decrease depth buffer accesses is to use occlusion culling. The screen is divided into display regions comprising e.g. 8×8 display blocks. For each display region the maximum depth value or z-value, zmax, for the display region is stored in a memory, such as an on-chip memory or a cache memory, which is fast and energy-efficient. When a new polygon is to be rendered inside said region, the minimum z-value, zmin, of the part of the polygon inside that display region is computed or estimated. If zmin is larger than zmax of the display region, the polygon that is to be rendered is completely occluded for that display region, and that display region need not be processed any further. If the polygon is not occluded, the pixels inside the display region are processed one by one to decide whether the depth buffer should be overwritten with the values of the polygon.

It is also possible to store both zmin and zmax for a display region in the memory. Initially, zmin and zmax are set to initial values, zmin=FAR and zmax=NEAR. When a new polygon is to be rendered in a display region, zmin and zmax are calculated or estimated for that part of the polygon, which is to be rendered in the display block. If zmin for the polygon is larger than zmax for the display region, the part of the polygon that is inside that display region will definitely not be rendered, and the depth buffer need not be updated. If zmax for the polygon is smaller than zmin for the display region, the depth buffer can simply be overwritten without first being read. If the range defined by zmin and zmax for the polygon overlaps with the range defined by zmin and zmax for the display region, then each z-value for the polygon is computed and compared to the corresponding z-value stored in the depth buffer. Thus, it may be decided whether the depth buffer should be overwritten with the z-value for the polygon for that pixel.

The effectiveness of the culling is dependent on the size of the display regions. With smaller display regions the culling can be made more accurate. However, the smaller display regions, the more memory resources are required.

In a portable electronic apparatus, the bandwidth usage to main memory should be reduced as much as possible, because such memory accesses consume a significant portion of the energy, which is a scarce resource in a portable electronic apparatus.

SUMMARY OF THE INVENTION

It is an object of the invention to provide a method and a device, which decrease the bandwidth requirements for memory reads.

In a first aspect, the invention provides a method for reading values from and/or writing values to a depth buffer comprising depth values for display blocks of a display, whereby the display is partitioned into a plurality of display regions including a plurality of display subregions each including a plurality of said display blocks. The method comprises: determining a minimum region depth value and a maximum region depth value for the display blocks of at least one display region; and determining a minimum subregion depth value and a maximum subregion depth value for the display blocks of at least one display subregion.

In an embodiment, the minimum subregion depth value is determined relative to the minimum region depth value and the maximum subregion depth value is determined relative to the maximum region depth value.

In another embodiment, the minimum subregion depth value is determined relative to the minimum and maximum region depth value and the maximum subregion depth value is determined relative to the maximum and minimum region depth value.

The minimum subregion depth value may be determined such that it is larger than or equal to the minimum region depth value and the maximum subregion depth value such that it is smaller than or equal to the maximum region depth value. Moreover, the minimum subregion depth value may be determined such that it is smaller than or equal to all stored depth values for said subregion and the maximum subregion depth value such that it is larger than or equal to all stored depth values for said subregion. In addition, the minimum region depth value may be determined such that it is smaller than or equal to all stored depth values for said region and the maximum region depth value such that it is larger than or equal to all stored depth values for said region

According to another embodiment, at least one of a minimum depth value and a maximum depth value of a geometric primitive to be rendered in a specific display subregion is determined; and at least one of the minimum depth value and the maximum depth value is compared with at least one of the minimum subregion depth value and the maximum subregion depth value for determining whether the depth buffer needs to be read for said display subregion. Moreover, at least one of a minimum depth value and a maximum depth value of a geometric primitive to be rendered may be determined in a specific display region; and at least one of the minimum depth value and the maximum depth value is compared with at least one of the minimum region depth value and the maximum region depth value for determining whether the depth buffer needs to be read for said display region.

At least one geometric primitive depth value may be determined for at least one display block of said subregion. The depth value of said at least one display block may be compared with at least one of the minimum subregion depth value and the maximum subregion depth value to determine whether the depth buffer needs to be read for said display block. The geometric primitive depth value of said at least one display block may be compared with at least one of the minimum region depth value and the maximum region depth value to determine whether the depth buffer needs to be read for said display block.

In an alternative embodiment, the minimum subregion depth value, zminsub, may be determined relative to the minimum region depth value, zminr, and the maximum region depth value, zmaxr, according to the equation:
zminsub=zminr+(zmaxr−zminr)*k/(2m−1)

and the value of the maximum subregion depth value, zmaxsub, may be determined relative to the minimum region depth value, zminr, and the maximum region depth value, zmaxr, according to the equation:
zmaxsub=zmaxr+(zminr−zmaxr)*s/(2n−1)

n being the number of bits used for encoding zmaxsuband m being the number of bits used for encoding zminsubrelative to the minimum region depth value and the maximum region depth value.

Alternatively, the value of the minimum subregion depth value, zminsub, may be determined relative to the minimum region depth value, zminr, and the maximum region depth value, zmaxr, according to the equation:
zminsub=zmin r+(zmaxr−zminr)*k/2m

and the value of the maximum subregion depth value, zmaxsub, may be determined relative to the minimum region depth value, zminr, and the maximum region depth value, zmaxr, according to the equation:
zmaxsub=zmaxr+(zminr−zmaxr)*s/2n

wherein m is the number of bits used for encoding the minimum subregion depth value and n is the number of bits used for encoding the maximum subregion depth value relative to the minimum region depth value and the maximum region depth value.

In still another embodiment, the method comprises first determining the minimum subregion depth value relative to the minimum region depth value and the maximum region depth value, and then determining the maximum subregion depth value relative to the minimum subregion depth value and the maximum region depth value. Alternatively, the method comprises first determining the maximum subregion depth value relative to the minimum region depth value and the maximum region depth value, and then determining the minimum subregion depth value relative to the maximum subregion depth value and the minimum region depth value.

In another aspect, there is provided a processing device for performing the methods indicated above. The device is further defined in the appended patent claims.

In a further aspect, there is provided an electronic apparatus comprising a processing device as defined above. The apparatus may be a mobile radio terminal, a pager, a communicator, an electronic organizer, a smartphone, a personal digital assistant, a handheld device or a computer. The apparatus may be a mobile telephone. In a still further aspect, there is provided a computer program product comprising computer program code means to execute the method as mentioned above when the computer program code means is run by an electronic device having computer capabilities. The computer program product may be embodied on a computer readable medium.

DETAILED DESCRIPTION OF EMBODIMENTS

FIG. 1illustrates an electronic apparatus in which the device and method according to the invention may be implemented. The electronic apparatus is in this example embodied as, but not limited to, a mobile telephone1.

According to embodiments of the invention, z-values or depth values for geometric primitives are tested against at least one of a minimum depth value, zmin, and a maximum depth value, zmax, which are associated with a specific display region. An object may be built up of one or several geometric primitives, such as polygons or, more specifically, triangles. Below, the terms “object”, “geometric primitives” and “polygones” are used to describe something that should be rendered. Geometric primitives that have already been rendered are called “content”.

According to an embodiment of the invention, estimated or calculated minimum, obj-zminr, and, maximum, obj-zmaxr, z-values of a geometric primitive or polygon to be rendered inside a display region are tested against at least one of zminrand zmaxrfor the display region. If it may be definitely determined that all the display blocks of the polygon to be rendered will be visible when rendered, a depth buffer need not be read during the rendering of the polygon, only written to. If it may be definitely determined that the polygon will be occluded, the depth buffer need not be read or written to during the rendering. Finally, if it may be determined that the polygon to be rendered may be at least partly visible when rendered, then a depth value, obj-z-value, of the polygon is calculated for each display block. These calculated depth values per display block could in turn be compared with stored values of the display block. If it can be determined from this comparison that the polygon display block is visible during rendering, the depth value can be directly written to the depth buffer and no read of the values stored in the depth buffer is needed for that display block. If it can be determined that the polygon display block is occluded, no write of values stored in the depth buffer is needed either.

According to another embodiment of the invention, each display region is partitioned into display subregions. A minimum subregion depth value, zminsub, and a maximum subregion depth value, zmaxsub, for each display subregion are known to lie in the range of zminrand zmaxrfor the complete display region. Therefore, according to the invention, the minimum and maximum depth values for each display subregion may be described relative to the minimum- and maximum depth value of the display region, which means that even further readings of the depth buffer may be avoided, as will be described below. However, the relative values need to be read.

The memory bandwidth requirements for implementing the invention is lower compared to conventional occlusion culling. As memory accesses are relatively power consuming, the present invention is useful in portable electronic devices, in which memory and battery capacity is limited, such as in a handheld device, a mobile radio terminal, a pager, a communicator, an electronic organizer, a smartphone, a cellular phone or a personal digital assistant. However, the invention may also be implemented in a stationary electronic device, such as a computer.

The mobile telephone1shown inFIG. 1comprises a man-machine interface for interaction between a user and the mobile telephone1. The man-machine interface comprises, but is not limited to, a display2, such as an LCD display or a touch screen, on which graphics, such as still images, continuous streams of images, icons, text, etc., may be displayed. To render three-dimensional objects, such as polygons, the objects are tested for occlusion during rendering to determine whether the depth buffer at all needs to be accessed, as will be explained below.

FIG. 2is a block diagram of an embodiment of a system for determining, comparing and storing z-values. A processor10, such as a CPU (Central Processing Unit), a DSP (Digital Signal Processor), an ASIC (Application Specific Integrated Circuit), a FPGA (Field-Programmable Gate Array), hard-wired logic etc., is connected to a memory11by means of a data bus12. The processor may be responsible for the overall control of the mobile telephone1.

A processing device10a, such as a GPU, may be provided as a stand-alone processor or be provided by software implemented in the processor10and be configured to generate z-values and various maximum and minimum depth values as will be explained below. The GPU may also be arranged for producing color data for the objects. The memory11may comprise computer readable instructions or code means, such as code portions of an application program, which is run by the system. The application program may be a computer game or a CAD (Computer Aided Design) program.

The processor10retrieves instructions from the memory11, and executes them in order to perform specific tasks. A task for the processor10may be to provide a display controller13with information regarding content or graphics to be drawn on a display14. The display controller13may be provided as a separate hardware component, such as a processor, a DSP, an ASIC, a FPGA, hard-wired logic etc. Alternatively, the display controller13is implemented with a combination of software and hardware, or it may be provided in software and executed by the processor10. The display controller13is connected to the data bus12. Alternatively, or in addition, the display processor13is connected to processor10by means of a separate data bus (not shown) The data bus may be a high-speed data bus, in case a large amount of information is to be transferred between the processor10and the display controller13. In this case, the data transfer on the separate data bus will not interfere with the data traffic on the ordinary data bus12.

A display memory15is connected to the data bus12and stores information sent from the processor10regarding the content that shall be drawn on the display14. The display memory15comprises e.g. a sample buffer for storing information, such as sample values of the rendered content, and a color buffer. The color buffer holds the pixel values generated, such as colors of the pixels to be displayed on the display14after the rendering of a previous image is completed. As with the interconnection between processor10and the display controller13, the display memory15may be connected directly to the display controller13by means of a separate, high-speed bus17, shown in phantom lines. The display memory15may also form part of the memory11. Since the display controller13and the display memory15normally are used for producing a continuous stream of images, it may be an advantage if the link between these two units is as fast as possible and does not block the normal traffic on the data bus12. The display memory may be connected by a separate high-speed bus17ato the processing device10a.

The display controller13may comprise a VDAC (Video Digital to Analog Converter), which reads the information from the display memory15and converts it to an analog signal, e.g. a RGB (Red, Green, Blue) composite signal that is provided to the display14in order to draw the individual pixels thereon.

The color buffer or frame buffer stored in the display memory15may store pixel information corresponding to a graphical image. The pixel information may be represented by a grid-like array of pixels where each pixel is assigned a color. The values in the color buffer may be represented as R, G, and B values corresponding to red color, green color, and blue color of the pixel making up a graphical image. The number of bits defining the R, G, and B values depends on the number of colors and shades to be represented. Further bits may be defined.

In processing the three-dimensional graphic object to be displayed, the depth attribute, or z-values at the sample positions inside the polygon, of the object must be considered prior to updating any value in the color buffer. If the new object being processed is located at least partly behind and at least partly obscured by a displayed content, only a visible portion of the new object should be drawn to the color and depth buffer. On the other hand, if the new object is completely obscured by already drawn content, there is no need to update the color buffer at all and the object is not drawn or rendered.

Three-dimensional objects may be represented by a set of vertices defining polygon surfaces. Each vertex is defined by x, y and z dimensions corresponding to the X, Y and Z axes. The X and Y axes define a view plane and the Z axis represents a scaled distance from the view plane to a viewer's origin. The z coordinate value indicates the depth of an object at a pixel location defined by specific x and y coordinates.

A depth buffer16for storing depth values is connected to the bus12. The depth buffer16may by provided as a stand-alone memory unit directly connected to the bus12or be an integral part of memory15. The depth buffer16provides a storage means, in which z-values or depth values of each pixel may be stored. When a new object should be drawn in a displayed portion of a view plane, a determination has to be made as to whether the new object will be visible and should be displayed, or whether the new object is hidden by content already displayed. As the z-values are stored in a depth buffer that may be located off-chip, a high-speed bus18(shown in phantom lines) may be provided between processing device10aand the depth buffer16, whereupon access to the depth buffer16does not interfere with other traffic on the bus12.

Processing device10amay comprise an integrated storage means19, such as an on-chip memory or a cache memory. The processing device10aand the storage means19may be provided on the same chip, thus not occupying any memory bandwidth of the bus12. The storage means19may store minimum region depth values and maximum regions depth values associated with each display region101(FIG. 3) of the display. Also, the storage means may store minimum subregion depth values and maximum subregion depth values for display subregions. If the processing device10ais a GPU, the storage means19may be an on-chip memory. If the processing device10ais a CPU, the storage means19may be either a cache memory or an on-chip memory.

FIG. 3illustrates a display100partitioned into a plurality of display regions101. In this embodiment, the display100comprises 10×10 display regions. However, the display may according to other embodiments be partitioned into any number of display regions101, even a single one. Each display region is partitioned into a plurality of display blocks102. Each display block may comprise one pixel. In this embodiment, each display region101comprises 8×8 display blocks. Alternative dimensions may e.g. be 4×4, 8×4, 16×4, 16×8 or 16×16. These dimensions are only examples and other embodiments could comprise any number of display blocks102within each display region101. If a display region with 8×8 display blocks are used, a screen with a resolution of 1024×768 pixels would comprise 123×96 display regions.

The minimum region depth value for a display region101represents a minimum of all the depth values of display blocks within said display region101. Correspondingly, the maximum region display value represents a maximum of all the depth values of display blocks102within said display region101.

InFIG. 3, a portion of a new triangle103is to be rendered in a specific display region104. Before the color and depth buffers are updated according to the potential influence of triangle103, it has to be tested whether the triangle103will be obscured by primitives already rendered into the display region104.

FIGS. 4a-4cillustrate various situations that could happen when an object, such as a triangle is rendered into a display region104. That part of a triangle that is located further away than at least a portion of another triangle is drawn with a dashed line.

InFIG. 4a, a first triangle120is displayed in a specific display region122. A second triangle121is then rendered in said specific display region122. The minimum region depth value, zminr, is the same as the minimum polygon depth value for the first triangle in that display region, and the maximum region depth value, zmaxr, is the same as the maximum polygon depth value for the first triangle in that display region. Assume the second triangle121is entirely located further away than the first triangle120. Consequently, zmin of the second triangle121is larger than zmax of the first triangle120and consequently larger than zmaxr. The first triangle120is the object, which is located closest to a viewer in said display region. By comparing zmin of the second triangle121with zmaxrof the display region it may be ascertained that the second triangle should definitely not overwrite any buffer values (e.g. z and color) for said specific display region122.

InFIG. 4b, a first triangle130is displayed in a specific display region132. A second triangle131is then rendered in said specific display region132. The minimum region depth value, zminr, is the same as zmin for the first triangle, and the maximum region depth value, zmaxr, is the same as zmax for the first triangle in the display region132. The second triangle131is located closer to the viewer than the first triangle130. Consequently, zmax of the second triangle131is smaller than zmin of the first triangle130and than zminr. Thus, by comparing zmax of the second triangle131with zminrof the display region it may be ascertained that the second triangle should definitely be rendered, and memory reads to the depth buffer can be completely avoided for said display region132, but the z-values of the polygon can be directly written to the depth buffer. Also, the storage means19should be updated, if needed, with new values of zminrand zmaxrcorresponding to zmin and/or zmax of the second triangle131.

InFIG. 4c, a first triangle140is displayed in a specific display region142. The minimum region depth value, zminris the same as zmin for the first triangle140, and the maximum region depth value, zmaxr, is the same as zmax for the first triangle140. A second triangle141is rendered in said specific display region142. The second triangle141is only partly located further away than the first triangle140in a way so that at least a portion of the first triangle141(marked with a solid line) is closer than the first triangle140, and at least one other portion of the second triangle141(marked with a dashed line) is farther away than the first triangle140. Consequently, zmin of the second triangle141is smaller than the zmaxrof the display region142, and/or zmax of the second triangle141is larger than zmaxrof the display region. Thus, only by comparing zmin and zmax of the second triangle141with zminrand/or zmaxrof the display region142, it may not be ascertained that the second triangle141should definitely be rendered or definitely not be rendered, and further processing is required, wherein it will be necessary to read the depth buffer16.

The values of zmin and zmax for the new triangles121,131,141may be calculated or estimated. Zmin and zmax may e.g. be determined as the zmin and zmax values of the vertices of the polygon. Alternatively, if the graphics primitive is a polygon, they can be estimated by evaluating the plane equation of the polygon at the corners of the display region, and then take the min and max of these values. Moreover, a combination of these techniques may be used. According to another embodiment, zmin and zmax for a new triangle are estimated by knowing the size of the display region and the slope of a border of the triangle within said display region. The values of zmin and zmax should be estimated conservatively.

It should be noted that the situations described inFIGS. 4a-4care only given for explanation purpose. Other situations may also occur, for example when the triangles are not overlapping. Also, other numbers of triangles within a display region are possible. Furthermore, each display block of a display region may relate to a different triangle.

When a definite answer with respect to the visibility of the new object cannot be given by region-wise comparing zmin and zmax of the new object with zminrand zmaxrof the display region, a similar comparison is made subregion-wise. If still no definite answer can be given, all z-values for the object within a specific display region may be generated. The z-value for each display block of the new triangle may be generated by perspective-correct interpolation of the z-values of the vertices.

Each z-value may be compared with at least one of zminsuband zmaxsubfor the subdisplay region, i.e. it is not necessary to compare the z-values with both zminsuband zmaxsub. Thus, it may be definitely determined, display block per display block, whether the depth buffer needs to be read or not for each z-value.

If the z-value of the polygon corresponding to a specific display block is smaller than zminrfor the display region, the depth buffer16does not need to be read, but it definitely needs to be written in order to update the depth buffer with the z-value corresponding to the specific display block for the new object. The depth buffer16can be updated without any further processing for that display block.

If the z-value of the polygon corresponding to the specific display block is larger than zmaxrfor the display region, the depth buffer16does definitely not need to be neither read from, nor written to, for that display block.

However, if the z-value of the polygon corresponding to the specific display block is between zminrand zmaxrfor the display region, no definite answer can be given. Then, the depth buffer16needs to be read in order to retrieve a stored z-value associated with the specific display block. The generated z-value for the specific display block is compared to the corresponding stored, and now retrieved, z-value. If the generated z-value is smaller than the corresponding stored z-value, the depth buffer is updated with the generated z-value. If the generated z-value is larger than the corresponding stored z-value, the depth buffer does not need to be updated.

It should be noted that other comparison operators may be used according to other embodiments, such as less or equal than, larger than, equal to, larger or equal to the corresponding stored z-value.

It is an advantage to compare not only zmin and zmax for the object but also each interpolated z-value for an object to zminsuband zmaxsubfor a subdisplay region, as reads to the depth buffer16may be avoided. Thus the utilized memory bandwidth may be even more decreased compared to only comparing zmin and zmax for the object.

FIG. 5illustrates a display region in cross-section, wherein display blocks are illustrated in the Y-axis and the relationship between depth values is indicated along the Z-axis. For illustrative purposes, the number of display blocks of one column of a display region is only four.

A first and a second object150,151have been rendered in the display region. Zmaxrfor the display region is the same as a maximum z-value for the first object150. Zminrfor the display region is the same as a minimum z-value for the first object150. A third object152is to be rendered in the display region. When obj-zminrand obj-zmaxrfor the third object are compared to zminrand zmaxrof the display region, no definite answer on the visibility of the third object152can be given, as obj-zmaxrfor the third object is between zminrand zmaxr. Therefore, obj-z-values at sample points153,154,155for the third object152are generated in each display block in the display region. By looking at the z-values at sample points153,154,155it may be determined that the z-value at sample point155is smaller than zminr, wherein the depth buffer need not be read for that display region. However, the value of zminris updated for sample point155. Sample points153and154are determined in each display block, whereby a read of the display buffer is required before it can be determined that sample point154should be rendered and sample point153should not be rendered.

Turning now toFIG. 8, there is shown a flow-chart of a method wherein minimum polygon depth values and maximum polygon depth values are compared with at least one of the minimum region depth value and the maximum region depth value.

When a new object is to be rendered the following procedure is performed with reference toFIG. 8.

In block200, obj-zminrand obj-zmaxrfor the new object are estimated in a specific display region.

In block201, zminrand zmaxrof a display region are retrieved from memory16,11or19.

In block202, obj-zmaxris compared to zminr.

If obj-zmaxris smaller than zminr, the object is entirely positioned in front of all other content already present at the display in the region and should definitely be rendered and the procedure follows the yes-line to block214a.

In block214a, a z-value for the new object in a display block included in the region is generated. In block215a, the z-buffer of the specific display block is updated with the new generated z-value. In block216a, it is determined if all display blocks in the specific region have been processed. If no, the procedure proceeds with the next display block as indicated in block217aand the procedure is returned to block214a. If yes, the procedure proceeds to block219, in which it is determined if all display regions have been processed, otherwise, the process proceeds to the next display region in block220and is returned to block200for the next region.

If in block202, obj-zmaxris larger than zminsub, the procedure follows the no-line to block203.

In block203, obj-zminris compared to zmaxr.

If obj-zminris larger than zmaxr, the object is entirely positioned behind any other object already present on the display and should definitely not be rendered and the procedure follows the yes-line to block219for the next region.

If obj-zminris smaller than zmaxsub, no firm conclusion can be drawn as to the rendering of the object and a further investigation is required, following the no-line to block204a.

In block204a, obj-zmaxsuband obj-minsubare determined for the object in a subregion.

In block204b, zmaxsuband zminsubare retrieved and/or calculated for the display subregion.

In block205, obj-zmaxsubis compared to zminsub.

If obj-zmaxsubis smaller than zminsub, the object is entirely positioned in front of all other objects already present at the display for the subregion and should definitely be rendered and the procedure follows the yes-line to block214b.

In block214b, a z-value for the new object in a display block included in the subregion is generated. In block215b, the z-buffer of the specific display block is updated with the new generated z-value. In block216b, it is determined if all display blocks in the specific subregion has been processed. If no, the procedure proceeds with the next display block as indicated in block217band the procedure is returned to block214b. If yes, the procedure proceeds to block213, in which it is determined if all display subregions have been processed, otherwise, the process proceeds to the next display subregion as indicated in block218and is returned to block204afor the next subregion.

If in block205, obj-zmaxsubis larger than zminsub, the procedure follows the no-line to block206.

In block206, obj-zminsubis compared to zmaxsub.

If obj-zminsubis larger than zmaxsub, the object is entirely positioned behind any other content already present on the display and should definitely not be rendered and the procedure follows the yes-line to block213for the next subregion.

If obj-zminsubis smaller than zmaxsub, no firm conclusion can be drawn as to the rendering of the object and a further investigation is required, following the no-line to block207.

In block207, the z-value of the new object is generated for a specific display block.

In block218, the z-value of the object is compared to zminsub.

If the z-value is smaller than zminsub, the object is positioned in front of any content already present in the display block and should definitely be rendered and the procedure follows the yes-line to block212.

If in block218, the z-value is larger than zminsub, the procedure follows the no-line to block219.

In block219, the z-value is compared to zmaxsub.

If the z-value is larger than zmaxsub, the object is entirely positioned behind any content already present in the display block and should definitely not be rendered and the procedure follows the yes-line to block210for the next display block.

If the z-value is smaller than zmaxsub, no firm conclusion can be drawn as to the rendering of the object and a further investigation is required, following the no-line to block208.

In block208, the stored z-value is retrieved from the memory for the specific display block.

In block209, the generated z-value for the object is compared with the stored and retrieved z-value.

If the generated z-value is larger than the stored z-value, the new object is behind the previous content and should not be rendered in the specific display block and the procedure follows the no-line to block210.

In block210, it is determined if all display blocks have been processed. If not, the procedure proceeds to the next display block as indicated in block211, and the procedure proceeds to block207.

If all display blocks have been processed, the procedure proceeds to block213for the next subregion.

If in block209the generated z-value is smaller than the stored z-value, the new object should be rendered in the specific display block and the procedure follows the yes-line to block212.

In block212, the z-buffer for that display block is updated and the procedure proceeds to block210for any new display block.

When all display subregions have been processed, as determined in block213, the procedure proceeds to block219.

In block219, it is determined if all display regions have been processed. If yes, the procedure ends.

It is noted that the information in the color buffer may be updated at the same time as the z-buffer is updated. Alternatively, the color buffer is updated at a later time. This may be the case if several polygons are to be rendered, whereby the color buffer is updated when several or all polygons have been processed according to the invention.

According to a further embodiment, it is possible to increase the resolution of zminrand zmaxrof the display region. With smaller display regions the culling can be made more accurate. However, the on-chip storage requirements increase with decreased display regions, or if a cache is used to access zminr/zmaxrthen that cache will access the memory11more frequently. The former incurs a large cost in chip area, and the latter is counterproductive in terms of bandwidth usage. For example, moving from a display region size of 8×8 display blocks to a display region size of 4×4 display blocks will in general cost 4 times as much in terms of bandwidth usage and memory requirements.

According to one embodiment, a rather inexpensive solution to this problem is provided. Assume that a display region size of p×p display blocks is used. In order to increase performance it would be nice to use a display region size of p/2×p/2 display blocks, but increasing the on-chip memory cost by a factor of four is undesirable. Below, a p×p display region is called a display region and a p/2×p/2 display region is called a display subregion.

FIG. 7illustrates a display region250comprising four display subregions251,252,253,254. Each display subregion comprises 4×4 display blocks.

Zminrand zmaxrare stored in the storage means19for the entire display region250. A minimum subregion depth value, zminsuband a maximum subregion depth value, zmaxsub, for each subregion region251,252,253,254are known to lie in the range of zminrand zmaxrfor the display region. Therefore, according to one embodiment, zminsuband zmaxsubare associated with zminrand zmaxr. Zminsuband zmaxsubmay be determined relative to zminrand zmaxrfor the display region. Zminsuband zmaxsubmay be stored in the storage means19together with zminrand zmaxrfor the display region. Thus, when a new object is to be rendered, a comparison can be made between determined zmin and zmax for the new object and at least one of zminsuband zmaxsubfor each display subregion. If no general determination on visibility can be made on the first comparison, each generated z-value can be compared with zminsuband/or zmaxsub. Also, the determined zmin and/or zmax for the polygon to be rendered may be compared with zminrand/or zmaxrif this is desired.

Zminsubmay be determined such that it is larger than or equal to zminrand zmaxsubmay be determined such that it is smaller than or equal zmaxr.

Of course, zminsuband zmaxsubmay be determined as the true minimum and maximum values of the depth values in the subregion.

Alternatively, zminsubis determined such that it is smaller than or equal to all stored depth values for said specific subregion and zmaxsubmay be determined such that it is larger than or equal to all stored depth values for said specific subregion.

m being the number of bits used for encoding zminsuband n being the number of bits used for encoding zmaxsubper display subregion. m and n are integers larger or equal to one.

If m=n=2, a division by three will be performed, which comes from the fact that 2 bits were used for encoding zminsuband zmaxsub; 22−1=3. The division by three also entails that the possible values between and including zminrand zmaxrare evenly distributed. Zminsuband zmaxsubcan take any of the possible values, including zminrand zmaxr.

From a hardware perspective, the division by an odd number is undesirable as the hardware becomes more complicated. To take care of this problem, the following algorithm for determining zminsuband zmaxsubmay be used instead:
zminsub=zminr+(zmaxr−zminr)*k/2m, where k is in [0, 1, 2, . . . , 2n−1],
zmaxsub=zmaxr+(zminr−zmaxr)*s/2n, where s is in [0, 1, 2, . . . , 2n−1],

In this embodiment, the value of the zminsubis larger than or equal to zminrand smaller than the zmaxr. The value of zmaxsubis larger than zminrand smaller than or equal to zmaxr. This means that zminsubcannot store the value of zmaxr, and zmaxsubcannot store the value of zminr. However, it is unlikely that this situation will occur often as one of zminsuband zmaxsubalways can store zminror zmaxr. Furthermore, as long as every zmin, zmax, zminsub, zmaxsub, zminrand zmaxrare encoded conservatively, i.e. the nearest possible lower value for zminsuband the nearest possible higher value for zmaxsub, even if another higher value is closer, the rendering will still be correct.

Other distributions of possible values for zminsuband zmaxsubbetween zminrand zmaxrare also possible. For example, more possible values may be provided closer to zminrthan to zmaxr, or vice versa, or within a certain range between zminrand zmaxr. The actual distribution may be tested in each specific case.

Thus, the values of zmaxrand zminrare stored in any desired resolution with a corresponding number of bits. The values of zmaxsuband zminsubare stored as the k-number and s-number indicated in the equations above, with n bits.

FIG. 6illustrates a display region in cross-section, wherein display blocks are illustrated along the Y-axis and the relationship between depth values is indicated in the Z-axis. For illustrative purposes, the number of display blocks of one column of the display subregion is only four. Zminrand zmaxrfor each display region, and zminsuband zmaxsubfor the display subregion are indicated. Z-values270,271,272,273, are indicated which have been generated for a new object to be rendered in the display blocks of the display subregion.

By comparing either zmin/zmax, or each generated z-value270,271,272,273for the new object, with zminrand zmaxra definite answer on visibility will not be given, as said generated z-values are in the range defined by zminrand zmaxr. Furthermore, comparing zmin/zmax for the new object will give the answer that the depth buffer16needs to be read, as zmin for the new object is smaller than zmaxrand zmax for the new object is larger than zminr. By comparing the generated z-values270,271,272,273with zminsuband zmaxsubit can be determined that z-value270is larger than zmaxsuband definitely will be covered by content previously drawn in that display subregion when rendered, and there is no need to update the depth buffer16for this subregion block. Z-values271and272are larger than zminsuband smaller than zmaxsub. Consequently, the depth buffer16has to be read to retrieve the stored z-values for the display blocks corresponding to z-value271and272. Z-value273is smaller than zminsub, wherein it may be determined that no object will cover the new object in this display block when rendered, and the depth buffer16may be updated for this display block without being read.

As is apparent from above, using encoded zminsuband zmaxsubrelative to zminrand zmaxr, has the advantage that even further depth buffer read may be avoided. In the example described above, two depth buffer read out of four were avoided.

In another embodiments, a minimum polygon and/or a maximum polygon depth value for a display subregion or a polygon depth value may be compared against a combination of the minimum subregion depth value, the maximum subregion depth value, the minimum region depth value, and/or the maximum region depth value.

In still another embodiment, zminsubfor the display subregion is first determined relative to zminrand zmaxrof the display region. Then, zmaxsubis encoded relative to said determined zminsubfor the display subregion and zmaxrfor the display region. Alternatively, zmaxsubfor the display subregion is first determined relative to zminrand zmaxrfor the display region and then zminsubfor said display subregion is determined relative to zminrfor the display region and said determined zmaxsubfor the display subregion. Zminsuband zmaxsubcan be generated by determining zmin and zmax of all z-values within a display subregion, and then determine zminsuband zmaxsubas described above.

InFIG. 9, another embodiment of the procedure is shown.

The procedure starts in block300.

In block302, it is determined if obj-zmaxris smaller than zminr, in which case the new object is in front of any previous content in the display region.

If yes in block302, the object is rendered in the entire region as shown in block316. In block317it is determined if all regions are processed. If this is the case, the procedure ends in block318, else a new display region is processed returning to block301.

If no in block302, the procedure proceeds to block303, where it is determined if obj-zminris larger than zmaxr, in which case the new object is behind any previous objects in the display region.

If yes in block303, the object should not be rendered as indicated in block319and the procedure proceeds to block317where it is determined if all regions are processed as indicated above. Block317is also shown on another place inFIG. 9, but that is only for making the procedure more easy to understand. The procedure is the same in each block labeled with the same reference number.

If no in block303, no firm decision can be taken as to the rendering of the object in the region and the procedure proceeds to block304.

In block305, it is determined if obj-zmaxsubis smaller than zminrwhich already has been retrieved in block301and is available without any further action.

If yes in block305, the object is rendered in the entire subregion as shown in block320. In block321it is determined if all subregions are processed. If this is the case, the procedure proceeds to block317for the next region. Otherwise the procedure is returned to block304for a new subregion.

If no in block305, the procedure proceeds to block306, where it is determined if obj-zminsubis larger than zmaxr, in which case the new object is behind any previous objects in the subregion. Zmaxris already available.

If yes in block306, the object should not be rendered as indicated in block324.

If no in block306, the procedure proceeds to block307, where zmaxsuband zminsubfor a display subregion is retrieved and/or calculated from memory.

In block308, it is determined if obj-zmaxsubis smaller than zmaxsub, in which case the object is in front of any previous content in the entire subregion.

If yes in block308, the object is rendered in the entire subregion as shown in block320.

If no in block308, the procedure proceeds to block309, where it is determined if obj-zminsubis larger than zmaxsub, in which case the new object is behind any previous content in the display subregion.

If yes in block309, the object should not be rendered as indicated in block324.

If no in block309, no firm decision can be taken as to the rendering of the object in the subregion and the procedure proceeds to block310.

In block310, the z-value of the object in the display block is determined.

In block311, it is determined if the z-value of the object is smaller than zminsubwhich already has been retrieved in block307and is available without any further action.

If yes in block311, the object is rendered in the display block as shown in block322. In block323it is determined if all display blocks are processed. If this is the case, the procedure proceeds to block321for the next subregion. Otherwise the procedure is returned to block310for a new display block.

If no in block311, the procedure proceeds to block312, where it is determined if the z-value is larger than zmaxsub, in which case the new object is behind any previous content in the subregion. Zmaxsubis already available.

If yes in block312, the object should not be rendered as indicated in block325.

If no in block312, the procedure proceeds to block313, where z-stored for a display block is retrieved from memory.

In block314, it is determined-if the z-value is smaller than z-stored, in which case the object is in front of any other content in the display block.

If yes in block314, the object is rendered in the display block as shown in block322.

If no in block314, the procedure proceeds to block325.

InFIG. 9, five steps are disclosed, including blocks302,303;305,306;308,309;311,312; and314,315. The different steps can be performed in other combinations than what is shown inFIG. 9. For example, step302,303, step305,306and step311,312may be optional. All three, two, one or none of these steps may be used. Moreover, it is not always necessary to use both blocks308and309, while it still is an advantage to use only one of these two blocks. The same is true for all combinations of two blocks in each step.

The blocks319,324,325, “don't render”, involves that a read of the z-buffer and/or display subregion and region values are not required, which means a saving.

The blocks316,320and322involves that the z-buffer is updated without first being read, which also means a saving. The procedure may be as described in relation toFIG. 8.

The display subregions may have any size, such as p×q display blocks, where p>=1 and q>=1. Also, any number of bits may be used for encoding zminsuband zmaxsub. Assuming that 2×2 display blocks are used for each display subregion and that 2 bits are used for storing each relative position for each of zminsuband zmaxsub, the cost is (2*2)*(2+2)=16 bits per display region. Furthermore, assuming that zminrand zmaxrare stored in 16 bits each, it is obvious that the scheme according to this embodiment is more effective than the prior art. For example, going from 32 bits per display region (16+16 bits for zminr+zmaxr) to a display region size of [n/2]×[n/2] would cost 32*4=128 bits with a standard prior art scheme. The scheme according to this embodiment would cost 48 bits (16+16+16 bits for zminr+zmaxr+relative position bits).

In one embodiment, at least one of the zminrand zmaxrfor the display blocks of at least one display region is determined. Either or both zminrand zmaxris determined. Thus, also only one of zminsubor zmaxsubfor the display blocks of at least one display subregion needs to be determined. However, if both zminrand zmaxrare determined both zminsuband zmaxsubare determined. This embodiment may e.g. be used if either of zmaxsubor zminsubvalues is not used.

Zminsubmay be determined relative to at least zminr. Zmaxsubmay be determined relative to at least zmaxr.

Imagine a display region having 4 display subregions A, B, C, D. Each subregion A, B, C, D has a minimum subregion depth value zminsub_A, zminsub_B, zminsub_C, and zminsub_D, respectively. For each display region, two minimum depth values zmin_1and zmin_2are determined and stored. Zmin_1may be determined as min[zminsub_A, zminsub_B, zminsub_C, zminsub_D]. Thus, zmin_1may be determined as zminrfor the display region. Zmin_2is a value equal to or higher than zmin_1. For example, zmin_2may be determined as (zmin_1+max[zminsub_A, zminsub_B, zminsub_C, zminsub_D])/2. Another example is to take the second largest value of [zminsub_A, zminsub_B, zminsub_C, zminsub_D] as the value for zmin_2. Each subregion depth value may be determined relative zmin_1, i.e. relative zminr. A bit value zminsub_bit may be used (set or cleared) for each subregion. If zminsubfor a specific subregion is smaller than zmin_2, the zminsubbit for said specific subregion is set to a first value, such as 0. If zminsubfor a specific subregion is larger than or equal to zmin_2, the zminsubbit for said specific subregion is set to a second value, such as 1. The first value references to zmin_1and the second value references to zmin_2. A correct or conservative representation is in this way assured, since the encoded value will be equal to or smaller than the real value. Thus the minimum subregion depth value will be represented by either zmin_1or zmin_2during rendering. The values of zmin_1, zmin_2, and zminsub_bit for each subregion of the display region are stored. Zmin_1and zmin_2may be stored using a first number of bits, such as 16 bits for each value. The zminsub_bit values may be stored using a single bit for each value.

In another embodiment, zmin_1is determined as described above, while zmin_2is chosen as a number that is equal to or larger than zmin_1, for instance, the maximum of all the individual depth values of the display blocks (pixels) in the display region. To increase the resolution of the subregion depth values, a display region depth value interval is determined, for example the interval [zmin_1, zmin_2−1], having zmin_1and zmin_2−1 as the end values of the interval. The interval is split into 2Nsubintervals. N bits are used to store the bit value for each sub region. When encoding zminsub, the subinterval containing zminsubis chosen, and the lowest value in a subinterval is used to provide conservative encoding.

Zminsubmay be determined using, for instance, the following formula: zminsub=zmin_1+(zmin_2−zmin_1)*k/(2N). k equals the zminsub_bit-value, and is thus in the range 0, 1, . . . , 2N−1. In the example, N=3 and k=4, giving 4*(256−128)/23+128=192.

In an alternative embodiment, the main interval can be [zmin_1, zmin_2], and it can be divided in a different manner, so that zminsubinstead will be calculated the formula zminsub=zmin_1+(zmin_2−zmin_1)*k/(2N−1), where k=0, 1, . . . , 2N−1. However, these two formulas are only examples and the starting values for the sub intervals may be calculated in alternative ways.

What has been described above with reference to zmin_1and zmin_2is also applicable for zmax values. Thus, zmax_1and zmax_2values may be determined in a corresponding manner, and thus encoding zmaxsubin a corresponding manner. Thus, one of zmax_1and zmax_2will be determined at least relative zmaxr. Also zminsuband zmaxsubvalues that are stored are thus represented by the bit values. As is apparent from the above, zmin_1may be equal to zmaxr. Zmin_2may be larger than or equal to zmin_1. Similarly, zmax_2may be equal to zmaxr. Zmax_ may be smaller than or equal to zmax_2.

Zmax_2can then be calculated as max[zmaxsub_A, zmaxsub_B, zmaxsub_C, zmaxsub_D], and zmax_1can be chosen to be a value that is equal to or smaller than zmax_2. For instance, zmax_2may be calculated as the minimum of the depth values of the individual display elements blocks in the display region. Furthermore, the interval [zmax_1+1, zmax_2] may then be divided into 2Nsub intervals, and the end values of these intervals may be used as zmaxsub. For instance, zmaxsubmay be calculated using the formula zmaxsub=zmax_2+(zmin_1−zmin_2)*k/(2N), where k equals the zmaxsub_bit, and is thus in the range 0, 1, . . . , 2N−1. Alternatively, the interval could be [zmax_1, zmax_2], and the endpoints could be calculated as zmaxsub=zmax_2+(zmin_1−zmin_2)*k/(2N−1), where k=0, 1, . . . , 2N−1. zmax_2=zmaxr, zmax_2≧zmax_1. However, these two formulas are only examples and the end values for the sub intervals could be calculated in alternative ways.

Compared to traditional zmin/zmax techniques, combining the step of comparing a depth value of the polygon with the zminrand zmaxrof the display region with the step of splitting the display region into display subregions with associated coding of more accurate zminsuband zmaxsubresults in significant savings in terms of depth buffer reads. The savings can give 1.6-2.9 times fewer depth buffer reads compared to traditional zmin/zmax techniques. For a game scene, this can entail that up to 40,000 unnecessary depth buffer reads are avoided per frame. Put it in another way, about 40% of the depth buffer reads are avoided. At 30 Hz (images per second), this gives 1.2 millions fewer memory accesses per second.

The present invention has been described above with reference to specific embodiments. However, other embodiments than the above described are possible within the scope of the invention. Different method steps than those described above, performing the method by hardware or software, may be provided within the scope of the invention. The different features and steps of the invention may be combined in other combinations than those described. The scope of the invention is only limited by the appended patent claims.