[Paraview] Delaunay 3D filter too slow

Sat Sep 28 15:58:01 EDT 2013

庞庆源,

I found some spare time to look into this.

The test data set you provided defines a point cloud with spherical
topology. Your reader does import this geometric information (as
points), but provides no topology. In order for VTK and hence ParaView
to display anything, some kind of topology is needed. The simplest being
vertices as 0D topology, i.e. a dot per point. The patch attached does
exactly add that. With this, you can already see something in ParaView
when using your reader plugin to import the test data set.

You've been trying to triangulate your point cloud with spherical
topology with Delaunay3D, in vain. I could reproduce that. With a debug
build of ParaView, one notices thousands of warnings of kind "Unable to
factor linear system" being issued when trying to apply Delaunay3D
filter to your input.

The same actually happens when applying Delaunay3D filter to a sphere
source created with theta resolution 180 and phi resolution 90.
A few dozen warnings about being unable to factor a linear system are
raised. (On a side node: a debug build of ParaView master branch with
CMake option VTK_DEBUG_LEAKS:BOOL=ON reveals a memory leak in Delaunay3D
when applied to this densely meshed sphere.) The result, however, is
disappointing as the volume mesh has some gaps and rifts, not really a
smooth surface any more. So, you need to pursue another triangulation
approach.

Applying Delaunay2D filter instead produces at least a hemisphere,
almost instantly. I suspect, however, that a hemisphere is not good
enough.

You could resort to applying a Glyph filter with Glyph type "Sphere" and
otherwise default settings. That yields a coarse approximation of what I
guess you would like to achieve.

It might also be that class vtkSurfaceReconstructionFilter or class
vtkMarchingCubes or one of the filters from the pv-meshless plugin are
able to create the surface mesh, but I'm not too familiar with them to
say this with confidence or provide additional advice.

There have recently even been a few discussions on the VTK mailing list
regarding the general problem of triangulating point clouds with
spherical topology, see e.g.
http://markmail.org/message/fc3kjifkwtpggqai

But given that your points are not arbitrarily distributed over the
sphere, but in fact stored in your input file in a very regular and pre-
sorted way (180 points per latitude, latitude after latitude from pole
to pole) and given that the implied topology is very simple too (every
vertex has exactly 4 neighbors), it is not too hard to extend your
reader to have it create a smooth triangulation of the surface by simple
quads (connecting vertex i with i+1, i+181 and i+180) without involving
the help from additional VTK meshing classes.

Maybe someone else on the list can even tell you how to re-arrange your
data to fulfill the prerequisites for a structured grid data set for
which the triangulation is implicitly done by VTK.

Hope this helps,
Karl

庞庆源 wrote, On 27.09.2013 02:46:
> This is the source of my test plugin.Could you have a try?
> My paraview version is 4.0.1 ,built from source.
> 
> 
> 2013/9/27 Moreland, Kenneth <kmorel at sandia.gov <mailto:kmorel at sandia.gov>>
> 
>     I doubt that would make a difference. I just tried a bimodal
>     distribution using two point sources, and the filter still executed
>     in about the same amount of time.
> 
>     So what version of ParaView are you using? Are you using a binary
>     downloaded from paraview.org <http://paraview.org> or did you build
>     your own?
> 
>     -Ken
> 
>     From: 庞庆源 <pangqingyuan1991 at gmail.com
>     <mailto:pangqingyuan1991 at gmail.com>>
>     Date: Thursday, September 26, 2013 3:05 AM
>     To: Kenneth Moreland <kmorel at sandia.gov <mailto:kmorel at sandia.gov>>
>     Cc: "paraview at paraview.org <mailto:paraview at paraview.org>"
>     <paraview at paraview.org <mailto:paraview at paraview.org>>
> 
>     Subject: [EXTERNAL] Re: [Paraview] Delaunay 3D filter too slow
> 
>     My points are not Uniform distribution.They take from intersections
>     of 89 wefts and 180 warps.So the points are intensive at poles and
>     sparse at equator.Is this the problem?
> 
> 
>     2013/9/25 Moreland, Kenneth <kmorel at sandia.gov
>     <mailto:kmorel at sandia.gov>>
> 
>         That is strange. I cannot replicate your problem. I used a point
>         source to create 16020 random points in a sphere, and the
>         Delaunay triangulation took only about 2 seconds. My processor
>         might be a bit better than yours, but not anywhere near enough
>         to explain the difference.
> 
>         What version of ParaView are you using? Are you a binary
>         downloaded from paraview.org <http://paraview.org> or did you
>         build your own?
> 
>         -Ken
> 
>         From: 庞庆源 <pangqingyuan1991 at gmail.com
>         <mailto:pangqingyuan1991 at gmail.com>>
>         Date: Tuesday, September 24, 2013 10:29 PM
>         To: Kenneth Moreland <kmorel at sandia.gov <mailto:kmorel at sandia.gov>>
>         Subject: [EXTERNAL] Re: [Paraview] Delaunay 3D filter too slow
> 
>         in fact,I have only 16020 points for test.My cpu is AMD
>         Athlon(tm) II P320 Dual-Core Processor with 2.1GHz.How long will
>         it take in this case if I use one cpu to calculate?I have wait
>         for more than 10 minutes before stopping it.
> 
> 
>         2013/9/24 Moreland, Kenneth <kmorel at sandia.gov
>         <mailto:kmorel at sandia.gov>>
> 
>             Your options are probably either to wait or do something
>             else. Delaunay triangulation is a pretty heavyweight
>             operation and in general it is not trivial to impose a
>             topology on a collection of points.
> 
>             You might rethink whether you really need to create a solid
>             sphere in the first place. I'm guessing you have at least
>             around 100,000 points (or else Delaunay probably would not
>             be that slow). If you just render these points as a cloud of
>             points, you should get enough occlusion for it to look
>             pretty much like a sphere.
> 
>             -Ken
> 
>             From: 庞庆源 <pangqingyuan1991 at gmail.com
>             <mailto:pangqingyuan1991 at gmail.com>>
>             Date: Tuesday, September 24, 2013 5:01 AM
>             To: paraview <paraview at paraview.org
>             <mailto:paraview at paraview.org>>
>             Subject: [EXTERNAL] [Paraview] Delaunay 3D filter too slow
> 
>             I have a lot of points taking sample from a solid sphere.So
>             I want to use Delaunay 3D filter to render the shpere with
>             known scalars of the points.But it took me so much time.What
>             should I do?

-------------- next part --------------
A non-text attachment was scrubbed...
Name: Auto-create-a-vertex-for-every-point-in-input-file.patch
Type: text/x-patch
Size: 1093 bytes
Desc: not available
URL: <http://www.paraview.org/pipermail/paraview/attachments/20130928/5bd53b3e/attachment.bin>