FarthestPointDownSample: starting with an index other than 0

[abhishek47kashyap]

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

My Question

Looking at the implementation of PointCloud::FarthestPointDownSample() (linked down below for convenience), the downsampling always starts from points_[0] because farthest_index is initialized as 0.

Open3D/cpp/open3d/geometry/PointCloud.cpp

Lines 509 to 542 in fcc396e

	std::shared_ptr<PointCloud> PointCloud::FarthestPointDownSample(
	size_t num_samples) const {
	if (num_samples == 0) {
	return std::make_shared<PointCloud>();
	} else if (num_samples == points_.size()) {
	return std::make_shared<PointCloud>(*this);
	} else if (num_samples > points_.size()) {
	utility::LogError(
	"Illegal number of samples: {}, must <= point size: {}",
	num_samples, points_.size());
	}
	// We can also keep track of the non-selected indices with unordered_set,
	// but since typically num_samples << num_points, it may not be worth it.
	std::vector<size_t> selected_indices;
	selected_indices.reserve(num_samples);
	const size_t num_points = points_.size();
	std::vector<double> distances(num_points,
	std::numeric_limits<double>::infinity());
	size_t farthest_index = 0;
	for (size_t i = 0; i < num_samples; i++) {
	selected_indices.push_back(farthest_index);
	const Eigen::Vector3d &selected = points_[farthest_index];
	double max_dist = 0;
	for (size_t j = 0; j < num_points; j++) {
	double dist = (points_[j] - selected).squaredNorm();
	distances[j] = std::min(distances[j], dist);
	if (distances[j] > max_dist) {
	max_dist = distances[j];
	farthest_index = j;
	}
	}
	}
	return SelectByIndex(selected_indices);
	}

However, how could I start the downsampling from another index?

I could copy the implementation and modify the initial value of farthest_index to my desired index, but I wanted to ask if something already exists for this.

[benjaminum]

You could swap the point at index 0 with the point of your desired index and then call FarthestPointDownSample. Does this work for you?

[abhishek47kashyap]

swap the point at index 0 with the point of your desired index

That is indeed how I'm doing it right now

[abhishek47kashyap]

Would maintainers be in favor of providing the option to start from a specified index other than 0? I can take a shot at this then and open a PR

[benjaminum]

Can you explain how you use the feature? I just want to understand the use case better

[abhishek47kashyap]

Use case

I've got several camera poses (200+) looking at the same region/scene from different viewpoints. For every camera pose, I want to find n farthest viewpoints so as to get maximum "spread" for the scene. So my idea is that I can use the camera positions from the poses and run farthest point sampling, cycle through every camera position, and find the set of camera poses that are truly as far apart as they can be.

Admittedly, I'm not directly operating on a point cloud for this use case, but since I'm working with point clouds as part of the project anyway and therefore am already using Open3D, I thought I would create a "point cloud" out of the camera positions and use an Open3D functionality if available. I came across tools like fpsample but I'm not keen on bringing in a new dependency just for this one thing.

[benjaminum]

Looks like a really good example where setting the start index is needed. Looking forward to the PR!

[abhishek47kashyap]

@benjaminum PR's up for you to take a look when you can :)