[vtkusers] Convex hull of spherical point cloud has holes

Thu Aug 10 22:22:50 EDT 2017

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 --------------
A non-text attachment was scrubbed...
Name: MinWorkingEx.py
Type: text/x-python
Size: 1839 bytes
Desc: not available
URL: <http://public.kitware.com/pipermail/vtkusers/attachments/20170810/06f226c9/attachment.py>
-------------- next part --------------
# vtk DataFile Version 4.1
vtk output
ASCII
DATASET POLYDATA
POINTS 72 float
2.09299 0.33088 -0.39825 1.6453 0.643098 -1.23616 1.70037 1.2495 -0.442911 
1.06241 1.45408 -1.18558 0.853381 0.728438 -1.84114 0.161724 1.41545 -1.61834 
-0.468113 2.09732 -0.175458 0.300949 1.97804 -0.803411 -0.626043 1.74646 -1.09847 
0.6262 1.7464 1.09847 0.468301 2.09728 0.175458 -0.300772 1.97807 0.803411 
1.37968 1.10319 1.23617 1.93236 0.847638 0.442921 1.33319 1.64702 0.398259 
-1.33304 1.64714 -0.398259 -1.37958 1.10332 -1.23617 -1.93228 0.847812 -0.442921 
-0.161597 1.41546 1.61834 -1.06228 1.45418 1.18558 -0.853316 0.728514 1.84114 
-1.70026 1.24965 0.442911 -2.09296 0.331068 0.39825 -1.64524 0.643246 1.23616 
0.104999 0.567724 2.07734 -0.544171 -0.192925 2.07734 0.439155 -0.374799 2.07734 
1.05756 0.374732 1.84115 1.30662 -0.567787 1.61835 1.79049 0.192869 1.18559 
-0.72822 -1.64705 1.18559 -0.204261 -1.10325 1.84114 -1.14503 -0.847674 1.61834 
0.265547 -1.74644 1.23617 -0.232105 -2.09729 0.442915 0.759764 -1.97809 0.398258 
1.19932 -1.41551 1.09848 1.58215 -1.4542 0.175461 1.86344 -0.728559 0.803416 
-1.82553 -0.330892 1.09847 -2.05045 -0.64308 0.175451 -1.56267 -1.24951 0.803407 
-0.265704 -1.74642 -1.23617 0.231917 -2.09731 -0.442915 -0.759942 -1.97802 -0.398258 
-1.19945 -1.4154 -1.09848 -1.58228 -1.45406 -0.175461 -1.8635 -0.728392 -0.803417 
0.204162 -1.10326 -1.84114 1.14496 -0.847776 -1.61834 0.728073 -1.64711 -1.18559 
2.05039 -0.643264 -0.175451 1.56256 -1.24965 -0.803407 1.8255 -0.331056 -1.09847 
-0.439188 -0.374759 -2.07734 -0.104949 0.567733 -2.07734 0.544154 -0.192973 -2.07734 
-1.30667 -0.56767 -1.61835 -1.79047 0.193029 -1.18559 -1.05753 0.374827 -1.84115 
-0.760634 1.3176 -1.99154 -0.760752 -1.31754 -1.99154 -2.46167 0.000110329 -0.470145 
1.5214 -6.81525e-05 -1.99153 2.46167 -0.000110335 0.470145 1.23074 -2.13193 -0.470134 
-1.23093 -2.13182 0.470134 -1.5214 6.81664e-05 1.99153 0.760634 -1.3176 1.99154 
0.760752 1.31754 1.99154 -1.23074 2.13193 0.470134 1.23093 2.13182 -0.470134 

POINT_DATA 72
NORMALS PointNormals double
0.94553368432 0.18910660529 -0.26496177771 0.78405862855 0.35773532998 -0.50722529579 0.83862196559 0.50312372408 -0.20875755577 
0.47835764175 0.62004070162 -0.62187096324 0.34064025315 0.41025176095 -0.84596554928 0.16203922386 0.66872894226 -0.72563413076 
-0.15139105539 0.97783566905 -0.14463109167 0.053678257752 0.91341969646 -0.40346388037 -0.27685262676 0.85789740302 -0.43285640684 
0.27692932868 0.85787207687 0.43285753621 0.15147913613 0.97782196711 0.144631504 -0.05359830278 0.91342422147 0.40346426554 
0.70187687409 0.50008703194 0.50722954775 0.85507145162 0.47462740128 0.20876216749 0.63660095473 0.72424583112 0.26496641397 
-0.63653687657 0.72430226382 -0.26496610234 -0.70183511182 0.5001458299 -0.507229361 -0.85502805043 0.47470557246 -0.20876219114 
-0.16197141142 0.66874499688 0.72563447481 -0.4783016704 0.62008456354 0.62187028081 -0.34060898817 0.41027308652 0.84596779587 
-0.83857597135 0.50320039033 0.20875753267 -0.94551685553 0.18919030769 0.26496207916 -0.78402859711 0.35780088238 0.50722547992 
-0.0082788878824 0.19407405734 0.98095194596 -0.16393765474 -0.10420444477 0.98095151718 0.17220848886 -0.089869640139 0.98095243725 
0.52560794361 0.089837476351 0.84597016345 0.66013288875 -0.19410287148 0.72563671659 0.77615727195 0.10417763286 0.62187370906 
-0.29786070719 -0.7242622139 0.621870762 -0.18500590095 -0.5001105867 0.84596821317 -0.49816743492 -0.47464214579 0.72563354403 
0.082147558581 -0.85788792856 0.507227839 -0.01649719425 -0.97782779752 0.2087597686 0.3089137252 -0.91343614623 0.2649655018 
0.604472574 -0.66876490414 0.43285841827 0.77107850318 -0.62009610852 0.14463318472 0.81784607861 -0.41029558084 0.40346663808 
-0.88140545654 -0.18910718492 0.43285435632 -0.92255882689 -0.3577258627 0.14462855211 -0.76425108836 -0.50312865194 0.40346230746 
-0.082219353166 -0.85788114612 -0.50722767778 0.01640779864 -0.97782929073 -0.20875981975 -0.3089946325 -0.91340886168 -0.26496522128 
-0.60453285212 -0.66871112812 -0.43285731811 -0.77113440767 -0.62002667498 -0.14463280273 -0.8178821308 -0.41022406378 -0.40346627815 
0.18497178599 -0.50012697611 -0.84596598404 0.49811961313 -0.47469282558 -0.72563322164 0.29779472569 -0.72428873818 -0.62187146992 
0.92252665033 -0.35780898992 -0.14462816516 0.76420718541 -0.50319562125 -0.4034619493 0.88138903144 -0.18918626232 -0.43285324696 
-0.17221875164 -0.089849688021 -0.98095246324 0.0083012803662 0.19407299549 -0.9809519668 0.16392552278 -0.10422327973 -0.98095154363 
-0.66015287986 -0.19403609608 -0.72563638872 -0.77614726197 0.10424805402 -0.62187440129 -0.52560509432 0.089875239119 -0.84596792269 
-0.30351736748 0.52573663949 -0.79465602214 -0.30353934114 -0.52572393812 -0.79465603204 -0.98224647852 4.4937898655e-05 -0.18759491839 
0.60706322495 -1.2678738313e-05 -0.79465353504 0.98224637254 -4.430574591e-05 0.1875954735 0.491085093 -0.85067331443 -0.1875908941 
-0.4911623247 -0.8506286058 0.18759143312 -0.60706405439 2.7283884489e-05 0.79465290103 0.30350513 -0.5257446625 0.79465538815 
0.30355239996 0.52571735629 0.79465539813 -0.49108558792 0.85067290629 0.18759144928 0.49116292465 0.85062838182 -0.18759087797 