Rvcg: Save and reuse KD-trees using external pointers

KD-trees are a fast and reliable method for spatial indexing and closest point searches. In Rvcg, the functions vcgKDtree and vcgClostKD provide these functionality, however only returning the result and discarding the KD-trees. For registration processes, the distances are updated in each iteration and it would be sensible to save and reuse the computationally expensive KD-tree setup, especially for large meshes.

How to achieve this

The package Rcpp, that is used to exchange data between R and vcglib, is also sporting external pointers (some sort of smart pointers) that allow to return pointers to objects created by the C++ code and later pass it back and reuse it. The newly introduced function vcgCreateKD tree allows to create such an object from meshes and point clouds. Using vcgSearchKDtree allows to calculated the k-closest neighbours and the respective distances. For closest point searches on triangular meshes, this is based on visiting the faces with the k-closest barycenters. Apart from the KD-tree and the corresponding points (the faces’ barycenters in this case), we now also need the information of the surface mesh. This can be obtained by the function vcgCreateKDtreeFromBarycenters and to search it using the function vcgClostOnKDtreeFromBarycenters can be used.

Below is the speed comparison of 10 closest point searches for 5637 coordinates on a triangular mesh with 564877 vertices and 1127080 faces.

CAVEAT: In order to reproduce this, you need to install the xptr branch from Rvcg: devtools::install_github("zarquon42b/Rvcg",ref="xptr")

Here the results (Figure 1):

• setting up the kd-tree takes 1.7 secs
• running 10 searches without reusing the KD-tree takes 11.3 secs
• running 10 searches reusing the KD-tree takes 11.3 secs only 3.7 secs

require(Rvcg)
data(humface)
data(dummyhead)
## do a face subdivision to get a mesh with 564877 vertices and 1127080 faces
humfacehigh <- vcgSubdivide(humface,threshold = 0.5,iterations = 8)

tbary <- system.time(kdtreeBary <- vcgCreateKDtreeFromBarycenters(humfacehigh))
print(tbary[3])


tsearch0 <- system.time(lapply(1:10,function(x) test <- vcgClostOnKDtreeFromBarycenters(kdtreeBary,dummyhead.mesh,threads=parallel::detectCores())))
print(tsearch0[3])

## now without reusing the kd-tree
tsearch1 <- system.time(lapply(1:10,function(x) test <- vcgClostKD(dummyhead.mesh,humfacehigh,threads=parallel::detectCores())))
print(tsearch1[3])