RangeSearch vs RayIntersectedAll inconsistency?

[Katharsas]

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

```cpp inline bool rayDownIntersectsFaceBB(const VEC3& pos, const vector& 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)); } ```

[Katharsas]

Interestingly, when i reduce the rayIntersectTolerance from 0.1f to 0.001f, the numbers become:

//  tolerance: 0.001f
35909 (RangeSearch)
25348 (RayIntersectedAll)
33002 (Ground Truth)

So the tolerance is handled differently in RayIntersectedAll vs my own searchBox, but compared to ground truth RayIntersectedAll does not find all the boxes it should find.

When i make the tolerance so small things seem to get crazy:

//  tolerance: 0.00001f
13957 (RangeSearch)
25601 (RayIntersectedAll)
32981 (Ground Truth)

This just seems completely wrong (broken) in the case of RangeSearch and still wrong (not enough) in the case of RayIntersectedAll.

Upping the tolerance a little bit and we get this:

//  tolerance: 0.0001f
35868 (RangeSearch)
25532 (RayIntersectedAll)
32981 (Ground Truth)

RangeSearch is not broken anymore. All in all there seems to be some really weird stuff going on.

Edit: What is also very interesting to me is that the number of intersected bboxes increases for RayIntersectedAll with smaller tolerance values.

[attcs]

Thank you for reporting this issue! I am currently investigating it, but I haven't found any obvious error by code reading yet. Could you give the box of the search range and dump out the boxes in a text file? It would be a great help!

[Katharsas]

Sure, output created with this line: LOG(DEBUG) << "min: { " << bb.Min[0] << ", " << bb.Min[1] << ", " << bb.Min[2] << " }, max: { " << bb.Max[0] << ", " << bb.Max[1] << ", " << bb.Max[2] << " }";

Output: bbox_output.txt

[attcs]

Hi! Thank you for the input file! I found a bug with the tolerances in the IsRayHit(). I hope it will solve all of your issues, but to make sure and to reproduce your numbers exactly, could you send me the exact search box and the origin point of the ray?

[Katharsas]

The numbers in my initial posts are accumulated result counts from multiple calls (7221 calls to be exact) to rayDownIntersected:

• searchSizeY is always exactly 100 (function call line: vertKeys = rayDownIntersectedNaive(meshData, pos3, 100);).
• tree is not changed in between calls
• pos is different on every call

Here is a list of all pos values used: pos_input.txt

[Katharsas]

The problem seems to be fixed in the newest version!

//  tolerance: 0.0001f
35868  (RangeSearch)
35884  (RayIntersectedAll)

//  tolerance: 0.01f
36150  (RangeSearch)
36195  (RayIntersectedAll)

This looks very good to me, thanks for your awesome work!

[attcs]

Thank you for the input file! The conclusion: the inclusive tolerance handling (allowing equality) does not conform with the range search, because the adjacent bounding boxes will be found with the ray search. Overall, I replaced it with exclusive handling (not allowed eq), and I could reproduce exactly the same result with the three approaches. Side note: Ray intersection uses cubic tolerance zone around the origin point (not spherical!), and also for the hit points (not perpendicular to the ray direction!) for better performance. But it perfectly conforms with axis-aligned box searches.

Again, thank you for the bug report and input files, it was a great help!