[vtk-developers] perf improvements to vtkDijkstra* classes

[Karthik Krishnan]

Hi Dean:

Thanks a lot for the contrib.

I took a look at vtkDijkstraImageGeodesicPath and the first input 
polydata is required but isn't used. The second input (cost function 
image) is the one used.

I think you can have a class deriving from vtkPolyDataAlgorithm that has 
its first input as something other than vtkpolydata. This can be done by 
overriding the method FillInputPortInformation and having the first 
input be a vtkImageData. Can't it ?

If not, maybe we should change vtkGeodesicPath to derive from vtkAlgorithm.

The other changes to vtkDijkstraGraphGeodesicPath look great.

Thanks
--
karthik

Dean Inglis wrote:
>
> Hi Will,
>
> thanks! Been having some fun here.
>
> Hi Karthik,
>
> I made a separate header file: vtkDijkstraGraphInternals that contains
>
> all the replacement stl containers so that 
> vtkDijkstraGraphGeodesicPath and vtkDijkstraImageGeodesicPath
>
> have access. I left the implementation of the binary heap as is in 
> vtkDijkstraGraphGeodesicPath
>
> with the exception that it now uses stl containers. I broke the cost 
> function into “static”
>
> and “dynamic” parts so that edge costs can be calculated more 
> efficiently. I have also
>
> taken the liberty to rename internal containers from things like 
> this->f to this->OpenVertices
>
> as given in vtkDijkstraGraphInternals (see below). I will wait till 
> tomorrow to commit in
>
> case you have any reservations or would like to discuss.
>
> thanks,
>
> Dean
>
> ------------------------------------------------------------------------
>
> *From:* Will Schroeder [mailto:will.schroeder at kitware.com]
> *Sent:* August-26-08 5:14 PM
> *To:* dean.inglis at camris.ca
> *Cc:* Karthik Krishnan
> *Subject:* Re: [vtk-developers] perf improvements to vtkDijkstra* classes
>
> I have no objections and have been doing similar things to other VTK 
> classes. Great work!
> W
>
> 2008/8/26 Dean Inglis <dean.inglis at sympatico.ca 
> <mailto:dean.inglis at sympatico.ca>>
>
> Is there any interest in (or objections to) PIMPL'ing some (or all) of
>
> the storage containers in vtkDijkstraGraphGeodesicPath?
>
> In a test class, I have reimplemented vtkDijkstraGraphGeodesicPath
>
> using the following substitutions and noticed substantial (qualitative)
>
> speed gains in interactivity:
>
> 1) - change containers f and s to vector<bool>
>
> 2) - change containers pre, Heap, and p to vector<int>
>
> 3) - change container for cost; d, to vector<float>
>
> 4) - change container for Adjacency from an array of vtkIdList* to
>
> vector<map<int,float>> for unique insertion of vertex id's and
>
> associated edge costs
>
> Probably most of the improvement comes from item 4) since
>
> you can pre-calculate all edge costs at the time of constructing
>
> the adjacency array, which only needs to be done when the input
>
> changes (not when start and end vertices change).
>
> Dean
>
>
> _______________________________________________
> vtk-developers mailing list
> vtk-developers at vtk.org <mailto:vtk-developers at vtk.org>
> http://www.vtk.org/mailman/listinfo/vtk-developers
>
>
>
>
> -- 
> William J. Schroeder, PhD
> Kitware, Inc.
> 28 Corporate Drive
> Clifton Park, NY 12065
> will.schroeder at kitware.com <mailto:will.schroeder at kitware.com>
> http://www.kitware.com
> 518-371-3971 (phone and fax)
>

-- 
Karthik Krishnan
R & D Engineer,
Kitware Inc,
Ph:  518 371 3971 x119
Fax: 518 371 3971