how to do closest point query using OpenVDB?

Question

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.

@pingul thanks, i edited post. First, how to find closest point using openvdb. If ClosestSurfacePoint is right way to do that, how to use it? — eclipse0922, Nov 17 '16 at 10:20
You should only need a `PointIndexGrid`. Use the grid to get the LeafNode where your point is, and then iterate over all the points in the LeafNode to find which one is the closest. — pingul, Nov 17 '16 at 13:43
@pingul actually, i decided to try another method. because if i traverse all of leaf nodes its just same as naive sequential traverse. it looks like put points into kdtree and convert into array then, traverse. I need to look around openvdb api and docs more time. Anyway thanks, — eclipse0922, Nov 21 '16 at 01:10
maybe you're right, but i need to figure out fastest way and reason for that. — eclipse0922, Nov 21 '16 at 01:23
You don't traverse all the leaf nodes -- you traverse all the voxels and particle in 1 leaf node. — pingul, Nov 21 '16 at 15:41
The last statement is half-true. You would probably need to expand the search radius somewhat (if you look for at a coordinate close to the edge of a leaf, the closest point might be in a nearby leaf, so you might have to increase the search radius). For your small example you will definitely not see a speedup, but it should go significantly faster than a normal traverse of the array when you start increasing the number of points. Also, note that OpenVDB since 1 week supports points internally: https://github.com/dneg/openvdb_points_dev — pingul, Nov 21 '16 at 15:46
@pingul oh,, i see. i misunderstood your previous comment. i will try again. Thanks for help. — eclipse0922, Nov 22 '16 at 00:10
And... because of environmental constraints(VS2013) i can not build 4.0, i need to use 3.2 instead. so.. before usage of openvdb points, i have to build it separately. Too bad. — eclipse0922, Nov 22 '16 at 00:18

score 1 · Accepted Answer · answered Nov 26 '16 at 03:52

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

how to do closest point query using OpenVDB?

1 Answers1