Can Anyone Help Me Fix My 3D Space Filling Tree Algorithm?

[intervoxel]

Hi all,

I need an algorithm that fills a 3d lattice from any point, always expanding (no return allowed as in ref. http://msl.cs.illinois.edu/~lavalle/papers/KufLav09.pdf). The cells must be visited just once.
My efforts are contained in the attached file. It works ***almost*** correct. Some gaps remain, though. No matter my attempts I could not fix the code. Could you help me, fixing the code or cite an alternate reference?

The executable (Tree.exe) can use the mouse for orbital rotations and the following keys and conventions:

1 shows root
2 shows x axis
3 shows y axis
4 shows z axis
5 shows xy plane
6 shows yz plane
7 shows zx plane
8 shows octant spirals
q selects the first octant only
a shows positive axes
pgup increases dimension
pgdwn decreases dimension

The not visited positions are shown as a white dot.

The relevant algorithm is contained in the functions expandTree() and isAllowed() in file 'forum.c'.

Thanks for any help.

 

[jedishrfu]

I would ask that you not to provide a zip file but instead post your code here / not all of it just the piece you think has the problem. We have a code tags that will colorize it (syntax highlight) your listing.

What have you tried as far as debugging?

Have you used print statements to see what's going on and whether it makes sense?

or are you just looking at what is produced and then are lost?

 

[intervoxel]

Thank you for the prompt answer, jedishrfu.

I debugged the code using Eclipse without success.

Below is the relevant code, the dirs[] array contains the six von Neumann directions (1,0,0; -1,0,0, ...):

boolean isAllowed(int dir)
{
    // Expansion algorithm
    //
    int s0 = (tree.x * tree.y < 0) ? 1 : 0;
    int s1 = (tree.y * tree.z < 0) ? 1 : 0;
    int s2 = (tree.z * tree.x < 0) ? 1 : 0;
    //
    int sx = sgn(tree.x);
    int sy = sgn(tree.y);
    int sz = sgn(tree.z);
    //
    if(tree.x != 0)
    {
        if(tree.y != 0)
        {
            if(tree.z != 0)
            {
                // 3d spiral
                //
                switch(level % 3)
                {
                    case 0:
                        if(sx < 0)
                        {
                            if(dir == 1) return true;
                        }
                        else
                        {
                            if(dir == 0) return true;
                        }
                        break;
                    case 1:
                        if(sy < 0)
                        {
                            if(dir == 3) return true;
                        }
                        else
                        {
                            if(dir == 2) return true;
                        }
                        break;
                    case 2:
                        if(sz < 0)
                        {
                            if(dir == 5) return true;
                        }
                        else
                        {
                            if(dir == 4) return true;
                        }
                        break;
                }
            }
            else
            {
                // xy plane
                //
                if(level % 2 == s0)
                {
                    if(sx < 0)
                    {
                        if(dir == 1) return true;
                    }
                    else
                    {
                        if(dir == 0) return true;
                    }
                }
                else
                {
                    if(sy < 0)
                    {
                        if(dir == 3) return true;
                    }
                    else
                    {
                        if(dir == 2) return true;
                    }
                }
                //
                if(level % 3 == 0 && dir > 3)
                    return true;
            }
        }
        else if(tree.z != 0)
        {
            // zx plane
            //
            if(level % 2 == s2)
            {
                if(sz < 0)
                {
                    if(dir == 5) return true;
                }
                else
                {
                    if(dir == 4) return true;
                }
            }
            else
            {
                if(sx < 0)
                {
                    if(dir == 1) return true;
                }
                else
                {
                    if(dir == 0) return true;
                }
            }
            //
            if(level % 3 == 2 && (dir == 2 || dir == 3))
                return true;
        }
        else
        {
            // x axis
            //
            if(sx < 0)
            {
                if(dir == 1) return true;
            }
            else
            {
                if(dir == 0) return true;
            }
            //
            if(level % 2 == 0)
            {
                if(sx < 0)
                {
                    if(dir == 2) return true;
                }
                else
                {
                    if(dir == 3) return true;
                }
                //
                if(sx < 0)
                {
                    if(dir == 5) return true;
                }
                else
                {
                    if(dir == 4) return true;
                }
            }
            else
            {
                if(sx < 0)
                {
                    if(dir == 3) return true;
                }
                else
                {
                    if(dir == 2) return true;
                }
                //
                if(sx < 0)
                {
                    if(dir == 4) return true;
                }
                else
                {
                    if(dir == 5) return true;
                }
            }
        }
    }
    else if(tree.y != 0)
    {
        if(tree.z != 0)
        {
            // yz plane
            //
            if(level % 2 == s1)
            {
                if(sy < 0)
                {
                    if(dir == 3) return true;
                }
                else
                {
                    if(dir == 2) return true;
                }
            }
            else
            {
                if(sz < 0)
                {
                    if(dir == 5) return true;
                }
                else
                {
                    if(dir == 4) return true;
                }
            }
            //
            if(level % 3 == 1 && dir < 2)
                return true;
        }
        else
        {
            // y axis
            //
            if(sy < 0)
            {
                if(dir == 3) return true;
            }
            else
            {
                if(dir == 2) return true;
            }
            //
            if(level % 2 == 0)
            {
                if(sy < 0)
                {
                    if(dir == 1) return true;
                }
                else
                {
                    if(dir == 0) return true;
                }
                //
                if(sy < 0)
                {
                    if(dir == 4) return true;
                }
                else
                {
                    if(dir == 5) return true;
                }
            }
            else
            {
                if(sy < 0)
                {
                    if(dir == 0) return true;
                }
                else
                {
                    if(dir == 1) return true;
                }
                //
                if(sy < 0)
                {
                    if(dir == 5) return true;
                }
                else
                {
                    if(dir == 4) return true;
                }
            }
        }
    }
    else if(tree.z != 0)
    {
        // z axis
        //
        if(sz < 0)
        {
            if(dir == 5) return true;
        }
        else
        {
            if(dir == 4) return true;
        }
        //
        if(level % 2 == 0)
        {
            if(sz < 0)
            {
                if(dir == 0) return true;
            }
            else
            {
                if(dir == 1) return true;
            }
            //
            if(sz < 0)
            {
                if(dir == 3) return true;
            }
            else
            {
                if(dir == 2) return true;
            }
        }
        else
        {
            if(sz < 0)
            {
                if(dir == 1) return true;
            }
            else
            {
                if(dir == 0) return true;
            }
            //
            if(sz < 0)
            {
                if(dir == 2) return true;
            }
            else
            {
                if(dir == 3) return true;
            }
        }
    }
    else
    {
        // Root
        //
        return true;
    }
    return false;
}

void expandTree()
{
    int i;
    for(i = 0; i < 6; i++)
    {
        int type = getType(i);
        {
            last.x = tree.x;
            last.y = tree.y;
            last.z = tree.z;
            //
            tree.x += dirs[i].x;
            tree.y += dirs[i].y;
            tree.z += dirs[i].z;
            //
            if(abs(tree.x) == n / 2 + 1 || abs(tree.y) == n / 2 + 1 || abs(tree.z) == n / 2 + 1)
            {
                tree.x -= dirs[i].x;
                tree.y -= dirs[i].y;
                tree.z -= dirs[i].z;
                continue;
            }
            else
            {
                plotLine(last, tree);
                //
                level++;
                expandTree();
                level--;
                //
                tree.x -= dirs[i].x;
                tree.y -= dirs[i].y;
                tree.z -= dirs[i].z;
            }
        }
    }
}

 

[jedishrfu]

I think you probably need to try print statements to get an idea of what its doing as its running then identify the first point where it goes wrong. From there you can use the debugger to run to that spot in your code and step through your logic.

A key part of debugging is knowing how your algorithm is supposed to work by doing it yourself step by step.

I often step thru my code and manually step through my algorithm checking both until I spot the error. Usually its something simple like a < instead of a <= or checking the wrong variable like checking x when it should have been y ( common error during copy/paste and tweak the coding ).

 

[mfb]

Some explanation would help. What does isAllowed do? Where is it used? Where is the point in changing tree and then changing it back no matter what happens - but with separate code for both cases?
Which things do not get visited?

Where is tree defined, where does the program start, and why do you use global variables?