[vtkusers] slow vtkCleanPolyData filter

[Karl Merkley]

>> 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
>> ________________________________
On Aug 12, 2008, at 12:21 AM, John Biddiscombe wrote:

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

Just to wrap up this thread . . .  I actually had to use a  
vtkPointLocator instead of the vtkMergePoints because I wanted an  
absolute tolerance.    Increasing the number of divisions dramatically  
improved the speed.

Karl