Possiblitiy for deterministic results with KDTreeFlann

[Andreas-W]

Checklist

• [X] I have searched for similar issues.
• [X] For Python issues, I have tested with the latest development wheel.
• [X] I have checked the release documentation and the latest documentation (for master branch).

My Question

open3d.geometry.KDTreeFlann produces non-deterministic results for KNN search, also mentioned here:

The only non-deterministic part of the algorithm is the KNN search. I verified with PCL implementation of radius_outlier_removal, it is similar to the Open3D implementation. Only, KD-Tree based KNN search output might differ. Open3D uses nanoflann on CPU for KNN Search.

Originally posted by @reyanshsolis in https://github.com/isl-org/Open3D/issues/2344#issuecomment-1007505205

As I understand o3d uses the nanoflann library. Are there any plans for possible deterministic results in the future or is this entirely up to nanoflann?

kind regards, Andreas

[hernot]

Best check sources for nanoflann to see if non-determinism only affects order of points reported of points to be included are missed and not to be included ones are contained. In case it is just about order either in terms of distance or index or both than i'd suggest to use the distance vector returned (L2 norm - squared distance) and do an index sort on it to get order of points or sort indices returned to get points again in order of indices.

If it is about missing points and falsely included points, than you have to check whether parameters selected for the default tree used by open3D are suitable for your needs, otherwise the your only option is either to directly use nanoflann or switch to an exact knntree library or at least one which allows you to increase number of iterations and tune other tree and search parameters not yet accessible through open3d or even nanoflann api.