Strange behavior when inserting boxes into an empty tree

[tonichedgehog]

Hi @attcs, it's a very nice octree implementation you have made. I'm experiencing a somewhat unexpected behavior when trying to use it, as demonstrated with the patch below.

• If I create a tree by inserting bounding boxes one-by-one, the resulting tree is different from a tree created with all bounding boxes at once. Is this by design, or am I just using it wrong?

• Also, there seems to be some problems with uniqueness, the check (triggered by calling UpdateIndexes<true>({})) fails for some reason. Is this check expected to pass, or can it safely be ignored?

Thanks in Advance.

diff --git "a/unittests/general.tests.cpp" "b/unittests/general.tests.cpp"
index 38eb084..e3bfa15 100644
--- "a/unittests/general.tests.cpp"
+++ "b/unittests/general.tests.cpp"
@@ -1825,6 +1825,44 @@ namespace Tree2DTest

 namespace Tree3DTest
 {
+  TEST_CLASS(Box_AddTest)
+  {
+      TEST_METHOD(CreateWithData)
+      {
+          // This gives a tree with 9 nodes.
+          std::vector<BoundingBox3D> treeData = {
+              { { -2.00375, -0.20375, +0.19625 }, { -1.52125, -0.19625, +0.20375 } },
+              { { -0.88692, -1.05210, -0.80026 }, { +0.88692, +0.72175, +0.97359 } },
+              { { -0.78692, -1.05210, -0.80026 }, { +0.98692, +0.72175, +0.97359 } },
+              { { -0.68692, -1.05210, -0.80026 }, { +1.08692, +0.72175, +0.97359 } },
+              { { -0.58692, -1.05210, -0.80026 }, { +1.18692, +0.72175, +0.97359 } },
+          };
+
+          OctreeBox tree(treeData, 8, BoundingBox3D{ { -10, -10, -10 }, { +10, +10, +10 } }, 2);
+          tree.UpdateIndexes<true>({});
+      }
+
+      TEST_METHOD(AddToEmptyTree)
+      {
+          // This gives a tree with 10 nodes.
+          std::vector<BoundingBox3D> treeData;
+          OctreeBox tree(treeData, 8, BoundingBox3D{ { -10, -10, -10 }, { +10, +10, +10 } }, 2);
+
+          std::vector<BoundingBox3D> boxes = {
+              { { -2.00375, -0.20375, +0.19625 }, { -1.52125, -0.19625, +0.20375 } },
+              { { -0.88692, -1.05210, -0.80026 }, { +0.88692, +0.72175, +0.97359 } },
+              { { -0.78692, -1.05210, -0.80026 }, { +0.98692, +0.72175, +0.97359 } },
+              { { -0.68692, -1.05210, -0.80026 }, { +1.08692, +0.72175, +0.97359 } },
+              { { -0.58692, -1.05210, -0.80026 }, { +1.18692, +0.72175, +0.97359 } },
+          };
+
+          for (unsigned i = 0; i < boxes.size(); ++i) {
+              Assert::IsTrue(tree.Insert(i, boxes[i], true));
+              treeData.emplace_back(boxes[i]);
+          }
+          tree.UpdateIndexes<true>({});
+      }
+    };
 }```

[attcs]

Hi @tonichedgehog!

I am glad you like it, and I hope this will be useful for you!

1. Yes, the Insert and the Create methods could lead to different trees.

Entity0: Node6362 is the Leaf node. Entity1,2,3,4 are cross the zero planes, so Node1 is the Leaf node.

Insert: Entity0 is split into 3 pieces because of the nSplitStrategyAdditionalDepth = 2, those Leaf nodes are 407187, 407194, 407195. fInsertToLeaf = true, so these are created, then the parent nodes are as well.

Create: nSplitStrategyAdditionalDepth = 2, therefore the placing begins at Node6362, but the leaf insert is not forced, it could stop if NoElements < 2 (this is what you set with nElementMaxInNode = 2), and in the case of Node50898 it does, the other two will reach the final leaf nodes. Create could always stop, if nElementMaxInNode condition is fulfilled.

By default nSplitStrategyAdditionalDepth = 2, which means the entities are divided by the grid system and pushed down with 2 levels than the original leaf node. The adjustment of nSplitStrategyAdditionalDepth due to your problem could be beneficial, if the possibility of entity grid crossing is lower, eg. small entities compared to the boundary space.

2. Uniqueness check is only developed for nSplitStrategyAdditionalDepth = 0, otherwise, the entity ids are inevitably placed into multiple nodes.

If you definitely need Insert, I recommend the OctreeBoxC wrapper, its member functions: Add/Update/Erase, these are maybe more foolproof than the underlying solution's Insert.

[tonichedgehog]

Hi, and thanks a lot for the info on nSplitStrategyAdditionalDepth and the uniqueness check, I now have a better understanding of how to tune the implementation to suit my needs.

One reason for choosing the core tree instead of the wrapper, is that I need to maintain a mapping between the entities I want to update, and their respective entity id. I don't think the wrapper prevents me from that, I just need to rethink my approach a little.

Thanks, /J