[vtk-developers] About vtkParametricSpline Initialize() performance

[Simon ESNEAULT]

Hi all,

We use a lot vtkParametricSpline here, with quite a lot of points, ~4000
With that number of points, the method "Initialize()" takes around 0.7
seconds (vtk 5.8, linux, intel Core i7 at 3.0 Ghz)

After some hack, this time is reduced to : 0.001 seconds, (700x speed up
!), for the exact same result

Explanations :
While digging into the code, I've noticed that for each added point in
vtkSpline, there is a call of the method SortAndUpdateRange() in
vtkPiecewiseFunction, and after that, a search through all the nodes in
order to return the array index of the point.
Now in vtkParametricSpline, all the point are added with something like :
/********************************************************************/
    for ( len = 0.0, i = 0; i < npts; ++i )
      {
      this->Points->GetPoint(i,x);
      len += sqrt(vtkMath::Distance2BetweenPoints(x,xPrev));
  this->XSpline->AddPoint(len,x[0]);
   this->YSpline->AddPoint(len,x[1]);
  this->ZSpline->AddPoint(len,x[2]);
      xPrev[0]=x[0]; xPrev[1]=x[1]; xPrev[2]=x[2];
      }
/********************************************************************/

2 remarks :
- we don't need to sort because all the points are added already sorted
(the variable "len" can only increase), or at least we should sort only
once at the end
- we don't use the return value (no need to search)

So I've added a method in vtkSpline which looks like :
/********************************************************************/
void vtkSpline::AddPoints (double* t, double* x, int n)
{
  this->PiecewiseFunction->AddPoints (t, x, n);
}
/********************************************************************/

And another one in vtkPiecewiseFunction which looks like this :
/********************************************************************/
void vtkPiecewiseFunction::AddPoints( double* x, double* y, int n )
{
  for( int i=0; i<n; i++ ){
    vtkPiecewiseFunctionNode *node = new vtkPiecewiseFunctionNode;
    node->X         = x[i];
    node->Y         = y[i];
    node->Sharpness = 0.0;
    node->Midpoint  = 0.5;
    this->Internal->Nodes.push_back(node);
  }
  this->SortAndUpdateRange();
}
/********************************************************************/

Finally the modified vtkParametricSpline Initialize() method looks like :
/********************************************************************/
    double lengths[npts];
    double pointx[npts];
    double pointy[npts];
    double pointz[npts];
    for ( len = 0.0, i = 0; i < npts; ++i )
      {
      this->Points->GetPoint(i,x);
      len += sqrt(vtkMath::Distance2BetweenPoints(x,xPrev));
      lengths[i] = len;
      pointx[i] = x[0];
      pointy[i] = x[1];
      pointz[i] = x[2];
      xPrev[0]=x[0]; xPrev[1]=x[1]; xPrev[2]=x[2];
      }
    this->XSpline->AddPoints(lengths,pointx,npts);
    this->YSpline->AddPoints(lengths,pointy,npts);
    this->ZSpline->AddPoints(lengths,pointz,npts);
    }
/********************************************************************/

Conclusion :
I know 4000 points for a spline is somewhat stupid, but the gain is
significant and maybe this can help some other people. Also, maybe this can
be useful for TransferFunction with a big number of points. And last but no
least, on windows, the underlying std::sort is especially slow in Debug,
because visual studio enables some heap debugging. So the gain in
performance may even be higher in that case.

Cheers,
Simon


-- 
------------------------------------------------------------------
Simon Esneault
13 rue Vasselot
35000 Rennes, France
Tel : 06 64 61 30 94
Mail : simon.esneault at gmail.com
------------------------------------------------------------------
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20131001/b93bbe58/attachment.html>