[vtkusers] New class for contouring unstructured grids

[Will Schroeder]

If you are interested in a new class for fast contouring of 3D unstructured
grids, read on.

The class VTK/Filters/Core/vtkContour3DLinearGrid is a threaded,
high-performance filter for generating isocontours from unstructured grids.
It is specialized for 3D linear cells: any combination of tetrahedra,
hexahedra, voxels, pyramids, and/or wedges. (Other cell types are skipped.)

In practice we routinely see 10-20x speed ups. In an extreme case we saw a
1000x speedup (a customer's tetrahedral mesh with over 500millions tets).
Of course this depends on the number of threads and the particulars of the
data so YMMV.

By default the class has a fast path where it just generates output
triangles and points, and the points are not merged (i.e., coincident
points exist in the output). Other available features, at the cost of some
speed, are point merging, attribute interpolation, and/or point normal
generation. (Note that for dense input meshes the fast path often produces
acceptable results; other options can be enabled as needed or in a
progressive rendering approach.)

The speed comes from 1) threading, 2) a new edge locator
(vtkStaticEdgeLocatorTemplate.h/.txx) which identifies coincident points by
sorting edge tuples (v0,v1), 3) templating, and 4) better and more
efficient algorithm design.

In particular,#2) above: contouring in VTK typically relies on point
locators to merge coincident points. This is not only a parallel computing
bottleneck, but the locator binning can execute very slowly when lots of
points fall into the same locator bin. (For example: an unstructured mesh
that resolves tiny flow features like a boundary layer etc.) The edge
locator eliminates this behavior. Furthermore, duplicate points are
identified by using a parallel sort of edge tuples using vtkSMPTools:Sort()
- much faster than the point locator's InsertUniquePoint().

The effect of threading on performance is modest - it doesn't scale all
that well on the tests we've tried. My guess is that the data bus is
saturated as the algorithm does a small amount of computation which can
produce a large amount of output. (Set the CMake variable
VTK_SMP_IMPLEMENTATION_TYPE to something other than Sequential- I use TBB -
to enable threading. See this blog
<https://blog.kitware.com/simple-parallel-computing-with-vtksmptools-2/> for
more information.)

Like any new algorithm I'm sure there are issues. If you are so inclined,
please try the filter and provide feedback. At some point we'll integrate
the algorithm into ParaView but it may be awhile as we are swamped :-)

Best,

-- 
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/vtkusers/attachments/20181102/98fc1380/attachment.html>