[vtk-developers] Voronoi2D

[Will Schroeder]

If all goes well, I'm thinking we'll likely maintain the current Delaunay
algorithms as reference implementations (as they are classic, serial
insertion approaches) and extend the new Voronoi classes to optionally
output Delaunay triangulations. This will likely take a while and we may
not replicate all features found in vtkDelaunay classes (e.g., alpha
shapes). However I've been down the path of mesh generation before and it
is littered with the bodies of gotchas and numerical instabilities so I
reserve the right to be cautious :-) However if David can successfully pull
off the 3D implementation in vtk-m it is likely to be very fast and more
robust, which is why we are quite excited about the work. And needless to
say I'm hoping community members will help out in any way they can.

On Sat, Jun 16, 2018 at 2:40 AM Chiranjib Sur <sur.chiranjib at gmail.com>
wrote:

> This is very interesting. Will the implementation of Delaunay
> triangulations API's be improved following this?
> I experienced Delaunay3D for large datasets is very slow.
>
> Thanks and regards,
> Chiranjib
>
> ------
> Using hand held device. Sorry for the typo, if any.
>
> On Sat, Jun 16, 2018, 10:46 AM Andrew Maclean <andrew.amaclean at gmail.com>
> wrote:
>
>> +1!
>> I just  had a play with it, the tests  for Voronoi2D are really
>> impressive.
>>
>> ---------- Forwarded message ----------
>>> From: Will Schroeder <will.schroeder at kitware.com>
>>> To: vtk-developers <vtk-developers at vtk.org>
>>> Cc:
>>> Bcc:
>>> Date: Fri, 15 Jun 2018 05:32:10 -0400
>>> Subject: [vtk-developers] Voronoi2D
>>> FYI I pushed in some code today that may be of interest to folks on this
>>> list:
>>>
>>> - vtkVoronoi2D - parallel Voronoi tessellation in 2D
>>> - vtkStaticCleanPolyData - faster, threaded clean poly data (we've seen
>>> anywhere from 50-150x on a 4 core laptop)
>>> - vtkStaticPointLocator2D - 2D version of the fast, parallel
>>> vtkStaticPointLocator
>>> - vtkSpheres - an implicit function represents union of spheres (great
>>> for visualizing the Voronoi Flower error metric and related stuff like
>>> Delaunay spheres)
>>> - Some fun tests e.g. TestVoronoi2D2.py, which includes functions
>>> stretching numerical stability (lissajous, quarterDisk, Kuzmin) provided by
>>> David and Joachim Pouderoux).
>>>
>>> While the code that has been pushed is very useful in its current state
>>> there is more work to be done. Specifically the Voronoi algorithm is a
>>> novel parallel algorithm that seems to be surprisingly robust and very
>>> fast. (I've been working with Dave Thompson and he is working on a 3D
>>> version in vtk-m; we are preparing some publications.) We also want to
>>> extend the Voronoi class to produce Delaunay triangulations, maybe support
>>> constrained boundaries etc. Also because these are parallel algorithms
>>> there are some quirks to be worked out (for example the order of execution,
>>> which in some parallel systems is not always predictable, can affect
>>> results).
>>>
>>> The point is if you have a request or see something amiss please let me
>>> know.
>>>
>>> Best,
>>> W
>>>
>>>
>>>
>>> --
>>> William J. Schroeder, PhD
>>> Kitware, Inc. - Building the World's Technical Computing Software
>>> 28 Corporate Drive
>>> Clifton Park, NY 12065
>>> will.schroeder at kitware.com
>>> http://www.kitware.com
>>> (518) 881-4902
>>>
>>>
>>>
>> --
>> ___________________________________________
>> Andrew J. P. Maclean
>>
>> ___________________________________________
>> _______________________________________________
>> Powered by www.kitware.com
>>
>> Visit other Kitware open-source projects at
>> http://www.kitware.com/opensource/opensource.html
>>
>> Search the list archives at: http://markmail.org/search/?q=vtk-developers
>>
>> Follow this link to subscribe/unsubscribe:
>> https://public.kitware.com/mailman/listinfo/vtk-developers
>>
>>

-- 
William J. Schroeder, PhD
Kitware, Inc. - Building the World's Technical Computing Software
28 Corporate Drive
Clifton Park, NY 12065
will.schroeder at kitware.com
http://www.kitware.com
(518) 881-4902
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://public.kitware.com/pipermail/vtk-developers/attachments/20180618/9cf6a88a/attachment.html>