AACubeTree.hpp

Go to the documentation of this file.

namespace GfxTL
{
 
    //-- AACubeCell
 
    template <class Point, class Base>
    AACubeCell<Point, Base>::AACubeCell() : _parent(NULL)
    {
        memset(_children, 0, sizeof(_children));
    }
 
    template <class Point, class Base>
    AACubeCell<Point, Base>::AACubeCell(ThisType* parent, const CubeType& cube) :
        _parent(parent), _cube(cube)
    {
        memset(_children, 0, sizeof(_children));
    }
 
    template <class Point, class Base>
    AACubeCell<Point, Base>::~AACubeCell()
    {
        for (int i = 0; i < NChildren; ++i)
        {
            if (_children[i])
            {
                delete _children[i];
            }
        }
    }
 
    template <class Point, class Base>
    const AACubeCell<Point, Base>*
    AACubeCell<Point, Base>::operator[](unsigned int index) const
    {
        return _children[index];
    }
 
    template <class Point, class Base>
    AACubeCell<Point, Base>*
    AACubeCell<Point, Base>::operator[](unsigned int index)
    {
        return _children[index];
    }
 
    template <class Point, class Base>
    void
    AACubeCell<Point, Base>::Child(unsigned int index, ThisType* child)
    {
        _children[index] = child;
    }
 
    template <class Point, class Base>
    typename AACubeCell<Point, Base>::CubeType&
    AACubeCell<Point, Base>::Cube()
    {
        return _cube;
    }
 
    template <class Point, class Base>
    const typename AACubeCell<Point, Base>::CubeType&
    AACubeCell<Point, Base>::Cube() const
    {
        return _cube;
    }
 
    template <class Point, class Base>
    AACubeCell<Point, Base>*
    AACubeCell<Point, Base>::Parent()
    {
        return _parent;
    }
 
    template <class Point, class Base>
    const AACubeCell<Point, Base>*
    AACubeCell<Point, Base>::Parent() const
    {
        return _parent;
    }
 
    template <class Point, class Base>
    void
    AACubeCell<Point, Base>::Parent(ThisType* parent)
    {
        _parent = parent;
    }
 
    template <class Point, class Base>
    AACubeCell<Point, Base>*
    AACubeCell<Point, Base>::FaceNeighborIndexed(unsigned int index, unsigned int* level)
    {
        int axis = index >> 1;
        ++axis;
        if (index & 1)
        {
            axis = -axis;
        }
        return FaceNeighbor(axis, level);
    }
 
    template <class Point, class Base>
    const AACubeCell<Point, Base>*
    AACubeCell<Point, Base>::FaceNeighborIndexed(unsigned int index, unsigned int* level) const
    {
        int axis = index >> 1;
        ++axis;
        if (index & 1)
        {
            axis = -axis;
        }
        return FaceNeighbor(axis, level);
    }
 
    template <class Point, class Base>
    AACubeCell<Point, Base>*
    AACubeCell<Point, Base>::FaceNeighbor(int axis, unsigned int* level)
    {
        int box = SubBox();
        if (box < 0)
        {
            return NULL;
        }
        int a = axis;
        if (a > 0)
        {
            a -= 1;
            if (box & (1 << a))
            {
                return (*_parent)[box & ~(1 << a)];
            }
        }
        if (a < 0)
        {
            a = (-a) - 1;
            if (!(box & (1 << a)))
            {
                return (*_parent)[box | (1 << a)];
            }
        }
        unsigned int l = *level;
        ++(*level);
        ThisType* c = _parent->FaceNeighbor(axis, level);
        if (!c)
        {
            return NULL;
        }
        int invBox = box;
        if (invBox & (1 << a))
        {
            invBox &= ~(1 << a);
        }
        else
        {
            invBox |= 1 << a;
        }
        if (*level == l + 1 && (*c)[invBox])
        {
            --(*level);
            c = (*c)[invBox];
        }
        return c;
    }
 
    template <class Point, class Base>
    const AACubeCell<Point, Base>*
    AACubeCell<Point, Base>::FaceNeighbor(int axis, unsigned int* level) const
    {
        return const_cast<ThisType*>(this)->FaceNeighbor(axis, level);
    }
 
    template <class Point, class Base>
    int
    AACubeCell<Point, Base>::SubBox() const
    {
        unsigned int box;
        if (!_parent)
        {
            return -1;
        }
        if (!(_parent->Cube().IsSubCube(&box, Cube())))
        {
            assert(false);
            return -1;
        }
        return (int)box;
    }
 
    //-- AACubeTree
 
    template <class Strategies>
    void
    AACubeTree<Strategies>::Clear()
    {
        StrategyBaseType::Clear();
        _cellCount = 0;
    }
 
    template <class Strategies>
    void
    AACubeTree<Strategies>::Build()
    {
        AABox<PointType> bbox;
        BoundingVolume(&bbox);
        PointType center;
        bbox.Center(&center);
        ScalarType w = (bbox.Max() - bbox.Min()).Length();
        PointType bbl;
        for (unsigned int i = 0; i < PointType::Dim; ++i)
        {
            bbl[i] = center[i] - (w / 2);
        }
        CubeType bc(bbl, w);
        /*CubeType bc;
        BoundingCube(&bc);*/
        CubeType cc(bc[CubeType::NCorners - 1] * (ScalarType)1.2, bc.Width() * (ScalarType)1.2);
        Build(cc);
    }
 
    template <class Strategies>
    void
    AACubeTree<Strategies>::Build(const CubeType& bc)
    {
        Clear();
 
        std::queue<CellType*>* q;
        std::queue<CellType*>* qq;
        std::queue<CellType*> q1, q2, level;
 
        CellType* c = new CellType(NULL, bc);
        RootCellData(bc, c); // implemented by TreeData
        q1.push(c);
        Root(c); // implemented by BaseTree
        InitCellData(c); // implemented by Strategies
        q = &q1;
        qq = &q2;
 
        do
        {
            while (q->size())
            {
                c = q->front();
                level.push(c);
                q->pop();
                //InitCellData(c); // implemented by Strategies
                if (ShouldSubdivide(*c)) // implemented by Strategies
                {
                    Subdivide(c);
                    for (int i = 0; i < CellType::NChildren; ++i)
                    {
                        qq->push((*c)[i]);
                    }
                    _cellCount += CellType::NChildren;
                }
            }
            std::queue<CellType*>* qqq = q;
            q = qq;
            qq = qqq;
 
            while (level.size())
            {
                c = level.front();
                level.pop();
                InitLevelDependentCellData(c); // implemented by Strategies
            }
        } while (q->size());
    }
 
    template <class Strategies>
    void
    AACubeTree<Strategies>::Subdivide(CellType* cell)
    {
        Subdivide(cell, 0, 0, cell);
        for (unsigned int i = 0; i < CellType::NChildren; ++i)
        {
            InitCellData((*cell)[i]); // implemented by Strategies
        }
    }
 
    template <class Strategies>
    void
    AACubeTree<Strategies>::RefreshWithNewTreeData(const CubeType& bc)
    {
        // iterate over all cells and readjust cell data
        CellType* c = Root();
        if (!c)
        {
            return;
        }
        RootCellData(c->Cube(), c);
        std::list<CellType*> stack;
        stack.push_back(c);
        while (stack.size())
        {
            c = stack.back();
            stack.pop_back();
            if (!IsLeaf(c))
            {
                ReadjustChildrenData(c, 0, 0, c);
                for (unsigned int i = 0; i < CellType::NChildren; ++i)
                {
                    stack.push_back((*c)[i]);
                }
            }
        }
        StrategyBaseType::RefreshWithNewTreeData(bc);
    }
 
    template <class Strategies>
    void
    AACubeTree<Strategies>::ReadjustChildrenData(CellType* cell,
                                                 unsigned int axis,
                                                 unsigned int box,
                                                 CellType* data)
    {
        if (axis == Dim)
        {
            (*cell)[box]->Data(*data);
        }
        else
        {
            ScalarType s;
            cell->Cube().DividingPlane(axis, &s);
            CellType left, right;
            SplitAlongAxis(*data, axis, s, &left, &right); // implemented by TreeData
 
            ReadjustChildrenData(cell, axis + 1, box | (1 << axis), &left);
            ReadjustChildrenData(cell, axis + 1, box & (~(1 << axis)), &right);
        }
    }
 
    template <class Strategies>
    void
    AACubeTree<Strategies>::Subdivide(CellType* cell,
                                      unsigned int axis,
                                      unsigned int box,
                                      CellType* data)
    {
        if (axis == Dim)
        {
            CellType* child = new CellType;
            child->Data(*data);
            child->Parent(cell);
            child->Cube() = CubeType(box, cell->Cube());
            cell->Child(box, child);
        }
        else
        {
            ScalarType s;
            cell->Cube().DividingPlane(axis, &s);
            CellType left, right;
            SplitAlongAxis(*data, axis, s, &left, &right); // implemented by TreeData
 
            Subdivide(cell, axis + 1, box | (1 << axis), &left);
            Subdivide(cell, axis + 1, box & (~(1 << axis)), &right);
        }
    }
 
}; // namespace GfxTL