Index: tests/testvolume.cpp =================================================================== --- tests/testvolume.cpp (revision 1406) +++ tests/testvolume.cpp (working copy) @@ -29,26 +29,4 @@ using namespace PolyVox; -void TestVolume::testSize() -{ - const uint16_t g_uVolumeSideLength = 128; - Volume volData(g_uVolumeSideLength, g_uVolumeSideLength, g_uVolumeSideLength); - - //Note: Deliberatly go past each edge by one to test if the bounds checking works. - for (uint16_t z = 0; z < g_uVolumeSideLength + 1; z++) - { - for (uint16_t y = 0; y < g_uVolumeSideLength + 1; y++) - { - for (uint16_t x = 0; x < g_uVolumeSideLength + 1; x++) - { - volData.setVoxelAt(x,y,z,255); - } - } - } - - QCOMPARE(volData.getWidth(), g_uVolumeSideLength); - QCOMPARE(volData.getHeight(), g_uVolumeSideLength); - QCOMPARE(volData.getDepth(), g_uVolumeSideLength); -} - QTEST_MAIN(TestVolume) Index: tests/testvolume.h =================================================================== --- tests/testvolume.h (revision 1406) +++ tests/testvolume.h (working copy) @@ -31,7 +31,6 @@ Q_OBJECT private slots: - void testSize(); }; #endif Index: library/PolyVoxCore/source/Region.cpp =================================================================== --- library/PolyVoxCore/source/Region.cpp (revision 1406) +++ library/PolyVoxCore/source/Region.cpp (working copy) @@ -31,28 +31,28 @@ { } - Region::Region(const Vector3DInt16& v3dLowerCorner, const Vector3DInt16& v3dUpperCorner) + Region::Region(const Vector3DInt32& v3dLowerCorner, const Vector3DInt32& v3dUpperCorner) :m_v3dLowerCorner(v3dLowerCorner) ,m_v3dUpperCorner(v3dUpperCorner) { } - const Vector3DInt16& Region::getLowerCorner(void) const + const Vector3DInt32& Region::getLowerCorner(void) const { return m_v3dLowerCorner; } - const Vector3DInt16& Region::getUpperCorner(void) const + const Vector3DInt32& Region::getUpperCorner(void) const { return m_v3dUpperCorner; } - void Region::setLowerCorner(const Vector3DInt16& v3dLowerCorner) + void Region::setLowerCorner(const Vector3DInt32& v3dLowerCorner) { m_v3dLowerCorner = v3dLowerCorner; } - void Region::setUpperCorner(const Vector3DInt16& v3dUpperCorner) + void Region::setUpperCorner(const Vector3DInt32& v3dUpperCorner) { m_v3dUpperCorner = v3dUpperCorner; } @@ -67,7 +67,7 @@ && (pos.getZ() >= m_v3dLowerCorner.getZ() + boundary); } - bool Region::containsPoint(const Vector3DInt16& pos, uint8_t boundary) const + bool Region::containsPoint(const Vector3DInt32& pos, uint8_t boundary) const { return (pos.getX() <= m_v3dUpperCorner.getX() - boundary) && (pos.getY() <= m_v3dUpperCorner.getY() - boundary) @@ -87,38 +87,38 @@ m_v3dUpperCorner.setZ((std::min)(m_v3dUpperCorner.getZ(), other.m_v3dUpperCorner.getZ())); } - int16_t Region::depth(void) const + int32_t Region::depth(void) const { return m_v3dUpperCorner.getZ() - m_v3dLowerCorner.getZ(); } - int16_t Region::height(void) const + int32_t Region::height(void) const { return m_v3dUpperCorner.getY() - m_v3dLowerCorner.getY(); } - void Region::shift(const Vector3DInt16& amount) + void Region::shift(const Vector3DInt32& amount) { m_v3dLowerCorner += amount; m_v3dUpperCorner += amount; } - void Region::shiftLowerCorner(const Vector3DInt16& amount) + void Region::shiftLowerCorner(const Vector3DInt32& amount) { m_v3dLowerCorner += amount; } - void Region::shiftUpperCorner(const Vector3DInt16& amount) + void Region::shiftUpperCorner(const Vector3DInt32& amount) { m_v3dUpperCorner += amount; } - Vector3DInt16 Region::dimensions(void) + Vector3DInt32 Region::dimensions(void) { return m_v3dUpperCorner - m_v3dLowerCorner; } - int16_t Region::width(void) const + int32_t Region::width(void) const { return m_v3dUpperCorner.getX() - m_v3dLowerCorner.getX(); } Index: library/PolyVoxCore/source/VoxelFilters.cpp =================================================================== --- library/PolyVoxCore/source/VoxelFilters.cpp (revision 1406) +++ library/PolyVoxCore/source/VoxelFilters.cpp (working copy) @@ -32,9 +32,6 @@ assert(volIter.getPosX() >= 1); assert(volIter.getPosY() >= 1); assert(volIter.getPosZ() >= 1); - assert(volIter.getPosX() <= volIter.getVolume()->getWidth() - 2); - assert(volIter.getPosY() <= volIter.getVolume()->getHeight() - 2); - assert(volIter.getPosZ() <= volIter.getVolume()->getDepth() - 2); float sum = 0.0; Index: library/PolyVoxCore/source/GradientEstimators.cpp =================================================================== --- library/PolyVoxCore/source/GradientEstimators.cpp (revision 1406) +++ library/PolyVoxCore/source/GradientEstimators.cpp (working copy) @@ -42,10 +42,9 @@ VolumeSampler volIter(volumeData); //Check all corners are within the volume, allowing a boundary for gradient estimation - bool lowerCornerInside = volumeData->getEnclosingRegion().containsPoint(v3dFloor,2); - bool upperCornerInside = volumeData->getEnclosingRegion().containsPoint(v3dFloor+Vector3DInt16(1,1,1),2); + bool lowerCornerInside = (v3dFloor.getX() > 2)&&(v3dFloor.getY() > 2)&&(v3dFloor.getZ() > 2); - if(lowerCornerInside && upperCornerInside) //If this test fails the vertex will be left as it was + if(lowerCornerInside) //If this test fails the vertex will be left as it was { Vector3DFloat v3dGradient = computeNormal(volumeData, v3dPos, normalGenerationMethod); @@ -56,7 +55,7 @@ v3dGradient.normalise(); iterSurfaceVertex->setNormal(v3dGradient); } - } //(lowerCornerInside && upperCornerInside) + } //(lowerCornerInside) ++iterSurfaceVertex; } } @@ -97,7 +96,7 @@ } if((v3dPos.getZ() - v3dFloor.getZ()) > 0.25) //The result should be 0.0 or 0.5 { - volIter.setPosition(static_cast(v3dFloor+Vector3DInt32(0,0,1))); + volIter.setPosition(static_cast(v3dFloor+Vector3DInt32(0,0,1))); } Vector3DFloat gradCeil; Index: library/PolyVoxCore/include/Volume.inl =================================================================== --- library/PolyVoxCore/include/Volume.inl (revision 1406) +++ library/PolyVoxCore/include/Volume.inl (working copy) @@ -32,6 +32,23 @@ #include #include //For invalid_argument +#include + +template +void loadEmptyBlock_fun(PolyVox::Volume& vol, PolyVox::Region reg) +{ + std::cout << "loading empty block: " << reg.getLowerCorner() << " -> " << reg.getUpperCorner() << std::endl; + // when you implement this function yourself, you should probablly put something into the region... otherwise it'll be empty (filled with VoxelType()) +} + +template +void unloadBlock_fun(PolyVox::Volume&, PolyVox::Region reg) +{ + std::cout << "warning unloading block: " << reg.getLowerCorner() << " -> " << reg.getUpperCorner() << std::endl; + // when you implement this function yourself, you should save the data from blockToSave +} + + namespace PolyVox { //////////////////////////////////////////////////////////////////////////////// @@ -47,17 +64,20 @@ /// the default if you are not sure what to choose here. //////////////////////////////////////////////////////////////////////////////// template - Volume::Volume(uint16_t uWidth, uint16_t uHeight, uint16_t uDepth, uint16_t uBlockSideLength) + Volume::Volume(uint16_t uBlockSideLength, uint16_t uMaxBlocksLoaded) :m_uTimestamper(0) ,m_uMaxUncompressedBlockCacheSize(256) + ,m_uMaxBlocksLoaded(uMaxBlocksLoaded) ,m_uBlockSideLength(uBlockSideLength) - ,m_pUncompressedBorderData(0) - ,m_ulastAccessedBlockIndex((std::numeric_limits::max)()) //An invalid index + ,m_ulastAccessedBlockIndex(BlockPos((std::numeric_limits::max)(), (std::numeric_limits::max)(), (std::numeric_limits::max)() ) )//An invalid index { + m_fLoad = boost::bind(&loadEmptyBlock_fun, boost::ref(*this), _1); + m_fUnload = boost::bind(&unloadBlock_fun, boost::ref(*this), _1); setBlockCacheSize(m_uMaxUncompressedBlockCacheSize); + setMaxBlocksLoaded(m_uMaxBlocksLoaded); //Create a volume of the right size. - resize(uWidth, uHeight, uDepth, uBlockSideLength); + resize(uBlockSideLength); } //////////////////////////////////////////////////////////////////////////////// @@ -66,126 +86,34 @@ template Volume::~Volume() { + typename boost::unordered_map >::iterator i = m_pBlocks.begin(); + while(i != m_pBlocks.end()) { + unloadBlock(i); + i = m_pBlocks.begin(); + } } //////////////////////////////////////////////////////////////////////////////// - /// The border value is returned whenever an atempt is made to read a voxel which - /// is outside the extents of the volume. - /// \return The value used for voxels outside of the volume - //////////////////////////////////////////////////////////////////////////////// - template - VoxelType Volume::getBorderValue(void) const - { - /*Block* pUncompressedBorderBlock = getUncompressedBlock(const_cast*>(&m_pBorderBlock)); - return pUncompressedBorderBlock->getVoxelAt(0,0,0);*/ - return *m_pUncompressedBorderData; - } - - //////////////////////////////////////////////////////////////////////////////// - /// The result will always have a lower corner at (0,0,0) and an upper corner at one - /// less than the side length. For example, if a volume has dimensions 256x512x1024 - /// then the upper corner of the enclosing region will be at (255,511,1023). - /// \return A Region representing the extent of the volume. - //////////////////////////////////////////////////////////////////////////////// - template - Region Volume::getEnclosingRegion(void) const - { - return Region(Vector3DInt16(0,0,0), Vector3DInt16(m_uWidth-1,m_uHeight-1,m_uDepth-1)); - } - - //////////////////////////////////////////////////////////////////////////////// - /// \return The width of the volume in voxels - /// \sa getHeight(), getDepth() - //////////////////////////////////////////////////////////////////////////////// - template - uint16_t Volume::getWidth(void) const - { - return m_uWidth; - } - - //////////////////////////////////////////////////////////////////////////////// - /// \return The height of the volume in voxels - /// \sa getWidth(), getDepth() - //////////////////////////////////////////////////////////////////////////////// - template - uint16_t Volume::getHeight(void) const - { - return m_uHeight; - } - - //////////////////////////////////////////////////////////////////////////////// - /// \return The depth of the volume in voxels - /// \sa getWidth(), getHeight() - //////////////////////////////////////////////////////////////////////////////// - template - uint16_t Volume::getDepth(void) const - { - return m_uDepth; - } - - //////////////////////////////////////////////////////////////////////////////// - /// \return The length of the shortest side in voxels. For example, if a volume has - /// dimensions 256x512x1024 this function will return 256. - /// \sa getLongestSideLength(), getDiagonalLength() - //////////////////////////////////////////////////////////////////////////////// - template - uint16_t Volume::getShortestSideLength(void) const - { - return m_uShortestSideLength; - } - - //////////////////////////////////////////////////////////////////////////////// - /// \return The length of the longest side in voxels. For example, if a volume has - /// dimensions 256x512x1024 this function will return 1024. - /// \sa getShortestSideLength(), getDiagonalLength() - //////////////////////////////////////////////////////////////////////////////// - template - uint16_t Volume::getLongestSideLength(void) const - { - return m_uLongestSideLength; - } - - //////////////////////////////////////////////////////////////////////////////// - /// \return The length of the diagonal in voxels. For example, if a volume has - /// dimensions 256x512x1024 this function will return sqrt(256*256+512*512+1024*1024) - /// = 1173.139. This value is computed on volume creation so retrieving it is fast. - /// \sa getShortestSideLength(), getLongestSideLength() - //////////////////////////////////////////////////////////////////////////////// - template - float Volume::getDiagonalLength(void) const - { - return m_fDiagonalLength; - } - - //////////////////////////////////////////////////////////////////////////////// /// \param uXPos the \c x position of the voxel /// \param uYPos the \c y position of the voxel /// \param uZPos the \c z position of the voxel /// \return the voxel value //////////////////////////////////////////////////////////////////////////////// template - VoxelType Volume::getVoxelAt(uint16_t uXPos, uint16_t uYPos, uint16_t uZPos) const + VoxelType Volume::getVoxelAt(VoxelPosType uXPos, VoxelPosType uYPos, VoxelPosType uZPos) { - //We don't use getEnclosingRegion here because we care - //about speed and don't need to check the lower bound. - if((uXPos < getWidth()) && (uYPos < getHeight()) && (uZPos < getDepth())) - { - const uint16_t blockX = uXPos >> m_uBlockSideLengthPower; - const uint16_t blockY = uYPos >> m_uBlockSideLengthPower; - const uint16_t blockZ = uZPos >> m_uBlockSideLengthPower; + const BlockPosType blockX = uXPos >> m_uBlockSideLengthPower; + const BlockPosType blockY = uYPos >> m_uBlockSideLengthPower; + const BlockPosType blockZ = uZPos >> m_uBlockSideLengthPower; - const uint16_t xOffset = uXPos - (blockX << m_uBlockSideLengthPower); - const uint16_t yOffset = uYPos - (blockY << m_uBlockSideLengthPower); - const uint16_t zOffset = uZPos - (blockZ << m_uBlockSideLengthPower); + // see setVoxelAt for more about the uint16_t and the offsets + const uint16_t xOffset = uXPos - (blockX << m_uBlockSideLengthPower); + const uint16_t yOffset = uYPos - (blockY << m_uBlockSideLengthPower); + const uint16_t zOffset = uZPos - (blockZ << m_uBlockSideLengthPower); - Block* pUncompressedBlock = getUncompressedBlock(blockX, blockY, blockZ); + Block* pUncompressedBlock = getUncompressedBlock(blockX, blockY, blockZ); - return pUncompressedBlock->getVoxelAt(xOffset,yOffset,zOffset); - } - else - { - return getBorderValue(); - } + return pUncompressedBlock->getVoxelAt(xOffset,yOffset,zOffset); } //////////////////////////////////////////////////////////////////////////////// @@ -193,7 +121,7 @@ /// \return the voxel value //////////////////////////////////////////////////////////////////////////////// template - VoxelType Volume::getVoxelAt(const Vector3DUint16& v3dPos) const + VoxelType Volume::getVoxelAt(const VoxelPos& v3dPos) { return getVoxelAt(v3dPos.getX(), v3dPos.getY(), v3dPos.getZ()); } @@ -213,14 +141,27 @@ } //////////////////////////////////////////////////////////////////////////////// - /// \param tBorder The value to use for voxels outside the volume. + /// volume data and then set it to a smaller value (e.g.64) for general processing. + /// \param uMaxBlocksLoaded The number of blocks which can be simultanously in memory + /// lowering the number of blocks that is allowed might cause some blocks to unload //////////////////////////////////////////////////////////////////////////////// template - void Volume::setBorderValue(const VoxelType& tBorder) + void Volume::setMaxBlocksLoaded(uint16_t uMaxBlocksLoaded) { - /*Block* pUncompressedBorderBlock = getUncompressedBlock(&m_pBorderBlock); - return pUncompressedBorderBlock->fill(tBorder);*/ - std::fill(m_pUncompressedBorderData, m_pUncompressedBorderData + m_uBlockSideLength * m_uBlockSideLength * m_uBlockSideLength, tBorder); + if(uMaxBlocksLoaded < m_pBlocks.size()) { + for(int j = uMaxBlocksLoaded; j < m_pBlocks.size(); j++) { + typename boost::unordered_map >::iterator oldest_block = m_pBlocks.begin(); + typename boost::unordered_map >::iterator i; + for(i = m_pBlocks.begin(); i!=m_pBlocks.end(); i++) { + if(i->second.m_uTimestamp < oldest_block->second.m_uTimestamp) { + oldest_block = i; + } + } + unloadBlock(oldest_block); + } + } + + m_uMaxBlocksLoaded = uMaxBlocksLoaded; } //////////////////////////////////////////////////////////////////////////////// @@ -231,32 +172,24 @@ /// \return whether the requested position is inside the volume //////////////////////////////////////////////////////////////////////////////// template - bool Volume::setVoxelAt(uint16_t uXPos, uint16_t uYPos, uint16_t uZPos, VoxelType tValue) + bool Volume::setVoxelAt(VoxelPosType uXPos, VoxelPosType uYPos, VoxelPosType uZPos, VoxelType tValue) { - //We don't use getEnclosingRegion here because we care - //about speed and don't need to check the lower bound. - if((uXPos < getWidth()) && (uYPos < getHeight()) && (uZPos < getDepth())) - { - const uint16_t blockX = uXPos >> m_uBlockSideLengthPower; - const uint16_t blockY = uYPos >> m_uBlockSideLengthPower; - const uint16_t blockZ = uZPos >> m_uBlockSideLengthPower; + const BlockPosType blockX = uXPos >> m_uBlockSideLengthPower; + const BlockPosType blockY = uYPos >> m_uBlockSideLengthPower; + const BlockPosType blockZ = uZPos >> m_uBlockSideLengthPower; - const uint16_t xOffset = uXPos - (blockX << m_uBlockSideLengthPower); - const uint16_t yOffset = uYPos - (blockY << m_uBlockSideLengthPower); - const uint16_t zOffset = uZPos - (blockZ << m_uBlockSideLengthPower); + // uint16 is ok here, because a single block should never need 256 terabytes (+ I'm too lazy to change PolyVox::Block) + // xOffset = uXPos%m_uBlockSideLength + const uint16_t xOffset = static_cast(uXPos - (blockX << m_uBlockSideLengthPower)); + const uint16_t yOffset = static_cast(uYPos - (blockY << m_uBlockSideLengthPower)); + const uint16_t zOffset = static_cast(uZPos - (blockZ << m_uBlockSideLengthPower)); - Block* pUncompressedBlock = getUncompressedBlock(blockX, blockY, blockZ); + Block* pUncompressedBlock = getUncompressedBlock(blockX, blockY, blockZ); - pUncompressedBlock->setVoxelAt(xOffset,yOffset,zOffset, tValue); + pUncompressedBlock->setVoxelAt(xOffset,yOffset,zOffset, tValue); - //Return true to indicate that we modified a voxel. - return true; - } - else - { - //Return false to indicate that no voxel was modified. - return false; - } + //Return true to indicate that we modified a voxel. + return true; } //////////////////////////////////////////////////////////////////////////////// @@ -265,7 +198,7 @@ /// \return whether the requested position is inside the volume //////////////////////////////////////////////////////////////////////////////// template - bool Volume::setVoxelAt(const Vector3DUint16& v3dPos, VoxelType tValue) + bool Volume::setVoxelAt(const VoxelPos& v3dPos, VoxelType tValue) { return setVoxelAt(v3dPos.getX(), v3dPos.getY(), v3dPos.getZ(), tValue); } @@ -283,9 +216,6 @@ //////////////////////////////////////////////////////////////////////////////// /// Note: Calling this function will destroy all existing data in the volume. - /// \param uWidth The desired width in voxels. This must be a power of two. - /// \param uHeight The desired height in voxels. This must be a power of two. - /// \param uDepth The desired depth in voxels. This must be a power of two. /// \param uBlockSideLength The size of the blocks which make up the volume. Small /// blocks are more likely to be homogeneous (so more easily shared) and have better /// cache behaviour. However, there is a memory overhead per block so if they are @@ -294,14 +224,11 @@ /// the default if you are not sure what to choose here. //////////////////////////////////////////////////////////////////////////////// template - void Volume::resize(uint16_t uWidth, uint16_t uHeight, uint16_t uDepth, uint16_t uBlockSideLength) + void Volume::resize(uint16_t uBlockSideLength) { //Debug mode validation assert(uBlockSideLength > 0); assert(isPowerOf2(uBlockSideLength)); - assert(uBlockSideLength <= uWidth); - assert(uBlockSideLength <= uHeight); - assert(uBlockSideLength <= uDepth); //Release mode validation if(uBlockSideLength == 0) @@ -312,129 +239,123 @@ { throw std::invalid_argument("Block side length must be a power of two."); } - if(uBlockSideLength > uWidth) - { - throw std::invalid_argument("Block side length cannot be greater than volume width."); - } - if(uBlockSideLength > uHeight) - { - throw std::invalid_argument("Block side length cannot be greater than volume height."); - } - if(uBlockSideLength > uDepth) - { - throw std::invalid_argument("Block side length cannot be greater than volume depth."); - } //Clear the previous data - m_pBlocks.clear(); + typename boost::unordered_map >::iterator i; + for(i = m_pBlocks.begin(); i != m_pBlocks.end(); i++) { + unloadBlock(i); + } m_pUncompressedTimestamps.clear(); - //Compute the volume side lengths - m_uWidth = uWidth; - m_uHeight = uHeight; - m_uDepth = uDepth; //Compute the block side length m_uBlockSideLength = uBlockSideLength; m_uBlockSideLengthPower = logBase2(m_uBlockSideLength); - //Compute the side lengths in blocks - m_uWidthInBlocks = m_uWidth / m_uBlockSideLength; - m_uHeightInBlocks = m_uHeight / m_uBlockSideLength; - m_uDepthInBlocks = m_uDepth / m_uBlockSideLength; - - //Compute number of blocks in the volume - m_uNoOfBlocksInVolume = m_uWidthInBlocks * m_uHeightInBlocks * m_uDepthInBlocks; - - //Create the blocks - m_pBlocks.resize(m_uNoOfBlocksInVolume); - for(uint32_t i = 0; i < m_uNoOfBlocksInVolume; ++i) - { - m_pBlocks[i].initialise(m_uBlockSideLength); - } - - m_pUncompressedTimestamps.resize(m_uNoOfBlocksInVolume); - std::fill(m_pUncompressedTimestamps.begin(), m_pUncompressedTimestamps.end(), 0); - - //Create the border block - m_pUncompressedBorderData = new VoxelType[m_uBlockSideLength * m_uBlockSideLength * m_uBlockSideLength]; - std::fill(m_pUncompressedBorderData, m_pUncompressedBorderData + m_uBlockSideLength * m_uBlockSideLength * m_uBlockSideLength, VoxelType()); - - //Other properties we might find useful later - m_uLongestSideLength = (std::max)((std::max)(m_uWidth,m_uHeight),m_uDepth); - m_uShortestSideLength = (std::min)((std::min)(m_uWidth,m_uHeight),m_uDepth); - m_fDiagonalLength = sqrtf(static_cast(m_uWidth * m_uWidth + m_uHeight * m_uHeight + m_uDepth * m_uDepth)); + m_pUncompressedTimestamps.resize(m_uMaxUncompressedBlockCacheSize, 0); } template - Block* Volume::getUncompressedBlock(uint16_t uBlockX, uint16_t uBlockY, uint16_t uBlockZ) const + void Volume::unloadBlock(typename boost::unordered_map >::iterator& block) + { + const VoxelPos lower(block->first.getX() << m_uBlockSideLengthPower, + block->first.getY() << m_uBlockSideLengthPower, + block->first.getZ() << m_uBlockSideLengthPower); + const VoxelPos upper((block->first.getX()+1) << m_uBlockSideLengthPower, + (block->first.getY()+1) << m_uBlockSideLengthPower, + (block->first.getZ()+1) << m_uBlockSideLengthPower); + m_fUnload(Region(static_cast(lower), static_cast(upper))); + m_pBlocks.erase(block); + } + + template + Block* Volume::getUncompressedBlock(BlockPosType uBlockX, BlockPosType uBlockY, BlockPosType uBlockZ) { - //Compute the block's index from it's position. - uint32_t uBlockIndex = - uBlockX + - uBlockY * m_uWidthInBlocks + - uBlockZ * m_uWidthInBlocks * m_uHeightInBlocks; + const BlockPos pos(uBlockX, uBlockY, uBlockZ); + typename boost::unordered_map >::iterator block_i; + block_i = m_pBlocks.find(pos); - //Get the block - Block* block = &(m_pBlocks[uBlockIndex]); + // load the block if necessary + if(block_i == m_pBlocks.end()) { + // unload other blocks if necessary + if(m_pBlocks.size() == m_uMaxBlocksLoaded) { + typename boost::unordered_map >::iterator oldest_block = m_pBlocks.begin(); + typename boost::unordered_map >::iterator i; + for(i = m_pBlocks.begin(); i!=m_pBlocks.end(); i++) { + if(i->second.m_uTimestamp < oldest_block->second.m_uTimestamp) { + oldest_block = i; + } + } + unloadBlock(i); + } + // create an empty block at pos + m_pBlocks[pos] = Block(m_uBlockSideLength); + VoxelPos lower(uBlockX << m_uBlockSideLengthPower, uBlockY << m_uBlockSideLengthPower, uBlockZ << m_uBlockSideLengthPower); + VoxelPos upper((uBlockX+1) << m_uBlockSideLengthPower, (uBlockY+1) << m_uBlockSideLengthPower, (uBlockZ+1) << m_uBlockSideLengthPower); + m_fLoad(Region(static_cast(lower), static_cast(upper))); + } + //Get the block + Block& block = m_pBlocks[pos]; //Check if we have the same block as last time, if so there's no need to even update - //the time stamp. If we updated it everytime then that would be every time we touched + //the time stamp or read the block. If we updated it everytime then that would be every time we touched //a voxel, which would overflow a uint32_t and require us to use a uint64_t instead. - if(uBlockIndex == m_ulastAccessedBlockIndex) + if(pos == m_ulastAccessedBlockIndex) { - return block; + return █ } + m_ulastAccessedBlockIndex = pos; - m_pUncompressedTimestamps[uBlockIndex] = ++m_uTimestamper; + m_uTimestamper++; + block.m_uTimestamp = m_uTimestamper; + m_pUncompressedTimestamps[block.m_uUncompressedIndex] = m_uTimestamper; - if(block->m_bIsCompressed == false) + if(block.m_bIsCompressed == false) { - return block; + return █ } //Currently we find the oldest block by iterating over the whole array. Of course we could store the blocks sorted by //timestamp (set, priority_queue, etc) but then we'll need to move them around as the timestamp changes. Can come back - //to this if it proves to be a bottleneck (compraed to the cost of actually doing the compression/decompression). - uint32_t uUncompressedBlockIndex = 100000000; + //to this if it proves to be a bottleneck (compared to the cost of actually doing the compression/decompression). + uint32_t uUncompressedBlockIndex = std::numeric_limits::max(); assert(m_vecUncompressedBlockCache.size() <= m_uMaxUncompressedBlockCacheSize); if(m_vecUncompressedBlockCache.size() == m_uMaxUncompressedBlockCacheSize) { int32_t leastRecentlyUsedBlockIndex = -1; - uint64_t uLeastRecentTimestamp = 1000000000000000; + uint32_t uLeastRecentTimestamp = std::numeric_limits::max(); for(uint32_t ct = 0; ct < m_vecUncompressedBlockCache.size(); ct++) { - if(m_pUncompressedTimestamps[m_vecUncompressedBlockCache[ct].uBlockIndex] < uLeastRecentTimestamp) + if(m_pUncompressedTimestamps[ct] < uLeastRecentTimestamp) { - uLeastRecentTimestamp = m_pUncompressedTimestamps[m_vecUncompressedBlockCache[ct].uBlockIndex]; + uLeastRecentTimestamp = m_pUncompressedTimestamps[ct]; leastRecentlyUsedBlockIndex = ct; } } uUncompressedBlockIndex = leastRecentlyUsedBlockIndex; m_pBlocks[m_vecUncompressedBlockCache[leastRecentlyUsedBlockIndex].uBlockIndex].compress(); - m_pBlocks[m_vecUncompressedBlockCache[leastRecentlyUsedBlockIndex].uBlockIndex].m_tUncompressedData = 0; - m_vecUncompressedBlockCache[leastRecentlyUsedBlockIndex].uBlockIndex = uBlockIndex; + m_vecUncompressedBlockCache[leastRecentlyUsedBlockIndex].uBlockIndex = pos; } else { UncompressedBlock uncompressedBlock; //uncompressedBlock.block = block; - uncompressedBlock.uBlockIndex = uBlockIndex; + uncompressedBlock.uBlockIndex = pos; uncompressedBlock.data = new VoxelType[m_uBlockSideLength * m_uBlockSideLength * m_uBlockSideLength]; m_vecUncompressedBlockCache.push_back(uncompressedBlock); uUncompressedBlockIndex = m_vecUncompressedBlockCache.size() - 1; } - block->uncompress(m_vecUncompressedBlockCache[uUncompressedBlockIndex].data); + block.uncompress(m_vecUncompressedBlockCache[uUncompressedBlockIndex].data); - return block; + return █ } template float Volume::calculateCompressionRatio(void) { - float fRawSize = m_uWidth * m_uHeight * m_uDepth * sizeof(VoxelType); + float fRawSize = m_pBlocks.size()*m_uBlockSideLength*m_uBlockSideLength*m_uBlockSideLength*sizeof(VoxelType); float fCompressedSize = calculateSizeInBytes(); return fCompressedSize/fRawSize; } @@ -445,39 +366,16 @@ uint32_t uSizeInBytes = sizeof(Volume); //Memory used by the blocks - for(uint32_t i = 0; i < m_uNoOfBlocksInVolume; ++i) - { - uSizeInBytes += m_pBlocks[i].calculateSizeInBytes(); - } + typename boost::unordered_map >::const_iterator i; + for(i = m_pBlocks.begin(); i != m_pBlocks.end(); i++) { + uSizeInBytes += i->second.calculateSizeInBytes(); + } //Memory used by the block cache. uSizeInBytes += m_vecUncompressedBlockCache.capacity() * sizeof(UncompressedBlock); uSizeInBytes += m_vecUncompressedBlockCache.size() * m_uBlockSideLength * m_uBlockSideLength * m_uBlockSideLength * sizeof(VoxelType); uSizeInBytes += m_pUncompressedTimestamps.capacity() * sizeof(uint32_t); - //Memory used by border data. - if(m_pUncompressedBorderData) - { - uSizeInBytes += m_uBlockSideLength * m_uBlockSideLength * m_uBlockSideLength * sizeof(VoxelType); - } - return uSizeInBytes; } - - template - void Volume::useCompatibilityMode(void) - { - setBlockCacheSize(m_uNoOfBlocksInVolume * 2); //Times two gives space to spare - - for(uint32_t z = 0; z < m_uDepthInBlocks; z++) - { - for(uint32_t y = 0; y < m_uHeightInBlocks; y++) - { - for(uint32_t x = 0; x < m_uWidthInBlocks; x++) - { - getUncompressedBlock(x,y,z); - } - } - } - } } Index: library/PolyVoxCore/include/SurfaceExtractor.inl =================================================================== --- library/PolyVoxCore/include/SurfaceExtractor.inl (revision 1406) +++ library/PolyVoxCore/include/SurfaceExtractor.inl (working copy) @@ -38,7 +38,7 @@ { //m_regSizeInVoxels.cropTo(m_volData->getEnclosingRegion()); m_regSizeInCells = m_regSizeInVoxels; - m_regSizeInCells.setUpperCorner(m_regSizeInCells.getUpperCorner() - Vector3DInt16(1,1,1)); + m_regSizeInCells.setUpperCorner(m_regSizeInCells.getUpperCorner() - Vector3DInt32(1,1,1)); m_meshCurrent->clear(); } @@ -61,7 +61,7 @@ //Create a region corresponding to the first slice m_regSlicePrevious = m_regSizeInVoxels; - Vector3DInt16 v3dUpperCorner = m_regSlicePrevious.getUpperCorner(); + Vector3DInt32 v3dUpperCorner = m_regSlicePrevious.getUpperCorner(); v3dUpperCorner.setZ(m_regSlicePrevious.getLowerCorner().getZ()); //Set the upper z to the lower z to make it one slice thick. m_regSlicePrevious.setUpperCorner(v3dUpperCorner); m_regSliceCurrent = m_regSlicePrevious; @@ -88,10 +88,10 @@ m_pPreviousVertexIndicesZ.swap(m_pCurrentVertexIndicesZ); m_regSlicePrevious = m_regSliceCurrent; - m_regSliceCurrent.shift(Vector3DInt16(0,0,1)); + m_regSliceCurrent.shift(Vector3DInt32(0,0,1)); //Process the other slices (previous slice is available) - for(int16_t uSlice = 1; uSlice <= m_regSizeInVoxels.depth(); uSlice++) + for(int32_t uSlice = 1; uSlice <= m_regSizeInVoxels.depth(); uSlice++) { computeBitmaskForSlice(pPreviousBitmask, pCurrentBitmask); uNoOfNonEmptyCellsForSlice1 = m_uNoOfOccupiedCells; @@ -116,7 +116,7 @@ m_pPreviousVertexIndicesZ.swap(m_pCurrentVertexIndicesZ); m_regSlicePrevious = m_regSliceCurrent; - m_regSliceCurrent.shift(Vector3DInt16(0,0,1)); + m_regSliceCurrent.shift(Vector3DInt32(0,0,1)); } m_meshCurrent->m_Region = m_regSizeInVoxels; @@ -134,8 +134,8 @@ { m_uNoOfOccupiedCells = 0; - const int16_t iMaxXVolSpace = m_regSliceCurrent.getUpperCorner().getX(); - const int16_t iMaxYVolSpace = m_regSliceCurrent.getUpperCorner().getY(); + const int32_t iMaxXVolSpace = m_regSliceCurrent.getUpperCorner().getX(); + const int32_t iMaxYVolSpace = m_regSliceCurrent.getUpperCorner().getY(); iZVolSpace = m_regSliceCurrent.getLowerCorner().getZ(); uZRegSpace = iZVolSpace - m_regSizeInVoxels.getLowerCorner().getZ(); @@ -400,15 +400,15 @@ Array2DInt32& m_pCurrentVertexIndicesY, Array2DInt32& m_pCurrentVertexIndicesZ) { - int16_t iZVolSpace = m_regSliceCurrent.getLowerCorner().getZ(); + int32_t iZVolSpace = m_regSliceCurrent.getLowerCorner().getZ(); const uint16_t uZRegSpace = iZVolSpace - m_regSizeInVoxels.getLowerCorner().getZ(); //Iterate over each cell in the region - for(int16_t iYVolSpace = m_regSliceCurrent.getLowerCorner().getY(); iYVolSpace <= m_regSliceCurrent.getUpperCorner().getY(); iYVolSpace++) + for(int32_t iYVolSpace = m_regSliceCurrent.getLowerCorner().getY(); iYVolSpace <= m_regSliceCurrent.getUpperCorner().getY(); iYVolSpace++) { const uint16_t uYRegSpace = iYVolSpace - m_regSizeInVoxels.getLowerCorner().getY(); - for(int16_t iXVolSpace = m_regSliceCurrent.getLowerCorner().getX(); iXVolSpace <= m_regSliceCurrent.getUpperCorner().getX(); iXVolSpace++) + for(int32_t iXVolSpace = m_regSliceCurrent.getLowerCorner().getX(); iXVolSpace <= m_regSliceCurrent.getUpperCorner().getX(); iXVolSpace++) { //Current position const uint16_t uXRegSpace = iXVolSpace - m_regSizeInVoxels.getLowerCorner().getX(); @@ -622,11 +622,11 @@ indlist[i] = -1; } - for(int16_t iYVolSpace = m_regSlicePrevious.getLowerCorner().getY(); iYVolSpace <= m_regSizeInCells.getUpperCorner().getY(); iYVolSpace++) + for(int32_t iYVolSpace = m_regSlicePrevious.getLowerCorner().getY(); iYVolSpace <= m_regSizeInCells.getUpperCorner().getY(); iYVolSpace++) { - for(int16_t iXVolSpace = m_regSlicePrevious.getLowerCorner().getX(); iXVolSpace <= m_regSizeInCells.getUpperCorner().getX(); iXVolSpace++) + for(int32_t iXVolSpace = m_regSlicePrevious.getLowerCorner().getX(); iXVolSpace <= m_regSizeInCells.getUpperCorner().getX(); iXVolSpace++) { - int16_t iZVolSpace = m_regSlicePrevious.getLowerCorner().getZ(); + int32_t iZVolSpace = m_regSlicePrevious.getLowerCorner().getZ(); m_sampVolume.setPosition(iXVolSpace,iYVolSpace,iZVolSpace); //Current position Index: library/PolyVoxCore/include/VolumeSampler.inl =================================================================== --- library/PolyVoxCore/include/VolumeSampler.inl (revision 1406) +++ library/PolyVoxCore/include/VolumeSampler.inl (working copy) @@ -144,25 +144,13 @@ const uint16_t uYPosInBlock = mYPosInVolume - (uYBlock << mVolume->m_uBlockSideLengthPower); const uint16_t uZPosInBlock = mZPosInVolume - (uZBlock << mVolume->m_uBlockSideLengthPower); - const uint32_t uVoxelIndexInBlock = uXPosInBlock + + const uint32_t uVoxelIndexInBlock = uXPosInBlock + uYPosInBlock * mVolume->m_uBlockSideLength + uZPosInBlock * mVolume->m_uBlockSideLength * mVolume->m_uBlockSideLength; - if((uXBlock < mVolume->m_uWidthInBlocks) && (uYBlock < mVolume->m_uHeightInBlocks) && (uZBlock < mVolume->m_uDepthInBlocks)) - { - const uint32_t uBlockIndexInVolume = uXBlock + - uYBlock * mVolume->m_uWidthInBlocks + - uZBlock * mVolume->m_uWidthInBlocks * mVolume->m_uHeightInBlocks; - const Block& currentBlock = mVolume->m_pBlocks[uBlockIndexInVolume]; + Block* pUncompressedCurrentBlock = mVolume->getUncompressedBlock(uXBlock, uYBlock, uZBlock); - Block* pUncompressedCurrentBlock = mVolume->getUncompressedBlock(uXBlock, uYBlock, uZBlock); - - mCurrentVoxel = pUncompressedCurrentBlock->m_tUncompressedData + uVoxelIndexInBlock; - } - else - { - mCurrentVoxel = mVolume->m_pUncompressedBorderData + uVoxelIndexInBlock; - } + mCurrentVoxel = pUncompressedCurrentBlock->m_tUncompressedData + uVoxelIndexInBlock; } template Index: library/PolyVoxCore/include/Volume.h =================================================================== --- library/PolyVoxCore/include/Volume.h (revision 1406) +++ library/PolyVoxCore/include/Volume.h (working copy) @@ -19,7 +19,7 @@ 3. This notice may not be removed or altered from any source distribution. -*******************************************************************************/ + *******************************************************************************/ #ifndef __PolyVox_Volume_H__ #define __PolyVox_Volume_H__ @@ -33,180 +33,180 @@ #include #include -namespace PolyVox -{ - ///The Volume class provides a memory efficient method of storing voxel data while also allowing fast access and modification. - //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// - /// A Volume is essentially a '3D image' in which each element (voxel) is identified by a three dimensional (x,y,z) coordinate, - /// rather than the two dimensional (x,y) coordinate which is used to identify an element (pixel) in a normal image. Within PolyVox, - /// the Volume class is used to store and manipulate our data before we extract our SurfaceMeshs from it. - /// - /// Data Representaion - /// If stored carelessly, volume data can take up a huge amount of memory. For example, a volume of dimensions 1024x1024x1024 with - /// 1 byte per voxel will require 1GB of memory if stored in an uncompressed form. Natuarally our Volume class is much more efficient - /// than this and it is worth understanding (at least at a high level) the approach which is used. - /// - /// Essentially, the Volume class stores its data as a collection of blocks. Each of these block is much smaller than the whole volume, - /// for example a typical size might be 32x32x32 voxels (though is is configurable by the user). In this case, a 256x512x1024 volume - /// would contain 8x16x32 = 4096 blocks. The data for each block is stored in a compressed form, which uses only a small amout of - /// memory but it is hard to modify the data. Therefore, before any given voxel can be modified, its corresponding block must be uncompressed. - /// - /// The compression and decompression of block is a relatively slow process and so we aim to do this as rarely as possible. In order - /// to achive this, the volume class store a cache of recently used blocks and their associated uncompressed data. Each time a voxel - /// is touched a timestamp is updated on the corresponding block, when the cache becomes full the block with the oldest timestamp is - /// recompressed and moved out of the cache. - /// - /// Achieving high compression rates - /// Note: This section is theorectical and not well tested. Please let us know if you find the tips below do or do not work. - /// - /// The compression rates which can be achieved can vary significantly depending the nature of the data you are storing, but you can - /// encourage high compression rates by making your data as homogenous as possible. If you are simply storing a material with each - /// voxel then this will probably happen naturally. Games such as Minecraft which use this approach will typically involve large ares - /// of th same material which will compress down well. - /// - /// However, if you are storing density values then you may want to take some care. The advantage of storing smoothly changing values - /// is that you can get smooth surfaces extracted, but storing smoothly changing values inside or outside objects (rather than just - /// on the boundary) does not benefit the surface and is very hard to compress effectively. You should apply some thresholding to your - /// density values to reduce this problem (this threasholding should only be applied to voxels who don't contribute to the surface). - /// - /// For example, suppose you are using layers of 3D Perlin noise to create a 3D terrain (not a heightmap). If you store the raw Perlin - /// noise value at each voxel then a slice through the volume might look like the following: - /// - /// - /// - /// However, by setting high values to be fixed to one and low values to be fixed to zero you can make a slice through your volume look more like this: - /// - /// - /// - /// The boundary is in the same place and is still smooth, but the large homogenous regions mean the data should compress much more effectively. - /// Although it may look like you have lost some precision in this process this is only because the images above are constrained to 256 - /// greyscale values, where as true Perlin noise will give you floating point values. - /// - /// Cache-aware traversal - /// You might be suprised at just how many cache misses can occur when you traverse the volume in a naive manner. Consider a 1024x1024x1024 volume - /// with blocks of size 32x32x32. And imagine you iterate over this volume with a simple three-level for loop which iterates over x, the y, then z. - /// If you start at position (0,0,0) then ny the time you reach position (1023,0,0) you have touched 1024 voxels along one edge of the volume and - /// have pulled 32 blocks into the cache. By the time you reach (1023,1023,0) you have hit 1024x1024 voxels and pulled 32x32 blocks into the cache. - /// You are now ready to touch voxel (0,0,1) which is right nect to where you started, but unless your cache is at least 32x32 blocks large then this - /// initial block has already been cleared from the cache. - /// - /// Ensuring you have a large enough cache size can obviously help the above situation, but you might also consider iterating over the voxels in a - /// different order. For example, if you replace your three-level loop with a six-level loop then you can first process all the voxels between (0,0,0) - /// and (31,31,31), then process all the voxels between (32,0,0) and (63,0,0), and so forth. Using this approach you will have no cache misses even - /// is your cache sise is only one. Of course the logic is more complex, but writing code in such a cache-aware manner may be beneficial in some situations. - /// - /// Threading - /// The volume class does not provide any thread safety constructs and can therefore not be assumed to be thread safe. To be safe you should only allow - /// one thread to access the volume at a time. Even if you have several threads just reading data from the volume they can cause blocks to be pushed - /// out of the cache, potentially invalidating any pointers other threads might be using. - /// - /// That said, we believe that if care is taken then multiple threads can be used, and are currently experimenting with this. - /// - /// Use of templates - /// Although this class is templatised on the voxel type it is not expected that you can use any primative type to represent your voxels. It is only - /// intended for PolyVox's voxel types such as Material, Density, and MarterialDensityPair. If you need to store 3D grids of ints, floats, or pointers - /// you should look ar the Array class instead. - //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// - template - class Volume - { - // Make VolumeSampler a friend - friend class VolumeSampler; +#include +#include +#include - struct UncompressedBlock - { - uint32_t uBlockIndex; - VoxelType* data; +typedef uint32_t VoxelPosType; +typedef PolyVox::Vector<3, VoxelPosType> VoxelPos; +typedef uint16_t BlockPosType; +typedef PolyVox::Vector<3, BlockPosType> BlockPos; - }; +namespace boost { - public: - /// Constructor - Volume(uint16_t uWidth, uint16_t uHeight, uint16_t uDepth, uint16_t uBlockSideLength = 32); - /// Destructor - ~Volume(); + template<> + struct hash { + size_t operator()(const BlockPos& v) const { + // by "thefries" @ http://www.gamedev.net/topic/567378-how-do-i-find-hash-value-of-a-3d-vector-/ + // multiplied by large prime numbers and xord + return (v.getX() * 73856093) ^ (v.getY() * 19349663) ^ (v.getZ() * 83492791); + /* + const size_t primes[] = {73856093, 19349663, 83492791}; + const size_t num_primes = sizeof(primes)/sizeof(size_t); + size_t ret = 0; + for(size_t i = 0; i < T_dims; i++) { + ret ^= v.getElement(i) * primes[i%num_primes]; + } + return ret;*/ + } + }; +} - /// Gets the value used for voxels which are outside the volume - VoxelType getBorderValue(void) const; - /// Gets a Region representing the extents of the Volume. - Region getEnclosingRegion(void) const; - /// Gets the width of the volume in voxels. - uint16_t getWidth(void) const; - /// Gets the height of the volume in voxels. - uint16_t getHeight(void) const; - /// Gets the depth of the volume in voxels. - uint16_t getDepth(void) const; - /// Gets the length of the longest side in voxels - uint16_t getLongestSideLength(void) const; - /// Gets the length of the shortest side in voxels - uint16_t getShortestSideLength(void) const; - /// Gets the length of the diagonal in voxels - float getDiagonalLength(void) const; - /// Gets a voxel by x,y,z position - VoxelType getVoxelAt(uint16_t uXPos, uint16_t uYPos, uint16_t uZPos) const; - /// Gets a voxel by 3D vector position - VoxelType getVoxelAt(const Vector3DUint16& v3dPos) const; - /// Sets the number of blocks for which uncompressed data is stored. - void setBlockCacheSize(uint16_t uBlockCacheSize); - /// Sets the value used for voxels which are outside the volume - void setBorderValue(const VoxelType& tBorder); - /// Sets the voxel at an x,y,z position - bool setVoxelAt(uint16_t uXPos, uint16_t uYPos, uint16_t uZPos, VoxelType tValue); - /// Sets the voxel at a 3D vector position - bool setVoxelAt(const Vector3DUint16& v3dPos, VoxelType tValue); +namespace PolyVox { - void clearBlockCache(void); - float calculateCompressionRatio(void); - uint32_t calculateSizeInBytes(void); - void useCompatibilityMode(void); - /// Resizes the volume to the specified dimensions - void resize(uint16_t uWidth, uint16_t uHeight, uint16_t uDepth, uint16_t uBlockSideLength = 32); + ///The Volume class provides a memory efficient method of storing voxel data while also allowing fast access and modification. + //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /// A Volume is essentially a '3D image' in which each element (voxel) is identified by a three dimensional (x,y,z) coordinate, + /// rather than the two dimensional (x,y) coordinate which is used to identify an element (pixel) in a normal image. Within PolyVox, + /// the Volume class is used to store and manipulate our data before we extract our SurfaceMeshs from it. + /// + /// Data Representaion + /// If stored carelessly, volume data can take up a huge amount of memory. For example, a volume of dimensions 1024x1024x1024 with + /// 1 byte per voxel will require 1GB of memory if stored in an uncompressed form. Natuarally our Volume class is much more efficient + /// than this and it is worth understanding (at least at a high level) the approach which is used. + /// + /// Essentially, the Volume class stores its data as a collection of blocks. Each of these block is much smaller than the whole volume, + /// for example a typical size might be 32x32x32 voxels (though is is configurable by the user). In this case, a 256x512x1024 volume + /// would contain 8x16x32 = 4096 blocks. The data for each block is stored in a compressed form, which uses only a small amout of + /// memory but it is hard to modify the data. Therefore, before any given voxel can be modified, its corresponding block must be uncompressed. + /// + /// The compression and decompression of block is a relatively slow process and so we aim to do this as rarely as possible. In order + /// to achive this, the volume class store a cache of recently used blocks and their associated uncompressed data. Each time a voxel + /// is touched a timestamp is updated on the corresponding block, when the cache becomes full the block with the oldest timestamp is + /// recompressed and moved out of the cache. + /// + /// Achieving high compression rates + /// Note: This section is theorectical and not well tested. Please let us know if you find the tips below do or do not work. + /// + /// The compression rates which can be achieved can vary significantly depending the nature of the data you are storing, but you can + /// encourage high compression rates by making your data as homogenous as possible. If you are simply storing a material with each + /// voxel then this will probably happen naturally. Games such as Minecraft which use this approach will typically involve large ares + /// of th same material which will compress down well. + /// + /// However, if you are storing density values then you may want to take some care. The advantage of storing smoothly changing values + /// is that you can get smooth surfaces extracted, but storing smoothly changing values inside or outside objects (rather than just + /// on the boundary) does not benefit the surface and is very hard to compress effectively. You should apply some thresholding to your + /// density values to reduce this problem (this threasholding should only be applied to voxels who don't contribute to the surface). + /// + /// For example, suppose you are using layers of 3D Perlin noise to create a 3D terrain (not a heightmap). If you store the raw Perlin + /// noise value at each voxel then a slice through the volume might look like the following: + /// + /// + /// + /// However, by setting high values to be fixed to one and low values to be fixed to zero you can make a slice through your volume look more like this: + /// + /// + /// + /// The boundary is in the same place and is still smooth, but the large homogenous regions mean the data should compress much more effectively. + /// Although it may look like you have lost some precision in this process this is only because the images above are constrained to 256 + /// greyscale values, where as true Perlin noise will give you floating point values. + /// + /// Cache-aware traversal + /// You might be suprised at just how many cache misses can occur when you traverse the volume in a naive manner. Consider a 1024x1024x1024 volume + /// with blocks of size 32x32x32. And imagine you iterate over this volume with a simple three-level for loop which iterates over x, the y, then z. + /// If you start at position (0,0,0) then ny the time you reach position (1023,0,0) you have touched 1024 voxels along one edge of the volume and + /// have pulled 32 blocks into the cache. By the time you reach (1023,1023,0) you have hit 1024x1024 voxels and pulled 32x32 blocks into the cache. + /// You are now ready to touch voxel (0,0,1) which is right nect to where you started, but unless your cache is at least 32x32 blocks large then this + /// initial block has already been cleared from the cache. + /// + /// Ensuring you have a large enough cache size can obviously help the above situation, but you might also consider iterating over the voxels in a + /// different order. For example, if you replace your three-level loop with a six-level loop then you can first process all the voxels between (0,0,0) + /// and (31,31,31), then process all the voxels between (32,0,0) and (63,0,0), and so forth. Using this approach you will have no cache misses even + /// is your cache sise is only one. Of course the logic is more complex, but writing code in such a cache-aware manner may be beneficial in some situations. + /// + /// Threading + /// The volume class does not provide any thread safety constructs and can therefore not be assumed to be thread safe. To be safe you should only allow + /// one thread to access the volume at a time. Even if you have several threads just reading data from the volume they can cause blocks to be pushed + /// out of the cache, potentially invalidating any pointers other threads might be using. + /// + /// That said, we believe that if care is taken then multiple threads can be used, and are currently experimenting with this. + /// + /// Use of templates + /// Although this class is templatised on the voxel type it is not expected that you can use any primative type to represent your voxels. It is only + /// intended for PolyVox's voxel types such as Material, Density, and MarterialDensityPair. If you need to store 3D grids of ints, floats, or pointers + /// you should look ar the Array class instead. + //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// - private: - Block* getUncompressedBlock(uint16_t uBlockX, uint16_t uBlockY, uint16_t uBlockZ) const; + template + class Volume { + // Make VolumeSampler a friend + friend class VolumeSampler; - //The block data - mutable std::vector< Block > m_pBlocks; + struct UncompressedBlock { + BlockPos uBlockIndex; + VoxelType* data; - //The cache of uncompressed blocks. The uncompressed block data and the timestamps are stored here rather - //than in the Block class. This is so that in the future each VolumeIterator might to maintain its own cache - //of blocks. However, this could mean the same block data is uncompressed and modified in more than one - //location in memory... could be messy with threading. - mutable std::vector< UncompressedBlock > m_vecUncompressedBlockCache; - mutable std::vector m_pUncompressedTimestamps; - mutable uint32_t m_uTimestamper; - uint32_t m_ulastAccessedBlockIndex; - uint32_t m_uMaxUncompressedBlockCacheSize; + }; + public: + /// Constructor + Volume(uint16_t uBlockSideLength = 32, uint16_t uMaxBlocksLoaded = 4096); - //We don't store an actual Block for the border, just the uncompressed data. This is partly because the border - //block does not have a position (so can't be passed to getUncompressedBlock()) and partly because there's a - //good chance we'll often hit it anyway. It's a chunk of homogenous data (rather than a single value) so that - //the VolumeIterator can do it's usual pointer arithmetic without needing to know it's gone outside the volume. - VoxelType* m_pUncompressedBorderData; + /// Destructor + ~Volume(); - uint32_t m_uNoOfBlocksInVolume; + /// Gets a voxel by x,y,z position + VoxelType getVoxelAt(VoxelPosType uXPos, VoxelPosType uYPos, VoxelPosType uZPos); + /// Gets a voxel by 3D vector position + VoxelType getVoxelAt(const VoxelPos& v3dPos); - uint16_t m_uWidthInBlocks; - uint16_t m_uHeightInBlocks; - uint16_t m_uDepthInBlocks; + /// Sets the number of blocks for which uncompressed data is stored. + void setBlockCacheSize(uint16_t uBlockCacheSize); + /// Sets the maximum number of blocks that can be available without calling the load callback + void setMaxBlocksLoaded(uint16_t uMaxBlocksLoaded); + /// Sets the voxel at an x,y,z position + bool setVoxelAt(VoxelPosType uXPos, VoxelPosType uYPos, VoxelPosType uZPos, VoxelType tValue); + /// Sets the voxel at a 3D vector position + bool setVoxelAt(const VoxelPos& v3dPos, VoxelType tValue); - uint16_t m_uWidth; - uint16_t m_uHeight; - uint16_t m_uDepth; + void clearBlockCache(void); + float calculateCompressionRatio(void); + uint32_t calculateSizeInBytes(void); + /// Resizes the volume to the specified dimensions + void resize(uint16_t uBlockSideLength = 32); - uint8_t m_uBlockSideLengthPower; - uint16_t m_uBlockSideLength; + private: + Block* getUncompressedBlock(BlockPosType uBlockX, BlockPosType uBlockY, BlockPosType uBlockZ); + void unloadBlock(typename boost::unordered_map >::iterator& block); + public: + // portable function syntax, might be useful + //boost::function2&, Region> m_fLoad; + //boost::function2&, Region> m_fUnload; + boost::function m_fLoad; + boost::function m_fUnload; + private: + //The block data + mutable boost::unordered_map > m_pBlocks; - uint16_t m_uLongestSideLength; - uint16_t m_uShortestSideLength; - float m_fDiagonalLength; - }; + //The cache of uncompressed blocks. The uncompressed block data and the timestamps are stored here rather + //than in the Block class. This is so that in the future each VolumeIterator might maintain its own cache + //of blocks. However, this could mean the same block data is uncompressed and modified in more than one + //location in memory... could be messy with threading. + mutable std::vector< UncompressedBlock > m_vecUncompressedBlockCache; + mutable std::vector m_pUncompressedTimestamps; + mutable uint32_t m_uTimestamper; + BlockPos m_ulastAccessedBlockIndex; + uint32_t m_uMaxUncompressedBlockCacheSize; + uint32_t m_uMaxBlocksLoaded; - //Some handy typedefs - typedef Volume FloatVolume; - typedef Volume UInt8Volume; - typedef Volume UInt16Volume; + uint8_t m_uBlockSideLengthPower; + uint16_t m_uBlockSideLength; + }; + + //Some handy typedefs + typedef Volume FloatVolume; + typedef Volume UInt8Volume; + typedef Volume UInt16Volume; } #include "Volume.inl" Index: library/PolyVoxCore/include/PolyVoxImpl/Block.h =================================================================== --- library/PolyVoxCore/include/PolyVoxImpl/Block.h (revision 1406) +++ library/PolyVoxCore/include/PolyVoxImpl/Block.h (working copy) @@ -25,7 +25,7 @@ #define __PolyVox_Block_H__ #include "PolyVoxForwardDeclarations.h" - +#include #include namespace PolyVox @@ -58,7 +58,7 @@ void fill(VoxelType tValue); void initialise(uint16_t uSideLength); - uint32_t calculateSizeInBytes(void); + uint32_t calculateSizeInBytes(void) const; public: void compress(void); @@ -69,7 +69,9 @@ uint16_t m_uSideLength; uint8_t m_uSideLengthPower; bool m_bIsCompressed; - bool m_bIsUncompressedDataModified; + bool m_bIsUncompressedDataModified; + uint32_t m_uUncompressedIndex; + uint32_t m_uTimestamp; }; } Index: library/PolyVoxCore/include/PolyVoxImpl/Block.inl =================================================================== --- library/PolyVoxCore/include/PolyVoxImpl/Block.inl (revision 1406) +++ library/PolyVoxCore/include/PolyVoxImpl/Block.inl (working copy) @@ -39,6 +39,8 @@ ,m_tUncompressedData(0) ,m_bIsCompressed(true) ,m_bIsUncompressedDataModified(true) + ,m_uUncompressedIndex(0) + ,m_uTimestamp(0) { if(uSideLength != 0) { @@ -128,10 +130,15 @@ //Compute the side length m_uSideLength = uSideLength; m_uSideLengthPower = logBase2(uSideLength); + uint32_t uNoOfVoxels = m_uSideLength * m_uSideLength * m_uSideLength; + RunlengthEntry entry; + entry.length = uNoOfVoxels; + entry.value = VoxelType(); + m_vecCompressedData.push_back(entry); } template - uint32_t Block::calculateSizeInBytes(void) + uint32_t Block::calculateSizeInBytes(void) const { uint32_t uSizeInBytes = sizeof(Block); uSizeInBytes += m_vecCompressedData.capacity() * sizeof(RunlengthEntry); Index: library/PolyVoxCore/include/CubicSurfaceExtractorWithNormals.inl =================================================================== --- library/PolyVoxCore/include/CubicSurfaceExtractorWithNormals.inl (revision 1406) +++ library/PolyVoxCore/include/CubicSurfaceExtractorWithNormals.inl (working copy) @@ -37,7 +37,7 @@ ,m_meshCurrent(result) { m_regSizeInCells = m_regSizeInVoxels; - m_regSizeInCells.setUpperCorner(m_regSizeInCells.getUpperCorner() - Vector3DInt16(1,1,1)); + m_regSizeInCells.setUpperCorner(m_regSizeInCells.getUpperCorner() - Vector3DInt32(1,1,1)); m_meshCurrent->clear(); } @@ -45,11 +45,11 @@ template void CubicSurfaceExtractorWithNormals::execute() { - for(int16_t z = m_regSizeInVoxels.getLowerCorner().getZ(); z < m_regSizeInVoxels.getUpperCorner().getZ(); z++) + for(int32_t z = m_regSizeInVoxels.getLowerCorner().getZ(); z < m_regSizeInVoxels.getUpperCorner().getZ(); z++) { - for(int16_t y = m_regSizeInVoxels.getLowerCorner().getY(); y < m_regSizeInVoxels.getUpperCorner().getY(); y++) + for(int32_t y = m_regSizeInVoxels.getLowerCorner().getY(); y < m_regSizeInVoxels.getUpperCorner().getY(); y++) { - for(int16_t x = m_regSizeInVoxels.getLowerCorner().getX(); x < m_regSizeInVoxels.getUpperCorner().getX(); x++) + for(int32_t x = m_regSizeInVoxels.getLowerCorner().getX(); x < m_regSizeInVoxels.getUpperCorner().getX(); x++) { uint16_t regX = x - m_regSizeInVoxels.getLowerCorner().getX(); uint16_t regY = y - m_regSizeInVoxels.getLowerCorner().getY(); Index: library/PolyVoxCore/include/Region.h =================================================================== --- library/PolyVoxCore/include/Region.h (revision 1406) +++ library/PolyVoxCore/include/Region.h (working copy) @@ -37,28 +37,28 @@ { public: Region(); - Region(const Vector3DInt16& v3dLowerCorner, const Vector3DInt16& v3dUpperCorner); + Region(const Vector3DInt32& v3dLowerCorner, const Vector3DInt32& v3dUpperCorner); - const Vector3DInt16& getLowerCorner(void) const; - const Vector3DInt16& getUpperCorner(void) const; + const Vector3DInt32& getLowerCorner(void) const; + const Vector3DInt32& getUpperCorner(void) const; - void setLowerCorner(const Vector3DInt16& v3dLowerCorner); - void setUpperCorner(const Vector3DInt16& v3dUpperCorner); + void setLowerCorner(const Vector3DInt32& v3dLowerCorner); + void setUpperCorner(const Vector3DInt32& v3dUpperCorner); bool containsPoint(const Vector3DFloat& pos, float boundary = 0.0f) const; - bool containsPoint(const Vector3DInt16& pos, uint8_t boundary = 0) const; + bool containsPoint(const Vector3DInt32& pos, uint8_t boundary = 0) const; void cropTo(const Region& other); - int16_t depth(void) const; - int16_t height(void) const; - void shift(const Vector3DInt16& amount); - void shiftLowerCorner(const Vector3DInt16& amount); - void shiftUpperCorner(const Vector3DInt16& amount); - Vector3DInt16 dimensions(void); - int16_t width(void) const; + int32_t depth(void) const; + int32_t height(void) const; + void shift(const Vector3DInt32& amount); + void shiftLowerCorner(const Vector3DInt32& amount); + void shiftUpperCorner(const Vector3DInt32& amount); + Vector3DInt32 dimensions(void); + int32_t width(void) const; private: - Vector3DInt16 m_v3dLowerCorner; - Vector3DInt16 m_v3dUpperCorner; + Vector3DInt32 m_v3dLowerCorner; + Vector3DInt32 m_v3dUpperCorner; //FIXME - This variable is unused, but without it the OpenGL example crashes in release mode //when the volume size is 128^3 and the level of detail is 2. Very strange, but consistant. Index: library/PolyVoxCore/include/SurfaceExtractor.h =================================================================== --- library/PolyVoxCore/include/SurfaceExtractor.h (revision 1406) +++ library/PolyVoxCore/include/SurfaceExtractor.h (working copy) @@ -71,9 +71,9 @@ VolumeSampler m_sampVolume; //Holds a position in volume space. - int16_t iXVolSpace; - int16_t iYVolSpace; - int16_t iZVolSpace; + int32_t iXVolSpace; + int32_t iYVolSpace; + int32_t iZVolSpace; //Holds a position in region space. uint16_t uXRegSpace; Index: CMakeLists.txt =================================================================== --- CMakeLists.txt (revision 1406) +++ CMakeLists.txt (working copy) @@ -40,9 +40,9 @@ OPTION(ENABLE_EXAMPLES "Should the examples be built" ON) IF(ENABLE_EXAMPLES) ADD_SUBDIRECTORY(examples/Basic) - ADD_SUBDIRECTORY(examples/OpenGL) + #ADD_SUBDIRECTORY(examples/OpenGL) ADD_DEPENDENCIES(BasicExample PolyVoxCore PolyVoxUtil) - ADD_DEPENDENCIES(OpenGLExample PolyVoxCore PolyVoxUtil) + #ADD_DEPENDENCIES(OpenGLExample PolyVoxCore PolyVoxUtil) ENDIF(ENABLE_EXAMPLES) INCLUDE(Packaging.cmake) Index: examples/Basic/main.cpp =================================================================== --- examples/Basic/main.cpp (revision 1406) +++ examples/Basic/main.cpp (working copy) @@ -25,6 +25,7 @@ #include "MaterialDensityPair.h" #include "CubicSurfaceExtractorWithNormals.h" +#include "SurfaceExtractor.h" #include "SurfaceMesh.h" #include "Volume.h" @@ -342,7 +343,8 @@ mSeed = seed; mStart = true; } - +// #define PERLIN_SLOW +#ifdef PERLIN_SLOW void createPerlinVolumeSlow(Volume& volData) { Perlin perlin(2,8,1,234); @@ -381,7 +383,7 @@ } } } - +#endif // PERLIN_SLOW /*void createPerlinVolumeFast(Volume& volData) { Perlin perlin(2,8,1,234); @@ -430,20 +432,49 @@ } }*/ -void createPerlinTerrain(Volume& volData) +void createPerlinTerrainChunk(Volume& volData, PolyVox::Region reg) { + Perlin perlin(2,2,1,234); + for(int x = reg.getLowerCorner().getX(); x < reg.getUpperCorner().getX(); x++) { + for(int y = reg.getLowerCorner().getY(); y < reg.getUpperCorner().getY(); y++) { + float perlinVal = perlin.Get(x / 254.0f , y / 254.0f); + perlinVal += 1.0f; + perlinVal *= 0.5f; + perlinVal *= 255.0f; + + for(int z = reg.getLowerCorner().getZ(); z < reg.getUpperCorner().getZ(); z++) { + MaterialDensityPair44 voxel; + if(z < perlinVal) + { + voxel.setMaterial(245); + voxel.setDensity(MaterialDensityPair44::getMaxDensity()); + } + else + { + voxel.setMaterial(0); + voxel.setDensity(MaterialDensityPair44::getMinDensity()); + } + + volData.setVoxelAt(x, y, z, voxel); + } + } + } +} +#ifdef NOT_DEFINED_1234123532 +void createPerlinTerrain(Volume& volData, Vector3DInt16 size) +{ Perlin perlin(2,2,1,234); - for(int x = 1; x < volData.getWidth()-1; x++) + for(int x = 1; x < size.getX()-1; x++) { - std::cout << x << std::endl; - for(int y = 1; y < volData.getHeight()-1; y++) + std::cout << "." << std::flush; + for(int y = 1; y < size.getY()-1; y++) { - float perlinVal = perlin.Get(x / static_cast(volData.getHeight()-1), y / static_cast(volData.getDepth()-1)); + float perlinVal = perlin.Get(x / static_cast(size.getZ()-1), y / static_cast(size.getZ()-1)); perlinVal += 1.0f; perlinVal *= 0.5f; - perlinVal *= volData.getWidth(); - for(int z = 1; z < volData.getDepth()-1; z++) + perlinVal *= size.getX(); + for(int z = 1; z < size.getZ()-1; z++) { MaterialDensityPair44 voxel; if(z < perlinVal) @@ -501,46 +532,39 @@ } } } +#endif //NOT_DEFINED_1234123532 int main(int argc, char *argv[]) { - //Create and show the Qt OpenGL window - QApplication app(argc, argv); - OpenGLWidget openGLWidget(0); - openGLWidget.show(); + //Create and show the Qt OpenGL window + QApplication app(argc, argv); + OpenGLWidget openGLWidget(0); + openGLWidget.show(); - //Create an empty volume and then place a sphere in it - Volume volData(256, 256, 256); - volData.useCompatibilityMode(); - //createSphereInVolume(volData, 30); - createPerlinTerrain(volData); - //createPerlinVolumeSlow(volData); - std::cout << "Memory usage: " << volData.calculateSizeInBytes() << std::endl; - //volData.setBlockCacheSize(8); - std::cout << "Memory usage: " << volData.calculateSizeInBytes() << std::endl; - std::cout << "Compression ratio: " << volData.calculateCompressionRatio() << std::endl; + //Create an empty volume and then place a sphere in it + Volume volData; + volData.setBlockCacheSize(4096); + volData.m_fLoad = boost::bind(&createPerlinTerrainChunk, boost::ref(volData), _1); + //createSphereInVolume(volData, 30); + //createPerlinTerrain(volData, Vector3DInt16(255,255,255)); + //createPerlinVolumeSlow(volData); + std::cout << "Memory usage of empty volume: " << volData.calculateSizeInBytes() << std::endl; + //volData.setBlockCacheSize(8); - /*srand(12345); - for(int ct = 0; ct < 1000; ct++) - { - std::cout << ct << std::endl; - int x = rand() % volData.getWidth(); - int y = rand() % volData.getHeight(); - int z = rand() % volData.getDepth(); + //Extract the surface + SurfaceMesh mesh; + PolyVox::Region reg(Vector3DInt32(1,1,1), Vector3DInt32(1022,253,253)); + reg.shift(Vector3DInt32(100000,1,1)); + CubicSurfaceExtractorWithNormals surfaceExtractor(&volData, reg, &mesh); + surfaceExtractor.execute(); - int r = rand() % 20; + std::cout << "Memory usage after surface extraction: " << volData.calculateSizeInBytes() << std::endl; + std::cout << "Compression ratio: " << volData.calculateCompressionRatio() << std::endl; - createSphereInVolume(volData, Vector3DFloat(x,y,z), r); - }*/ + // this will work, because the coordinates of the mesh are relative to the lower corner of the region that was extracted, otherwise our drawing would be somewhere totally else... + //Pass the surface to the OpenGL window + openGLWidget.setSurfaceMeshToRender(mesh); - //Extract the surface - SurfaceMesh mesh; - CubicSurfaceExtractorWithNormals surfaceExtractor(&volData, volData.getEnclosingRegion(), &mesh); - surfaceExtractor.execute(); - - //Pass the surface to the OpenGL window - openGLWidget.setSurfaceMeshToRender(mesh); - - //Run the message pump. - return app.exec(); + //Run the message pump. + return app.exec(); }