This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

 

  Octree Implementation
  Submitted by



Editor's Note: This code compliments an Ask MidNight response on octrees which can be found here.

Download Associated File: octree.cpp (11,707 bytes)


// 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; }


The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.