Simple Octree implementation

I've implemented a rather straightforward octree, but I don't feel that good about the coding style or some of the implementation. In particular, I use some nasty void pointers and extra news because I couldn't figure unions out, and I'd like to have that replaced (I'm thinking maybe templating can solve it, but any feedback is appreciated).

There are a few methods I'm not very interested in that are in the interface, but haven't been implemented. Feel free to ignore them, as they shouldn't have a substantive effect on the rest of the code.

Lastly, I'm not looking for a complete overhaul of the structure of the octree - I'm going to implement some other versions at a later date (i.e. pointerless duals, a few other fun ones), so please review this structure, where each node has a pointer to 8 children.

Octree.h

```
/*
file - octree.h

Templated implementation of an octree for a cpu

*/

#ifndef OCTREE_CPU_H
#define OCTREE_CPU_H

#include
#include
#include
#include
#include
#include
#include

#include "boundingbox.h"

using Point = std::array;

template
class Octree {
public:
using tree_type = Octree;

Octree();

Octree(InputIterator begin, InputIterator end);

Octree(InputIterator begin, InputIterator end, PointExtractor f);

Octree(const tree_type& rhs);

template
Octree(const Octree& rhs);

template
Octree(const Octree& rhs);

template
Octree(const Octree& rhs);

Octree(tree_type&& rhs);

void swap(tree_type& rhs);

template
bool search(const BoundingBox& box, OutputIterator& it) const;

tree_type& operator=(tree_type rhs);

tree_type& operator=(tree_type&& rhs);

~Octree();

size_t size() const;

private:
class Node;

enum NodeContents {
LEAF = 1,
MAX_DEPTH_LEAF = 2,
INTERNAL = 4
};

struct LeafNodeValues {
std::array, max_per_node> values_;
size_t size_;
};

using childNodeArray = std::array;
using maxItemNode = std::vector>;

class Node {
public:

I'm looking only at the BoundingBox class. There are a lot of interesting cleanups you can apply to it:

Ditch the constructors

BoundingBox is a Plain Old Data (POD) type. It only holds a handful of doubles, so the compiler will supply all the necessary default constructors and operators, including:

• Copy constructor

• Assignment operator

• No-op destructor

Move operator and move-assign are pointless. You cannot move a double, it fits in a machine register, so the ones you've implemented basically do the same as a copy constructor. Your copy/assignment code is essentially doing unsafe memcopies and might even be less efficient than the defaults the compiler would generate had you omitted them.

But we still got these two:

BoundingBox(InputIterator begin, InputIterator end);
BoundingBox(std::initializer_list l);

The initializer list constructor is cool, it lets you write code like this:

BoundingBox bb = { 1.0, 2.0, 3.0,  4.0, 5.0, 6.0 };

But it turns out that you don't even need to define one. If you instead remove all the other constructors and leave all data public, as it is now, you can already initialize a struct instance with that syntax.

But to get the aggregate-style initialization working we need to remove all user defined constructors, so the begin/end range constructor has to go. I would consider this a fair trade, given how much it would simplify the code, so instead, consider turning that constructor into a helper function:

template 
BoundingBox makeBoundingBox(InputIterator begin, InputIterator end);

BoundingBox is cheap to copy, so that function should be just as fast as the constructor, assuming it isn't inlined (which is likely, since it is a template).

Types are your friends

So don't be afraid to make new friends (i.e. create other helper types) ;)

This member data:

double xhi, xlo, yhi, ylo, zhi, zlo;

Should be a type, like a Point3D:

struct Point3D {
    double x;
    double y;
    double z;
};

I can see that you have a quasi-Point3D already by using a std::array of 3 elements, but I'd advise making it a struct in its own right, so it can have methods and also the nicer v.x, v.y v.z syntax over just v[0], v[1], v[2].

Miscellaneous

-
The stream output operator doesn't have to be a friend function. The struct has no private data. You only use friend when you want to allow access to the private data of the type in question. Just make it a free-standing function.

-
The comparison operator is way too big. Assuming we went with the Point3D idea, it could be rewriting like so:

bool BoundingBox::operator == (const BoundingBox& rhs) const {
    const bool allEqual = (mins == rhs.mins && maxs == rhs.maxs);
    if (allEqual) return true;

    const bool allNaN = (mins.isNaN() && rhs.mins.isNaN() && 
                         maxs.isNaN() && rhs.maxs.isNaN());
    if (allNaN) return true;

    return false;
}

A couple notes on the above:

-
I've used the names mins and maxs for our bounding box extents. That's a very common notation for this particular data structure, so I'd suggest sticking to that.

-
Also note that comparing floating point numbers with == is not very reliable. They are prone to floating point rounding errors, so you might end up with two very close numbers that for all purposes would be equal but end up comparing not equal. Take a look at Stack Overflow on how to compare floats for equality within a given epsilon.

Summing up, this is how your axis-aligned bounding-box could look like after the suggested changes:

struct Point3D {
    double x;
    double y;
    double z;

    bool isNaN() const;
    bool operator == (const Point3D& other) const;
};

struct BoundingBox {
    Point3D mins;
    Point3D maxs;

    bool contains(const BoundingBox& other) const;
    bool contains(const Point3D& point) const;

    bool overlap(const BoundingBox& other, BoundingBox* out) const;
    std::array partition() const;

    bool operator == (const BoundingBox& rhs) const;
    bool operator != (const BoundingBox& rhs) const;
};

template 
BoundingBox makeBoundingBox(InputIterator begin, InputIterator end);
std::ostream& operator << (std::ostream& stream, const BoundingBox& rhs);

StackExchange Code Review Q#124883, answer score: 6