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

[Elvis Stansvik]

Den fre 14 dec. 2018 kl 00:06 skrev David Gobbi <david.gobbi at gmail.com>:
>
> 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.

Yes, I figured as much. Note that I haven't even profiled/benchmarked
my use case to see whether it's a problem, it was just something that
struck me while reading the code for vtkViewport/vtkRenderer, that
e.g. RemoveViewPort is O(2N) (first checks for presence, then walks
the collection again when doing the removal).

You're probably right David that the time needed for the collection is
negligible to the other things going on.

In my use case I was removing thousands (though not tens of thousands)
of poly actors when the user zooms in with the scroll wheel, which may
happen rather rapidly, so I guess the "other stuff" in my case would
be the freeing of graphics resources et.c. We are using a glyph mapper
to cut down on the number of actors, but there may still be ~1000-2000
or so of them that needs to be removed.

Thanks everyone for your answers. I might do some measurements to see
whether this could really be something that hurts interactivity in our
case.

Elvis

>
>   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