Spatial Index

[GIacomoponti00]

Hi, I'm very confused on how to build the spatial index for faster search, since we're using it for 2 very different tasks. The first task (closest neighbor) only uses cloud point while the 2nd uses all the constraint points and its based on grid points positions which have no connection to the spatial index cubes. Should the search grid include all constraint points or just the initial cloud points? Should we center each search cell to the corresponding initial cloud point?

Any help is appreciated. Thanks.

[segaviv]

Hi,

The spatial index should be a grid of some resolution (different from the resolution of the marching cubes grid), where each grid cell contains all the input points that lie within its bounds. You should decide which resolution to use for the acceleration structure - try to think which value could make the implementation easier/more efficient, while keeping the query result correct.

For the first task you should indeed use only the input points. For the second you can decide - you could either add the extra constraint points to the acceleration structure, or query for the input points within the given radius and add their corresponding constraints as a separate step.

I'm not sure I understand your second question - the spatial index should be a regular grid, and the centers of the cells should be uniformly distributed within the bounding box of the mesh.

Best, Aviv

[GIacomoponti00]

Thank you for your answer. To me what is confusing with using uniform distributed grids is the position of the grid vertex in the search grid. Suppose a grid point lies on the upper left corner of a cube in the search grid. Then if we were to search for constraints in a radius then a search in the current cube would not be sufficient, we would need to search the cubes adjacent to the upper left part of the cube. Instead if we were to center the grid we would only need to search the current cube (provided the cube is bigger than the sphere of wendlandRadius).

[segaviv]

Well, if the spatial index cell size is bigger than the Wendland radius, and you center each cell at a marching cube grid point, the spatial index won't really be a grid since its cells will overlap one another (when the radius is greater than the grid resolution, otherwise you'll have 'gaps' in the search structure). The structure you're describing sounds more like a cache than a search structure, and you'll have to regenerate it whenever the marching cube grid resolution changes. It's also not very efficient to use it for a nearest neighbor search (due to the gaps/overlapping cells).

It is true that you'll have to search more than one cell, depending on the resolution of the spatial index (which you can set as a parameter, or choose one that makes the implementation easier/more efficient). It should still be faster than a brute force search, however, as you won't have to check all the points in the search queries.

[GIacomoponti00]

Thanks for the clarification, now it makes more sense. I understand now that the goal is just to make the neighbor queries faster than the brute force search.