[vtkusers] Performance issue with vtkAssembly::UpdatePaths

[Andrew Cunningham]

There is, I think , a serious o(n!) (factorial) problem with the vtkAssembly::UpdatePaths code.


The problem is
1) vtkAssembly::GetMTime()  recursively descends through the "scene graph" touching all nodes
2)  vtkAssemblyPath::GetMTime() runs through all it's items (some of which will be  vtkAssembly's ) and calls GetMTime()  on each item

So for example, if you have a vtkAssembly:: tree that is with various mixtures of vtkAssembly's  and vtkActors.

Firstly, the call this->GetMTime() causes a recursive transversal of the graph starting at 'this', calling GetMTime() on every node. This is o(n).

Then, this->Paths->GetMTime() , is called. This iterates through each node of the vtkAssemblyPath calling GetMTime(). Each time it encounters a node that is a  vtkAssembly, then it will trigger a recursive traversal starting at that node. The number of calls to GetMTime will be on the order of n!

If you have a complex scene graph, this can actually  become a huge bottleneck.


Here is the code snippet.

// Build the assembly paths if necessary. UpdatePaths()
// is only called when the assembly is at the root
// of the hierarchy; otherwise UpdatePaths() is called.
void vtkAssembly::UpdatePaths()
{
  if ( this->GetMTime() > this->PathTime ||
    (this->Paths != NULL && this->Paths->GetMTime() > this->PathTime) )
    {
....


Andrew