44 #ifndef _INCLUDED_Field3D_SparseField_H_
45 #define _INCLUDED_Field3D_SparseField_H_
51 #include <boost/lexical_cast.hpp>
56 #define BLOCK_ORDER 4 // 2^BLOCK_ORDER is the block size along each axis
68 template <
class Field_T>
70 template <
class Field_T>
84 template <
typename Data_T>
98 Data_T&
value(
int i,
int j,
int k,
int blockOrder)
100 {
return data[(k << blockOrder << blockOrder) + (j << blockOrder) + i]; }
104 const Data_T&
value(
int i,
int j,
int k,
int blockOrder)
const
105 {
return data[(k << blockOrder << blockOrder) + (j << blockOrder) + i]; }
109 { this->
data.resize(n); }
113 { std::vector<Data_T>().swap(
data); }
159 template <
class Data_T>
167 typedef boost::intrusive_ptr<SparseField>
Ptr;
168 typedef std::vector<Ptr>
Vec;
180 return "SparseField";
248 template <
typename Functor_T>
252 int blockId(
int blockI,
int blockJ,
int blockK)
const;
257 void getBlockCoord(
int i,
int j,
int k,
int &bi,
int &bj,
int &bk)
const;
262 void getVoxelInBlock(
int i,
int j,
int k,
int &vi,
int &vj,
int &vk)
const;
276 virtual Data_T
value(
int i,
int j,
int k)
const;
277 virtual long long int memSize()
const;
284 virtual Data_T&
lvalue(
int i,
int j,
int k);
290 Data_T
fastValue(
int i,
int j,
int k)
const;
312 class const_iterator;
315 const_iterator
cbegin()
const;
319 const_iterator
cend()
const;
322 const_iterator
cend(
const Box3i &subset)
const;
342 class block_iterator;
354 void addReference(
const std::string &filename,
const std::string &layerPath,
355 int valuesPerBlock,
int occupiedBlocks);
454 template <
typename Data_T>
466 const V3i &validSize,
const V3i &blockSize)
469 Data_T first = block.
data[0];
472 if (validSize == blockSize) {
474 for (
typename std::vector<Data_T>::const_iterator i = block.
data.begin();
475 i != block.
data.end(); ++i) {
484 for (
typename std::vector<Data_T>::const_iterator i = block.
data.begin();
485 i != block.
data.end(); ++i, ++x) {
486 if (x >= blockSize.x) {
489 if (y >= blockSize.y) {
494 if (x >= validSize.x || y >= validSize.y || z >= validSize.z) {
506 retEmptyValue = first;
516 template <
typename Data_T>
517 inline bool isAnyLess(
const Data_T &left,
const Data_T &right)
519 return (std::abs(left) < right);
527 return (std::abs(left.x) < right.x ||
528 std::abs(left.y) < right.y ||
529 std::abs(left.z) < right.z );
537 return (std::abs(left.x) < right.x ||
538 std::abs(left.y) < right.y ||
539 std::abs(left.z) < right.z );
547 return (std::abs(left.x) < right.x ||
548 std::abs(left.y) < right.y ||
549 std::abs(left.z) < right.z );
557 template <
typename Data_T>
573 const V3i &validSize,
const V3i &blockSize)
576 Data_T first = block.
data[0];
578 bool allGreater =
true;
579 if (validSize == blockSize) {
581 for (
typename std::vector<Data_T>::const_iterator i = block.
data.begin();
582 i != block.
data.end(); ++i) {
591 for (
typename std::vector<Data_T>::const_iterator i = block.
data.begin();
592 i != block.
data.end(); ++i, ++x) {
593 if (x >= blockSize.x) {
596 if (y >= blockSize.y) {
601 if (x >= validSize.x || y >= validSize.y || z >= validSize.z) {
612 retEmptyValue = first;
629 template <
class Data_T>
637 : x(currentPos.x), y(currentPos.y), z(currentPos.z),
638 m_p(NULL), m_blockIsActivated(false),
640 m_blockId(-1), m_window(window), m_field(&field)
642 m_manager = m_field->m_fileManager;
643 setupNextBlock(x, y, z);
646 if (m_manager && m_blockId >= 0 &&
647 m_blockId < static_cast<int>(m_field->m_blocks.size())) {
648 if (m_field->m_blocks[m_blockId].isAllocated)
649 m_manager->decBlockRef<Data_T>(m_field->m_fileId, m_blockId);
654 bool resetPtr =
false;
656 if (x == m_window.max.x) {
657 if (y == m_window.max.y) {
671 ++m_blockStepsTicker;
673 if (!m_isEmptyBlock && (!m_manager || m_blockIsActivated))
680 m_blockStepsTicker = 0;
681 setupNextBlock(x, y, z);
685 template <
class Iter_T>
686 inline bool operator == (
const Iter_T &rhs)
const
688 return x == rhs.x && y == rhs.y && z == rhs.z;
690 template <
class Iter_T>
691 inline bool operator != (
const Iter_T &rhs)
const
693 return x != rhs.x || y != rhs.y || z != rhs.z;
697 if (!m_isEmptyBlock && m_manager && !m_blockIsActivated) {
698 m_manager->activateBlock<Data_T>(m_field->m_fileId, m_blockId);
699 m_blockIsActivated =
true;
700 const Block &block = m_field->m_blocks[m_blockId];
702 m_field->getVoxelInBlock(x, y, z, vi, vj, vk);
707 inline const Data_T* operator -> ()
const
709 if (!m_isEmptyBlock && m_manager && !m_blockIsActivated) {
711 manager->
activateBlock<Data_T>(m_field->m_fileId, m_blockId);
712 m_blockIsActivated =
true;
713 const Block &block = m_field->m_blocks[m_blockId];
715 m_field->getVoxelInBlock(x, y, z, vi, vj, vk);
734 void setupNextBlock(
int i,
int j,
int k)
736 m_field->applyDataWindowOffset(i, j, k);
737 m_field->getBlockCoord(i, j, k, m_blockI, m_blockJ, m_blockK);
738 int oldBlockId = m_blockId;
739 m_blockId = m_field->blockId(m_blockI, m_blockJ, m_blockK);
740 if (m_manager && oldBlockId != m_blockId &&
742 oldBlockId < static_cast<int>(m_field->m_blocks.size()) &&
743 m_field->m_blocks[oldBlockId].isAllocated) {
744 m_manager->decBlockRef<Data_T>(m_field->m_fileId, oldBlockId);
746 if (m_blockId >= m_field->m_blockXYSize * m_field->m_blockRes.z) {
747 m_isEmptyBlock =
true;
751 const Block &block = m_field->m_blocks[m_blockId];
753 m_field->getVoxelInBlock(i, j, k, vi, vj, vk);
754 m_blockStepsTicker = vi;
756 if (m_manager && oldBlockId != m_blockId && m_blockId >= 0) {
757 m_manager->incBlockRef<Data_T>(m_field->m_fileId, m_blockId);
766 m_isEmptyBlock =
false;
769 m_isEmptyBlock =
true;
771 if (m_field->m_fileManager) {
772 m_blockIsActivated =
false;
777 mutable const Data_T *
m_p;
802 template <
class Data_T>
810 : x(currentPos.x), y(currentPos.y), z(currentPos.z),
811 m_p(NULL), m_blockStepsTicker(0),
m_blockOrder(blockOrder),
812 m_blockId(-1), m_window(window), m_field(&field)
814 setupNextBlock(x, y, z);
818 bool resetPtr =
false;
820 if (x == m_window.max.x) {
821 if (y == m_window.max.y) {
835 ++m_blockStepsTicker;
844 m_blockStepsTicker = 0;
845 setupNextBlock(x, y, z);
849 inline bool operator == (
const iterator &rhs)
const
851 return x == rhs.
x && y == rhs.
y && z == rhs.
z;
853 inline bool operator != (
const iterator &rhs)
const
855 return x != rhs.
x || y != rhs.
y || z != rhs.
z;
859 if (m_field->m_fileManager) {
860 assert(
false &&
"Dereferencing iterator on a dynamic-read sparse field");
866 if (m_isEmptyBlock) {
868 m_field->lvalue(x, y, z);
870 setupNextBlock(x, y, z);
874 inline Data_T* operator -> ()
876 if (m_field->m_fileManager) {
877 assert(
false &&
"Dereferencing iterator on a dynamic-read sparse field");
883 if (m_isEmptyBlock) {
885 m_field->lvalue(x, y, z);
887 setupNextBlock(x, y, z);
896 void setupNextBlock(
int i,
int j,
int k)
898 m_field->applyDataWindowOffset(i, j, k);
899 m_field->getBlockCoord(i, j, k, m_blockI, m_blockJ, m_blockK);
900 m_blockId = m_field->blockId(m_blockI, m_blockJ, m_blockK);
901 if (m_blockId >= m_field->m_blockXYSize * m_field->m_blockRes.z) {
902 m_isEmptyBlock =
true;
905 Block &block = m_field->m_blocks[m_blockId];
907 m_field->getVoxelInBlock(i, j, k, vi, vj, vk);
908 m_blockStepsTicker = vi;
911 m_isEmptyBlock =
false;
914 m_isEmptyBlock =
true;
939 template <
class Data_T>
947 const V3i ¤tPos)
948 : x(currentPos.x), y(currentPos.y), z(currentPos.z),
949 m_window(window), m_field(field)
951 recomputeBlockBoundingBox();
956 if (x == m_window.max.x) {
957 if (y == m_window.max.y) {
968 recomputeBlockBoundingBox();
974 return x == rhs.
x && y == rhs.
y && z == rhs.
z;
979 return x != rhs.
x || y != rhs.
y || z != rhs.
z;
984 return m_currentBlockWindow;
989 void recomputeBlockBoundingBox()
993 box.min =
V3i(x * blockSize, y * blockSize, z * blockSize);
994 box.max = box.min +
V3i(blockSize - 1, blockSize - 1, blockSize - 1);
999 m_currentBlockWindow = box;
1013 template <
class Data_T>
1024 template <
class Data_T>
1033 template <
class Data_T>
1036 if (m_fileManager) {
1040 m_fileManager->removeFieldFromCache<Data_T>(m_fileId);
1046 template <
class Data_T>
1051 this->base::operator=(o);
1059 template <
class Data_T>
1070 m_fileManager->reference<Data_T>(o.
m_fileId);
1075 setupReferenceBlocks();
1082 m_fileManager = NULL;
1088 template <
class Data_T>
1090 const std::string &layerPath,
1095 m_fileId = m_fileManager->getNextId<Data_T>(filename, layerPath);
1098 m_fileManager->reference<Data_T>(m_fileId);
1100 reference.occupiedBlocks = occupiedBlocks;
1101 reference.setNumBlocks(m_blocks.size());
1106 template <
class Data_T>
1109 if (m_blocks.size() != o.
m_blocks.size())
return;
1111 typename std::vector<Sparse::SparseBlock<Data_T> >
::iterator b =
1113 typename std::vector<Sparse::SparseBlock<Data_T> >
::iterator bend =
1118 for (; b != bend; ++b, ++ob) {
1119 b->isAllocated = ob->isAllocated;
1120 b->emptyValue = ob->emptyValue;
1127 template <
class Data_T>
1130 if (!m_fileManager || m_fileId < 0)
return;
1133 m_fileManager->reference<Data_T>(m_fileId);
1137 reference.
blocks.begin();
1138 typename std::vector<Sparse::SparseBlock<Data_T> >
::iterator b =
1140 typename std::vector<Sparse::SparseBlock<Data_T> >
::iterator bend =
1142 int nextBlockIdx = 0;
1144 for (; b != bend; ++b, ++fb, ++bp) {
1145 if (b->isAllocated) {
1157 template <
class Data_T>
1163 typename std::vector<Block>::iterator i;
1164 typename std::vector<Block>::iterator end;
1165 for (i = m_blocks.begin(), end = m_blocks.end(); i != end; ++i) {
1166 i->emptyValue = value;
1172 template <
class Data_T>
1175 m_blockOrder = order;
1181 template <
class Data_T>
1184 return m_blockOrder;
1189 template <
class Data_T>
1192 return 1 << m_blockOrder;
1197 template <
class Data_T>
1201 applyDataWindowOffset(i, j, k);
1202 getBlockCoord(i, j, k, bi, bj, bk);
1203 return blockIsAllocated(bi, bj, bk);
1208 template <
class Data_T>
1211 const Block &block = m_blocks[blockId(bi, bj, bk)];
1217 template <
class Data_T>
1220 return m_blocks[blockId(bi, bj, bk)].emptyValue;
1225 template <
class Data_T>
1229 Block &block = m_blocks[blockId(bi, bj, bk)];
1231 deallocBlock(block, val);
1239 template <
class Data_T>
1242 return bi >= 0 && bj >= 0 && bk >= 0 &&
1243 bi < m_blockRes.x && bj < m_blockRes.y && bk < m_blockRes.z;
1248 template <
class Data_T>
1256 template <
class Data_T>
1257 template <
typename Functor_T>
1261 int numDeallocs = 0;
1262 typename std::vector<Block>::iterator i;
1270 V3i blockAllocSize(blockSize());
1273 for (i = m_blocks.begin(), bx=0, by=0, bz=0; i != m_blocks.end(); ++i, ++bx) {
1274 if (bx >= m_blockRes.x) {
1277 if (by >= m_blockRes.y) {
1282 validSize = blockAllocSize;
1283 if (bx == m_blockRes.x-1) {
1284 validSize.x = dataRes.x - bx * blockAllocSize.x;
1286 if (by == m_blockRes.y-1) {
1287 validSize.y = dataRes.y - by * blockAllocSize.y;
1289 if (bz == m_blockRes.z-1) {
1290 validSize.z = dataRes.z - bz * blockAllocSize.z;
1293 if (i->isAllocated) {
1294 if (func.check(*i, emptyValue, validSize, blockAllocSize)) {
1295 deallocBlock(*i, emptyValue);
1305 template <
class Data_T>
1308 return fastValue(i, j, k);
1313 template <
class Data_T>
1316 return fastLValue(i, j, k);
1321 template <
class Data_T>
1324 assert (i >= base::m_dataWindow.min.x);
1325 assert (i <= base::m_dataWindow.max.x);
1326 assert (j >= base::m_dataWindow.min.y);
1327 assert (j <= base::m_dataWindow.max.y);
1328 assert (k >= base::m_dataWindow.min.z);
1329 assert (k <= base::m_dataWindow.max.z);
1331 applyDataWindowOffset(i, j, k);
1334 getBlockCoord(i, j, k, bi, bj, bk);
1337 getVoxelInBlock(i, j, k, vi, vj, vk);
1339 int id = blockId(bi, bj, bk);
1341 const Block &block = m_blocks[id];
1344 if (m_fileManager) {
1345 m_fileManager->incBlockRef<Data_T>(m_fileId, id);
1346 m_fileManager->activateBlock<Data_T>(m_fileId, id);
1347 Data_T tmpValue = block.
value(vi, vj, vk, m_blockOrder);
1348 m_fileManager->decBlockRef<Data_T>(m_fileId, id);
1351 return block.
value(vi, vj, vk, m_blockOrder);
1361 template <
class Data_T>
1364 assert (i >= base::m_dataWindow.min.x);
1365 assert (i <= base::m_dataWindow.max.x);
1366 assert (j >= base::m_dataWindow.min.y);
1367 assert (j <= base::m_dataWindow.max.y);
1368 assert (k >= base::m_dataWindow.min.z);
1369 assert (k <= base::m_dataWindow.max.z);
1371 if (m_fileManager) {
1372 assert(
false &&
"Called fastLValue() on a dynamic-read sparse field");
1379 applyDataWindowOffset(i, j, k);
1382 getBlockCoord(i, j, k, bi, bj, bk);
1385 getVoxelInBlock(i, j, k, vi, vj, vk);
1387 int id = blockId(bi, bj, bk);
1388 Block &block = m_blocks[id];
1391 return block.
value(vi, vj, vk, m_blockOrder);
1395 block.
data.resize(1 << m_blockOrder << m_blockOrder << m_blockOrder);
1397 return block.
value(vi, vj, vk, m_blockOrder);
1403 template <
class Data_T>
1406 long long int blockSize = m_blocks.capacity() *
sizeof(
Block);
1407 long long int dataSize = 0;
1408 typename std::vector<Block>::const_iterator i;
1409 for (i = m_blocks.begin(); i != m_blocks.end(); ++i) {
1410 if (i->isAllocated) {
1411 dataSize += i->data.capacity() *
sizeof(Data_T);
1414 return sizeof(*this) + dataSize + blockSize;
1419 template <
class Data_T>
1425 return const_iterator(*
this, base::m_dataWindow, base::m_dataWindow.min,
1431 template <
class Data_T>
1435 if (subset.isEmpty())
1436 return cend(subset);
1442 template <
class Data_T>
1447 V3i(base::m_dataWindow.min.x,
1448 base::m_dataWindow.min.y,
1449 base::m_dataWindow.max.z + 1),
1455 template <
class Data_T>
1462 subset.max.z + 1), m_blockOrder);
1467 template <
class Data_T>
1473 return iterator(*
this, base::m_dataWindow,
1474 base::m_dataWindow.min, m_blockOrder); }
1478 template <
class Data_T>
1482 if (subset.isEmpty())
1484 return iterator(*
this, subset, subset.min, m_blockOrder);
1489 template <
class Data_T>
1493 return iterator(*
this, base::m_dataWindow,
1494 V3i(base::m_dataWindow.min.x,
1495 base::m_dataWindow.min.y,
1496 base::m_dataWindow.max.z + 1), m_blockOrder);
1501 template <
class Data_T>
1506 V3i(subset.min.x, subset.min.y, subset.max.z + 1),
1512 template <
class Data_T>
1524 template <
class Data_T>
1529 V3i(0, 0, m_blockRes.z));
1534 template <
class Data_T>
1538 V3f res(base::m_dataWindow.size() +
V3i(1));
1539 V3f blockRes(res / (1 << m_blockOrder));
1540 blockRes.x = ceil(blockRes.x);
1541 blockRes.y = ceil(blockRes.y);
1542 blockRes.z = ceil(blockRes.z);
1543 V3i intBlockRes(static_cast<int>(blockRes.x),
1544 static_cast<int>(blockRes.y),
1545 static_cast<int>(blockRes.z));
1546 m_blockRes = intBlockRes;
1547 m_blockXYSize = m_blockRes.x * m_blockRes.y;
1550 std::vector<Block>().swap(m_blocks);
1552 m_blocks.resize(intBlockRes.x * intBlockRes.y * intBlockRes.z);
1557 template <
class Data_T>
1560 return blockK * m_blockXYSize + blockJ * m_blockRes.x + blockI;
1566 template <
class Data_T>
1568 int &bi,
int &bj,
int &bk)
const
1573 bi = i >> m_blockOrder;
1574 bj = j >> m_blockOrder;
1575 bk = k >> m_blockOrder;
1581 template <
class Data_T>
1583 int &vi,
int &vj,
int &vk)
const
1588 vi = i & ((1 << m_blockOrder) - 1);
1589 vj = j & ((1 << m_blockOrder) - 1);
1590 vk = k & ((1 << m_blockOrder) - 1);
1595 template <
class Data_T>
1610 #endif // Include guard