assertion failure in Impl::InsertIntoTree

[sthalik]

Having integrated your loose quadtree implementation into my game project early in development, I'm getting an off-by-one assertion failure during insertion.

This crash happens deterministically so I can provide additional details if you need them.

assertion failed: effective_bounds.Contains(object_bounds) in F:/dev/game/./compat/LooseQuadtree-impl.h:1114
(gdb) bt 5
#0  0x00007ff64c2fc032 in floormat::_fm_abort () at F:/dev/game/./compat/assert.hpp:32
#1  0x00007ff64c30b846 in loose_quadtree::LooseQuadtree<short, loose_quadtree::BoundingBox<short>, loose_quadtree::TrivialBBExtractor<short> >::Impl::InsertIntoTree (this=0x2a975dcf810, object=0x2a975e11380)
    at F:/dev/game/./compat/LooseQuadtree-impl.h:1114
#2  0x00007ff64c30a5d9 in loose_quadtree::LooseQuadtree<short, loose_quadtree::BoundingBox<short>, loose_quadtree::TrivialBBExtractor<short> >::Impl::Insert (this=0x2a975dcf810, object=0x2a975e11380)
    at F:/dev/game/./compat/LooseQuadtree-impl.h:824
#3  0x00007ff64c48f8af in loose_quadtree::LooseQuadtree<short, loose_quadtree::BoundingBox<short>, loose_quadtree::TrivialBBExtractor<short> >::Insert (this=0x2a975dcf810, object=0x2a975e11380)
    at F:/dev/game/./compat/LooseQuadtree-impl.h:1162
#4  0x00007ff64c48e007 in floormat::chunk::ensure_passability (this=0x2a975dd1fe8)
    at F:/dev/game/src/chunk-bbox.cpp:109
(More stack frames follow...)
(gdb) fr 1
#1  0x00007ff64c30b846 in loose_quadtree::LooseQuadtree<short, loose_quadtree::BoundingBox<short>, loose_quadtree::TrivialBBExtractor<short> >::Impl::InsertIntoTree (this=0x2a975dcf810, object=0x2a975e11380)
    at F:/dev/game/./compat/LooseQuadtree-impl.h:1114
1114            assert(effective_bounds.Contains(object_bounds));
(gdb) l
1109                (Number)((typename detail::MakeDistance<Number>::Type)effective_bounds.height / 2);
1110            effective_bounds.width = (Number)(effective_bounds.width * 2);
1111            effective_bounds.height = (Number)(effective_bounds.height * 2);
1112            effective_bounds.left = (Number)(effective_bounds.left - half_width);
1113            effective_bounds.top = (Number)(effective_bounds.top - half_height);
1114            assert(effective_bounds.Contains(object_bounds));
1115    #endif
1116
1117            typename detail::TreeNode<Object>::ObjectContainer& objects =
1118                    trav.GetNode()->objects;
(gdb) p effective_bounds
$1 = {left = 671, top = 353, width = 128, height = 126}
(gdb) p object_bounds
$2 = {left = 672, top = 352, width = 64, height = 64}

[gerazo]

@sthalik Thank you for reporting. I will look into it. What compiler are you using?
But first, are you aware of the closed-open interval logic? In order to have all calculations work the same way for both floating point and integral types, intervals and bounding boxes are inclusive from one side and exclusive from the other. So check first your assertion for containment. If it is just off by one, it may be just this.

[sthalik]

I'm using Clang 15, GCC 12.2 and MSVC 17.5 on Windows, and GCC 12.2 on Linux.

It works when either changing the internal data type to float or dividing as (x+1)/2. But in both cases there's another problem. When scrolling the box into the position that originally made it crash, iterating over all bounding boxes makes some of them not appear. There's an interval of Y values for that single bbox where that happens and recreating the tree after scrolling the Y beyond that point makes them appear again.

[gerazo]

You are right. It seems to be a bug. I suppose that the disappearance is caused by some boxes not registering to its rightful place and temporarily being lost in the tree. If it is only true for a region, I wonder what is special with that region. I see you use short coordinates. How far are you from the theoretical bounds of this type? Is there a change if you switch to int? As far as I remember, I tried to be careful that even internal calculations are promoted to int, results are always correctly written back to short. And it is also tested for that type... still it is worth a try.

[sthalik]

I've had difficulty finding the file that caused the crash. But here's the next best thing. Change the first one's height from 120 to 122 to make 736 287 64 66 disappear when queried as:

auto bb = lqt->GetLooseBoundingBox();
bb.left -= bb.width; bb.top -= bb.height;
bb.width *= 2; bb.height *= 2;
auto q = lqt->QueryInsideRegion(bb);

lrwh 398 322 100 120
lrwh 672 224 64 64
lrwh 672 288 64 64
lrwh 736 287 64 66
lrwh 672 352 64 64
lrwh 480 479 64 2
lrwh 479 480 2 64
lrwh 543 480 2 64
lrwh 224 543 64 2
lrwh 352 543 64 2
lrwh 416 528 64 32
lrwh 480 543 64 2
lrwh 608 544 64 64
lrwh 608 543 64 2
lrwh 672 528 64 32
lrwh 736 543 64 2