Assertion failure in RTree::choosePartition

[JosiahWI]

#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
#1  0x00007ffff721c537 in __GI_abort () at abort.c:79
#2  0x00007ffff721c40f in __assert_fail_base (fmt=0x7ffff7393688 "%s%s%s:%u: %s%sAssertion `%s' failed.\n%n", 
    assertion=0x555555f3e9c8 "(partitionVars.count[0] >= partitionVars.minFill()) && (partitionVars.count[1] >= partitionVars.minFill())", 
    file=0x555555f3aee8 "../lib/THST/RTree.h", line=1178, function=<optimized out>) at assert.c:92
#3  0x00007ffff722b662 in __GI___assert_fail (
    assertion=0x555555f3e9c8 "(partitionVars.count[0] >= partitionVars.minFill()) && (partitionVars.count[1] >= partitionVars.minFill())", 
    file=0x555555f3aee8 "../lib/THST/RTree.h", line=1178, 
    function=0x555555f3e6c8 "void spatial::RTree<T, ValueType, Dimension, max_child_items, min_child_items, indexable_getter, bbox_volume_mode, RealType, custom_allocator>::choosePartition(spatial::RTree<T, ValueType, Dimension, "...) at assert.c:101
#4  0x0000555555ae0e8b in spatial::RTree<float, sp_util::TaggedBBox<unsigned short>, 3, 4, 3, sp_util::TaggedBBoxIndexable<unsigned short>, 0, float, spatial::allocator<spatial::detail::Node<sp_util::TaggedBBox<unsigned short>, spatial::BoundingBox<float, 3>, 4> > >::choosePartition
    (this=0x555557aecec0, partitionVars=...) at ../lib/THST/RTree.h:1178
#5  0x0000555555ae0154 in spatial::RTree<float, sp_util::TaggedBBox<unsigned short>, 3, 4, 3, sp_util::TaggedBBoxIndexable<unsigned short>, 0, float, spatial::allocator<spatial::detail::Node<sp_util::TaggedBBox<unsigned short>, spatial::BoundingBox<float, 3>, 4> > >::splitNode (
    this=0x555557aecec0, node=..., branch=..., newNodePtr=0x7fffcbffabc8) at ../lib/THST/RTree.h:1063
#6  0x0000555555adf286 in spatial::RTree<float, sp_util::TaggedBBox<unsigned short>, 3, 4, 3, sp_util::TaggedBBoxIndexable<unsigned short>, 0, float, spatial::allocator<spatial::detail::Node<sp_util::TaggedBBox<unsigned short>, spatial::BoundingBox<float, 3>, 4> > >::addBranch (
    this=0x555557aecec0, branch=..., node=..., newNode=0x7fffcbffabc8) at ../lib/THST/RTree.h:1004
#7  0x0000555555adf1ea in spatial::RTree<float, sp_util::TaggedBBox<unsigned short>, 3, 4, 3, sp_util::TaggedBBoxIndexable<unsigned short>, 0, float, spatial::allocator<spatial::detail::Node<sp_util::TaggedBBox<unsigned short>, spatial::BoundingBox<float, 3>, 4> > >::insertRec<spatial::detail::DummyInsertPredicate> (this=0x555557aecec0, branch=..., predicate=..., node=..., newNode=@0x7fffcbffabc8: 0x0, 
    added=@0x7fffcbffabc7: true, level=0) at ../lib/THST/RTree.h:924
#8  0x0000555555ade213 in spatial::RTree<float, sp_util::TaggedBBox<unsigned short>, 3, 4, 3, sp_util::TaggedBBoxIndexable<unsigned short>, 0, float, spatial::allocator<spatial::detail::Node<sp_util::TaggedBBox<unsigned short>, spatial::BoundingBox<float, 3>, 4> > >::insertImpl<spatial::detail::DummyInsertPredicate> (this=0x555557aecec0, branch=..., predicate=..., level=0) at ../lib/THST/RTree.h:954
#9  0x0000555555aee164 in spatial::RTree<float, sp_util::TaggedBBox<unsigned short>, 3, 4, 3, sp_util::TaggedBBoxIndexable<unsigned short>, 0, float, spatial::allocator<spatial::detail::Node<sp_util::TaggedBBox<unsigned short>, spatial::BoundingBox<float, 3>, 4> > >::insert (
    this=0x555557aecec0, value=...) at ../lib/THST/RTree.h:574
#10 0x0000555555aede67 in SpatialStore<irr::core::aabbox3d<float>, unsigned short>::insert (this=0x555557aeceb8, id=4, space=...)
    at ../src/server/../util/spatialstore.h:73
#11 0x0000555555aed22c in ServerActiveObject::addedToEnvironment (this=0x7fffbc328310, dtime_s=0) at ../src/server/serveractiveobject.cpp:41
#12 0x0000555555ae2369 in LuaEntitySAO::addedToEnvironment (this=0x7fffbc328310, dtime_s=0) at ../src/server/luaentity_sao.cpp:101
#13 0x0000555555cfd225 in ServerEnvironment::addActiveObjectRaw (this=0x555557aecc30, object=0x7fffbc328310, set_changed=true, dtime_s=0)
    at ../src/serverenvironment.cpp:1843
#14 0x0000555555cfc8fb in ServerEnvironment::addActiveObject (this=0x555557aecc30, object=0x7fffbc328310)
    at ../src/serverenvironment.cpp:1682
#15 0x0000555555a87662 in ModApiEnv::l_add_entity (L=0x40000378) at ../src/script/lua_api/l_env.cpp:615
#16 0x0000555555a4a892 in script_exception_wrapper (L=0x40000378, f=0x555555a874b0 <ModApiEnv::l_add_entity(lua_State*)>)
    at ../src/script/common/c_internal.cpp:41
#17 0x00007ffff7ce5647 in ?? () from /lib/x86_64-linux-gnu/libluajit-5.1.so.2
#18 0x00007ffff7d3978f in lua_pcall () from /lib/x86_64-linux-gnu/libluajit-5.1.so.2

If no one beats me to it, I will attempt to write a unit test that reproduces the issue.

[JosiahWI]

I reproduced the failure, and @appgurueu was able to identify it as caused by the tree parameters. I created the tree with a minimum child size of 3 and a maximum child size of 4. On the 5th insertion, the tree will split, and one partition will be underfilled. I will try to clean up the test case to be minimal and add it here later.

[JosiahWI]

TEST_CASE("regression test") {
	typedef spatial::RTree<int, Box2<int>, 2, 4, 3> rtree_box_t;
	rtree_box_t rtree;
	Box2<int> box{{-3, 0}, {3, 17}};
	rtree.insert(box);
	rtree.insert(box);
	rtree.insert(box);
	rtree.insert(box);
	rtree.insert(box);
}```

[tuxalin]

Thanks, will test that out.