[vtk-developers] vtkDataArrayTemplate
Benjamin Schindler
bschindler at student.ethz.ch
Tue Nov 25 04:02:58 EST 2008
Hi Andy
Well, the kdtree locator does not have a findPointsWithinRadius method
(it seems to have one in the cvs version, but not in 5.2), so right now
I can't use this one.
The changes I made to the PointLocator were posted on my last mail to
this list. Did you overlook it? My mailbox says that mail arrived 11/24
05:34 PM (With time shift of course)
The patch is really a very dirty hack and to have it included, it really
should be reworked.
Cheers
Benjamin
Andy Bauer wrote:
> 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
> <mailto:bschindler at student.ethz.ch>>
> Cc: vtk-developers at vtk.org <mailto: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 <mailto: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 <mailto:vtk-developers at vtk.org>
> http://www.vtk.org/mailman/listinfo/vtk-developers
>
>
> End of vtk-developers Digest, Vol 55, Issue 13
> **********************************************
>
>
More information about the vtk-developers
mailing list