Voronoi2D

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Voronoi2D

Will Schroeder-2
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
[hidden email]
http://www.kitware.com
(518) 881-4902

_______________________________________________
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

Reply | Threaded
Open this post in threaded view
|

Re: Voronoi2D

Andrew Maclean-3
+1!
I just  had a play with it, the tests  for Voronoi2D are really impressive.

---------- Forwarded message ----------
From: Will Schroeder <[hidden email]>
To: vtk-developers <[hidden email]>
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
[hidden email]
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

Reply | Threaded
Open this post in threaded view
|

Re: Voronoi2D

chiranjibsur
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 <[hidden email]> wrote:
+1!
I just  had a play with it, the tests  for Voronoi2D are really impressive.

---------- Forwarded message ----------
From: Will Schroeder <[hidden email]>
To: vtk-developers <[hidden email]>
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
[hidden email]
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


_______________________________________________
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

Reply | Threaded
Open this post in threaded view
|

Re: Voronoi2D

Will Schroeder-2
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 <[hidden email]> 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 <[hidden email]> wrote:
+1!
I just  had a play with it, the tests  for Voronoi2D are really impressive.

---------- Forwarded message ----------
From: Will Schroeder <[hidden email]>
To: vtk-developers <[hidden email]>
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
[hidden email]
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
[hidden email]
http://www.kitware.com
(518) 881-4902

_______________________________________________
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