[vtkusers] Convex hull of spherical point cloud has holes

Wed Sep 13 13:57:25 EDT 2017

Hi everyone.

I finally found a working solution to my problem which I would like to 
share in case it may help someone else.
I had a curious observation that the point clouds (generated as a vector 
of doubles through some optimization) for which I was not able to 
programatically generate a convex hull using VTK C++ functions, if I 
wrote the point coordinates to a VTK file and opened it in Paraview and 
applied vtkDelaunay3D filter, I was getting a proper convex hull. Thus, 
I guessed that the issue may be due to some floating point corner cases 
because my point co-ordinates were stored as double in my original 
program but in the course of writing to file and reading back there 
might be some loss of precision which seems to fix the issue. With this 
as an hypothesis, in my original program, I rounded off all the point 
coordinates to just 2 decimal places and now I get proper convex hull 
without using Paraview! If you noticed my original use case scenario, I 
am simply interested in the topology of the cells and this loss of 
precision is not a deal-breaker. So this solution works well enough for me.

Thanks and regards,
Amit

On 08/10/2017 07:22 PM, Amit wrote:
> I am sorry. I think I spoke too soon that my problem is solved. My 
> code is part of a larger C++ project. I am generate several point 
> clouds based on an optimization criteria. I triangulate every point 
> cloud. But the issue of missing triangles does not happen for all the 
> point clouds consistently. It happens only for a few of them. Changing 
> the alpha value to something non-zero helped resolve the issue in one 
> of the point-clouds but it started happening in some other ones. I 
> tried multiple alpha-values but I am not able to figure out one that 
> works for all. Sometimes, if I print out the point cloud data for 
> which I get missing triangles to a VTK file and open it in Paraview, 
> when I apply my triangulation algorithm using a programmable filter, 
> it works there. So I suspect there may also be some floating point 
> corner case which gets resolved when writing to a file and re-reading 
> in paraview. I am only guessing. It was hard to generate a minimum 
> working example.
>
> Finally, I think I have a minimum working Python code. Please find 
> attached two files:
> 1. Sample.vtk -- contains a culprit point cloud
> 2. MinWorkingEx.py -- a Python code to triangulate the point cloud by 
> projecting them to a unit sphere first
>
> Repeating my question: Since I am trying to generate a convex hull on 
> points located on a unit sphere, why should there be any missing 
> triangles ever?
>
> Regards,
> Amit
>
>
> On 08/09/2017 08:34 PM, Amit wrote:
>> Thank you Bill and David for your replies.
>>
>> David: I did not use vtkCleanPolyData. I had read the doc multiple 
>> times but I did not have the patience to understand the significance 
>> of alpha.
>>
>> Bill: You are right. I was using the default value of alpha=0.0. Just 
>> out of trial and error I set alpha=1.0 and the issue got resolved. I 
>> think that as I am working with unit spheres, alpha_radius=1.0 is 
>> sufficiently large value so that all faces of all tetrahedron get 
>> included in the output convex hull.
>>
>> Thanks once again for the pointers.
>>
>> Regards,
>> Amit
>>
>>
>> On 08/09/2017 04:03 PM, Bill Lorensen wrote:
>>> If you save your polydata in a .vtp file you can try this example:
>>> https://lorensen.github.io/VTKExamples/site/Cxx/Modelling/Delaunay3D/
>>>
>>> It reports the # of verts, lines, triangles and tets.
>>>
>>>
>>> On Wed, Aug 9, 2017 at 4:56 PM, Bill Lorensen 
>>> <bill.lorensen at gmail.com> wrote:
>>>> I assume Alpha=0.0 for the Delaunay filter?
>>>>
>>>> Can you post a small, standalone compilable program that produces 
>>>> this output?
>>>>
>>>> Bill
>>>>
>>>>
>>>> On Wed, Aug 9, 2017 at 2:18 PM, Amit via vtkusers 
>>>> <vtkusers at vtk.org> wrote:
>>>>> Dear all.
>>>>> I have a point cloud made up of points lying on surface of a unit 
>>>>> sphere
>>>>> stored in a vtkPolyData. I want to get the convex hull of this 
>>>>> point cloud
>>>>> using the vtkDelaunay3D filter. Then using vtkDataSetSurfaceFilter 
>>>>> I want to
>>>>> extract the surface of the convex hull. This way, I can get a 
>>>>> triangulation
>>>>> of the point cloud as a hollow spherical shell. Kindly open the 
>>>>> attached
>>>>> UnstructuredGrid file in Paraview. It represents the output of 
>>>>> vtkDelaunay3D
>>>>> filter made up of tetrahedrons. But the surface of the convex-hull 
>>>>> has some
>>>>> missing triangles. Using the SpreadSheet View, I can see that 
>>>>> cells with Ids
>>>>> 60, 61, 64 have triangular faces in the missing region. Hence, I 
>>>>> would not
>>>>> have expected these "hole" in the surface. Can somebody explain 
>>>>> why the
>>>>> triangles are not being rendered? When I extract surface from this
>>>>> unstructured grid I get a spherical shell with missing triangles 
>>>>> as holes.
>>>>> Regards,
>>>>> Amit
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> Powered by www.kitware.com
>>>>>
>>>>> Visit other Kitware open-source projects at
>>>>> http://www.kitware.com/opensource/opensource.html
>>>>>
>>>>> Please keep messages on-topic and check the VTK FAQ at:
>>>>> http://www.vtk.org/Wiki/VTK_FAQ
>>>>>
>>>>> Search the list archives at: http://markmail.org/search/?q=vtkusers
>>>>>
>>>>> Follow this link to subscribe/unsubscribe:
>>>>> http://public.kitware.com/mailman/listinfo/vtkusers
>>>>>
>>>>
>>>>
>>>> -- 
>>>> Unpaid intern in BillsBasement at noware dot com
>>>
>>>
>>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtkusers/attachments/20170913/debe4753/attachment.html>