sample_points_poisson_disk is extremely slow

[BG4444]

Checklist

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

Describe the issue

By comparing the algorithm in TriangleMesh.cpp I found that the implementation of SamplePointsPoissonDisk differs from the original paper (Fig. 2), as well as from the author’s reference implementation: (lines 370-380).

The original version runs about 10× faster than the implementation currently in Open3D due to excessive KD-tree queries and unnecessary recalculation of point weights and memory allocations.

Steps to reproduce the bug

import open3d as o3d
import time


def main():
    # Standford bunny https://graphics.stanford.edu/~mdfisher/Data/Meshes/bunny.obj
    mesh = o3d.io.read_triangle_mesh('bunny.obj') 

    start = time.time()
    pcd = mesh.sample_points_poisson_disk(number_of_points=16384)
    done = time.time()

    print(f'Spent {done-start:8.4f}s')

if __name__=="__main__":
    main()

Error message

Spent 1.9823s

Expected behavior

Spent 0.3s

Open3D, Python and System information

- Operating system: Ubuntu 24.04
- Python version: 3.10.14 (main, Mar 21 2024, 16:24:04) [GCC 11.2.0]
- Open3D version: 0.19.0
- System architecture: amd64
- Is this a remote workstation?: no
- How did you install Open3D?: pip

Additional information

No response