test_pruning fails under Windows

[merfels]

Hi,

the test case test_pruning fails under Windows 64bit Visual Studio 2010 for unknown reason. This is a minimal code example which shows the same behavior:

double res = 0.01;
OcTree tree(res);

for (double x=0.005; x <= 0.32; x+=res){
    for (double y=0.005; y <= 0.32; y+=res){
        for (double z=0.005; z <= 0.32; z+=res){                
            OcTreeNode* node = tree.updateNode(x,y,z, true);
            /*if(!tree.isNodeOccupied(node)) {
                node = tree.search(x,y,z);
            }*/
            EXPECT_TRUE(node);
            EXPECT_TRUE(tree.isNodeOccupied(node));
        }
    }
}

In this setup, it will return false for tree.isNodeOccupied(node) for (x,y,z) = (0.015, 0.015, 0.015) and I have no idea why. It works under Linux though. If you add the commented part (tree.search()) then you will notice that this function returns another pointer than tree.updateNode(), and then isNodeOccupied yields true. Do you have any idea why this code doesn't work?

Edit: so everything I stated above is true for when you compile it in Debug mode, but there seems to be no problem in Release mode?!

Best,
Christian

[ahornung]

Weird, I would guess that overly aggressive optimization could be a problem but here it's the other way around only Debug is problematic?

To debug further you could output the explicit node values before and after updating.

Does the problem also affect earlier releases (1.6, 1.5, 1.4)?

[ahornung]

Regarding the different pointers: That could happen and is a valid behavior. After you update 8 child nodes of a parent identically, the children get auto-pruned since the parent already contains the information. Searching for any coordinate within a child will then return the pointer to the parent. That behavior was introduced with v1.6.

[merfels]

So we tried several things and we're trying to nail it down but with not a lot of success. We've seen some strange behavior which seems to relate to the Visual Studio compiler/debugger. It was possible to create an even smaller testcase which just consists of 8 nodes being updated as occupied, and it has the bug as well. I then tried the 1.5.6 version (which supposedly doesn't have autopruning) and there test_pruning seems to work just fine, no errors. Could you give me some information what the major changes for autopruning where? I will then try to dig into it a little deeper.

[ahornung]

Thanks for digging into this! The autopruning commit in question was b3ca41b. Although there are other changes in the range v1.5.4...v1.6.0 that could be the culprit... => git bisect?

[wessnerj]

I got exactly the same behavior than merfels, so I digged into the code and I think I have located the bug:

Following function in OccupancyOcTreeBase.hxx

template <class NODE>
NODE* OccupancyOcTreeBase<NODE>::updateNodeRecurs(NODE* node, bool node_just_created, const OcTreeKey& key,
    unsigned int depth, const float& log_odds_update, bool lazy_eval)

returns the pointer to the node, where the value has been updated. Now when the pruning happens the function will still return the pointer to the node, which was updated. Unfortunately this node was been deleted by the pruning before, so the function will return an invalid pointer.
As a bugfix I suggest changing following code:

            if (lazy_eval)
                return updateNodeRecurs(node->getChild(pos), created_node, key, depth+1, log_odds_update, lazy_eval);
            else {
                NODE* retval = updateNodeRecurs(node->getChild(pos), created_node, key, depth+1, log_odds_update, lazy_eval);
                // prune node if possible, otherwise set own probability
                // note: combining both did not lead to a speedup!
                if (node->pruneNode())
                    this->tree_size -= 8;
                else
                    node->updateOccupancyChildren();

                return retval;
            }

with this one:

            if (lazy_eval)
                return updateNodeRecurs(node->getChild(pos), created_node, key, depth+1, log_odds_update, lazy_eval);
            else {
                NODE* retval = updateNodeRecurs(node->getChild(pos), created_node, key, depth+1, log_odds_update, lazy_eval);
                // prune node if possible, otherwise set own probability
                // note: combining both did not lead to a speedup!
                if (node->pruneNode()) {
                    this->tree_size -= 8;
                    retval = NULL; // or maybe node will be better?
                }
                else
                    node->updateOccupancyChildren();

                return retval;
            }

I still don't know why the VisualStudio Debug compiler overwrites the memory after the delete (in the pruning function), but anyways returning a invalid pointer appears to be a bug for me. ;)

[ahornung]

Good catch! NULL is reserved for errors, e.g. when the coordinates are out of bounds in updateNode so I'll change it to returning node. That way the pointer remains usable.

Other compilers should at least result in a segfault when accessing the invalid (pruned) node, but I guess the deletion gets postponed due to some optimization. I'll also add a unit test that catches this error.

[ahornung]

Fixed, along with a unit test that would also fail on Linux / gcc. Let me know if there are still issues with VS!