[prev in list] [next in list] [prev in thread] [next in thread]
List: vtk-developers
Subject: Re: [vtk-developers] Voronoi2D
From: Will Schroeder <will.schroeder () kitware ! com>
Date: 2018-06-18 10:56:13
Message-ID: CAEiDrtU=OnEGT-S2zpR89dy2Gz8P4Dhn4ETgNFHn5R1UZu4N1g () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
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@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@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@kitware.com>
>>> To: vtk-developers <vtk-developers@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@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@kitware.com
http://www.kitware.com
(518) 881-4902
[Attachment #5 (text/html)]
<div dir="ltr"><div class="gmail_default" style="font-family:verdana,sans-serif">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.</div></div><br><div class="gmail_quote"><div dir="ltr">On Sat, Jun 16, 2018 at \
2:40 AM Chiranjib Sur <<a \
href="mailto:sur.chiranjib@gmail.com">sur.chiranjib@gmail.com</a>> \
wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 \
.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto">This is very \
interesting. Will the implementation of Delaunay triangulations API's be improved \
following this? <div dir="auto">I experienced Delaunay3D for large datasets is very \
slow. <br><br><div data-smartmail="gmail_signature" dir="auto">Thanks and \
regards,<br>Chiranjib<br><br>------<br>Using hand held device. Sorry for the typo, if \
any.</div></div></div><br><div class="gmail_quote"><div dir="ltr">On Sat, Jun 16, \
2018, 10:46 AM Andrew Maclean <<a href="mailto:andrew.amaclean@gmail.com" \
target="_blank">andrew.amaclean@gmail.com</a>> wrote:<br></div><blockquote \
class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex"><div dir="ltr"><div class="gmail_default" \
style="font-size:small">+1!<br></div><div class="gmail_default" \
style="font-size:small">I just had a play with it, the tests for <span \
style="font-size:13px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">Voronoi2D \
are really impressive.</span></div><br><div class="gmail_quote"><blockquote \
class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex">---------- Forwarded message ----------<br>From: Will \
Schroeder <<a href="mailto:will.schroeder@kitware.com" rel="noreferrer" \
target="_blank">will.schroeder@kitware.com</a>><br>To: vtk-developers <<a \
href="mailto:vtk-developers@vtk.org" rel="noreferrer" \
target="_blank">vtk-developers@vtk.org</a>><br>Cc: <br>Bcc: <br>Date: Fri, 15 \
Jun 2018 05:32:10 -0400<br>Subject: [vtk-developers] Voronoi2D<br><div \
dir="ltr"><div style="font-family:verdana,sans-serif">FYI I pushed in some code today \
that may be of interest to folks on this list:</div><div \
style="font-family:verdana,sans-serif"><br></div><div \
style="font-family:verdana,sans-serif">- vtkVoronoi2D - parallel Voronoi tessellation \
in 2D</div><div style="font-family:verdana,sans-serif">- vtkStaticCleanPolyData - \
faster, threaded clean poly data (we've seen anywhere from 50-150x on a 4 core \
laptop)</div><div style="font-family:verdana,sans-serif">- vtkStaticPointLocator2D - \
2D version of the fast, parallel vtkStaticPointLocator</div><div \
style="font-family:verdana,sans-serif">- vtkSpheres - an implicit function represents \
union of spheres (great for visualizing the Voronoi Flower error metric and related \
stuff like Delaunay spheres)</div><div style="font-family:verdana,sans-serif">- Some \
fun tests e.g. TestVoronoi2D2.py, which includes functions stretching numerical \
stability (lissajous, quarterDisk, Kuzmin) provided by David and Joachim \
Pouderoux).</div><div style="font-family:verdana,sans-serif"><br></div><div \
style="font-family:verdana,sans-serif">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,
<span style="background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">can</span> \
affect results).</div><div style="font-family:verdana,sans-serif"><br></div><div \
style="font-family:verdana,sans-serif">The point is if you have a request or see \
something amiss please let me know.</div><div \
style="font-family:verdana,sans-serif"><br></div><div \
style="font-family:verdana,sans-serif">Best,</div><div \
style="font-family:verdana,sans-serif">W</div><div \
style="font-family:verdana,sans-serif"><br></div><div \
style="font-family:verdana,sans-serif"><br></div><div><br></div>-- <br><div dir="ltr" \
class="m_6230582346032696214m_5211788639129198234m_-2046028812712904164gmail_signature"><div \
dir="ltr"><div>William J. Schroeder, PhD<br>Kitware, Inc. - Building the World's \
Technical Computing Software<br>28 Corporate Drive<br>Clifton Park, NY 12065<br><a \
href="mailto:will.schroeder@kitware.com" rel="noreferrer" \
target="_blank">will.schroeder@kitware.com</a><br><a href="http://www.kitware.com" \
rel="noreferrer" target="_blank">http://www.kitware.com</a><br>(518) \
881-4902</div></div></div></div> <br><br></blockquote></div><div><br></div>-- \
<br><div dir="ltr" class="m_6230582346032696214m_5211788639129198234gmail_signature" \
data-smartmail="gmail_signature">___________________________________________<br>Andrew \
J. P. Maclean<br><br>___________________________________________</div></div> \
_______________________________________________<br> Powered by <a \
href="http://www.kitware.com" rel="noreferrer noreferrer" \
target="_blank">www.kitware.com</a><br> <br>
Visit other Kitware open-source projects at <a \
href="http://www.kitware.com/opensource/opensource.html" rel="noreferrer noreferrer" \
target="_blank">http://www.kitware.com/opensource/opensource.html</a><br> <br>
Search the list archives at: <a href="http://markmail.org/search/?q=vtk-developers" \
rel="noreferrer noreferrer" \
target="_blank">http://markmail.org/search/?q=vtk-developers</a><br> <br>
Follow this link to subscribe/unsubscribe:<br>
<a href="https://public.kitware.com/mailman/listinfo/vtk-developers" rel="noreferrer \
noreferrer" target="_blank">https://public.kitware.com/mailman/listinfo/vtk-developers</a><br>
<br>
</blockquote></div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" \
class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div>William \
J. Schroeder, PhD<br>Kitware, Inc. - Building the World's Technical Computing \
Software<br>28 Corporate Drive<br>Clifton Park, NY 12065<br><a \
href="mailto:will.schroeder@kitware.com" \
target="_blank">will.schroeder@kitware.com</a><br><a href="http://www.kitware.com" \
target="_blank">http://www.kitware.com</a><br>(518) 881-4902</div></div></div>
_______________________________________________
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
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic