[vtk-developers] vtkDataArrayTemplate

Mon Nov 24 14:03:22 EST 2008

First off, I would suggest testing out the KdTree locator.  It doesn't use
GetPoint, it actually makes a new copy of the point array ordered by what
bin it is in.  That way the coordinates are in contiguous memory for each
binning of points.  For large amounts of points, the kdtree point locator
will usually do better.  If you have points that are clustered very close
together you may want to check on the bins that are created for the kdtree
as they may have high aspect ratios which can hurt performance (I had a case
where the search point was in a bin but the locator had to check 95 other
nearby bins to determine which of the points was closest to the search
point).  I'm working on an octree based locator that should go into the
repository in a week or two that will avoid this problem by making the bins
be equal-sided.

I'd also like to see the changes that you did to the point locator if you
don't mind sending them to the list.

Andy

 ------------------------------

>
> Message: 6
> Date: Mon, 24 Nov 2008 17:51:49 +0100
> From: John Biddiscombe <biddisco at cscs.ch>
> Subject: Re: [vtk-developers] vtkDataArrayTemplate
> To: Benjamin Schindler <bschindler at student.ethz.ch>
> Cc: vtk-developers at vtk.org
> Message-ID: <492ADBA5.8070303 at cscs.ch>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> Benjamin
>
> If you want to send me your changes, I'll look into making them
> official. I am at this moment also doing SPH interpolation, and I have
> just been adjusting some custom probe filters for particle data.
> https://twiki.cscs.ch/twiki/bin/view/ParaViewMeshless
> has some details about the old stuff.
>
> As you're at ETHZ I can help you with specific requirements. Contact me
> off list if you want our probe stuff to be optimized for your needs
>
> JB
>
>
> > Hi John
> >
> > Okay, I introduced a _very_ ugly hack in vtkPointLocator just for a
> > quick test. As a result, my filter was roughly twice as fast
> > The algorithm I'm working on is basically simple sph interpolation.
> > Find closest neighbours, calculate kernel and interpolate the data
> > There were a few issues I had to kindof ignore for the moment:
> > - vtkPointLocator inherits from vtkLocator the this->DataSet member,
> > which is of type vtkDataSet. vtkDataSet has no GetPoints() method, so
> > I had to do a dirty cast
> > - I cast the point to float atm because the points are in float and
> > there is no Distance function that works on float*, double*. Thus
> > points in double are completely unsupported
> >
> > So all in all - a very ugly hack, but it clearly shows what kind of
> > potential there is. This also of course applies the kd-tree
> > implementation and other locators as it just as much uses GetPoint
> >
> > Cheers
> > Benjamin
> >
> > John Biddiscombe wrote:
> >> Benjamin
> >>
> >> OK I see the problem
> >>
> >> Solution
> >> 1) Rewrite vtkPointLocator to not use GetPoint()/GetTuple()
> >> 2) there is no 2)
> >>
> >> Point locator could be quite easily changed. all you need do is
> >> 1) At the start, get the Points array, it can be either float or
> >> double. find out which and store the points data pointer
> >> 2) Modify the main loop to be templated over type float/double and
> >> remove GetPoint, replace with data[n] etc...
> >>
> >> try and see if it runs any faster. It's been a while since I looked
> >> at the PointLocator code, so it might be a bit more messy than that.
> >> (Actually, I'm sure it's more messy as there are many GetXXX
> >> functions all implemented individually as I recall).
> >>
> >> Sorry that I don't have a better solution. Perhaps you could have a
> >> play with KdTree, it is a point locator too and might be implemented
> >> more efficiently. Many of these classes (vtkPointLocator) date back
> >> to the origins of vtk and then double precision wasn't even used for
> >> points as I recall!
> >>
> >> What algorithm are you implementing?
> >>
> >> JB
> >>> Hi John
> >>>
> >>> Thanks for the reply. I've got a few comments because there still
> >>> are some issues with this
> >>>
> >>> - One performance bottleneck is the vtkPointLocator. It can't use
> >>> the GetPointer method because it operates on vtkPoints which wraps
> >>> around arrays and it doesn't seem to offer that interface. Why is
> >>> there a vtkPoints interface anyway (Roughly 50% of the time spent in
> >>> GetClosestNPoints goes to GetPoint and because of this, the code
> >>> isn't even race free)
> >>> - Any GetPoint Method currently wraps around GetTuple. And they're
> >>> used really all over the place
> >>> - GetPointer is not component sensitive - so retreiving tuple i
> >>> results in arr->GetPointer(i*arr->GetNumberOfComponents()). An
> >>> tuple-sensitive arr[i] operator would be a lot nicer no?
> >>>
> >>> Cheers
> >>> Benjamin
> >>>
> >>> John Biddiscombe wrote:
> >>>> Benjamin
> >>>>
> >>>> The GetTuple interface is only intended if you really don't know
> >>>> what type of data you are expecting. You should use the GetPointer
> >>>> cast to float/double etc - this gives you raw access to the array
> >>>> in native form. Only use the GetTuple in emergencies.
> >>>>
> >>>> vtkDataArrayTemplate is already remplated over types for the bulk
> >>>> of work in creating the class definitions for each type. You should
> >>>> look at some of the imageing filters for examples of how to get a
> >>>> scalar pointer then execute on whatever type you need.
> >>>>
> >>>> I'm keeping this reply brief as timeis too short. Hopefully someone
> >>>> else will give you further details if you need them.
> >>>>
> >>>> JB
> >>>>> Hi
> >>>>>
> >>>>> I noticed that my code ran very slow so I did some profiling and I
> >>>>> noticed to my horror, that about 50% of all time is spent inside
> >>>>> the GetTuple (and it's wrappers). Looking at the code I noticed
> >>>>> that for every access a copy of a tuple is generated which is
> >>>>> pretty insane when all you want is a distance to another point...
> >>>>> I do realize that in vtk, you never know whether you work with
> >>>>> floats or doubles or ints etc, but I'm sure there are other ways
> >>>>> that are not this hard on performance
> >>>>>
> >>>>> Are there plans on improving this? I've looked at a few ideas and
> >>>>> my interest was caught by Eigen2, a very fast Math Library making
> >>>>> extensive use of templates challenging even the mkl in terms of
> >>>>> speed. They make heavy use of template expressions so there are no
> >>>>> intermediate copies at any point. I'd guess something like this
> >>>>> would be very much doable for vtk
> >>>>>
> >>>>> Even though it would be quite some work, I imagine all of vtk
> >>>>> would gain significantly from this - in terms of genericity,
> >>>>> design and performance
> >>>>>
> >>>>> Any comments?
> >>>>>
> >>>>> Cheers
> >>>>> Benjamin
> >>>>> _______________________________________________
> >>>>> vtk-developers mailing list
> >>>>> vtk-developers at vtk.org
> >>>>> http://www.vtk.org/mailman/listinfo/vtk-developers
> >>>>
> >>>>
> >>>
> >>
> >>
> >
>
>
> --
> John Biddiscombe,                            email:biddisco @ cscs.ch
> http://www.cscs.ch/
> CSCS, Swiss National Supercomputing Centre  | Tel:  +41 (91) 610.82.07
> Via Cantonale, 6928 Manno, Switzerland      | Fax:  +41 (91) 610.82.82
>
>
>
>
> ------------------------------
>
> _______________________________________________
> vtk-developers mailing list
> vtk-developers at vtk.org
> http://www.vtk.org/mailman/listinfo/vtk-developers
>
>
> End of vtk-developers Digest, Vol 55, Issue 13
> **********************************************
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20081124/6b9fa7ae/attachment.html>