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

[Paul Harris]

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/897e7882/attachment-0001.html>