gpuCache/gpuCacheSpatialGrid.h

#ifndef __SpatialGrid_h 
#define __SpatialGrid_h 
//-----------------------------------------------------------------------------
//
//  Class: SpatialGrid
//  
//  Purpose: 
//           This class just provides a bunch of grid cells containing
//           lists of index data, and some indexing functions to find
//           grid cells corresponding to bounding boxes in space.  The
//           voxel grid is axis-aligned.
//
//           The SpatialGridWalker iterator knows how to walk through
//           the grid cells that are intersected by a ray.
//
//           The voxels are organized into a flat array, in X-Y-Z order
//           (moving linearly through array, X coordinate grows fastest,
//           then Y, then Z).
// 
//           Data in the spatial grid is blind, i.e. the underlying
//           class does not understand anything about the data (other
//           than it is a uint). The ideal way to store data in
//           the table would be to create your own array of data then
//           use the indices of that array to map the contents of the
//           grid to your domain specific data.
// 
//
//-----------------------------------------------------------------------------

#include <maya/MBoundingBox.h>
#include <maya/MIntArray.h>
#include <maya/MUintArray.h>

#include <vector>

// Class represents a 3-integer index to the spatial grid.
// Contains a comparison value to be used in 
// sorting grid points (used along with std::set)
template <class T>
class gridPoint3 {
public:
    gridPoint3(){}
    gridPoint3(T _1, T _2, T _3){
        fData[0] = _1;
        fData[1] = _2;
        fData[2] = _3;
        fCompareVal = fData[0]+3083*fData[1]+7919*fData[2]; //using two prime numbers
    }

    operator T *(){return fData;}
    operator const T *() const{return fData;}
    double compareVal()const { return fCompareVal; }
    
    gridPoint3 operator+ (const gridPoint3& x) const{gridPoint3 y(x); y.fData[0]+=fData[0]; y.fData[1]+=fData[1]; y.fData[2]+=fData[2]; return y; }
    gridPoint3 operator+ (const T& x) const{ gridPoint3 y(*this); y.fData[0]+=x; y.fData[1]+=x; y.fData[2]+=x; return y; }
    gridPoint3 operator- (const T& x) const{ gridPoint3 y(*this); y.fData[0]-=x; y.fData[1]-=x; y.fData[2]-=x; return y; }
    gridPoint3 operator* (const gridPoint3& x) const{gridPoint3 y(x); y.fData[0]*=fData[0]; y.fData[1]*=fData[1]; y.fData[2]*=fData[2]; return y;}
    gridPoint3 operator* (const T& x)  const{ gridPoint3 y(*this); y.fData[0]*=x; y.fData[1]*=x; y.fData[2]*=x; return y; }

    gridPoint3& operator+= (const gridPoint3& x){ fData[0]+=x[0]; fData[1]+=x[1]; fData[2]+=x[2]; return *this;}
    gridPoint3& operator*= (const gridPoint3& x){fData[0]*=x[0]; fData[1]*=x[1]; fData[2]*=x[2]; return *this;}
    gridPoint3& operator*= (const T& x){fData[0]*=x;    fData[1]*=x;    fData[2]*=x;    return *this;}

    bool operator< (const gridPoint3& y) const{
        return fCompareVal < y.compareVal();
    }

private:
    T fData[3];
    double fCompareVal;
};

class SpatialGridWalker;

class SpatialGrid { 
public:
    //  constructor specifies region of space to be gridded, and number of
    //  grid cells along each dimension
    //
    SpatialGrid( const MBoundingBox& bound, const gridPoint3<int>& numVoxels );

    virtual ~SpatialGrid();

    //  retrieves an iterator that walks through grid cells intersected
    //  by the ray from "origin" along "direction"
    //
    SpatialGridWalker getRayIterator( const MPoint& origin,
        const MVector& direction );

    //  computes x,y,z voxel coords for given 3d point (assumed to be 
    //  inside bounding box).  Optionally returns residual, which is
    //  distances from point to next-lowest grid lines in x, y, z
    //
    void getVoxelCoords( const MPoint& point, 
        gridPoint3<int>& coords, 
        MPoint *residual = NULL ) const;

    void getClosestVoxelCoords( const MPoint& point, 
        gridPoint3<int>& coords) const;

    bool isValidVoxel(gridPoint3<int>& vox);

    //  returns x, y, z index ranges of voxels at least partially
    //  intersected by given bounding box
    //
    void getVoxelRange( const MBoundingBox& box, 
        gridPoint3<int>& minIndices, 
        gridPoint3<int>& maxIndices ) const;

    //  gets triangle list for given voxel
    //                      
    MUintArray *            getVoxelContents( const gridPoint3<int>& index );

    //  accessors useful for debugging output
    //
    const gridPoint3<int>&          getNumVoxels();
    virtual float           getMemoryFootprint();

    MBoundingBox getBounds(){ return fBounds;}
    //  iterator gets internal access
    //
    friend class SpatialGridWalker; 

private:
    //  accessors for bounding box, bounding box corners
    //
    const MBoundingBox& bounds();
    void bounds( MPoint& lowCorner, 
        MPoint& highCorner );

    //  converts from x,y,z index to linear index into 
    //  voxel array
    //  
    int getLinearVoxelIndex( const gridPoint3<int>& index ) const;

    //  bounding box for the entire grid
    //
    MBoundingBox                fBounds;

    //  number of grid cells along each axis
    //
    gridPoint3<int>                     fNumVoxels;

    //  dimensions of each voxel in x, y, z
    //
    gridPoint3<float>                       fVoxelSizes;

    //  The actual voxel grid contents, one array entry for each voxel.
    //  Each voxel stores a pointer to a index array, pointers are
    //  all NULL originally. The index array is intended to be data blind.
    //  That is, we don't know what the indices they refer to.  
    //
    std::vector<MUintArray*>        fVoxels;

    void expandBBoxByPercentage( 
        MBoundingBox& bbox,
        double percentage,
        double min[3] 
    );
    
};
#endif