MantisBT - VTK
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0002929VTK(No Category)public2006-03-02 05:202016-08-12 09:54
ReporterJens Henrik Goebbert 
Assigned ToDave DeMarle 
PrioritylowSeverityfeatureReproducibilityalways
StatusclosedResolutionmoved 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Project
Type
Summary0002929: faster vtkCellLocator with buckets = sqrt(NumberOfCells)
DescriptionI think that vtkCellLocator is faster if it sets the number of buckets to sqrt(NumberOfCells) instead of fixed 25.
(the same is true for vtkPointLocator, too)
Steps To Reproduce
Additional Information
TagsNo tags attached.
Relationships
Attached Files
Issue History
Date ModifiedUsernameFieldChange
2008-11-30 09:13Mathieu MalaterreAssigned ToMathieu Malaterre => David Cole
2011-01-19 09:57David ColeAssigned ToDavid Cole =>
2011-06-16 13:11Zack GalbreathCategory => (No Category)
2013-06-05 17:46Jean-Christophe Fillion-RobinNote Added: 0030952
2013-07-22 19:18Dave DeMarleNote Added: 0031220
2013-07-22 19:18Dave DeMarleStatusbacklog => expired
2013-07-22 19:18Dave DeMarleAssigned To => Dave DeMarle
2016-08-12 09:54Kitware RobotNote Added: 0036838
2016-08-12 09:54Kitware RobotStatusexpired => closed
2016-08-12 09:54Kitware RobotResolutionopen => moved

Notes
(0003824)
Mathieu Malaterre   
2006-03-02 13:09   
Do you have a way to test/reproduce ?
(0003828)
Jens Henrik Goebbert   
2006-03-02 18:48   
Suppose...
(1)... it would take one step to check if a bucket contains the searched cell.
(2)... it would take one step to check if a cell is the one we are searching for.

In average we would have to check half the buckets to find the correct one and
half the cells in that bucket to find the searched cell.
We would need
    steps = buckets/2 + cells_per_bucket/2
with
    number_of_cells = buckets*cells_per_bucket

=> if "buckets" and "cells_per_bucket" would be the same size, "steps" would be minimum.

Of course (1) and (2) do not take the same amount of calculation-time. So my thoughts may not
be exact. But simply having 25 buckets seems to me worse.
(0030952)
Jean-Christophe Fillion-Robin   
2013-06-05 17:46   
Could you check if the performance issue have been fixed in either VTK 5.10 or VTK 6 ? Ideally, providing a small program allowing to benchmark the proposed change would be helpful.

In addition, if you would like, you could submit a patch using Gerrit. This would make the review and integration easier. For more details see http://www.vtk.org/Wiki/VTK/Git/Develop [^]
(0031220)
Dave DeMarle   
2013-07-22 19:18   
If the bug persists in 6.0.0, please reopen.
(0036838)
Kitware Robot   
2016-08-12 09:54   
Resolving issue as `moved`.

This issue tracker is no longer used. Further discussion of this issue may take place in the current VTK Issues page linked in the banner at the top of this page.