Help Request

[kriNon]

Hey, I'm currently in the process of switching over from Unreal Engine 5's Octree implementation to this one (specifically OrthoTree::OctreeBox). I'm having a few small issues, and I was hoping I could get some help.

The one major issue I'm running into is that Unreal Engine's implementation has a function: void FindElementsWithBoundsTest(const FBoxCenterAndExtent& BoxBounds, const IterateBoundsFunc& Func) What it does is return all elements that are within the BoxBounds.

The closest that I've been able to find is RangeSearch, but RangeSearch has a requirement for a span<box_type const> const& vBox to be passed in. Maybe I'm misunderstanding something though.

[kriNon]

I spent some more time working on trying to figure this out, and I made a bit of progress. It looks like instead of OctreeBox I want to use OctreeBoxC.

I'm having some issues getting it working though. What I am doing is, I iterate over my lights and call this code: bool success = LightingOctree.Add(OrthoTree::BoundingBox3D{{MinPoint.X,MinPoint.Y,MinPoint.Z}, {MaxPoint.X,MaxPoint.Y,MaxPoint.Z}}, true); Afaik this should be working, but it is always returning false. My first guess as to why it is always returning false would be that I need to call create() before I can add to the octree, but maybe it is something else?

Then when I want to find elements in my boxbounds, I can call: LightingOctree.RangeSearch(OrthoTree::BoundingBox3D{ {MinPoint.X, MinPoint.Y, MinPoint.Z}, {MaxPoint.X, MaxPoint.Y, MaxPoint.Z}}); And this should work fine?

[attcs]

Hi,

The Add function will fail if your box is not in the handled space of the octree. Is the tree bounding box set properly (or in debug, m_box member shows proper values)? If you have already all lights when the octree is created, much more effective to use the Constructor or the Create. These functions set up everything that you need and use a much faster algorithm.

OctreeBoxC is a good choice. OctreeBox is a not containing solution, therefore you need to add all box information of the entities at all searches.

[kriNon]

Hey, thanks for the quick response!

I suspect that the issue is that the tree bounding box is not set properly, but I'm not sure how to do that. In debug m_box doesn't show proper values. I don't have all lights when the octree is created, so I don't think using the constructor or create helps me there.

[kriNon]

I ended up getting it somewhat working, although it is in a very janky & suboptimal setup. Instead of trying to add to the octree whenever a light is spawned, I am currently clearing the entire octree and calling create using the entire list of lights.

This works, but it is not ideal.

When I go back to trying to use Add it doesn't work. Based on this information it does sound right that add is failing because the tree's bounding box is not being set properly.

[attcs]

First of all, I found a bug! Thank you for the feedback, this part of the implementation is undertested. I pushed up the bugfix.

I made a little unittest case, which is also a guide what is the intended usage. It could be suboptimal, but the previously focused use-cases came from my own field of expertise (scientific calculation). But I am open to any suggestion to make this tool better.

    TEST_METHOD(InitThenInsert)
    {
      auto tree = DualtreeBoxC{};
      autoc handledSpaceDomain = BoundingBox1D{ -2, +2 };
      tree.Init(handledSpaceDomain, 3, 10);

      // Trying to add into the lead nodes
      {
        autoc boxes = array
        {
          BoundingBox1D{ -2.0, -1.0 },    // Fit in the leaf node
          BoundingBox1D{ -1.0,  0.0 },    // Fit in the leaf node
          BoundingBox1D{  0.0,  1.0 },    // Fit in the leaf node
          BoundingBox1D{  1.0,  2.0 },    // Fit in the leaf node
          BoundingBox1D{ -1.5,  1.5 }     // Only fit in a parent node
        };

        for (auto const& box : boxes)
        {
          autoc isInsertedSuccessfully = tree.Add(box, true /* Insert into leaf */);
          Assert::IsTrue(isInsertedSuccessfully);
        }
      }

      // Adding nodes in the current structure
      {
        autoc boxes = array
        {
          BoundingBox1D{ -1.5, -1.2 },    // Fit in the leaf node
          BoundingBox1D{ -1.2,  0.2 },    // Not fit in the leaf node
          BoundingBox1D{  0.0,  1.0 },    // Fit in the leaf node
          BoundingBox1D{ -1.1,  1.2 }     // Only fit in the root
        };

        for (auto const& box : boxes)
        {
          autoc isInsertedSuccessfully = tree.Add(box, false /* Insert into the previously defined nodes */);
          Assert::IsTrue(isInsertedSuccessfully);
        }
      }

      // Outside of the handled domain
      {
        autoc boxIsNotInTheHandledSpace = BoundingBox1D{ 1, 3 }; // Min point inside, max point outside
        autoc isInsertedSuccessfully = tree.Add(boxIsNotInTheHandledSpace);
        Assert::IsFalse(isInsertedSuccessfully);
      }

      autoc& nodes = tree.GetCore().GetNodes();
      Assert::AreEqual<size_t>(7, nodes.size());

      autoc idsActual = tree.RangeSearch<false /*overlap instead of fully contained*/>(BoundingBox1D{ -1.1, 0.9 });
      autoc idsExpected = vector<size_t>{ /* 1. phase */ 0, 1, 2, 4, /* 2. phase */ 6, 7, 8 };
      Assert::IsTrue(std::ranges::is_permutation(idsActual, idsExpected));
    }

And there are two other things that you should know:

• Be aware of nSplitStrategyAdditionalDepth, in Issue #3, it is already explained what is it, and how it works. Maybe you can use the nSplitStrategyAdditionalDepth = 0, which can be set in your own definition but the simplest way to adjust here:

  
  template<dim_type N, uint32_t nSplitStrategyAdditionalDepth = 2>
  using TreeBoxContainerND = OrthoTreeContainerBox<TreeBoxND<N, nSplitStrategyAdditionalDepth>, BoundingBoxND<N>>;

 - This implementation cannot be dynamically extended yet, because there won't be a use-case before.

[kriNon]

I think that I have found another bug (although it might be intentional): If you try to remove an element that doesn't exist in the octree, it will crash, for example:

LightingOctree.Reset();
LightingOctree.Init(OrthoTree::BoundingBox3D{{-9999,-9999,-9999}, {9999,9999,9999}}, 10, 4);
LightingOctree.Erase(0);

On one hand, I can understand the argument that trying to remove something that doesn't exist should enter some sort of failure state, but on the other hand it still would be nice if this didn't crash.

But yeah, at the moment I'm having some challenges managing the lifecycle of the object that holds my octree. It's a bit of a challenging situation that will take a bit of troubleshooting. Because I am not managing the lifecycle of the object correctly, some amount of state isn't being reset, which means that when I reload my world (which involves destroying and then constructing a new world), the event for lights being destroyed in the previous world is being called after the construction of the new world, which is attempting to remove lights that don't exist.

Again to reiterate, this is definitely an issue with my code, however I think that this issue with my code has helped to find a potential issue in the octree implementation. Especially since it looks like Erase is intended to be safe.

Relevant part of the crash report:

Unhandled Exception: EXCEPTION_ACCESS_VIOLATION reading address 0x0000000000000000

UnrealEditor_AdvancedLighting!OrthoTree::OrthoTreeBoundingBox<3,std::array<double,3>,OrthoTree::BoundingBoxND<3,double>,OrthoTree::AdaptorGeneralBase<3,std::array<double,3>,OrthoTree::BoundingBoxND<3,double>,OrthoTree::AdaptorGeneralBasics<3,std::array<doubl() [U:\Unreal Projects\AdvancedLights-master\Plugins\AdvancedLighting\Source\AdvancedLighting\Public\Octree\octree.h:2100]
UnrealEditor_AdvancedLighting!OrthoTree::OrthoTreeContainerBase<OrthoTree::OrthoTreeBoundingBox<3,std::array<double,3>,OrthoTree::BoundingBoxND<3,double>,OrthoTree::AdaptorGeneralBase<3,std::array<double,3>,OrthoTree::BoundingBoxND<3,double>,OrthoTree::Adapt() [U:\Unreal Projects\AdvancedLights-master\Plugins\AdvancedLighting\Source\AdvancedLighting\Public\Octree\octree_container.h:106]

[attcs]

Thank you, I fixed it too.

If you have a totally new world, with new entities, it may be worth recreating the whole tree. Generally speaking, in any case, if possible, use the constructor()/Create() these are always faster than entity-wise adding the same system.

It is worth revising the settings: Higher element numbers by node, with lower depth could have better performance. Too deep trees could be slowed by the administration step in adding/searching. E.g.: During the search, on every node level, it has to make a box overlap check with all existing child nodes. The entities who are not fit in the base resolution grid will land in a parent node anyway, maybe as sliced (according to nSplitStrategyAdditionalDepth). I reached the best performance around 10 max. entity elements by nodes in my benchmarks.

[kriNon]

Hey, I was hoping to get some feedback if that is okay with you. I've been making some decent progress refactoring my code and overall things are mostly functional, however I've run into an issue that I hadn't considered. The world in my lighting engine is (somewhat) infinite. This is an issue because lights can be anywhere in the world, and octrees have limited bounds. This is likely not something that you have run into in scientific computing, but I'm interested in your intuition on the task.

I spent some time researching how this is normally handled, and there are two main ways of handling this:

1. World Origin Shifting: Shift the coordinates of all objects relative to the player, such that objects near the player end up being within the bounds of the octree, and objects far away from the player end up not being in the bounds of the octree. This means that the octree is frequently being invalidated, but with some planning it is possible to shift already existing nodes (and only recalculate part of the tree). I am not a huge fan of this approach though.

2. Split the world into a sparse grid of chunks (e.g. 1000m1000m1000m cubes). Each chunk contains an octree (with so many octrees we will likely want to lower the depth of each individual octree). The octrees in each chunk are only allocated / created when an object is spawned within that grid. There is also minimal re-processing of objects. My only concern would be objects that straddle the border of multiple chunks, but I'm sure that some sort of workaround exists.

I am currently leaning towards option 2.

Thanks a lot for the continued support!

[attcs]

Hi! It's a tough question, and I have no in-depth experience. Maybe you should check/ask on a game development forum. So what I could say, that is very general. You have to think over the following questions: How many entities must be handled? How many search or collision detection happens? How many inserts happen? How dense is the handled space? What is the size of the objects (they could be stuck on a parent node)?

Maybe you should not bother with Octree at all. From what I read on this topic, the overall effectiveness by No. of elements follows this order: Grid < k-D tree < BVH < Loose octree < Octree. If you have

• less than 100 objects maybe you don't need anything,
• less than 1000, an octree is usually slower than the other hierarchies.

But what I learned from a SimonDev video (Spatial Hash Grids & Tales from Game Development), a simple sparse grid for the objects could work fine in a lot of cases. Easy to implement and easy to solve adding new elements to a not previously handled space. (To be honest, for a few days, I've been thinking about implementing this as an alternative Core using the same Container wrapper.)

But, if I would have to choose from your options:

1. Noway. The whole regeneration would be faster, than this.
2. It could work. As I measured on a usual PC, If you have less than 500 objects on the new field, the Create() could fit in one frame (if the goal is 60fps). Maybe you could use QuadtreeBoxC and check everything in the top-plane view. If your objects have the same size, you could handle them as a point with the OctreePointC/QuadtreePointC, and the RangeSearch should be used with the size extended range.

I hope I could help.

[kriNon]

Hey, Thanks a lot for all the help! The video you linked really helped to point me in the right direction. It was easy to implement the sparse grid, and I was quickly able to get results that I was happy with. I think that in the end octrees weren't super well suited to my task, but it was a good learning experience for me.

I'm going to close up this issue. It was a nice experience using your library, and thanks for the support. Cheers