IteratorBVH.cc

Go to the documentation of this file.

#include <esg/iterator/IteratorBVH.h>
#include <esg/Statistics.h>

using namespace esg;

#ifdef ESG_STATISTICS
#define BVH_INC_TEST     { _bvTestsCounter++; }
#define BVH_INC_SUC_TEST { _bvTestsSucCounter++; }
#define BVH_UPDATE_STAT  { \
    ((Counter*)Statistics::instance()->get(Statistics::OID_BV_TESTS)->receptor())->add(_bvTestsCounter); \
    ((Counter*)Statistics::instance()->get(Statistics::OID_BV_TESTS_SUC)->receptor())->add(_bvTestsSucCounter); \
    _bvTestsCounter = (_bvTestsSucCounter = 0); \
}
#else
#define BVH_INC_TEST     {}
#define BVH_INC_SUC_TEST {}
#define BVH_UPDATE_STAT  {}
#endif // ESG_STATISTICS

#define BVH_BACKTRACK { \
    do { \
        pNode = _stack.back(); _stack.pop_back(); \
        BVH_INC_TEST; \
        pNode->bv->rayIntersection(&(_riAttr->iEnv), \
                                   ENV_WANT_INTERFERENCE|ENV_USE_CACHE, \
                                   _riAttr->origin, \
                                   _riAttr->direction, \
                                   _riAttr->distLimit); \
        if (!_riAttr->iEnv.mask & ENV_HAVE_INTERFERENCE) pNode = NULL; \
        else BVH_INC_SUC_TEST; \
    } while (!pNode && !_stack.empty()); \
}


SceneGraphObject* IteratorBVH::_first_ray_intersection(BVH::Node* pNode)
{
    /*
     * Initial preconditions for this non-recursive top-down traversal:
     *    _pLastUsedChild == NULL
     *    [_pBottomUpNode  == NULL]
     *    _stack.empty()  == true
     *
     * Output:
     *    succcessful leaf 
     *    _stack filled by unchecked branches
     */

    while (pNode) {
        if (pNode->leaf) { // we are in leaf in the first time
            _pLastUsedChild = pNode;
            return pNode->list->firstItem();
        }

        // we are in inner node
        BVH_INC_TEST;
        pNode->leftChild->bv->rayIntersection(&(_riAttr->iEnv),
                                              ENV_WANT_INTERFERENCE|ENV_USE_CACHE,
                                              _riAttr->origin,
                                              _riAttr->direction,
                                              _riAttr->distLimit);
        if (_riAttr->iEnv.mask & ENV_HAVE_INTERFERENCE) {
            BVH_INC_SUC_TEST;
            _stack.push_back(pNode->rightChild);
            pNode = pNode->leftChild;
            continue;
        }

        BVH_INC_TEST;
        pNode = pNode->rightChild;
        pNode->bv->rayIntersection(&(_riAttr->iEnv),
                                   ENV_WANT_INTERFERENCE|ENV_USE_CACHE,
                                   _riAttr->origin,
                                   _riAttr->direction,
                                   _riAttr->distLimit);
        if (_riAttr->iEnv.mask & ENV_HAVE_INTERFERENCE) {
            BVH_INC_SUC_TEST;
            continue;
        }

        if (_stack.empty()) return NULL;
        
        BVH_BACKTRACK;
    } // while (pNode)

    return NULL;
}

SceneGraphObject* IteratorBVH::_next_ray_intersection(void)
{
    /*
     * Initial preconditions:
     *    _pLastUsedChild != NULL
     *    _stack contain untraversed branches
     *    inspection of _pLastUsedChild is done
     */
    
    /*
     * Inspection of actual leaf is done here
     */
    BVH::Node * pNode;
    do {
        if (_stack.empty()) {
            /*
             * Stack is empty => actual sub-tree is inspected 
             */
            
            if (!_pBottomUpNode) return NULL; // Entire tree is inspected
            
            pNode = _pBottomUpNode; // Store branch for following inspection
            
            /*
             * Find and store upper colliding branch
             */
            while (true) {
                if (!_pBottomUpNode->parent||!_pBottomUpNode->parent->sibling){
                    _pBottomUpNode = NULL;
                    break;
                }

                BVH_INC_TEST;
                _pBottomUpNode = _pBottomUpNode->parent->sibling;
                _pBottomUpNode->bv->rayIntersection(&(_riAttr->iEnv),
                                                    ENV_WANT_INTERFERENCE|
                                                    ENV_USE_CACHE,
                                                    _riAttr->origin,
                                                    _riAttr->direction,
                                                    _riAttr->distLimit);
                if (_riAttr->iEnv.mask & ENV_HAVE_INTERFERENCE) {
                    BVH_INC_SUC_TEST;
                    break;
                }
            }
        } else {
            /*
             * Node in stack => traverse down this branch
             */
            BVH_BACKTRACK;
        }
        
        /*
         * Now we have branch for inspection in pNode and upper colliding
         * branch for future inspection in _pBottomUpNode (if exists)
         */
        
        while (pNode) {
            if (pNode->leaf) { // we are in leaf in the first time
                _pLastUsedChild = pNode;
                return pNode->list->firstItem();
            }

            BVH_INC_TEST;
            // we are in inner node
            pNode->leftChild->bv->rayIntersection(&(_riAttr->iEnv),
                                                  ENV_WANT_INTERFERENCE|ENV_USE_CACHE,
                                                  _riAttr->origin,
                                                  _riAttr->direction,
                                                  _riAttr->distLimit);
            if (_riAttr->iEnv.mask & ENV_HAVE_INTERFERENCE) {
                BVH_INC_SUC_TEST;
                _stack.push_back(pNode->rightChild);
                pNode = pNode->leftChild;
                continue;
            }

            BVH_INC_TEST;
            pNode = pNode->rightChild;
            pNode->bv->rayIntersection(&(_riAttr->iEnv),
                                       ENV_WANT_INTERFERENCE|ENV_USE_CACHE,
                                       _riAttr->origin,
                                       _riAttr->direction,
                                       _riAttr->distLimit);
            if (_riAttr->iEnv.mask & ENV_HAVE_INTERFERENCE) {
                BVH_INC_SUC_TEST;
                continue;
            }
            
            if (_stack.empty()) { pNode = NULL; continue; }

            BVH_BACKTRACK;
        } // while (pNode)
    } while (_pBottomUpNode);

    return NULL;
}

#undef BVH_BACKTRACK

SceneGraphObject* IteratorBVH::_halfspace_search(void)
{
    SceneGraphObject * pObj;
    BVH::Node        * pNode;
    Interval           interval;
    float              dist;

    if (_pLastUsedChild) {
        pObj = _pLastUsedChild->list->nextItem();
        if (pObj) return pObj;
    }

    while (!_stack.empty()) {
        pNode = _stack.back();
        _stack.pop_back();

        // is the actual node "interesting"?
        interval = pNode->bv->extent(_hsAttr->direction);
        dist     = _hsAttr->origin.dot(_hsAttr->direction);
        if (interval.max < dist) continue;

        if (pNode->leaf) { // first visit during this traverse
            _pLastUsedChild = pNode;
            return pNode->list->firstItem();
        }

        _stack.push_back(pNode->rightChild);
        _stack.push_back(pNode->leftChild);
    }

    return NULL;
}

SceneGraphObject* IteratorBVH::_area_search(void)
{
    SceneGraphObject * pObj;
    BVH::Node        * pNode;

    if (_pLastUsedChild) {
        pObj = _pLastUsedChild->list->nextItem();
        if (pObj) return pObj;
    }

    while (!_stack.empty()) {
        pNode = _stack.back();
        _stack.pop_back();

        // is the actual node "interesting"?
        if (pNode->bv->separation(*(_arAttr->area), NULL)) continue;

        if (pNode->leaf) { // first visit during this traverse
            _pLastUsedChild = pNode;
            return pNode->list->firstItem();
        }

        _stack.push_back(pNode->rightChild);
        _stack.push_back(pNode->leftChild);
    }
    
    return NULL;
}

SceneGraphObject* IteratorBVH::_children_search(void)
{
    // we are in leaf and we was there already in the past:
    if (_pLastUsedChild) {
        SceneGraphObject* pObject = _pLastUsedChild->list->nextItem();
        if (pObject) return pObject;
        _pLastUsedChild = _pLastUsedChild->rightChild;
    }
    else 
        _pLastUsedChild = ((BVH*)_pAggregate)->_leftLeaf;
  
    if (_pLastUsedChild) return _pLastUsedChild->list->firstItem();
    else return NULL;
}

SceneGraphObject* IteratorBVH::_first_child()
{
    while (!_stack.empty()) _stack.pop_back();
    
#ifdef ESG_STATISTICS
    SceneGraphObject * pRet;

    if (_traverse == RAY_INTERSECTION && _riAttr) {
        if (_riAttr->parentElement) {
            _pLastUsedChild = (BVH::Node*) _riAttr->parentElement;
            _pBottomUpNode = _pLastUsedChild->sibling;
            return _pLastUsedChild->list->firstItem();
        } else {
            _pLastUsedChild = NULL;
            _pBottomUpNode  = NULL;
            if (!(pRet = _first_ray_intersection(((BVH*)_pAggregate)->_root)))
                BVH_UPDATE_STAT;
            return pRet;
        }
    }
    
    _pLastUsedChild = NULL;
    _pBottomUpNode = NULL;

    if (!((BVH*)_pAggregate)->_root) return NULL;
  
    if (_traverse == HALF_SPACE && _hsAttr) {
        _stack.push_back(((BVH*)_pAggregate)->_root);
        if (!(pRet = _halfspace_search())) BVH_UPDATE_STAT;
        return pRet;
    }
    
    if (_traverse == AREA && _arAttr) {
        _stack.push_back(((BVH*)_pAggregate)->_root);
        if (!(pRet = _area_search())) BVH_UPDATE_STAT;
        return pRet;
    }
    
    if (_traverse == CHILDREN) {
        if (!(pRet = _children_search())) BVH_UPDATE_STAT;
        return pRet;
    }

#else
    if (_traverse == RAY_INTERSECTION && _riAttr) {
        if (_riAttr->parentElement) {
            _pLastUsedChild = (BVH::Node*) _riAttr->parentElement;
            _pBottomUpNode = _pLastUsedChild->sibling;
            return _pLastUsedChild->list->firstItem();
        } else {
            _pLastUsedChild = NULL;
            _pBottomUpNode  = NULL;
            return _first_ray_intersection(((BVH*)_pAggregate)->_root);
        }
    }

    _pLastUsedChild = NULL;
    _pBottomUpNode = NULL;

    if (!((BVH*)_pAggregate)->_root) return NULL;
  
    if (_traverse == HALF_SPACE && _hsAttr) {
        _stack.push_back(((BVH*)_pAggregate)->_root);
        return _halfspace_search();
    }
    
    if (_traverse == AREA && _arAttr) {
        _stack.push_back(((BVH*)_pAggregate)->_root);
        return _area_search();
    }
    
    if (_traverse == CHILDREN)
        return _children_search();
#endif // ESG_STATISTICS        

    return NULL;
}

SceneGraphObject* IteratorBVH::_next_child()
{
#ifdef ESG_STATISTICS
    SceneGraphObject* pRet;

    if (!_pLastUsedChild) { BVH_UPDATE_STAT; return NULL; }
  
    if (_traverse == RAY_INTERSECTION && _riAttr) {
        SceneGraphObject * pObj = _pLastUsedChild->list->nextItem();
        if (pObj) return pObj;
        else {
            if (!(pRet = _next_ray_intersection())) BVH_UPDATE_STAT;
            return pRet;
        }
    }
    
    if (_traverse == HALF_SPACE && _hsAttr) {
        if (!(pRet = _halfspace_search())) BVH_UPDATE_STAT;
        return pRet;
    }
  
    if (_traverse == AREA && _arAttr) {
        if (!(pRet = _area_search())) BVH_UPDATE_STAT;
        return pRet;
    }
  
    if (_traverse == CHILDREN) {
        if (!(pRet = _children_search())) BVH_UPDATE_STAT;
        return pRet;
    }

#else 
    if (!_pLastUsedChild) return NULL; 
    if (_traverse == RAY_INTERSECTION && _riAttr) {
        SceneGraphObject * pObj = _pLastUsedChild->list->nextItem();
        if (pObj) return pObj; else return _next_ray_intersection();
    }
    if (_traverse == HALF_SPACE && _hsAttr) return _halfspace_search();
    if (_traverse == AREA && _arAttr)       return _area_search();
    if (_traverse == CHILDREN)              return _children_search();
#endif // ESG_STATISTICS    

    return NULL;
}


//--------- public ---------

IteratorBVH::IteratorBVH(BVH* bvh)
    : IteratorSDS((SDS*) bvh)
{
    _pLastUsedChild = NULL;
#ifdef ESG_STATISTICS
    _bvTestsCounter = 0;
    _bvTestsSucCounter = 0;
#endif // ESG_STATISTICS
}

#if 0
Geometry* IteratorBVH::delimitBoundary(void) const
{
    if (!((BVH*)_pAggregate)->_root) return NULL;
    else return (Geometry*) ((BVH*)_pAggregate)->_root->bv->clone();
}
#endif



#ifdef ESG_STATISTICS
#undef BVH_INC_TEST    
#undef BVH_INC_SUC_TEST
#undef BVH_UPDATE_STAT
#endif // ESG_STATISTICS

---