SoLDMTopoOctree.h

/*=======================================================================
 *** THE CONTENT OF THIS WORK IS PROPRIETARY TO FEI S.A.S, (FEI S.A.S.),            ***
 ***              AND IS DISTRIBUTED UNDER A LICENSE AGREEMENT.                     ***
 ***                                                                                ***
 ***  REPRODUCTION, DISCLOSURE,  OR USE,  IN WHOLE OR IN PART,  OTHER THAN AS       ***
 ***  SPECIFIED  IN THE LICENSE ARE  NOT TO BE  UNDERTAKEN  EXCEPT WITH PRIOR       ***
 ***  WRITTEN AUTHORIZATION OF FEI S.A.S.                                           ***
 ***                                                                                ***
 ***                        RESTRICTED RIGHTS LEGEND                                ***
 ***  USE, DUPLICATION, OR DISCLOSURE BY THE GOVERNMENT OF THE CONTENT OF THIS      ***
 ***  WORK OR RELATED DOCUMENTATION IS SUBJECT TO RESTRICTIONS AS SET FORTH IN      ***
 ***  SUBPARAGRAPH (C)(1) OF THE COMMERCIAL COMPUTER SOFTWARE RESTRICTED RIGHT      ***
 ***  CLAUSE  AT FAR 52.227-19  OR SUBPARAGRAPH  (C)(1)(II)  OF  THE RIGHTS IN      ***
 ***  TECHNICAL DATA AND COMPUTER SOFTWARE CLAUSE AT DFARS 52.227-7013.             ***
 ***                                                                                ***
 ***                   COPYRIGHT (C) 1996-2024 BY FEI S.A.S,                        ***
 ***                        BORDEAUX, FRANCE                                        ***
 ***                      ALL RIGHTS RESERVED                                       ***
**=======================================================================*/
/*=======================================================================
** Author      : T. DUFOUR (May 2005)
**=======================================================================*/
 
#ifndef  _SO_LDM_TOPO_OCTREE_
#define  _SO_LDM_TOPO_OCTREE_
 
#include <Inventor/SbLinear.h>
#include <Inventor/SbBox.h>
#include <LDM/SoLDMTileID.h>
 
class SoLDMOctreeNode;
 
 
#ifdef _MSC_VER
#pragma warning( push )
#pragma warning(disable:4251)
#endif
 
// Note : this level will be never reached (at least this century!)
#define LEVEL_MAX 20
 
class  SoLDMTopoOctree
{
 
public:
 
  SoLDMTopoOctree();
 
  void init(const SbVec3i32& dimension, const SbVec3i32& tileDim, const int border = 0);
 
  void init(const SbVec3i32& dimension, const int tileDim, const int border=0)
  {
    init(dimension, SbVec3i32(tileDim, tileDim, tileDim), border);
  }
 
  SbBox3i32 getTilePos( const SoLDMTileID& tileID )const;
 
  SoLDMTileID getTileID( const SbVec3i32& cellPos, const int resolutionLevel )const;
 
  int getNumFileIDs()const;
 
  inline size_t getNumTileIDs()const;
 
  inline int getFileID( const SoLDMTileID& tileID )const;
 
  SoLDMTileID getTileID( const int fileID )const;
 
  inline bool isEmpty() const
  { return (m_numFileIDs<=0); }
 
  int getLevelMax()const;
 
  inline int level( const SoLDMTileID& id ) const;
 
  int level( const LDM_TILE_ID_TYPE index ) const;
 
  const SbVec3i32& getTileSize() const
  {
    return m_tileDim;
  }
 
private:
 
  
  enum Location
  {
    LEFT =  0x01,
    RIGHT = 0x02,
    BOTTOM = 0x04,
    TOP = 0x08,
    FRONT = 0x10,
    BACK = 0x20
  };
  int opposite(int locationMask) const;
 
  static const int s_allLocations[26];
 
  ~SoLDMTopoOctree();
 
  SbVec3i32 getTileOrigin( const LDM_TILE_ID_TYPE tileID )const;
 
  LDM_TILE_ID_TYPE parent( const LDM_TILE_ID_TYPE index )const;
  inline LDM_TILE_ID_TYPE children( const LDM_TILE_ID_TYPE index )const;
 
  LDM_TILE_ID_TYPE getNumTilesAtDepth( const int level )const;
  LDM_TILE_ID_TYPE getSumTilesAtDepth( const int level )const;
 
  int getNumFileIDsAtDepth( const int level )const;
  int getSumFileIDsAtDepth( const int level )const;
  int sizeofTiles( const int numTile, int tileDim )const;
 
  inline bool hasChildren(const SoLDMTileID& tileId) const;
 
  const SbVec3i32& getTileDimAtLevel(int l) const
  {
    return m_tileDimAtLevel[l];
  }
 
  const SbVec3i32& getTileDimAtLevel(const SoLDMTileID& id) const;
 
  inline bool isChildOf(const SoLDMTileID& parent,
                        const SoLDMTileID& child) const;
 
  inline bool isInFamilyOf(const SoLDMTileID& parent, const SoLDMTileID& child) const;
 
 
  SbVec3i32 getTileSpacePos( const LDM_TILE_ID_TYPE tileID , const int tileLevel ) const;
 
  SoLDMTileID getTileSpaceID( const SbVec3i32& cellPos, const int level) const;
 
  SoLDMTileID getNeighborTile(const SoLDMTileID& tileID, int locationMask) const;
 
  SoLDMOctreeNode* operator [](const LDM_TILE_ID_TYPE tileID)const;
  SoLDMOctreeNode* operator ()(const int fileID)const;
 
  inline static void getOrderedOctant(int octantOrder[8], const SbVec3f & viewVector);
 
  /* Allow the octree to use (or not) the optimisation made on thin volume */
  void useThinOptim(bool useThinVolumeOptim);
 
  inline int getMaxNumChildren() const
  { return m_maxNumChildren; }
 
  void commonInit( const SbVec3i32& dimension, const SbVec3i32& tileDim, const int border=0 );
 
  const SbVec3i32& getVolumeDimensions() const
  {
    return m_dimension;
  }
 
private:
  void fillTileDimAtLevel();
 
  SbVec3i32 getTileOrigin( const LDM_TILE_ID_TYPE tileID, int tileLevel ) const;
 
  int getFileIDReverseTable( const SoLDMTileID& tileID )const;
 
  static float computeLevelMax(unsigned int maxDim, unsigned int tileDim,
                               unsigned int border);
 
  static const int MAX_OCTREE_DEPTH;
 
  // precomputed data
  static const uint64_t s_numTilesAtDepth[LEVEL_MAX+1];
  static const uint64_t s_sumTilesAtDepth[LEVEL_MAX+2];
 
  // data depending on the volume dimension
  SbVec3i32         m_dimension;
  SbVec3i32         m_tileDim;
  int               m_border;
  int               m_levelMax;
  int               m_maxNumChildren;
  LDM_TILE_ID_TYPE  m_numTileIDs;
  int               m_numFileIDs;
  SoLDMOctreeNode  *m_tileIDs;
  int*              m_fileIDs;
  int               m_numFileIDsAtDepth[LEVEL_MAX+1];
  int               m_sumFileIDsAtDepth[LEVEL_MAX+1];
  bool              m_initIsDone;
  static const unsigned int TDimension;
 
  std::vector<SbVec3i32> m_tileDimAtLevel;
 
  /* Indicate if the octree can use thin volume optimization */
  bool m_useThinVolumeOptim;
 
};
 
/******************************************************************************/
size_t
SoLDMTopoOctree::getNumTileIDs() const
{
  return (size_t)(m_numTileIDs);
}
 
/******************************************************************************/
bool
SoLDMTopoOctree::hasChildren(const SoLDMTileID& tileId) const
{
  return children(tileId.getID()) < (LDM_TILE_ID_TYPE)getNumTileIDs() ;
}
 
/******************************************************************************/
int
SoLDMTopoOctree::level(const SoLDMTileID& id) const
{
  return level(id.getID());
}
 
/******************************************************************************/
bool
SoLDMTopoOctree::isChildOf(const SoLDMTileID& parent, const SoLDMTileID& child) const
{
  if ( child.getID() >= m_numTileIDs )
    return false;
 
  LDM_TILE_ID_TYPE firstChild = children(parent.getID());
  LDM_TILE_ID_TYPE childId = child.getID();
  return childId >= firstChild && childId < firstChild+8;
}
 
/******************************************************************************/
bool 
SoLDMTopoOctree::isInFamilyOf(const SoLDMTileID& _parent, const SoLDMTileID& child) const
{
  LDM_TILE_ID_TYPE childId = child.getID();
  LDM_TILE_ID_TYPE parentId = _parent.getID();
  if ( childId >= m_numTileIDs || childId < 0 )
    return false;
  else if ( childId == parentId)
    return true;
  else
  {
    LDM_TILE_ID_TYPE parentChildID = parent(childId);
    if ( parentChildID == parentId )
      return true;
    else
      return isInFamilyOf(_parent,parentChildID);
  }
  return false;
}
 
/******************************************************************************/
int
SoLDMTopoOctree::getFileID( const SoLDMTileID& tileID )const
{
  if ( tileID.getID()<0 || tileID.getID()>=m_numTileIDs)
    return -1;
 
  // if m_fileIDs exists, use it straight
  if ( m_fileIDs )
    return m_fileIDs[tileID.getID()] - 1;
 
  return getFileIDReverseTable(tileID);
}
 
/******************************************************************************/
LDM_TILE_ID_TYPE
SoLDMTopoOctree::children( const LDM_TILE_ID_TYPE index )const
{
  return (index << TDimension) + 1;
}
 
/******************************************************************************/
void
SoLDMTopoOctree::getOrderedOctant(int octantOrder[8], const SbVec3f & viewVector)
{
  int bitMask = 0;
  for ( int i = 0; i < 3; i++ )
    bitMask |= (viewVector[i] < 0) << i;
  for ( unsigned int i = 0; i < 8; i++ )
    octantOrder[i] = i^bitMask;
}
 
#ifdef _MSC_VER
#pragma warning( pop )
#endif
 
#endif /* _SO_LDM_TOPO_OCTREE_ */