I am struggling my way through implementing a sparse voxel octree, but I don't know how to differenciate between branch and leaf nodes effectively.

One way I thought of was to downcast the Node pointers to a child class, but I fear a big performance hit from casting thousand of times

struct Node
{
    Node* parent;
};

struct Branch : public Node
{
    Node* children[8];
    unsigned char activeChildren = 0;
};

struct Leaf : public Node
{
    unsigned char color[3];
}

Then I read about type unions, but my compiler went wild and I got tons of weird errors when trying to access the unions variables.

struct Leaf
{
    unsigned char r = 0;
    unsigned char g = 0;
    unsigned char b = 0;
};

struct Branch
{
    Node* children[8];
    unsigned char activeChildren = 0;
};

union NodeData
{
    Leaf leaf;
    Branch branch;
};

struct Node
{
    Node* parent;
    NodeData data;
};

Now I'm thinking about storing the data in a bitmask big enough to fit the biggest node type, and setting an extra bit to know if it's a branch or leaf.

class Node
{
public:
    // getter and setter for the nodes content

public:
    Node* parent;

private:
    // bitmask
    // 8*64 bits for pointers to children
    // 8 bit to identify active nodes
    // 
    // 1 bit to identify node type
    // 7 unused bits -> maybe for depth of the node
    unsigned char bitmask[66];
};

How would this be handled usually?

Thanks in advance for your help!

CodePudding user response：

Premature optimization is the root of all evil

Check here why

You are worrying now about a performance issue that you don't know if it will ever happen. Make your implementation using dynamic_cast<> as suggested.

Once your implementation is working, you can benchmark it and see if the casts are really a problem. And I bet they won't be, their implementation is very similar to creating an isLeaf() method.

CodePudding user response：

Your options are:

1. Inheritance

Like your original solution. Easy to understand.

template<typename T>
class Node {
};

template<typename T>
class Internal<T> : public Node<T> {
    Node<T> *children[8];
};

template<typename T>
class Leaf<T> : public Node<T> {
    T value;
};

Speed overhead: either one or more virtual functions or dynamic_casting.

Size overhead: one vtable pointer, probably 8 bytes on a 64-bits platform.

2. A discriminated union

Since the two types of nodes occupy the same bytes in memory, you need to add some way to distinguish which of the types is valid.

template<typename T>
class Node {
    bool isLeaf;
    union {
        T value;              // Valid if isLeaf
        Node<T> *children[8]; // Valid if !isLeaf
    };
};

Speed overhead: a boolean check.

Size overhead: one byte, plus probably 7 bytes of padding on a 64-bits platform.

Advanced idea: if sizeof(value) is less than sizeof(children) by at least sizeof(Node<T> *), you can avoid the space overhead of the isLeaf flag by prepending a null pointer to the value. Then you can check if children[0] == nullptr to detect whether it's a leaf. This will usually work, but is technically undefined behaviour.

3. No polymorphism at all

Have a single type that contains both data and pointers to child nodes. You can deduce whether it's a leaf by checking children[0] == nullptr.

template<typename T>
class Node {
    bool isLeaf;
    T value;              // Valid if isLeaf
    Node<T> *children[8]; // Valid if !isLeaf
};

Speed overhead: a pointer check.

Size overhead: either the value or the child pointers are redundant.

So there really is no advantage compared to solution 2.