[vtkusers] Determine which points are inside of a cell

[David Doria]

> Hi David,
>
> Don't use locators with structured data like vtkImageData.  The
> FindPoint() and FindCell() methods for the vtkImageData object itself
> work in constant time and are hundreds of times faster than using
> FindPoint/Cell on a locator.  Also, building a locator for an image
> data is wasteful... the locator will eat up around 24 times as much
> memory as the image itself (assuming a 16-bit image) because the
> locator computes and stores the bounding box for each and every cell.
>
> As an aside, you also have to be careful about what vtk means by a
> "vtkVoxel" cell.  The vtkVoxel is a cell with a data point at each
> corner, and is used by VTK's generic data interface for interpolating
> between the data values at the eight corner points.  It's actually the
> points in the vtkImageData that correspond to what people usually mean
> when they say "voxel".  As an illustration of this, if you display an
> image with vtkImageActor, then the center each square pixel you see on
> the screen corresponds to the (x,y,z) of a point in the data.
>
> Another way of explaining this is that when you store data in the
> image, you store the data as "PointData", not as "CellData".  So
> please make sure that image->FindCell is what you want, because I
> suspect that image->FindPoint is the method that actually gives you
> the information you need.
>
>
> Finally getting to your question, about the only really useful method
> for finding multiple points is this:
>
> vtkPointLocator::FindPointsWithinRadius(radius, point, pointIdList);
>
> It finds all the points within a sphere, so you need "radius" to be
> larger than the voxel so that it will return more points than you
> need, and then you can use a "for" loop to exclude points that aren't
> within the voxel.  It's clunky, but I don't think there is any other
> way.
>
>  David
>

Hi David G,

Thanks for your very detailed response.

I apologize if my terminology was clunky. What I am trying to do here
is determine which points (from a polydata) are inside of a grid of
cubes. Am I correct that these cubes are the cells of the ImageData,
and the corners (or centers?) of the cubes are the points of the
ImageData? If this is correct, then since I am interested in which
cube, I think I am indeed looking to use the FindCell function.

It has quite a beast of a signature:

virtual vtkIdType vtkDataSet::FindCell	(	double 	x[3],
vtkCell * 	cell,
vtkIdType 	cellId,
double 	tol2,
int & 	subId,
double 	pcoords[3],
double * 	weights	
)	

Maybe you can check/fill in these parameter explanations:

- double x[3] : the point in question (the point we want to know which
cube it falls inside of)

- vtkCell* cell : a point to the actual cell that is found

- vtkIdType cellId: is this the same value that is returned by the
function? If so, that seems very odd.

- double tol2: what is a reasonable value for this?

- int & subId : I assume I'll never use this so I'll just pass it a
variable to make it happy and then never use it

- pcoords : not used for this type of query

- weights : also not used for this

Could we add a

virtual vtkIdType vtkDataSet::FindCell	(double 	x[3])	

that uses some good default values and is much easier to call when
trying to do operations like this?

Also, could we add a function "FindPointsWithinVoxel" (or maybe voxel
is again bad terminology) which calls FindPointsWithinRadius (with the
radius = the diagonal length of the cube)and then loops through to
remove points outside of the cube but inside of the sphere?

Thanks,

David