Field3D
|
00001 //----------------------------------------------------------------------------// 00002 00003 /* 00004 * Copyright (c) 2009 Sony Pictures Imageworks Inc 00005 * 00006 * All rights reserved. 00007 * 00008 * Redistribution and use in source and binary forms, with or without 00009 * modification, are permitted provided that the following conditions 00010 * are met: 00011 * 00012 * Redistributions of source code must retain the above copyright 00013 * notice, this list of conditions and the following disclaimer. 00014 * Redistributions in binary form must reproduce the above copyright 00015 * notice, this list of conditions and the following disclaimer in the 00016 * documentation and/or other materials provided with the 00017 * distribution. Neither the name of Sony Pictures Imageworks nor the 00018 * names of its contributors may be used to endorse or promote 00019 * products derived from this software without specific prior written 00020 * permission. 00021 * 00022 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 00023 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 00024 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 00025 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 00026 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 00027 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 00028 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 00029 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00030 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 00031 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 00032 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 00033 * OF THE POSSIBILITY OF SUCH DAMAGE. 00034 */ 00035 00036 //----------------------------------------------------------------------------// 00037 00042 //----------------------------------------------------------------------------// 00043 00044 #ifndef _INCLUDED_Field3D_SparseField_H_ 00045 #define _INCLUDED_Field3D_SparseField_H_ 00046 00047 //----------------------------------------------------------------------------// 00048 00049 #include <vector> 00050 00051 #include <boost/lexical_cast.hpp> 00052 00053 #include "Field.h" 00054 #include "SparseFile.h" 00055 00056 #define BLOCK_ORDER 4 // 2^BLOCK_ORDER is the block size along each axis 00057 00058 //----------------------------------------------------------------------------// 00059 00060 #include "ns.h" 00061 00062 FIELD3D_NAMESPACE_OPEN 00063 00064 //----------------------------------------------------------------------------// 00065 // Forward declarations 00066 //----------------------------------------------------------------------------// 00067 00068 template <class Field_T> 00069 class LinearGenericFieldInterp; 00070 template <class Field_T> 00071 class CubicGenericFieldInterp; 00072 00073 //----------------------------------------------------------------------------// 00074 // SparseBlock 00075 //----------------------------------------------------------------------------// 00076 00079 namespace Sparse { 00080 00084 template <typename Data_T> 00085 struct SparseBlock 00086 { 00087 // Constructors -------------------------------------------------------------- 00088 00090 SparseBlock() 00091 : isAllocated(false), 00092 emptyValue(static_cast<Data_T>(0)) 00093 { /* Empty */ } 00094 00095 // Main methods -------------------------------------------------------------- 00096 00098 Data_T& value(int i, int j, int k, int blockOrder) 00100 { return data[(k << blockOrder << blockOrder) + (j << blockOrder) + i]; } 00101 00104 const Data_T& value(int i, int j, int k, int blockOrder) const 00105 { return data[(k << blockOrder << blockOrder) + (j << blockOrder) + i]; } 00106 00108 void resize(int n) 00109 { this->data.resize(n); } 00110 00112 void clear() 00113 { std::vector<Data_T>().swap(data); } 00114 00116 Data_T& dataRef() 00117 { return data[0]; } 00118 00119 // Data members -------------------------------------------------------------- 00120 00122 bool isAllocated; 00123 00127 Data_T emptyValue; 00128 00130 std::vector<Data_T> data; 00131 00132 private: 00133 00136 00137 }; 00138 00139 } // namespace Sparse 00140 00141 //----------------------------------------------------------------------------// 00142 // SparseField 00143 //----------------------------------------------------------------------------// 00144 00157 //----------------------------------------------------------------------------// 00158 00159 template <class Data_T> 00160 class SparseField 00161 : public ResizableField<Data_T> 00162 { 00163 public: 00164 00165 // Typedefs ------------------------------------------------------------------ 00166 00167 typedef boost::intrusive_ptr<SparseField> Ptr; 00168 typedef std::vector<Ptr> Vec; 00169 00170 typedef LinearGenericFieldInterp<SparseField<Data_T> > LinearInterp; 00171 typedef CubicGenericFieldInterp<SparseField<Data_T> > CubicInterp; 00172 00173 // Constructors -------------------------------------------------------------- 00174 00177 00179 SparseField(); 00180 00182 SparseField(const SparseField &o); 00183 00185 ~SparseField(); 00186 00189 SparseField & operator=(const SparseField &o); 00190 00191 // \} 00192 00193 // Main methods -------------------------------------------------------------- 00194 00196 virtual void clear(const Data_T &value); 00197 00200 void setBlockOrder(int order); 00201 00203 int blockOrder() const; 00204 00206 int blockSize() const; 00207 00209 bool voxelIsInAllocatedBlock(int i, int j, int k) const; 00210 00212 bool blockIsAllocated(int bi, int bj, int bk) const; 00213 00216 const Data_T getBlockEmptyValue(int bi, int bj, int bk) const; 00217 00220 void setBlockEmptyValue(int bi, int bj, int bk, const Data_T &val); 00221 00223 bool blockIndexIsValid(int bi, int bj, int bk) const; 00224 00226 V3i blockRes() const; 00227 00233 template <typename Functor_T> 00234 int releaseBlocks(Functor_T func); 00235 00237 int blockId(int blockI, int blockJ, int blockK) const; 00238 00242 void getBlockCoord(int i, int j, int k, int &bi, int &bj, int &bk) const; 00243 00247 void getVoxelInBlock(int i, int j, int k, int &vi, int &vj, int &vk) const; 00248 00250 void applyDataWindowOffset(int &i, int &j, int &k) const 00251 { 00252 i -= base::m_dataWindow.min.x; 00253 j -= base::m_dataWindow.min.y; 00254 k -= base::m_dataWindow.min.z; 00255 } 00256 00257 // From Field base class ----------------------------------------------------- 00258 00261 virtual Data_T value(int i, int j, int k) const; 00262 virtual long long int memSize() const; 00264 00265 // RTTI replacement ---------------------------------------------------------- 00266 00267 typedef SparseField<Data_T> class_type; 00268 DEFINE_FIELD_RTTI_CONCRETE_CLASS; 00269 00270 // From WritableField base class --------------------------------------------- 00271 00274 virtual Data_T& lvalue(int i, int j, int k); 00276 00277 // Concrete voxel access ----------------------------------------------------- 00278 00280 Data_T fastValue(int i, int j, int k) const; 00282 Data_T& fastLValue(int i, int j, int k); 00283 00284 // From FieldBase ------------------------------------------------------------ 00285 00288 virtual std::string className() const 00289 { return std::string("SparseField"); } 00290 00291 virtual FieldBase::Ptr clone() const 00292 { return Ptr(new SparseField(*this)); } 00293 00295 00296 // Iterators ----------------------------------------------------------------- 00297 00300 00302 class const_iterator; 00303 00305 const_iterator cbegin() const; 00307 const_iterator cbegin(const Box3i &subset) const; 00309 const_iterator cend() const; 00312 const_iterator cend(const Box3i &subset) const; 00313 00317 class iterator; 00318 00320 iterator begin(); 00322 iterator begin(const Box3i &subset); 00324 iterator end(); 00327 iterator end(const Box3i &subset); 00328 00332 class block_iterator; 00333 00334 block_iterator blockBegin() const; 00336 block_iterator blockEnd() const; 00337 00339 00340 // Internal utility functions ------------------------------------------------ 00341 00344 void addReference(const std::string &filename, const std::string &layerPath, 00345 int valuesPerBlock, int occupiedBlocks); 00348 void setupReferenceBlocks(); 00349 00350 protected: 00351 00352 friend class SparseFieldIO; 00353 00354 // Typedefs ------------------------------------------------------------------ 00355 00356 typedef ResizableField<Data_T> base; 00357 typedef Sparse::SparseBlock<Data_T> Block; 00358 00359 // From ResizableField class ------------------------------------------------- 00360 00361 virtual void sizeChanged() 00362 { 00363 // Call base class 00364 base::sizeChanged(); 00365 setupBlocks(); 00366 } 00367 00368 // Convenience methods ------------------------------------------------------- 00369 00372 00374 void setupBlocks(); 00375 00377 void deallocBlock(Block &block, const Data_T &emptyValue); 00378 00380 00381 // Data members -------------------------------------------------------------- 00382 00384 int m_blockOrder; 00386 V3i m_blockRes; 00388 int m_blockXYSize; 00390 std::vector<Block> m_blocks; 00391 00394 SparseFileManager *m_fileManager; 00396 int m_fileId; 00397 00399 Data_T m_dummy; 00400 00401 private: 00402 00405 void copySparseField(const SparseField &o); 00406 00409 void copyBlockStates(const SparseField<Data_T> &o); 00410 00411 }; 00412 00413 //----------------------------------------------------------------------------// 00414 // Typedefs 00415 //----------------------------------------------------------------------------// 00416 00417 typedef SparseField<half> SparseFieldh; 00418 typedef SparseField<float> SparseFieldf; 00419 typedef SparseField<double> SparseFieldd; 00420 typedef SparseField<V3h> SparseField3h; 00421 typedef SparseField<V3f> SparseField3f; 00422 typedef SparseField<V3d> SparseField3d; 00423 00424 //----------------------------------------------------------------------------// 00425 // Helper functors 00426 //----------------------------------------------------------------------------// 00427 00428 namespace Sparse { 00429 00432 template <typename Data_T> 00433 struct CheckAllEqual 00434 { 00443 bool check(const SparseBlock<Data_T> &block, Data_T &retEmptyValue, 00444 const V3i &validSize, const V3i &blockSize) 00445 { 00446 // Store first value 00447 Data_T first = block.data[0]; 00448 // Iterate over rest 00449 bool match = true; 00450 if (validSize == blockSize) { 00451 // interior block so look at all voxels 00452 for (typename std::vector<Data_T>::const_iterator i = block.data.begin(); 00453 i != block.data.end(); ++i) { 00454 if (*i != first) { 00455 match = false; 00456 break; 00457 } 00458 } 00459 } else { 00460 // only look at valid voxels 00461 int x=0, y=0, z=0; 00462 for (typename std::vector<Data_T>::const_iterator i = block.data.begin(); 00463 i != block.data.end(); ++i, ++x) { 00464 if (x >= blockSize.x) { 00465 x = 0; 00466 ++y; 00467 if (y >= blockSize.y) { 00468 y = 0; 00469 ++z; 00470 } 00471 } 00472 if (x >= validSize.x || y >= validSize.y || z >= validSize.z) { 00473 continue; 00474 } 00475 00476 if (*i != first) { 00477 match = false; 00478 break; 00479 } 00480 } 00481 } // end of interior block test 00482 00483 if (match) { 00484 retEmptyValue = first; 00485 return true; 00486 } else { 00487 return false; 00488 } 00489 } 00490 }; 00491 00492 //----------------------------------------------------------------------------// 00493 00494 template <typename Data_T> 00495 inline bool isAnyLess(const Data_T &left, const Data_T &right) 00496 { 00497 return (std::abs(left) < right); 00498 } 00499 00500 //----------------------------------------------------------------------------// 00501 00502 template <> 00503 inline bool isAnyLess(const V3h &left, const V3h &right) 00504 { 00505 return (std::abs(left.x) < right.x || 00506 std::abs(left.y) < right.y || 00507 std::abs(left.z) < right.z ); 00508 } 00509 00510 //----------------------------------------------------------------------------// 00511 00512 template <> 00513 inline bool isAnyLess(const V3f &left, const V3f &right) 00514 { 00515 return (std::abs(left.x) < right.x || 00516 std::abs(left.y) < right.y || 00517 std::abs(left.z) < right.z ); 00518 } 00519 00520 //----------------------------------------------------------------------------// 00521 00522 template <> 00523 inline bool isAnyLess(const V3d &left, const V3d &right) 00524 { 00525 return (std::abs(left.x) < right.x || 00526 std::abs(left.y) < right.y || 00527 std::abs(left.z) < right.z ); 00528 } 00529 00530 //----------------------------------------------------------------------------// 00531 00535 template <typename Data_T> 00536 struct CheckMaxAbs 00537 { 00539 CheckMaxAbs(Data_T maxValue) 00540 : m_maxValue(maxValue) 00541 { } 00550 bool check(const SparseBlock<Data_T> &block, Data_T &retEmptyValue, 00551 const V3i &validSize, const V3i &blockSize) 00552 { 00553 // Store first value 00554 Data_T first = block.data[0]; 00555 // Iterate over rest 00556 bool allGreater = true; 00557 if (validSize == blockSize) { 00558 // interior block so look at all voxels 00559 for (typename std::vector<Data_T>::const_iterator i = block.data.begin(); 00560 i != block.data.end(); ++i) { 00561 if (isAnyLess<Data_T>(*i, m_maxValue)) { 00562 allGreater = false; 00563 break; 00564 } 00565 } 00566 } else { 00567 // only look at valid voxels 00568 int x=0, y=0, z=0; 00569 for (typename std::vector<Data_T>::const_iterator i = block.data.begin(); 00570 i != block.data.end(); ++i, ++x) { 00571 if (x >= blockSize.x) { 00572 x = 0; 00573 ++y; 00574 if (y >= blockSize.y) { 00575 y = 0; 00576 ++z; 00577 } 00578 } 00579 if (x >= validSize.x || y >= validSize.y || z >= validSize.z) { 00580 continue; 00581 } 00582 if (isAnyLess<Data_T>(*i, m_maxValue)) { 00583 allGreater = false; 00584 break; 00585 } 00586 } 00587 } // end of interior block test 00588 00589 if (allGreater) { 00590 retEmptyValue = first; 00591 return true; 00592 } else { 00593 return false; 00594 } 00595 } 00596 private: 00597 Data_T m_maxValue; 00598 }; 00599 00600 } // namespace Sparse 00601 00602 //----------------------------------------------------------------------------// 00603 // SparseField::const_iterator 00604 //----------------------------------------------------------------------------// 00605 00607 template <class Data_T> 00608 class SparseField<Data_T>::const_iterator 00609 { 00610 public: 00611 typedef SparseField<Data_T> class_type; 00612 const_iterator(const class_type &field, 00613 const Box3i &window, 00614 const V3i ¤tPos, int blockOrder) 00615 : x(currentPos.x), y(currentPos.y), z(currentPos.z), 00616 m_p(NULL), m_blockIsActivated(false), 00617 m_blockStepsTicker(0), m_blockOrder(blockOrder), 00618 m_blockId(-1), m_window(window), m_field(&field) 00619 { 00620 m_manager = m_field->m_fileManager; 00621 setupNextBlock(x, y, z); 00622 } 00623 ~const_iterator() { 00624 if (m_manager && m_blockId >= 0 && 00625 m_blockId < static_cast<int>(m_field->m_blocks.size())) { 00626 if (m_field->m_blocks[m_blockId].isAllocated) 00627 m_manager->decBlockRef<Data_T>(m_field->m_fileId, m_blockId); 00628 } 00629 } 00630 const const_iterator& operator ++ () 00631 { 00632 bool resetPtr = false; 00633 // Check against end of data window 00634 if (x == m_window.max.x) { 00635 if (y == m_window.max.y) { 00636 x = m_window.min.x; 00637 y = m_window.min.y; 00638 ++z; 00639 resetPtr = true; 00640 } else { 00641 x = m_window.min.x; 00642 ++y; 00643 resetPtr = true; 00644 } 00645 } else { 00646 ++x; 00647 } 00648 // These can both safely be incremented here 00649 ++m_blockStepsTicker; 00650 // ... but only step forward if we're in a non-empty block 00651 if (!m_isEmptyBlock && (!m_manager || m_blockIsActivated)) 00652 ++m_p; 00653 // Check if we've reached the end of this block 00654 if (m_blockStepsTicker == (1 << m_blockOrder)) 00655 resetPtr = true; 00656 if (resetPtr) { 00657 // If we have, we need to reset the current block, etc. 00658 m_blockStepsTicker = 0; 00659 setupNextBlock(x, y, z); 00660 } 00661 return *this; 00662 } 00663 template <class Iter_T> 00664 inline bool operator == (const Iter_T &rhs) const 00665 { 00666 return x == rhs.x && y == rhs.y && z == rhs.z; 00667 } 00668 template <class Iter_T> 00669 inline bool operator != (const Iter_T &rhs) const 00670 { 00671 return x != rhs.x || y != rhs.y || z != rhs.z; 00672 } 00673 inline const Data_T& operator * () const 00674 { 00675 if (!m_isEmptyBlock && m_manager && !m_blockIsActivated) { 00676 m_manager->activateBlock<Data_T>(m_field->m_fileId, m_blockId); 00677 m_blockIsActivated = true; 00678 const Block &block = m_field->m_blocks[m_blockId]; 00679 int vi, vj, vk; 00680 m_field->getVoxelInBlock(x, y, z, vi, vj, vk); 00681 m_p = &block.value(vi, vj, vk, m_blockOrder); 00682 } 00683 return *m_p; 00684 } 00685 inline const Data_T* operator -> () const 00686 { 00687 if (!m_isEmptyBlock && m_manager && !m_blockIsActivated) { 00688 SparseFileManager *manager = m_field->m_fileManager; 00689 manager->activateBlock<Data_T>(m_field->m_fileId, m_blockId); 00690 m_blockIsActivated = true; 00691 const Block &block = m_field->m_blocks[m_blockId]; 00692 int vi, vj, vk; 00693 m_field->getVoxelInBlock(x, y, z, vi, vj, vk); 00694 m_p = &block.value(vi, vj, vk, m_blockOrder); 00695 } 00696 return m_p; 00697 } 00698 00699 // Public data members ------------------------------------------------------- 00700 00702 int x, y, z; 00703 00704 private: 00705 00706 // Typedefs ------------------------------------------------------------------ 00707 00708 typedef Sparse::SparseBlock<Data_T> Block; 00709 00710 // Convenience methods ------------------------------------------------------- 00711 00712 void setupNextBlock(int i, int j, int k) 00713 { 00714 m_field->applyDataWindowOffset(i, j, k); 00715 m_field->getBlockCoord(i, j, k, m_blockI, m_blockJ, m_blockK); 00716 int oldBlockId = m_blockId; 00717 m_blockId = m_field->blockId(m_blockI, m_blockJ, m_blockK); 00718 if (m_manager && oldBlockId != m_blockId && 00719 oldBlockId >= 0 && 00720 oldBlockId < static_cast<int>(m_field->m_blocks.size()) && 00721 m_field->m_blocks[oldBlockId].isAllocated) { 00722 m_manager->decBlockRef<Data_T>(m_field->m_fileId, oldBlockId); 00723 } 00724 if (m_blockId >= m_field->m_blockXYSize * m_field->m_blockRes.z) { 00725 m_isEmptyBlock = true; 00726 return; 00727 } 00728 00729 const Block &block = m_field->m_blocks[m_blockId]; 00730 int vi, vj, vk; 00731 m_field->getVoxelInBlock(i, j, k, vi, vj, vk); 00732 m_blockStepsTicker = vi; 00733 if (block.isAllocated) { 00734 if (m_manager && oldBlockId != m_blockId && m_blockId >= 0) { 00735 m_manager->incBlockRef<Data_T>(m_field->m_fileId, m_blockId); 00736 // this is a managed field, so the block may not be loaded 00737 // yet, so don't bother setting m_p yet (it'll get set in the 00738 // * and -> operators when the block is activated) 00739 } else { 00740 // only set m_p to the voxel's address if this is not a 00741 // managed field, i.e., if the data is already in memory. 00742 m_p = &block.value(vi, vj, vk, m_blockOrder); 00743 } 00744 m_isEmptyBlock = false; 00745 } else { 00746 m_p = &block.emptyValue; 00747 m_isEmptyBlock = true; 00748 } 00749 if (m_field->m_fileManager) { 00750 m_blockIsActivated = false; 00751 } 00752 } 00753 00755 mutable const Data_T *m_p; 00757 bool m_isEmptyBlock; 00760 mutable bool m_blockIsActivated; 00762 int m_blockStepsTicker; 00764 int m_blockOrder; 00766 int m_blockI, m_blockJ, m_blockK, m_blockId; 00768 Box3i m_window; 00770 const class_type *m_field; 00772 SparseFileManager *m_manager; 00773 }; 00774 00775 //----------------------------------------------------------------------------// 00776 // SparseField::iterator 00777 //----------------------------------------------------------------------------/ 00778 00780 template <class Data_T> 00781 class SparseField<Data_T>::iterator 00782 { 00783 public: 00784 typedef SparseField<Data_T> class_type; 00785 iterator(class_type &field, 00786 const Box3i &window, 00787 const V3i ¤tPos, int blockOrder) 00788 : x(currentPos.x), y(currentPos.y), z(currentPos.z), 00789 m_p(NULL), m_blockStepsTicker(0), m_blockOrder(blockOrder), 00790 m_blockId(-1), m_window(window), m_field(&field) 00791 { 00792 setupNextBlock(x, y, z); 00793 } 00794 const iterator& operator ++ () 00795 { 00796 bool resetPtr = false; 00797 // Check against end of data window 00798 if (x == m_window.max.x) { 00799 if (y == m_window.max.y) { 00800 x = m_window.min.x; 00801 y = m_window.min.y; 00802 ++z; 00803 resetPtr = true; 00804 } else { 00805 x = m_window.min.x; 00806 ++y; 00807 resetPtr = true; 00808 } 00809 } else { 00810 ++x; 00811 } 00812 // These can both safely be incremented here 00813 ++m_blockStepsTicker; 00814 // ... but only step forward if we're in a non-empty block 00815 if (!m_isEmptyBlock) 00816 ++m_p; 00817 // Check if we've reached the end of this block 00818 if (m_blockStepsTicker == (1 << m_blockOrder)) 00819 resetPtr = true; 00820 if (resetPtr) { 00821 // If we have, we need to reset the current block, etc. 00822 m_blockStepsTicker = 0; 00823 setupNextBlock(x, y, z); 00824 } 00825 return *this; 00826 } 00827 inline bool operator == (const iterator &rhs) const 00828 { 00829 return x == rhs.x && y == rhs.y && z == rhs.z; 00830 } 00831 inline bool operator != (const iterator &rhs) const 00832 { 00833 return x != rhs.x || y != rhs.y || z != rhs.z; 00834 } 00835 inline Data_T& operator * () 00836 { 00837 if (m_field->m_fileManager) { 00838 assert(false && "Dereferencing iterator on a dynamic-read sparse field"); 00839 Msg::print(Msg::SevWarning, "Dereferencing iterator on a dynamic-read " 00840 "sparse field"); 00841 return *m_p; 00842 } 00843 // If the block is currently empty, we must allocate it 00844 if (m_isEmptyBlock) { 00845 // Touch the voxel to allocate the block 00846 m_field->lvalue(x, y, z); 00847 // Set up the block again 00848 setupNextBlock(x, y, z); 00849 } 00850 return *m_p; 00851 } 00852 inline Data_T* operator -> () 00853 { 00854 if (m_field->m_fileManager) { 00855 assert(false && "Dereferencing iterator on a dynamic-read sparse field"); 00856 Msg::print(Msg::SevWarning, "Dereferencing iterator on a dynamic-read " 00857 "sparse field"); 00858 return m_p; 00859 } 00860 // If the block is currently empty, we must allocate it 00861 if (m_isEmptyBlock) { 00862 // Touch the voxel to allocate the block 00863 m_field->lvalue(x, y, z); 00864 // Set up the block again 00865 setupNextBlock(x, y, z); 00866 } 00867 return m_p; 00868 } 00869 // Public data members 00870 int x, y, z; 00871 private: 00872 typedef Sparse::SparseBlock<Data_T> Block; 00874 void setupNextBlock(int i, int j, int k) 00875 { 00876 m_field->applyDataWindowOffset(i, j, k); 00877 m_field->getBlockCoord(i, j, k, m_blockI, m_blockJ, m_blockK); 00878 m_blockId = m_field->blockId(m_blockI, m_blockJ, m_blockK); 00879 if (m_blockId >= m_field->m_blockXYSize * m_field->m_blockRes.z) { 00880 m_isEmptyBlock = true; 00881 return; 00882 } 00883 Block &block = m_field->m_blocks[m_blockId]; 00884 int vi, vj, vk; 00885 m_field->getVoxelInBlock(i, j, k, vi, vj, vk); 00886 m_blockStepsTicker = vi; 00887 if (block.isAllocated) { 00888 m_p = &block.value(vi, vj, vk, m_blockOrder); 00889 m_isEmptyBlock = false; 00890 } else { 00891 m_p = &block.emptyValue; 00892 m_isEmptyBlock = true; 00893 } 00894 } 00896 Data_T *m_p; 00898 bool m_isEmptyBlock; 00900 int m_blockStepsTicker; 00902 int m_blockOrder; 00904 int m_blockI, m_blockJ, m_blockK, m_blockId; 00906 Box3i m_window; 00908 class_type *m_field; 00909 }; 00910 00911 //----------------------------------------------------------------------------// 00912 // SparseField::block_iterator 00913 //----------------------------------------------------------------------------/ 00914 00917 template <class Data_T> 00918 class SparseField<Data_T>::block_iterator 00919 { 00920 public: 00922 typedef SparseField<Data_T> class_type; 00924 block_iterator(const class_type &field, const Box3i &window, 00925 const V3i ¤tPos) 00926 : x(currentPos.x), y(currentPos.y), z(currentPos.z), 00927 m_window(window), m_field(field) 00928 { 00929 recomputeBlockBoundingBox(); 00930 } 00932 const block_iterator& operator ++ () 00933 { 00934 if (x == m_window.max.x) { 00935 if (y == m_window.max.y) { 00936 x = m_window.min.x; 00937 y = m_window.min.y; 00938 ++z; 00939 } else { 00940 x = m_window.min.x; 00941 ++y; 00942 } 00943 } else { 00944 ++x; 00945 } 00946 recomputeBlockBoundingBox(); 00947 return *this; 00948 } 00950 inline bool operator == (const block_iterator &rhs) const 00951 { 00952 return x == rhs.x && y == rhs.y && z == rhs.z; 00953 } 00955 inline bool operator != (const block_iterator &rhs) const 00956 { 00957 return x != rhs.x || y != rhs.y || z != rhs.z; 00958 } 00960 const Box3i& blockBoundingBox() 00961 { 00962 return m_currentBlockWindow; 00963 } 00965 int x, y, z; 00966 private: 00967 void recomputeBlockBoundingBox() 00968 { 00969 Box3i box; 00970 int blockSize = m_field.blockSize(); 00971 box.min = V3i(x * blockSize, y * blockSize, z * blockSize); 00972 box.max = box.min + V3i(blockSize - 1, blockSize - 1, blockSize - 1); 00973 // Clamp the box 00974 box.min = FIELD3D_CLIP(box.min, m_field.dataWindow()); 00975 box.max = FIELD3D_CLIP(box.max, m_field.dataWindow()); 00976 // Set the member variable 00977 m_currentBlockWindow = box; 00978 } 00980 Box3i m_window; 00982 const class_type& m_field; 00984 Box3i m_currentBlockWindow; 00985 }; 00986 00987 //----------------------------------------------------------------------------// 00988 // SparseField implementations 00989 //----------------------------------------------------------------------------// 00990 00991 template <class Data_T> 00992 SparseField<Data_T>::SparseField() 00993 : base(), 00994 m_blockOrder(BLOCK_ORDER), 00995 m_fileManager(NULL) 00996 { 00997 setupBlocks(); 00998 } 00999 01000 //----------------------------------------------------------------------------// 01001 01002 template <class Data_T> 01003 SparseField<Data_T>::SparseField(const SparseField<Data_T> &o) : 01004 base(o) 01005 { 01006 copySparseField(o); 01007 } 01008 01009 //----------------------------------------------------------------------------// 01010 01011 template <class Data_T> 01012 SparseField<Data_T>::~SparseField() 01013 { 01014 if (m_fileManager) { 01015 // this file is dynamically managed, so we need to ensure the 01016 // cache doesn't point to this field's blocks because they are 01017 // about to be deleted 01018 m_fileManager->removeFieldFromCache<Data_T>(m_fileId); 01019 } 01020 } 01021 01022 //----------------------------------------------------------------------------// 01023 01024 template <class Data_T> 01025 SparseField<Data_T> & 01026 SparseField<Data_T>::operator=(const SparseField<Data_T> &o) 01027 { 01028 if (this != &o) { 01029 this->base::operator=(o); 01030 copySparseField(o); 01031 } 01032 return *this; 01033 } 01034 01035 //----------------------------------------------------------------------------// 01036 01037 template <class Data_T> 01038 void 01039 SparseField<Data_T>::copySparseField(const SparseField<Data_T> &o) 01040 { 01041 m_blockOrder = o.m_blockOrder; 01042 if (o.m_fileManager) { 01043 // allocate m_blocks, sets m_blockRes, m_blockXYSize, m_blocks 01044 setupBlocks(); 01045 01046 m_fileManager = o.m_fileManager; 01047 SparseFile::Reference<Data_T> &oldReference = 01048 m_fileManager->reference<Data_T>(o.m_fileId); 01049 addReference(oldReference.filename, oldReference.layerPath, 01050 oldReference.valuesPerBlock, 01051 oldReference.occupiedBlocks); 01052 copyBlockStates(o); 01053 setupReferenceBlocks(); 01054 } else { 01055 // directly copy all values and blocks from the source, no extra setup 01056 m_blockRes = o.m_blockRes; 01057 m_blockXYSize = o.m_blockXYSize; 01058 m_blocks = o.m_blocks; 01059 m_fileId = -1; 01060 m_fileManager = NULL; 01061 } 01062 } 01063 01064 //----------------------------------------------------------------------------// 01065 01066 template <class Data_T> 01067 void SparseField<Data_T>::addReference(const std::string &filename, 01068 const std::string &layerPath, 01069 int valuesPerBlock, 01070 int occupiedBlocks) 01071 { 01072 m_fileManager = &SparseFileManager::singleton(); 01073 m_fileId = m_fileManager->getNextId<Data_T>(filename, layerPath); 01074 // Set up the manager data 01075 SparseFile::Reference<Data_T> &reference = 01076 m_fileManager->reference<Data_T>(m_fileId); 01077 reference.valuesPerBlock = valuesPerBlock; 01078 reference.occupiedBlocks = occupiedBlocks; 01079 reference.setNumBlocks(m_blocks.size()); 01080 } 01081 01082 //----------------------------------------------------------------------------// 01083 01084 template <class Data_T> 01085 void SparseField<Data_T>::copyBlockStates(const SparseField<Data_T> &o) 01086 { 01087 if (m_blocks.size() != o.m_blocks.size()) return; 01088 01089 typename std::vector<Sparse::SparseBlock<Data_T> >::iterator b = 01090 m_blocks.begin(); 01091 typename std::vector<Sparse::SparseBlock<Data_T> >::iterator bend = 01092 m_blocks.end(); 01093 typename std::vector<Sparse::SparseBlock<Data_T> >::const_iterator ob = 01094 o.m_blocks.begin(); 01095 01096 for (; b != bend; ++b, ++ob) { 01097 b->isAllocated = ob->isAllocated; 01098 b->emptyValue = ob->emptyValue; 01099 b->clear(); 01100 } 01101 } 01102 01103 //----------------------------------------------------------------------------// 01104 01105 template <class Data_T> 01106 void SparseField<Data_T>::setupReferenceBlocks() 01107 { 01108 if (!m_fileManager || m_fileId < 0) return; 01109 01110 SparseFile::Reference<Data_T> &reference = 01111 m_fileManager->reference<Data_T>(m_fileId); 01112 01113 std::vector<int>::iterator fb = reference.fileBlockIndices.begin(); 01114 typename SparseFile::Reference<Data_T>::BlockPtrs::iterator bp = 01115 reference.blocks.begin(); 01116 typename std::vector<Sparse::SparseBlock<Data_T> >::iterator b = 01117 m_blocks.begin(); 01118 typename std::vector<Sparse::SparseBlock<Data_T> >::iterator bend = 01119 m_blocks.end(); 01120 int nextBlockIdx = 0; 01121 01122 for (; b != bend; ++b, ++fb, ++bp) { 01123 if (b->isAllocated) { 01124 *fb = nextBlockIdx; 01125 *bp = &(*b); 01126 nextBlockIdx++; 01127 } else { 01128 *fb = -1; 01129 } 01130 } 01131 } 01132 01133 //----------------------------------------------------------------------------// 01134 01135 template <class Data_T> 01136 void SparseField<Data_T>::clear(const Data_T &value) 01137 { 01138 // If we're clearing, we can get rid of all current blocks 01139 setupBlocks(); 01140 // Then just fill in the default values 01141 typename std::vector<Block>::iterator i; 01142 for (i = m_blocks.begin(); i != m_blocks.end(); ++i) { 01143 i->emptyValue = value; 01144 } 01145 } 01146 01147 //----------------------------------------------------------------------------// 01148 01149 template <class Data_T> 01150 void SparseField<Data_T>::setBlockOrder(int order) 01151 { 01152 m_blockOrder = order; 01153 setupBlocks(); 01154 } 01155 01156 //----------------------------------------------------------------------------// 01157 01158 template <class Data_T> 01159 int SparseField<Data_T>::blockOrder() const 01160 { 01161 return m_blockOrder; 01162 } 01163 01164 //----------------------------------------------------------------------------// 01165 01166 template <class Data_T> 01167 int SparseField<Data_T>::blockSize() const 01168 { 01169 return 1 << m_blockOrder; 01170 } 01171 01172 //----------------------------------------------------------------------------// 01173 01174 template <class Data_T> 01175 bool SparseField<Data_T>::voxelIsInAllocatedBlock(int i, int j, int k) const 01176 { 01177 int bi, bj, bk; 01178 applyDataWindowOffset(i, j, k); 01179 getBlockCoord(i, j, k, bi, bj, bk); 01180 return blockIsAllocated(bi, bj, bk); 01181 } 01182 01183 //----------------------------------------------------------------------------// 01184 01185 template <class Data_T> 01186 bool SparseField<Data_T>::blockIsAllocated(int bi, int bj, int bk) const 01187 { 01188 const Block &block = m_blocks[blockId(bi, bj, bk)]; 01189 return block.isAllocated; 01190 } 01191 01192 //----------------------------------------------------------------------------// 01193 01194 template <class Data_T> 01195 const Data_T SparseField<Data_T>::getBlockEmptyValue(int bi, int bj, int bk) const 01196 { 01197 return m_blocks[blockId(bi, bj, bk)].emptyValue; 01198 } 01199 01200 //----------------------------------------------------------------------------// 01201 01202 template <class Data_T> 01203 void SparseField<Data_T>::setBlockEmptyValue(int bi, int bj, int bk, 01204 const Data_T &val) 01205 { 01206 Block &block = m_blocks[blockId(bi, bj, bk)]; 01207 if (block.isAllocated) { 01208 deallocBlock(block, val); 01209 } else { 01210 block.emptyValue = val; 01211 } 01212 } 01213 01214 //----------------------------------------------------------------------------// 01215 01216 template <class Data_T> 01217 bool SparseField<Data_T>::blockIndexIsValid(int bi, int bj, int bk) const 01218 { 01219 return bi >= 0 && bj >= 0 && bk >= 0 && 01220 bi < m_blockRes.x && bj < m_blockRes.y && bk < m_blockRes.z; 01221 } 01222 01223 //----------------------------------------------------------------------------// 01224 01225 template <class Data_T> 01226 V3i SparseField<Data_T>::blockRes() const 01227 { 01228 return m_blockRes; 01229 } 01230 01231 //----------------------------------------------------------------------------// 01232 01233 template <class Data_T> 01234 template <typename Functor_T> 01235 int SparseField<Data_T>::releaseBlocks(Functor_T func) 01236 { 01237 Data_T emptyValue; 01238 int numDeallocs = 0; 01239 typename std::vector<Block>::iterator i; 01240 01241 // If the block is on the edge of the field, it may have unused 01242 // voxels, with undefined values. We need to pass the range of 01243 // valid voxels into the check function, so it only looks at valid 01244 // voxels. 01245 V3i dataRes = FieldRes::dataResolution(); 01246 V3i validSize; 01247 V3i blockAllocSize(blockSize()); 01248 int bx, by, bz; 01249 01250 for (i = m_blocks.begin(), bx=0, by=0, bz=0; i != m_blocks.end(); ++i, ++bx) { 01251 if (bx >= m_blockRes.x) { 01252 bx = 0; 01253 ++by; 01254 if (by >= m_blockRes.y) { 01255 by = 0; 01256 ++bz; 01257 } 01258 } 01259 validSize = blockAllocSize; 01260 if (bx == m_blockRes.x-1) { 01261 validSize.x = dataRes.x - bx * blockAllocSize.x; 01262 } 01263 if (by == m_blockRes.y-1) { 01264 validSize.y = dataRes.y - by * blockAllocSize.y; 01265 } 01266 if (bz == m_blockRes.z-1) { 01267 validSize.z = dataRes.z - bz * blockAllocSize.z; 01268 } 01269 01270 if (i->isAllocated) { 01271 if (func.check(*i, emptyValue, validSize, blockAllocSize)) { 01272 deallocBlock(*i, emptyValue); 01273 numDeallocs++; 01274 } 01275 } 01276 } 01277 return numDeallocs; 01278 } 01279 01280 //----------------------------------------------------------------------------// 01281 01282 template <class Data_T> 01283 Data_T SparseField<Data_T>::value(int i, int j, int k) const 01284 { 01285 return fastValue(i, j, k); 01286 } 01287 01288 //----------------------------------------------------------------------------// 01289 01290 template <class Data_T> 01291 Data_T& SparseField<Data_T>::lvalue(int i, int j, int k) 01292 { 01293 return fastLValue(i, j, k); 01294 } 01295 01296 //----------------------------------------------------------------------------// 01297 01298 template <class Data_T> 01299 Data_T SparseField<Data_T>::fastValue(int i, int j, int k) const 01300 { 01301 assert (i >= base::m_dataWindow.min.x); 01302 assert (i <= base::m_dataWindow.max.x); 01303 assert (j >= base::m_dataWindow.min.y); 01304 assert (j <= base::m_dataWindow.max.y); 01305 assert (k >= base::m_dataWindow.min.z); 01306 assert (k <= base::m_dataWindow.max.z); 01307 // Add crop window offset 01308 applyDataWindowOffset(i, j, k); 01309 // Find block coord 01310 int bi, bj, bk; 01311 getBlockCoord(i, j, k, bi, bj, bk); 01312 // Find coord in block 01313 int vi, vj, vk; 01314 getVoxelInBlock(i, j, k, vi, vj, vk); 01315 // Get the actual block 01316 int id = blockId(bi, bj, bk); 01317 01318 const Block &block = m_blocks[id]; 01319 // Check if block data is allocated 01320 if (block.isAllocated) { 01321 if (m_fileManager) { 01322 m_fileManager->incBlockRef<Data_T>(m_fileId, id); 01323 m_fileManager->activateBlock<Data_T>(m_fileId, id); 01324 Data_T tmpValue = block.value(vi, vj, vk, m_blockOrder); 01325 m_fileManager->decBlockRef<Data_T>(m_fileId, id); 01326 return tmpValue; 01327 } else { 01328 return block.value(vi, vj, vk, m_blockOrder); 01329 } 01330 } else { 01331 return block.emptyValue; 01332 } 01333 } 01334 01335 //----------------------------------------------------------------------------// 01336 01338 template <class Data_T> 01339 Data_T& SparseField<Data_T>::fastLValue(int i, int j, int k) 01340 { 01341 assert (i >= base::m_dataWindow.min.x); 01342 assert (i <= base::m_dataWindow.max.x); 01343 assert (j >= base::m_dataWindow.min.y); 01344 assert (j <= base::m_dataWindow.max.y); 01345 assert (k >= base::m_dataWindow.min.z); 01346 assert (k <= base::m_dataWindow.max.z); 01347 01348 if (m_fileManager) { 01349 assert(false && "Called fastLValue() on a dynamic-read sparse field"); 01350 Msg::print(Msg::SevWarning, "Called fastLValue() on a dynamic-read " 01351 "sparse field"); 01352 return m_dummy; 01353 } 01354 01355 // Add crop window offset 01356 applyDataWindowOffset(i, j, k); 01357 // Find block coord 01358 int bi, bj, bk; 01359 getBlockCoord(i, j, k, bi, bj, bk); 01360 // Find coord in block 01361 int vi, vj, vk; 01362 getVoxelInBlock(i, j, k, vi, vj, vk); 01363 // Get the actual block 01364 int id = blockId(bi, bj, bk); 01365 Block &block = m_blocks[id]; 01366 // If block is allocated, return a reference to the data 01367 if (block.isAllocated) { 01368 return block.value(vi, vj, vk, m_blockOrder); 01369 } else { 01370 // ... Otherwise, allocate block 01371 block.isAllocated = true; 01372 block.data.resize(1 << m_blockOrder << m_blockOrder << m_blockOrder); 01373 std::fill(block.data.begin(), block.data.end(), block.emptyValue); 01374 return block.value(vi, vj, vk, m_blockOrder); 01375 } 01376 } 01377 01378 //----------------------------------------------------------------------------// 01379 01380 template <class Data_T> 01381 long long int SparseField<Data_T>::memSize() const 01382 { 01383 long long int blockSize = m_blocks.capacity() * sizeof(Block); 01384 long long int dataSize = 0; 01385 typename std::vector<Block>::const_iterator i; 01386 for (i = m_blocks.begin(); i != m_blocks.end(); ++i) { 01387 if (i->isAllocated) { 01388 dataSize += i->data.capacity() * sizeof(Data_T); 01389 } 01390 } 01391 return sizeof(*this) + dataSize + blockSize; 01392 } 01393 01394 //----------------------------------------------------------------------------// 01395 01396 template <class Data_T> 01397 typename SparseField<Data_T>::const_iterator 01398 SparseField<Data_T>::cbegin() const 01399 { 01400 if (FieldRes::dataResolution() == V3i(0)) 01401 return cend(); 01402 return const_iterator(*this, base::m_dataWindow, base::m_dataWindow.min, 01403 m_blockOrder); 01404 } 01405 01406 //----------------------------------------------------------------------------// 01407 01408 template <class Data_T> 01409 typename SparseField<Data_T>::const_iterator 01410 SparseField<Data_T>::cbegin(const Box3i &subset) const 01411 { 01412 if (subset.isEmpty()) 01413 return cend(subset); 01414 return const_iterator(*this, subset, subset.min, m_blockOrder); 01415 } 01416 01417 //----------------------------------------------------------------------------// 01418 01419 template <class Data_T> 01420 typename SparseField<Data_T>::const_iterator 01421 SparseField<Data_T>::cend() const 01422 { 01423 return const_iterator(*this, base::m_dataWindow, 01424 V3i(base::m_dataWindow.min.x, 01425 base::m_dataWindow.min.y, 01426 base::m_dataWindow.max.z + 1), 01427 m_blockOrder); 01428 } 01429 01430 //----------------------------------------------------------------------------// 01431 01432 template <class Data_T> 01433 typename SparseField<Data_T>::const_iterator 01434 SparseField<Data_T>::cend(const Box3i &subset) const 01435 { 01436 return const_iterator(*this, subset, 01437 V3i(subset.min.x, 01438 subset.min.y, 01439 subset.max.z + 1), m_blockOrder); 01440 } 01441 01442 //----------------------------------------------------------------------------// 01443 01444 template <class Data_T> 01445 typename SparseField<Data_T>::iterator 01446 SparseField<Data_T>::begin() 01447 { 01448 if (FieldRes::dataResolution() == V3i(0)) 01449 return end(); 01450 return iterator(*this, base::m_dataWindow, 01451 base::m_dataWindow.min, m_blockOrder); } 01452 01453 //----------------------------------------------------------------------------// 01454 01455 template <class Data_T> 01456 typename SparseField<Data_T>::iterator 01457 SparseField<Data_T>::begin(const Box3i &subset) 01458 { 01459 if (subset.isEmpty()) 01460 return end(subset); 01461 return iterator(*this, subset, subset.min, m_blockOrder); 01462 } 01463 01464 //----------------------------------------------------------------------------// 01465 01466 template <class Data_T> 01467 typename SparseField<Data_T>::iterator 01468 SparseField<Data_T>::end() 01469 { 01470 return iterator(*this, base::m_dataWindow, 01471 V3i(base::m_dataWindow.min.x, 01472 base::m_dataWindow.min.y, 01473 base::m_dataWindow.max.z + 1), m_blockOrder); 01474 } 01475 01476 //----------------------------------------------------------------------------// 01477 01478 template <class Data_T> 01479 typename SparseField<Data_T>::iterator 01480 SparseField<Data_T>::end(const Box3i &subset) 01481 { 01482 return iterator(*this, subset, 01483 V3i(subset.min.x, subset.min.y, subset.max.z + 1), 01484 m_blockOrder); 01485 } 01486 01487 //----------------------------------------------------------------------------// 01488 01489 template <class Data_T> 01490 typename SparseField<Data_T>::block_iterator 01491 SparseField<Data_T>::blockBegin() const 01492 { 01493 if (FieldRes::dataResolution() == V3i(0)) 01494 return blockEnd(); 01495 return block_iterator(*this, Box3i(V3i(0), m_blockRes - V3i(1)), 01496 V3i(0)); 01497 } 01498 01499 //----------------------------------------------------------------------------// 01500 01501 template <class Data_T> 01502 typename SparseField<Data_T>::block_iterator 01503 SparseField<Data_T>::blockEnd() const 01504 { 01505 return block_iterator(*this, Box3i(V3i(0), m_blockRes - V3i(1)), 01506 V3i(0, 0, m_blockRes.z)); 01507 } 01508 01509 //----------------------------------------------------------------------------// 01510 01511 template <class Data_T> 01512 void SparseField<Data_T>::setupBlocks() 01513 { 01514 // Do calculation in floating point so we can round up later 01515 V3f res(base::m_dataWindow.size() + V3i(1)); 01516 V3f blockRes(res / (1 << m_blockOrder)); 01517 blockRes.x = ceil(blockRes.x); 01518 blockRes.y = ceil(blockRes.y); 01519 blockRes.z = ceil(blockRes.z); 01520 V3i intBlockRes(static_cast<int>(blockRes.x), 01521 static_cast<int>(blockRes.y), 01522 static_cast<int>(blockRes.z)); 01523 m_blockRes = intBlockRes; 01524 m_blockXYSize = m_blockRes.x * m_blockRes.y; 01526 m_blocks.clear(); 01527 m_blocks.resize(intBlockRes.x * intBlockRes.y * intBlockRes.z); 01528 01529 } 01530 01531 //----------------------------------------------------------------------------// 01532 01533 template <class Data_T> 01534 int SparseField<Data_T>::blockId(int blockI, int blockJ, int blockK) const 01535 { 01536 return blockK * m_blockXYSize + blockJ * m_blockRes.x + blockI; 01537 } 01538 01539 //----------------------------------------------------------------------------// 01540 01542 template <class Data_T> 01543 void SparseField<Data_T>::getBlockCoord(int i, int j, int k, 01544 int &bi, int &bj, int &bk) const 01545 { 01546 assert(i >= 0); 01547 assert(j >= 0); 01548 assert(k >= 0); 01549 bi = i >> m_blockOrder; 01550 bj = j >> m_blockOrder; 01551 bk = k >> m_blockOrder; 01552 } 01553 01554 //----------------------------------------------------------------------------// 01555 01557 template <class Data_T> 01558 void SparseField<Data_T>::getVoxelInBlock(int i, int j, int k, 01559 int &vi, int &vj, int &vk) const 01560 { 01561 assert(i >= 0); 01562 assert(j >= 0); 01563 assert(k >= 0); 01564 vi = i & ((1 << m_blockOrder) - 1); 01565 vj = j & ((1 << m_blockOrder) - 1); 01566 vk = k & ((1 << m_blockOrder) - 1); 01567 } 01568 01569 //----------------------------------------------------------------------------// 01570 01571 template <class Data_T> 01572 void SparseField<Data_T>::deallocBlock(Block &block, const Data_T &emptyValue) 01573 { 01574 block.isAllocated = false; 01575 block.clear(); 01576 block.emptyValue = emptyValue; 01577 } 01578 01579 //----------------------------------------------------------------------------// 01580 01581 FIELD3D_NAMESPACE_HEADER_CLOSE 01582 01583 //----------------------------------------------------------------------------// 01584 01585 #endif // Include guard