attcs / octree Goto Github PK

Octree/Quadtree/N-dimensional linear tree

License: MIT License

C++ 99.84% CMake 0.16%

bounding-box collision-detection cpp cpp20 geometry geometry-algorithms high-dimensional knearest-neighbors knn n-dimensions octree parallel quadtree range-search ray

octree's People

Contributors

Stargazers

Watchers

Forkers

jerrycxj kpwelsh jimbok8 gyh8 eokeeffe sammyramone marvin-hyk maybelaterornot messiyue lewec tonichedgehog

octree's Issues

During Insert wrong key calculated if child node should be attached

Simultaneous update for multiple entities

Missing Points in Container RangeSearch

I am using a simple custom version of your octree that is something like:

// Adaptor
using int3D = std::array<long int, 3>;
using CustomBoundingBox = std::array<int3D ,2>;
struct AdaptorBasicsCustom
{
	static inline long int& point_comp(int3D & pt, OrthoTree::dim_type iDimension)
	{
		return pt[iDimension];
	}

	static constexpr long int point_comp_c(int3D const& pt, OrthoTree::dim_type iDimension)
	{
		return pt[iDimension];
	}

	static inline int3D& box_min(CustomBoundingBox& box) { return box[0]; }
	static inline int3D& box_max(CustomBoundingBox& box) { return box[1]; }
	static constexpr int3D const& box_min_c(CustomBoundingBox const& box) { return box[0]; }
	static constexpr int3D const& box_max_c(CustomBoundingBox const& box) { return box[1]; }
};

using AdaptorCustom = OrthoTree::AdaptorGeneralBase<3, int3D, CustomBoundingBox, AdaptorBasicsCustom, long int>;


// Tailored Quadtree objects
using QuadtreePointCustom = OrthoTree::OrthoTreePoint<3, int3D, CustomBoundingBox, AdaptorCustom, long int>;
using QuadtreeContainerCustom = OrthoTree::OrthoTreeContainerPoint<QuadtreePointCustom, int3D>;

I have tried the RangeSearch function, but when I compare it to a simple slow method I use now it misses certain points. It happens on a octree with 423 points. I have not been able to reproduce the issue on a smaller problem.

However, I think the lines [1368-1374] might be an issue. Debugging the code I found that a nodeChild bounding box containing the missing point should have been giving a true statement for overlap with the range but it wasn't. Are these comparisons supposed to be strictly lesser than and strictly greater than? I think it will work if it is changed to <= or >=. I am a beginner when it comes to octtrees and the morton code indexing, so I am not sure if I am missing something.

        for (dim_type iDim = 0; iDim < nDimension && bOverlap; ++iDim)
        {
          if (IsValidKey(keyChild & (morton_node_id_type{ 1 } << iDim)))
            bOverlap &= AD::point_comp_c(AD::box_min_c(nodeChild.box), iDim) < AD::point_comp_c(AD::box_max_c(range), iDim);
          else
            bOverlap &= AD::point_comp_c(AD::box_max_c(nodeChild.box), iDim) > AD::point_comp_c(AD::box_min_c(range), iDim);
        }

glm adaptor

Strange behavior when inserting boxes into an empty tree

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>({});
+      }
+    };
 }```

Refactor: Additional adapter for `Ray` and `Plane`

Make `AdaptorBasics` interface more capable

Current interface fails to adapt many geometry libraries, which

are not handling bounding box corner points as point
has setter method for the points and box settings.

Alternative insert with advanced node management

Alternative Insert which is capable of rearranging entities of node into child node.

Refactor: Remove `snake-case` and `_type` from the `Tree` classes

PickSearch function can sometimes return duplicate ids

As the title says, that sometimes happen when queries are run using that function. It seems to be the case with last modification to it that was introduced in this commit 825f080, the implementation prior to that one seems to be stable

Cannot Install in Ubuntu 18

Hi,
I am not able to install and use the repository in ubuntu 18. Can you lay down the steps how I can use it and what other dependencies and libraries I need to install for the same.
One of the error I am getting while compiling is shown below.

jainsamarth@sjain:~/Downloads/Octree/build(master)$ make -j
[ 50%] Building CXX object CMakeFiles/MyExample.dir/test.cpp.o
In file included from /home/jainsamarth/Downloads/Octree/test.cpp:1:
In file included from /home/jainsamarth/Downloads/Octree/octree.h:43:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/execution:32:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/pstl/glue_execution_defs.h:50:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/pstl/algorithm_impl.h:22:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/pstl/parallel_backend.h:20:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/pstl/parallel_backend_tbb.h:19:
In file included from /home/jainsamarth/tbb/include/tbb/blocked_range.h:20:
In file included from /home/jainsamarth/tbb/include/tbb/tbb_stddef.h:452:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/memory:72:
/usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/align.h:96:16: error: no member named 'is_constant_evaluated' in namespace 'std'
      if (std::is_constant_evaluated())
          ~~~~~^
In file included from /home/jainsamarth/Downloads/Octree/test.cpp:1:
/home/jainsamarth/Downloads/Octree/octree.h:114:16: error: no member named 'span' in namespace 'std'
    using std::span;
          ~~~~~^
/home/jainsamarth/Downloads/Octree/octree.h:138:3: error: expected unqualified-id
  concept AdaptorBasicsConcept =
  ^
/home/jainsamarth/Downloads/Octree/octree.h:148:3: error: expected unqualified-id
  concept AdaptorConcept =
  ^
/home/jainsamarth/Downloads/Octree/octree.h:176:19: error: use of undeclared identifier 'AdaptorBasicsConcept'
    static_assert(AdaptorBasicsConcept<base, vector_type, box_type, geometry_type>);
                  ^
/home/jainsamarth/Downloads/Octree/octree.h:176:40: error: unexpected type name 'base': expected expression
    static_assert(AdaptorBasicsConcept<base, vector_type, box_type, geometry_type>);
                                       ^
/home/jainsamarth/Downloads/Octree/octree.h:314:35: error: no template named 'span'
    static box_type box_of_points(span<vector_type const> const& vPoint)
                                  ^
/home/jainsamarth/Downloads/Octree/octree.h:314:59: error: expected ')'
    static box_type box_of_points(span<vector_type const> const& vPoint)
                                                          ^
/home/jainsamarth/Downloads/Octree/octree.h:314:34: note: to match this '('
    static box_type box_of_points(span<vector_type const> const& vPoint)
                                 ^
/home/jainsamarth/Downloads/Octree/octree.h:330:34: error: no template named 'span'
    static box_type box_of_boxes(span<box_type const> const& vExtent)
                                 ^
/home/jainsamarth/Downloads/Octree/octree.h:330:55: error: expected ')'
    static box_type box_of_boxes(span<box_type const> const& vExtent)
                                                      ^
/home/jainsamarth/Downloads/Octree/octree.h:330:33: note: to match this '('
    static box_type box_of_boxes(span<box_type const> const& vExtent)
                                ^
/home/jainsamarth/Downloads/Octree/octree.h:317:24: error: use of undeclared identifier 'vPoint'
      for (autoc& pt : vPoint)
                       ^
/home/jainsamarth/Downloads/Octree/octree.h:333:23: error: use of undeclared identifier 'vExtent'
      for (autoc& e : vExtent)
                      ^
/home/jainsamarth/Downloads/Octree/octree.h:386:26: error: no member named 'ranges' in namespace 'std'
      autoc rMin = *std::ranges::max_element(aRMinMax[0]);
                    ~~~~~^
/home/jainsamarth/Downloads/Octree/octree.h:387:26: error: no member named 'ranges' in namespace 'std'
      autoc rMax = *std::ranges::min_element(aRMinMax[1]);
                    ~~~~~^
/home/jainsamarth/Downloads/Octree/octree.h:386:13: error: variables defined in a constexpr function must be initialized
      autoc rMin = *std::ranges::max_element(aRMinMax[0]);
            ^
/home/jainsamarth/Downloads/Octree/octree.h:544:20: error: no type named 'strong_ordering' in namespace 'std'
    using R = std::strong_ordering;
              ~~~~~^
/home/jainsamarth/Downloads/Octree/octree.h:547:26: error: use of undeclared identifier 'R'
        return lhs[id] ? R::greater : R::less;
                         ^
/home/jainsamarth/Downloads/Octree/octree.h:547:39: error: use of undeclared identifier 'R'
        return lhs[id] ? R::greater : R::less;
                                      ^
/home/jainsamarth/Downloads/Octree/octree.h:549:12: error: use of undeclared identifier 'R'
    return R::equal;
           ^
fatal error: too many errors emitted, stopping now [-ferror-limit=]
20 errors generated.
CMakeFiles/MyExample.dir/build.make:62: recipe for target 'CMakeFiles/MyExample.dir/test.cpp.o' failed
make[2]: *** [CMakeFiles/MyExample.dir/test.cpp.o] Error 1
CMakeFiles/Makefile2:67: recipe for target 'CMakeFiles/MyExample.dir/all' failed
make[1]: *** [CMakeFiles/MyExample.dir/all] Error 2
Makefile:83: recipe for target 'all' failed
make: *** [all] Error 2

Thanks

RangeSearch vs RayIntersectedAll inconsistency?

Hello,

thanks for this awesome library. I have used it to create a AABB octree and want to find aabbs that intersect with a ray (the ray always just goes downwards on y axis):

using OrthoBoundingBox3D = OrthoTree::BoundingBoxND<3, float>;
using OrthoOctree = OrthoTree::TreeBoxContainerND<3, 2, float>;
const float rayIntersectTolerance = 0.1f;

// TODO intersection function
[...] rayDownIntersected(const OrthoOctree& tree, const VEC3& pos, float searchSizeY)
{
    [...]
}

So,
I have first implemented this with RangeSearch like this:

auto searchBox = OrthoBoundingBox3D{
    { pos.x - rayIntersectTolerance, pos.y - searchSizeY, pos.z - rayIntersectTolerance },
    { pos.x + rayIntersectTolerance, pos.y,               pos.z + rayIntersectTolerance }
};

constexpr bool shouldFullyContain = false;
auto intersectedBoxes = tree.RangeSearch<shouldFullyContain>(searchBox);

And this seems to work just fine.

However, later i found out that RayIntersectedAll exists, which should make this easier (no need to create ray-like searchbox):

auto intersectedBoxes = tree.RayIntersectedAll({ pos.x, pos.y, pos.z }, { 0, -1, 0 }, rayIntersectTolerance, searchSizeY);

However, the second implementation finds much less intersected bboxes.
With the first impl, i find a total number of 38571 bboxes during loading, with the second i only get a total of 25094 bboxes.

When i use my ground truth implementation (quadratic looping, no trees used), i end up with 35131 bboxes, so some results are definitely missing when using RayIntersectedAll.

Summary (number of bboxes found):

//  tolerance: 0.1f
38571  (RangeSearch)
25094  (RayIntersectedAll)
35131  (Ground Truth)

My code is fully available here:
https://github.com/Katharsas/ZenRen/blob/6cdd6ebfdbfea042618a8ed44ea766fa07626339/ZenRen/src/renderer/loader/VertPosLookup.h
https://github.com/Katharsas/ZenRen/blob/6cdd6ebfdbfea042618a8ed44ea766fa07626339/ZenRen/src/renderer/loader/VertPosLookup.cpp

Do you know why there might be this high of a difference between the two functions?

Note: The ground truth implementation is a bit messed up in those commits, here is the fixed version:

Click me

inline bool rayDownIntersectsFaceBB(const VEC3& pos, const vector<VERTEX_POS>& verts, const size_t vertIndex, const float searchSizeY) {
    float minX = FLT_MAX, maxX = -FLT_MAX;
    float minY = FLT_MAX, maxY = -FLT_MAX;
    float minZ = FLT_MAX, maxZ = -FLT_MAX;

    for (uint32_t i = vertIndex; i < vertIndex + 3; i++) {
        const auto& vert = verts[i];
        minX = std::min(minX, vert.x);
        maxX = std::max(maxX, vert.x);
    }
    if (pos.x >= (maxX + rayIntersectTolerance) || pos.x <= (minX - rayIntersectTolerance)) return false;

    for (uint32_t i = vertIndex; i < vertIndex + 3; i++) {
        const auto& vert = verts[i];
        minZ = std::min(minZ, vert.z);
        maxZ = std::max(maxZ, vert.z);
    }
    if (pos.z >= (maxZ + rayIntersectTolerance) || pos.z <= (minZ - rayIntersectTolerance)) return false;

    for (uint32_t i = vertIndex; i < vertIndex + 3; i++) {
        const auto& vert = verts[i];
        minY = std::min(minY, vert.y);
        maxY = std::max(maxY, vert.y);
    }
    return !(pos.y >= (maxY + rayIntersectTolerance + searchSizeY) || pos.y >= (minY - rayIntersectTolerance));
}

Add GCC compiling action

Collision detection for Point solution

Cube/Spherical tolerance collision check for the point solution.

Space increasement of tree during Insert

Remove nodes in Erase()

KNN not finding the nearest neighbour with small K

As the title says, the KNN function does not return the nearest neighbour for me in many cases.

I noticed this when I created N number of random points and a random searchpoint, all within the boundaries of the octree.
Then I manually calculated each euclidean distance for the points to the search point.
The KNN function of the tree sometimes does not find the closest point.
How often the first value was wrong depended on a few parameters like K or the number of points I created.

It happened for every TreePoint (tested with Quadtree, Octree and TreePointND<6>).
The Quadtree needed more than 20 points to get the error, I am not sure if higher dimensional trees have the same or a higher threshold for points to get the error. I have mostly tested with 1000+ points for Octree and TreePointND<6>.

I have copied one of the many configurations below. It also includes some debug output.

I have included the specific points only to have a reproducible example, it is very easy to get the error with different points.
I mostly created random points, checked whether the tree found the correct answer or not, and repeated the test function with new random points. With some configurations 16% of the trees gave wrong results. Here I simply added points manually that I found through random generation.

double euclidean_distance(double x1, double y1, double x2, double y2)
{
    return sqrt(pow(x2- x1, 2) + pow(y2 - y1, 2));
}

void test_setup()
{
    array<double, 2> point0 = {78.2619, 77.843};
    array<double, 2> point1 = {90.3005, 90.5172};
    array<double, 2> point2 = {69.8652, 12.2467};
    array<double, 2> point3 = {48.4675, 48.4948};
    array<double, 2> point4 = {36.3226, 68.4619};
    array<double, 2> point5 = {98.8799, 42.7149};
    array<double, 2> point6 = {31.412, 38.6866};
    array<double, 2> point7 = {63.2748, 77.0524};
    array<double, 2> point8 = {62.8844, 17.0536};
    array<double, 2> point9 = {80.8931, 39.8099};
    array<double, 2> point10 = {77.426, 64.9844};
    array<double, 2> point11 = {81.9552, 25.009};
    array<double, 2> point12 = {87.6088, 51.319};
    array<double, 2> point13 = {78.5609, 80.4623};
    array<double, 2> point14 = {51.3967, 39.5269};
    array<double, 2> point15 = {32.2042, 81.8779};
    array<double, 2> point16 = {79.1739, 81.5467};
    array<double, 2> point17 = {95.2619, 40.4742};
    array<double, 2> point18 = {86.437, 92.4406};
    array<double, 2> point19 = {3.95388, 60.2327};
    array<double, 2> point20 = {31.1283, 44.4917};
    array<double, 2> point21 = {35.6778, 79.8545};
    array<double, 2> point22 = {50.9926, 66.1373};
    array<double, 2> point23 = {3.16271, 65.2519};
    array<double, 2> point24 = {56.3665, 45.3819};

    vector<array<double, 2>> poses = {
        point0,
        point1,
        point2,
        point3,
        point4,
        point5,
        point6,
        point7,
        point8,
        point9,
        point10,
        point11,
        point12,
        point13,
        point14,
        point15,
        point16,
        point17,
        point18,
        point19,
        point20,
        point21,
        point22,
        point23,
        point24,
        };

    array<double, 2> search_point = {43.6406, 57.5691};

    auto start = std::chrono::high_resolution_clock::now();
    vector<std::pair<double,int>> results;
    double distance = 10000.0;
    int winner_id;
    for (size_t i = 0; i < poses.size(); i++)
    {
        array<double, 2> pose = poses[i];
        double tranlation_distance = euclidean_distance(search_point[0], search_point[1], pose[0], pose[1]);

        if (tranlation_distance < distance)
        {
            distance = tranlation_distance;
            winner_id = i;
        }
    }


    std::array<double, 2> inspection_space_min = {0.0, 0.0};
    std::array<double, 2> inspection_space_max = {100.0, 100.0};
    OrthoTree::BoundingBox2D inspection_space;
    inspection_space.Min = inspection_space_min;
    inspection_space.Max = inspection_space_max;
    //Standard Tree
    auto tree = QuadtreePointC(poses, 9, inspection_space);

    auto neighbors = tree.GetNearestNeighbors(search_point, 1);

    if (neighbors[0] != winner_id)
    {
        std::cout << "Winner ID is: " << winner_id << " with distance: " << euclidean_distance(search_point[0], search_point[1], poses[winner_id][0], poses[winner_id][1]) << std::endl;
        std::cout << "Tree found ID: " << neighbors[0] << " with distance: " << euclidean_distance(search_point[0], search_point[1], poses[neighbors[0]][0], poses[neighbors[0]][1]) << std::endl;

        std::cout << "Search Point with coordinates:  X: " << search_point[0]<< " Y: " << search_point[1] << std::endl;
        for (size_t i = 0; i < poses.size(); i++)
        {
            std::cout<<"ID is: "<< i << " Point with coordinates:  X: " << poses[i][0]<< ", " << poses[i][1] << "  With Distance "<< euclidean_distance(search_point[0], search_point[1], poses[i][0], poses[i][1]) << std::endl;

        }
    }
}

int main()
{
   test_setup();
}

Here the tree returns ID 22, which has a distance of 11.2901 to the search point, although the winner should be ID 3 with a distance of 10.2782.
I did a lot of testing to maybe find the bug myself, here are some interesting things I found:

The depth of the tree has no effect.
A "big" K solves the problem. Big" depends on how many numbers are in the tree. I have not yet seen a pattern of how big it needs to be. This is the most interesting to me, because the K should only affect how many neighbours are returned, it should not affect whether the winner is found.
Wrong results only occur if a certain "break;" is triggered in the KNN function.
https://github.com/attcs/Octree/blob/master/octree.h#L1845

      if (!setNodeDist.empty())
      {
        auto rLatestNodeDist = std::begin(setNodeDist)->distance;
        for (autoc& nodeDist : setNodeDist)
        {
          autoc n = setEntity.size();
          if (k <= n && rLatestNodeDist < nodeDist.distance)
            break;

          createEntityDistance(nodeDist.node, pt, vpt, setEntity);
          rLatestNodeDist = nodeDist.distance;

I think this is somehow triggered too early, at a stage where the smallest distance is not yet inside setEntity. Here a bigger K would also make the code go in there at a later stage, which is probably why the bigger K sometimes fixes things.

I am not sure what the if function is for and why the distances we are comparing are distances to the wall. I am a bit out of my depth here and need help debugging this.

Im also not sure why this has not happened to anyone else or why it was not found by the unit test. Maybe because the unit tests dont have enough points in the tree, but thats just a guess because as I said I needed more than 20 for Quadtree and probably more for higher dimensional trees.

Picksearch sometimes misses things

Hello, awesome library you got here :)

I was using it in a small experiment where I used the container version of it and built it with bounding boxes that form a 3D grid of a specific cell size, so all bounding boxes are the same length basically. I also changed the geometry type of all the structures needed to integer instead of double. Using the PickSearch function with a specific 3D point, it sometimes fails to find points that are for sure contained within one of those bounding boxes that the tree was built with, so I was wondering if this is a similar boundary check problem like in the range search problem that was mentioned in another issue?

CGAL adaptor

Frustum culling

Plane-Object orientation by plane normal
Check for multiple planes

Help Request

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.

boost/geometry adapter

Optional node Bounding boxes

Nodes' bounding boxes could be omitted in some use cases, and/or in-place calculated. Removing bounding boxes could

highly reduce the memory footprint
slightly (speculative) increase CPU usage at the searches
highly (speculative) reduce CPU usage at the creation

Suggestion: a DEFINE or a new template parameter to make it optionally set by the client code

Abstract class as point

Hello,

How can we use an abstract class as a point?

This is our block class :

class Block
{
public:
    float x{}, y{}, z{};
    virtual ~Block() = default;
    virtual void addFace(int) = 0;
    virtual void removeFace(int) = 0;
    virtual glm::vec3 getCoords() = 0;
    virtual void setupMesh() = 0;
    virtual void draw(Program&) = 0;
};

I want my custom point to be block pointer,
and i believe you are default constructing the point type in the octree. which would not work with the point type that im trying to use.

Thank you for the awesome source code, and help.

a lot of small vector allocations could be spared
more cache-friendly.