[vtk-developers] Better than O(n) prop operations on vtkRenderer

Bill Lorensen bill.lorensen at gmail.com
Thu Dec 13 20:53:09 EST 2018


Is there an stl container that has similar performance. Adding a
 boost dependency in a core vtk class adds complexity to the build process.

On Thu, Dec 13, 2018, 4:26 PM Paul Harris <harris.pc at gmail.com wrote:

> I didn't bother with the benchmarks, the improvement was so significant
> for my situation, it went from 5-10 seconds down to milliseconds for some
> operations.
>
> I was adding hundreds or thousands of polydata actors (one per 3d model
> loaded from files),
> and there were a few situations where VTK would to search the collection
> looking for a particular actor.
>
> I recall that ::Remove() (or similar) was used in RemoveAll() ? Or
> destruction?  I can't quite remember.
> There were a couple of other places where it would iterate through the
> list looking for a particular actor.
> I think during destruction was a problem for me for this reason.
> So it was effectively O(n^2) for a RemoveAll() operation.
>
> eg If the list of actors / model files changed, I would need to remove
> lots of actors and add new actors to match the new files.
> If the file list changed significantly, it would take a long long time
> just because of the actor removal.
> If the user ticked off a whole folder of files, it might cause the GUI to
> pause for multiple seconds.
> Significant enough that it became a road block and I had to spend some
> time on the problem.
>
> Perhaps I could've structured it differently by putting all the polydata
> into one actor,
> but as its implemented it works very quickly - no need to recompute
> polygons and vertices just to switch off an actor/model from the list of
> models.
>
>
> On Fri, 14 Dec 2018 at 08:09, Bill Lorensen <bill.lorensen at gmail.com>
> wrote:
>
>> Do you have benchmarks that show the differences?
>>
>> On Thu, Dec 13, 2018, 3:47 PM Paul Harris <harris.pc at gmail.com wrote:
>>
>>> I had to hack vtkCollection for this exact reason.
>>>
>>> It keeps an ordered linked list because its design allows for the same
>>> element to be added multiple times.
>>>
>>> I replaced that ordered linked list with a boost::multi_index, so it
>>> kept the old interface, multiple-entry feature, and addition-order,
>>> but also added fast lookups and fast removal.
>>>
>>> I'm happy to share the code.  It was hacked into an older VTK version,
>>> and added a boost dependency, so it'll need some cleanup in that respect.
>>> But I did check the newer VTK code when I hacked it in July and it didn't
>>> look like it had changed much.  So apart from the boost dependency, it
>>> might be easy to bring into the latest VTK.
>>>
>>>
>>> On Fri, 14 Dec 2018 at 07:19, Todd Martin via vtk-developers <
>>> vtk-developers at public.kitware.com> wrote:
>>>
>>>> My solution to this kind of problem in the past has been to build a
>>>> (non-clustered) sorted index for fast lookup on the collection, without
>>>> changing the underlying collection itself. In fact multiple indicies could
>>>> be built and (if desired) attached to the collection in a list. Of course
>>>> it means that each index needs to be rebuilt, when anything is added to or
>>>> removed from the collection. The most efficient way to do that is to set a
>>>> flag when anything changes and then only rebuild the index the next time it
>>>> is accessed.
>>>>
>>>>
>>>>
>>>> Todd Martin, PhD.
>>>> *Freelance Engineer/Software Architect.*
>>>>
>>>>
>>>>
>>>> On Friday, 14 December 2018, 12:06:59 PM NZDT, David Gobbi <
>>>> david.gobbi at gmail.com> wrote:
>>>>
>>>>
>>>> Hi Elvis,
>>>>
>>>> I don't think there are any fans of vtkCollection, but replacing it
>>>> with something modern would be lot of work and would provide
>>>> far less benefit than e.g. the recent reworking of the VTK data
>>>> arrays to provide flexible memory access patterns.
>>>>
>>>> Also, given the cost for vtkRenderer to render a bunch of props,
>>>> you would have to be doing many hundreds (thousands?) of
>>>> insertions/removals per render before the time required for those
>>>> operations becomes significant to overall app performance.
>>>>
>>>>   David
>>>>
>>>>
>>>> On Thu, Dec 13, 2018 at 3:33 PM Elvis Stansvik <
>>>> elvis.stansvik at orexplore.com> wrote:
>>>>
>>>> Hi all,
>>>>
>>>> The props of a vtkRenderer are kept in a vtkCollection (and probably
>>>> have been since VTKs childhood), meaning linear time
>>>> search/insert/remove.
>>>>
>>>> I realize the use of vtkCollection is pervasive in these classes, and
>>>> also shines through in their API, so this is a bit of a long shot,
>>>> but, is there any chance that it'll at some point be converted to use
>>>> a sorted data structure, to permit logarithmic operations?
>>>>
>>>> Has anyone else had the need to rapidly insert/remove/check for props
>>>> in a renderer with a large amounts of props in it? Has the idea of
>>>> having vtkRenderer backed by something else been discussed before?
>>>>
>>>> Cheers,
>>>> Elvis
>>>>
>>>> _______________________________________________
>>>> Powered by www.kitware.com
>>>>
>>>> Visit other Kitware open-source projects at
>>>> http://www.kitware.com/opensource/opensource.html
>>>>
>>>> Search the list archives at:
>>>> http://markmail.org/search/?q=vtk-developers
>>>>
>>>> Follow this link to subscribe/unsubscribe:
>>>> https://public.kitware.com/mailman/listinfo/vtk-developers
>>>>
>>>> _______________________________________________
>>>> Powered by www.kitware.com
>>>>
>>>> Visit other Kitware open-source projects at
>>>> http://www.kitware.com/opensource/opensource.html
>>>>
>>>> Search the list archives at:
>>>> http://markmail.org/search/?q=vtk-developers
>>>>
>>>> Follow this link to subscribe/unsubscribe:
>>>> https://public.kitware.com/mailman/listinfo/vtk-developers
>>>>
>>>> _______________________________________________
>>> Powered by www.kitware.com
>>>
>>> Visit other Kitware open-source projects at
>>> http://www.kitware.com/opensource/opensource.html
>>>
>>> Search the list archives at:
>>> http://markmail.org/search/?q=vtk-developers
>>>
>>> Follow this link to subscribe/unsubscribe:
>>> https://public.kitware.com/mailman/listinfo/vtk-developers
>>>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://public.kitware.com/pipermail/vtk-developers/attachments/20181213/32359813/attachment.html>


More information about the vtk-developers mailing list