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

[Paul Harris]

No, not without combining a couple of containers

On Fri., 14 Dec. 2018, 9:53 am Bill Lorensen <bill.lorensen at gmail.com wrote:

> 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/20181214/e6096e1f/attachment.html>