Hello,
I am planning to implement a baseline radiance cache algorithm which might use KNN algorithm, but I am unsure what would be the recommanded way.
Here is the description: In the scene, I have sampled a point cloud with around 500,000 points or 3 to 1000 per triangle depending on the area. In the __closesthit__radiance program, I wish to find the k-nearest points around the hit position. The actual value I need are the identifiers of the k-nearest points.
I am wondering if there are any previous work has done something similar. I have thought about two ways to this.
- Store the sample points per surface through shader binding table. Then calculate all the euclidean distance between the sample points and the hit position, followed by a sort operation. But this might not be good for points at the edge of the triangles.
- Store the point cloud in a data structure like octree and in global memory, for example in LaunchParams. Then query the octree in the
__closesthit__radiance program.
I am wondering if there are other ways to this. Or does optix has built-in functions that do the knn search? If not, which one of the above option sounds better?
I know there is nerual radiance caching and spatial hash radiance cahing techniques to avoid the knn search. But I am planning to include this knn search as a baseline method to compare.
Best,
- Store the sample points per surface through shader binding table. Then calculate all the euclidean distance between the sample points and the hit position, followed by a sort operation. But this might not be good for points at the edge of the triangles.
No, that would be super slow because that would walk through all points per surface hit.
In any case, you should be able to determine which of the points would be contributing radiance to a triangle based on its position relative to the triangle (front or back side).
- Store the point cloud in a data structure like octree and in global memory, for example in LaunchParams. Then query the octree in the
__closesthit__radiance program.
Yes, using some data structure for the points inside the point cloud which accelerates the kNN search is the recommended approach.
Inside the closesthit program you would only need to have some algorithm which finds the k nearest neighbours.
The algorithm with which you search these nearest points would depend on the search structure you pick.
Other suitable structures are for example kD-trees or spatial hash-maps.
The very old OptiX SDK 3.9.x you can still find on the OptiX SDK legacy versions download site, contained an example named progressivePhotonMap which builds a kD-tree on the host inside ppm.cpp function buildKDTree() and searches through that kD-tree inside the ppm_gather.cu function gather().
That kD-tree structure is basically a binary tree with fixed locations easily accessible via the node index for the two children at each node. (Look for the push_node() macros.)