TS/TS_Octree.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      David Wong
 *      Side Effects
 *      477 Richmond Street West
 *      Toronto, Ontario
 *      Canada   M5V 3E7
 *      416-504-9876
 *
 * NAME:        Octree (C++)
 *
 * COMMENTS:
 *
 */


#ifndef __TS_Octree_H__
#define __TS_Octree_H__

#include "TS_API.h"
#include <UT/UT_RefArray.h>
#include <UT/UT_BoundingBox.h>
#include "TS_Expression.h"
#include "TS_Primitive.h"

#define TS_OCTREE_INITIALIZED   1       // Normal octree intersect
#define TS_OCTREE_DOFAST        2       // For small octrees (1 deep)

//
//  Here's the class for a voxel.  Each voxel contains a list of primitives
//      as well as a bounding box and a split direction.  Each voxel can
//      be split into two children (creating a binary tree).
//
class TS_API TS_OctreeVoxel {
public:
    TS_OctreeVoxel();
   ~TS_OctreeVoxel();

    TS_OctreeVoxel              *myKids[2];     // Left and right
    TS_ExpressionList            myList;        // List of objects in this voxel
    unsigned                     myAxis;        // My split direction (axis)
    float                        myAvg;         // The split distance
    UT_BoundingBox               myBBox;        // Bounding box

    float                xmin() const { return myBBox(0, 0); }
    float                xmax() const { return myBBox(0, 1); }
    float                ymin() const { return myBBox(1, 0); }
    float                ymax() const { return myBBox(1, 1); }
    float                zmin() const { return myBBox(2, 0); }
    float                zmax() const { return myBBox(2, 1); }
    TS_OctreeVoxel      *left() { return myKids[0]; }
    TS_OctreeVoxel      *right() { return myKids[1]; }

    void                 addThing(TS_MetaPrimitive *object);

    void                 subdivide(const TS_ExpressionList &nodes,
                                    unsigned maxEntries, unsigned level);
private:
    void                 bestSplit(unsigned maxEntries, 
                                   const TS_ExpressionList &nodes);
    void                 getKids(TS_ExpressionList &kids,
                                 const TS_ExpressionList &nodes,
                                 int left = 1);
};

//
//  This class is used in octree traversal.  This maintains a stack
//      of where we are in the octree...
//
class TS_API TS_OctreeStack {
public:
    TS_OctreeVoxel      *myVoxel;
    float                myMin, myMax;

    TS_OctreeStack      &operator=(const TS_OctreeStack &d)
                         {
                            myVoxel = d.myVoxel;
                            myMin = d.myMin;
                            myMax = d.myMax;
                            return *this;
                         }
    unsigned             operator==(const TS_OctreeStack &) const
                         {
                            return 0;
                         }
};

//
//  Here is the real octree class.
//
class TS_API TS_Octree {
public:
             TS_Octree();
             TS_Octree(const TS_MetaExpression *e);
    virtual ~TS_Octree();

    void                 setSweepList(const TS_Ray &ray, TS_SweepList &sweep,
                                        fpreal tmin=0, fpreal tmax=1e20);
    TS_OctreeVoxel      *findVoxel(const UT_Vector3 &P) const;

protected:
    virtual int          buildMe();     // Other people may have to do things

    TS_OctreeVoxel      *myHead;        // My BSP tree
    unsigned             myMaxLevel;

private:
    UT_RefArray<TS_OctreeStack>          myStack;       // used for intersect
    const TS_MetaExpression             *myOwner;
    unsigned                             myStackPtr;
};

#endif

---