c++arraystreetree-traversaloctree

How to properly assign indexes when transforming octree into array?

I'm attempting to flatten an octree into an array so that I can pass it to the GPU. I want to get the data from my octree, load it into a vector of Voxel structs and then send that over to the GPU. I'm inserting 2 voxels into the octree at the beginning. These are my insert functions:

template<typename T>
Octree<T>::Octree(glm::vec3 position, float octreeSize, int depth) : root(position, 1.0f), depth(depth), octreeSize(octreeSize), transform(1.0f)
{
    insert(glm::vec3(0.5, 0.1, 0.7f), true);
    insert(glm::vec3(-0.5, -0.1, -0.7f), true);
    transform = glm::translate(transform, glm::vec3(0, 0, 5));
}

template<typename T>
void Octree<T>::insert(glm::vec3 pos, T data)
{
    root.subdivide(pos, data, depth, 1.0f);
}

template<typename T>
int Octree<T>::Node::getIndexOfPosition(glm::vec3 lookupPosition, glm::vec3 nodePosition) const
{
    int index = 0;
    index |= lookupPosition.y > nodePosition.y ? 4 : 0;
    index |= lookupPosition.x > nodePosition.x ? 2 : 0;
    index |= lookupPosition.z > nodePosition.z ? 1 : 0;

    return index;
}


template<typename T>
void Octree<T>::Node:: subdivide(glm::vec3 targetPos, T value, int divDepth, float parentSize)
{
    int subdivIndex = getIndexOfPosition(targetPos, position);
    if(children.empty())
    {
        for(int i = 0; i < 8; i++)
        {
            glm::vec3 newPos = position;
            float sizeModifier = parentSize * 0.5f;
            if ((i & 4) == 4)
                newPos.y += sizeModifier;
            else
                newPos.y -= sizeModifier;

            if ((i & 2) == 2)
                newPos.x += sizeModifier;
            else
                newPos.x -= sizeModifier;

            if ((i & 1) == 1)
                newPos.z += sizeModifier;
            else
                newPos.z -= sizeModifier;
            Node newNode(newPos, sizeModifier);
            children.push_back(newNode);
        }
    }

    if (divDepth > 0)
    {
        //std::cout << "Subdividing" << std::endl;
        children[subdivIndex].subdivide(targetPos, value, divDepth - 1, parentSize*0.5f);
    }
    else
    {
        children[subdivIndex].data = value;
    }
}

My Voxel struct:

struct Voxel
{
    Voxel(): pIndex(-1), index(-1), pos(90000.f), col(0.f) { for (int & i : cIdx) i = -1; }
    int cIdx[8]; // The indexes of the child nodes in the vector
    int index;   // The current index of this voxel within the vector
    int pIndex;
    glm::vec4 pos;
    glm::vec4 col;
};

Currently I'm traversing my octree in pre-order, I recursively iterate through each nodes children (if they have any), setting the current voxels child index to the current index, then doing the same for all it's children. Finally once we're at the bottom of the tree or we have no children, push that node onto the GPU and set the child nodes parent index to the current index. This is my function:

template<typename T>
int
Octree<T>::Node::fillShaderVector(std::vector<Voxel> &voxelData, glm::mat4 octTransform, float octSize, int index) const
{
    Voxel voxel;
    if (isInternal())
    {
        int i = 0;
        for (auto child: children)
        {
            // I think this is where we have issues
            voxel.cIdx[i] = index;
            index = child.fillShaderVector(voxelData, octTransform, octSize, index);
            i++;
        }
    }

    voxel.pos = glm::vec4(position, 1.0);
    // Store size as the 4th element in the vector
    voxel.pos.w = voxelSize;
    voxel.col = glm::vec4(1.0);
    voxel.index = index;

    voxelData.push_back(voxel);
    index++;

    if (isInternal())
    {
        for(int i : voxel.cIdx)
            voxelData[i].pIndex = voxel.index;
    }

    return index;
}

template<typename T>
bool Octree<T>::Node::isInternal() const
{
    return !children.empty();
}

This iterates through the nodes correctly and I'm able to get the correct indexes for each voxel, however I cannot seem to set the parent indexes properly.

Example output (I've cut out a lot for the sake of brevity, it goes from 0..56 Parent: -1 means no parent node, i.e. should only be the root node, and child: -1, means that it's a leaf node):

Index: 0
Parent: 56
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 1
Parent: 24
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 2
Parent: 24
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 3
Parent: 24
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 4
Parent: 24
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 5
Parent: 20
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 6
Parent: 20
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 7
Parent: 20
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 8
Parent: 20
Children: -1 -1 -1 -1 -1 -1 -1 -1
...
Index: 16
Parent: 19
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 17
Parent: 19
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 18
Parent: 19
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 19
Parent: -1
Children: 11 12 13 14 15 16 17 18
Index: 20
Parent: -1
Children: 4 5 6 7 8 9 10 11
...
Index: 47
Parent: 48
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 48
Parent: -1
Children: 32 33 34 43 44 45 46 47
Index: 49
Parent: 55
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 50
Parent: 55
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 51
Parent: 55
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 52
Parent: 55
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 53
Parent: 55
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 54
Parent: 55
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 55
Parent: -1
Children: 31 32 49 50 51 52 53 54
Index: 56
Parent: -1
Children: 0 25 26 27 28 29 30 31

What am I doing wrong in my fillShaderVector function that is preventing me from accurately filling in parent indexes?

Solution

  • I fixed the issue, going in pre-order I push the voxel onto the vector and then I make modifications directly to the vector using it's index and update both the parent and children data succesfully.

    New insertion code

    template<typename T>
int
Octree<T>::Node::fillShaderVector(std::vector<Voxel> &voxelData, glm::mat4 octTransform, float octSize, int index) const
{
    Voxel voxel;

    voxel.pos = glm::vec4(position, 1.0);
    // Store size as the 4th element in the vector
    voxel.pos.w = voxelSize;
    voxel.col = glm::vec4(1.0);
    voxel.index = index;

    voxelData.push_back(voxel);
    index++;
    if (isInternal())
    {
        int i = 0;
        for (auto child: children)
        {
            voxelData[voxel.index].cIdx[i] = index;
            index = child.fillShaderVector(voxelData, octTransform, octSize, index);
            i++;
        }
    }
    if (isInternal())
    {
        for(auto c: voxelData[voxel.index].cIdx)
            if(c != -1) voxelData[c].pIndex = voxel.index;
    }

    return index;
}

    which leads to proper indexing and hierarchy

    Index: 0
Parent: -1
Children: 1 26 27 28 29 30 31 32
Index: 1
Parent: 0
Children: 2 3 4 5 6 23 24 25
Index: 2
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 3
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 4
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 5
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 6
Parent: 1
Children: 7 8 9 10 11 12 13 14
Index: 7
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 8
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 9
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 10
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 11
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 12
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 13
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 14
Parent: 6
Children: 15 16 17 18 19 20 21 22
Index: 15
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 16
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 17
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 18
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 19
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 20
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 21
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 22
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 23
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 24
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 25
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 26
Parent: 0
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 27
Parent: 0
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 28
Parent: 0
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 29
Parent: 0
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 30
Parent: 0
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 31
Parent: 0
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 32
Parent: 0
Children: 33 34 51 52 53 54 55 56
Index: 33
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 34
Parent: 32
Children: 35 36 37 46 47 48 49 50
Index: 35
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 36
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 37
Parent: 34
Children: 38 39 40 41 42 43 44 45
Index: 38
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 39
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 40
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 41
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 42
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 43
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 44
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 45
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 46
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 47
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 48
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 49
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 50
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 51
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 52
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 53
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 54
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 55
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 56
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1