attcs / octree Goto Github PK
View Code? Open in Web Editor NEWOctree/Quadtree/N-dimensional linear tree
License: MIT License
Octree/Quadtree/N-dimensional linear tree
License: MIT License
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.
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);
}
Nodes' bounding boxes could be omitted in some use cases, and/or in-place calculated. Removing bounding boxes could
Suggestion: a DEFINE or a new template parameter to make it optionally set by the client code
Do not insert an entity if it is colliding with another one.
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.
Cube/Spherical tolerance collision check for the point solution.
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.
Current interface fails to adapt many geometry libraries, which
point
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?
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
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>({});
+ }
+ };
}```
If the geometry is static, node-wise containment unnecessary, entity ID-s could be stored directly in the tree.
With this change,
Alternative Insert which is capable of rearranging entities of node into child node.
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:
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));
}
Since the library uses only size()
, operator[]
to access point/box for an entity, it would be better to provide an accessor callback that only needs to implements those 2 operations rather than requiring the use of std::span
.
This will be very useful for ecs libraries where they use their own storage techniques.
Hello,
I found by chance this repo, and would like to compare the quality of the resulting meshes to snappyHexMesh results, which takes as input a surface mesh (for the geometry) and a background mesh, in the examples in the unit test, I didn't saw anything similar, is this a possible workflow of this code?
thanks in advance
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
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.