[vtkusers] slow vtkCleanPolyData filter

[Karl Merkley]

Thanks for the hint!   That cut down the time to something like 6  
seconds.

Maybe I should have used the variable name minCellSize.   What I'm  
looking to do is to merge cells that are within around half the  
minimum size.   It does not end up collapsing everything to a point!  
(thankfully . . .)

My data set is planar  on the XY plane, so I set the divisions to 100,  
100, 1.  It doesn't seem to make sense to have divisions in the z  
direction if there is no z-variation and that appears to match the  
filter.   Is my reasoning right?

    Thanks again for the help,

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