# Image-Space coherence of the z-buffer algorithm

I'm reading Hierarchical z-Buffer Visibility by Ned Greene et al. and they state that

traditional Z buffering makes reasonably good use of image-space coherence in the course of scan conversion.

I don't see how the z-buffer algorithm that I know makes use of image-space coherence at all. In the paper, they state that

implementations usually do a set-up computation for each polygon and then an incremental update for each pixel in the polygon.

How exactly is this "set-up computation" and "incremental update" defined?

• You might try asking on this on e.g. the opengl.org forums. – Engineer Mar 23 '16 at 11:56
• @ArcaneEngineer I don't think that this a question of a specific implementation (I suppose your advice is motivated by the "implementations usually ..." part), but of algorithm design. – 0xbadf00d Mar 23 '16 at 12:24
• In truth it would probably be speculation on the part of most here to give you a straight answer on what are, at the end of the day, hardware-specific implementation details, yes. The same is true of the "scan conversion" part. But maybe here someone will know. I'm just trying to help you accelerate your search. – Engineer Mar 23 '16 at 13:10
• @ArcaneEngineer No offense to you, but I don't think that these are (hardware-specific) implementation details. Don't focus on the "implementations usually ..." part. I'm not interested in specific implementations. I just want to know in which sense the traditional z-buffer algorithm is image-space coherent and how we need to alter (abstractly) it in order to use "incremental updates". – 0xbadf00d Mar 23 '16 at 13:19
• You might have better luck on computergraphics.stackexchange.com – whn Mar 31 '18 at 17:39

It seems to me that the setup refers to calculating the the Z values (as these can be determined a polygon at a time, once per frame) & the update is comparing a pair of Z values to update the pixel color as needed.

In terms of implementation, I've always seen it presented in an interleaved fashion (much like your definition link), but conceptually, you can think of them as separate steps.

I would say the traditional Z-buffer algorithm is temporally coherent in image-space. That is to say that, frame by frame, given fine adjustments of camera position and orientation, you are likely to see a lot of similarities between temporally-adjacent frames (frame N and N+1, for example).

I remember reading about the concept some years ago, for accelerating global illumination and/or raytracing(?). Here is a source that discusses this as an optimisational approach.

• It's not merely time coherence, there is also a reasonably high probability that the adjacent scan-segments in succesive scanlines themselves also belong to the same polygones, but with slight displacements. So starting with a copy of the previous line could be a way to optimize memory operations. If the scene is rather static or slow moving you would have a stronger benefit. – StarShine May 7 '18 at 17:49
• You are indeed right about the ray tracing use of Z buffer for a more real time. In fact, if I get time, I can dig up a technical demo where the previous frames data is used to determine next frames ray tracing (and reuse the previous frame to refine the frame outcome). – ErnieDingo Aug 20 '18 at 3:09

The Z-Buffer algorithm itself does not use image-space coherence concept, it works exactly as we know. But the result of this algorith is quite coherent, which means that for any given pixel there's a big chance that neighboring pixels have similar value.

This property (image-space coherence) of Z-Buffer data makes it possible to use i.e. Quad-Tree to make some tests faster. (If you had noise in ZBuffer then there's no point in using QuadTree over such data).

So in short: The coherence of data coming from traditional Z-Buffer makes it reasonable to use Hierarchical Visibility tests.

I hope this answers your first question. For the second let's say you're writing your own ZBuffer and you want to add a feature of Hierarchical Visibility tests. You have a grid of Z values already and you add a QuadTree, which contains min/max values for each node. At start you initialize those structures as needed.

Then you render a pixel, you compute its Z and test it with latest Z value of this pixel. If it's visible you store the new Z value but you also need to update the Quad-Tree and this is the 'incremental update' part.

There are two possibilities that occurred to me: 1) Triangles meshes are typically supplied in one of strip, fan, or indexed triangle lists. Since the first two automatically imply adjacency of (at least some) triangles and the last is typically optimised to maximise vertex cache reuse, these will also result in considerable spatial coherence. This, in turn, allows Greene's hierarchical Z-buffer to be effective.

2) If we can take it as read that the polygon (read triangle) vertices have been projected into screen coordinates, then setup in this case is any of the processing that takes the 3 triangle vertices, $$\V_1, V_2, V_3\$$ (where each $$\V\$$ has components, $$$$X^{screen}, Y^{screen}, Z^{screen}, \$$ + inverse W,texture coordinates, RGB values etc$$$$\$$ and maps them to a per-pixel evaluation cooefficients.

In older systems that usually meant DDA values for walking along edges and then interpolating along the scan lines, but this gradually changed over to using 'half-plane' evaluation schemes which make parallel evaluation on multiple pixels feasible.

Assuming it is the latter, then for edge equations this can be achieved by computing the inverse/adjoint of a 3x3 matrix comprising a row of the 3 X values, a row of the Ys and a row of 1s. $$\begin{vmatrix} V_1^{xscreen}&V_2^{xscreen}&V_3^{xscreen}\\ V_1^{yscreen}&V_2^{yscreen}&V_3^{yscreen}\\ 1&1&1 \end{vmatrix}$$

Each row of the adjoint of the above give the coefficients of a 'edge equation' of the form $$\d_{edge}=a.X + b.Y + c\$$, which can be used for 'inside' tests.
(FWIW this would be a good question for https://computergraphics.stackexchange.com/ )