DataStructures.h

#pragma once
 
#include "GeometryTools.h"
#include "ObjectFactoryStack.h"
 
namespace CoRiBoDynamics{
 
namespace DataStructures{
 
struct LINKEDLIST {LINKEDLIST* next; int value;};
 
 
class RadixSparseSet{
public:
    static const unsigned int BUFFER_SIZE = 128;
    static const unsigned int BRANCH_FACTOR = 4;
    static const unsigned int TREE_DEPTH = 4;
 
    static const unsigned int BLOCK_SIZE = 0x1<<BRANCH_FACTOR;
    static const unsigned int BIT_MASK = BLOCK_SIZE-1;
    static const unsigned int MAX_INDEX = 0x1<<(TREE_DEPTH*BRANCH_FACTOR);
 
    RadixSparseSet();
 
    void insert(int value); // adds value to set
    bool insert_and_check(int value); // adds value to set. return true if it was already present 
    bool check(int value); // return true if value is present
 
    LINKEDLIST* getValues(); // get linked list of all values in set
 
    void reset(); // remove all values from set
protected:
    struct ARRAY {
        void* POINTERS[BLOCK_SIZE];
        void SetToNULL(){for(size_t i = 0; i < BLOCK_SIZE; ++i){POINTERS[i] = nullptr;}}
    };
    ARRAY m_rootArray;
    ObjectFactoryStack<ARRAY> m_ARRAY_factory;
    ObjectFactoryStack<LINKEDLIST> m_List_factory;
};
 
class Sparse3DArray{
public:
static const unsigned int BUFFER_SIZE = 512;
static const unsigned int BRANCH_FACTOR = 5;
static const unsigned int TREE_DEPTH = 3;
 
static const unsigned int BLOCK_SIZE = 0x1<<BRANCH_FACTOR;
static const unsigned int INDEX_SIZE = 3*TREE_DEPTH;
static const unsigned int BIT_MASK = BLOCK_SIZE-1;
static const unsigned int MAX_INDEX = 0x1<<(TREE_DEPTH*BRANCH_FACTOR);
 
    Sparse3DArray();
 
    ~Sparse3DArray();
 
    void InsertToMap(int x, int y, int z, int ID, RadixSparseSet* set); // adds ID to map at coordinates x,y,z. previously present values are added to set
    void CheckMap(int x, int y, int z, RadixSparseSet* set); // adds all values at coordinates x,y,z to set
    void Reset(); // remove all values from map
 
protected:
    struct ARRAY {
        void* POINTERS[BLOCK_SIZE];
        void SetToNULL(){for(size_t i = 0; i < BLOCK_SIZE; ++i){POINTERS[i] = nullptr;}}
    };
 
    struct INDEX {int i[INDEX_SIZE];};
 
    struct LINKEDLIST {int value; LINKEDLIST* next;};
 
    INDEX convert(int x, int y, int z);
 
    ARRAY m_rootArray;
 
    ObjectFactoryStack<ARRAY> m_ARRAY_factory;
    ObjectFactoryStack<LINKEDLIST> m_List_factory;
};
 
class SpacePartitioner{
public:
    SpacePartitioner();
 
    // tuning parameter for grid cell side length. to large value gives more false collition positives, too small value gives high cell count allocation and a smaller total bounding volume
    void SetLength(double length); 
 
    // insert ID into all grid cells that contains any part of boundingVolume. Returns all values already present.
    LINKEDLIST* InsertToMap(const GeometryTools::AABB& boundingVolume, int ID);
 
    // returns all values in grid cells that contains any part of boundingVolume
    LINKEDLIST* CheckMap(const GeometryTools::AABB& boundingVolume); 
 
    // remove all values from map
    void Reset(); 
    void setOrigo(double x, double y, double z);
 
protected:
    Sparse3DArray m_Array;
    struct SpatialIndex{unsigned int x; unsigned int y; unsigned int z; SpatialIndex(unsigned int X, unsigned int Y, unsigned int Z){x=X;y=Y;z=Z;}};
    SpatialIndex CoordinateToIndex( double d_x, double d_y, double d_z );
 
    DataStructures::RadixSparseSet m_CollisionTestSet;
 
    double m_lengthInv;
 
    double m_origoX;
    double m_origoY;
    double m_origoZ;
};
 
}
 
}