orient_normals_consistent_tangent_plane runtime is really slow when part of the cloud is coplanar

[Sheradil]

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).

Describe the issue

To me it seems that there is a mathematical issue in the calculation of this method.

I have a point cloud (200k points) that resembles a mug. I want to calculate the volume (as if the mug is closed on top). So I have to do surface reconstruction and get a watertight mesh. For that I have to close the hole on the top of the mug and estimate normals do be able to perform the surface reconstruction. I sample 10k points in that hole ( to have some support vertices to the surface). All on the same plane. Then I set the normal vectors of the sampled points to the normal of the plane. Then both clouds are combined. Now for the reconstruction, normals in a neighbourhood should face in the same direction. So I called "orient_normals_consistent_tangent_plane" to match the direction of the mug and the sampled points.

It didn't work. It didn't finish the execution. And it didn't make sense to me. I thought that I just used too many points. So I tried with 10k points (no sampled points, just from the cloud), then 50k and 200k and it always executed. Then I tried 210k and it stopped working. So I thought there is a kind of limitation. So I randomly selected 200k points from my 210k points and it stopped working again. So it wasn't the number of points. In fact the issue were the sampled points.

The issue in my case was that all of the sampled points were coplanar. I then added a minimum amount of noise, e.g. created a random vector of length 0.0001 and added it to each individual sampled point. That fixed the issue and the execution time is back to 12s.

My guess: If too many points are coplanar, then something goes wrong. And that shouldn't happen. (I also mentioned it here: https://github.com/isl-org/Open3D/issues/4983)

Steps to reproduce the bug

import time

import open3d as o3d
import numpy as np


def sample_points_in_square_uniform(u, v, sample_num = 25000):
	"""
	Samples 'sample_num' points uniformly in a trapeze specified by the vectors 'u' and 'v'
	:param u: a vector representing the first side of the trapeze
	:param v: a vector representing the second side of the trapeze
	:param sample_num: the number of samples to be drawn
	:return: an array that holds the coordinate of all samples
	"""
	scalars = np.random.uniform((0, 0), (1, 1), (sample_num, 2))
	s = np.asarray([x * u for x in scalars[:, 0]])
	t = np.asarray([x * v for x in scalars[:, 1]])
	return s + t


USE_NOISE = True
points_plane = sample_points_in_square_uniform(
	np.asarray([5.0, 0.0, 0.0]),
	np.asarray([0.0, 5.0, 0.0])
)
normal = np.asarray(25000 * [0.0, 0.0, 1.0])
normal = np.reshape(normal, [25000, 3])
if USE_NOISE:
	noise = np.random.uniform((-0.0001, -0.0001, -0.0001), (0.001, 0.001, 0.001), (25000, 3))
	points_plane = points_plane + noise

points_rnd = np.random.uniform((-3, -3, -3), (0, 0, 0), (25000, 3))
pcd = o3d.geometry.PointCloud()
pcd.points = o3d.utility.Vector3dVector(points_rnd)
pcd.estimate_normals()

points = np.concatenate((points_plane, points_rnd))
normals = np.concatenate((normal, pcd.normals))

pcd = o3d.geometry.PointCloud()
pcd.points = o3d.utility.Vector3dVector(points)
pcd.normals = o3d.utility.Vector3dVector(normals)
start = time.time()
pcd.orient_normals_consistent_tangent_plane(k = 50)
end = time.time()
print(end - start)

Error message

Not an error: Runtime without noise: 85.74937605857849 (Just let it run it once) Runtime with noise: 1.5569915771484375 1.5150337219238281 1.5520386695861816

Expected behavior

Without noise it should ran as fast as with noise. It shouldn't matter that a subset of the points is coplanar.

Open3D, Python and System information

- Operating system: Ubuntu 20.04 
- Python version: Python 3.10.12
- Open3D version: output from python: 0.17.0
- System architecture: x86
- Is this a remote workstation?: no
- How did you install Open3D?: conda

Additional information

No response