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

[Paul Harris]

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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://public.kitware.com/pipermail/vtk-developers/attachments/20181214/80aa4f72/attachment-0001.html>