BVList.cc

Go to the documentation of this file.

#include <esg/geometry/BVList.h>
#include <esg/explorer/POGExplorer.h>
#include <esg/explorer/NExtentsExplorer.h>
#include <time.h>
#include <assert.h>

using namespace esg;

unsigned BVList::qsortIndex;

int BVList::qsortCompare(const void * pBV1, const void * pBV2)
{
    Interval * i1 = &((*((BVNode**)pBV1))->extents[BVList::qsortIndex]);
    Interval * i2 = &((*((BVNode**)pBV2))->extents[BVList::qsortIndex]);
    double     e1 = i1->min + i1->max;
    double     e2 = i2->min + i2->max;

    return ((e1 < e2) ? -1 : ((e1 == e2) ? 0 : 1));
}

void BVList::_split_by_handles(List<BVNode>& srcList,
                               List<BVNode>& dstList,
                               unsigned      index)
{
    float    median;
    unsigned i_rand;
    long int length  = (long int) srcList.length();
    BVNode*  pMedian = NULL;

    assert(length > 1);
    
    // find i-th element in list, i_rand = rand()%length = [0,length)
    //i_rand = (unsigned) (rand() % length);
    i_rand = (unsigned) ESG_INT_RAND(length);
    pMedian = srcList.iThItem(i_rand, false);
    assert(pMedian);
    (void) srcList.remove(pMedian);
    length--;

    median = pMedian->handle[index];

    BVNode * pNode = srcList.firstItem();
    for (register unsigned i = 0; i < (unsigned) length; i++) {
        //fprintf(stderr,"%u %u\n",i,length);
        
        if ((pNode->handle[index] < median) ||
            ((pNode->handle[index] == median) && (i < i_rand)))
        {
            // keep object in this (left) list
            pNode = srcList.nextItem();
        } else
        {                       /* move object to right son list */
            BVNode* pTmp = srcList.nextItem();
            dstList.append(srcList.remove(pNode));
            pNode = pTmp;
        }
    }   /* for */

    if (dstList.length() == 0) dstList.append(pMedian);
    else srcList.append(pMedian);
}

void BVList::_comp_handle(BVNode* pNode)
{
    if (!pNode || !pNode->pObject) return;
    
    POGExplorer explorer;
    explorer.explore(*(pNode->pObject));
    Vector3 pog = explorer.result();
    Vector3 v;
    
    if (pog.x == MAX_VEC_VALUE ||
        pog.y == MAX_VEC_VALUE ||
        pog.z == MAX_VEC_VALUE)
    {
        for (register unsigned i = 0; i < _dirs; i++)
            pNode->handle[i] = MAXFLOAT;
        return;
    }
    
    for (register unsigned i = 0; i < _dirs; i++) {
        v.set(_dirMat[i][0], _dirMat[i][1], _dirMat[i][2]);
        pNode->handle[i] = pog.dot(v);
    }
}

void BVList::_comp_extents(BVNode* pNode)
{
    if (!pNode || !pNode->pObject) return;
    
    NExtentsExplorer explorer(_dirMat, _dirs);
    explorer.explore(*(pNode->pObject));

    for (unsigned i = 0; i < _dirs; i++) 
        pNode->extents[i] = explorer.result(i);
}


unsigned BVList::_index_with_max_extent()
{
#ifdef WIN32
    Interval *d = new Interval [_dirs];
#else
    Interval d[_dirs];
#endif
    BVNode*  pNode = _pList->firstItem();
    
    while (pNode) {
        for (unsigned i = 0; i < _dirs; i++) {
            if (pNode->extents[i].min < d[i].min)
                d[i].min = pNode->extents[i].min;
            if (pNode->extents[i].max > d[i].max)
                d[i].max = pNode->extents[i].max;
        }
        pNode = _pList->nextItem();
    }

    unsigned ret  = 0;
    double   dist = -MAXDOUBLE;
    double   actDist;
    for (unsigned i = 0; i < _dirs; i++) {
        actDist = d[i].max - d[i].min;
        if (actDist > dist) { ret = i; dist = actDist; }
    }

#ifdef WIN32
    delete [] d;
#endif
    
    return ret;
}

void BVList::_build_area_table(BVNode** nodes, long a, long b, double *areas) const
{
    long      imin, dir;
    double    tmin, tmax;
    Vector3   bmin(MAX_VEC_VALUE, MAX_VEC_VALUE, MAX_VEC_VALUE);
    Vector3   bmax(MIN_VEC_VALUE, MIN_VEC_VALUE, MIN_VEC_VALUE);
    Vector3   len;
    Interval* e;

    if (a < b) { imin = a; dir =  1; }
    else       { imin = b; dir = -1; }

    for (long i = a; i != (b + dir); i += dir) {
        e = nodes[i]->extents;

        tmin = e[0].min;
        tmax = e[0].max;
        if (tmin < bmin.x) { bmin.x = tmin; }
        if (tmax > bmax.x) { bmax.x = tmax; }

        tmin = e[1].min;
        tmax = e[1].max;
        if (tmin < bmin.y) { bmin.y = tmin; }
        if (tmax > bmax.y) { bmax.y = tmax; }

        tmin = e[2].min;
        tmax = e[2].max;
        if (tmin < bmin.z) { bmin.z = tmin; }
        if (tmax > bmax.z) { bmax.z = tmax; }

        len.set(bmax);
        len.sub(bmin);

        areas[i - imin] = len.x * (len.y + len.z) + len.y * len.z;
    }
}

unsigned BVList::_split_by_extent(List<BVNode>& list)
{
    unsigned      i, size;
    BVNode**      qsortArray = NULL;
    double        bestIndex, newIndex;
    unsigned      bestLoc;
    double*       leftArea;
    double*       rightArea;

    size       = length();
    qsortIndex = _index_with_max_extent();
    qsortArray = new BVNode* [size];
    leftArea   = new double [size];
    rightArea  = new double [size];
    i          = 0;
    
    for (BVNode * pN = _pList->firstItem(); pN; pN = _pList->nextItem())
        qsortArray[i++] = pN;
    
    delete _pList;
    qsort((void*)qsortArray, size, sizeof(BVNode*), BVList::qsortCompare);

    _build_area_table(qsortArray, 0, size-1, leftArea);
    _build_area_table(qsortArray, size-1, 0, rightArea);
    
    bestIndex = rightArea[0] * (size - 3.);
    bestLoc   = 0;
    
    /*
     * Find the most effective point to split. The best location will be
     * the one that minimizes the function N1*A1 + N2*A2 where N1 and N2
     * are the number of objects in the two groups and A1 and A2 are the
     * surface areas of the bounding boxes of the two groups.
     */
    for (i = 0; i < size - 1; i++) {
        newIndex = (i+1) * leftArea[i] + (size-1-i) * rightArea[i+1];
        if (newIndex < bestIndex) {
            bestIndex = newIndex;
            bestLoc = i;
        }
    }
    
    delete [] leftArea;
    delete [] rightArea;

    _pList = new List<BVNode>;
    for (i = 0; i < bestLoc + 1; i++) _pList->append(qsortArray[i]);
    for (i = bestLoc + 1; i < size; i++) list.append(qsortArray[i]);

    delete [] qsortArray;

    return qsortIndex;
}

unsigned BVList::_index_with_max_variation()
{
    float     max_hodn;
    unsigned  max_variace = MAXUNSIGNED;
    float     hndl;
    double    ekohandle2, e2kohandle;

#if defined(_MSC_VER)
    float    *variace = new float [_dirs];
#else
    float     variace [_dirs];
#endif

    variace[0] = 0;

    if (length() > 1) {
        for (register unsigned i = 0; i < _dirs; i++) {
            BVNode* pNode = _pList->firstItem();
            ekohandle2 = 0;
            e2kohandle = 0;
            while (pNode) {
                hndl = pNode->handle[i];
                ekohandle2 += (hndl * hndl);
                e2kohandle += hndl;
                pNode = _pList->nextItem();
            }
            ekohandle2 /= length();
            e2kohandle /= length();
            e2kohandle *= e2kohandle;
            variace[i]  = ekohandle2 - e2kohandle;
        }
        max_variace = 0;
        max_hodn = variace[0];
        for (register unsigned i = 1; i < _dirs; i++) {
            if (max_hodn < variace[i]) {
                max_hodn = variace[i];
                max_variace = i;
            }
        }
    }

#if defined(_MSC_VER)
    delete [] variace;
#endif
        
    return max_variace;
}

unsigned BVList::_split_by_variation(List<BVNode>& list)
{
    if (length() < 2) return MAXUNSIGNED;

    unsigned      index, ll;
    unsigned      LL_room, RR_room;
    //time_t        t;
    List<BVNode>* rightList = new List<BVNode>;
    List<BVNode>* leftList  = _pList;
    
    LL_room = length() / 2;
    RR_room = length() - LL_room;
    
    if ((index = _index_with_max_variation()) == MAXUNSIGNED) return index;

    _pList = new List<BVNode>();

    //srand((unsigned)time(&t));

#if 1
    while (true) { // rightList is always empty at this point
        if (leftList->length() > 1)
            _split_by_handles(*leftList, *rightList, index);
        if ((ll = leftList->length()) < LL_room) { // right list is too large
            LL_room -= ll;
            _pList->append(*leftList);
            List<BVNode>* pTmp = leftList;
            leftList = rightList;
            rightList = pTmp;;
        } else {
            if (ll == LL_room){ // we are done
                _pList->append(*leftList);
                list.append(*rightList);
                break;
            } else { // left list is too large
                RR_room -= rightList->length();
                list.append(*rightList);
            }
        }
    }
#endif
    
#if 0
    while (leftList->length()) {  // rightList is always empty at this moment
        if (leftList->length() > LL_room) 
            _split_by_handles(*leftList, *rightList, index);
            
        if (rightList->length() == 0) {
            for (unsigned i = 0; i < LL_room; i++)
                _pList->append(leftList->remove(leftList->firstItem()));
            while (leftList->length())
                list.append(leftList->remove(leftList->firstItem()));
            //list.append(*leftList);
            continue;
        }

        if (leftList->length() == 0) {
            for (unsigned i = 0; i < RR_room; i++)
                list.append(rightList->remove(rightList->firstItem()));
            while (rightList->length())
                _pList->append(rightList->remove(rightList->firstItem()));
            //_pList->append(*rightList);
            continue;
        }

        if (rightList->length() <= RR_room) {
            RR_room -= rightList->length();
            while (rightList->length())
            list.append(rightList->remove(rightList->firstItem()));
            //list.append(*rightList);
        }

        if (leftList->length() <= LL_room) {
            LL_room -= leftList->length();
            while (leftList->length())
            _pList->append(leftList->remove(leftList->firstItem()));
            //_pList->append(*leftList);
            List<BVNode>* pTmp = leftList;
            leftList = rightList;
            rightList = pTmp;;
        }
    }
#endif
    
    delete leftList;
    delete rightList;

    return index;
}


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

BVList::BVList(unsigned s, const float (*m)[3])
    : _dirs(s), _dirMat(m)
{
    _pList = new List<BVNode>();
}

BVList::~BVList()
{
    while (BVNode* pNode=_pList->remove(_pList->firstItem())) { delete pNode; }
    delete _pList;
}

void BVList::append(SceneGraphObject* o)
{
    BVNode* pnode = new BVNode(_dirs, o);
    _comp_handle(pnode);
    _comp_extents(pnode);
    _pList->append(pnode);
}

SceneGraphObject* BVList::remove(SceneGraphObject* pObj)
{
    if (!pObj) return NULL;
    BVNode* pItem = _pList->firstItem();
    
    while (pItem && pItem->pObject != pObj)
        pItem = _pList->nextItem();
    
    if (pItem && pItem->pObject == pObj) {
        SceneGraphObject* pRet =  pItem->pObject;
        _pList->remove(pItem);
        return pRet;
    } else
        return NULL;
}

unsigned BVList::split(BVList& list, SplitStrategy splitStrategy)
{
    if (length() < 2) return MAXUNSIGNED;

    switch (splitStrategy) {
    case SPLIT_BY_MAX_VARIATION:
        return _split_by_variation(*(list._pList));
        break;
    case SPLIT_BY_MAX_EXTENT:
        return _split_by_extent(*(list._pList));
        break;
    default:
        return MAXUNSIGNED;
    }
}

---