Iteration over all Positions in Region

ker · **Posted:** Fri Dec 30, 2011 5:19 pm

I have about 20 pieces of code surronded by

Code:

for(int32_t x = reg.getLowerCorner().getX(); x < reg.getUpperCorner().getX(); x++) {
    for(int32_t y = reg.getLowerCorner().getY(); y < reg.getUpperCorner().getY(); y++) {
        for(int32_t z = reg.getLowerCorner().getZ(); z < reg.getUpperCorner().getZ(); z++) {
            somevolume.setVoxelAt(x, y, z, voxel);
            // code here
        }
    }
}

I got annoyed with that

Anyone who is sharing my annoyance and uses c++11 might enjoy the following...

Code:

for(PolyVox::Position3DInt pos:RegionWrap(reg)) {
    somevolume.setVoxelAt(pos, voxel);
    // code here
}

all you need is a small object that implements the standard library input iterator interface

Code:

#include <iterator>
#include <PolyVoxCore/PolyVoxCore/Vector.h>
#include <PolyVoxCore/PolyVoxCore/Region.h>

class RegionIterator : public std::iterator<std::input_iterator_tag, PolyVox::Vector3DInt32>
{
  PolyVox::Vector3DInt32 m_Pos;
  const PolyVox::Region& m_Reg;
public:
  RegionIterator(PolyVox::Region& reg, PolyVox::Vector3DInt32 pos) :m_Pos(pos),m_Reg(reg) {}
  RegionIterator(const RegionIterator& other) : m_Pos(other.m_Pos), m_Reg(other.m_Reg) {}
  RegionIterator& operator++()
  {
      if(m_Pos.getX() == m_Reg.getUpperCorner().getX()) {
          m_Pos.setX(m_Reg.getLowerCorner().getX());
          if(m_Pos.getY() == m_Reg.getUpperCorner().getY()) {
              m_Pos.setY(m_Reg.getLowerCorner().getY());
              if(m_Pos.getZ() == m_Reg.getUpperCorner().getZ() || m_Pos.getZ() == (std::numeric_limits<int32_t>::max)()) {
                  const int32_t maximum = (std::numeric_limits<int32_t>::max)();
                  m_Pos.setElements(maximum, maximum, maximum);
              } else {
                  m_Pos.setZ(m_Pos.getZ() + 1);
              }
          } else {
              m_Pos.setY(m_Pos.getY() + 1);
          }
      } else {
          m_Pos.setX(m_Pos.getX() + 1);
      }
      return *this;
  }
  
  RegionIterator operator++(int) {RegionIterator tmp(*this); operator++(); return tmp;}
  bool operator==(const RegionIterator& rhs) {return (m_Pos==rhs.m_Pos)&&(m_Reg == rhs.m_Reg);}
  bool operator!=(const RegionIterator& rhs) {return (m_Pos!=rhs.m_Pos)||(m_Reg != rhs.m_Reg);}
  PolyVox::Vector3DInt32 operator*() {return m_Pos;}
};


struct RegionWrap
{
    typedef RegionIterator iterator;
    PolyVox::Region reg;
    RegionWrap(PolyVox::Vector3DInt32 l, PolyVox::Vector3DInt32 u)
    :reg(l, u) {}
    RegionWrap(PolyVox::Region reg)
    :reg(reg) {}
    RegionIterator end() {
        int32_t maximum = (std::numeric_limits<int32_t>::max)();
        return RegionIterator(reg, PolyVox::Vector3DInt32(maximum, maximum, maximum));
    }
    RegionIterator begin() { return RegionIterator(reg, reg.getLowerCorner()); }
};

I'm planning on creating Volume read/write iterator through VolumeSampler,
but currently this is enough, as it increases readability a lot imo.

I didn't do any performance tests yet, but it should not really be slower than the first version.

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

Very good, the idea of iterators makes a lot of sense. A few months ago I added write access (setVoxel(...)) to the existing samplers for the same reason (though thre are some issues here). I've also started referring to them as iterators in the code and I need to unify this. There is a very basic test in LowPassFilter.inl:

Code:

do
{
   float previousSum = satVolumeIter.peekVoxel1nx0py0pz();

   float currentVal = static_cast<float>(srcVolumeIter.getVoxel().getDensity());

   satVolumeIter.setVoxel(previousSum + currentVal);

   srcIterCont.moveForward(); 

}while(satIterCont.moveForward());

The current interface is completely temporary, but my motivation was the same as yours in that I have lots of triple-nested loops operating over the whole volume.

However, I didn't add any kind of STL compatibility and it does seem like this could be beneficial. Even if we don't add it directly (as it requires C++11?) we should at least make sure that it is easy to wrap a PolyVox iterator in an STL one. That way your wrapper can probably be even simpler than what you show above.

ker · **Posted:** Sat Dec 31, 2011 11:45 am

the only c++11 thing is the

Code:

for(type varname:arrayname) {}

you can easily use my Wrapper with c++03:

Code:

RegionWrap regwrap(reg);
for(RegionWrap::iterator it = regwrap.begin(); it != regwrap.end(); it++)
{
    //conquer the world
}

Quote:

satIterCont.moveForward()

this seems like a feature that was added silently

Maybe I should check polyvox for new features first before I implement sth ^^

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

ker wrote:

the only c++11 thing is the

Code:

for(type varname:arrayname) {}

you can easily use my Wrapper with c++03:

Code:

RegionWrap regwrap(reg);
for(RegionWrap::iterator it = regwrap.begin(); it != regwrap.end(); it++)
{
    //conquer the world
}

Right, I've got you. Well I do think that STL compatibility should be kept in mind when thinking how these iterators should work.

ker wrote:

Quote:

satIterCont.moveForward()

this seems like a feature that was added silently

Maybe I should check polyvox for new features first before I implement sth ^^

It was really just an experiment to see how such a feature might look... it's probably buggy and can undergo interface changes (perhaps towards STL, as suggested). It also added the idea of an 'IteratorController' so that maybe users can choose to traverse along a Hilbert curve (for cache efficiency) or on a block-by-block basis within a region (to minimise compression/paging times).
But I didn't really work out whether any of this made sense before I got sidetracked, so your ideas are also welcome :-)

ker · **Posted:** Mon Jan 02, 2012 2:28 pm

I don't quite get how the Hilbert curve might aid cache usage... would't simply running along the axis in zyx order perfectly follow the array as it is in memory?

Well, for iterators like mine (that return Vectors which may then be used as wished), processing by Blocks would be rather simple. They'd only need to get the Block size from the Volume.

For iterators that can access the volume through VolumeSampler everything might get a little messier, as someone might use get/setVoxelAt and compress block containing the voxel which the iterator points at in that moment.

Also, have you done any performance tests of looping over coordinates and using get/setVoxelAt against using VolumeSampler?

Oh, and could you add .inl files to the permitted attachements?
I split the iterator into .hpp and .inl and the forum does not like the latter.

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

ker wrote:

I don't quite get how the Hilbert curve might aid cache usage... would't simply running along the axis in zyx order perfectly follow the array as it is in memory?

Sorry, yes, I think you are right. I had Hilbert curves on my mind as I'd been thinking of storing the data in Hilbert curve order to improve compression. Again, something that is completely untested ;-)

ker wrote:

Well, for iterators like mine (that return Vectors which may then be used as wished), processing by Blocks would be rather simple. They'd only need to get the Block size from the Volume.

Yep, and I'd still say that this was useful (especially for the LargeVolume). I can imagine that in the future we might want something like an octree volume (or at least we shouldn't rule it out) so I guess there could be an iterator for each volume type, so that it knows how the data is stored. Perhaps a default iterator as well.

ker wrote:

For iterators that can access the volume through VolumeSampler everything might get a little messier, as someone might use get/setVoxelAt and compress block containing the voxel which the iterator points at in that moment.

Right, this is a problem with using the sampler with LargeVolume at the moment. We've mentioned this previously of course, but even if the sampler is read only it can still lose it's data if other operations on the volume cause the sampler's current block to become compressed. This is on my list of known problems to be thought about, though it seems no one has encountered it.

If you don't find any performance problems you might find it easiest to just access the volume directly. But I can still imagine that once the samplers are improved so that they do have write access then there won't be a need for a separate iterator class (we can make the samplers implement std::iterator?).

ker wrote:

Also, have you done any performance tests of looping over coordinates and using get/setVoxelAt against using VolumeSampler?

I did see benefits of using the VolumeSampler when implementing the new cubic surface extractor. The profiler actually showed getVoxelAt() being the bottleneck and using the sampler fixed this. However, a lot more testing should be done.

But it's imporant to realise that pointing the iterator at a voxel and then reading it's value is no faster than accessing the voxel directly with getVoxelAt(). The real performance benefit of the sampler occurs when:

You can position the sampler using one of the 'move' functions, as these should be faster than calling setPosition().
You need access to the neighbours and can get this through the 'peek' functions. This happens a lot in PolyVox when performing surface extraction and normal calculation. A good test for this could be code which blurs the volume, by averaging each voxel with it's neighbours.

ker wrote:

Oh, and could you add .inl files to the permitted attachements?
I split the iterator into .hpp and .inl and the forum does not like the latter.

It looks like Matt has fixed this for you, try it again.

Iteration over all Positions in Region

Who is online