octree.h

Go to the documentation of this file.

#ifndef __OCTREE_H__
#define __OCTREE_H__


#ifdef _MSC_VER  
typedef __int32 int32_t; 
typedef unsigned __int32 uint32_t; 
typedef __int64 int64_t; 
typedef unsigned __int64 uint64_t;  
#else 
#include <stdint.h> 
#endif 

#include <deque>
#include <vector>

#ifdef _OPENMP
//#include <thrust/sort.h>
//#include <thrust/host_vector.h>
//#include <thrust/system/omp/vector.h>
#endif


//#include "particle_bunch.h"


using namespace std;

struct SearchResult {
  double distance; 
  int index; 
  bool operator < (const SearchResult& sr) const {
    return (distance < sr.distance);
  }
};





struct KeyIndex
{
  int key;//Should be a 32/64 bit integer. With a 32 bit integer we can use Octrees of depth 10. With a 64 bit integer we can use octrees of depth 20.
  int index;
  bool operator < (const KeyIndex& a) const
  {
    return (key < a.key);
  }
};



class Octree {

private:

  size_t m_iMaxParticleNum;

  //vector<ParticleBunch*> *m_vParticleBunchList;

  const double *m_vCoordX;
  const double *m_vCoordY;
  const double *m_vCoordZ;

  int m_iTotalNumberOfParticles;
 
#ifdef _OPENMP
  //thrust::omp::vector<KeyIndex> m_vParticleKeyIndex;
  //thrust::host_vector<KeyIndex> m_vParticleKeyIndex;
  //std::vector<KeyIndex> m_vParticleKeyIndex;
  KeyIndex *m_vParticleKeyIndex;
#else
  KeyIndex *m_vParticleKeyIndex;
#endif
                        
  int m_iMaxDepth;

  int m_iLinearSearchDepth;
  //int maxParticleNumInCell;

  double m_dBoundingBox_min_x ;

  double m_dBoundingBox_max_x ;
 
  double m_dBoundingBox_min_y ;

  double m_dBoundingBox_max_y ;

  double m_dBoundingBox_min_z ;

  double m_dBoundingBox_max_z ;


  int m_iTreeLength;
  


  int* m_vNodeKey;
  
  int* m_vDepth;

  int* m_vFirstParticleIndex;
  
  int* m_vNumberOfContainedParticles;

  int* m_vFirstChildIndex;
  
  int* m_vNumberOfChildren;

  double* m_vLowerLimitOfX;
  
  double* m_vLowerLimitOfY;
  
  double* m_vLowerLimitOfZ;

  double* m_vUpperLimitOfX;
  
  double* m_vUpperLimitOfY;
  
  double* m_vUpperLimitOfZ;


  //vector<int>* m_vParticleNumList;

public:
  //Octree(int treedepth, int numOfParticles);
  Octree(int treedepth, size_t maxParticleNum);
  virtual ~Octree();


  //int initialize();
  int buildOctree(const double* x, const double* y, const double* z, size_t numParticles);
  //int buildOctree(const double *xp, const double *yp, const double *zp);

  int searchNeighbor(const double search_x, const double search_y, const double search_z, const double radius, int* result, size_t& result_length);

  int searchNeighbor(const double search_x, const double search_y, const double search_z, const double radius, SearchResult* result, size_t& result_length);

private:
  inline uint32_t computeKey(const double& x, const double& y, const double& z);

  //void oneDimIndexTo2DimPair(vector<int>* numParticles, int index, int& clusterIndex, int& particleIndex);
};


#endif // __OCTREE_H__