PolyVox
0.3.0-dev
Open source voxel management library
|
The LargeVolume class provides a memory efficient method of storing voxel data while also allowing fast access and modification. More...
#include <LargeVolume.h>
Classes | |
struct | LoadedBlock |
class | Sampler |
Public Member Functions | |
LargeVolume (polyvox_function< void(const ConstVolumeProxy< VoxelType > &, const Region &)> dataRequiredHandler, polyvox_function< void(const ConstVolumeProxy< VoxelType > &, const Region &)> dataOverflowHandler, uint16_t uBlockSideLength=32) | |
Constructor for creating a very large paging volume. | |
LargeVolume (const Region ®Valid, Compressor *pCompressor=0, polyvox_function< void(const ConstVolumeProxy< VoxelType > &, const Region &)> dataRequiredHandler=0, polyvox_function< void(const ConstVolumeProxy< VoxelType > &, const Region &)> dataOverflowHandler=0, bool bPagingEnabled=false, uint16_t uBlockSideLength=32) | |
Constructor for creating a fixed size volume. | |
~LargeVolume () | |
Destructor. | |
VoxelType | getVoxel (int32_t uXPos, int32_t uYPos, int32_t uZPos) const |
Gets a voxel at the position given by x,y,z coordinates. | |
VoxelType | getVoxel (const Vector3DInt32 &v3dPos) const |
Gets a voxel at the position given by a 3D vector. | |
VoxelType | getVoxelAt (int32_t uXPos, int32_t uYPos, int32_t uZPos) const |
Gets a voxel at the position given by x,y,z coordinates. | |
VoxelType | getVoxelAt (const Vector3DInt32 &v3dPos) const |
Gets a voxel at the position given by a 3D vector. | |
VoxelType | getVoxelWithWrapping (int32_t uXPos, int32_t uYPos, int32_t uZPos, WrapMode eWrapMode=WrapModes::Border, VoxelType tBorder=VoxelType()) const |
Gets a voxel at the position given by x,y,z coordinates. | |
VoxelType | getVoxelWithWrapping (const Vector3DInt32 &v3dPos, WrapMode eWrapMode=WrapModes::Border, VoxelType tBorder=VoxelType()) const |
Gets a voxel at the position given by a 3D vector. | |
void | setMaxNumberOfUncompressedBlocks (uint32_t uMaxNumberOfUncompressedBlocks) |
Sets the number of blocks for which uncompressed data is stored. | |
void | setMaxNumberOfBlocksInMemory (uint32_t uMaxNumberOfBlocksInMemory) |
Sets the number of blocks which can be in memory before the paging system starts unloading them. | |
bool | setVoxelAt (int32_t uXPos, int32_t uYPos, int32_t uZPos, VoxelType tValue) |
Sets the voxel at the position given by x,y,z coordinates. | |
bool | setVoxelAt (const Vector3DInt32 &v3dPos, VoxelType tValue) |
Sets the voxel at the position given by a 3D vector. | |
void | prefetch (Region regPrefetch) |
Tries to ensure that the voxels within the specified Region are loaded into memory. | |
void | flush (Region regFlush) |
Ensures that any voxels within the specified Region are removed from memory. | |
void | flushAll () |
Removes all voxels from memory. | |
void | clearBlockCache (void) |
Empties the cache of uncompressed blocks. | |
float | calculateCompressionRatio (void) |
Calculates the approximate compression ratio of the store volume data. | |
uint32_t | calculateSizeInBytes (void) |
Calculates approximatly how many bytes of memory the volume is currently using. | |
Public Member Functions inherited from PolyVox::BaseVolume< VoxelType > | |
VoxelType | getBorderValue (void) const |
Gets the value used for voxels which are outside the volume. | |
const Region & | getEnclosingRegion (void) const |
Gets a Region representing the extents of the Volume. | |
int32_t | getWidth (void) const |
Gets the width of the volume in voxels. | |
int32_t | getHeight (void) const |
Gets the height of the volume in voxels. | |
int32_t | getDepth (void) const |
Gets the depth of the volume in voxels. | |
int32_t | getLongestSideLength (void) const |
Gets the length of the longest side in voxels. | |
int32_t | getShortestSideLength (void) const |
Gets the length of the shortest side in voxels. | |
float | getDiagonalLength (void) const |
Gets the length of the diagonal in voxels. | |
VoxelType | getVoxel (int32_t uXPos, int32_t uYPos, int32_t uZPos) const |
Gets a voxel at the position given by x,y,z coordinates. | |
VoxelType | getVoxel (const Vector3DInt32 &v3dPos) const |
Gets a voxel at the position given by a 3D vector. | |
VoxelType | getVoxelAt (int32_t uXPos, int32_t uYPos, int32_t uZPos) const |
Gets a voxel at the position given by x,y,z coordinates. | |
VoxelType | getVoxelAt (const Vector3DInt32 &v3dPos) const |
Gets a voxel at the position given by a 3D vector. | |
VoxelType | getVoxelWithWrapping (int32_t uXPos, int32_t uYPos, int32_t uZPos, WrapMode eWrapMode=WrapModes::Border, VoxelType tBorder=VoxelType()) const |
Gets a voxel at the position given by x,y,z coordinates. | |
VoxelType | getVoxelWithWrapping (const Vector3DInt32 &v3dPos, WrapMode eWrapMode=WrapModes::Border, VoxelType tBorder=VoxelType()) const |
Gets a voxel at the position given by a 3D vector. | |
void | setBorderValue (const VoxelType &tBorder) |
Sets the value used for voxels which are outside the volume. | |
bool | setVoxelAt (int32_t uXPos, int32_t uYPos, int32_t uZPos, VoxelType tValue) |
Sets the voxel at the position given by x,y,z coordinates. | |
bool | setVoxelAt (const Vector3DInt32 &v3dPos, VoxelType tValue) |
Sets the voxel at the position given by a 3D vector. | |
uint32_t | calculateSizeInBytes (void) |
Calculates approximatly how many bytes of memory the volume is currently using. | |
Protected Member Functions | |
LargeVolume (const LargeVolume &rhs) | |
Copy constructor. | |
LargeVolume & | operator= (const LargeVolume &rhs) |
Assignment operator. | |
Protected Member Functions inherited from PolyVox::BaseVolume< VoxelType > | |
BaseVolume (const Region ®Valid) | |
Constructor for creating a fixed size volume. | |
BaseVolume (const BaseVolume &rhs) | |
Copy constructor. | |
~BaseVolume () | |
Destructor. | |
BaseVolume & | operator= (const BaseVolume &rhs) |
Assignment operator. | |
Friends | |
class | ConstVolumeProxy< VoxelType > |
Additional Inherited Members | |
Public Types inherited from PolyVox::BaseVolume< VoxelType > | |
typedef VoxelType | VoxelType |
Protected Attributes inherited from PolyVox::BaseVolume< VoxelType > | |
Region | m_regValidRegion |
int32_t | m_uLongestSideLength |
int32_t | m_uShortestSideLength |
float | m_fDiagonalLength |
VoxelType | m_tBorderValue |
The LargeVolume class provides a memory efficient method of storing voxel data while also allowing fast access and modification.
A LargeVolume is essentially a 3D array in which each element (or voxel) is identified by a three dimensional (x,y,z) coordinate. We use the LargeVolume class to store our data in an efficient way, and it is the input to many of the algorithms (such as the surface extractors) which form the heart of PolyVox. The LargeVolume class is templatised so that different types of data can be stored within each voxel.
The following code snippet shows how to construct a volume and demonstrates basic usage:
In this particular example each voxel in the LargeVolume is of type 'Material8', as specified by the template parameter. This is one of several predefined voxel types, and it is also possible to define your own. The Material8 type simply holds an integer value where zero represents empty space and any other value represents a solid material.
The LargeVolume constructor takes a Region as a parameter. This specifies the valid range of voxels which can be held in the volume, so in this particular case the valid voxel positions are (0,0,0) to (63, 127, 255). Attempts to access voxels outside this range will result is accessing the border value (see getBorderValue() and setBorderValue()). PolyVox also has support for near infinite volumes which will be discussed later.
Access to individual voxels is provided via the setVoxelAt() and getVoxelAt() member functions. Advanced users may also be interested in the Sampler class for faster read-only access to a large number of voxels.
Lastly the example prints out some properties of the LargeVolume. Note that the dimentsions getWidth(), getHeight(), and getDepth() are inclusive, such that the width is 64 when the range of valid x coordinates goes from 0 to 63.
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 LargeVolume 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 LargeVolume 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 stores 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.
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 areas of the 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 may wish to 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).
The compression scheme described previously will typically allow you to load several billion voxels into a few hundred megabytes of memory, though as explained the exact compression rate is highly dependant on your data. If you have more data than this then PolyVox provides a mechanism by which parts of the volume can be paged out of memory by calling user supplied callback functions. This mechanism allows a potentially unlimited amount of data to be loaded, provided the user is able to take responsibility for storing any data which PolyVox cannot fit in memory, and then returning it back to PolyVox on demand. For example, the user might choose to temporarily store this data on disk or stream it to a remote database.
You can construct such a LargeVolume as follows:
Essentially you are providing an extension to the LargeVolume class - a way for data to be stored once PolyVox has run out of memory for it. Note that you don't actually have to do anything with the data - you could simply decide that once it gets removed from memory it doesn't matter anymore. But you still need to be ready to then provide something to PolyVox (even if it's just default data) in the event that it is requested.
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.
The LargeVolume class does not make any guarentees about thread safety. You should ensure that all accesses are performed from the same thread. This is true even if you are only reading data from the volume, as concurrently reading from different threads can invalidate the contents of the block cache (amoung other problems).
Definition at line 159 of file LargeVolume.h.
PolyVox::LargeVolume< VoxelType >::LargeVolume | ( | polyvox_function< void(const ConstVolumeProxy< VoxelType > &, const Region &)> | dataRequiredHandler, |
polyvox_function< void(const ConstVolumeProxy< VoxelType > &, const Region &)> | dataOverflowHandler, | ||
uint16_t | uBlockSideLength = 32 |
||
) |
Constructor for creating a very large paging volume.
When construncting a very large volume you need to be prepared to handle the scenario where there is so much data that PolyVox cannot fit it all in memory.
When PolyVox runs out of memory, it identifies the least recently used data and hands it back to the application via a callback function. It is then the responsibility of the application to store this data until PolyVox needs it again (as signalled by another callback function). Please see the LargeVolume class documentation for a full description of this process and the required function signatures. If you really don't want to handle these events then you can provide null pointers here, in which case the data will be discarded and/or filled with default values.
dataRequiredHandler | The callback function which will be called when PolyVox tries to use data which is not currently in memory. |
dataOverflowHandler | The callback function which will be called when PolyVox has too much data and needs to remove some from memory. |
uBlockSideLength | The size of the blocks making up the volume. Small blocks will compress/decompress faster, but there will also be more of them meaning voxel access could be slower. |
Definition at line 39 of file LargeVolume.inl.
PolyVox::LargeVolume< VoxelType >::LargeVolume | ( | const Region & | regValid, |
Compressor * | pCompressor = 0 , |
||
polyvox_function< void(const ConstVolumeProxy< VoxelType > &, const Region &)> | dataRequiredHandler = 0 , |
||
polyvox_function< void(const ConstVolumeProxy< VoxelType > &, const Region &)> | dataOverflowHandler = 0 , |
||
bool | bPagingEnabled = false , |
||
uint16_t | uBlockSideLength = 32 |
||
) |
Constructor for creating a fixed size volume.
This constructor creates a volume with a fixed size which is specified as a parameter.
By default this constructor will not enable paging but you can override this if desired. If you do wish to enable paging then you are required to provide the call back function (see the other LargeVolume constructor).
regValid | Specifies the minimum and maximum valid voxel positions. |
pCompressor | An implementation of the Compressor interface which is used to compress blocks in memory. |
dataRequiredHandler | The callback function which will be called when PolyVox tries to use data which is not currently in momory. |
dataOverflowHandler | The callback function which will be called when PolyVox has too much data and needs to remove some from memory. |
bPagingEnabled | Controls whether or not paging is enabled for this LargeVolume. |
uBlockSideLength | The size of the blocks making up the volume. Small blocks will compress/decompress faster, but there will also be more of them meaning voxel access could be slower. |
Definition at line 64 of file LargeVolume.inl.
PolyVox::LargeVolume< VoxelType >::~LargeVolume | ( | ) |
Destructor.
Destroys the volume The destructor will call flushAll() to ensure that a paging volume has the chance to save it's data via the dataOverflowHandler() if desired.
Definition at line 100 of file LargeVolume.inl.
|
protected |
Copy constructor.
This function should never be called.
Copying volumes by value would be expensive, and we want to prevent users from doing it by accident (such as when passing them as paramenters to functions). That said, there are times when you really do want to make a copy of a volume and in this case you should look at the VolumeResampler.
Definition at line 91 of file LargeVolume.inl.
float PolyVox::LargeVolume< VoxelType >::calculateCompressionRatio | ( | void | ) |
Calculates the approximate compression ratio of the store volume data.
Note: This function needs reviewing for accuracy...
Definition at line 682 of file LargeVolume.inl.
uint32_t PolyVox::LargeVolume< VoxelType >::calculateSizeInBytes | ( | void | ) |
Calculates approximatly how many bytes of memory the volume is currently using.
Note: This function needs reviewing for accuracy...
Definition at line 693 of file LargeVolume.inl.
void PolyVox::LargeVolume< VoxelType >::clearBlockCache | ( | void | ) |
Empties the cache of uncompressed blocks.
Definition at line 434 of file LargeVolume.inl.
void PolyVox::LargeVolume< VoxelType >::flush | ( | Region | regFlush | ) |
Ensures that any voxels within the specified Region are removed from memory.
Removes all voxels in the specified Region from memory, and calls dataOverflowHandler() to ensure the application has a chance to store the data.
It is possible that there are no voxels loaded in the Region, in which case the function will have no effect.
Definition at line 392 of file LargeVolume.inl.
void PolyVox::LargeVolume< VoxelType >::flushAll | ( | ) |
Removes all voxels from memory.
Removes all voxels from memory, and calls dataOverflowHandler() to ensure the application has a chance to store the data.
Definition at line 377 of file LargeVolume.inl.
VoxelType PolyVox::LargeVolume< VoxelType >::getVoxel | ( | int32_t | uXPos, |
int32_t | uYPos, | ||
int32_t | uZPos | ||
) | const |
Gets a voxel at the position given by x,y,z
coordinates.
uXPos | The x position of the voxel |
uYPos | The y position of the voxel |
uZPos | The z position of the voxel |
Definition at line 125 of file LargeVolume.inl.
Referenced by PolyVox::LargeVolume< VoxelType >::Sampler::getSubSampledVoxel().
VoxelType PolyVox::LargeVolume< VoxelType >::getVoxel | ( | const Vector3DInt32 & | v3dPos | ) | const |
Gets a voxel at the position given by a 3D vector.
v3dPos | The 3D position of the voxel |
Definition at line 147 of file LargeVolume.inl.
VoxelType PolyVox::LargeVolume< VoxelType >::getVoxelAt | ( | int32_t | uXPos, |
int32_t | uYPos, | ||
int32_t | uZPos | ||
) | const |
Gets a voxel at the position given by x,y,z
coordinates.
uXPos | The x position of the voxel |
uYPos | The y position of the voxel |
uZPos | The z position of the voxel |
Definition at line 159 of file LargeVolume.inl.
Referenced by PolyVox::LargeVolume< VoxelType >::Sampler::getVoxel().
VoxelType PolyVox::LargeVolume< VoxelType >::getVoxelAt | ( | const Vector3DInt32 & | v3dPos | ) | const |
Gets a voxel at the position given by a 3D vector.
v3dPos | The 3D position of the voxel |
Definition at line 186 of file LargeVolume.inl.
VoxelType PolyVox::LargeVolume< VoxelType >::getVoxelWithWrapping | ( | int32_t | uXPos, |
int32_t | uYPos, | ||
int32_t | uZPos, | ||
WrapMode | eWrapMode = WrapModes::Border , |
||
VoxelType | tBorder = VoxelType() |
||
) | const |
Gets a voxel at the position given by x,y,z
coordinates.
uXPos | The x position of the voxel |
uYPos | The y position of the voxel |
uZPos | The z position of the voxel |
Definition at line 198 of file LargeVolume.inl.
VoxelType PolyVox::LargeVolume< VoxelType >::getVoxelWithWrapping | ( | const Vector3DInt32 & | v3dPos, |
WrapMode | eWrapMode = WrapModes::Border , |
||
VoxelType | tBorder = VoxelType() |
||
) | const |
Gets a voxel at the position given by a 3D vector.
v3dPos | The 3D position of the voxel |
Definition at line 242 of file LargeVolume.inl.
|
protected |
Assignment operator.
This function should never be called.
Copying volumes by value would be expensive, and we want to prevent users from doing it by accident (such as when passing them as paramenters to functions). That said, there are times when you really do want to make a copy of a volume and in this case you should look at the Volumeresampler.
Definition at line 113 of file LargeVolume.inl.
void PolyVox::LargeVolume< VoxelType >::prefetch | ( | Region | regPrefetch | ) |
Tries to ensure that the voxels within the specified Region are loaded into memory.
Note that if MaxNumberOfBlocksInMemory is not large enough to support the region this function will only load part of the region.
In this case it is undefined which parts will actually be loaded. If all the voxels in the given region are already loaded, this function will not do anything. Other voxels might be unloaded to make space for the new voxels.
regPrefetch | The Region of voxels to prefetch into memory. |
Definition at line 320 of file LargeVolume.inl.
void PolyVox::LargeVolume< VoxelType >::setMaxNumberOfBlocksInMemory | ( | uint32_t | uMaxNumberOfBlocksInMemory | ) |
Sets the number of blocks which can be in memory before the paging system starts unloading them.
Increasing the number of blocks in memory causes fewer calls to dataRequiredHandler()/dataOverflowHandler()
uMaxNumberOfBlocksInMemory | The number of blocks |
Definition at line 266 of file LargeVolume.inl.
void PolyVox::LargeVolume< VoxelType >::setMaxNumberOfUncompressedBlocks | ( | uint32_t | uMaxNumberOfUncompressedBlocks | ) |
Sets the number of blocks for which uncompressed data is stored.
Increasing the size of the block cache will increase memory but may improve performance.
You may want to set this to a large value (e.g. 1024) when you are first loading your volume data and then set it to a smaller value (e.g.64) for general processing.
uMaxNumberOfUncompressedBlocks | The number of blocks for which uncompressed data can be cached. |
Definition at line 254 of file LargeVolume.inl.
bool PolyVox::LargeVolume< VoxelType >::setVoxelAt | ( | int32_t | uXPos, |
int32_t | uYPos, | ||
int32_t | uZPos, | ||
VoxelType | tValue | ||
) |
Sets the voxel at the position given by x,y,z
coordinates.
uXPos | the x position of the voxel |
uYPos | the y position of the voxel |
uZPos | the z position of the voxel |
tValue | the value to which the voxel will be set |
Definition at line 283 of file LargeVolume.inl.
bool PolyVox::LargeVolume< VoxelType >::setVoxelAt | ( | const Vector3DInt32 & | v3dPos, |
VoxelType | tValue | ||
) |
Sets the voxel at the position given by a 3D vector.
v3dPos | the 3D position of the voxel |
tValue | the value to which the voxel will be set |
Definition at line 309 of file LargeVolume.inl.
|
friend |
Definition at line 232 of file LargeVolume.h.