osg::ParticleBSPTree Class Reference

Particle BSP Tree. More...

#include <OSGParticleBSP.h>

List of all members.

Public Member Functions
Constructors
	ParticleBSPTree (void)
Destructors
virtual	~ParticleBSPTree (void)
Creation / Deletion
bool	created (void)
void	build (Particles *core)
void	destroy (void)
Traversal
Int32 *	traverse (const Pnt3f &refPoint, UInt32 &length, Int32 *order=NULL) const
Int32 *	traverse (const Vec3f &refVec, UInt32 &length, Int32 *order=NULL) const
Input / Output
virtual void	dump (UInt32 uiIndent=0, const BitVector bvFlags=0) const
void	putToString (std::string &outVal) const
bool	getFromString (const Char8 *&inVal)
UInt32	getBinSize (void) const
void	copyToBin (BinaryDataHandler &pMem) const
void	copyFromBin (BinaryDataHandler &pMem)
Protected Member Functions
Node Traversal
UInt32	doTraverse (const Pnt3f &refPoint, UInt32 index, UInt32 length, Int32 *order) const
UInt32	doTraverse (const Vec3f &refVec, UInt32 index, UInt32 length, Int32 *order) const
Creation Tools
UInt32	doBuild (std::vector< Int32 >::iterator begin, std::vector< Int32 >::iterator end, UInt32 nodeindex, GeoPositionsPtr pos)
Private Attributes
std::vector< ParticleBSPNode >	_tree

---

Detailed Description

A very simple BSP tree, optimized for particle sorting.

Definition at line 130 of file OSGParticleBSP.h.

---

Constructor & Destructor Documentation

ParticleBSPTree::ParticleBSPTree

(

void

)

Definition at line 127 of file OSGParticleBSP.cpp.

{
}

ParticleBSPTree::~ParticleBSPTree

(

void

)

[virtual]

Definition at line 131 of file OSGParticleBSP.cpp.

{
} 

---

Member Function Documentation

bool osg::ParticleBSPTree::created

(

void

)

[inline]

Definition at line 87 of file OSGParticleBSP.inl.

References _tree.

{
    return _tree.size() > 1;
}

void ParticleBSPTree::build

(

Particles *

core

)

Definition at line 362 of file OSGParticleBSP.cpp.

References _tree, doBuild(), FWARNING, osg::ParticlesBase::getMFIndices(), osg::ParticlesBase::getPositions(), osg::NullFC, osg::osgnextpower2(), osg::MField< FieldTypeT, fieldNameSpace >::reserve(), and osg::MField< FieldTypeT, fieldNameSpace >::size().

Referenced by osg::Particles::drawPrimitives().

{
    _tree.clear();
    
    if(core == NULL)
    {
        FWARNING(("ParticleBSP::build: no core!!\n"));
        return;
    }
    
    const GeoPositionsPtr pos = core->getPositions();
    
    if(pos == NullFC)
        return;

    const MFInt32 *indices = core->getMFIndices();
        
    // 1. create list for particles
 
    std::vector<Int32> order;
    order.reserve(pos->getSize());
    
    for(UInt32 i = 0; i < pos->getSize(); ++i )
    {     
        if(indices->size() == pos->getSize())
        {        
            order.push_back((*indices)[i]);
        }
        else
        {
            order.push_back(i);            
        }
    }
    
    // reserve mem for tree
    
    _tree.resize(osgnextpower2(order.size()) * 2);
    
    // 2. recursively build the tree
    
    UInt32 nnodes = doBuild(order.begin(), order.end(), 1, pos);
    
    // 3. remove the unneeded elements from the end
    
    if(nnodes < _tree.size())
        _tree.erase( _tree.begin() + nnodes, _tree.end());

    // done
}

void ParticleBSPTree::destroy

(

void

)

Definition at line 495 of file OSGParticleBSP.cpp.

References _tree.

Referenced by osg::Particles::changed().

{
    _tree.clear();
}

Int32 * ParticleBSPTree::traverse	(	const Pnt3f &	refPoint,
		UInt32 &	length,
		Int32 *	order = NULL
	)			const

Definition at line 279 of file OSGParticleBSP.cpp.

References _tree, and doTraverse().

Referenced by osg::Particles::drawPrimitives().

{
    if(_tree.empty())
        return NULL;
        
    if(order == NULL)
    {
        order = new Int32 [length];
    }
    
    length = doTraverse(refPoint,1,0,order);
    
    return order;
}

Int32 * ParticleBSPTree::traverse	(	const Vec3f &	refVec,
		UInt32 &	length,
		Int32 *	order = NULL
	)			const

Definition at line 321 of file OSGParticleBSP.cpp.

References doTraverse().

{
    if(order == NULL)
    {
        order = new Int32 [length];
    }
    
    length = doTraverse(refVec,1,0,order);
    
    return order;
}

void ParticleBSPTree::dump	(	UInt32	uiIndent = 0,
		const BitVector	bvFlags = 0
	)			const [virtual]

Definition at line 137 of file OSGParticleBSP.cpp.

References _tree, and PLOG.

{
    PLOG << "ParticleBSPTree(";

    if(!_tree.empty())
    {
        for(std::vector<ParticleBSPNode>::const_iterator i = _tree.begin() + 1;
            i != _tree.end(); ++i )
        {
            i->dump();
        }
    }   
    
    PLOG << ")" << std::endl;
}

void ParticleBSPTree::putToString

(

std::string &

outVal

)

const

Definition at line 154 of file OSGParticleBSP.cpp.

References _tree.

Referenced by osg::osg::FieldDataTraits< ParticleBSPTree >::putToString().

{
    outVal.assign(TypeTraits<UInt32>::putToString(_tree.size()));
    outVal.append(";");
    
    if(! _tree.empty())
    {
        for(std::vector<ParticleBSPNode>::const_iterator i = _tree.begin() + 1;
            i != _tree.end(); ++i )
        {
            outVal.append(TypeTraits<UInt8>::putToString(i->getAxis()));
            outVal.append(":");
            if(i->isLeaf())
            {
                outVal.append(TypeTraits<Int32>::putToString(i->getValue()));
            }
            else
            {
                outVal.append(TypeTraits<Real32>::putToString(
                    i->getSplitValue()));
            }
            outVal.append(";");
        }   
    }
}

bool ParticleBSPTree::getFromString

(

const Char8 *&

inVal

)

Definition at line 180 of file OSGParticleBSP.cpp.

References _tree, and osg::ParticleBSPNode::Leaf.

Referenced by osg::osg::FieldDataTraits< ParticleBSPTree >::getFromString().

{
    UInt32 size = TypeTraits<UInt32>::getFromString(inVal);
 
    const Char8 *c = strchr(inVal, ';');
    
    if(!c)
        return false;
    c++;
    
    _tree.resize(size);
    
    for(UInt32 i = 1; i < size; ++i)
    {
        UInt8 axis = TypeTraits<UInt8>::getFromString(c);
        c = strchr(c, ':');
        if(!c)
            return false;
        c++;
        
        if(axis == ParticleBSPNode::Leaf)
        {
            Int32 value = TypeTraits<Int32>::getFromString(c);
            _tree[i].setValue(value);
        }
        else
        {
            Real32 value = TypeTraits<Real32>::getFromString(c);
            _tree[i].setSplit(axis, value);           
        }
        c = strchr(c, ';');
        if(!c)
            return false;
        c++;
    }
    
    return true;
}

UInt32 ParticleBSPTree::getBinSize

(

void

)

const

Definition at line 219 of file OSGParticleBSP.cpp.

References _tree.

Referenced by osg::osg::FieldDataTraits< ParticleBSPTree >::getBinSize().

{
    return sizeof(UInt32) // num elements
        + (sizeof(UInt8)+sizeof(UInt32)) * _tree.size();
}

void ParticleBSPTree::copyToBin

(

BinaryDataHandler &

pMem

)

const

Definition at line 225 of file OSGParticleBSP.cpp.

References _tree, osg::ParticleBSPNode::Leaf, and osg::BinaryDataHandler::putValue().

Referenced by osg::osg::FieldDataTraits< ParticleBSPTree >::copyToBin().

{
    UInt8  axis;
    Int32  value;
    Real32 splitvalue;
    UInt32 i;
    UInt32 size = _tree.size();
    pMem.putValue(size);

    for(i=0;i<size;++i)
    {
        axis=_tree[i].getAxis();
        pMem.putValue(axis);
        if(axis==ParticleBSPNode::Leaf)
        {
            value=_tree[i].getValue();
            pMem.putValue(value);
        }
        else
        {
            splitvalue=_tree[i].getSplitValue();
            pMem.putValue(splitvalue);
        }
    }
}

void ParticleBSPTree::copyFromBin

(

BinaryDataHandler &

pMem

)

Definition at line 251 of file OSGParticleBSP.cpp.

References _tree, osg::BinaryDataHandler::getValue(), and osg::ParticleBSPNode::Leaf.

Referenced by osg::osg::FieldDataTraits< ParticleBSPTree >::copyFromBin().

{
    UInt8  axis;
    Int32  value;
    Real32 splitvalue;
    UInt32 i;
    UInt32 size;
    pMem.getValue(size);
    _tree.resize(size);

    for(i=0;i<size;++i)
    {
        pMem.getValue(axis);
        if(axis==ParticleBSPNode::Leaf)
        {
            pMem.getValue(value);
            _tree[i].setValue(value);
        }
        else
        {
            pMem.getValue(splitvalue);
            _tree[i].setSplit(axis, Real32(value));
        }
    }
}

UInt32 ParticleBSPTree::doTraverse	(	const Pnt3f &	refPoint,
		UInt32	index,
		UInt32	length,
		Int32 *	order
	)			const [protected]

Definition at line 295 of file OSGParticleBSP.cpp.

References _tree, osg::ParticleBSPNode::getAxis(), osg::ParticleBSPNode::getSplitValue(), osg::ParticleBSPNode::getValue(), and osg::ParticleBSPNode::isLeaf().

Referenced by doTraverse(), and traverse().

{
    const ParticleBSPNode *n = &_tree[index];
    
    if(n->isLeaf())
    {
        order[length] = n->getValue();
        return ++length;
    }
    else
    {
        if(refPoint[n->getAxis()] > n->getSplitValue())
        {
            length = doTraverse(refPoint, index * 2    , length, order);
            length = doTraverse(refPoint, index * 2 + 1, length, order);
        }
        else
        {
            length = doTraverse(refPoint, index * 2 + 1, length, order);
            length = doTraverse(refPoint, index * 2    , length, order);
        }
    }
    return length;
}

UInt32 ParticleBSPTree::doTraverse	(	const Vec3f &	refVec,
		UInt32	index,
		UInt32	length,
		Int32 *	order
	)			const [protected]

Definition at line 334 of file OSGParticleBSP.cpp.

References _tree, doTraverse(), osg::ParticleBSPNode::getAxis(), osg::ParticleBSPNode::getValue(), and osg::ParticleBSPNode::isLeaf().

{
    const ParticleBSPNode *n = &_tree[index];
    
    if(n->isLeaf())
    {
        order[length] = n->getValue();
        return ++length;
    }
    else
    {
        if(refVec[n->getAxis()] > 0.f)
        {
            length = doTraverse(refVec, index * 2    , length, order);
            length = doTraverse(refVec, index * 2 + 1, length, order);
        }
        else
        {
            length = doTraverse(refVec, index * 2 + 1, length, order);
            length = doTraverse(refVec, index * 2    , length, order);
        }
    }
    return length;
}

UInt32 ParticleBSPTree::doBuild	(	std::vector< Int32 >::iterator	begin,
		std::vector< Int32 >::iterator	end,
		UInt32	nodeindex,
		GeoPositionsPtr	pos
	)			[protected]

Definition at line 433 of file OSGParticleBSP.cpp.

References _tree, osg::BoxVolume::extendBy(), osg::BoxVolume::getMax(), osg::BoxVolume::getMin(), osg::osgMax(), p, osg::Volume::setEmpty(), osg::ParticleBSPNode::X, osg::ParticleBSPNode::Y, and osg::ParticleBSPNode::Z.

Referenced by build().

{
    // reached a leaf?
    
    if(begin + 1 == end)
    {
        _tree[nodeindex].setValue(*begin);
        return nodeindex + 1;
    }
    
    // find the bounding volume of the group
    
    BoxVolume b;
    Pnt3f p;
    
    b.setEmpty();
    
    for(std::vector<Int32>::iterator i = begin; i != end; ++i)
    {
        pos->getValue(p,*i);     
        b.extendBy(p);
    }
    
    // find the axis with the longest extension
    
    Vec3f d = b.getMax() - b.getMin();
    
    UInt8 axis = ParticleBSPNode::X;
    Real32 maxval = d[0];
    
    if(d[1] > maxval)
    {
        axis = ParticleBSPNode::Y;
        maxval = d[1];
    }
    if(d[2] > maxval)
    {
        axis = ParticleBSPNode::Z;
        maxval = d[2];
    }

    // sort in that axis
    ParticleCompare comp(pos, axis);
    
    std::sort(begin,end,comp);
    
    // find median value
    std::vector<Int32>::iterator mid = begin + (end - begin) / 2;
    
    Pnt3f p2;
    pos->getValue(p ,*mid);
    pos->getValue(p2,(*mid)-1);
    _tree[nodeindex].setSplit(axis, (p[axis] + p2[axis]) / 2.f);
    
    return osgMax( doBuild(begin, mid, nodeindex * 2    , pos),
                   doBuild(  mid, end, nodeindex * 2 + 1, pos) );   
}   

---

Member Data Documentation

std::vector<ParticleBSPNode> osg::ParticleBSPTree::_tree [private]

Definition at line 217 of file OSGParticleBSP.h.

Referenced by build(), copyFromBin(), copyToBin(), created(), destroy(), doBuild(), doTraverse(), dump(), getBinSize(), getFromString(), putToString(), and traverse().

---

The documentation for this class was generated from the following files:

• OSGParticleBSP.h
• OSGParticleBSP.cpp
• OSGParticleBSP.inl