[vtk-developers] Polyhedral challenge

Wed Mar 24 22:00:15 EDT 2010

Hi Will,

It is a VTK polydata filter.  It uses the vtkCell operations for
clipping, contouring, and triangulation.  For all other computational
pieces that were needed, I wrote my own code that uses stl-based
containers.

A rough description of the algorithm is as follows:
1) clip scalars are generated for the input data, using the clip function
2) the input polydata cells are clipped
3) the input polydata cells are contoured to find out where the
freshly-cut edges are
4) the edge lines generated by the contouring are used to generate new
polygons that are triangulated and added to the dataset

Step 4 required around 1000 lines of code.  It consists of the
following sub-steps:
 a) the cut edges are sorted and joined end-to-end to create new polys
 b) the new polys are simplified by removing any vertices that have an
angle of 180 degrees
 c) the polys are oriented according to the cut-plane normal, to
ensure they have the correct sense
 d) checks are done to see if any of the created polys lie inside
other polys (I call this the "hole check")
 e) holes are dealt with by cutting between the outer and inner polygon
 f) the polys are converted into vtkPolygon cells and triangulated
 g) the triangles are added to the data set

Each of steps (a) through (f) is done in its own subroutine using
vtkstd::vector<vtkIdType> as the polygon container, and using
vtkPoints as the container for the points.

Originally I was hoping that I could write a routine that would always
give a watertight polydata as an output if it was given a watertight
polydata as input.  Unfortunately I didn't quite achieve that because
of (b) above.  Also, the triangulation step can produce some very
sharp triangles.

All in all it works good enough for my visualization needs, even with
concave inputs.  But it would need further tuning for use with FEM.

   David

On Wed, Mar 24, 2010 at 1:20 PM, Will Schroeder
<will.schroeder at kitware.com> wrote:
> David-
> This is good timing. Hua has been looking into the problem too. We came up
> with an initial, very limited solution and it will be good to have a more
> thorough approach. We are looking forward to seeing what you did.
> I'm curious, did you create a filter to do this? How did you implement it in
> VTK....
> Will
>
> On Wed, Mar 24, 2010 at 2:39 PM, David Gobbi <david.gobbi at gmail.com> wrote:
>>
>> Hi Will,
>>
>> I've finally completed my code for clipping closed polydata shapes and
>> creating new "cap" polygons so that the result is also a closed
>> polydata.  The solution was more complicated than I originally
>> thought.  After the branch I'll commit it to VTK.
>>
>>   David
>>
>>
>> On Thu, Feb 18, 2010 at 2:57 PM, Will Schroeder
>> <will.schroeder at kitware.com> wrote:
>> > Awesome David, simply great. You are ahead of us for now, but we will
>> > definitely need something like this soon. Can we ping you when we are
>> > ready?
>> >
>> > On Thu, Feb 18, 2010 at 3:04 PM, David Gobbi <david.gobbi at gmail.com>
>> > wrote:
>> >>
>> >> Hi Will,
>> >>
>> >> Have you and Hua done the "Clip" part of the cell implementation yet?
>> >> If not, I might have some code that will help.  I've been working on a
>> >> class for clipping of watertight polydata in VTK.  It does the capping
>> >> of the open end after a clip:
>> >>
>> >> - contouring the polydata at the clip plane to get the clip-edges of
>> >> the clipped polygons
>> >> - joining the new edge line segments into a one or more cap polygons
>> >> - identifying complex polygons, i.e. polygons with holes
>> >> - triangulating the polygons (*partly done*)
>> >>
>> >> The "triangulating" part is the only part that I haven't finished
>> >> (that's why I asked about Delaunay earlier).  I'm using ear-cut
>> >> triangulation, which only works for simple polygons, but other than
>> >> that everything is done.
>> >>
>> >>   David
>> >>
>> >>
>> >> On Thu, Feb 18, 2010 at 9:38 AM, Will Schroeder
>> >> <will.schroeder at kitware.com> wrote:
>> >> > Hua and I have made progress on adding a vtkPolyhedron cell to VTK.
>> >> > We
>> >> > have
>> >> > a wiki page describing the tasks (which will take some time
>> >> > to implement depending on our funding and
>> >> > schedule http://www.vtk.org/Wiki/VTK/Polyhedron_Support). We are
>> >> > using
>> >> > the
>> >> > interpolation method of mean value coordinates which Hua has already
>> >> > implemented, thus far it is a super algorithm. Comments are welcome.
>> >> > We are now starting the integration into vtkUnstructuredGrid. If you
>> >> > are
>> >> > interested let me know and at the appropriate point we can make our
>> >> > git
>> >> > repository available.
>> >> >
>> >> >
>> >> > On Thu, Jan 21, 2010 at 6:53 AM, Will Schroeder
>> >> > <will.schroeder at kitware.com>
>> >> > wrote:
>> >> >>
>> >> >> FYI-
>> >> >>
>> >> >> Hua Yang and I are adding a new cell type to VTK: the polyhedral
>> >> >> cell.
>> >> >> This is mainly to support our CFD friends who like to compute flow
>> >> >> solutions
>> >> >> using flux approaches (balance mass and energy in and out of a
>> >> >> region).
>> >> >>
>> >> >> One of the key questions is how to interpolate across the interior
>> >> >> of
>> >> >> such
>> >> >> a cell. In the past I have seen two typical approaches 1) tessellate
>> >> >> the
>> >> >> polyhedron into tetrahedra, and then use the tetrahedra to
>> >> >> interpolate;
>> >> >> and
>> >> >> 2) use a 1/r**2 (or similar weighting function) to interpolate from
>> >> >> the
>> >> >> cell
>> >> >> nodes to an interior point in the polyhedron. Both approaches have
>> >> >> problems
>> >> >> with continuity, etc.
>> >> >>
>> >> >> We are also researching other approaches. However in the interest of
>> >> >> completeness, if anybody has suggestions for alternatives we'd love
>> >> >> to
>> >> >> hear
>> >> >> about them.
>> >> >>
>> >> >> Will
>> >> >
>> >> >
>> >> >
>> >> > --
>> >> > William J. Schroeder, PhD
>> >> > Kitware, Inc.
>> >> > 28 Corporate Drive
>> >> > Clifton Park, NY 12065
>> >> > will.schroeder at kitware.com
>> >> > 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
>> >> >
>> >> > Follow this link to subscribe/unsubscribe:
>> >> > http://www.vtk.org/mailman/listinfo/vtk-developers
>> >> >
>> >> >
>> >> >
>> >> _______________________________________________
>> >> Powered by www.kitware.com
>> >>
>> >> Visit other Kitware open-source projects at
>> >> http://www.kitware.com/opensource/opensource.html
>> >>
>> >> Follow this link to subscribe/unsubscribe:
>> >> http://www.vtk.org/mailman/listinfo/vtk-developers
>> >>
>> >
>> >
>> >
>> > --
>> > William J. Schroeder, PhD
>> > Kitware, Inc.
>> > 28 Corporate Drive
>> > Clifton Park, NY 12065
>> > will.schroeder at kitware.com
>> > http://www.kitware.com
>> > (518) 881-4902
>> >
>
>
>
> --
> William J. Schroeder, PhD
> Kitware, Inc.
> 28 Corporate Drive
> Clifton Park, NY 12065
> will.schroeder at kitware.com
> http://www.kitware.com
> (518) 881-4902
>