// COTD Entry submitted by Paul Nettle [midnight@FluidStudios.com]
// Corresponds with an Ask MidNight response (http://www.flipcode.com/askmid/)

// -----------------------------------------------------------------------------
// This defines a callback for traversal
// -----------------------------------------------------------------------------

class   Octree;
typedef bool            (*callback)(const Octree &o, void *data);

// -----------------------------------------------------------------------------
// This defines a point class (it's incomplete, but the data elements are there)
// -----------------------------------------------------------------------------

class   Point
{
public:

        double          x, y, z;        // Position
        double          n;              // User's unique identifier
        unsigned int    code;           // Used during octree generation

        // Insert typical operators, such as *, +, -, etc.
};

// -----------------------------------------------------------------------------
// This defines a cubic bounding volume (center, radius)
// -----------------------------------------------------------------------------

typedef struct
{
        Point           center;         // Center of a cubic bounding volume
        double          radius;         // Radius of a cubic bounding volume
} Bounds;

// -----------------------------------------------------------------------------
// The octree class -- almost real code!
// -----------------------------------------------------------------------------

class   Octree
{
public:
        // Construction/Destruction

                                Octree();
virtual                         ~Octree();

        // Accessors

inline  const   Point * const * points() const {return _points;}
inline  const   unsigned int    pointCount() const {return _pointCount;}

        // Implementation

virtual const   bool            build(Point **points,
                                      const unsigned int count,
                                      const unsigned int threshold,
                                      const unsigned int maximumDepth,
                                      const Bounds &bounds,
                                      const unsigned int currentDepth = 0);
static  const   Bounds          calcCubicBounds(const Point * const * points,
                                                const unsigned int count);
virtual const   bool            traverse(callback proc, void *data) const;

protected:
        Octree                  *_child[8];
        unsigned int            _pointCount;
        Point                   **_points;
        Point                   _center;
        double                  _radius;
};

// -----------------------------------------------------------------------------
// Construction -- Just "nullify" the class
// -----------------------------------------------------------------------------

        Octree::Octree()
        : _pointCount(0), _points(NULL), _center(0,0,0,0), _radius(0.0)
{
        memset(_child, 0, sizeof(_child));
}

// -----------------------------------------------------------------------------
// Destruction -- free up memory
// -----------------------------------------------------------------------------

        Octree::~Octree()
{
        delete[] _points;
}

// -----------------------------------------------------------------------------
// Build the octree
// -----------------------------------------------------------------------------

const   bool    Octree::build(Point **points,
                              const unsigned int count,
                              const unsigned int threshold,
                              const unsigned int maximumDepth,
                              const Bounds &bounds,
                              const unsigned int currentDepth)
{
        // You know you're a leaf when...
        //
        // 1. The number of points is <= the threshold
        // 2. We've recursed too deep into the tree
        //    (currentDepth >= maximumDepth)
        //
        //    NOTE: We specifically use ">=" for the depth comparison so that we
        //          can set the maximumDepth depth to 0 if we want a tree with
        //          no depth.

        if (count <= threshold || currentDepth >= maximumDepth)
        {
                // Just store the points in the node, making it a leaf

                _pointCount = count;
                _points = new Point *[count];
                memcpy(_points, points, sizeof(Point *) * count);
                return true;
        }

        // We'll need this (see comment further down in this source)

        unsigned int    childPointCounts[8];

        // Classify each point to a child node

        for (unsigned int i = 0; i < count; i++)
        {
                // Current point

                Point   &p = *points[i];

                // Center of this node

                const Point &c = bounds.center;

                // Here, we need to know which child each point belongs to. To
                // do this, we build an index into the _child[] array using the
                // relative position of the point to the center of the current
                // node

                p.code = 0;
                if (p.x > c.x) p.code |= 1;
                if (p.y > c.y) p.code |= 2;
                if (p.z > c.z) p.code |= 4;

                // We'll need to keep track of how many points get stuck in each
                // child so we'll just keep track of it here, since we have the
                // information handy.

                childPointCounts[p.code]++;
        }

        // Recursively call build() for each of the 8 children

        for (i = 0; i < 8; i++)
        {
                // Don't bother going any further if there aren't any points for
                // this child

                if (!childPointCounts[i]) continue;

                // Allocate the child

                _child[i] = new Octree;

                // Allocate a list of points that were coded JUST for this child
                // only

                Point   **newList = new Point *[childPointCounts[i]];

                // Go through the input list of points and copy over the points
                // that were coded for this child

                Point   **ptr = newList;

                for (unsigned int j = 0; j < count; j++)
                {
                        if (points[j]->code == i)
                        {
                                *ptr = points[j];
                                ptr++;
                        }
                }

                // At this point, we have a list of points that will belong to
                // this child node. We'll want to remove any point with a
                // duplicate 'n' in them...
                //
                // [We won't need to reallocate the list, since it's temporary]

                int     newCount = 0;
                for (j = 0; j < childPointCounts[i]; j++)
                {
                        // Remove duplicates from newList
                        // ...
                        // Keep track of the new count in 'newCount'
                }

                // Generate a new bounding volume -- We do this with a touch of
                // trickery...
                //
                // We use a table of offsets. These offsets determine where a
                // node is, relative to it's parent. So, for example, if want to
                // generate the bottom-left-rear (-x, -y, -z) child for a node,
                // we use (-1, -1, -1).
                // 
                // However, since the radius of a child is always half of its
                // parent's, we use a table of 0.5, rather than 1.0.
                // 
                // These values are stored the following table. Note that this
                // won't compile because it assumes Points are structs, but you
                // get the idea.

                Point   boundsOffsetTable[8] =
                {
                        {-0.5, -0.5, -0.5},
                        {+0.5, -0.5, -0.5},
                        {-0.5, +0.5, -0.5},
                        {+0.5, +0.5, -0.5},
                        {-0.5, -0.5, +0.5},
                        {+0.5, -0.5, +0.5},
                        {-0.5, +0.5, +0.5},
                        {+0.5, +0.5, +0.5}
                };

                // Calculate our offset from the center of the parent's node to
                // the center of the child's node

                Point   offset = boundsOffsetTable[i] * bounds.radius;

                // Create a new Bounds, with the center offset and half the
                // radius

                Bounds  newBounds;
                newBounds.radius = bounds.radius * 0.5;
                newBounds.center = bounds.center + offset;

                // Recurse

                _child[i]->build(newList, newCount, threshold, maximumDepth,
                                newBounds, currentDepth+1);

                // Clean up

                delete[] newList;
        }

        return true;
}

// -----------------------------------------------------------------------------
// Determine the [cubic] bounding volume for a set of points
// -----------------------------------------------------------------------------

const Bounds Octree::calcCubicBounds(const Point * const * points,
                                     const unsigned int count)
{
        // What we'll give to the caller

        Bounds  b;

        // Determine min/max of the given set of points

        Point   min = *points[0];
        Point   max = *points[0];

        for (unsigned int i = 1; i < count; i++)
        {
                const Point &p = *points[i];
                if (p.x < min.x) min.x = p.x;
                if (p.y < min.y) min.y = p.y;
                if (p.z < min.z) min.z = p.z;
                if (p.x > max.x) max.x = p.x;
                if (p.y > max.y) max.y = p.y;
                if (p.z > max.z) max.z = p.z;
        }

        // The radius of the volume (dimensions in each direction)

        Point   radius = max - min;

        // Find the center of this space

        b.center = min + radius * 0.5;

        // We want a CUBIC space. By this, I mean we want a bounding cube, not
        // just a bounding box. We already have the center, we just need a
        // radius that contains the entire volume. To do this, we find the
        // maxumum value of the radius' X/Y/Z components and use that

        b.radius = radius.x;
        if (b.radius < radius.y) b.radius = radius.y;
        if (b.radius < radius.z) b.radius = radius.z;

        // Done

        return b;
}

// -----------------------------------------------------------------------------
// Generic tree traversal
// -----------------------------------------------------------------------------

const bool Octree::traverse(callback proc, void *data) const
{
        // Call the callback for this node (if the callback returns false, then
        // stop traversing.

        if (!proc(*this, data)) return false;

        // If I'm a node, recursively traverse my children

        if (!_pointCount)
        {
                for (unsigned int i = 0; i < 8; i++)
                {
                        // We store incomplete trees (i.e. we're not guaranteed
                        // that a node has all 8 children)

                        if (!_child[i]) continue;

                        if (!_child[i]->traverse(proc, data)) return false;
                }
        }

        return true;
}