how to do closest point query using OpenVDB?

First, How to find closest point using openvdb?

Second, If ClosestSurfacePoint is right way to do that, how to use it?

I read paper about ICP using OpenVDB for faster NNS.

(http://www.pmavridis.com/research/efficient_sparse_icp/)

The author says that he got advance in speed by using openvdb for NNS.

And some other people achieved same thing in similar way.

So, I wanted to try that myself.

After several trying, i finally succeeded in compiling.

However, i am little bit confused.

In my point of view(after reading lots of docs including online cookbook) sampler seemed to do that

so, i tried these examples.

GridType::ConstAccessor accessor = grid.getConstAccessor();
GridType::ValueType v0 = openvdb::tools::PointSampler::sample(accessor, ijk);
GridType::ValueType v1 = openvdb::tools::BoxSampler::sample(accessor, ijk);
GridType::ValueType v2 = openvdb::tools::QuadraticSampler::sample(accessor, ijk);

I did things as described below

object: find point in grid closest to query point(ijk)

Create points(or load points) and convert into vec3d format
make point index grid.
set query point(ijk)
set accessor of index grid
function call of point sampler()

But, these examples show 0 or 1.

If, it finds exact same position, it return 1. If not, 0.

Probably, this pointsampler is not what i looking for.

Try in other way.

Other candidates are

 ClosestSurfacePoint, ClosestPointProjector.

i tried the codes written in below it's similar as betajippity's work https://github.com/betajippity/Ariel/blob/master/src/grid/levelset.cpp

but it makes error because of vector

std::vector<openvdb::Vec3s> positions = {
        { 1, 1, 1 },
        { 1, 2, 1 },
        { 2, 1, 1 },
        { 2, 2, 1 },
        { 100, 100, 100 },
        { 100, 101, 100 }
    };

myPointList pointlist(positions);

const float voxelSize(1.0);
openvdb::math::Transform::Ptr transform(openvdb::math::Transform::createLinearTransform(voxelSize));

openvdb::tools::PointIndexGrid::Ptr vdbgrid =
    openvdb::tools::createPointIndexGrid<openvdb::tools::PointIndexGrid>(pointlist, *transform);

openvdb::FloatGrid vdbgrid;


openvdb::util::NullInterrupter n;
std::vector<float> distances;


openvdb::tools::ClosestSurfacePoint<openvdb::tools::PointIndexGrid> csp;

csp.initialize(*vdbgrid, 0.0f, &n);

The last line

csp.initialize(*vdbgrid, 0.0f, &n);

Causes Debug Assertion failed.

File: C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\vector
Line: 72

Expression: vector iterator not dereferencable

I have no idea how to deal with these things.

Because I cannot modify openvdb's inside. I just called function and it makes error :(

If you have any idea for this, please help.

Again, Questions are..

How to find closest point using openvdb?

If ClosestSurfacePoint is right way to do that, how to use it?

I really appreciate you in advance.

Solution

Answer from OpenVDB points developer.

It's a good question, I'll attempt to answer this.

In short, yes and no. OpenVDB Points is an ideal base data structure for doing nearest neighbor search as it is already spatially organised,

however we have not yet provided any high-level APIs to do for this for you so you would have to write much of the algorithm yourself.

Due to the spatial nature of the grid, it's relatively simple and very fast to do a nearest neighbor search where you have a "maximum radius" in which to search that isn't too large as you can tune the size of your voxels to match this radius and maximise performance.

It is much more challenging to perform an arbitrary-distance nearest neighbor search, where I suggest you'll find it hard to get decent performance out of the data structure without also writing a supporting framework (such as a kd-tree).

We have attempted nearest-neighbor algorithms though, so if I haven't put you off with that summary, we would be happy to point you in the right direction here regarding an implementation. :)

Thanks, Dan