[vtkusers] slow vtkCleanPolyData filter

[John Biddiscombe]

Try adding something like

#include "vtkMergePoints.h"
...
    vtkSmartPointer<vtkMergePoints> locator = blah
    locator->SetDivisions(100,100,100);
    cleanData->SetLocator(locator);
also you will need to set tolerance.
...
to increase the number of buckets (by a factor of 8 in this case). If your data is unevenly distributed, you may find that the locator is really doing an O(N)^2 check most of the time. The PointLocator divides space equally and is a bit rubbish on some datasets.

When tolerance is exactly 0.0, it is much faster, but when >0.0, it has to compare every point in the bucket, and possibly a neighbour bucket to ensure the distance is not exceeded. If the bucket size is very large (comparable to a bucket)....then O(N)^2 essentially.

In fact looking again at your code, you have "minMeshSize*.54" - does this mean that the tolerance is half the datset size? if so, you might as well just have one bucket. All tests will search every point! No need to use a locator at all. Not much you can do if the tolerance is so large that all points are merged into one.

JB





> I have a vtkPolyData with a couple of thousand quads that are approximately uniform size.   It is a relatively small set.   I apply the vtkPolyData filter with a real tolerance and it seems to take extraordinarily long.   I don't have exact timings at this point but it is on the order 5 to 10 seconds.  I understand that the vtkPointLocator is being used and that it is slower but with this number of points it would be faster to do an O(n^2) compare than the current logic.  
>
> Here is just a code snippet of what I'm doing.  During the 5-10 second hang I can break into the debugger and it is typically doing lookups in the vtkPointLocator.   
>
>     // data possibly contains nearly coincident points.  let's merge them
>     // but don't merge smaller than the smallest mesh size.
>     vtkSmartPointer<vtkCleanPolyData> cleanData = vtkSmartPointer<vtkCleanPolyData>::New();
>     cleanData->SetInput(wellGrid);
>     cleanData->SetToleranceIsAbsolute(1);
>     cleanData->SetAbsoluteTolerance(minMeshSize*.54);
>     cleanData->SetConvertLinesToPoints(1);  // convert degenerate lines to points
>     cleanData->Update();
>
> This gives me the desired results but it seems terribly slow.  The tolerance is quite high because I want to merge points that are close but I don't want to merge entire cells. Am I abusing this filter in some way?  Is there a better way to accomplish this kind of operation?
>
>   Thanks,
>      Karl
> _______________________________________________
> This is the private VTK discussion list.
> Please keep messages on-topic. Check the FAQ at: http://www.vtk.org/Wiki/VTK_FAQ
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers
>   


-- 
John Biddiscombe,                            email:biddisco @ cscs.ch
http://www.cscs.ch/
CSCS, Swiss National Supercomputing Centre  | Tel:  +41 (91) 610.82.07
Via Cantonale, 6928 Manno, Switzerland      | Fax:  +41 (91) 610.82.82