Logo Search packages:      
Sourcecode: blender version File versions  Download package

HierarchicalZbuffer.cpp

//----------------------------------------------------------------------------------------------
// Simple Hierarchical Zbuffer implementation for occlusion culling.
// Always square, side length must be a power of 2. To avoid having to check this,
// the contructor must be called with the log2 of the side length of the lowest main level.
// maximum possible sidelength is 32768 (maxlog2 == 15)
// It is not adapted yet to work with size != pow of 2.
//----------------------------------------------------------------------------------------------
// NOTE:
// Using a hierarchical zbuffer didn't seem to be of any advantage,
// it's slower (not by much though), but also uses more memory...
// So either I'm doing something wrong (not unlikely of course),
// or my implementation is not efficient enough...
// (recursion & all those overlap tests probably don't help)
// In any case, the code is still here if anyone knows how to do it better.
// Of course other occlusion culling methods might be more suitable.
// minor update: now a tiny bit faster than zbuf in some cases for high depth complexity,
// otherwise, for most scenes, still slower...
// (failed to make a non-recursive version sofar... code removed)

#include "HierarchicalZbuffer.h"
#include "Mathutil.h"

#include "QDRender.h"
__BEGIN_QDRENDER

HierarchicalZbuffer::HierarchicalZbuffer(unsigned int maxlog2)
{
      zLayer = 0;

      // maxlog2 must be < 16
      //assert(maxlog2<16)

      sideLen = 1 << maxlog2;
      levels = maxlog2+1;

      // allocate array of layers
      zLayer = new float*[levels];

      // size in bytes of all required levels combined
      totalSize = 0x55555555 & ((2 << (maxlog2 << 1)) - 1);
      // allocate the pyramid
      zLayer[0] = new float[totalSize];

      // from that, assign the next pointers to the individual layers
      unsigned int size = sideLen*sideLen;
      for (unsigned int i=1; i<levels; ++i) {
            zLayer[i] = zLayer[i-1] + size;
            size >>= 2;
      }
      // initialize all to maximum depth
      initLayers();
}

HierarchicalZbuffer::~HierarchicalZbuffer()
{
      if (zLayer) {
            // only need to delete zLayer[0];
            if (zLayer[0]) delete[] zLayer[0];
            delete[] zLayer;
      }
}

// initialize all layers
void HierarchicalZbuffer::initLayers()
{
      for (unsigned int i=0; i<totalSize; ++i)
            zLayer[0][i] = 1e10f;
}

//------------------------------------------------------------------------------
// Point Occlusion testing

// tests the hzbuf. at coord. (x, y), for points, only need to test main layer
bool HierarchicalZbuffer::pointOccluded(int x, int y, float zval) const
{
      if ((x<0) || (y<0) || (x>=sideLen) || (y>=sideLen)) return false;
      // if zval > z value at main level, occlusion is true
      return (zval > zLayer[0][x + (y << (levels-1))]);
}

// updates all layers for coord(x, y) (coord of main level)
void HierarchicalZbuffer::updatePoint(int x, int y, float zval)
{
      if ((x<0) || (y<0) || (x>=sideLen) || (y>=sideLen)) return;

      // update first layer
      int sl = levels-1;  // y mult. factor (as shift)
      zLayer[0][x + (y << sl)] = zval;

      // starting from second layer, test the maximum z value of previous level 2x2 sub square
      // to check if update needed for next level, continue until no more update needed
      for (unsigned int i=1; i<levels; ++i) {
            // x, y coords for next level
            x >>= 1;
            y >>= 1;
            // previous level 2x2 subsquare coords
            const int x1 = x << 1, y1 = y << 1,
                                          x2 = x1 + 1, y2 = y1 + 1, im = i-1;
            // max z of subsquare
            const float maxz = MAX4(zLayer[im][x1 + (y1 << sl)], zLayer[im][x2 + (y1 << sl)],
                                                                                    zLayer[im][x2 + (y2 << sl)], zLayer[im][x1 + (y2 << sl)]);
            // if no update needed in next layer (maximum did not change), nothing to do further
            if (sl!=0) sl--;
            if (maxz==zLayer[i][x + (y << sl)]) return;
            // otherwise update, and test next layer
            zLayer[i][x + (y << sl)] = maxz;
      }
}

//------------------------------------------------------------------------------
// (2D) Bound occlusion testing

bool HierarchicalZbuffer::bOcc(const Bound2D& b, float zval, int curlev, int cell) const
{
      if (zval >= zLayer[curlev][cell]) return true;

      // if max level reached, no occlusion
      if (--curlev < 0) return false;

      // check for overlap with child cells, recurse if so
      // 0 | 1
      // -----
      // 2 | 3

      // log2 width in new cell
      const int w = (levels - 1) - curlev;
      // log2 width in old cell, half new cell width
      const int hw = w - 1;
      // new cell start coords x, y = old cell x*2, y*2
      int x = (cell & ((1 << hw)-1)) << 1, y = (cell >> hw) << 1;

      // new cells (x,y), (x,y+1)
      const int c0 = x + (y << w), c2 = c0 + (1 << w);

      // current cell bound max width/height
      const int cbm = (1 << curlev) - 1;

      // cell 0, (x, y)
      int xmin = x << curlev, ymin = y << curlev;
      int xmax = xmin + cbm, ymax = ymin + cbm;
      if ((xmax >= b.xmin) && (b.xmax >= xmin) && (ymax >= b.ymin) && (b.ymax >= ymin))
            if (!bOcc(b, zval, curlev, c0)) return false;

      // cell 1, (x+1, y)
      xmin += cbm + 1;
      xmax = xmin + cbm;
      if ((xmax >= b.xmin) && (b.xmax >= xmin) && (ymax >= b.ymin) && (b.ymax >= ymin))
            if (!bOcc(b, zval, curlev, c0+1)) return false;

      // cell 3 (x+1, y+1)
      ymin += cbm + 1;
      ymax = ymin + cbm;
      if ((xmax >= b.xmin) && (b.xmax >= xmin) && (ymax >= b.ymin) && (b.ymax >= ymin))
            if (!bOcc(b, zval, curlev, c2+1)) return false;

      // cell 2 (x, y+1)
      xmin -= cbm + 1;
      xmax = xmin + cbm;
      if ((xmax >= b.xmin) && (b.xmax >= xmin) && (ymax >= b.ymin) && (b.ymax >= ymin))
            if (!bOcc(b, zval, curlev, c2)) return false;

      return true;
}

bool HierarchicalZbuffer::boundOccluded(const Bound2D &b, float zval) const
{
      return bOcc(b, zval, levels-1, 0);
}

__END_QDRENDER

Generated by  Doxygen 1.6.0   Back to index