What is the function of the grid points? Can it be used to subsample a point cloud in a voxel downsample way?

[liuzhy71]

Hi,

Thank you for the great work!

Currently I need to find the k nearest neighbor for a point cloud, then I need to downsample the point cloud in a voxel downsample way, can the grid output be use for the downsampling?

[lxxue]

Hi,

I hope I understand your question correctly. Here is the documentation for the returned grid structure:

FRNN/frnn/frnn.py

Lines 217 to 223 in 59a4c8f

	grid: A namedtuple of 4 tensors for reusing the grid if necessary/possible.
	Users don't need to know what's inside.
	_GRID = namedtuple("GRID", "sorted_points2 pc2_grid_off sorted_points2_idxs grid_params")
	sorted_points2 is a spatially sorted version of points2;
	sorted_points2_idxs records the mapping between points2 and sorted_points2;
	grid_params characterizes the constructed grid;
	pc2_grid_off records the start and the end indices of sorted_points2 for each grid

In sorted_points2, points are sorted according to their voxel index. Therefore, with pc2_grid_off you will know the points inside one specific voxel (Here 2 are hard-coded for 2D points, you might want to change to 3):

FRNN/frnn/csrc/grid/find_nbrs.cu

Lines 50 to 60 in 3e370d8

	int p2_start = pc2_grid_off[n * G + cell_idx];
	int p2_end;
	if (cell_idx + 1 == grid_total) {
	p2_end = lengths2[n];
	} else {
	p2_end = pc2_grid_off[n * G + cell_idx + 1];
	}
	for (int p2 = p2_start; p2 < p2_end; ++p2) {
	float2 diff;
	diff.x = points2[n * P2 * 2 + p2 * 2] - cur_point.x;
	diff.y = points2[n * P2 * 2 + p2 * 2 + 1] - cur_point.y;

And then you can do whatever you want to downsample the points inside each voxel.

[liuzhy71]

Thanks a lot! Are we allowed to change the initial grid size before fitting the knn?

[lxxue]

Yes, the search radius r and radius_cell_ratio jointly determine the grid size:

FRNN/frnn/frnn.py

Line 77 in 3e370d8

cell_size = r[i].item() / radius_cell_ratio

For KNN you should find a radius large enough so that you can find K neighbors within the radius for sure. When the radius_cell_ratio is an integer, the method runs more efficiently since it search 2*ceil(radius_cell_ratio)+1 grids on one dimension.