Programming, Work

My weekends have been very productive

I was removing some old implementation and I removed just about any Unity GameObject I was needlessly constructing. So, the only game objects my editor is creating are the wrappers around the final geometry, the rest is just numbers in arrays and custom structures and classes. Very few instances where we allocate from the heap and the results are very efficient and make room for a lot of other things.

When I removed the game objects, I also polished my Octree to a blistering shine. I am not using any ray casts or bounding volumes for finding shapes within the scene. Just a very efficient Octree.

All the items in the Octree are just points. There are no lists of structs or classes representing nodes, just the points.

It is a linear array ordered from back to front. Meaning that the root of the tree is at the back of it, and all the leafs are at the front. That way I can use the indices after the traversal as look ups into other linear data arrays within the tree that are the same size as the leafs.<

int GetLeaf(int px, int py, int pz)
{
    // The order of the children follow
    // a 3 bit binary table.
    // x:y:z where the sign relative to their parents origin is their bit state.
    // The tree was constructed with the same rules.

    // The tree is setup in a linear array of points.
    // A Octree with 4096 leafs would look something like this.
    // [4096][512][64][8][1]

    // The leafs are at the front and the root is at the back.
    // This way we can use the indices we get from this function as
    // an index into other linear arrays of data that are only the
    // same size as the leafs.

    // We start at the very end
    int baseLine = m_positions.Length;
    int cindex = 0;
    int accum = 0;
    for (int i = 0; i < m_levels; i++)
    {
        // What child do we need to jump to.
        cindex = 0;
        // Set our index to the correct base
        baseLine = baseLine - s_powersOf8[i];
        // Create the number from the sign values
        cindex |= (px >= m_positions[baseLine + accum][0]) ? 4 : 0;
        cindex |= (py >= m_positions[baseLine + accum][1]) ? 2 : 0;
        cindex |= (pz >= m_positions[baseLine + accum][2]) ? 1 : 0;

        // Accumulate the index.
        accum = (accum * 8) + cindex;
    }

    return accum;
}

Cool, ha?

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s