RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc > Class Template Reference

#include "RegularGrid.h"

Inheritance diagram for RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >:

Classes
struct	Cell

Public Types
enum	{ CELL_NUMBER = 64 }
typedef G3D::Table< const T *, NodeArray< Node > >	MemberTable

Public Member Functions
	RegularGrid2D ()
	~RegularGrid2D ()
void	insert (const T &value)
void	remove (const T &value)
void	balance ()
bool	contains (const T &value) const
int	size () const
Node &	getGridFor (float fx, float fy)
Node &	getGrid (int x, int y)
template<typename RayCallback >
void	intersectRay (const G3D::Ray &ray, RayCallback &intersectCallback, float max_dist, bool stopAtFirstHit)
template<typename RayCallback >
void	intersectRay (const G3D::Ray &ray, RayCallback &intersectCallback, float &max_dist, const G3D::Vector3 &end, bool stopAtFirstHit)
template<typename IsectCallback >
void	intersectPoint (const G3D::Vector3 &point, IsectCallback &intersectCallback)
template<typename RayCallback >
void	intersectZAllignedRay (const G3D::Ray &ray, RayCallback &intersectCallback, float &max_dist)

Public Attributes
MemberTable	memberTable
Node *	nodes [CELL_NUMBER][CELL_NUMBER]

Detailed Description

template<class T, class Node, class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>
class RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >

Member Typedef Documentation

MemberTable

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

typedef G3D::Table<const T*, NodeArray<Node> > RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::MemberTable

Member Enumeration Documentation

anonymous enum

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

anonymous enum

Enumerator
CELL_NUMBER

    {
        CELL_NUMBER = 64,
    };

Constructor & Destructor Documentation

RegularGrid2D()

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::RegularGrid2D ( )

inline

    {
        memset(nodes, 0, sizeof(nodes));
    }

References RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::nodes.

~RegularGrid2D()

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::~RegularGrid2D ( )

inline

    {
        for (int x = 0; x < CELL_NUMBER; ++x)
            for (int y = 0; y < CELL_NUMBER; ++y)
            {
                delete nodes[x][y];
            }
    }

References RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::CELL_NUMBER, and RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::nodes.

Member Function Documentation

balance()

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

void RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::balance ( )

inline

    {
        for (int x = 0; x < CELL_NUMBER; ++x)
            for (int y = 0; y < CELL_NUMBER; ++y)
                if (Node* n = nodes[x][y])
                {
                    n->balance();
                }
    }

References RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::CELL_NUMBER, and RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::nodes.

Referenced by DynTreeImpl::balance().

contains()

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

bool RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::contains ( const T &  value ) const

inline

{ return memberTable.containsKey(&value); }

References RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::memberTable.

Referenced by DynamicMapTree::contains().

getGrid()

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

Node & RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::getGrid ( int  x, int  y  )

inline

    {
        ASSERT(x < CELL_NUMBER && y < CELL_NUMBER);
        if (!nodes[x][y])
        {
            nodes[x][y] = NodeCreatorFunc::makeNode(x, y);
        }
        return *nodes[x][y];
    }

References ASSERT, RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::CELL_NUMBER, and RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::nodes.

Referenced by RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::getGridFor().

getGridFor()

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

Node & RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::getGridFor ( float  fx, float  fy  )

inline

    {
        Cell c = Cell::ComputeCell(fx, fy);
        return getGrid(c.x, c.y);
    }

References RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::ComputeCell(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::getGrid(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::x, and RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::y.

Referenced by RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::insert().

insert()

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

void RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::insert ( const T &  value )

inline

    {
        G3D::Vector3 pos[9];
        pos[0] = value.GetBounds().corner(0);
        pos[1] = value.GetBounds().corner(1);
        pos[2] = value.GetBounds().corner(2);
        pos[3] = value.GetBounds().corner(3);
        pos[4] = (pos[0] + pos[1]) / 2.0f;
        pos[5] = (pos[1] + pos[2]) / 2.0f;
        pos[6] = (pos[2] + pos[3]) / 2.0f;
        pos[7] = (pos[3] + pos[0]) / 2.0f;
        pos[8] = (pos[0] + pos[2]) / 2.0f;
 
        NodeArray<Node> na;
        for (uint8 i = 0; i < 9; ++i)
        {
            Cell c = Cell::ComputeCell(pos[i].x, pos[i].y);
            if (!c.isValid())
            {
                continue;
            }
            Node& node = getGridFor(pos[i].x, pos[i].y);
            na.AddNode(&node);
        }
 
        for (uint8 i = 0; i < 9; ++i)
        {
            if (na._nodes[i])
            {
                na._nodes[i]->insert(value);
            }
            else
            {
                break;
            }
        }
 
        memberTable.set(&value, na);
    }

References NodeArray< Node >::_nodes, NodeArray< Node >::AddNode(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::ComputeCell(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::getGridFor(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::isValid(), and RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::memberTable.

Referenced by DynTreeImpl::insert().

intersectPoint()

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

template<typename IsectCallback >

void RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::intersectPoint ( const G3D::Vector3 &  point, IsectCallback &  intersectCallback  )

inline

    {
        Cell cell = Cell::ComputeCell(point.x, point.y);
        if (!cell.isValid())
        {
            return;
        }
        if (Node* node = nodes[cell.x][cell.y])
        {
            node->intersectPoint(point, intersectCallback);
        }
    }

References RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::ComputeCell(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::isValid(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::nodes, RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::x, and RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::y.

Referenced by DynamicMapTree::GetAreaAndLiquidData(), and DynamicMapTree::GetAreaInfo().

intersectRay() [1/2]

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

template<typename RayCallback >

void RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::intersectRay ( const G3D::Ray &  ray, RayCallback &  intersectCallback, float &  max_dist, const G3D::Vector3 &  end, bool  stopAtFirstHit  )

inline

    {
        Cell cell = Cell::ComputeCell(ray.origin().x, ray.origin().y);
        if (!cell.isValid())
        {
            return;
        }
 
        Cell last_cell = Cell::ComputeCell(end.x, end.y);
 
        if (cell == last_cell)
        {
            if (Node* node = nodes[cell.x][cell.y])
            {
                node->intersectRay(ray, intersectCallback, max_dist, stopAtFirstHit);
            }
            return;
        }
 
        float voxel = (float)CELL_SIZE;
        float kx_inv = ray.invDirection().x, bx = ray.origin().x;
        float ky_inv = ray.invDirection().y, by = ray.origin().y;
 
        int stepX, stepY;
        float tMaxX, tMaxY;
        if (kx_inv >= 0)
        {
            stepX = 1;
            float x_border = (cell.x + 1) * voxel;
            tMaxX = (x_border - bx) * kx_inv;
        }
        else
        {
            stepX = -1;
            float x_border = (cell.x - 1) * voxel;
            tMaxX = (x_border - bx) * kx_inv;
        }
 
        if (ky_inv >= 0)
        {
            stepY = 1;
            float y_border = (cell.y + 1) * voxel;
            tMaxY = (y_border - by) * ky_inv;
        }
        else
        {
            stepY = -1;
            float y_border = (cell.y - 1) * voxel;
            tMaxY = (y_border - by) * ky_inv;
        }
 
        //int Cycles = std::max((int)ceilf(max_dist/tMaxX),(int)ceilf(max_dist/tMaxY));
        //int i = 0;
 
        float tDeltaX = voxel * std::fabs(kx_inv);
        float tDeltaY = voxel * std::fabs(ky_inv);
        do
        {
            if (Node* node = nodes[cell.x][cell.y])
            {
                //float enterdist = max_dist;
                node->intersectRay(ray, intersectCallback, max_dist, stopAtFirstHit);
            }
            if (cell == last_cell)
            {
                break;
            }
            if (tMaxX < tMaxY)
            {
                tMaxX += tDeltaX;
                cell.x += stepX;
            }
            else
            {
                tMaxY += tDeltaY;
                cell.y += stepY;
            }
            //++i;
        } while (cell.isValid());
    }

References CELL_SIZE, RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::ComputeCell(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::isValid(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::nodes, RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::x, and RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::y.

intersectRay() [2/2]

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

template<typename RayCallback >

void RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::intersectRay ( const G3D::Ray &  ray, RayCallback &  intersectCallback, float  max_dist, bool  stopAtFirstHit  )

inline

    {
        intersectRay(ray, intersectCallback, max_dist, ray.origin() + ray.direction() * max_dist, stopAtFirstHit);
    }

References RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::intersectRay().

Referenced by DynamicMapTree::GetIntersectionTime(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::intersectRay(), and DynamicMapTree::isInLineOfSight().

intersectZAllignedRay()

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

template<typename RayCallback >

void RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::intersectZAllignedRay ( const G3D::Ray &  ray, RayCallback &  intersectCallback, float &  max_dist  )

inline

    {
        Cell cell = Cell::ComputeCell(ray.origin().x, ray.origin().y);
        if (!cell.isValid())
        {
            return;
        }
        if (Node* node = nodes[cell.x][cell.y])
        {
            node->intersectRay(ray, intersectCallback, max_dist, false);
        }
    }

References RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::ComputeCell(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::isValid(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::nodes, RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::x, and RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::Cell::y.

Referenced by DynamicMapTree::getHeight().

remove()

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

void RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::remove ( const T &  value )

inline

    {
        NodeArray<Node>& na = memberTable[&value];
        for (uint8 i = 0; i < 9; ++i)
        {
            if (na._nodes[i])
            {
                na._nodes[i]->remove(value);
            }
            else
            {
                break;
            }
        }
 
        // Remove the member
        memberTable.remove(&value);
    }

References NodeArray< Node >::_nodes, and RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::memberTable.

Referenced by DynTreeImpl::remove().

size()

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

int RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::size ( ) const

inline

{ return memberTable.size(); }

References RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::memberTable.

Referenced by DynamicMapTree::size(), and DynTreeImpl::update().

Member Data Documentation

memberTable

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

MemberTable RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::memberTable

Referenced by RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::contains(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::insert(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::remove(), and RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::size().

nodes

template<class T , class Node , class NodeCreatorFunc = NodeCreator<Node>, class PositionFunc = PositionTrait<T>>

Node* RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::nodes[CELL_NUMBER][CELL_NUMBER]

Referenced by RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::balance(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::getGrid(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::intersectPoint(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::intersectRay(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::intersectZAllignedRay(), RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::RegularGrid2D(), and RegularGrid2D< T, Node, NodeCreatorFunc, PositionFunc >::~RegularGrid2D().