search

attcs / Octree

Octree/Quadtree/N-dimensional linear tree
MIT License
113 stars 13 forks source link

PickSearch function can sometimes return duplicate ids #8

Closed RoboticHuman closed 10 months ago

RoboticHuman commented 12 months ago

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

attcs commented 11 months ago

Hi! I am back from the holiday!

However, I could not reproduce the issue (code review/debug/unit tests/randomly generated pick points-box). Could you give me some clues? The ideal would be the octree ctor params, list of boxes, pick point.

Thank you for the report and the help!

sbonnalc commented 11 months ago

Hi, I'm working with RoboticHuman, and manage to reproduce the problem: Here are some information that might help you:

    static constexpr int mGridDimensions{ 3 };

    using OctreePointType = OrthoTree::PointND<mGridDimensions, int64_t>;
    struct CustomBoundingBox : OrthoTree::BoundingBoxND<mGridDimensions, int64_t>
    {
        explicit CustomBoundingBox(const OctreePointType& Min, const OctreePointType& Max)
            : OrthoTree::BoundingBoxND<mGridDimensions, int64_t>(Min, Max)
        {}
        CustomBoundingBox(const CustomBoundingBox& other) = default;
        CustomBoundingBox& operator=(const CustomBoundingBox& other) = default;
        CustomBoundingBox() = default;
        CustomBoundingBox(CustomBoundingBox&& other) noexcept
            : OrthoTree::BoundingBoxND<mGridDimensions, int64_t>(std::move(other.Min), std::move(other.Max))
            , mBoundingBoxContent(std::move(other.mBoundingBoxContent))
        {}
        CustomBoundingBox& operator=(CustomBoundingBox&& other) noexcept
        {
            this->Min = std::move(other.Min);
            this->Max = std::move(other.Max);
            mBoundingBoxContent = std::move(other.mBoundingBoxContent);
            return *this;
        }

        mutable robin_hood::unordered_flat_map<K, V> mBoundingBoxContent;
    };
    using OctreeBoundingBoxType = CustomBoundingBox;
    using OctreeType = OrthoTree::OrthoTreeBoundingBox<mGridDimensions, OctreePointType, OctreeBoundingBoxType, OrthoTree::AdaptorGeneral<mGridDimensions, OctreePointType, OctreeBoundingBoxType, int64_t>, int64_t, 2>;
    using OctreeTypeContainer = OrthoTree::OrthoTreeContainerBox<OctreeType, OctreeBoundingBoxType>;

        std::vector<OctreeBoundingBoxType> mGridCells;
        OctreeType mOctree;

        OctreeType::template Create<std::execution::parallel_unsequenced_policy>(mOctree, mGridCells);

        const auto ids = mOctree.PickSearch(OctreePointType{-864, 0, 447}, mGridCells);

with: mGridCells[0]: Min[-1024, 0, 0], Max[-961, 0, 63] mGridCells[1]: Min[-1024, 0, 64], Max[-961, 0, 127] mGridCells[2]: Min[-1024, 0, 128], Max[-961, 0, 191] mGridCells[3]: Min[-1024, 0, 192], Max[-961, 0, 255] mGridCells[4]: Min[-1024, 0, 256], Max[-961, 0, 319] mGridCells[5]: Min[-1024, 0, 320], Max[-961, 0, 383] mGridCells[6]: Min[-1024, 0, 384], Max[-961, 0, 447] mGridCells[7]: Min[-1024, 0, 448], Max[-961, 0, 511] mGridCells[8]: Min[-960, 0, 0], Max[-897, 0, 63] mGridCells[9]: Min[-960, 0, 64], Max[-897, 0, 127] mGridCells[10]: Min[-960, 0, 128], Max[-897, 0, 191] mGridCells[11]: Min[-960, 0, 192], Max[-897, 0, 255] mGridCells[12]: Min[-960, 0, 256], Max[-897, 0, 319] mGridCells[13]: Min[-960, 0, 320], Max[-897, 0, 383] mGridCells[14]: Min[-960, 0, 384], Max[-897, 0, 447] mGridCells[15]: Min[-960, 0, 448], Max[-897, 0, 511] mGridCells[16]: Min[-896, 0, 0], Max[-833, 0, 63] mGridCells[17]: Min[-896, 0, 64], Max[-833, 0, 127] mGridCells[18]: Min[-896, 0, 128], Max[-833, 0, 191] mGridCells[19]: Min[-896, 0, 192], Max[-833, 0, 255] mGridCells[20]: Min[-896, 0, 256], Max[-833, 0, 319] mGridCells[21]: Min[-896, 0, 320], Max[-833, 0, 383] mGridCells[22]: Min[-896, 0, 384], Max[-833, 0, 447] mGridCells[23]: Min[-896, 0, 448], Max[-833, 0, 511] mGridCells[24]: Min[-832, 0, 0], Max[-769, 0, 63] mGridCells[25]: Min[-832, 0, 64], Max[-769, 0, 127] mGridCells[26]: Min[-832, 0, 128], Max[-769, 0, 191] mGridCells[27]: Min[-832, 0, 192], Max[-769, 0, 255] mGridCells[28]: Min[-832, 0, 256], Max[-769, 0, 319] mGridCells[29]: Min[-832, 0, 320], Max[-769, 0, 383] mGridCells[30]: Min[-832, 0, 384], Max[-769, 0, 447] mGridCells[31]: Min[-832, 0, 448], Max[-769, 0, 511] mGridCells[32]: Min[-768, 0, 0], Max[-705, 0, 63] mGridCells[33]: Min[-768, 0, 64], Max[-705, 0, 127] mGridCells[34]: Min[-768, 0, 128], Max[-705, 0, 191] mGridCells[35]: Min[-768, 0, 192], Max[-705, 0, 255] mGridCells[36]: Min[-768, 0, 256], Max[-705, 0, 319] mGridCells[37]: Min[-768, 0, 320], Max[-705, 0, 383] mGridCells[38]: Min[-768, 0, 384], Max[-705, 0, 447] mGridCells[39]: Min[-768, 0, 448], Max[-705, 0, 511] mGridCells[40]: Min[-704, 0, 0], Max[-641, 0, 63] mGridCells[41]: Min[-704, 0, 64], Max[-641, 0, 127] mGridCells[42]: Min[-704, 0, 128], Max[-641, 0, 191] mGridCells[43]: Min[-704, 0, 192], Max[-641, 0, 255] mGridCells[44]: Min[-704, 0, 256], Max[-641, 0, 319] mGridCells[45]: Min[-704, 0, 320], Max[-641, 0, 383] mGridCells[46]: Min[-704, 0, 384], Max[-641, 0, 447] mGridCells[47]: Min[-704, 0, 448], Max[-641, 0, 511] mGridCells[48]: Min[-640, 0, 0], Max[-577, 0, 63] mGridCells[49]: Min[-640, 0, 64], Max[-577, 0, 127] mGridCells[50]: Min[-640, 0, 128], Max[-577, 0, 191] mGridCells[51]: Min[-640, 0, 192], Max[-577, 0, 255] mGridCells[52]: Min[-640, 0, 256], Max[-577, 0, 319] mGridCells[53]: Min[-640, 0, 320], Max[-577, 0, 383] mGridCells[54]: Min[-640, 0, 384], Max[-577, 0, 447] mGridCells[55]: Min[-640, 0, 448], Max[-577, 0, 511] mGridCells[56]: Min[-576, 0, 0], Max[-513, 0, 63] mGridCells[57]: Min[-576, 0, 64], Max[-513, 0, 127] mGridCells[58]: Min[-576, 0, 128], Max[-513, 0, 191] mGridCells[59]: Min[-576, 0, 192], Max[-513, 0, 255] mGridCells[60]: Min[-576, 0, 256], Max[-513, 0, 319] mGridCells[61]: Min[-576, 0, 320], Max[-513, 0, 383] mGridCells[62]: Min[-576, 0, 384], Max[-513, 0, 447] mGridCells[63]: Min[-576, 0, 448], Max[-513, 0, 511] mGridCells[64]: Min[-1152, 0, -128], Max[-1089, 0, -65] mGridCells[65]: Min[-1152, 0, -64], Max[-1089, 0, -1] mGridCells[66]: Min[-1152, 0, 0], Max[-1089, 0, 63] mGridCells[67]: Min[-1152, 0, 64], Max[-1089, 0, 127] mGridCells[68]: Min[-1152, 0, 128], Max[-1089, 0, 191] mGridCells[69]: Min[-1152, 0, 192], Max[-1089, 0, 255] mGridCells[70]: Min[-1152, 0, 256], Max[-1089, 0, 319] mGridCells[71]: Min[-1152, 0, 320], Max[-1089, 0, 383] mGridCells[72]: Min[-1152, 0, 384], Max[-1089, 0, 447] mGridCells[73]: Min[-1152, 0, 448], Max[-1089, 0, 511] mGridCells[74]: Min[-1152, 0, 512], Max[-1089, 0, 575] mGridCells[75]: Min[-1152, 0, 576], Max[-1089, 0, 639] mGridCells[76]: Min[-1088, 0, -128], Max[-1025, 0, -65] mGridCells[77]: Min[-1088, 0, -64], Max[-1025, 0, -1] mGridCells[78]: Min[-1088, 0, 0], Max[-1025, 0, 63] mGridCells[79]: Min[-1088, 0, 64], Max[-1025, 0, 127] mGridCells[80]: Min[-1088, 0, 128], Max[-1025, 0, 191] mGridCells[81]: Min[-1088, 0, 192], Max[-1025, 0, 255] mGridCells[82]: Min[-1088, 0, 256], Max[-1025, 0, 319] mGridCells[83]: Min[-1088, 0, 320], Max[-1025, 0, 383] mGridCells[84]: Min[-1088, 0, 384], Max[-1025, 0, 447] mGridCells[85]: Min[-1088, 0, 448], Max[-1025, 0, 511] mGridCells[86]: Min[-1088, 0, 512], Max[-1025, 0, 575] mGridCells[87]: Min[-1088, 0, 576], Max[-1025, 0, 639] mGridCells[88]: Min[-512, 0, -128], Max[-449, 0, -65] mGridCells[89]: Min[-512, 0, -64], Max[-449, 0, -1] mGridCells[90]: Min[-512, 0, 0], Max[-449, 0, 63] mGridCells[91]: Min[-512, 0, 64], Max[-449, 0, 127] mGridCells[92]: Min[-512, 0, 128], Max[-449, 0, 191] mGridCells[93]: Min[-512, 0, 192], Max[-449, 0, 255] mGridCells[94]: Min[-512, 0, 256], Max[-449, 0, 319] mGridCells[95]: Min[-512, 0, 320], Max[-449, 0, 383] mGridCells[96]: Min[-512, 0, 384], Max[-449, 0, 447] mGridCells[97]: Min[-512, 0, 448], Max[-449, 0, 511] mGridCells[98]: Min[-512, 0, 512], Max[-449, 0, 575] mGridCells[99]: Min[-512, 0, 576], Max[-449, 0, 639] mGridCells[100]: Min[-448, 0, -128], Max[-385, 0, -65] mGridCells[101]: Min[-448, 0, -64], Max[-385, 0, -1] mGridCells[102]: Min[-448, 0, 0], Max[-385, 0, 63] mGridCells[103]: Min[-448, 0, 64], Max[-385, 0, 127] mGridCells[104]: Min[-448, 0, 128], Max[-385, 0, 191] mGridCells[105]: Min[-448, 0, 192], Max[-385, 0, 255] mGridCells[106]: Min[-448, 0, 256], Max[-385, 0, 319] mGridCells[107]: Min[-448, 0, 320], Max[-385, 0, 383] mGridCells[108]: Min[-448, 0, 384], Max[-385, 0, 447] mGridCells[109]: Min[-448, 0, 448], Max[-385, 0, 511] mGridCells[110]: Min[-448, 0, 512], Max[-385, 0, 575] mGridCells[111]: Min[-448, 0, 576], Max[-385, 0, 639] mGridCells[112]: Min[-1024, 0, -128], Max[-961, 0, -65] mGridCells[113]: Min[-1024, 0, -64], Max[-961, 0, -1] mGridCells[114]: Min[-960, 0, -128], Max[-897, 0, -65] mGridCells[115]: Min[-960, 0, -64], Max[-897, 0, -1] mGridCells[116]: Min[-896, 0, -128], Max[-833, 0, -65] mGridCells[117]: Min[-896, 0, -64], Max[-833, 0, -1] mGridCells[118]: Min[-832, 0, -128], Max[-769, 0, -65] mGridCells[119]: Min[-832, 0, -64], Max[-769, 0, -1] mGridCells[120]: Min[-768, 0, -128], Max[-705, 0, -65] mGridCells[121]: Min[-768, 0, -64], Max[-705, 0, -1] mGridCells[122]: Min[-704, 0, -128], Max[-641, 0, -65] mGridCells[123]: Min[-704, 0, -64], Max[-641, 0, -1] mGridCells[124]: Min[-640, 0, -128], Max[-577, 0, -65] mGridCells[125]: Min[-640, 0, -64], Max[-577, 0, -1] mGridCells[126]: Min[-576, 0, -128], Max[-513, 0, -65] mGridCells[127]: Min[-576, 0, -64], Max[-513, 0, -1] mGridCells[128]: Min[-1024, 0, 512], Max[-961, 0, 575] mGridCells[129]: Min[-1024, 0, 576], Max[-961, 0, 639] mGridCells[130]: Min[-960, 0, 512], Max[-897, 0, 575] mGridCells[131]: Min[-960, 0, 576], Max[-897, 0, 639] mGridCells[132]: Min[-896, 0, 512], Max[-833, 0, 575] mGridCells[133]: Min[-896, 0, 576], Max[-833, 0, 639] mGridCells[134]: Min[-832, 0, 512], Max[-769, 0, 575] mGridCells[135]: Min[-832, 0, 576], Max[-769, 0, 639] mGridCells[136]: Min[-768, 0, 512], Max[-705, 0, 575] mGridCells[137]: Min[-768, 0, 576], Max[-705, 0, 639] mGridCells[138]: Min[-704, 0, 512], Max[-641, 0, 575] mGridCells[139]: Min[-704, 0, 576], Max[-641, 0, 639] mGridCells[140]: Min[-640, 0, 512], Max[-577, 0, 575] mGridCells[141]: Min[-640, 0, 576], Max[-577, 0, 639] mGridCells[142]: Min[-576, 0, 512], Max[-513, 0, 575] mGridCells[143]: Min[-576, 0, 576], Max[-513, 0, 639]

result: ids[0]=22 ids[1]=22

I can get the debugger on the PickSearch function. So, if you don't reproduce it, I can provide more info if necessary. another point that could be important, is that mOctree was Reset(), and Created again at least 3-4 times.

sbonnalc commented 11 months ago

In this stack: in the pickSearch(...) function, I can see the Node structure:

point: {-864, 0, 1471}

Node: {-1152, 0, 831} - {-576, 0, 1663}

vid: 3, 11, 19, 27, 35, 43, 51, 69, 81

96: {-1152, 0, 831} - {-864, 0, 1247}

vid: 0,1,2,8,9,10,16,17,18,64,65,66,67,68,76,77,78,79,80,112,113,114,115,116,117 no child

97: {-864, 0, 831} - {-576, 0, 1247}

vid: 16,17,18,24,25,26,32,33,34,40,41,42,48,49,50,116,117,118,119,120,121,122,123,124,125 no child

100: {-1152, 0, 1247} - {-864, 0, 1663}

vid: 4,5,6,7,12,13,14,15,20,21,22,23,70,71,72,73,74,75,82,83,84,85,86,87,128,129,130,131,132,133 no child

101: {-864, 0, 1247} - {-576, 0, 1663}

vid: 20,21,22,23,28,29,30,31,36,37,38,39,44,45,46,47,52,53,54,55,132,133,134,135,136,137,138,139,140,141 no child

Child leaf nodes Boxes overlapp on the edge. The vBox is not aligned to those leaf boxes. So a vBox can span on several leaf nodes. And so, it is added twice in the result. In our case vBox[22] is part of leaf nodes 100 and 101. vBox[22] = {-896, 0, 1408} - {-833, 0, 1471}

Here is the mGridCells, associated to this comment: mGridCells[0]: Min[-1024, 0, 1024], Max[-961, 0, 1087] mGridCells[1]: Min[-1024, 0, 1088], Max[-961, 0, 1151] mGridCells[2]: Min[-1024, 0, 1152], Max[-961, 0, 1215] mGridCells[3]: Min[-1024, 0, 1216], Max[-961, 0, 1279] mGridCells[4]: Min[-1024, 0, 1280], Max[-961, 0, 1343] mGridCells[5]: Min[-1024, 0, 1344], Max[-961, 0, 1407] mGridCells[6]: Min[-1024, 0, 1408], Max[-961, 0, 1471] mGridCells[7]: Min[-1024, 0, 1472], Max[-961, 0, 1535] mGridCells[8]: Min[-960, 0, 1024], Max[-897, 0, 1087] mGridCells[9]: Min[-960, 0, 1088], Max[-897, 0, 1151] mGridCells[10]: Min[-960, 0, 1152], Max[-897, 0, 1215] mGridCells[11]: Min[-960, 0, 1216], Max[-897, 0, 1279] mGridCells[12]: Min[-960, 0, 1280], Max[-897, 0, 1343] mGridCells[13]: Min[-960, 0, 1344], Max[-897, 0, 1407] mGridCells[14]: Min[-960, 0, 1408], Max[-897, 0, 1471] mGridCells[15]: Min[-960, 0, 1472], Max[-897, 0, 1535] mGridCells[16]: Min[-896, 0, 1024], Max[-833, 0, 1087] mGridCells[17]: Min[-896, 0, 1088], Max[-833, 0, 1151] mGridCells[18]: Min[-896, 0, 1152], Max[-833, 0, 1215] mGridCells[19]: Min[-896, 0, 1216], Max[-833, 0, 1279] mGridCells[20]: Min[-896, 0, 1280], Max[-833, 0, 1343] mGridCells[21]: Min[-896, 0, 1344], Max[-833, 0, 1407] mGridCells[22]: Min[-896, 0, 1408], Max[-833, 0, 1471] mGridCells[23]: Min[-896, 0, 1472], Max[-833, 0, 1535] mGridCells[24]: Min[-832, 0, 1024], Max[-769, 0, 1087] mGridCells[25]: Min[-832, 0, 1088], Max[-769, 0, 1151] mGridCells[26]: Min[-832, 0, 1152], Max[-769, 0, 1215] mGridCells[27]: Min[-832, 0, 1216], Max[-769, 0, 1279] mGridCells[28]: Min[-832, 0, 1280], Max[-769, 0, 1343] mGridCells[29]: Min[-832, 0, 1344], Max[-769, 0, 1407] mGridCells[30]: Min[-832, 0, 1408], Max[-769, 0, 1471] mGridCells[31]: Min[-832, 0, 1472], Max[-769, 0, 1535] mGridCells[32]: Min[-768, 0, 1024], Max[-705, 0, 1087] mGridCells[33]: Min[-768, 0, 1088], Max[-705, 0, 1151] mGridCells[34]: Min[-768, 0, 1152], Max[-705, 0, 1215] mGridCells[35]: Min[-768, 0, 1216], Max[-705, 0, 1279] mGridCells[36]: Min[-768, 0, 1280], Max[-705, 0, 1343] mGridCells[37]: Min[-768, 0, 1344], Max[-705, 0, 1407] mGridCells[38]: Min[-768, 0, 1408], Max[-705, 0, 1471] mGridCells[39]: Min[-768, 0, 1472], Max[-705, 0, 1535] mGridCells[40]: Min[-704, 0, 1024], Max[-641, 0, 1087] mGridCells[41]: Min[-704, 0, 1088], Max[-641, 0, 1151] mGridCells[42]: Min[-704, 0, 1152], Max[-641, 0, 1215] mGridCells[43]: Min[-704, 0, 1216], Max[-641, 0, 1279] mGridCells[44]: Min[-704, 0, 1280], Max[-641, 0, 1343] mGridCells[45]: Min[-704, 0, 1344], Max[-641, 0, 1407] mGridCells[46]: Min[-704, 0, 1408], Max[-641, 0, 1471] mGridCells[47]: Min[-704, 0, 1472], Max[-641, 0, 1535] mGridCells[48]: Min[-640, 0, 1024], Max[-577, 0, 1087] mGridCells[49]: Min[-640, 0, 1088], Max[-577, 0, 1151] mGridCells[50]: Min[-640, 0, 1152], Max[-577, 0, 1215] mGridCells[51]: Min[-640, 0, 1216], Max[-577, 0, 1279] mGridCells[52]: Min[-640, 0, 1280], Max[-577, 0, 1343] mGridCells[53]: Min[-640, 0, 1344], Max[-577, 0, 1407] mGridCells[54]: Min[-640, 0, 1408], Max[-577, 0, 1471] mGridCells[55]: Min[-640, 0, 1472], Max[-577, 0, 1535] mGridCells[56]: Min[-576, 0, 1024], Max[-513, 0, 1087] mGridCells[57]: Min[-576, 0, 1088], Max[-513, 0, 1151] mGridCells[58]: Min[-576, 0, 1152], Max[-513, 0, 1215] mGridCells[59]: Min[-576, 0, 1216], Max[-513, 0, 1279] mGridCells[60]: Min[-576, 0, 1280], Max[-513, 0, 1343] mGridCells[61]: Min[-576, 0, 1344], Max[-513, 0, 1407] mGridCells[62]: Min[-576, 0, 1408], Max[-513, 0, 1471] mGridCells[63]: Min[-576, 0, 1472], Max[-513, 0, 1535] mGridCells[64]: Min[-1152, 0, 896], Max[-1089, 0, 959] mGridCells[65]: Min[-1152, 0, 960], Max[-1089, 0, 1023] mGridCells[66]: Min[-1152, 0, 1024], Max[-1089, 0, 1087] mGridCells[67]: Min[-1152, 0, 1088], Max[-1089, 0, 1151] mGridCells[68]: Min[-1152, 0, 1152], Max[-1089, 0, 1215] mGridCells[69]: Min[-1152, 0, 1216], Max[-1089, 0, 1279] mGridCells[70]: Min[-1152, 0, 1280], Max[-1089, 0, 1343] mGridCells[71]: Min[-1152, 0, 1344], Max[-1089, 0, 1407] mGridCells[72]: Min[-1152, 0, 1408], Max[-1089, 0, 1471] mGridCells[73]: Min[-1152, 0, 1472], Max[-1089, 0, 1535] mGridCells[74]: Min[-1152, 0, 1536], Max[-1089, 0, 1599] mGridCells[75]: Min[-1152, 0, 1600], Max[-1089, 0, 1663] mGridCells[76]: Min[-1088, 0, 896], Max[-1025, 0, 959] mGridCells[77]: Min[-1088, 0, 960], Max[-1025, 0, 1023] mGridCells[78]: Min[-1088, 0, 1024], Max[-1025, 0, 1087] mGridCells[79]: Min[-1088, 0, 1088], Max[-1025, 0, 1151] mGridCells[80]: Min[-1088, 0, 1152], Max[-1025, 0, 1215] mGridCells[81]: Min[-1088, 0, 1216], Max[-1025, 0, 1279] mGridCells[82]: Min[-1088, 0, 1280], Max[-1025, 0, 1343] mGridCells[83]: Min[-1088, 0, 1344], Max[-1025, 0, 1407] mGridCells[84]: Min[-1088, 0, 1408], Max[-1025, 0, 1471] mGridCells[85]: Min[-1088, 0, 1472], Max[-1025, 0, 1535] mGridCells[86]: Min[-1088, 0, 1536], Max[-1025, 0, 1599] mGridCells[87]: Min[-1088, 0, 1600], Max[-1025, 0, 1663] mGridCells[88]: Min[-512, 0, 896], Max[-449, 0, 959] mGridCells[89]: Min[-512, 0, 960], Max[-449, 0, 1023] mGridCells[90]: Min[-512, 0, 1024], Max[-449, 0, 1087] mGridCells[91]: Min[-512, 0, 1088], Max[-449, 0, 1151] mGridCells[92]: Min[-512, 0, 1152], Max[-449, 0, 1215] mGridCells[93]: Min[-512, 0, 1216], Max[-449, 0, 1279] mGridCells[94]: Min[-512, 0, 1280], Max[-449, 0, 1343] mGridCells[95]: Min[-512, 0, 1344], Max[-449, 0, 1407] mGridCells[96]: Min[-512, 0, 1408], Max[-449, 0, 1471] mGridCells[97]: Min[-512, 0, 1472], Max[-449, 0, 1535] mGridCells[98]: Min[-512, 0, 1536], Max[-449, 0, 1599] mGridCells[99]: Min[-512, 0, 1600], Max[-449, 0, 1663] mGridCells[100]: Min[-448, 0, 896], Max[-385, 0, 959] mGridCells[101]: Min[-448, 0, 960], Max[-385, 0, 1023] mGridCells[102]: Min[-448, 0, 1024], Max[-385, 0, 1087] mGridCells[103]: Min[-448, 0, 1088], Max[-385, 0, 1151] mGridCells[104]: Min[-448, 0, 1152], Max[-385, 0, 1215] mGridCells[105]: Min[-448, 0, 1216], Max[-385, 0, 1279] mGridCells[106]: Min[-448, 0, 1280], Max[-385, 0, 1343] mGridCells[107]: Min[-448, 0, 1344], Max[-385, 0, 1407] mGridCells[108]: Min[-448, 0, 1408], Max[-385, 0, 1471] mGridCells[109]: Min[-448, 0, 1472], Max[-385, 0, 1535] mGridCells[110]: Min[-448, 0, 1536], Max[-385, 0, 1599] mGridCells[111]: Min[-448, 0, 1600], Max[-385, 0, 1663] mGridCells[112]: Min[-1024, 0, 896], Max[-961, 0, 959] mGridCells[113]: Min[-1024, 0, 960], Max[-961, 0, 1023] mGridCells[114]: Min[-960, 0, 896], Max[-897, 0, 959] mGridCells[115]: Min[-960, 0, 960], Max[-897, 0, 1023] mGridCells[116]: Min[-896, 0, 896], Max[-833, 0, 959] mGridCells[117]: Min[-896, 0, 960], Max[-833, 0, 1023] mGridCells[118]: Min[-832, 0, 896], Max[-769, 0, 959] mGridCells[119]: Min[-832, 0, 960], Max[-769, 0, 1023] mGridCells[120]: Min[-768, 0, 896], Max[-705, 0, 959] mGridCells[121]: Min[-768, 0, 960], Max[-705, 0, 1023] mGridCells[122]: Min[-704, 0, 896], Max[-641, 0, 959] mGridCells[123]: Min[-704, 0, 960], Max[-641, 0, 1023] mGridCells[124]: Min[-640, 0, 896], Max[-577, 0, 959] mGridCells[125]: Min[-640, 0, 960], Max[-577, 0, 1023] mGridCells[126]: Min[-576, 0, 896], Max[-513, 0, 959] mGridCells[127]: Min[-576, 0, 960], Max[-513, 0, 1023] mGridCells[128]: Min[-1024, 0, 1536], Max[-961, 0, 1599] mGridCells[129]: Min[-1024, 0, 1600], Max[-961, 0, 1663] mGridCells[130]: Min[-960, 0, 1536], Max[-897, 0, 1599] mGridCells[131]: Min[-960, 0, 1600], Max[-897, 0, 1663] mGridCells[132]: Min[-896, 0, 1536], Max[-833, 0, 1599] mGridCells[133]: Min[-896, 0, 1600], Max[-833, 0, 1663] mGridCells[134]: Min[-832, 0, 1536], Max[-769, 0, 1599] mGridCells[135]: Min[-832, 0, 1600], Max[-769, 0, 1663] mGridCells[136]: Min[-768, 0, 1536], Max[-705, 0, 1599] mGridCells[137]: Min[-768, 0, 1600], Max[-705, 0, 1663] mGridCells[138]: Min[-704, 0, 1536], Max[-641, 0, 1599] mGridCells[139]: Min[-704, 0, 1600], Max[-641, 0, 1663] mGridCells[140]: Min[-640, 0, 1536], Max[-577, 0, 1599] mGridCells[141]: Min[-640, 0, 1600], Max[-577, 0, 1663] mGridCells[142]: Min[-576, 0, 1536], Max[-513, 0, 1599] mGridCells[143]: Min[-576, 0, 1600], Max[-513, 0, 1663]

sbonnalc commented 11 months ago

Strange: I have the feeling that what ever the point and our input Grid, the problem occurs on id=22

sbonnalc commented 11 months ago

I actually found the problem.

The code is using numeric_limits::infinity(). This is only valid for floating point types.
It's not valid for integer types. you can check that with has_infinity().
So, replacing infinity with numeric_limits::max and min solves the problem.
In our case, when the input boxes are only in the negative part of the integer, the box_of_boxes() method computes a global bounding box including 0. Which messes the Rasterizer factors.

attcs commented 11 months ago

Nice catch! Thank you very much! I attached these boxes as a unittest and pushed the solution also.

sbonnalc commented 11 months ago

Actually, strickly speaking numeric_limits::min() != -numeric_limits::max(). Usually, it's more numeric_limits::min() = -numeric_limits::max() -1.

attcs commented 11 months ago

Yes, it is true for integer types, but I tried to keep this inf variable. But honestly, this infinity thing caused more trouble than it's worth, so I dropped in favor of numeric_limits::max()/lowest().

sbonnalc commented 11 months ago

Applied your commit in our project. All good :-) Thanks a lot for your help and prompt reaction. That's appreciated.