[vtk-developers] potential speedup for the vtkpolydatatoimagestencil

[Mark Roden]

Hi David,

I'm looking to make the vtkpolydatatoimagestencil class faster.  Right
now, on a core i7 machine and in using release-compiled code,
translating a body mask in an rtstruct to pixels using this filter is
prohibitively expensive in time (upwards of a minute for the mask).

There are three possible speedups to do here, in my mind.  I wanted to
clear them by you, because I don't want to fork vtk to solve this
problem, but the problem has become a serious problem for us.

First, treat each plane independently of one another, and then have
each plane processed by different threads.  This change is fairly
straightforward theoretically, and something you mentioned you were
looking into a while back
(http://www.vtk.org/pipermail/vtkusers/2011-January/114538.html).  Is
this something you're still investigating?  For my work on other
projects, I've found that the intel tbb
(http://threadingbuildingblocks.org/) makes multithreading this kind
of work very easy; the library is free and works with any c++ project
that uses the C++0x standard and can use lambda expressions.  I also
know that vtk has its own multithreading architecture which is
probably more appropriate for this kind of work, but I'm not as
familiar with it.  Threading, though, can lead to lots of
complications, so would be the solution of last resort for me.

Second, change the interior while/for loop collision detection to be a
hash table.  Right now, in the ThreadedExecute function, there is this
code:

    for (vtkIdType i = 0; i < numberOfPoints; ++i)
      {
...
      while( lines->GetNextCell(npts, pointIds) )
        {
        for (vtkIdType j = 0; j < npts; ++j)
          if ( pointIds[j] == i )
            {

But what if collision detection was changed to uses a hash table where
the hashing function automatically detected point collisions through a
single pass through the data?  The pseudocode for such an operation
would be:

for (points)
   bool collision = placePointInHash(hash, point)

for (pointsInHash)
   if (points is 1)
    HandleLooseEndCase
   if (points is > 2)
     HandleMultiplePoints

etc etc

The idea is to loose that O(N^2) loop and bring it down to O(N).

If this approach were to be used, does vtk contain its own native hash
tables?  If not, what kind of hash would be appropriate to incorporate
here?

Third, there does not appear to be an iterator over the points vector,
but a Get and Set function.  These functions appear to be pretty slow,
and go through several thunking layers before data can actually be set
or not.  Is there an iterator class for points as there is for lines?
If not, how hard would it be to create such a class?

Thanks,
Mark